22  Lab: Small-Step Operational Semantics

$$

Learning Goals

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

• the distinction between a big-step and a small-step operational semantics;
• evaluation order; and
• substitution and program transformation.

Functional Programming Skills

Iteration. Introduction to higher-order functions.

Programming Language Ideas

Semantics: evaluation order. Small-step operational semantics. Substitution and program transformation.

Instructions

A version of project files for this lab resides in the public pppl-lab3 repository. Please follow separate instructions to get a private clone of this repository for your work.

You will be replacing ??? or case _ => ??? in the Lab3.scala file with solutions to the coding exercises described below.

Your lab will not be graded if it does not compile. You may check compilation with your IDE, sbt compile, or with the “sbt compile” GitHub Action provided for you. Comment out any code that does not compile or causes a failing assert. Put in ??? as needed to get something that compiles without error.

You may add additional tests to the Lab3Spec.scala file. In the Lab3Spec.scala, there is empty test class Lab3StudentSpec that you can use to separate your tests from the given tests in the Lab3Spec class. You are also likely to edit Lab3.worksheet.sc for any scratch work. You can also use Lab3.worksheet.js to write and experiment in a JavaScript file that you can then parse into a JavaScripty AST (see Lab3.worksheet.sc).

If you like, you may use this notebook for experimentation. However, please make sure your code is in Lab3.scala; code in this notebook will not graded.

Note that there is a section with concept exercises (Section 22.6). Make sure to complete the concept exercises in that section and turn in this file as part of your submission for the concept exercises. However, all code and testing exercises from other sections are submitted in Lab3.scala or Lab3Spec.scala.

Recall that you need to switch kernels between running JavaScript and Scala cells.

22.1 Small-Step Interpreter: JavaScripty Functions

We consider the same JavaScripty variant as in the previous exercise on big-step operational semantics (Section 20.1) where the interesting language feature are first-class functions:

trait Expr
case class Fun(xopt: Option[String], y: String, e1: Expr) extends Expr // e ::= x?(y) => e1
case class Call(e1: Expr, e2: Expr) extends Expr                       // e ::= e1(e2) 

defined trait Expr
defined class Fun
defined class Call

We consider a Fun constructor for representing JavaScripty function literals. This version of Fun allows for named functions. When a function expression $x\mathtt{\text{(}}y\mathtt{\text{)}}\mathtt{\text{=}}\mathtt{\text{>}}{e}^{\prime }$ has a name, then it is can be recursive. As noted previously about recursive functions (Section 19.5), variable $x$ is an additional formal parameter, and the function body $e^{\prime }$ may have free variable uses of $x$. The variable $x$ gets bound to itself (i.e., the function value for $x\mathtt{\text{(}}y\mathtt{\text{)}}\mathtt{\text{=}}\mathtt{\text{>}}{e}^{\prime }$) on a function call.

In the abstract syntax representation, the xopt: Option[String] parameter in our Fun constructor is None if there is no identifier present (cannot be used recursively), or Some(x: String) if there is an identifier, x, present (can be used recursively).

In this lab, we will do two things. First, we will move to implementing a small-step interpreter with a function step that takes an e: Expr and returns a one-step reduction of e. A small-step interpreter makes explicit the evaluation order of expressions. Second, we will remove environments and instead use a language semantics based on substitution. This change will result in static, lexical scoping without needing closures, thus demonstrating another way to fix dynamical scoping.

These two changes are orthogonal, that is, one could implement a big-step interpreter using substitution (as in Section 19.4) or a small-step interpreter using environments. Substitution is a fairly simple way to get lexical scoping, but in practice, it is rarely used because it is not the most efficient implementation.

22.2 Static Scoping

Exercise 22.1 (Substitute) Since our implementation requires substitution, we begin by implementing substitute, which substitutes value v for all free occurrences of variable x in expression e:

def substitute(e: Expr, v: Expr, x: String): Expr = ???

defined function substitute

We advise defining substitute by induction on e. The cases to be careful about are ConstDecl and Fun because these are the variable binding constructs (as discussed in the reading on substitution in Section 21.9). In particular, calling substitute on expression

a; { const a = 4; a }

with value 3 for variable a should return

3; { const a = 4; a }

not

3; { const a = 4; 3 }

This function is a helper for the step function, but you might want to implement all of the cases of step that do not require substitute first.

