This assignment has to be solved individually and handed in using the fire system before Monday 7 Dec (i.e. Sunday midnight).
This week you are going to implement (in Haskell or some other programming language) some programs that manipulate expressions in the language X which is described in the lecture notes.
There is a file (here) which contains a parser and some other useful programs generated by the BNF-converter. You should unpack it to a directory, move to that directory and run the make command. (If your GHC version is rather new, it will give errors about haskell98 being a hidden package. This can be fixed be re-running `bnfc chi.cf' .) There is a file called Eval.hs which 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 directory, you should also submit them. If you implement this in some other programming language you must write a parser yourself, it is probably easy to modify the execution of the BNF-converter so that it produces a parser for your programming language.
Implement the substitution operation which is used to define the semantics of X.
Implement a function which replaces all occurrences of a let-expression with an application (this is described in the file). Notice that the grammar for X in the file is extended compared with the lecture notes (in that it contains local definitions).
Implement a function which works like a specialized case-expression for natural numbers in X. The function is called casenat and is defined in the file Eval.hs.
Implement functions which converts a positive integer in Haskell to its representation as a natural number in X (in both directions).
The BNF-converter is a program developed in the CS department in Gothenburg by Markus Forsberg and Aarne Ranta et al. It takes a grammar and generates a parser and prettyprinter in various languages. It is currently able to generate C, C++, C#, F#, Haskell, Java, and OCaml, as well as XML representations. A wonderful tool which relieves the compiler writer from many tedious tasks!