# Index of /705/coursedir/fib

fib-untyped.txt contains an implementation in the untyped lambda calculus
of the Fibonacci function:
let rec fib n =
if n = 0
then 0
else if n = 1
then 1
else fib(n - 2) + fib(n - 1)
in fib
To run it on input n, put the contents of fib-untyped.txt in a file,
and follow it with
c_n
(lambda x. lambda y. y x)
(lambda x. x);
Then give the untyped lambda calculus interpreter the new file as
its input. The output should look like
(lambda y.
y
(lambda y'.
y'
(lambda y''.
y''
... (lambda x.x) ...)))
where the number of occurrences of lambda y -- with
some number of primes on y -- is fib n. (There was no reason that
the primes were necessary, but the lambda calculus interpreter adds them.)
The Linux/Mac OS X shell script fib-test automates the process of
creating the input to the untyped lambda calculus interpreter.
Running
./fib-test fib-untyped.txt n
puts the text described above in the file fib-test-output.txt.
For example, running
./fib-test fib-untyped.txt 3
will put the text
( /* beginning of fib code */
...
/* end of fib code */ )
(lambda s. lambda z. s(s(s z))) /* 3 */
(lambda x. lambda y. y x)
(lambda x. x);
in fib-test-output.txt. Giving this file to the untyped lambda calculus
interpreter should produce the output (formatted slightly differently)
(lambda y.
y
(lambda y'.
y'
(lambda x.x)))
because fib 3 = 2.