This assignment has to be solved individually and handed in using the fire system before Monday 14 Dec.
This week you are going to implement (in Haskell or some other programming language) two versions of the X language which is described in the lecture notes. Use the same tar-file as for last week's assignment. The file called Eval.hs contains a skeleton to be filled in. This is also the file you should submit to fire.
If your solution depends on other programs than the ones provided in the tar-file, you should also submit them.
If you do not have a solution for Assignment X, part I, you can use the Haskell file in the bottom of this page (there is a download arrow to the right).
Write an interpreter for X! The program should contain the following parts:
A function parse :: String -> Exp which parses the input and generates an abstract syntax tree.
A function pp :: Exp -> String which prints a program in concrete syntax.
A functon evaltot :: Exp -> Exp which evaluates the input to its fully evaluated form. It should use the function eval :: Exp -> Exp which computes to weak head normal form (see the lecture notes).
An example which shows that evaltot works together with pp and parse.
Now you should change the interpreter above so that it implements the language X-PRF described in this week's exercises! You don't have to write a parser/pretty printer for this language. The implementation should contain the following parts:
A type PExp which is a modification of Exp. Remove all constructors except the ones for lambda, application, variables and constants. Then you add an operator for primitive recursion, i.e. you add a syntactic expression primrec e g f, where e, g and f are expressions in X-PRF. This program is computed by first computing the value of e. If the value is Z then the value of the program is equal to the value of g. Otherwise, if the value of e is (Succ a) then the value of the program primrec e g f is equal to the value of f a (primrec a g f).
A function evalp :: PExp -> PExp which computes the head normal form of its input.
A function evaltotp :: PExp -> PExp which computes the argument to its fully evaluated form.
An example which tests evaltotp.