Lambda Calculus Parser-Reducer
$ 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.
@@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
$ 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