22.3 Iteration

Our step performs a single reduction step. We may want to test it by repeatedly calling it with an expression until reducing to value. Thus, from a software engineering standpoint, you might want to evolve the iterate function described below together with your implementation of step.

This idea of repeatedly performing an action until some condition is satisfied is a loop or iteration. We have seen that we can iterate with a tail-recursive helper function. For example, consider the sumTo function that sums the integers from 0 to n:

def sumTo(n: Int): Int = {
  def loop(acc: Int, i: Int): Int = {
    require(n >= 0)
    if (i > n) acc
    else loop(acc + i, i + 1)
  }
  loop(0, 0)
}
sumTo(100)

defined function sumTo
res2_1: Int = 5050

This pattern of repeating something until a condition is satisfied is exceedingly common (e.g., computing the square root using Newton-Raphson approximation until the error is small enough from a previous assignment).

Because this pattern is so common, we want to get practice refactoring this pattern into a library function. This library function will be a higher-order function because it takes the “something” (i.e., what to do in each loop iteration) as a function parameter.

Exercise 22.2 (Iterate with Error Side-Effects) Implement the generic, higher-order library function iterateBasic. The iterateBasic function repeatedly calls (i.e., iterates) the callback stepi until it returns None starting from acc0: A. Note that iterateBasic is generic in the accumulation type A. The stepi callback takes the current accumulator of type A and the iteration number as an Int and indicates continuing by returning Some(acc) for some next accumulator value acc.

def iterateBasic[A](acc0: A)(stepi: (A, Int) => Option[A]): A = {
  def loop(acc: A, i: Int): A = ???
  loop(acc0, 0)
}

defined function iterateBasic

We can test iterateBasic by using it with a client like sumTo:

def sumTo(n: Int) = {
  iterateBasic(0) { case (acc, i) =>
    require(n >= 0)
    if (i > n) None
    else Some(acc + i)
  }
}
sumTo(100)

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd3$Helper.loop$1(cmd3.sc:2)
  ammonite.$sess.cmd3$Helper.iterateBasic(cmd3.sc:3)
  ammonite.$sess.cmd4$Helper.sumTo(cmd4.sc:2)
  ammonite.$sess.cmd4$Helper.<init>(cmd4.sc:8)
  ammonite.$sess.cmd4$.<clinit>(cmd4.sc:7)

We see how sumTo can use iterateBasic.

Exercise 22.3 (Iterate with Error Values) One unfortunate aspect of the above is that sumTo “exits iterateBasic with an error” by throwing an exception (i.e., with the require(n >= 0)). Let us refactor iterateBasic to allow for explicit error values using Either[Err, A]:

def iterate[Err, A](acc0: A)(stepi: (A, Int) => Option[Either[Err, A]]): Either[Err, A] = {
  def loop(acc: A, i: Int): Either[Err, A] = ???
  loop(acc0, 0)
}

def sumTo(n: Int): Either[IllegalArgumentException, Int] = {
  iterate(0) { case (acc, i) =>
    if (n < 0) Some(Left(new IllegalArgumentException("requirement failed")))
    else if (i > n) None
    else Some(Right(acc + i))
  }
}
sumTo(100)
sumTo(-1)

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd5$Helper.loop$1(cmd5.sc:2)
  ammonite.$sess.cmd5$Helper.iterate(cmd5.sc:3)
  ammonite.$sess.cmd5$Helper.sumTo(cmd5.sc:7)
  ammonite.$sess.cmd5$Helper.<init>(cmd5.sc:13)
  ammonite.$sess.cmd5$.<clinit>(cmd5.sc:7)

