User guide

216 CHAPTER 13. EXAMPLE PROGRAMS
13.5 Lambda Evaluator
The following program is a simple parser and evaluator for lambda expressions.
GET "libhdr"
MANIFEST {
// selectors
H1=0; H2; H3; H4
// Expression operators and tokens
Id=1; Num; Pos; Neg; Mul; Div;Add; Sub
Eq; Cond; Lam; Ap; Y
Lparen; Rparen; Comma; Eof
}
GLOBAL {
space:200; str; strp; strt; ch; token; lexval
}
LET lookup(bv, e) = VALOF
{ WHILE e DO { IF bv=H1!e RESULTIS H2!e
e := H3!e
}
writef("Undeclared name %c*n", H2!bv)
RESULTIS 0
}
AND eval(x, e) = VALOF SWITCHON H1!x INTO
{ DEFAULT: writef("Bad exppression, Op=%n*n", H1!x)
RESULTIS 0
CASE Id: RESULTIS lookup(H2!x, e)
CASE Num: RESULTIS H2!x
CASE Pos: RESULTIS eval(H2!x, e)
CASE Neg: RESULTIS - eval(H2!x, e)
CASE Add: RESULTIS eval(H2!x, e) + eval(H3!x, e)
CASE Sub: RESULTIS eval(H2!x, e) - eval(H3!x, e)
CASE Mul: RESULTIS eval(H2!x, e) * eval(H3!x, e)
CASE Div: RESULTIS eval(H2!x, e) / eval(H3!x, e)
CASE Eq: RESULTIS eval(H2!x, e) = eval(H3!x, e)
CASE Cond: RESULTIS eval(H2!x, e) -> eval(H3!x, e), eval(H4!x, e)
CASE Lam: RESULTIS mk3(H2!x, H3!x, e)
CASE Ap: { LET f, a = eval(H2!x, e), eval(H3!x, e)
LET bv, body, env = H1!f, H2!f, H3!f
RESULTIS eval(body, mk3(bv, a, env))
}
CASE Y: { LET bigf = eval(H2!x, e)
// bigf should be a closure whose body is an
// abstraction eg Lf Ln n=0 -> 1, n*f(n-1)
LET bv, body, env = H1!bigf, H2!bigf, H3!bigf
// Make a closure with a missing environment
LET yf = mk3(H2!body, H3!body, ?)
// Make a new environment including an item for bv
LET ne = mk3(bv, yf, env)
H3!yf := ne // Now fill in the environment component
RESULTIS yf // and return the closure
}
}