Lab Assignment #3 Solution

$35.00

Description

The purpose of this lab is to grapple with how dynamic scoping arises and how to formally specify semantics. Concretely, we will extend JAVA SC R I P T Y with recursive functions and imple- ment 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.

Like last time, you will work on this assignment in pairs. However, note that each student needs to submit a write-up 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 pre- conditions 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 ex- pression computation currently unfamilar to you.

Finally, make sure that your file compiles and runs (using Scala 2.10.3). A program that does not compile will not be graded.

1

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

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

Lab3YourIdentiKey.scala with your answers to the coding exercises.

Lab3SpecYourIdentiKey.scala with any updates to your unit tests.

Lab3YourIdentiKey.jsy with a challenging test case for your JAVA SC R I P T Y interpreter. Replace YourIdentiKey with your IdentiKey (e.g., I would submit Lab3-bec.pdf and so forth).

Dont use your student identification number. To help with managing the submissions, we ask that you rename your uploaded files in this manner.

Sign-up for an interview slot for an evaluator. To fairly accomodate 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. Download the code pack lab3.zip from the assignment page.

A suggested way to get familiar with Scala is to do some small lessons with Scala Koans (http://www.scalakoans.org/). If you havent looked at the ones from Lab 1, we consider you look at those, particularly AboutCaseClasses and AboutPatternMatching.

1. Feedback. Complete the survey on the linked from the moodle after completing this as- signment. 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 JAVA SC R I P T Y program should behave. Unless otherwise specified, we will continue to try to match JavaScript semantics as imple- mented by Node.js/Googles 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 JAVA SC R I P T Y specification with respect to JavaScript is certainly deserving of extra credit.

In this lab, we extend JAVA SC R I P T Y 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 ended up with a form of dynamic scoping.

The syntax of JAVA SC R I P T Y 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 ).

expressions e ::= x | n | b | str | undefined | uop e1 | e1 bop e2

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

| function p (x ) e1 | e1 (e2 ) | typeerror values v ::= n | b | undefined | str | function p (x ) e1 unary operators uop ::= | !

binary operators bop ::= , | + | | * | / | === | !== | < | <= | > | >= | && | ||

variables x

numbers (doubles) n

booleans b ::= true | false

strings str

function names p ::= x | ε

valueenvironments E ::= · | E [ x 7→ v ]

Figure 1: Abstract Syntax of JAVA SC R I P T Y

statements s ::= const x = e | e | { s1 } | ; | s1 s2

= 1

expressions e ::= · · · | const x e; e2

| (e1 )

x )

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

Figure 2: Concrete Syntax of JAVA SC R I P T Y

In a function expression, the function name p can either be an identifier or empty. The identifier is 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 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 ab- stract syntax in order to match the syntactic structure of JavaScript. For function expres- sions, 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 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 JAVA SC R I P T Y 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.

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

