[Home]

Lambda Calculus Parser-Reducer

[View the Source Code on Github]

$ echo '@@def ++.(@n. @f x.f (n f x)) @@churchnums.++ 3' | ./lambd
@@churchnums.4

The lambda calculus was a special interest of mine for a few years in high school and college. I wrote a little reducer program for it in Python the summer of 2014, which I recently reimplemented in Haskell, increasing performance by a great deal.

The parser uses @ for \lambda and adds several syntactic-sugar extensions (flagged by @@):

@@c introduces a comment: @@c.(This is a comment)

@@churchnums replaces numeric free variables in an expression with the corresponding Church numerals.
For example, @@churchnums.+ 1 3 would become:

(@3.(@1.+ 1 3) (@f.f)) (@f.@x.f (f (f x)))

@@def reorders a application to an abstraction for easier reading:
@@ def x.(y z) x z becomes (@x.x z) (y z)

@@include allows for including other .lambd files:

$ echo '@@include standard/logic.| #t #f`' | ./lambd
@@churchnums.@t.@f.t

@@list assists with list construction:
@@list e.x y z becomes @e.@f.f x(@f.f y(@f.f z e))

@@b isn’t as necessary in the Haskell version, but allows an expression to be marked for reduction before being applied.


© Emberlynn McKinney