The iterate is now parametrized by an error type Err and returns an Either[Err, A]. The stepi callback should return None if it wants to stop normally, Some(Left(err)) if it wants to stop with an error, and Some(Right(acc) if it wants to continue with an accumulator value acc.

We can now see how we can use iterate as a library function to iterate your step implementation. In particular, this is how iterate will be used to iterate step while adding some debugging output:

def iterateStep(e: Expr) = {
  require(closed(e), s"iterateStep: ${e} not closed")
  if (debug) {
    println("------------------------------------------------------------")
    println("Evaluating with step ...")
  }
  val v = iterate(e) { (e: Expr, n: Int) =>
    if (debug) { println(s"Step $n: $e") }
    if (isValue(e)) None else Some(step(e))
  }
  if (debug) { println("Value: " + v) }
  v
}

Of particular interest is the anonymous function passed to iterate that calls your implementation of step.

22.4 Small-Step Interpreter

In this section, we implement the one-step evaluation judgment form $e⟶r$ that says, “Expression $e$ can take one step of evaluation to a step-result $r$.”

$$\begin{array}{rrrl}\text{step-results}& r& ::=& \mathsf{typeerror}e\mid e^{\prime }\end{array}$$

A step-result $r$ is either a $\mathsf{typeerror}e$ indicating a dynamic type error in attempting to reduce $e$ or a successful one-step reduction to an expression $e^{\prime }$.

We represent a step-result $r$ in Scala using a type Either[DynamicTypeError, Expr]:

case class DynamicTypeError(e: Expr) {
  override def toString = s"TypeError: in expression $e"
}
type Result = Either[DynamicTypeError, Expr] // r ::= typeerror e | e

defined class DynamicTypeError
defined type Result

Note that unlike before, DynamicTypeError is not an Exception, so it cannot be thrown.

The small-step semantics that we should implement are given in the section below (Section 22.5). The language we implement is JavaScripty with numbers, booleans, strings, $\mathbf{undefined}$, printing, and first-class functions. It is a simpler language than the previous lab because we remove type coercions (except to booleans) and replace most coercion cases with dynamic type error $\mathsf{typeerror}e$.

Exercise 22.4 (Step without Dynamic Type Checking) We advise first implementing the cases restricted to judgments of the form $e⟶e^{\prime }$, that is, implement the $\text{Do}$ and $\text{Search}$ rules while ignoring the $\text{TypeError}$ and $\text{Propagate}$ rules. Start with implementing a stepBasic function with type:

def stepBasic(e: Expr): Expr = ???

defined function stepBasic

That is, just crash with a MatchError exception if your step encounters any ill-typed expression e.

The suggested practice here is to read some rules, write a few tests for those rules, and implement the cases for those tests.

Exercise 22.5 (Step with Dynamic Type Checking) Then, copy your code from stepBasic to stepCheck:

def stepCheck(e: Expr): Either[DynamicTypeError, Expr] = ???

defined function stepCheck

to then add dynamic type checking. You will likely need to refactor your code to satisfy the new types before implementing the $\text{TypeError}$ and $\text{Propagate}$ rules.

Exercise 22.6 (To Boolean) You will need to implement a toBoolean function to convert JavaScripty values to booleans, following the $\text{ToBoolean}$ rules in Section 22.5.

def toBoolean(e: Expr): Boolean = ???

defined function toBoolean

However, you will not need any other type coercion functions here.

Notes

• Note that the tests call the step function that is originally defined as:

  //def step(e: Expr): Either[DynamicTypeError, Expr] = Right(stepBasic(e))
  def step(e: Expr): Either[DynamicTypeError, Expr] = stepCheck(e)

  You can first test stepBasic by uncommenting the first line and commenting out the second line.

• Note that the provided tests are minimal. You will want to add your own tests to cover most language features.

22.5 Small-Step Operational Semantics

In this section, we give the small-step operational semantics for JavaScripty with numbers, booleans, strings, $\mathbf{undefined}$, printing, and first-class functions. We have type coercions to booleans but otherwise use dynamic type error for other cases.

We write $[v/x]e$ for substituting value $v$ for all free occurrences of the variable $x$ in expression $e$ (i.e., a call to substitute).

It is informative to compare the small-step semantics used in this lab and the big-step semantics from last homework.

22.5.1 Do Rules

$\boxed{e⟶e^{\prime }}$

$\begin{array}{l}\text{DoNeg}\\ {\displaystyle \frac{n^{\prime }=-n_1}{\mathtt{\text{-}}{n}_1⟶n^{\prime }}}\end{array}$

$\begin{array}{l}\text{DoArith}\\ {\displaystyle \frac{n^{\prime }=n_1\mathit{bop}{n}_2\mathit{bop}\in \{\mathtt{\text{+}},\mathtt{\text{-}},\mathtt{\text{*}},\mathtt{\text{/}}\}}{n_1\mathit{bop}{n}_2⟶n^{\prime }}}\end{array}$

$\begin{array}{l}\text{DoPlusString}\\ {\displaystyle \frac{{\mathit{str}}^{\prime }={\mathit{str}}_1{\mathit{str}}_2}{{\mathit{str}}_1\mathtt{\text{+}}{\mathit{str}}_2⟶{\mathit{str}}^{\prime }}}\end{array}$

$\begin{array}{l}\text{DoInequalityNumber}\\ {\displaystyle \frac{b^{\prime }=n_1\mathit{bop}{n}_2\mathit{bop}\in \{\mathtt{\text{<}},\mathtt{\text{<=}},\mathtt{\text{>}},\mathtt{\text{>=}}\}}{n_1\mathit{bop}{n}_2⟶b^{\prime }}}\end{array}$

$\begin{array}{l}\text{DoInequalityString}\\ {\displaystyle \frac{b^{\prime }={\mathit{str}}_1\mathit{bop}{\mathit{str}}_2\mathit{bop}\in \{\mathtt{\text{<}},\mathtt{\text{<=}},\mathtt{\text{>}},\mathtt{\text{>=}}\}}{{\mathit{str}}_1\mathit{bop}{\mathit{str}}_2⟶b^{\prime }}}\end{array}$

$\begin{array}{l}\text{DoEquality}\\ {\displaystyle \frac{b^{\prime }=(v_1\mathit{bop}{v}_2)\mathit{bop}\in \{\mathtt{\text{===}},\mathtt{\text{!==}}\}}{v_1\mathit{bop}{v}_2⟶b^{\prime }}}\end{array}$

$\begin{array}{l}\text{DoNot}\\ {\displaystyle \frac{v_1⇝b_1}{\mathtt{\text{!}}{v}_1⟶\mathrm{\neg }{b}_1}}\end{array}$

$\begin{array}{l}\text{DoAndTrue}\\ {\displaystyle \frac{v_1⇝\mathbf{true}}{v_1\mathtt{\text{\&\&}}{e}_2⟶e_2}}\end{array}$

$\begin{array}{l}\text{DoAndFalse}\\ {\displaystyle \frac{v_1⇝\mathbf{false}}{v_1\mathtt{\text{\&\&}}{e}_2⟶v_1}}\end{array}$

$\begin{array}{l}\text{DoOrTrue}\\ {\displaystyle \frac{v_1⇝\mathbf{true}}{v_1\mathtt{\text{||}}{e}_2⟶v_1}}\end{array}$

$\begin{array}{l}\text{DoOrFalse}\\ {\displaystyle \frac{v_1⇝\mathbf{false}}{v_1\mathtt{\text{||}}{e}_2⟶e_2}}\end{array}$

$\begin{array}{l}\text{DoIfTrue}\\ {\displaystyle \frac{v_1⇝\mathbf{true}}{v_1\mathtt{\text{?}}{e}_2\mathtt{\text{:}}{e}_3⟶e_2}}\end{array}$

$\begin{array}{l}\text{DoIfFalse}\\ {\displaystyle \frac{v_1⇝\mathbf{false}}{v_1\mathtt{\text{?}}{e}_2\mathtt{\text{:}}{e}_3⟶e_3}}\end{array}$

$\begin{array}{l}\text{DoSeq}\\ {\displaystyle \frac{}{v_1\mathtt{\text{,}}{e}_2⟶e_2}}\end{array}$

$\begin{array}{l}\text{DoPrint}\\ {\displaystyle \frac{v_1\text{ printed}}{\mathtt{\text{console}}\mathtt{\text{.}}\mathtt{\text{log}}\mathtt{\text{(}}{v}_1\mathtt{\text{)}}⟶\mathbf{undefined}}}\end{array}$

$\begin{array}{l}\text{DoConst}\\ {\displaystyle \frac{}{\mathbf{const}x\mathtt{\text{=}}{v}_1\mathtt{\text{;}}{e}_2⟶[v_1/x]e_2}}\end{array}$

$\begin{array}{l}\text{DoCall}\\ {\displaystyle \frac{}{(\mathtt{\text{(}}x\mathtt{\text{)}}\mathtt{\text{=}}\mathtt{\text{>}}{e}_1)\mathtt{\text{(}}{v}_2\mathtt{\text{)}}⟶[v_2/x]e_1}}\end{array}$

$\begin{array}{l}\text{DoCallRec}\\ {\displaystyle \frac{v_1=(x_1\mathtt{\text{(}}{x}_2\mathtt{\text{)}}\mathtt{\text{=}}\mathtt{\text{>}}{e}_1)}{v_1\mathtt{\text{(}}{v}_2\mathtt{\text{)}}⟶[v_1/x_1][v_2/x_2]e_1}}\end{array}$

Figure 22.1: The $\text{Do}$ rules for JavaScripty with numbers, booleans, strings, $\mathbf{undefined}$, printing, and first-class functions.

22.5.2 Search Rules

$\boxed{e⟶e^{\prime }}$

$\begin{array}{l}\text{SearchUnary}\\ {\displaystyle \frac{e_1⟶e_1^{\prime }}{\mathit{uop}{e}_1⟶\mathit{uop}{e}_1^{\prime }}}\end{array}$

$\begin{array}{l}\text{SearchBinary1}\\ {\displaystyle \frac{e_1⟶e_1^{\prime }}{e_1\mathit{bop}{e}_2⟶e_1^{\prime }\mathit{bop}{e}_2}}\end{array}$

$\begin{array}{l}\text{SearchBinary2}\\ {\displaystyle \frac{e_2⟶e_2^{\prime }}{v_1\mathit{bop}{e}_2⟶v_1\mathit{bop}{e}_2^{\prime }}}\end{array}$

$\begin{array}{l}\text{SearchIf}\\ {\displaystyle \frac{e_1⟶e_1^{\prime }}{e_1\mathtt{\text{?}}{e}_2\mathtt{\text{:}}{e}_3⟶e_1^{\prime }\mathtt{\text{?}}{e}_2\mathtt{\text{:}}{e}_3}}\end{array}$

$\begin{array}{l}\text{SearchPrint}\\ {\displaystyle \frac{e_1⟶e_1^{\prime }}{\mathtt{\text{console}}\mathtt{\text{.}}\mathtt{\text{log}}\mathtt{\text{(}}{e}_1\mathtt{\text{)}}⟶\mathtt{\text{console}}\mathtt{\text{.}}\mathtt{\text{log}}\mathtt{\text{(}}{e}_1^{\prime }\mathtt{\text{)}}}}\end{array}$

$\begin{array}{l}\text{SearchConst}\\ {\displaystyle \frac{e_1⟶e_1^{\prime }}{\mathbf{const}x\mathtt{\text{=}}{e}_1\mathtt{\text{;}}{e}_2⟶\mathbf{const}x\mathtt{\text{=}}{e}_1^{\prime }\mathtt{\text{;}}{e}_2}}\end{array}$

$\begin{array}{l}\text{SearchCall1}\\ {\displaystyle \frac{e_1⟶e_1^{\prime }}{e_1\mathtt{\text{(}}{e}_2\mathtt{\text{)}}⟶e_1^{\prime }\mathtt{\text{(}}{e}_2\mathtt{\text{)}}}}\end{array}$

$\begin{array}{l}\text{SearchCall2}\\ {\displaystyle \frac{e_2⟶e_2^{\prime }}{v_1\mathtt{\text{(}}{e}_2\mathtt{\text{)}}⟶v_1\mathtt{\text{(}}{e}_2^{\prime }\mathtt{\text{)}}}}\end{array}$

Figure 22.2: The $\text{Search}$ rules for JavaScripty with numbers, booleans, strings, $\mathbf{undefined}$, printing and first-class functions.

22.5.3 Coercing to Boolean

$\boxed{v⇝b}$

$\begin{array}{l}\text{ToBooleanNumFalse}\\ {\displaystyle \frac{n\in \{0.0,-0.0,\mathsf{NaN}\}}{n⇝\mathbf{false}}}\end{array}$

$\begin{array}{l}\text{ToBooleanNumTrue}\\ {\displaystyle \frac{n\notin \{0.0,-0.0,\mathsf{NaN}\}}{n⇝\mathbf{true}}}\end{array}$

$\begin{array}{l}\text{ToBooleanBoolean}\\ {\displaystyle \frac{}{b⇝b}}\end{array}$

$\begin{array}{l}\text{ToBooleanStrFalse}\\ {\displaystyle \frac{}{\mathtt{\text{""}}⇝\mathbf{false}}}\end{array}$

$\begin{array}{l}\text{ToBooleanStrTrue}\\ {\displaystyle \frac{\mathit{str}\ne \mathtt{\text{""}}}{\mathit{str}⇝\mathbf{true}}}\end{array}$

$\begin{array}{l}\text{ToBooleanUndefined}\\ {\displaystyle \frac{}{\mathbf{undefined}⇝\mathbf{false}}}\end{array}$

$\begin{array}{l}\text{ToBooleanFun}\\ {\displaystyle \frac{}{x^{?}\mathtt{\text{(}}y\mathtt{\text{)}}\mathtt{\text{=}}\mathtt{\text{>}}e⇝\mathbf{true}}}\end{array}$

Figure 22.3: The $\text{ToBoolean}$ rules for JavaScripty with numbers, booleans, strings, $\mathbf{undefined}$, and first-class functions.

22.5.4 Dynamic Typing Rules

$\boxed{e⟶r}$

$\begin{array}{l}\text{TypeErrorNeg}\\ {\displaystyle \frac{v_1\ne n_1}{\mathtt{\text{-}}{v}_1⟶\mathsf{typeerror}(\mathtt{\text{-}}{v}_1)}}\end{array}$

$\begin{array}{l}\text{TypeErrorPlus1}\\ {\displaystyle \frac{v_1\ne n_1{v}_1\ne {\mathit{str}}_1}{v_1\mathtt{\text{+}}{v}_2⟶\mathsf{typeerror}(v_1\mathtt{\text{+}}{v}_2)}}\end{array}$

$\begin{array}{l}\text{TypeErrorPlusString2}\\ {\displaystyle \frac{v_2\ne {\mathit{str}}_2}{{\mathit{str}}_1\mathtt{\text{+}}{v}_2⟶\mathsf{typeerror}({\mathit{str}}_1\mathtt{\text{+}}{v}_2)}}\end{array}$

$\begin{array}{l}\text{TypeErrorArith1}\\ {\displaystyle \frac{v_1\ne n_1\mathit{bop}\in \{\mathtt{\text{-}},\mathtt{\text{*}},\mathtt{\text{/}}\}}{v_1\mathit{bop}{v}_2⟶\mathsf{typeerror}(v_1\mathit{bop}{v}_2)}}\end{array}$

$\begin{array}{l}\text{TypeErrorArith2}\\ {\displaystyle \frac{v_2\ne n_2\mathit{bop}\in \{\mathtt{\text{+}},\mathtt{\text{-}},\mathtt{\text{*}},\mathtt{\text{/}}\}}{n_1\mathit{bop}{v}_2⟶\mathsf{typeerror}(n_1\mathit{bop}{v}_2)}}\end{array}$

$\begin{array}{l}\text{TypeErrorInequality1}\\ {\displaystyle \frac{v_1\ne n_1{v}_1\ne {\mathit{str}}_1\mathit{bop}\in \{\mathtt{\text{<}},\mathtt{\text{<=}},\mathtt{\text{>}},\mathtt{\text{>=}}\}}{v_1\mathit{bop}{v}_2⟶\mathsf{typeerror}(v_1\mathit{bop}{v}_2)}}\end{array}$

$\begin{array}{l}\text{TypeErrorInequalityNumber2}\\ {\displaystyle \frac{v_2\ne n_2\mathit{bop}\in \{\mathtt{\text{<}},\mathtt{\text{<=}},\mathtt{\text{>}},\mathtt{\text{>=}}\}}{n_1\mathit{bop}{v}_2⟶\mathsf{typeerror}(n_1\mathit{bop}{v}_2)}}\end{array}$

$\begin{array}{l}\text{TypeErrorInequalityString2}\\ {\displaystyle \frac{v_2\ne {\mathit{str}}_2\mathit{bop}\in \{\mathtt{\text{<}},\mathtt{\text{<=}},\mathtt{\text{>}},\mathtt{\text{>=}}\}}{{\mathit{str}}_1\mathit{bop}{v}_2⟶\mathsf{typeerror}({\mathit{str}}_1\mathit{bop}{v}_2)}}\end{array}$

$\begin{array}{l}\text{TypeErrorCall}\\ {\displaystyle \frac{v_1\ne x^{?}\mathtt{\text{(}}y\mathtt{\text{)}}\mathtt{\text{=}}\mathtt{\text{>}}{e}_1}{v_1\mathtt{\text{(}}{v}_2\mathtt{\text{)}}⟶\mathsf{typeerror}(v_1\mathtt{\text{(}}{v}_2\mathtt{\text{)}})}}\end{array}$

$\begin{array}{l}\text{PropagateUnary}\\ {\displaystyle \frac{e_1⟶\mathsf{typeerror}e}{\mathit{uop}{e}_1⟶\mathsf{typeerror}e}}\end{array}$

$\begin{array}{l}\text{PropagateBinary1}\\ {\displaystyle \frac{e_1⟶\mathsf{typeerror}e}{e_1\mathit{bop}{e}_2⟶\mathsf{typeerror}e}}\end{array}$

$\begin{array}{l}\text{PropagateBinary2}\\ {\displaystyle \frac{e_2⟶\mathsf{typeerror}e}{v_1\mathit{bop}{e}_2⟶\mathsf{typeerror}e}}\end{array}$

$\begin{array}{l}\text{PropagateIf}\\ {\displaystyle \frac{e_1⟶\mathsf{typeerror}e}{e_1\mathtt{\text{?}}{e}_2\mathtt{\text{:}}{e}_3⟶\mathsf{typeerror}e}}\end{array}$

$\begin{array}{l}\text{PropagatePrint}\\ {\displaystyle \frac{e_1⟶\mathsf{typeerror}e}{\mathtt{\text{console}}\mathtt{\text{.}}\mathtt{\text{log}}\mathtt{\text{(}}{e}_1\mathtt{\text{)}}⟶\mathsf{typeerror}e}}\end{array}$

$\begin{array}{l}\text{PropagateConst}\\ {\displaystyle \frac{e_1⟶\mathsf{typeerror}e}{\mathbf{const}x\mathtt{\text{=}}{e}_1\mathtt{\text{;}}{e}_2⟶\mathsf{typeerror}e}}\end{array}$

$\begin{array}{l}\text{PropagateCall1}\\ {\displaystyle \frac{e_1⟶\mathsf{typeerror}e}{e_1\mathtt{\text{(}}{e}_2\mathtt{\text{)}}⟶\mathsf{typeerror}e}}\end{array}$

$\begin{array}{l}\text{PropagateCall2}\\ {\displaystyle \frac{e_2⟶\mathsf{typeerror}e}{v_1\mathtt{\text{(}}{e}_2\mathtt{\text{)}}⟶\mathsf{typeerror}e}}\end{array}$

Figure 22.4: The $\text{TypeError}$ and $\text{Propagate}$ rules for JavaScripty with numbers, booleans, strings, $\mathbf{undefined}$, printing, and first-class functions.

22.6 Concept Exercises

Make sure to complete the concept exercises in this section and turn in this file as part of your submission. However, all code and testing exercises from other sections are submitted in Lab3.scala or Lab3Spec.scala.

Exercise 22.7 (Evaluation Order) Consider the small-step operational semantics shown in Section 22.5. What is the evaluation order for $e_1\mathtt{\text{+}}{e}_2$? Explain.

Edit this cell:

???

Exercise 22.8 (Changing Evaluation Order) How do we change the rules to obtain the opposite evaluation order?

Edit this cell:

???

Exercise 22.9 (Using Short-Circuit Evaluation) Give an example that illustrates the usefulness of short-circuit evaluation. Explain your example.

Edit this cell:

???

Exercise 22.10 (Removing Short-Circuit Evaluation) Consider the small-step operational semantics shown in Section 22.5. Does $e_1\mathtt{\text{\&\&}}{e}_2$ short circuit? Explain. If $e_1\mathtt{\text{\&\&}}{e}_2$ short circuits, give rules that eliminates short circuiting. If it does not short circuit, give the short-circuiting rules.

Edit this cell:

???

22.7 Testing

This section has some space to write some tests in our subset of JavaScript. You might want to work on these tests while you are implementing step. As before, you will add your tests to Lab3StudentSpec. Your interpreter will run the tests against the expected result you provide. We will write three tests, all of these tests must properly parse.

Exercise 22.11 (Test 1: Higher-Order Function) Write a test case that has a function that takes a function value as an argument (i.e., is a higher order function):

???

Exercise 22.12 (Test 2: Recursion) Write a test case that uses recursion

???

Exercise 22.13 (Test 3: Any Test in this variant of JavaScripty) Write another test

???

Notes

• Remember to add these to Lab3StudentSpec in Lab3Spec.scala.
• Add the JavaScripty code as a string in jsyStr and the expected result in answer.

22.8 Accelerated Component

For the accelerated component of this lab, we will give rules and implement the behavior that enables us to match JavaScript semantics. In particular, we will give rules and implement type coercions for numbers and strings, and we will update our small-step operational semantics to use them.

22.8.1 Additional Type Coercions

Exercise 22.14 Give the inference rules defining the judgment form for coercing a value to a number $v⇝n$

Edit this cell:

???

Exercise 22.15 Give the inference rules defining the judgment form for coercing a value to a string $v⇝\mathit{str}$

Edit this cell:

???

Exercise 22.16 Implement the toNumber and toStrcoercions.

def toNumber(v: Expr): Double = ???
def toStr(v: Expr): String = ???

defined function toNumber
defined function toStr

Notes

• If your recall Lab 2, we implemented these functions. They will be the same here, except we must add the rules for functions.

22.8.2 Updating the Small-Step Operational Semantics

Now that we are allowing type coersions, our operational semantics will change. For example, consider the following $\text{Do}$ rule:

$\begin{array}{l}\text{DoNeg}\\ {\displaystyle \frac{v⇝n}{\mathtt{\text{-}}v⟶-n}}\end{array}$

This is a new rule for $\text{DoNeg}$, which is read as if $v$ coerces to $n$, then $\mathtt{\text{-}}v$ steps to $-n$. Now that we are allowing non-numbers to be coerced and then negated, we no longer have our $\text{TypeErrorNeg}$ rule.

Note that we only need to update $\text{Do}$ rules with coercions and remove $\text{TypeError}$ rules. We do not need to update the $\text{Search}$ or $\text{Propagage}$ rules.

Exercise 22.17 Explain why we only need to update the $\text{Do}$ rules with coercions and remove $\text{TypeError}$ rules, and we do not need to update the $\text{Search}$ or $\text{Propagage}$ rules.

Edit this cell:

???

One rule of particular interest is $\text{DoArith}$, which we need to split to account for $e_1\mathtt{\text{+}}{e}_2$ being overloaded for numbers and strings. Given this, we need to rewrite $\text{DoArith}$ so it does not include $\mathtt{\text{+}}$ (and adds coersions), add the rule $\text{DoPlusNumber}$, and alter $\text{DoPlusString}$ to become two rules.

Exercise 22.18 Give these new $\text{Do}$ rules

Edit this cell:

???

Similar to this, our $\text{DoInequalityNumber}$ rule must be split into two and altered:

Exercise 22.19 Give the two new $\text{DoInequalityNumber}{}_1$ and $\text{DoInequalityNumber}{}_2$ rules:

Edit this cell:

???

Once we have all of these rules defined, we notice that most of our $\mathsf{typeerror}$ rules no longer result in type errors. Therefore, most of them should be deleted. In fact, the only non-propagate rule left for type errors is $\text{TypeErrorCall}$, since we are still not allowed to call something that is not a function (in JavaScript).

22.8.3 Update Step

Exercise 22.20 Now that we have our type conversion functions implemented and our new rules defined, we are ready to update step. Implement stepCoerce by first copying your code from stepCheck and then update based on your new rules.

def stepCoerce(e: Expr): Either[DynamicTypeError,Expr] = ???

defined function stepCoerce

As before, let the rules guide your implementation.

Notes

• None of your other functions should need to be altered.

Submission

If you are a University of Colorado Boulder student, we use Gradescope for assignment submission. In summary,

• Create a private GitHub repository by clicking on a GitHub Classroom link from the corresponding Canvas assignment entry.
• Clone your private GitHub repository to your development environment (using the <> Code button on GitHub to get the repository URL).
• Work on this lab from your cloned repository. Use Git to save versions on GitHub (e.g., git add, git commit, git push on the command line or via VSCode).
• Submit to the corresponding Gradescope assignment entry for grading by choosing GitHub as the submission method.

You need to have a GitHub identity and must have your full name in your GitHub profile in case we need to associate you with your submissions.