CSCI 3155: Lab Assignment 3 Solved

The purpose of this lab is to grapple with how dynamic scoping arises and how to formally specify semantics. Concretely, we will extend JAVASCRIPTY with recursive functions and implement two interpreters. The first will be a big-step interpreter that is an extension of Lab 2 but implements dynamic scoping “by accident.” The second will be a small-step interpreter that exposes evaluation order and implements static scoping by substitution.

From your team of 8-10 persons in your lab section, find a new partner for this lab assignment (different from your Lab 1 partner). You will work on this assignment closely with your partner. However, note that each student needs to submit and are individually responsible for completing the assignment.

You are welcome to talk about these questions in larger groups. However, we ask that you write up your answers in pairs. Also, be sure to acknowledge those with which you discussed, including your partner and those outside of your pair.

Recall the evaluation guideline from the course syllabus.

Both your ideas and also the clarity with which they are expressed matter—both in your English prose and your code!

We will consider the following criteria in our grading:

• How well does your submission answer the questions? For example, a common mistake is to give an example when a question asks for an explanation. An example may be useful in your explanation, but it should not take the place of the explanation.

• How clear is your submission? If we cannot understand what you are trying to say, then we cannot give you points for it. Try reading your answer aloud to yourself or a friend; this technique is often a great way to identify holes in your reasoning. For code, not every program that "works" deserves full credit. We must be able to read and understand your intent. Make sure you state any preconditions or invariants for your functions (either in comments, as assertions, or as require clauses as appropriate).

Try to make your code as concise and clear as possible. Challenge yourself to find the most crisp, concise way of expressing the intended computation. This may mean using ways of expression computation currently unfamilar to you.

Finally, make sure that your file compiles and runs on COG. A program that does not compile will not be graded.

1

Submission Instructions. Upload to the moodle exactly four files named as follows:

• Lab3-YourIdentiKey.pdf with your answers to the written questions (scanned, clearly legible handwritten write-ups are acceptable).

• Lab3-YourIdentiKey.scala with your answers to the coding exercises.

• Lab3Spec-YourIdentiKey.scala with any updates to your unit tests.

• Lab3-YourIdentiKey.jsy with a challenging test case for your JAVASCRIPTY interpreter.

Replace YourIdentiKey with your IdentiKey (e.g., I would submit Lab3-bec.pdf and so forth). Don’t use your student identification number. To help with managing the submissions, we ask that you rename your uploaded files in this manner.

Submit your Lab3.scala file to COG for auto-testing. We ask that you submit both to COG and to moodle in case of any issues.

Sign-up for an interview slot for an evaluator. To fairly accommodate everyone, the interview times are strict and will not be rescheduled. Missing an interview slot means missing the interview evaluation component of your lab grade. Please take advantage of your interview time to maximize the feedback that you are able receive. Arrive at your interview ready to show your implementation and your written responses. Implementations that do not compile and run will not be evaluated.

Getting Started. Clone the code from the Github repository with the following command: git clone -b lab3 https://github.com/bechang/pppl-labs.git lab3

