trait Expr // e ::=
case class N(n: Double) extends Expr // n
type Env = Map[String, Expr]
val empty: Env = Map.emptydefined trait Expr defined class N defined type Env empty: Env = Map()
16 Lab: Basic Values, Variables, and Judgments
Learning Goals
The primary learning goals of this assignment are to build intuition for the following:
- the distinction between concrete and abstract syntax;
- the relationship between judgment forms/inference rules/judgments and implementation code;
- using a reference implementation as a definition of semantics;
- variable binding and variable environments.
- Functional Programming Skills
- Recursion over abstract syntax. Representation invariants.
- Programming Language Ideas
- Inductive definitions (grammars/productions/sentences and judgment forms/inference rules/judgments). Semantics (via detective work).
Instructions
A version of project files for this lab resides in the public pppl-lab2 repository. Please follow separate instructions to get a private clone of this repository for your work.
You will be replacing ??? or case _ => ??? in the Lab2.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 Lab2Spec.scala file. In the Lab2Spec.scala, there is empty test class Lab2StudentSpec that you can use to separate your tests from the given tests in the Lab2Spec class. You are also likely to edit Lab2.worksheet.sc for any scratch work. You can also use Lab2.worksheet.js to write and experiment in a JavaScript file that you can then parse into a JavaScripty AST (see Lab2.worksheet.sc).
If you like, you may use this notebook for experimentation. However, please make sure your code is in Lab2.scala; this notebook will not graded.
Recall that you need to switch kernels between running JavaScript and Scala cells.
16.1 Interpreter: JavaScripty Calculator
In this lab, we extend JavaScripty with additional value types and variable binding. That is, the culmination of the lab is to implement an interpreter for the subset of JavaScript with numbers, booleans, strings, the undefined value, and variable binding.
def eval(env: Env, e: Expr): Expr = ???defined function eval
We leave the Expr inductive data type mostly undefined for the moment to focus on the type of eval.
First, observe that the return type of eval is an Expr (versus Double in the previous lab), as we now have more value types. However, eval should return an Expr that is a JavaScripty value (i.e., is an \(e\) : Expr such that isValue( \(e\) ) returns true). The need for the object-language versus meta-language distinction is even more salient here than in the previous lab. For example, it is critical to keep straight that N(1.0) is the Scala value representing the JavaScripty value 1.0.
Second, observe that the eval function takes a JavaScripty value environment env: Env to give meaning to free JavaScripty variables in e.
These ideas take unpacking, so let us start from the arithmetic sub-language of JavaScripty:
case class Unary(uop: Uop, e1: Expr) extends Expr // e ::= uop e1
case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // | e1 bop e2
trait Uop // uop ::=
case object Neg extends Uop // -
trait Bop // bop ::=
case object Plus extends Bop // +
case object Minus extends Bop // | -
case object Times extends Bop // | *
case object Div extends Bop // | /defined class Unary defined class Binary defined trait Uop defined object Neg defined trait Bop defined object Plus defined object Minus defined object Times defined object Div
Thus far, we have considered only one type of value in our JavaScripty object language: numbers \(n\) (which we have considered double-precision floating-point numbers). Specifically, we have stated the following:
\[ \begin{array}{rrrl} \text{expressions} & e& \mathrel{::=}& v \\ \text{values} & v& \mathrel{::=}& n \end{array} \]
Recall from our preliminary discussion about evaluation (Section 3.3) that the computational model is a rewriting or reduction of expressions until reaching values. A value is simply an expression that cannot be reduced any further. Thus, we can also consider a unary judgment form \(e\;\mathsf{value}\) that judges when an expression is a value. \[ \infer[NumVal]{ }{ n\;\mathsf{value} } \]
This judgment form corresponds to the isValue function:
def isValue(e: Expr): Boolean = e match {
case N(_) => true
case _ => false
}defined function isValue
From our discussion on grammars and inference rules (Section 15.1), we can see this unary judgment form \(e\;\mathsf{value}\) as defining a syntactic category values \(v\). Thus, we freely write grammar productions for \(v\) to define the judgment form \(e\;\mathsf{value}\).
Exercise 16.1 For this part of the lab, implement eval for the calculator language above (which is the same language as in the previous lab) but now with type (Env, Expr) => Expr.
def eval(env: Env, e: Expr): Expr = ???defined function eval
You will not use the env parameter yet. You will want to check that your implementation returns JavaScripty values. For example,
val e_oneplustwo = Binary(Plus, N(1), N(2))
assert( isValue( eval(empty, e_oneplustwo) ) )scala.NotImplementedError: an implementation is missing scala.Predef$.$qmark$qmark$qmark(Predef.scala:345) ammonite.$sess.cmd4$Helper.eval(cmd4.sc:1) ammonite.$sess.cmd5$Helper.<init>(cmd5.sc:2) ammonite.$sess.cmd5$.<clinit>(cmd5.sc:7)
16.2 Coercions: Basic Values
16.2.1 Booleans, Strings, and Undefined
Like most other languages, JavaScript has other basic value types. Let us extend JavaScripty with Booleans, strings, and the \(\mathbf{undefined}\) value:
\[ \begin{array}{rrrl} \text{values} & v& \mathrel{::=}& b \mid\mathit{str} \mid\mathbf{undefined} \\ \text{booleans} & b \\ \text{strings} & \mathit{str} \end{array} \]
Boolean values \(b\) are the literals \(\mathbf{true}\) and \(\mathbf{false}\). String values \(\mathit{str}\) are string literals like "hi" that we do not explicitly define here.
The \(\mathbf{undefined}\) literal is a distinguished value that is different than all other values. It is like the unit literal () in Scala.
case class B(b: Boolean) extends Expr // e ::= b
case class S(str: String) extends Expr // | str
case object Undefined extends Expr // | undefineddefined class B defined class S defined object Undefined
Examples
truefalse"Hello""Hola"undefinedWe update our isValue function appropriately:
def isValue(e: Expr): Boolean = e match {
case N(_) | B(_) | S(_) | Undefined => true
case _ => false
}defined function isValue
A good exercise here is to reflect on what this code translates to in terms of additional inference rules for the \(e\;\mathsf{value}\) judgment form.
16.2.2 Expressions
Each value type comes with some operations. Our abstract syntax tree has two constructors for unary and binary expressions that are parametrized by unary \(\mathit{uop}\) and binary \(\mathit{bop}\) operators, respectively:
\[ \begin{array}{rrrl} \text{expressions} & e& \mathrel{::=}& \mid\mathop{\mathit{uop}} e_1 \mid e_1 \mathbin{\mathit{bop}} e_2 \end{array} \]
16.2.2.1 Numbers
For example, numbers has
\[ \begin{array}{rrrl} \text{unary operators} & \mathit{uop}& \mathrel{::=}& \texttt{-} \\ \text{binary operators} & \mathit{bop}& \mathrel{::=}& \texttt{+}\mid\texttt{-}\mid\texttt{*}\mid\texttt{/} \end{array} \]
that we considered previously.
16.2.2.2 Booleans
For booleans, we add unary negation \(\texttt{!}\) and binary conjunction \(\texttt{\&\&}\) and disjunction \(\texttt{||}\). \[ \begin{array}{rrrl} \text{unary operators} & \mathit{uop}& \mathrel{::=}& \texttt{!} \\ \text{binary operators} & \mathit{bop}& \mathrel{::=}& \texttt{\&\&} \mid\texttt{||} \end{array} \]
case object Not extends Uop // uop ::= !
case object And extends Bop // bop ::= &&
case object Or extends Bop // | ||defined object Not defined object And defined object Or
Examples
!truetrue && falsetrue || falseWe also expect to be able to elimate booleans with a conditional if-then-else expression: \[ \begin{array}{rrrl} \text{expressions} & e& \mathrel{::=}& e_1\;\texttt{?}\;e_2\;\texttt{:}\;e_3 \end{array} \]
case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3defined class If
We also expect to be able to compare values for equality and disquality and numbers for inequality: \[ \begin{array}{rrrl} \text{binary operators} & \mathit{bop}& \mathrel{::=}& \texttt{===} \mid\texttt{!==} \mid\texttt{<} \mid\texttt{<=} \mid\texttt{>} \mid\texttt{>=} \end{array} \]
case object Eq extends Bop // bop ::= ===
case object Ne extends Bop // | !==
case object Lt extends Bop // | <
case object Le extends Bop // | <=
case object Gt extends Bop // | >
case object Ge extends Bop // | >=defined object Eq defined object Ne defined object Lt defined object Le defined object Gt defined object Ge
16.2.2.3 Strings
The string operations we support in JavaScripty are string concatenation and string comparison. In JavaScript, string concatenation is written with the binary operator + and string comparison using <, <=, >, and >=, so we do not need to extend the syntax.
Examples
"Hello" + ", " + "World" + "!"16.2.2.4 Undefined
As \(\mathbf{undefined}\) corresponds to unit () in Scala and is uninteresting in itself, we add a side-effecting expression that prints to console.
\[ \begin{array}{rrrl} \text{expressions} & e& \mathrel{::=}& \texttt{console}\texttt{.}\texttt{log}\texttt{(}e_1\texttt{)} \end{array} \]
case class Print(e1: Expr) extends Expr // e ::= console.log(e1)defined class Print
Examples
console.log("Hello, World!")If we now have side-effecting expressions, then we would expect to have a way to sequence executing expressions for their effects.
\[ \begin{array}{rrrl} \text{binary operators} & \mathit{bop}& \mathrel{::=}& \texttt{,} \end{array} \]
case object Seq extends Bop // bop ::= ,defined object Seq
Examples
undefined, 316.2.3 Semantics Detective: JavaScript is Bananas
In the above, we have carefully specified the abstract syntax of the object language of interest and informally discussed its semantics. But if we are to implement an interpreter in the eval function, we also need to define its semantics! And we give a precise definition as follows:
Important
In this lab, the semantics of a JavaScripty expression \(e\) is defined by the evaluation of it as a JavaScript program.
Given the careful specification of the abstract syntax, a natural question to ask is whether all abstract syntax trees of type Expr in the above are valid expressions and have a semantics in JavaScript (and hence JavaScripty). Is 3 + true a valid expression?
JavaScript
3 + trueWe try it out and see that yes it is. One aspect that makes the JavaScript specification interesting is the presence of implicit coercions (e.g., non-numeric values, such as booleans or strings, may be implicitly converted to numeric values depending on the context in which they are used).
You might guess that defining coercions between value types can lead to some interesting semantics. It is because of these coercions that we have the meme that “JavaScript is bananas.”
JavaScript
"b" + "a" + "n" + - "a" + "a" + "s"Armed with knowledge that in JavaScript, numbers are floating-point numbers, the + operator in JavaScript is overloaded for strings and numbers, and coercions happen between value types, see if you can explain what is happening in the “bananas” expression above.
16.2.3.1 Coercions
Our eval function interpreter will need to make use of three helper functions for converting values to numbers, booleans, and strings:
def toNumber(v: Expr): Double = ???
def toBoolean(v: Expr): Boolean = ???
def toStr(v: Expr): String = ???defined function toNumber defined function toBoolean defined function toStr
Exercise 16.2 Write at least 1 JavaScript expression that shows a coercion from a non-numeric value to a number and see what the result should be:
JavaScript
// YOUR CODE HERE
undefinedThen, translate this JavaScript expression (written in concrete syntax) into an Expr value (i.e., a JavaScripty abstract syntax tree).
Scala
???scala.NotImplementedError: an implementation is missing scala.Predef$.$qmark$qmark$qmark(Predef.scala:345) ammonite.$sess.cmd14$Helper.<init>(cmd14.sc:1) ammonite.$sess.cmd14$.<clinit>(cmd14.sc:7)
Finally, use this Expr as a unit test for toNumber in the Lab2StudentSpec class in the Lab2Spec.scala file.
Lab2Spec.scala
val e_toNumber_test1 = ???
"toNumber" should s"${e_toNumber_test1}" in {
assertResult(???) { toNumber(e_toNumber_test1) }
}Exercise 16.3 Do the same to create a toBoolean test. Write at least 1 JavaScript expression that shows a coercion from a non-boolean value to a boolean, see what the result should be, translate it to an Expr value, and add it as test in Lab2StudentSpec.
JavaScript
// YOUR CODE HERE
undefinedScala
???scala.NotImplementedError: an implementation is missing scala.Predef$.$qmark$qmark$qmark(Predef.scala:345) ammonite.$sess.cmd15$Helper.<init>(cmd15.sc:1) ammonite.$sess.cmd15$.<clinit>(cmd15.sc:7)
Exercise 16.4 Do the same to create a toStr test. Write at least 1 JavaScript expression that shows a coercion from a non-string value to a string, see what the result should be, translate it to an Expr value, and add it as test in Lab2StudentSpec.
JavaScript
// YOUR CODE HERE
undefinedScala
???scala.NotImplementedError: an implementation is missing scala.Predef$.$qmark$qmark$qmark(Predef.scala:345) ammonite.$sess.cmd16$Helper.<init>(cmd16.sc:1) ammonite.$sess.cmd16$.<clinit>(cmd16.sc:7)
Exercise 16.5 Implement toNumber, toBoolean, and toStr in Lab2.scala (using test-driven development with the test cases you have written above).
Exercise 16.6 For this part of the lab, extend your eval from Exercise 16.1 for booleans, strings, the undefined value, and printing.
def eval(env: Env, e: Expr): Expr = ???defined function eval
You still will not use the env parameter yet. You again will want to check that your implementation returns JavaScripty values using the latest isValue. For example,
val e_nottrue = Unary(Not, B(true))
assert( isValue( eval(empty, e_nottrue) ) )scala.NotImplementedError: an implementation is missing scala.Predef$.$qmark$qmark$qmark(Predef.scala:345) ammonite.$sess.cmd17$Helper.eval(cmd17.sc:1) ammonite.$sess.cmd18$Helper.<init>(cmd18.sc:2) ammonite.$sess.cmd18$.<clinit>(cmd18.sc:7)
16.3 Interpreter: JavaScripty Variables
The final piece of this lab is to extend our interpreter with variable uses and binding (cf. Chapter 14).
\[ \begin{array}{rrrl} \text{expressions} & e& \mathrel{::=}& x\mid\mathbf{const}\;x\;\texttt{=}\;e_1\texttt{;}\;e_2 \end{array} \]
case class Var(x: String) extends Expr // e ::= x
case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // | const x = e1; e2defined class Var defined class ConstDecl
Note that the above is the abstract syntax we consider for ConstDecl, which is more flexible the concrete syntax for const allowed by JavaScript (cf. Section 14.5)
In this lab, we define a value environment as a map from variable names to JavaScripty values, which we represent in Scala as a value of type Map[String, Expr]. Note that representing variable names as Scala Strings here, and it is a representation invariant that the Exprs must correspond to JavaScripty values.
type Env = Map[String, Expr]
val empty: Env = Map.empty
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 type Env empty: Env = Map() defined function lookup defined function extend
We provide the above value and function bindings to interface with the Scala standard library for Map[String, Expr] and maintain this representation invariant. You may use the Scala standard library directly if you wish, but we recommend that you just use these interfaces, as they are all that you need and give you the safety of enforcing the representation invariant. The empty value represents an empty value environment, the lookup function gets the value bound to the variable named by a given string, and the extend function extends a given environment with a new variable binding.
Exercise 16.7 For this part of the lab, extend your eval from Exercise 16.1 for variable uses (i.e., Var) and variable binding (i.e., ConstDecl). We suggest you start by adding tests with variables uses and const bindings to be able do test-driven development (see below).
def eval(env: Env, e: Expr): Expr = ???defined function eval
Testing
In this lab, we have carefully defined the syntax of the JavaScripty variant of interest, and we have defined its semantics to be defined to be the same as JavaScript. Thus, you can write any JavaScript program within the syntax defined above to create test cases for your eval function. Any of the above JavaScript examples could be used as test cases. In some cases, you may want to write abstract syntax trees directly in Scala (i.e., values of type Expr). In other cases, you can use the provided JavaScripty parser to translate concrete syntax (i.e., values of type String) into abstract syntax (i.e., values of type Expr).
Exercise 16.8 (Optional) We give some exercises below to explore this subset of JavaScripty that you can then use as test cases that you add to your Lab2StudentSpec.
16.3.0.1 Basic Arithmetic Operations
This program defines two constants, x and y, and calculates their sum. It then logs the result sum to the console.
const x = 10;
const y = 5;
const sum =
// YOUR CODE HERE (replace undefined)
undefined
;
console.log(sum);console.assert(sum === 15)16.3.0.2 Conditional Expressions
const a = 10;
const b = 20;
const max =
// YOUR CODE HERE (replace undefined)
undefined
;console.assert(max === 20)16.3.0.3 Unary and Binary Operations
This program checks if a number is positive using a unary negation - and a binary relational operator.
const num = -5;
const isPositive =
// YOUR CODE HERE (replace undefined)
undefined
;console.assert(isPositive === false)16.3.0.4 Undefined
This program demonstrates the correspondence between undefined in JavaScript and ().
const r = console.log("Hello");console.assert(r === undefined)Submission
If you are a University of Colorado Boulder student, we use Gradescope for assignment submission. In summary,
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.