(C) Ralf Lämmel, Andrei Varanovich, University of Koblenz Landau
Logistics
- Course site
- Date published: 20 Jan 2012
- Deadline SVN: 25 Jan 2012 (noon)
- SVN: https://svn.uni-koblenz.de/softlang/main/courses/plt1112/students + group name
- Present your solution with your own system.
- See the lab assistant's instructions for logistics.
Assignment
The following tasks require the following skills:
- recursive function definitions
- data-type declarations
- use of Eq, Ord, Show potentially
- everything else as of the previous assignment
1st option
Declare a data type for the syntax of NB. Write a predicate (i.e., a Boolean function) that determines whether a given NB term is in normal form. Further, implement the evaluation rules and the type system. To this end, you need recursive functions that presumably use the Maybe data-type constructor—-because these are partial functions. (That is, not every term is well-typed and ill-typed terms can get stuck, in which case you need to return Nothing.)
2nd option
Declare a data type for the syntax of set-theoretic operations union, intersection, difference, empty, and singleton set. Make sure that the syntax (and hence the data type) is polymorphic. That is, the data type must be parametric in the element type of the set. Define a function eval to interpret expressions over the syntax. You can reuse a module for set-theoretic operations. In particular, module Data.Set comes with Haskell.
3rd option
Declare a data type for the syntax of arithmetic expressions such that the following forms are supported: literal (Int); unary negation; binary addition. Further define a data type for the syntax of a stack machine with fitting operations: push an Int; apply unary negation to the top-of-stack (TOS); apply binary addition to TOS and second TOS. Define a function that "transforms" an arithmetic expression into a list of stack operations.