Function(p , x , e1 ) function p (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 JAVA SC R I P T Y. After each case class or

case object, we show the correspondence between the representation and the concrete syntax.

EVA LVA R

EVA LVA L

EVA L NE G

EVA L NOT

E ` e v

E ` x E (x )

EVA L SE Q

E ` v v

E ` e 1 v 1 n 0 = toNumber(v 1 )

E ` e1 n0

EVA L PLU S NU M B E R

E ` e 1 v 1 b 0 = ¬ toBoolean(v 1 )

E ` ! e1 b0

E ` e 1 v 1 E ` e 2 v 2

E ` e1 , e2 v2

EVA L PLU S ST R I N G1

E ` e 1 v 1 E ` e 2 v 2 n 0 = toNumber(v 1 ) + toNumber(v 2 ) v 1 6= str 1 v 2 6= str 2

E ` e1 + e2 n0

EVA L PLU S ST R I N G2

E ` e 1 str 1 E ` e 2 v 2 str 0 = str 1 + toString(v 2 )

E ` e1 + e2 str0

EVA L AR I T H

E ` e 1 v 1 E ` e 2 str 2 str 0 = toString(v 1 ) + str 2

E ` e1 + e2 str0

E ` e 1 v 1 E ` e 2 v 2 n 0 = toNumber(v 1 ) bop toNumber(v 2 ) bop {, , /}

E ` e1 bop e2 n0

EVA L IN E QUA L I T Y NU M B E R

E ` e1 v1 E ` e2 v2

b 0 = toNumber(v 1 ) bop toNumber(v 2 ) v 1 6= str 1 v 2 6= str 2 bop {<, <=, >, >=}

E ` e1 bop e2 b0

EVA L IN E QUA L I T Y ST R I N G

E ` e 1 str 1 E ` e 2 str 2 b 0 = str 1 bop str 2 bop {<, <=, >, >=}

E ` e1 bop e2 b0

EVA L EQUA L I T Y

E ` e1 v1 E ` e2 v2

v 1 6= function p 1 (x1 ) e 1 v 2 6= function p 1 (x2 ) e 2 b 0 = (v 1 bop v 2 ) bop {===, ! ==}

E ` e1 bop e2 b0

EVA L AN D TRU E

E ` e 1 v 1 true = toBoolean(v 1 ) E ` e 2 v 2

E ` e1 && e2 v2

EVA LOR FA L S E

EVA L AN D FA L S E

E ` e 1 v 1 false = toBoolean(v 1 )

E ` e1 && e2 v1

EVA L PR I N T

EVA LORTRU E

E ` e 1 v 1 true = toBoolean(v 1 )

E ` e1 || e2 v1

E ` e 1 v 1 false = toBoolean(v 1 ) E ` e 2 v 2

E ` e1 || e2 v2

EVA L IF TRU E

E ` e 1 v 1 true = toBoolean(v 1 ) E ` e 2 v 2

E ` e1 ? e2 : e3 v2

E ` e 1 v 1 v 1 printed

E ` console.log(e1 ) undefined

EVA L IF FA L S E

E ` e 1 v 1 false = toBoolean(v 1 ) E ` e 3 v 3

E ` e1 ? e2 : e3 v3

EVA LCO N S T

E ` e 1 v 1 E [ x 7→ v 1 ] ` e 2 v 2

E ` const x = e1 ; e2 v2

EVA LCA L L RE C

EVA LCA L L

E ` e 1 v 1 v 1 = function (x ) e 0 E ` e 2 v 2 E [ x 7→ v 2 ] ` e 0 v 0

E ` e1 (e2 ) v 0

E ` e 1 v 1 v 1 = function x1 (x2 ) e 0 E ` e 2 v 2 E [ x1 7→ v 1 ][ x2 7→ v 2 ] ` e 0 v 0

E ` e1 (e2 ) v 0

Figure 4: Big-step operational semantics of JAVA SC R I P T Y (with dynamic scoping).

toNumber(n) toNumber(true) toNumber(false) toNumber(undefined) toNumber(str) toNumber(function p (x ) e1 )

def

n

=

def

1

def

=

def

= 0

NaN

=

def

= parse str

def

= NaN

toBoolean(n) toBoolean(n) toBoolean(b) toBoolean(undefined) toBoolean(str) toBoolean(str)

toBoolean(function p (x ) e1 )

def

def

= false if n = 0 or n = NaN

true otherwise

=

def

= b

def

= false

def

= false if str = “”

def

= true otherwise

def

= true

toString(n) toString(true) toString(false) toString(undefined) toString(str) toString(function p (x ) e1 )

def

= string of n

def

def

= true

def

=

= false” “undefined

def

= str

def

= 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.

EVA LT Y PE ER RO R EQUA L I T Y1

E ` e 1 v 1 v 1 = function p 1 (x1 ) e 1 bop {===, ! ==}

E ` e1 bop e2 typeerror

E ` e v

EVA LT Y PE ER RO R EQUA L I T Y2

E ` e 2 v 2 v 2 = function p 1 (x1 ) e 1 bop {===, ! ==}

E ` e1 bop e2 typeerror

EVA LT Y PE ER RO RCA L L

v 1 6= function p (x ) e 1

E ` v1 (e2 ) typeerror

EVA L PRO PAG AT E UN A RY

E ` e 1 typeerror

E ` uop e1 typeerror

EVA L PRO PAG AT E PR I N T

E ` e 1 typeerror

E ` console.log(e1 ) typeerror

EVA L PRO PAG AT E BI N A RY1

E ` e 1 typeerror

E ` e1 bop e2 typeerror

EVA L PRO PAG AT E IF

E ` e 1 typeerror

E ` e1 ? e2 : e3 typeerror

EVA L PRO PAG AT E BI N A RY2

E ` e 2 typeerror

E ` e1 bop e2 typeerror

EVA L PRO PAG AT E CO N S T

E ` e 1 typeerror

E ` const x = e1 ; e2 typeerror

EVA L PRO PAG AT E CA L L1

E ` e 1 typeerror

E ` e1 (e2 ) typeerror

EVA L PRO PAG AT E CA L L2

E ` e 2 typeerror

E ` e1 (e2 ) typeerror

Figure 6: Big-step operational semantics of JAVA SC R I P T Y: Dynamic type error rules.

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 en- vironment 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 judg- ment 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 EVA LCA L L, EVA LCA L L RE C, and part of EVA L EQUA L I T Y. 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 JAVA SC R I P T Y, 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 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 will implement the EVA LT Y PE ER RO R rules explicitly, but the EVA L PRO PAG AT E rules are imple- mented implicitly with Scalas exception propagation semantics.

Note in rule EVA L EQUA L I T Y, 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 slight departure from JavaScript.

(a) First, write some JAVA SC R I P T Y 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 JAVA SC R I P T Y expression e in a value environment env to a value ac- cording to the evaluation judgment E ` e v .

The following helper functions for converting values to numbers, booleans, and strings are provided:

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

DO NE G

n 0 = toNumber(v )

v n0

DO PLU S NU M B E R

DO NOT

b 0 = ¬ toBoolean(v )

! v b0

D O S E Q

v1 , e2 e2

DO PLU S ST R I N G1

e e 0

n 0 = toNumber(v 1 ) + toNumber(v 2 ) v 1 6= str 1 v 2 6= str 2

v1 + v2 n0

str 0 = str 1 + toString(v 2 )

str1 + v2 str0

DO PLU S ST R I N G2

str 0 = toString(v 1 ) + str 2

v1 + str2 str0

DO IN E QUA L I T Y NU M B E R1

DOAR I T H

n 0 = toNumber(v 1 ) bop toNumber(v 2 ) bop {, , /}

v1 bop v2 n0

b 0 = toNumber(v 1 ) bop toNumber(v 2 ) bop {<, <=, >, >=} v 1 6= str 1

v1 bop v2 b0

DO IN E QUA L I T Y NU M B E R2

b 0 = toNumber(v 1 ) bop toNumber(v 2 ) bop {<, <=, >, >=} v 2 6= str 2

v1 bop v2 b0

DO IN E QUA L I T Y ST R I N G

b 0 = str 1 bop str 2 bop {<, <=, >, >=}

str1 bop str2 b0

DO EQUA L I T Y

v 1 6= function p 1 (x1 ) e 1 v 2 6= function p 1 (x2 ) e 2 b 0 = (v 1 bop v 2 ) bop {===, ! ==}

v1 bop v2 b0

DOAN D TRU E

DOAN D FA L S E

DO ORTRU E

DO OR FA L S E

true = toBoolean(v 1 )

v1 && e2 e2

false = toBoolean(v 1 )

v1 && e2 v1

true = toBoolean(v 1 )

v1 || e2 v1

false = toBoolean(v 1 )

v1 || e2 e2

DO PR I N T

v 1 printed

console.log(v1 ) undefined

D O C O N S T

const x = v1 ; e2 e2 [v1 /x ]

DO IF TRU E

true = toBoolean(v 1 )

v1 ? e2 : e3 e2

DO CA L L

v 1 = function (x ) e 1

v1 (v2 ) e1 [v2 /x ]

DO IF FA L S E

false = toBoolean(v 1 )

v1 ? e2 : e3 e3

DO CA L L RE C

v 1 = function x1 (x2 ) e 1

v1 (v2 ) e1 [v1 /x1 ][v2 /x2 ]

Figure 7: Small-step operational semantics of JAVA SC R I P T Y: DO rules.

SE A RC H UN A RY

1

SE A RC H BI N A RY1

2

SE A RC H BI N A RYAR I T H2

e e 0

1

e 1 e 0

1

uop e1 uop e 0

SE A RC H EQUA L I T Y2

e 1 e 0

1

e1 bop e2 e 0 bop e2

e 2 e 0 bop {+, , , /, <, <=, >, >=}

2

1

v1 bop e2 v1 bop e 0

SE A RC H PR I N T

2

e 2 e 0 v 1 6= function p (x ) e 1 bop {===, ! ==}

2

v1 bop e2 v1 bop e 0

e 1 e 0

1

console.log(e1 ) console.log(e 0 )

SE A RC H IF

1

e 1 e 0

1

e1 ? e2 : e3 e 0 ? e2 : e3

SE A RC H CO N S T

1

e 1 e 0

1

const x = e1 ; e2 const x = e 0 ; e2

SE A RC H CA L L1

1

e 1 e 0

1

e1 (e2 ) e 0 (e2 )

SE A RC H CA L L2

2

e 2 e 0

2

¡function p (x ) e1 ¢(e2 ) ¡function p (x ) e1 ¢(e 0 )

Figure 8: Small-step operational semantics of JAVA SC R I P T Y: SE A RC H rules.

T Y PE ER RO R EQUA L I T Y1

bop {===, ! ==}

(function p (x ) e1 ) bop e2 typeerror

T Y PE ER RO R EQUA L I T Y1

bop {===, ! ==}

v1 bop (function p (x ) e2 ) typeerror

e e 0

PRO PAG AT E UN A RY

uop typeerror typeerror

T Y PE ER RO RCA L L

v 1 6= function p (x ) e 1

v1 (e2 ) typeerror

PRO PAG AT E BI N A RY

typeerror bop e2 typeerror

PRO PAG AT E BI N A RY

v1 bop typeerror typeerror

PRO PAG AT E PR I N T

console.log(typeerror) typeerror

PRO PAG AT E IF

typeerror ? e2 : e3 typeerror

PRO PAG AT E CO N S T

const x = typeerror; e2 typeerror

PRO PAG AT E CA L L1

typeerror(e2 ) typeerror

PRO PAG AT E CA L L2

v1 (typeerror) typeerror

Figure 9: Small-step operational semantics of JAVA SC R I P T Y: Dynamic type error rules.

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 e 0 defined in Figures 7, 8, and 9. We write e [v /x ] for sub- stituting 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 e 0 .

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 ex- pressions to a value using your interpreter implementations.

4. Evaluation Order.

Consider the small-step operational semantics for JAVA SC R I P T Y 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) JAVA SC R I P T Y. Consider the small-step operational semantics for JAVA SC R I P T Y shown in Figures 7, 8, and 9. Does e1 && e2 short circuit? Explain.