Alieniloquent

Earlier this fall I wrote a little functional programming language. However, the guts of it were not based on the lambda calculus. I used more of a denotational semantics approach to the evaluation, which worked fine. But, I still wanted to implement an actual lambda calculus interpreter.

So, now that I am done with school and have some free time, I threw a little something together. I used it as an introductory project to OCaml, and really enjoyed writing it.

So what is the lambda calculus, you might ask?

There are three basic concepts in lambda calculus. There are variables:

x

There are abstractions:

fn x. x

And there are applications:

f x

Applications are left associative so:

f x y

is the same as:

(f x) y

So for a more complicated example from the REPL:

> (fn f. fn x. f x) (fn y. y) z;
z

The first part declares a function which binds f and returns a function which binds x and returns the application of f to x. We pass to that the identity function (fn y. y) and the variable z. That all reduces to just z.

You can download my code here. I will be posting snippets of it in future posts. I will also be blogging as I extend it to add more features.