Midterm Exam
CS 320, Fall 2019
Student id: Name:
Instructions: You have 180 minutes to complete this closed-book, closed-note, closed-computer exam. Please
write all answers in the provided space. Korean students should write your answers in Korean.
1) (5pts) Write what YOU learned from the “Growing a Language” video lecture in one sentence.
2) (5pts) Which of the following are examples of shadowing?
a) {with {x {with {x 3} {- 5 x}}}
{+ 1 x}}
b) {with {x 3}
{with {y 5} {+ 1 x}}}
c) {with {x 3}
{with {x 5} {+ 1 x}}}
1
3) (5pts) With the following list of function definitions in F1WAE:
{deffun {twice x} {+ x x}}
{deffun {x y} y}
{deffun {f x} {+ x 1}}
{deffun {g g} g}
Show the results of evaluating the following expressions under the empty environment. When it is an
error, describe which error it is.
a) {twice twice}
b) {with {x 5} {x x}}
c) {g 3}
d) {g f}
e) {g g}
4) (5pts) Consider the following expression:
{with {fac {fun {m}
{with {facX {fun {facX}
{fun {m}
{if0 m
1
{* n {{facX facX} {- x 1}}}}}}}
{{facX facX} m}}}}
{fac m}}
a) Draw arrows on the above expression from each bound variable to its binding occurrence.
b) Draw dotted arrows on the above expression from each shadowing variable to its shadowed vari-
able.
2
5) (5pts) What are the results of the following expression:
{with {count {recfun {count n} {if0 n n {+ 1 {count {- n 1}}}}}}
{with {count {fun {x} {+ 42 {count x}}}}
{count 7}}}
in different scoping semantics when we evaluate it under the following environment?
Map("count" -> CloV("y", Add(Num(13), Id("y")), Map()))
a) Dynamic scope
b) Static scope
6) (5pts) Write the value of fac at line 11:
1 {with {fac
2 {with {facX
3 {fun {facY}
4 {with {fac {fun {x} {{facY facY} x}}}
5 ; Exactly like original fac
6 {fun {n}
7 {if0 n
8 1
9 {* n {fac {- n 1}}}}}}}}
10 {facX facX}}}
11 {fac 10}}
using the following Scala types:
trait FWAEValue
case class NumV(n: Int) extends FWAEValue
case class CloV(param: String, body: String, env: Env) extends FWAEValue
type Env = Map[String, FWAEValue]
Note that the type of the body of CloV is String.
3
7) (5pts) Rewrite the following code by replacing with and sequence of two expressions with fun and
function applications. You should not “evaluate” the code:
a) {fun {body-proc}
{with {fX {fun {fX}
{with {f {fun {x} {{fX fX} x}}}
{body-proc f}}}}
{fX fX}}}
b) {{+ 42 8}; {fun {x} {- 8 x}}}
8) (5 pts) Write the operational semantics of the form σ ` e ⇒ v for a function expression λx.e, when
the semantics of the function expression is as follows:
1. Check whether the body of the function expression e contains any free identifiers.
2. If it does not contain any free identifiers, its value is a pair of the function expression and the
environment.
3. Otherwise, the value of the expression is a special value ↑.
You may want to use the function fv which takes an expression and returns a set of free identifiers in
the expression.
4
9) (10pts) The following code is an excerpt from the implementation of the interpreter for BMFAE:
def interp(bmfae:BMFAE, env:Env, sto:Sto): (BMFAEValue, Sto) = bmfae match { ...
case App(f, a) => a match {
case Id(name) =>
val (fv, fs) = interp(f, env, sto)
fv match {
case CloV(x, b, fenv) =>
val addr = lookup(name, env)
interp(b, fenv + (x -> addr), fs)
case _ => error(s"not a closure: $fv")
}
case _ =>
val (fv, fs) = interp(f, env, sto)
val (av, as) = interp(a, env, fs)
fv match {
case CloV(x, b, fenv) =>
val addr = malloc(as)
interp(b, fenv + (x -> addr), as + (addr -> av))
case _ => error(s"not a closure: $fv")
} } }
a) What is the calling convention of this semantics?
Consider the following expression in BMFAE:
{with {n 42}
{with {f {fun {g} {g n}}}
{f {fun {x} {+ x 8}}}}}
b) Show the environment and store just before evaluating addition in the call-by-reference semantics.
c) Show the environment and store just before evaluating addition in the call-by-value semantics.
5
10) (10 pts) The following quote describes the JavaScript sequencing semantics:
The value of a StatementList is the value of the last value-producing them in the StatementList.
For example, the following calls to the eval function all return the value 1:
eval("1;;;;;")
eval("1;()")
eval("1;var a;")
Consider the following language e:
e ::= () Void e ∈ Exp v ∈ Val = Closure ∪ {()}
fin
| x Id x ∈ Var σ ∈ Env = Var −−→ Val
| {fun {x} e} Fun hλx.e, σi ∈ Closure = Exp × Env
| {e e} App
| {e; · · · ; e} Seq
where evaluation of e results in either a closure hλx.e, σi or the void (). The value of the sequence
expression {e1 ; · · · ; en } is the value of the last expression whose value is not (). If the values of
all the expressions e1 , · · · , en are (), the value of the sequence expression is (). Write the operational
semantics of each expression of the form σ ` e ⇒ v.
– ():
– x:
– {fun {x} e}:
– {e e}:
– {e; · · · ; e}:
6
11) (20pts) Consider the following language e:
e ::= n Num
| {+ e e} Add
| {- e e} Sub
| {with {x e} e} With
| x Id
| {fun {x} e} Fun
| {e e} App
where evaluation of e results in either a number n or a closure {fun {x} e}.
Consider the following implementation of e:
trait FWAES
trait FWAESValue extends FWAES // v ::= n | {fun {x} e}
case class Num(num: Int) extends FWAES with FWAESValue // e ::= n
case class Add(left: FWAES, right: FWAES) extends FWAES // | {+ e e}
case class Sub(left: FWAES, right: FWAES) extends FWAES // | {- e e}
case class With(x: String, init: FWAES, body: FWAES) extends FWAES // | {with {x e} e}
case class Id(name: String) extends FWAES // | x
case class Fun(x: String, body: FWAES) extends FWAES with FWAESValue // | {fun {x} e}
case class App(fun: FWAES, arg: FWAES) extends FWAES // | {e e}
// subst : (FWAES, String, FWAESValue) => FWAES
def subst(fwaes: FWAES, x: String, v: FWAESValue): FWAES = fwaes match {
case Num(n) => fwaes
case Add(l, r) => Add(subst(l, x, v), subst(r, x, v))
case Sub(l, r) => Sub(subst(l, x, v), subst(r, x, v))
case With(y, i, b) => With(y, subst(i, x, v), if (y == x) b else subst(b, x, v))
case Id(name) => if (name == x) v else fwaes
case Fun(y, b) => Fun(y, if (y == x) b else subst(b, x, v))
case App(f, a) => App(subst(f, x, v), subst(a, x, v))
}
// interp : FWAES => FWAESValue
def interp(fwaes: FWAES): FWAESValue = fwaes match {
case Num(n) => Num(n)
case Add(l, r) => numAdd(interp(l), interp(r))
case Sub(l, r) => numSub(interp(l), interp(r))
case With(x, i, b) => interp(subst(b, x, interp(i)))
case Id(x) => error(s"free identifier: $x")
case Fun(x, b) => Fun(x, b)
case App(f, a) => interp(f) match {
case Fun(x, b) => interp(subst(b, x, interp(a)))
case fv => error(s"not a closure: $fv")
}
}
7
a) Write the operational semantics of the above implementation of the form ` e ⇒ v where e[x/v]
denotes subst(e, x, v) and a value v is either a number n or a closure {fun {x} e}.
∗ e≡n
∗ e ≡ {+ e e}
∗ e ≡ {with {x e} e}
∗ e ≡ {fun {x} e}
∗ e ≡ {e e}
8
b) Write the definition of the substitution e[x/v] denoting subst(e,x,v) of the form e[x/v] e:
∗ e≡n
∗ e ≡ {+ e e}
∗ e ≡ {with {x e} e}
∗ e≡x
∗ e ≡ {fun {x} e}
∗ e ≡ {e e}
9
c) Consider the following expression:
{with {z {fun {x} {- x y}}}
{with {y 10}
{z 32}}}
∗ What is the result of evaluating the expression under the empty environment?
∗ What is the result of evaluating the expression under the empty environment in FWAE?
∗ Why are the results different?
10
12) (10pts) Consider the following language e:
e ::= a atomic expression
| ea function application
| fn m function expression
a ::= n number
| x identifier
m ::= p e pattern matching
| p e|m pattern matching sequence
p ::= _ wildcard pattern
| n number pattern
| x identifier pattern
where a value of the language v is either a number n or a closure hm, σi, a result of evaluation r is
either a value v or a failure in pattern matching ↑, which is different from run-time errors, and an
environment σ maps identifiers to their values.
The operational semantics rules for expressions and atomic expressions are as follows:
σ`e⇒r
σ ` a ,→ v σ ` e ⇒↑ σ ` e ⇒ hm, σ 0 i σ ` a ⇒ v (σ 0 , v) ` m ⇒ v 0
σ`a⇒v σ ` e a ⇒↑ σ ` e a ⇒ v0
σ ` e ⇒ hm, σ 0 i σ ` a ⇒ v (σ 0 , v) ` m ⇒↑
σ ` fn m ⇒ hm, σi
σ ` e a ⇒↑
σ ` a ,→ v
x ∈ Domain(σ)
σ ` n ,→ n
σ ` x ,→ σ(x)
The semantics of pattern matching m and pattern p are as follows:
– Evaluation of p e under (σ, v) has two possibilities. First, when evaluation of p results in
a new environment σ 0 , the result of this pattern matching is the result of evaluation of e under
σ + σ 0 , where σ + σ 0 is a disjoint union of σ and σ 0 . Second, when evaluation of p produces ↑, the
evaluation of this pattern matching produces ↑ as well.
– Evaluation of “p e | m” under (σ, v) also has two possibilities. First, when evaluation of
p e succeeds with a value v 0 , the value of this pattern matching sequence is v 0 . Second, when
evaluation of p e fails, the result of evaluation of this pattern matching sequence is the result
of evaluation of m.
– Evaluation of the wildcard pattern _ under (σ, v) produces the empty environment.
– Evaluation of the number pattern n under (σ, v) has two possibilities. If val (n) = v where val (n)
returns a number n for a given number pattern n, it produces the empty environment. Otherwise,
it produces ↑.
– Evaluation of the identifier pattern x under (σ, v) produces a singleton environment {x 7→ v} if x
is not in the domain of σ.
Write the operational semantics for m and p of the forms (σ, v) ` m ⇒ r and (σ, v) ` p ⇒ σ/ ↑ ,
respectively, where (σ, v) ` p ⇒ σ/ ↑ denotes (σ, v) ` p ⇒ σ or (σ, v) ` p ⇒↑ . Remember that the
operational semantics do not specify run-time errors.
11
12
13) (10pts) Consider the following language e:
e ::= n
| x
| {fun {x∗ } e}
| {e e∗ }
| {get e}
where n denotes a number and a value of the language is one of the undefined value, a number, or a
closure hλx1 · · · xn .e, σi, and an environment maps names to values:
x ∈ Name v ∈ Value = {undefined} + Number + Closure
fin
n ∈ Number σ ∈ Env = Name → Value
fin
hλx1 · · · xn .e, σi ∈ Closure α ∈ Array = Number → Value
The semantics of some constructs are as follows:
– The value of a function expression {fun {x1 · · · xn } e} at an environment σ is a closure hλx1 · · · xn .e, σi.
– A function application {e0 · · · en } is evaluated as follows:
∗ Evaluate the subexpressions in order. The value of e0 should be a closure hλx1 · · · xm .e, σi
that has m parameters.
∗ Create an array α of size n and initialize the i-th value of the array with the value of ei+1
where 0 ≤ i ≤ n − 1.
∗ Evaluate the closure body e under the environment σ extended as follows:
· The value of the i-th parameter is the value of ei where 1 ≤ i ≤ m ≤ n.
· The value of the j-th parameter is the undefined value where n < j ≤ m.
and the array α.
– The value of {get e} is the n-th value of the array α where n is the value of e and the array
indices start from 0.
For example, {{fun {x y} y} 4} evaluates to undefined, and {{fun {x} {get 0}} 5} evaluate to 5.
a) Write the operational semantics of the form σ, α ` e ⇒ v
13
b) Write the evaluation derivation of the following expressions:
∅, ∅ ` {{fun {x y} {get x}} 2 19 141} ⇒
14