Submit this Haskell file with the questions completed.
**What you can use.** In this assignment, you can use anything from the lectures, the given Haskell file (including what's imported) and anything in the Prelude. Nothing more though. The first two import lines at the beginning of the file can be ignored. They're just for the parser. The next two are useful but you don't need to use them.
**Debugging.** You might find the debugger useful. It's imported above. It's quite easy to use the basic tracing facility. See the Haskell Hierarchical Libraries documentation for info on how to use it:
https://downloads.haskell.org/~ghc/latest/docs/html/libraries/
The assignment is to implement the evaluator for the language L discussed in class. You should review the notes from that class. There is also a complete description of the language in this file.
## Description of L
Expressions (abstract and concrete syntax):
%x.e -- lambda abstraction, like \x->e in Haskell
e e' -- application
x,y,z -- variables
succ, pred, ifzero, 0, 1, 2....
Values:
0, 1, 2, 3,...
%x.e
succ, pred, ifzero
ifzero e
ifzero e e
Evaluation: e ==> v means e evaluates to value v. The rules below specify how to evaluate.
For an algorithmic view, you can read the rules bottom-up. E.g. the second rule can be read as saying that to evaluate an application expression e e', first evaluate e, and if you get a value of the form %x.b, continue by evaluating b[e'/x], and if that results in a value v, return that as the result of evaluating e e'.
There's a more algorithmic presentation of evaluation in the lectures notes. There are a few small differences, so please use the definition below as the specification for your evaluator.
-- QUESTION 1:
--
-- subst x e e': substitute e for all "free" occurrences of (Var x) in
-- e'. "Free" means that the variable it is not declared by a
-- surrounding %. For example, in the expression
--
-- x (%x. x (%y.xz)) (%y.x)
-- there are 5 occurrences of x. The first is "free". The second is
-- the parameter for the % expression and is never substituted for.
-- The third and fourth occurrences refer to the parameter of the
-- enclosing % expression. The fifth is free. Therefore if we
-- substitute 0 for x we get 0 (%x. x (%y.xz)) (%y.0)
subst :: Id -> Exp -> Exp -> Exp
subst = stub "subst"
-- QUESTION 2:
--
-- isClosed e is true if and only if there are no free variables in e
-- (see the discussion in the comment for subst).
-- Examples: (%x. %y. x y) is closed; (%x. y %y. x y) is not since the
-- first occurrence of y is free.
isClosed :: Exp -> Bool
isClosed = stub "isClosed"
-- QUESTION 3:
--
-- eval e = v where e ==> v. If there is no v such that e==>v, the
-- result is undefined. Assume that e is closed.
eval :: Exp -> Exp
eval = stub "eval"
run :: Exp -> String
run e =
if isClosed e
then pp $ eval e
else error "run: expression must be closed"
stub :: String -> a
stub s = error ("Not implemented: " ++ s)
Attachment:- assignment.zip