Project Description
Introduced by Alonzo Church and his student Stephen Cole Kleene in the 1930s to
study computable functions.
A (very simple) formal system for defining functions and their operational meanings,
yet is shown to be as powerful as other systems.

This project aims to be a journey of discovery from the foundations of computing to the first commercial functional language on an industrial strength platform.


Recommended Reading
Programming F#
Lambda-Calculus, Combinators, and Functional Programming

Lambda Calculus Interpreter:

Lambda Calculus interpreter
> (λx.x) (λy.y)

Church Numerals
Lambda Calculus interpreter
> (λf.λx.x)
> (λn.λf.λx.(f (n f x))) (λf.λx.x)
(λf.(λx.(f x)))
> (λn.λf.λx.(f (n f x))) (λf.λx.(f x))
(λf.(λx.(f (f x))))
> (λn.λf.λx.(f (n f x))) (λf.λx.(f (f x)))
(λf.(λx.(f (f (f x)))))
> (λn.λf.λx.(f (n f x))) (λf.λx.(f (f (f x))))
(λf.(λx.(f (f (f (f x))))))

Lambda Calculus interpreter
> (λm.λn.λf.λx.((m f) (n f x))) (λh.λx.(h (h x))) (λg.λx.(g (g (g x))))
(λf.(λx.(f (f (f (f (f x)))))))
> (λm.λn.λf.λx.((m f) (n f x))) (λh.λx.(h (h (h (h x))))) (λg.λx.(g (g (g (g (g (g x)))))))
(λf.(λx.(f (f (f (f (f (f (f (f (f (f x))))))))))))

Last edited Sep 9, 2009 at 11:23 PM by holoed, version 16