QUESTION 1
Define a function that takes an environment and an identifier, and indicates whether or not the identifier has a value associated with in the environment. In other words, (hasBinding env id) should return False exactly if applyEnv env id raises an error.
hasBinding :: Env -> Id -> Bool
hasBinding = undefined
QUESTION 2
The Exp datatype (and parser) includes a "cond" constructor, which is a generalized if-then-else ("cond" for "conditional"). E.g. the
-- language expression
-- cond iszero(x) ==> +(x,1)
-- iszero(pred(x)) ==> 2
-- iszero(pred(pred(x) ==> 3
-- true ==> 4
-- end
-- has 4 clauses, each of which is a test followed by an expression to evaluate in the case the test evaluates to True.
To evaluate a "cond", evaluate the tests in order, and when one is found whose value is not zero, return the value of the corresponding result expression. If no true test is found, return 0 for the value of the cond expression.
In the above example, if x is bound to 2, the first 2 tests are false and the third is true, so the result of the whole cond expression is 3. Modify the interpreter to handle this new language feature; you'll need to modify the definition of evalExp above. Ignore evalExp'.
Question 3 Write a function boundIds that gives a list of all ids bound in the environment. Use this function and traceShow (imported from Debug.Trace) to print out a new line of currently-bound ids each time a function is called. Primitive operations don't count: only modify the evalExp clause for App. See the examples section for more.
boundIds :: Env -> [Id]
boundIds = undefined
Question 4
The Exp datatype (and parser) includes an "slet" constructor that is syntactically identical to "let" except for using the keyword "slet". The difference is in how the let bindings are evaluated.
The regular "let" is *parallel* binding: the right-hand sides are all evaluated in the same environment. The "slet" is sequential:
each let binding clause is processed in turn, and the binding it creates is added to the environment for evaluating the next binding.
For example, "let x=3 y=+(x,1) in y" is an error since +(x,1) is evaluated in the empty environment; "slet x=3 y=+(x,1) in y"evaluates to
4. Complete the evalExp clause(s) for SLet above.
Question 5
-- The "primed" version of the evaluator (run', evalExp' etc) is identical to the regular evaluator except for line with "***" beside it: here evalExp' uses env instead of closureEnv. Give an example where run and run' produce different results.
-- run q5Eg /= run' q5Eg
q5Eg :: String
q5Eg = undefined
-- Examples / Test Data
-- Q1
bogusFrame idSentence =
Frame ids (map (const $ Int 0) ids) where ids = words idSentence
envExample =
foldr ExtendedEnv EmptyEnv
$ map bogusFrame ["x y z", "u v", "s u x v", "a b c"]
-- Should be true.
q1Test =
map (hasBinding envExample) (words "x u g a i")
==
[True, True, False, True, False]
-- Q2
condeg0 =
"let x = 2 in \
\cond iszero(x) ==> +(x,1) \
\ iszero(pred(x)) ==> 2 \
\ iszero(pred(pred(x))) ==> 3 \
\ true ==> 4 \
\end"
condeg1 =
"let g = proc(x) cond iszero(x) ==> 0 true ==> 1 end in (g (g 3))"
condeg2 =
"let g = proc(x) cond iszero(x) ==> 0 false ==> 1 end in (g (g 3))"
-- Should be true.
q2Test =
map run [condeg0, condeg1, condeg2]
==
[Int 3, Int 1, Int 0]
-- Q3
q3eg =
" let f=proc(x) +(x,3) in \
\ let g = proc(h,y) succ((h (f y))) in \
\ let fact = \
\ letrec f(n) = if iszero(n) then 1 else *(n,(f pred(n))) \
\ in f \
\ in \
\ (g fact 17)"
-- Output should be something like:
-- ["fact","g","f"]
-- ["h","y","f"]
-- ["h","y","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- ["n","f","g","f"]
-- Int 2432902008176640001
-- Q4
slet0 = "slet x=3 y=+(x,1) in y"
slet1 = "let x=3 y=4 in slet z=2 f=proc() +(x,z) in (f)"
slet2 = "let x=2 y=4 in slet x=succ(x) u=x z=y in +(x,+(u,z))"
-- should be true
q4Test =
map run [slet0, slet1, slet2]
==
[Int 4, Int 5, Int 10]
-- Miscellaneous examples just to illustrate the language.
eg0 = "+(2,3)"
eg1 = "+(+(2,3), 4)"
eg2 = "let x=17 y=2 in *(x,y)"
eg3 = "let x=0 y=1 in let x=2 in x"
eg4 = "let x=-(3,3) in if iszero(x) then 17 else x"
eg5 = "let x=0 in +(let y=2 z=3 in +(y,z), x)"
eg6 = "let x=1 in let f = proc (y) +(x,y) in let x=2 in (f 17)"
eg7 =
"letrec even(x) = if iszero(x) then true else (odd pred(x)) \
\odd(x) = if iszero(x) then false else (even pred(x)) \
\in (odd 12)"
eg8 =
"let x=1 in \
\let g = proc (m) succ(m) in \
\letrec f(n) = if iszero(n) then x else (g (f pred(n))) in \
\(f 1)"
-- evaluates to true
miscTest =
map run [eg0, eg1, eg2, eg3, eg4, eg5, eg6, eg7, eg8]
==
[Int 5,Int 9,Int 34,Int 2,Int 17,Int 5,Int 18,Bool False,Int 2]
Attachment:- 1.zip