# Lambda Calculus compiler and interpreter (now with an IO Monad -- see below!)

Copyright (C) 2011, Bill Burdick, Tiny Concepts: http://tinyconcepts.com/fs.pl/lambda.fsl

Use the text field below to enter Lambda Calculus expressions. You can use normal Lambda Calculus syntax, with \ meaning λ, but you have to separate your variables with spaces (click edit on any of the definitions for an example). Try testing it out with this (you need to hit enter after you click this): (\x y . x) 1 2

You can define terms using NAME = EXPR. Try this: pickThird = \x y z . z

You can evaluate lambda calculus expressions in 3 ways:
1. The 'Run' button will compile into JavaScript and run it
2. The 'Reduce' button will use alpha conversion, beta reduction, and eta conversion to simplify it
3. The 'VM' button will compile it into byte code and display another 'Run' button you can use to run it (the VM is still a work-in-progress)
The evaluator displays lists for 'Run' (of the first kind) and 'Reduce' results, but not VM's 'Run' results, yet. It cannot display detailed function results of other types for 'Run' (both kinds), but it can for Reduce. Eventually, the VM will display fully detailed results, just like 'Reduce' can.
You can modify the parser in these ways:
• You can make your definition a token to the parser using
NAME =.= EXPR
this means that you won't need spaces around NAME. Good for punctuation, etc.
• You can make your definition a grouping token with
NAME =(CLOSE= EXPR
and
CLOSE =)= EXPR
(for the corresponding closing token).
I use these in the example definitions to create an array-like syntax for lists, using normal Lambda Calculus functions. This demonstrates a way to define functions that act like syntactic sugar. It's really not sugar, though; these are real functions but the point of them is to make things more convenient for the programmer, like syntactic sugar does: [1,2,3] is the same as saying cons 1 (cons 2 (cons 3 nil)) and [1,2|list] is the same as cons 1 (cons 2 list) (like in Prolog). The definitions of '[', ',', '|', and ']' are:
[ =(]= λitem c . c λcont rest . cons item rest
, =.= λf . λitem c . c λcont rest . f true (cons item rest)
] =)= λf . f false nil
| =.= λf rest g . f false rest