Term ::= Var| \Var.Term | Term Term % lambda terms | Num | true | false % numerical and boolean constants | Term Op Term % numerical ops and comparison | (Term,Term) | fst Term | snd Term % pairs | Term::Term % stream constructor | hd Term | tl Term % stream selectors | if Term then Term else Term % conditional | let Var = Term in Term % term with a local declaration | let fun f x = Term in Term % term with a local recursive definitionPlease define the datatype for the representation of the PCF terms above, the type environment and its operations, and the interpreter eval.
The interpreter eval should be environment-based (see Lecture Notes 18 and 19), and treat the scope correctly, i.e. it should have static scope. Please use the interepreter developed in Lecture Notes 18 and 19 (for the eager semantics) as a basis for your interpreter.
let fun nats n = n :: nats(n+1) % stream of natural numbers in let fun mult p = (hd (fst p) * hd (snd p)) :: mult (tl (fst p), tl (snd p)) % multiplication on streams in let fun facts k = 1::(mult (nats 1,facts 1)) % stream of factorials in hd(tl(tl(tl(facts 1))))Note: the functions nats, mult and facts are explained in Lecture Notes 16 and 17. In those LNs, "mult" is called "times" and its definition is in ML style i.e. it uses pattern matching). The definition given here is in PCF style. Note also that the function "facts", in the LNs, is without arguments. Here we need to use a dummy argument (k) just to respect the format of the let fun construct, which wants always an argument.
let x = 1 in let fun f y = x + y in let x = 2 in f 1
Please use ML val declaration to give these definitions, i.e.
val Facts = < ML expression of type term, representing the first PCF term above > val Test_static = < ML expression of type term, representing the second PCF term above >Note: the result of (eval Facts emptyenv) should be 6, and the result of (eval Test_static emptyenv) should be 2.
Please submit a hard-copy of the code by the deadline,
as usual. In addition, please submit the
electronic version (for testing purposes) by sending an
email to herescu@cse.psu.edu by the deadline.