[PL] Introduction to Programming Languages Exercise 9

Exercise 9.1

Consider the following expression:

val x=5 in 
val f=λy.y +x in 
(g.f (g 1)) (x.x) 

Write the arguments to interp each time it is called during the evaluation of the expression. Write them in the order in which the calls to interp occur during evaluation. For Num, Id, and Fun expressions, show their result values as well.

Exercise 9.2

This exercise examines differences between semantics by changing scope. Consider the following code:

def interp(e: Expr, env: Env): Value = e match { 
	... 
    case App(f, a) => 
    	val CloV(x, b, fEnv) = interp(f, env)
        interp(b, ??? + (x-> interp(a, env))) } 

Describe the semantics of the App case in prose when we use each of the following for ???.

1. env
2. Map()
3. fEnv

Exercise 9.3

Rewrite the following FVAE expression to an FAE expression by desugaring val:

val x=y.8 +y in y.x (10−y)

Exercise 9.4

This exercise asks you to implement the desugar function, which takes an FVAE expression as an argument and returns an FAE by desugaring val.

Complete the following implementation:

def desugar(e: Expr): Expr = e match { 
	case Num(n) => ??? 
    case Id(x) => ??? 
    case Val(x, e, b) => ??? 
    case Fun(x, b) => ??? 
    case App(f, a) => ??? }

Exercise 9.5

We can extend FVAE with pairs:

case class Pair(f: Expr, s: Expr) extends Expr 
case class Fst(e: Expr) extends Expr 
case class Snd(e: Expr) extends Expr 

This exercise asks you to implement the desugar function, which takes an expression and returns an expression that lacks Pair, Fst, and Snd but has the same behavior as the given expression. Precisely speaking, desugar satisfies the following:

• If e evaluates to an integer, desugar(e) evaluates to the same integer.
• If e evaluates to a function, desugar(e) evaluates to a function.
• If e evaluates to a pair, desugar(e) evaluates to a function.
• If e does not terminate, desugar(e) does not terminate.
• If e incurs a run-time error, desugar(e) can have any behavior.

Complete the following implementation:

def desugar(e: Expr): Expr = e match { 
	case Num(n) => Num(n) 
    case Id(x) => Id(x) 
    case Fun(x, b) => Fun(x, desugar(b)) 
    case App(f, a) => App(desugar(f), desugar(a)) 
    case Fst(e) => App(desugar(e), Fun("x", Fun("y", Id("x")))) 
    case Snd(e) => App(desugar(e), Fun("x", Fun("y", Id("y")))) 
    case Pair(f, s) => ??? 
}

Exercise 9.6

Consider the following semantics without closures:

v ::= n
	| λx.e

σ |- λx.e => λx.e

σ |- e1 => λx.e	σ |- e2 => v2	[x -> v2] |- e => v
---------------------------------------------------
σ |- e1 e2 => v
   

1. Explain why the above semantics, which lacks closures, is problematic.

2. Write an FVAE expression such that the evaluation in the original semantics with closures results in an integer, but the evaluation in the above semantics without closures incurs a run-time error.

Exercise 9.7

Suppose that we say that an expression terminates properly if and only if ∅ |- e => v for some v. Write an FVAE expression e suchthat only one of e and λx.x terminates properly.

Exercise 9.8

Write an FVAE expression that has a free identifier but evaluates to a value without incurring any run-time errors.

Exercise 9.9

This exercise extends FVAE with pairs. Consider the follow-ing language

e ::= ··· | (e,e) | e.1 | e.2 
v ::= ··· | (v,v) 

The semantics is as follows:

• The evaluation of (e1, e2) yields (v1,v2), where ei evaluates to vi.
• The evaluation of e.1 yields the first value of a pair v, where e evalutes to v.
• The evaluation of e.2 yields the second value of a pair v, where e evalutes to v.

1. Write the operational semantics of the form σ|-e ⇒ v.

2. Write the evaluation derivation of (8,(320,42).1).2.

Exercise 9.10

This exercise extends FVAE with records. A record is a value that maps labels to values. Consider the following language:

e ::= ··· | {l : e, ··· , l : e} | e.l
v ::= ··· | <l : v, ··· , l : v>

where l ranges over labels.

The semantics is as follows:

• The evaluation of {l1 : e1, ··· , ln : en} yields <l1 : v1, ··· , lv : vn>,
  where ei evaluates to vi
  .
• The evaluation of e.l yields the value of a field l in a record v,
  where e evaluates to v.

Write the operational semantics of the form σ|-e ⇒ v.

Exercise 9.11

This exercise extends FVAE with JavaScript-like sequencing. Consider the following language:

e ::= ··· | () | e; ··· ; e
v ::= ··· | ()

The semantics is as follows:

• The value of () is ().
• The value of e1; ··· ; en is () if every ei evaluates to ().
• The value of e1; ··· ; en is the value of the last expression whose value is not () if there is such an expression.

Write the operational semantics of the form σ|-e ⇒ v.

Exercise 9.12

This exercise modifies FVAE to check body expressions when evaluating function expressions. Consider we extend the value of FVAE to include a special value ↑ to represent an error during function body checking. Write the operational semantics of the form σ|-e ⇒ v for a function expression λx.e, when its semantics changes as follows:

• If every free identifier of e is in the domain of σ or is x, then evaluation of λx.e under σ yields a closure containing the function expression and the environment.
• Otherwise, evaluation of λx.e under σ yields ↑.

You may use the semantic function fv, which takes an expression and returns the set of every free identifier in the expression. For example fv(λx.y x) = {y}.

Exercise 9.13

This exercise extends FVAE to support multiple parameters. Consider the following language:

e ::= ··· | λx ··· x.e | e(e, ··· , e)
v ::= ··· | <λx ··· x.e, σ>

The semantics of some constructs are as follows:

• Evaluating λx1 ··· xn.e under σ yields a closure <λx1 ··· xn.e,σ>.
• If
  - evaluating e0 under σ yields a closure <λx1 ··· xn.e,σ>,
  - evaluating ei under σ yields vi for each 1 ≤ i ≤ n, and
  - evaluating e under σ'[x1 ↦ v1 , ··· , xn ↦ vn] yields v,
  then evaluating e0(e1, · · · , en) under σ yields v.
  

1. Write the operational semantics of the form σ|-e ⇒ v for the expressions.
2. Write the evaluation derivation of (λf m.f(m))(λx.x, 8).