Implementing a non-recursive fibonacci on the lambda-calculus and testing it on Optlam.js.

gistfile1.txt

(This is a response to @chi and @Tom Ellis on [this post](http://stackoverflow.com/questions/31707614/why-are-%CE%BB-calculus-optimal-evaluators-able-to-compute-big-modular-exponentiation).)

This non-recursive fib implementation, in Haskell:

    import Prelude hiding (pred)

    data Nat = Succ Nat | Zero deriving Show

    pred (Succ pred) = pred
    pred Zero        = Zero

    fold (Succ pred) succ zero = succ (fold pred succ zero)
    fold Zero succ zero        = zero

    add a b = fold a Succ b

    fromInt 0 = Zero
    fromInt x = Succ (fromInt (x-1))

    toInt x = fold x (+ 1) 0

    fib n = fold n fib' id (pred n) where
        fib' rec (Succ p) = add (rec p) (rec (pred p))
        fib' rec Zero     = Succ Zero

    main = print $ toInt (fib (fromInt 30))

Translates roughtly to the following expression on the lambda calculus:

    fib = (λa.(a(λbc.(c(λdefg.(bef(b(e(λhi.i)(λhij.(j(λk.(kij)))))fg)))(λdef.(ef))))
        (λb.b)(a(λbcd.(c(λe.(ecd))b))(λbc.(c(λd.(dbc))))(λbc.c)(λbcd.(d(λe.(ecd)))))))

Note the term must be non-recursive because otherwise we wouldn't be able to
find an EAL type to it to use Optlam. Also, it is a little inflated as it
converts from church-naturals to scott-naturals for convenience. Testing it on
Optlam.js, we can attest it is indeed exponential. See the results below:

Fib 1:
--------------
Result       : 1 (church encoded)
Time         : 0s
Stats        : {"iterations":67,"applications":29,"used_memory":954}


Fib 2:
--------------
Result       : 2 (church encoded)
Time         : 0.001s
Stats        : {"iterations":340,"applications":163,"used_memory":1548}


Fib 3:
--------------
Result       : 3 (church encoded)
Time         : 0.002s
Stats        : {"iterations":772,"applications":376,"used_memory":2970}


Fib 4:
--------------
Result       : 5 (church encoded)
Time         : 0.004s
Stats        : {"iterations":1541,"applications":755,"used_memory":5526}


Fib 5:
--------------
Result       : 8 (church encoded)
Time         : 0.001s
Stats        : {"iterations":2873,"applications":1412,"used_memory":10116}


Fib 6:
--------------
Result       : 13 (church encoded)
Time         : 0.001s
Stats        : {"iterations":5248,"applications":2585,"used_memory":18576}


Fib 7:
--------------
Result       : 21 (church encoded)
Time         : 0.003s
Stats        : {"iterations":9416,"applications":4645,"used_memory":33624}


Fib 8:
--------------
Result       : 34 (church encoded)
Time         : 0.004s
Stats        : {"iterations":16731,"applications":8264,"used_memory":60552}


Fib 9:
--------------
Result       : 55 (church encoded)
Time         : 0.007s
Stats        : {"iterations":29485,"applications":14578,"used_memory":108036}


Fib 10:
--------------
Result       : 89 (church encoded)
Time         : 0.016s
Stats        : {"iterations":51634,"applications":25551,"used_memory":191556}


Fib 11:
--------------
Result       : 144 (church encoded)
Time         : 0.028s
Stats        : {"iterations":89926,"applications":44532,"used_memory":337302}


Fib 12:
--------------
Result       : 233 (church encoded)
Time         : 0.041s
Stats        : {"iterations":155873,"applications":77239,"used_memory":590634}


Fib 13:
--------------
Result       : 377 (church encoded)
Time         : 0.075s
Stats        : {"iterations":269045,"applications":133393,"used_memory":1028682}


Fib 14:
--------------
Result       : 610 (church encoded)
Time         : 0.152s
Stats        : {"iterations":462640,"applications":229492,"used_memory":1783350}


Fib 15:
--------------
Result       : 987 (church encoded)
Time         : 0.278s
Stats        : {"iterations":792854,"applications":393468,"used_memory":3078522}


Fib 16:
--------------
Result       : 1597 (church encoded)
Time         : 0.394s
Stats        : {"iterations":1354623,"applications":672523,"used_memory":5294394}


Fib 17:
--------------
Result       : 2584 (church encoded)
Time         : 0.593s
Stats        : {"iterations":2308051,"applications":1146276,"used_memory":9074160}


Fib 18:
--------------
Result       : 4181 (church encoded)
Time         : 1.144s
Stats        : {"iterations":3922690,"applications":1948805,"used_memory":15504876}


Fib 19:
--------------
Result       : 6765 (church encoded)
Time         : 1.822s
Stats        : {"iterations":6651682,"applications":3305549,"used_memory":26419428}


Fib 20:
--------------
Result       : 10946 (church encoded)
Time         : 3.213s
Stats        : {"iterations":11255717,"applications":5595024,"used_memory":44904204}

Obvious conclusion: the abstract algorithm is not magic.