Definitions (substitutions , pretty )

Results (collapse reduce )

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
Licensed with the ZLIB license. See source code for details.

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:

The 'Run' button will compile into JavaScript and run it
The 'Reduce' button will use alpha conversion, beta reduction, and eta conversion to simplify it
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

IO Monad

If you make an IO monad, a "Step" button will appear that you can use to step through your code. Try testM1-testM10 to see it. Just run one of the tests and Click the "Step" button that appears until you see the final result.
The "stepIO" function in lc.js is the driver for the io monad. The "Step" button calls it with the queued commands in the current IO monad and the latest return value. If there is more computation left, it returns a two-element array containing the rest of the command list and the latest return value otherwise, it returns a one-element array containing only the final return value.
A "real" environment would repeatedly call stepIO until it reaches the final value. This is just a first crack at an IO monad. It's relatively efficient, because it uses difference lists, but the main point is that it demonstrates how to do IO without side effects.

Have fun!
Bill Burdick (you can send me mail at bill dot burdick on gmail)

To do

save button

true = \x y . x false = \x y . y # Y combinator Y = \g . (\x . g (x x)) \x . g (x x) rec = \f . f (Y f) # rec = \f . f f # lists # using false as "nil" in lists, so you use a list like this: # DUMMY can be anything, but it needs to be there # here's how you use a list: # aList (\h t DUMMY . {list-case}) {empty-case} # If the list is not empty, h and t are the head and tail of the list and it returns list-case. DUMMY is not used, but needs to be there # If the list is empty, it returns empty-case # these defs are required by the pretty-printer: cons, nil, head, tail cons = \a b f . f a b nil = \x y . y head = \l . l \h t . h tail = \l . l \h t . t null = \l . l (\h t D . false) true last = rec \last l . l (\h t D . null t h (last t)) nil append = rec \append l1 l2 . l1 (\h t D . cons h (append t l2)) l2 reverse = \l . (rec \rev l res . l (\h t D . rev t (cons h res)) res) l nil # list constructor: list 1 , 2 , 3 end # first attempt, using recursive 'list' definition # #list = (rec \list rest item if-continue . if-continue (list (cons item rest)) (reverse (cons item rest))) nil #, = true #end = false # # second attempt, using "post-processing" with reverse #[ =(]= \item f . f (cons item nil) #, =.= \l item f . f (cons item l) #] =)= reverse # # current constructor # no post processing # also allows [1, 2, 3 | REST ] (like Prolog) [ =(]= \item c . c \rest . cons item rest , =.= \f item c . c \rest . f (cons item rest) ] =)= \f . f nil | =.= \f rest g . f rest ident = \x . x 1f = \1 f . f 1 get = \f . f ident test8 = last \f . f 1 \g . g 2 nil test9 = last (cons 1 (cons 2 nil)) test1 = (\f . f a) (\x . x) test2 = 1f 1 ident test3 = head (cons 1 nil) test4 = head (tail (cons 1 (cons 2 nil))) test5 = get (1f a) test6 = (\a b c . a (b c)) ident ident 1 test7 = ident 4 puts = \x . #strict puts x puts2 = \x . #lazy putsl x test10 = puts2 (ident 3) # difference lists dl = \list . append list dlAppend = \da db list . da (db list) dlList = \dl . dl nil # simple IO monad getCmdVal = \cmd . cmd ident makeIO = \cmds f . f cmds getCmds = \m . m (\cmds . cmds) getAllCmds = \m . dlList (getCmds m) returnCmd = \x f . f x return = \x . makeIO (dl [(returnCmd x)]) bindCmd = \action f . f action getBindAction = \cmd . cmd ident bind = \io f . io \cmds . makeIO (dlAppend cmds (dl [(bindCmd f)])) alertCmd = \thing f . f thing alert = \thing . makeIO (dl [(alertCmd thing)]) promptCmd = \prompt f . f prompt prompt = \prompt . makeIO (dl [(promptCmd prompt)]) testM1 = return 3 testM2 = alert hello testM3 = prompt nil testM4 = bind (prompt [Please, type, something]) \x . alert x testM5 = bind (prompt One) \x . bind (alert x) \y . bind (prompt Two) \z . bind (alert z) \q . return [x, z] testM6 = bind (alert one) \x . bind (prompt Two) \y . alert y testM7 = bind (alert one) \x . return 3 testM8 = bind (alert one) \x . bind (alert two) \y . bind (alert three) \z . return z testM9 = bind (alert hello) \x . bind (prompt Goodbye) \y . return y testM10 = bind (prompt One) \x . bind (bind (prompt Two) \y . return y) \z . return x sunday = \sun mon tue wed thu fri sat . sun monday = \sun mon tue wed thu fri sat . mon tuesday = \sun mon tue wed thu fri sat . tue wednesday = \sun mon tue wed thu fri sat . wed thursday = \sun mon tue wed thu fri sat . thu friday = \sun mon tue wed thu fri sat . fri saturday = \sun mon tue wed thu fri sat . sat dayName = \day . day Sunday Monday Tuesday Wednesday Thursday Friday Saturday nextDay = \day . day monday tuesday wednesday thursday friday saturday sunday prevDay = \day . day saturday sunday monday tuesday wednesday thursday friday testDay = dayName (nextDay monday) testMName = bind (alert Please-enter-your-name) \_ . bind (prompt name) \nm . bind (return [nm, Jr]) \nm . alert [Your, actual, name, is, nm] #define puts i32 @puts(i8* nocapture) nounwind #define putsl i32 @putsl(i8* nocapture) nounwind

Definitions (substitutions , pretty )

Results (collapse reduce )Clear

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

IO Monad

To do

Results (collapse reduce )