Project Description
a simple lambda-calculus interpreter implemented in F#
using NUnit as a test framework and FParsec for parsing

Checks the evaluation for known identifiers (expressions assigned to an name)

the sources are provided for use with VS2012 RTM and .net 4.5 - the FParsec.dll was compiled with VS2012 RC and is provided in the sources, AFAIK the nuget-version will not work at the moment

Syntax

Atoms = one single lower letter and any number (including zero) of digits
Identifiers = beginning with a upper letter and ending in any number of letters or digits
Single Atom or Identifier is an Expression
Application (with or without parentheses) is an Exprewssion (for example "ab", "Id b")
Abstraction (\[atomName].Body where Body is an expression) is an Expression
Assignment: Identifier := Expression
Comparision: Expression == Expression
Evaluation: Expression
Command: ?command
where command:
  • quit = exitst the console
  • load file = loads the file as text and interprets it line by line

Sample run for simple number-arithmetic

LAMBDA CALCULUS INTERPRETER
===========================


>>> ?load numbers
\abf.(fab)
== [MkPair]

\ab.a
== [Fst]

\ab.b
== [Snd]

\nfx.(f(nfx))
== [Succ]

\fx.x
== [Snd, N0]

\fx.(fx)
== [N1]

\fx.(f^{2} x)
== [N2]

\fx.(f^{3} x)
== [N3]

\fx.(f^{4} x)
== [N4]

\fx.(f^{5} x)
== [N5]

\fx.(f^{6} x)
== [N6]

\fx.(f^{7} x)
== [N7]

\fx.(f^{8} x)
== [N8]

\fx.(f^{9} x)
== [N9]

\nmfx.(nf(mfx))
== [Add]

\nm.(n\_mfx.(mf(_mfx))\fx.x)
== [Mult]

\pf.(f(p\ab.b)\fx.(f(p\ab.bfx)))
== [Shift]

\f.(f\fx.x\fx.x)
== [Init]

\n.(n\pf.(f(p\ab.b)\fx.(f(p\ab.bfx)))\f.(f\fx.x\fx.x)\ab.a)
== [Pred]

>>> Mult N9 N8
\f_x.(f^{72} _x)

>>> Sqr := \n.Mult n n
\n.(n\_mfx.(nf(_mfx))\fx.x)
== [Sqr]

>>> Sqr N9
\f_x.(f^{81} _x)

>>> SqrMinusOne := \n.Pred (Sqr n)
\n.(n\_mfx.(nf(_mfx))\fx.x\pf.(f(p\ab.b)\fx.(f(p\ab.bfx)))\f.(f\fx.x\fx.x)\ab.a)
== [SqrMinusOne]

>>> SqrMinusOne N9
\fx.(f^{80} x)

>>> F := \n.Pred (Sqr (Add n N2))
\n.(n\_mfx.(nf(f^{2} (_mfx)))\f__x.(nf(f^{2} (nf(f^{2} __x))))\pf.(f(p\ab.b)\fx.
(f(p\ab.bfx)))\f.(f\fx.x\fx.x)\ab.a)
== [F]


>>> F N3
\fx.(f^{24} x)

>>>?quit

Last edited Aug 17, 2012 at 9:06 AM by CKoenig, version 9