Return to lambda.sml CVS log

Up to [Research Unix] / researchv10no / cmd / sml / doc / examples

Annotation of researchv10no/cmd/sml/doc/examples/lambda.sml, revision 1.1.1.1

1.1       root        1: (* ----- An Interpreter for Call-by-Value lambda-calculus ----- *)
                      2: 
                      3: datatype ide = IDE of string
                      4: 
                      5: datatype term = VAR of ide | LAMB of ide * term | APPL of term * term
                      6: 
                      7: datatype env = ENV of ide -> value
                      8:      and value = CLOSURE of term * env
                      9: 
                     10: exception Unbound_var of string
                     11: 
                     12: val Arid = ENV(fn (IDE s) => raise Unbound_var s)
                     13: 
                     14: fun LookUp(ide, ENV f) = f ide
                     15: 
                     16: fun Extend(ide, value, env) =
                     17:       ENV(fn ide' => if ide'=ide then value else LookUp(ide',env))
                     18: 
                     19: fun Eval(VAR ide, env) = LookUp(ide,env) |
                     20:     Eval(lamb as LAMB _, env) = CLOSURE(lamb,env) |
                     21:     Eval(APPL(rator,rand), env) = Apply(Eval(rator,env),Eval(rand,env))
                     22: 
                     23: and Apply(CLOSURE(LAMB(bind,body),env),arg) =
                     24:       Eval(body,Extend(bind,arg,env))
                     25: 
                     26: fun i s = IDE s            (* abbreviation for identifiers *)
                     27: and v s = VAR(IDE s)       (* abbreviation for variables *)
                     28: 
                     29: infix *
                     30: fun f * g = APPL(f,g)      (* abbreviation for application *)
                     31: 
                     32: val I = LAMB(i"a",v"a")                       (* I a = a *)
                     33: val K = LAMB(i"a",LAMB(i"b",v"a"))            (* K a b = a *)
                     34: val S = LAMB(i"a",LAMB(i"b",LAMB(i"c",        (* S a b c = (a c) (b c) *)
                     35:            (v"a" * v"c") * (v"b" * v"c"))))
                     36: val D = LAMB(i"a", v"a" * v"a")               (* D a = a a *)
                     37: 
                     38: 
                     39: 
                     40: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.