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

  (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.
     (lambda y'.
        (lambda 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.

  ./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.
     (lambda y'.
        (lambda x.x)))

because fib 3 = 2.