001    // Copyright 2007 Waterken Inc. under the terms of the MIT X license
002    // found at http://www.opensource.org/licenses/mit-license.html
003    package org.waterken.factorial;
004    
005    import org.ref_send.promise.Eventual;
006    import org.ref_send.promise.Promise;
007    
008    /**
009     * A tail recursive factorial implementation.
010     */
011    public final class
012    Factorial {
013        private Factorial() { /* no instance interface */ }
014        
015        /**
016         * Computes a factorial.
017         * @param _ eventual operator
018         * @param n <code>&gt;= 0</code>
019         * @return promise for the factorial of <code>n</code>
020         */
021        static public Promise<Integer>
022        make(final Eventual _, final int n) {
023            if (n < 0) { return Eventual.reject(new Exception()); }
024            /*
025             * We'll simulate tail recursive calls by doing eventual invocations of
026             * our loop function. Since the call is eventual, the current stack
027             * frame is popped right away and the loop's stack frame isn't created
028             * until the next event loop turn. The same trick is used inside the
029             * loop itself. The chain of promises produced by these calls also
030             * collapses during each event loop turn, so that there's always only
031             * a constant number of objects referenced. The efficiency of this
032             * probably isn't as good as in a VM designed for tail recursion, but
033             * may be good enough for some purposes.
034             */
035            final Recursion loop_ = _._(new Recursion() {
036                public Promise<Integer>
037                apply(final Recursion tail_, final int i, final int acc) {
038                    if (i == 0) { return Eventual.ref(acc); }
039                    return tail_.apply(tail_, i - 1, i * acc);
040                }
041            });
042            return loop_.apply(loop_, n, 1);
043        }
044    
045        /**
046         * The inner loop of a tail recursive factorial implementation.
047         */
048        static public interface
049        Recursion { Promise<Integer> apply(Recursion tail_, int i, int acc); }
050    }