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