A suggested way to get familiar with Scala is to do some small lessons with Scala Koans (http://www.scalakoans.org/). A useful one for Lab 3 is AboutOptions.

1. Feedback. Complete the survey on the linked from the moodle after completing this assignment. Any non-empty answer will receive full credit.

2. JavaScripty Interpreter: Tag Testing, Recursive Functions, and Dynamic Scoping.

We now have the formal tools to specify exactly how a JAVASCRIPTY program should behave. Unless otherwise specified, we will continue to try to match JavaScript semantics as implemented by Node.js/Google’s V8 JavaScript Engine. Thus, it is still useful to write little test JavaScript programs and run it through Node.js to see how the test should behave. Finding bugs in the JAVASCRIPTY specification with respect to JavaScript is certainly deserving of extra credit.

In this lab, we extend JAVASCRIPTY with recursive functions. This language is very similar to the LETREC language in Section 3.4 of Friedman and Wand.

For this question, we try to implement functions as an extension of Lab 2 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.

expressions

values unary operators binary operators
e ::= x |n |b |str |undefined|uope1 |e1bope2

| e1 ? e2 : e3 |constx =e1; e2 |console.log(e1)

| functionp(x) e1 |e1(e2) v ::= n |b |undefined|str |functionp(x) e1 |typeerror

uop ::= -|!

bop ::= ,|+|-|*|/|===|!==|<|<=||=|&&|||
variables
x
numbers (doubles)
n
booleans strings
b ::= true|false

str
function names
p ::= x |ε
value environments
E ::= ·|E[x 7→ v]
Figure 1: Abstract Syntax of JAVASCRIPTY

statements expressions
s ::= const( x =(e |(ee(|(1{(;se(12}||(;e|1s)1 s2

e ::= ···|const((x =
((((

|(function((( p(x) e1 |function p(x) { s1 return e1 }

Figure 2: Concrete Syntax of JAVASCRIPTY

The syntax of JAVASCRIPTY for this lab is given in Figure 1. Note that the grammar specifies the abstract syntax using notation borrowed from the concrete syntax. The new constructs are highlighted. We have function expressions function p(x) e1 and function calls e1(e2).

In a function expression, the function name p can either be an identifier or empty. When the identifier for the function name is present, it can be used for recursion. For simplicity, all functions are one argument functions. Since functions are first-class values, we can get multi-argument functions via currying.

We have also added a “marker” typeerror to the expression language. This marker is not part of the source language but is used in our definition of the evaluation judgment form. We discuss this in more detail further below.

As before, the concrete syntax accepted by the parser is slightly less flexible than the abstract syntax in order to match the syntactic structure of JavaScript. For function expressions, the body is surrounded by curly braces (i.e., { }) and consists of a statement s1 for const bindings followed by a return with an expression e1.

An abstract syntax tree representation is provided for you in ast.scala. We also provide a

case class Function(p: Option[String], x: String, e1: Expr) extends Expr

Function(p, x, e1) functionp(x) e1 case class Call(e1: Expr, e2: Expr) extends Expr Call(e1, e2) e1(e2)

Figure 3: Representing in Scala the abstract syntax of JAVASCRIPTY. After each caseclass or caseobject, we show the correspondence between the representation and the concrete syntax. parser and main driver for testing. The correspondence between the concrete syntax and the abstract syntax representation is shown in Figure 3.

A big-step operational semantics of JAVASCRIPTY is given in Figure 4. This figure 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 lab is such an opportunity to practice.

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!

In Figure 4, we define the judgment form E ` e ⇓ 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 think of the other parts of the judgment as just punctuation. This judgment form corresponds directly to the eval function that we are asked to implement (not a coincidence). It similarly has three parts:

def eval(env: Env, e: Expr): Expr
It takes as input a value environment env (E) and an expression e (e) returns a value v.

It is very informative to compare your Scala code from Lab 2 with the inference rules that define E ` e ⇓ v. One thing you should observe is that all of the rules are implemented, except for EVALCALL, EVALCALLREC, and part of EVALEQUALITY. In essence, implementing those rules is your task for this question.

In Lab 2, 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. In the formal semantics, we model this with evaluating to the “marker” typeerror.

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.

In our Scala implementation, we will not clutter our Expr type with a typeerror marker. Instead, we will use a Scala exception DynamicTypeError: case class DynamicTypeError(e: Expr) extends Exception

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 to eval where the type error was detected. One advantage of using a Scala exception for typeerror is that the marker does not need to be propagated explicitly as in the inference rules in Figure 6. In particular, your interpreter E ` e ⇓ v

EVALVAR EVALVAL EEVAL`e1N⇓ vEG1 n0 =−toNumber(v1) EEVAL`e1N⇓ vOT1 b0 =¬toBoolean(v1)



E ` x ⇓E(x) E ` v ⇓ v E `−e1 ⇓n0 E ` !e1 ⇓b0

EVALSEQ EVALPLUSNUMBER

E `e1 ⇓ v1 E `e2 ⇓ v2 E `e1 ⇓ v1 E `e2 ⇓ v2

E `e1 , e2 ⇓ v2
n0 = toNumber(v1)+toNumber(v2) v1 6=str1 v2 6=str2

E `e1 +e2 ⇓n0
EVALPLUSSTRING1

E `e1 ⇓str1 E `e2 ⇓ v2 str0 =str1 +toString(v2)

E `e1 +e2 ⇓str0 EVALARITH
EVALPLUSSTRING2

E `e1 ⇓ v1 E `e2 ⇓str2 str0 = toString(v1)+str2

E `e1 +e2 ⇓str0
E `e1 ⇓ v1 E `e2 ⇓ v2 n0 = toNumber(v1) bop toNumber(v2) bop∈ {−,∗,/}

E `e1 bope2 ⇓n0

EVALINEQUALITYNUMBER1

b0 = toNumber(E `ev11⇓) bopv1 toNumber(E `e2 ⇓vv22)

E `e1 bope2 ⇓b0
v1 6=str1

bop∈ {<,<=,,=}
EVALINEQUALITYNUMBER2

b0 = toNumber(E `ev11⇓) bopv1 toNumber(E `e2 ⇓vv22)

E `e1 bope2 ⇓b0
v2 6=str2

bop∈ {<,<=,,=}
EVALINEQUALITYSTRING

E `e1 ⇓str1 E `e2 ⇓str2 b0 =str1 bopstr2 bop∈ {<,<=,,=}

E `e1 bope2 ⇓b0 EVALEQUALITY

E `e1 ⇓ v1 E `e2 ⇓ v2

v1 6=functionp1(x1) e1 v2 6=functionp1(x2) e2 b0 = (v1 bopv2) bop∈ {===,! ==}

E `e1 bope2 ⇓b0

EVALANDTRUE EVALANDFALSE EVALORTRUE

E `e1 ⇓ v1 true= toBoolean(v1) E `e2 ⇓ v2 E `e1 ⇓ v1 false= toBoolean(v1) E `e1 ⇓ v1 true= toBoolean(v1)

E `e1 && e2 ⇓ v2 E `e1 && e2 ⇓ v1 E `e1 ||e2 ⇓ v1 EVALORFALSE EVALPRINT

E `e1 ⇓ v1 false= toBoolean(v1) E `e2 ⇓ v2 E `e1 ⇓ v1 v1 printed

E `e1 ||e2 ⇓ v2 E `console.log(e1) ⇓undefined

EVALIFTRUE EVALIFFALSE

E `e1 ⇓ v1 true= toBoolean(v1) E `e2 ⇓ v2 E `e1 ⇓ v1 false= toBoolean(v1) E `e3 ⇓ v3

E `e1 ? e2 : e3 ⇓ v2 E `e1 ? e2 : e3 ⇓ v3

EVALCONST EVALCALL

E `e1 ⇓ v1 E[x 7→ v1] `e2 ⇓ v2 E `e1 ⇓ v1 v1 =function (x) e0 E `e2 ⇓ v2 E[x →7 v2] `e0 ⇓ v0

E `constx =e1; e2 ⇓ v2 E `e1(e2) ⇓ v0

EVALCALLREC

E `e1 ⇓ v1 v1 =functionx1(x2) e0 E `e2 ⇓ v2 E[x1 →7 v1][x2 →7 v2] `e0 ⇓ v0

E `e1(e2) ⇓ v0

Figure 4: Big-step operational semantics of JAVASCRIPTY (with dynamic scoping).

def toNumber(n) def= n

toNumber(true) = 1

def toNumber(false) def= 0

toNumber(undefined) def= NaN toNumber(str) def= parse str

toNumber(functionp(x) e1) = NaN

def toBoolean(n) = false if n = 0 or n =NaN

def toBoolean(n) = true otherwise

def toBoolean(b) def= b

toBoolean(undefined) def= false toBoolean(str) = false if str= ""

def toBoolean(str) = true otherwise

def toBoolean(functionp(x) e1) = true

def toString(n) = string of n

def toString(true) = "true"

def toString(false) def= "false"

toString(undefined) def= "undefined" toString(str) def= str

toString(functionp(x) e1) = "function"

Figure 5: Conversion functions. We do not specify explicitly the parsing or string conversion of numbers. The conversion of a function to a string deviates slightly from JavaScript where the source code of the function is returned.

E ` e ⇓ v

EVALTYPEERROREQUALITY1

E `e1⇓v1 v1=functionp1(x1) e1 bop∈ {===,! ==}

E `e1 bope2⇓typeerror

EVALTYPEERROREQUALITY2 EVALTYPEERRORCALL
E `e2⇓v2 v2=functionp1(x1) e1 bop∈ {===,! ==} v16=functionp(x) e1

E `e1 bope2⇓typeerror E `v1(e2) ⇓typeerror

EVALPROPAGATEUNARY E `e1⇓typeerror

E `uope1⇓typeerror
EVALPROPAGATEBINARY1 E `e1⇓typeerror

E `e1 bope2⇓typeerror
EVALPROPAGATEBINARY2 E `e2⇓typeerror

E `e1 bope2⇓typeerror
EVALPROPAGATEPRINT E `e1⇓typeerror

E `console.log(e1) ⇓typeerror
EVALPROPAGATEIF

E `e1⇓typeerror

E `e1 ? e2 : e3⇓typeerror
EVALPROPAGATECONST E `e1⇓typeerror

E `constx =e1; e2⇓typeerror
EVALPROPAGATECALL1 EVALPROPAGATECALL2
E `e1⇓typeerror E `e2⇓typeerror

E `e1(e2) ⇓typeerror E `e1(e2) ⇓typeerror

Figure 6: Big-step operational semantics of JAVASCRIPTY: Dynamic type error rules.

will implement the EVALTYPEERROR rules explicitly, but the EVALPROPAGATE rules are implemented implicitly with Scala’s exception propagation semantics.

Note in rule EVALEQUALITY, we disallow equality and disequality checks (i.e., === and ! ==) on function values. If either argument to a equality or disequality check is a function value, then we consider this a dynamic type error. This choice is a departure from JavaScript semantics.

(a) First, write some JAVASCRIPTY programs and execute them as JavaScript programs. This step will inform how you will implement your interpreter and will serve as tests for your interpreter.

Write-up: Give one test case that behaves differently under dynamic scoping versus static scoping (and does not crash). Explain the test case and how they behave differently in your write-up.

(b) Then, implement def eval(env: Env, e: Expr): Expr
that evaluates a JAVASCRIPTY expression e in a value environment env to a value according to the evaluation judgment E ` e ⇓ v.

You will again want the following 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
We suggest the following step-by-step process:

1. Bring your Lab 2 implementation into Lab 3 and make sure your previous test cases work as expected.

2. Extend your implementation with non-recursive functions. On function calls, you need to extend the environment for the formal parameter but not for the function itself. Do not worry yet about dynamic type errors.

3. Add support for checking for dynamic type errors.

4. Check that your interpreter, unfortunately, implements dynamic scoping instead of static scoping.

5. Modify your implementation to support recursive functions.

3. JavaScripty Interpreter: Substitution and Evaluation Order.

In this question, we will do two things. First, we will remove environments and instead use a language semantics based on substitution. This change will “fix” the scoping issue, and we will end up with static, lexical scoping.

As an aside, substitution is not the only way to “fix” the scoping issue. Another way is to represent function values as closures, which is a pair of the function with the environment when it is defined. 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.

The second thing that we do is move to implementing a small-step interpreter. A small-step interpreter makes explicit the evaluation order of expressions. These two changes are orthogonal, that is, one could implement a big-step interpreter using substitution or a smallstep interpreter using environments.

(a) Implement def substitute(e: Expr, v: Expr, x: String): Expr
that substitutes value v for all free occurrences of variable x in expression e. We advise defining substitute by recursion on e. The cases to be careful about are ConstDecl and Function because these are the variable binding constructs. In particular, 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.

(b) Implement def step(e: Expr): Expr
that performs one-step of evaluation by rewriting the input expression e into a “onestep reduced” expression. This one-step reduction should be implemented according to the judgment form e −→ e0 defined in Figures 7, 8, and 9. We write e[v/x] for substituting value v for all free occurrences of the variable x in expression e (i.e., a call to substitute).

(c) Write-up: Explain whether the evaluation order is deterministic as specified by the judgment form e −→ e0.

It is informative to compare the small-step semantics used in this question and the big-step semantics from the previous one. In particular, for all programs where dynamic scoping is not an issue, your interpreters in this question and the previous should behave the same. We have provided the functions evaluate and iterateStep that evaluate “top-level” expressions to a value using your interpreter implementations.

4. Evaluation Order.

Consider the small-step operational semantics for JAVASCRIPTY shown in Figures 7, 8, and 9. What is the evaluation order for e1 + e2? Explain. How do we change the rules obtain the opposite evaluation order?

5. Short-Circuit Evaluation. In this question, we will discuss some issues with short-circuit evaluation.

(a) Concept. Give an example that illustrates the usefulness of short-circuit evaluation. Explain your example.

(b) JAVASCRIPTY. Consider the small-step operational semantics for JAVASCRIPTY shown in Figures 7, 8, and 9. Does e1 && e2 short circuit? Explain.


e −→ e0

DONEG DONOT

n0 =−toNumber(v) b0 =¬toBoolean(v) DOSEQ



−v −→n0 !v −→b0 v1 , e2 −→e2

DOPLUSNUMBER DOPLUSSTRING1

n0 = toNumber(v1)+toNumber(v2) v1 6=str1 v2 6=str2 str0 =str1+toString(v2)

v1 + v2 −→n0 str1 + v2 −→str0

DOPLUSSTRING2 DOARITH

str0 = toString(v1)+str2 n0 = toNumber(v1) bop toNumber(v2)

v1 +str2 −→str0 v1bopv2 −→n0

DOINEQUALITYNUMBER1
bop∈ {−,∗,/}
b0 = toNumber(v1) bop toNumber(v2) bop∈ {<,<=,,=}

v1bopv2 −→b0

DOINEQUALITYNUMBER2
v1 6=str1
b0 = toNumber(v1) bop toNumber(v2) bop∈ {<,<=,,=}

v1bopv2 −→b0

DOINEQUALITYSTRING b0 =str1bopstr2 bop∈ {<,<=,,=}

str1bopstr2 −→b0

DOEQUALITY
v2 6=str2
v1 6=functionp1(x1) e1 v2 6=functionp1(x2) e2 b0 = (v1bopv2)

v1bopv2 −→b0
bop∈ {===,! ==}
DOANDTRUE DOANDFALSE DOORTRUE

true= toBoolean(v1) false= toBoolean(v1) true= toBoolean(v1)

v1 && e2 −→e2 v1 && e2 −→ v1 v1 ||e2 −→ v1
DOORFALSE false= toBoolean(v1)

v1 ||e2 −→e2
DOPRINT DOIFTRUE DOIFFALSE

v1 printed true= toBoolean(v1) false= toBoolean(v1)



console.log(v1) −→undefined v1 ? e2 : e3 −→e2 v1 ? e2 : e3 −→e3

DOCALL DOCALLREC DOCONST v1 =function (x) e1 v1 =functionx1(x2) e1



constx = v1; e2 −→e2[v1/x] v1(v2) −→e1[v2/x] v1(v2) −→e1[v1/x1][v2/x2]
Figure 7: Small-step operational semantics of JAVASCRIPTY: DO rules.

e −→ e0

SEARCHUNARY e1 −→e10 uope1 −→uope10
SEARCHBINARY1 e1 −→e10 e1bope2 −→e10 bope2
SEARCHBINARYARITH2 e2 −→e20 bop∈ {+,−,∗,/,<,<=,,=}

v1bope2 −→ v1bope20
SEARCHEQUALITY2

SEARCHPRINT
e2 −→e20 v1 6=functionp(x) e1 bop∈ {===,! ==} e1 −→e10

v1bope2 −→ v1bope20 console.log(e1) −→console.log(e10 )

SEARCHIF SEARCHCONST SEARCHCALL1 e1 −→e10 e1 −→e10 e1 −→e10

e1 ? e2 : e3 −→e10 ? e2 : e3 constx =e1; e2 −→constx =e10 ; e2 e1(e2) −→e10 (e2)

SEARCHCALL2 e2 −→e20

¡functionp(x) e1¢(e2) −→¡functionp(x) e1¢(e20 )

Figure 8: Small-step operational semantics of JAVASCRIPTY: SEARCH rules.

e −→ e0

TYPEERROREQUALITY1 TYPEERROREQUALITY1

bop∈ {===,! ==} bop∈ {===,! ==}

(functionp(x) e1) bope2 −→typeerror v1bop (functionp(x) e2) −→typeerror

TYPEERRORCALL v1 6=functionp(x) e1

v1(e2) −→typeerror

PROPAGATEUNARY PROPAGATEBINARY PROPAGATEBINARY



uoptypeerror −→typeerror typeerrorbope2 −→typeerror v1boptypeerror −→typeerror

PROPAGATEPRINT PROPAGATEIF



console.log(typeerror) −→typeerror typeerror ? e2 : e3 −→typeerror

PROPAGATECONST PROPAGATECALL1 PROPAGATECALL2



constx =typeerror; e2 −→typeerror typeerror(e2) −→typeerror v1(typeerror) −→typeerror Figure 9: Small-step operational semantics of JAVASCRIPTY: Dynamic type error rules.