Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS225 Programming Languages: Homework 4
Due date: Thursday, December 9 by 11:59PM
Submission:: Please submit your solutions to Problems 1-5 (and 7 for Graduate Students) as one file, and
your completed arith.ml file to answer Problem 6. All submissions must be made electronically in
Blackboard.
Problem 1 (14 points). For each of the following CatML expressions e, specify whether there exists e′
such that e→ e′, and if so provide the full derivation of the reduction.
a. 3
b. (Fun y . 3 + y)
c. 1 + 2
d. True And Not False
e. (1 + 3) = False
f. 4 = False
g. (Fun x . x+ 2) 5
Problem 2 (16 points). Which of the expressions in the previous problem:
a. are reducible?
b. have a valuation?
c. are stuck?
d. go wrong?
Problem 3 (15 points). For each of the following CatML expressions e, state whether e is closed or not,
and why:
a. 1 + 2
b. x
c. (Fun x . x+ y)
d. (Fun x . (Fun y . x+ y))
e. (Fun x . (Fun y . x+ y))(y)
Problem 4 (15 points). For each of the following substitutions e[v/x] specify e′ such that e′ = e[v/x]:
a. x[True/x]
b. x[3/y]
c. (Fun x . x+ y)[3/y]
1
d. (Fun x . (Fun y . x And y))[False/x]
e. (Fun y . x And y)[False/x]
Problem 5 (15 points). For each of the following expressions e in the CatML concrete syntax, describe
its evaluation by specifying v such that e →? v, and also show it’s trace. In this problem you do not need
to provide justification of each reduction.
a. If 2 = 0 Then 1 Else 1 + 1
b. (Fun x . x And True)(False)
c. ((Fun x . (Fun y . x And y))(True))(False)
Problem 6 (25 points). Complete the ARITH interpreter as described in the arith.ml template
available in the CS225 git repo.
Problem 7 (15 points: Graduate Students Only). Complete the AND contextual reduction cases in the
inductive proof of Lemma 1.1 (see Lecture Notes 10 for example cases).