Alieniloquent

Alonzo Church invented the lambda calculus. He also figured out how to encode many kinds of data as lambda expressions. Take your simple booleans, for example.

This is true:

fn x y. x

And this is false:

fn x y. y

That makes the identity function the if then else construct:

> (fn p. p) (fn x y. x) a b;
a
> (fn p. p) (fn x y. y) a b;
b

And similarly you can get a logical and:

> (fn p. p) ((fn p q. p q p) (fn x y. x) (fn x y. x)) a b;
a
> (fn p. p) ((fn p q. p q p) (fn x y. x) (fn x y. y)) a b;
b
> (fn p. p) ((fn p q. p q p) (fn x y. y) (fn x y. x)) a b;
b

Fiddling around with these church booleans revealed several bugs in my code, which I’ve fixed. I’ve additionally added a new node to the parse tree to represent the () grouping that is typed into the code so that when it is formatted for display it looks better.

You can get the newest code here.

One of the first things I wanted to do to improve the readability of my language was to add the currying of function parameters. Since it is such a common pattern to have three or four abstractions right in a row to bind variables, there is a syntax for expressing them more consisely.

So this:

fn x. fn y. fn z. x y z

Becomes this:

fn x y z. x y z

Adding the code do this was nearly trivial, and all in the parser. First I wrote a function that given a list of variables and an expression for the body, would be able to construct the parse tree for a curried function:

let curry ids body =
  List.fold_right (fun id expr -> Abstraction(id, expr)) ids body

Then I took the existing production for recognizing expressions:

expr:
  aexprs {apply $1}
| FN VAR PERIOD expr {Abstraction ($2, $4)}
;

And turned it into this:

expr:
  aexprs {apply $1}
| FN ids PERIOD expr {curry $2 $4}
;

ids:
  VAR {[$1]}
| VAR ids {$1::$2}
;

That ids production is using the OCaml :: operator which performs the cons operation. So as I recurse on the right, I’m building up a list and consing each new id onto it all the way up.

And just like that I’ve added currying to my language.

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.