20 Exercise: Big-Step Operational Semantics

$\newcommand{\TirName}[1]{\text{#1}} \newcommand{\inferrule}[3][]{ \let\and\qquad \begin{array}{@{}l@{}} \TirName{#1} \\ \displaystyle \frac{#2}{#3} \end{array} } \newcommand{\infer}[3][]{\inferrule[#1]{#2}{#3}} $

Learning Goals

The primary learning goals of this assignment are to build intuition for the following:

how to read a formal specification of a language semantics;
how dynamic scoping arises; and
big-step interpretation.

Instructions

This assignment asks you to write Scala code. There are restrictions associated with how you can solve these problems. Please pay careful heed to those. If you are unsure, ask the course staff.

Note that ??? indicates that there is a missing function or code fragment that needs to be filled in. Make sure that you remove the ??? and replace it with the answer.

Use the test cases provided to test your implementations. You are also encouraged to write your own test cases to help debug your work. However, please delete any extra cells you may have created lest they break an autograder.

Imports

org.scalatest._

// Run this cell FIRST before testing.
import $ivy.`org.scalatest::scalatest:3.2.19`, org.scalatest._, events._, flatspec._
def report(suite: Suite): Unit = suite.execute(stats = true)
def assertPassed(suite: Suite): Unit =
  suite.run(None, Args(new Reporter {
    def apply(e: Event) = e match {
      case e @ (_: TestFailed) => assert(false, s"${e.message} (${e.testName})")
      case _ => ()
    }
  }))
def passed(points: Int): Unit = {
  require(points >=0)
  if (points == 1) println("*** 🎉 Tests Passed (1 point) ***")
  else println(s"*** 🎉 Tests Passed ($points points) ***")
}
def test(suite: Suite, points: Int): Unit = {
  report(suite)
  assertPassed(suite)
  passed(points)
}

import $ivy.$                                , org.scalatest._, events._, flatspec._
defined function report
defined function assertPassed
defined function passed
defined function test

20.1 A Big-Step Javascripty Interpreter

We now have the formal tools to specify exactly how a JavaScripty program should behave. Unless otherwise specified, we continue to try to match JavaScript semantics, though we are no longer beholden to it. Thus, it is still useful to write little test JavaScript programs and see how the test should behave.

In this exercise, we extend JavaScripty with functions. We try to implement the eval function in the most straightforward way. What we will discover is that we have made a historical mistake and have ended up with a form of dynamic scoping.

For the purpose of this exercise, we will limit the scope of JavaScripty by restricting expression forms and simplifying semantics as appropriate for pedagogical purposes. In particular, we simplify the semantics by no longer performing implicit type coercions.

20.1.1 Syntax

We consider the following abstract syntax for this exercise. Note that new constructs for functions are $\textcolor{purple}{\text{highlighted}}$.

\[ \begin{array}{rrrl} \text{expressions} & e& \mathrel{::=}& n \mid b \mid e_1 \mathbin{\mathit{bop}} e_2 \mid e_1\;\texttt{?}\;e_2\;\texttt{:}\;e_3 \mid x \mid\mathbf{const}\;x\;\texttt{=}\;e_1\texttt{;}\;e_2 \\ && \textcolor{purple}{\mid} & \textcolor{purple}{\texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e_1 \mid e_1\texttt{(}e_2\texttt{)}} \\ \text{values} & v& \mathrel{::=}& n \mid b \textcolor{purple}{\mid\texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e_1} \\ \text{binary operators} & \mathit{bop}& \mathrel{::=}& \texttt{+} \mid\texttt{===} \mid\texttt{!==} \\ \text{variables} & x \\ \text{numbers} & n \\ \text{booleans} & b \end{array} \]

Observe that we consider only base values numbers $n$ and booleans $b$ and have significantly reduced the number of expression forms we consider.

Like in the book chapter, all functions are one argument functions for simplicity.

20.2 Dynamic Scoping Test

Exercise 20.1 (5 points) Write a JavaScript program that behaves differently under dynamic scoping versus static scoping (and does not crash). This will get us used to the syntax, while providing a crucial test case for our interpreter.

Edit this cell:

const x = 10;
const f = (a) => {
  ???
}
const g = (b) => {
  ???
}
g(-1)

Explain in 1-2 sentences why you think this program would behave differently under dynamic scoping versus static scoping.

Edit this cell:

???

Notes

We are using $\mathbf{const}$ to name functions, that is, we are binding an expression, which is a function, to a variable. This binding allows us to get it later, but it does not allow us call it inside the function definition (i.e., recursion).
We are providing a throw-away parameter to our function because according to our syntax functions have exactly one parameter.
As noted above, we are simplifying some semantics in this exercise compared with the previous lab: implicit type coercions work in JavaScript and in the previous lab, but you will not include them in your implementation on this homework. Therefore, your test case cannot have any implicit type conversions.
In order to execute the program, you will need to switch your kernal to Deno, the Javascript kernel for Jupyter.

20.3 Reading an Operational Semantics

In this homework, we start to see specifications of programming language semantics. A big-step operational semantics of this small fragment of JavaScripty is given below. Except perhaps for the assigned reading, this figure (Figure 20.1) may be one of the first times that you are reading a formal semantics of a programming language. It may seem daunting at first, but it will be become easier with practice. This homework is such an opportunity to practice.

$\fbox{$E \vdash e \Downarrow v$}$

$\inferrule[EvalVar]{ \phantom{\Downarrow} }{ E \vdash x \Downarrow E(x) }$

$\inferrule[EvalConstDecl]{ E \vdash e_1 \Downarrow v_1 \and E[x \mapsto v_1] \vdash e_2 \Downarrow v_2 }{ E \vdash \mathbf{const}\;x\;\texttt{=}\;e_1\texttt{;}\;e_2 \Downarrow v_2 }$

$\inferrule[EvalVal]{ \phantom{ \Downarrow} }{ E \vdash v \Downarrow v }$

$\inferrule[EvalPlusNumber]{ E \vdash e_1 \Downarrow n_1 \and E \vdash e_2 \Downarrow n_2 }{ E \vdash e_1 \mathbin{\texttt{+}} e_2 \Downarrow n_1 \mathbin{+} n_2 }$

$\inferrule[EvalEquality]{ E \vdash e_1 \Downarrow v_1 \and E \vdash e_2 \Downarrow v_2 \and \mathit{bop}\in \left\{ \texttt{===}, \texttt{!==} \right\} }{ E \vdash e_1 \mathbin{\mathit{bop}} e_2 \Downarrow v_1 \mathbin{\mathit{bop}} v_2 }$

$\inferrule[EvalIfTrue]{ E \vdash e_1 \Downarrow \mathbf{true} \and E \vdash e_2 \Downarrow v_2 }{ E \vdash e_1\;\texttt{?}\;e_2\;\texttt{:}\;e_3 \Downarrow v_2 }$

$\inferrule[EvalIfFalse]{ E \vdash e_1 \Downarrow \mathbf{false} \and E \vdash e_3 \Downarrow v_3 }{ E \vdash e_1\;\texttt{?}\;e_2\;\texttt{:}\;e_3 \Downarrow v_3 }$

Figure 20.1: A big-step operational semantics of a fragment of JavaScripty with some arithmetic and logic expressions, as well as variable binding. We define the judgment form $E \vdash e \Downarrow v$, which says informally, “In value environment $E$, expression $e$ evaluates to value $v$.” This relation has three parameters: $E$, $e$, and $v$. You can see the other parts of the judgment form as simply punctuation.

A value environment $E$ is a finite map from variables $x$ to values $v$ that we write as follows: \[ \begin{array}{rrrl} \text{value environments} & E, \mathit{env}& \mathrel{::=}& \cdot \mid E[x \mapsto v] \end{array} \]

We write $\cdot$ for the empty environment and $E[x \mapsto v]$ as the environment that maps $x$ to $v$ but is otherwise the same as $E$ (i.e., extends $E$ with mapping $x$ to $v$). Additionally, we write $E(x)$ for looking up the value of $x$ in environment $E$.

A formal semantics enables us to describe the semantics of a programming language clearly and concisely. The initial barrier is getting used to the meta-language of judgment forms and inference rules. However, once you cross that barrier, you will see that we are telling you exactly how to implement the interpreter—it will almost feel like cheating!

20.3.1 Strings

Exercise 20.2 (5 points) Suppose that we extend the above language with strings $\mathit{str}$ and a string concatenation $e_1 \mathbin{\texttt{+}} e_2$ expression (like in JavaScript). Consider the following inference rule for the evaluation judgment form:

$\inferrule[EvalPlusString1]{ E \vdash e_1 \Downarrow \mathit{str}_1 \and E \vdash e_2 \Downarrow v_2 \and v_2 \rightsquigarrow \mathit{str}_2 }{ E \vdash e_1 \mathbin{\texttt{+}} e_2 \Downarrow \mathit{str}_1 \mathit{str}_2 }$

Explain in 1-2 sentences what $\TirName{EvalPlusString1}$ is stating.

Edit this cell:

???

Notes

The $v \rightsquigarrow \mathit{str}$ judgment form says that value $v$ coerces to string $\mathit{str}$.

Exercise 20.3 (5 points) Let us define rules that specify evaluation of the expression $e_1 \mathbin{\texttt{+}} e_2$ just like in JavaScript. Give the other rule $\TirName{EvalPlusString\(_2$}\) that concatenates strings in the case that $e_2$ evaluates to a string.

Edit this cell:

???

Explain in 1-2 sentences why you need $\TirName{EvalPlusString\(1$}\) and $\TirName{EvalPlusString\(2$}\) together for interpreting string concatenation like in JavaScript.

Edit this cell:

???

Notes

You may give the rule in LaTeX math or as plain text (ascii art) approximating the math rendering. For example,

EvalPlusString1
E |- e1 vv str1    E |- e2 vv v2    v2 ~~> str2
-----------------------------------------------
E |- e1 + e2 vv str1 str2

The LaTeX code for the rendered $\TirName{EvalPlusString1}$ rule above is as follows:

\inferrule[EvalPlusString1]{
  E \vdash e_1 \Downarrow \mathit{str}_1
  \and
  E \vdash e_2 \Downarrow v_2
  \and
  v_2 \rightsquigarrow \mathit{str}_2
}{
  E \vdash e_1 \mathbin{\texttt{+}} e_2 \Downarrow \mathit{str}_1 \mathit{str}_2
}

20.3.2 Functions

The inference rule defining evaluation of a function call (that accidentally results in dynamic scoping) is as follows:

$\inferrule[EvalCall]{ E \vdash e_1 \Downarrow \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e' \and E \vdash e_2 \Downarrow v_2 \and E[x \mapsto v_2] \vdash e' \Downarrow v' }{ E \vdash e_1\texttt{(}e_2\texttt{)} \Downarrow v' }$

Figure 20.2

Exercise 20.4 (5 points) To continue this warm up and guide our implementation of these inference rules, write out what $\TirName{EvalCall}$ is stating.

Edit this cell:

???

20.4 Implementing from Inference Rules

20.4.1 Abstract Syntax

In the following, we build up to implementing an eval function:

def eval(env: Env, e: Expr): Expr

This eval function directly corresponds the the evaluation judgment: $E \vdash e \Downarrow v$, which is the operational semantics defined above. It takes as input a value environment $E$ and an expression $e$ and returns a value $v$.

Below is the Expr type defining our abstract syntax tree in Scala. If you haven’t already, switch back to the Scala kernel and then run the two cells below.

trait Expr // e ::=

case class Var(x: String) extends Expr                           // e ::= x
case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // e ::= const x = e1; e2

case class N(n: Double) extends Expr  // e ::= n
case class B(b: Boolean) extends Expr // e ::= b

trait Bop // bop ::=
case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // e ::= e1 bop b2

case object Plus extends Bop // bop ::= +
case object Eq extends Bop   // bop ::= ===
case object Ne extends Bop   // bop ::= !==

case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3

case class Fun(x: String, e1: Expr) extends Expr // e ::= (x) => e1
case class Call(e1: Expr, e2: Expr) extends Expr // e ::= e1(e2)

defined trait Expr
defined class Var
defined class ConstDecl
defined class N
defined class B
defined trait Bop
defined class Binary
defined object Plus
defined object Eq
defined object Ne
defined class If
defined class Fun
defined class Call

Numbers $n$, booleans $b$, and functions $\texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e_1$ are values, and we represent a value environment $E$ as a Map[String, Expr]:

def isValue(e: Expr): Boolean = e match {
  case N(_) | B(_) | Fun(_, _) => true
  case _ => false
}

type Env = Map[String, Expr]
val empty: Env = Map()
def lookup(env: Env, x: String): Expr = env(x)
def extend(env: Env, x: String, v: Expr): Env = {
  require(isValue(v))
  env + (x -> v)
}

defined function isValue
defined type Env
empty: Env = Map()
defined function lookup
defined function extend

Exercise 20.5 (5 points) Now that we have the AST type Expr defined, take your JavaScripty test program from Exercise 20.1 and write out the AST it would parse to. This will serve as a test for your implementation.

def testAST: Expr = ConstDecl(
    "x",
    N(10),
    ConstDecl(
        "f",
        Fun(
            "a",
            ???
        ), 
        ConstDecl(
            "g",
            Fun(
                "b",
                ???
            ),
            Call(Var("g"), N(-1))
        )
    )
)

defined function testAST

Notes

Recall the difference between concrete and abstract syntax. Your AST here will use the abstract syntax and be of type Expr defined above. Therefore, the AST nodes you write in can only be constructors of Expr. For example, the $\mathbf{return}$ keyword is in the concrete syntax but not a constructor of Expr.

20.4.2 Variables, Numbers, and Booleans

Exercise 20.6 (10 points) Implement eval the evaluation judgment form $E \vdash e \Downarrow v$ for all rules except $\TirName{EvalCall}$ shown in Figure 20.1. It should be noted that this implementation should very similar to your implementation of eval in previous lab.

def eval(env: Env, e: Expr): Expr =
  // EvalVar
  // EvalConstDecl
  // EvalVal
  // EvalPlusNumber
  // EvalEquality
  // EvalIfTrue
  // EvalIfFalse
  ???

defined function eval

Notes

It is most beneficial to first implement eval from scratch by referencing the rules shown in Figure 20.1.
After you implement eval here by following the rules, it may then be informative to compare with your implementation from the previous lab (that was for a larger language and with implicit type coercions).
You will have unmatched cases (i.e., there are no corresponding rules), which you can leave unimplemented with ??? or the potential for MatchError.

Tests

def evalTest(e: Expr): Expr = {
  eval(empty, e)
}
val testExercise3 = test(new AnyFlatSpec {
  val testcase1 = {
    val e1 = N(1)
    val e2 = N(2)
    evalTest(Binary(Plus, e1, e2))
  }
  val testcase2 = {
    val e1 = N(5)
    val e2 = N(5)
    evalTest(Binary(Eq, e1, e2))  
  }
  val testcase3 = {
    val e1 = N(5)
    val e2 = N(7)
    evalTest(Binary(Eq, e1, e2))
  }
  val testcase4 = {
    val e1 = N(5)
    val e2 = N(7)
    evalTest(Binary(Ne, e1, e2))
  }
  val testcase5 = {
    val e1 = N(5)
    val e2 = N(5)
    evalTest(Binary(Ne, e1, e2))
  }
  val testcase6 = {
    val e1 = N(3)
    val e2 = Binary(Plus, Var("x"), N(1))
    evalTest(ConstDecl("x", e1, e2)) 
  }
  val testcase7 = {
    val e1 = Binary(Plus, N(3), N(2))
    val e2 = Binary(Plus, N(1), N(1))
    evalTest(If(B(true), e1, e2)) 
  }
  val testcase8 = {
    val e1 = Binary(Plus, N(3), N(2))
    val e2 = Binary(Plus, N(1), N(1))
    evalTest(If(B(false), e1, e2)) 

  }
    
  it should "Test Case 1" in { assertResult( N(3) ) { testcase1 } }
  it should "Test Case 2" in { assertResult( B(true) ) { testcase2 } }
  it should "Test Case 3" in { assertResult( B(false) ) { testcase3 } }
  it should "Test Case 4" in { assertResult( B(true) ) { testcase4 } }
  it should "Test Case 5" in { assertResult( B(false) ) { testcase5 } }
  it should "Test Case 6" in { assertResult( N(4) ) { testcase6 } }
  it should "Test Case 7" in { assertResult( N(5) ) { testcase7 } }
  it should "Test Case 8" in { assertResult( N(2) ) { testcase8 } }
}, 10)

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd4$Helper.eval(cmd4.sc:9)
  ammonite.$sess.cmd5$Helper.evalTest(cmd5.sc:2)
  ammonite.$sess.cmd5$Helper$$anon$1.<init>(cmd5.sc:8)
  ammonite.$sess.cmd5$Helper.<init>(cmd5.sc:4)
  ammonite.$sess.cmd5$.<clinit>(cmd5.sc:7)

20.4.3 Functions

Exercise 20.7 (10 points) Extend your implementation with functions. On function calls, you need to extend the environment for the formal parameter. Begin with what you have from Exercise 20.6.

def eval(env: Env, e: Expr): Expr = 
  // EvalVar
  // EvalConstDecl
  // EvalVal
  // EvalPlusNumber
  // EvalEquality
  // EvalIfTrue
  // EvalIfFalse
  // EvalCall
  ???

defined function eval

Notes

This question is asking you to implement $\TirName{EvalCall}$.
Do not worry yet about dynamic type errors, so this will still have some ???s or have the possibility of MatchErrors.

Tests

def evalTest(e: Expr): Expr = {
  eval(empty, e)
}
test(new AnyFlatSpec {
  val testcase1 = {
    val x = "x"
    val e1 = Fun(x, Binary(Plus, Var(x), N(1)))
    val e2 = N(2)
    evalTest(Call(e1, e2))
  }
  val testcase2 = {
    val x = "x"
    val e1 = Fun(x, If(Binary(Eq, Var(x), N(0)), N(1), N(0)))
    val e2 = N(0)
    evalTest(Call(e1, e2))
  }
  val testcase3 = {
    val x = "x"
    val e1 = Fun(x, If(Binary(Eq, Var(x), N(0)), N(1), N(0)))
    val e2 = N(1)
    evalTest(Call(e1, e2))
  }
  val testcase4 = {
    val x = "x"
    val e1 = Fun(x, If(Binary(Ne, Var(x), N(0)), N(1), N(0)))
    val e2 = N(1)
    evalTest(Call(e1, e2))
  }
  val testcase5 = {
    val a = "a"
    val e1 = N(3)
    val e2 = Binary(Plus, Var("x"), N(1))
    val e3 = ConstDecl("x", e1, e2)
    val e4 = Fun(a, e3)
    evalTest(Call(e4, N(1)))
  }
  val testcase6 = {
    val a = "a"
    val e1 = Binary(Plus, N(3), Var(a))
    val e2 = Binary(Plus, Var("x"), N(1))
    val e3 = ConstDecl("x", e1, e2)
    val e4 = Fun(a, e3)
    evalTest(Call(e4, N(2)))
  }
  val testcase7 = {
    val a = "a"
    val f = "f"
    val e1 = Binary(Plus, N(3), Var(a))
    val e2 = Binary(Plus, Var("x"), N(1))
    val e3 = ConstDecl("x", e1, e2)
    val e4 = Fun(a, e3)
    val e5 = ConstDecl(f, e4, Call(Var(f), N(2)))
    evalTest(e5)
  }
  val testcase8 = {
    val f = "f"
    val a = "a"
    val e1 = Binary(Plus, Var(a), Var(a))
    val e2 = Fun(a, e1)
    val e3 = Fun(f, Call(Var(f), N(5)))
    evalTest(Call(e3, e2))
  }
  val testcase9 = {
    val a1 = "a1"
    val a2 = "a2"
    val x = "x"
    val e1 = Fun(a1, Var(x))
    val e2 = ConstDecl(x, N(20), Call(e1, N(-1)))    
    val e3 = Fun(a2, e2)
    val e4 = ConstDecl(x, N(10), Call(e3, N(-1)))
    evalTest(e4)
  }

  it should "Test Case 1" in { assertResult( N(3) ) { testcase1 } }
  it should "Test Case 2" in { assertResult( N(1) ) { testcase2 } }
  it should "Test Case 3" in { assertResult( N(0) ) { testcase3 } }
  it should "Test Case 4" in { assertResult( N(1) ) { testcase4 } }
  it should "Test Case 5" in { assertResult( N(4) ) { testcase5 } }
  it should "Test Case 6" in { assertResult( N(6) ) { testcase6 } }
  it should "Test Case 7" in { assertResult( N(6) ) { testcase7 } }
  it should "Test Case 8" in { assertResult( N(10) ) { testcase8 } }
  it should "Test Case 9" in { assertResult( N(20) ) { testcase9 } }
    
}, 10)

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd6$Helper.eval(cmd6.sc:10)
  ammonite.$sess.cmd7$Helper.evalTest(cmd7.sc:2)
  ammonite.$sess.cmd7$Helper$$anon$1.<init>(cmd7.sc:9)
  ammonite.$sess.cmd7$Helper.<init>(cmd7.sc:4)
  ammonite.$sess.cmd7$.<clinit>(cmd7.sc:7)

20.4.4 Dynamic Typing

In the previous lab, all expressions could be evaluated to something (because of conversions). With functions, we encounter one of the very few run-time errors in JavaScript: trying to call something that is not a function. In JavaScript and in JavaScripty, calling a non-function raises a run-time error. Such a run-time error is known as a dynamic type error. Languages are called dynamically typed when they allow all syntactically valid programs to run and check for type errors during execution.

We define a Scala exception

case class DynamicTypeError(e: Expr) extends Exception {
  override def toString = s"TypeError: in expression $e"
}

defined class DynamicTypeError

to signal this case. In other words, when your interpreter discovers a dynamic type error, it should throw this exception using the following Scala code:

throw DynamicTypeError(e)

The argument should be the input expression e to eval where the type error was detected. That is, the expression where there is no possible rule to continue. For example, in the case of calling a non-function, the type error should be reported on the Call node and not any sub-expression.

Exercise 20.8 (10 points) Add support for checking for all dynamic type errors. You should have no possibility for a MatchError or a NotImplementedError. Start with what you have from Exercise 20.7.

def eval(env: Env, e: Expr): Expr = 
  // EvalVar
  // EvalConstDecl
  // EvalVal
  // EvalPlusNumber
  // EvalEquality
  // EvalIfTrue
  // EvalIfFalse
  // EvalCall
  ???

defined function eval

Tests

def evalTest(e: Expr): Expr = {
  eval(empty, e)
}
test(new AnyFlatSpec {
  val testcase1 = {
    val e1 = Binary(Plus, N(3), N(2))
    val e2 = Binary(Plus, N(1), N(1))
    evalTest(If(B(true), e1, e2)) 
  }
  val testcase2 = {
    val e1 = Binary(Plus, N(3), N(2))
    val e2 = Binary(Plus, N(1), N(1))
    evalTest(If(B(false), e1, e2)) 

  }
  val testcase3 = {
    val a = "a"
    val f = "f"
    val e1 = Binary(Plus, N(3), Var(a))
    val e2 = Binary(Plus, Var("x"), N(1))
    val e3 = ConstDecl("x", e1, e2)
    val e4 = Fun(a, e3)
    val e5 = ConstDecl(f, e4, Call(Var(f), N(2)))
    evalTest(e5)
  }
  val testcase4 = {
    val f = "f"
    val a = "a"
    val e1 = Binary(Plus, Var(a), Var(a))
    val e2 = Fun(a, e1)
    val e3 = Fun(f, Call(Var(f), N(5)))
    evalTest(Call(e3, e2))
  }
  val testcase5 = {
    val a1 = "a1"
    val a2 = "a2"
    val x = "x"
    val e1 = Fun(a1, Var(x))
    val e2 = ConstDecl(x, N(20), Call(e1, N(-1)))    
    val e3 = Fun(a2, e2)
    val e4 = ConstDecl(x, N(10), Call(e3, N(-1)))
    evalTest(e4)
  }
  val testcase6 = {
    Binary(Plus, N(4), B(true))
  }
  val testcase7 = {
    Call(N(4), N(2))
  }
  val testcase8 = {
    Call(N(4), B(true))
  }
    
  it should "Test Case 1" in { assertResult( N(5) ) { testcase1 } }
  it should "Test Case 2" in { assertResult( N(2) ) { testcase2 } }
  it should "Test Case 3" in { assertResult( N(6) ) { testcase3 } }
  it should "Test Case 4" in { assertResult( N(10) ) { testcase4 } }
  it should "Test Case 5" in { assertResult( N(20) ) { testcase5 } }
  it should "Test Case 6" in { intercept[DynamicTypeError] {evalTest(testcase6)} }
  it should "Test Case 7" in { intercept[DynamicTypeError] {evalTest(testcase7)} }
  it should "Test Case 8" in { intercept[DynamicTypeError] {evalTest(testcase8)} }
}, 10)

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd9$Helper.eval(cmd9.sc:10)
  ammonite.$sess.cmd10$Helper.evalTest(cmd10.sc:2)
  ammonite.$sess.cmd10$Helper$$anon$1.<init>(cmd10.sc:8)
  ammonite.$sess.cmd10$Helper.<init>(cmd10.sc:4)
  ammonite.$sess.cmd10$.<clinit>(cmd10.sc:7)

20.4.5 Dynamic Scoping

Exercise 20.9 (5 points) Below is a cell that runs the AST from the test case you wrote in Exercise 20.5 with your interpreter implementation.

def evalTest(e: Expr): Expr = {
  eval(empty, e)
}
evalTest(testAST)

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd3$Helper.testAST(cmd3.sc:8)
  ammonite.$sess.cmd11$Helper.<init>(cmd11.sc:4)
  ammonite.$sess.cmd11$.<clinit>(cmd11.sc:7)

Does it evaluate to what your excepted? The evaluation output above should be different from what it would evaluate to with a JavaScript interpreter, such as Deno. Ensure that the results are different and write below what each interpreter evaluates to.

Edit this cell:

???

It seems like we implemented dynamic scoping instead of static scoping. Explain the failed test case and how your interpreter behaves differently compared to a JavaScript interpreter. Furthermore, think about why this is the case and explain in 1-2 sentences why your interpreter behaves differently.

Edit this cell:

???

20.4.6 Closures

In order to fix our dynamic scoping issue, we will implement explicit closures. That is, when functions are evaluated, they will use the value environment in which they were defined.

Here are the updates to our abstract syntax.

\[ \begin{array}{rrrll} \text{expressions} & e& \mathrel{::=}& \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e_1 \mid e_1\texttt{(}e_2\texttt{)} \\ \text{values} & v& \mathrel{::=}& \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e_1[E] \\ \text{variables} & x \end{array} \]

Notice that now, closures are values (and functions are not), while functions are still expressions.

We also add the $\TirName{EvalFun}$ rule to our operational semantics, and edit the $\TirName{EvalCall}$ rule, seen below.

$\fbox{$E \vdash e \Downarrow v$}$

$\inferrule[EvalFun]{ }{ E \vdash \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e \Downarrow \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e [ E] { } }$

$\inferrule[EvalCall]{ E \vdash e_1 \Downarrow \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e'[E'] \and E \vdash e_2 \Downarrow v_2 \and E'[x \mapsto v_2] \vdash e' \Downarrow v' }{ E \vdash e_1\texttt{(}e_2\texttt{)} \Downarrow v' }$

In order to implement this, we will add Closure to our Expr type, and edit other helper functions as needed.

case class Closure(fun: Fun, env: Env) extends Expr 
def isValue(e: Expr): Boolean = e match {
  case N(_) | B(_) | Closure(_, _) => true
  case _ => false
}
def extend(env: Env, x: String, v: Expr): Env = {
  require(isValue(v))
  env + (x -> v)
}

defined class Closure
defined function isValue
defined function extend

Exercise 20.10 (10 points) With the above, implement a new version of eval that uses closures to enforce static scoping. Begin with what you have from Exercise 20.8.

def eval(env: Env, e: Expr): Expr = 
  // EvalVar
  // EvalConstDecl
  // EvalVal
  // EvalPlusNumber
  // EvalEquality
  // EvalIfTrue
  // EvalIfFalse
  // EvalFun
  // EvalCall
  ???

defined function eval

Tests

def evalTest(e: Expr): Expr = {
  eval(empty, e)
}
test(new AnyFlatSpec {
  val testcase1 = {
    val a = "a"
    val f = "f"
    val e1 = Binary(Plus, N(3), Var(a))
    val e2 = Binary(Plus, Var("x"), N(1))
    val e3 = ConstDecl("x", e1, e2)
    val e4 = Fun(a, e3)
    val e5 = ConstDecl(f, e4, Call(Var(f), N(2)))
    evalTest(e5)
  }
  val testcase2 = {
    val a1 = "a1"
    val a2 = "a2"
    val x = "x"
    val e1 = Fun(a1, Var(x))
    val e2 = ConstDecl(x, N(40), Call(e1, N(-1)))    
    val e3 = Fun(a2, e2)
    val e4 = ConstDecl(x, N(10), Call(e3, N(-1)))
    evalTest(e4)
  }
  val testcase3 = {
    val f = "f"
    val a = "a"
    val e1 = Binary(Plus, Var(a), Var(a))
    val e2 = Fun(a, e1)
    val e3 = Fun(f, Call(e2, N(5)))
    evalTest(Call(e3, e2))
  }
  val testcase4 = {
    Call(N(4), B(true))
  }
  val testcase5 = {
    Binary(Ne, B(false), Fun("a", N(2)))
  }
  val testcase6 = {
    evalTest(ConstDecl( "x", N(30), ConstDecl("f", Fun("a", Var("x")), ConstDecl("g", Fun( "b", ConstDecl("x", N(20), Call(Var("f"), N(-1)))),Call(Var("g"), N(-1))))))
  }
  it should "Test Case 1" in { assertResult( N(6) ) { testcase1 } }
  it should "Test Case 2" in { assertResult( N(40) ) { testcase2 } }
  it should "Test Case 3" in { assertResult( N(10) ) { testcase3 } }
  it should "Test Case 4" in { intercept[DynamicTypeError] {evalTest(testcase4)} }
  it should "Test Case 5" in { intercept[DynamicTypeError] {evalTest(testcase5)} }
  it should "Test Case 6" in { assertResult( N(30) ) { testcase6 } }
}, 10)

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd13$Helper.eval(cmd13.sc:11)
  ammonite.$sess.cmd14$Helper.evalTest(cmd14.sc:2)
  ammonite.$sess.cmd14$Helper$$anon$1.<init>(cmd14.sc:13)
  ammonite.$sess.cmd14$Helper.<init>(cmd14.sc:4)
  ammonite.$sess.cmd14$.<clinit>(cmd14.sc:7)

This code tests your new implementation against the dynamic scoping test case you wrote:

def evalTest(e: Expr): Expr = {
  eval(empty, e)
}
evalTest(testAST)

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd3$Helper.testAST(cmd3.sc:8)
  ammonite.$sess.cmd15$Helper.<init>(cmd15.sc:4)
  ammonite.$sess.cmd15$.<clinit>(cmd15.sc:7)

If you’re implementation is correct, it should evaluate to what a JavaScript interpreter evaluates it to.

20.5 Implementing Recursive Functions (Accelerated)

The remaining exercises are for those who want to go deeper and take an “accelerated” version of this course.

We begin by extending our abstract syntax to allow for recursive functions. To call a function within itself, we permit functions to have a variable identifier to refer to itself. If the identifier is present, then it can be used for recursion.

\[\begin{array}{rlrll} \text{expressions} & e& \mathrel{::=}& x^{?}\texttt{(}y\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e_1 \mid e_1\texttt{(}e_2\texttt{)} \\ \text{optional variables} & x^{?}& \mathrel{::=}& x\mid\varepsilon \\ \text{variables} & x \end{array}\]

20.5.1 Defining Inference Rules

Exercise 20.11 (10 points) To allow for recursion, at a function call, we must bind the function identifier to the function value when evaluating the function body. Give a inference rule called $\TirName{EvalCallRec}$ that describes this semantics.

Edit this cell:

???

20.5.2 Writing a Test Case

Exercise 20.12 (1 point) Write a function sumOneToN that computes the sum from 1 to n using the fragment of JavaScripty in this assignment.

Edit this cell:

function sumOneToN(n) 
  ???

In order to allow for recursive, we must edit our Fun constructor to accept an optional variable. (We must also re-run the other constructor and helper functions that rely on Fun.)

case class Fun(xopt: Option[String], y: String, e1: Expr) extends Expr 
case class Closure(fun: Fun, env: Env) extends Expr 
def isValue(e: Expr): Boolean = e match {
  case N(_) | B(_) | Closure(_, _) => true
  case _ => false
}
def extend(env: Env, x: String, v: Expr): Env = {
  require(isValue(v))
  env + (x -> v)
}

defined class Fun
defined class Closure
defined function isValue
defined function extend

Exercise 20.13 (4 points) Now that we have an abstract syntax tree node to write recursive functions, create an Expr that is a recursive function which computes the sum from 1 to a parameter n. This will be used in a test case for an updated version of eval. Write out the AST that your sumOneToN function will be parsed to.

Edit this cell:

val recTestAST: Expr = 
  ???

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd17$Helper.<init>(cmd17.sc:2)
  ammonite.$sess.cmd17$.<clinit>(cmd17.sc:7)

Exercise 20.14 (10 points) Rewrite your eval function to handle recursive functions.

def eval(env: Env, e: Expr): Expr = 
  ???

defined function eval

This cell tests your implementation against your test case sumOneToN.

def evalTest(e: Expr): Expr = {
  eval(empty, e)
}
test(new AnyFlatSpec {
  val yourSumOneToN = evalTest(Call(recTestAST, N(10)))
  it should "Compute 1 to N of 10 correctly" in { assertResult( N(55) ) { yourSumOneToN } }
}, 5)

cmd19.sc:5: not found: value recTestAST
  val yourSumOneToN = evalTest(Call(recTestAST, N(10)))
                                    ^Compilation Failed

: 
Compilation Failed

Tests

def evalTest(e: Expr): Expr = {
  eval(empty, e)
}
test(new AnyFlatSpec {
  val testcase1 = {
    val f = "f"
    val x = "x"
    val fbody = If(
      Binary(Eq, Var(x), N(10)),
      Var(x),
      Binary(Plus, Var(x), Call(Var(f), Binary(Plus, Var(x), N(1))))
    )
    val e1 = Fun(Some(f), x, fbody)
    val e2 = N(3) 
    evalTest(Call(e1, e2)) 
  }
  val testcase2 = {
    val a1 = "a1"
    val a2 = "a2"
    val x = "x"
    val e1 = Fun(None, a1, Var(x))
    val e2 = ConstDecl(x, N(40), Call(e1, N(-1)))    
    val e3 = Fun(None, a2, e2)
    val e4 = ConstDecl(x, N(10), Call(e3, N(-1)))
    evalTest(e4)
  }
 
  it should "Test Case 1" in { assertResult( N(52) ) { testcase1 } }
  it should "Test Case 2" in { assertResult( N(40) ) { testcase2 } }

}, 5)

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd18$Helper.eval(cmd18.sc:2)
  ammonite.$sess.cmd19$Helper.evalTest(cmd19.sc:2)
  ammonite.$sess.cmd19$Helper$$anon$1.<init>(cmd19.sc:15)
  ammonite.$sess.cmd19$Helper.<init>(cmd19.sc:4)
  ammonite.$sess.cmd19$.<clinit>(cmd19.sc:7)