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
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.
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
: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];