A technical post, after a long time. For the past few days, I’ve been working on a lambda calculus reduction machine; which I’ve named L. The code is up at http://github.com/sanjoy/L.

I’ve tried to the internals as brain-dead and trivial as possible; more as a reflection on my incompetence than anything else. I don’t know, for instance, what a W.H.N.F. is, and neither does my code.

The (normal order) evaluation process is quite naive; it (I’ve used bison and flex) builds a binary tree from the expressions and then lazy-evaluates them (i.e. it evaluates only the arguments which need evaluating). This is more of a correctness issue than an efficiency feature – some halting expressions may have sub-expressions which are non-halting; I don’t want L to halt on them.

The memory management is quite dumb as of now; I’ve used a memory pool which essentially mmaps pages to /dev/zero and then does a bump-pointer-allocation dance. Things may be done more intelligently (right now I don’t even free any memory); and so they will be done. Soon.

Edit: L now has a basic (non-moving) garbage collector.

As a side-note, I just discovered how easy it is to implement a basic (linked) list on L:

:Zero = (L a b . b);
:Cons = (L value prev . (L x . :IfThenElse x value prev));
:IfThenElse = (L a b c . a b c);
:True = (L t f . t);
:False = (L t f . f);
:Null = (L n . n);
:One = (L f x . f x);
:Two = (L f x . f (f x));
:Car = L a . a :True;
:Cdr = L a . a :False;

Once you’ve entered the above you can do things like:

:List = [:Cons :One :Null];
:List = [:Cons :Two :List];
[:Car :List]; (Will prompt `L f x . f (f x)')
:List = [:Cdr :List];
This entry was posted in Rest. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s