Lab Assignment #4 Solution

$30.00

Description

The primary purpose of this lab to understand the interplay between type checking and evaluation. Concretely, we will extend JAVA SC R I P T Y with immutable objects and extend our small-step interpreter from Lab 3. Unlike all prior language constructs, object expressions do not have an a priori bound on the number of sub-expressions because an object can have any number of fields. To represent objects, we will use collections from the Scala library and thus will need to get used to working with the Scala collection API.

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 two files named as follows:

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

Lab4_YourIdentiKey.scala with your answers to the coding exercises

Lab4SpecYourIdentiKey.scala with any updates to your unit tests.

Lab4YourIdentiKey.jsy with a challenging test case for your JAVA SC R I P T Y interpreter. Replace YourIdentiKey with your IdentiKey. To help with managing the submissions, we ask that

you rename your uploaded files in this manner.

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/). Useful ones for Lab 4 are AboutHigherOrderFunctions, AboutLists, AboutPartialFunctions, and AboutInfixPrefixAndPostfixOperators.

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. Warm-Up: Collections. To implement our interpreter for JAVA SC R I P T Y with objects, we will need to make use of collections from Scalas library. One of the most fundamental opera- tions that one needs to perform with a collection is to iterate over the elements of the collection. Like many other languages with first-class functions (e.g., Python, ML), the Scala library provides various iteration operations via higher-order functions. Higher-order func- tions are functions that take functions as parameters. The function parameters are often called callbacks, and for collections, they typically specify what the library client wants to do for each element.

In this question, we practice both writing such higher-order functions in a library and using them as a client.

(a) Implement a function

def compressRec[A](l: List[A]): List[A]

that eliminates consecutive duplicates of list elements. If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.

Example:

scala> compressRec(List(1, 2, 2, 3, 3, 3))

res0: List[Int] = List(1, 2, 3)

This test has been provided for you in the template.

For this exercise, implement the function by direct recursion (e.g., pattern match on l

and call compressRec recursively). Do not call any List library methods. This exercise is from NinetyNine Scala Problems:

http://aperiodic.net/phil/scala/s99/ .

Some sample solutions are given there, which you are welcome to view. However, it is strongly encouraged that you first attempt this exercise before looking there. The purpose of the exercise is to get some practice for the later part of this homework. Note that the solutions there do not satisfy the requirements here (as they use library functions). If at some point you feel like you need more practice with collections, the above page is a good resource.

(b) Re-implement the compress function from the previous part as compressFold using the foldRight method from the List library. The call to foldRight has been pro- vided for you. Do not call compressFold recursively or any other List library methods.

(c) Implement a higher-order recursive function

def mapFirst[A](f: A => Option[A])(l: List[A]): List[A]

that finds the first element in l where f applied to it returns a Some(a) for some value a. It should replace that element with a and leave l the same everywhere else. Example:

scala> mapFirst((i: Int) => if (i < 0) Some(-i) else None)(List(1,2,-3,4,-5))

res0: List[Int] = List(1, 2, 3, 4, -5)

(d) Consider again the binary search tree data structure from Lab 1:

sealed abstract class Tree {

def insert(n: Int): Tree = this match { case Empty => Node(Empty, n, Empty) case Node(l, d, r) =>

if (n < d) Node(l insert n, d, r) else Node(l, d, r insert n)

}

def foldLeft[A](z: A)(f: (A, Int) => A): A = {

def loop(acc: A, t: Tree): A = t match {

case Empty => throw new UnsupportedOperationException

case Node(l, d, r) => throw new UnsupportedOperationException

}

loop(z, this)

}

}

case object Empty extends Tree

case class Node(l: Tree, d: Int, r: Tree) extends Tree

Here, we have implement the binary search tree insert as a method of Tree. For this exercise, complete the higher-order method foldLeft. This method performs an in-order traversal of the input tree this calling the callback f to accumulate a result. Suppose the in-order traversal of the input tree yields the following sequence of data values: d1 , d2 , . . . , dn . Then, foldLeft yields

f(· · · (f(f(z, d1 ), d2 )) · · · ), dn ) .

We have provided a test client sum that computes the sum of all of the data values in the tree using your foldLeft method.

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

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

| str | function p (x : τ)tann e1 | e0 (e )

| { f1 : e1 , . . . , fn : en } | e1 . f

values v ::= n | b | undefined | str | function p (x : τ)tann e1

| { f1 : v1 , . . . , fn : vn }

unary operators uop ::= | !

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

types τ ::= number | bool | string | Undefined | (x : τ) τ0 | { f1 : τ1 ; . . . ; fn : τn }

variables x

numbers (doubles) n

booleans b ::= true | false

strings str function names p ::= x | ε field names f

type annotations tann ::= : τ | ε

type environments Γ ::= · | Γ[ x 7→ τ]

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

(e) Implement a function

def strictlyOrdered(t: Tree): Boolean

as a client of your foldLeft method that checks that the data values of t as an inorder traversal are in strictly accending order (i.e., d1 < d2 < · · · < dn ).

Example:

scala> strictlyOrdered(treeFromList(List(1,1,2)))

res0: Boolean = false

3. JavaScripty Type Checker

As we have seen in the prior labs, dealing conversions and checking for dynamic type errors complicate the interpreter implementation. Some languages restrict the possible programs that it will execute to ones that it can guarantee will not result in a dynamic type error. This restriction of programs is enforced with an analysis phase after parsing known as type checking. Such languages are called strongly, statically-typed. In this lab, we will implement a strongly, statically-typed version of JAVA SC R I P T Y. We will not permit any type conversions and will guarantee the absence of dynamic type errors.

In this lab, we extend JAVA SC R I P T Y with types, multi-parameter functions, and objects/rec- ords (see Figure 1). We have a language of types τ and annotate function parameters with types. Functions can now take any number of parameters. We write a sequence of things using either an overbar or dots (e.g., e or e1 , . . . , en for a sequence of expressions). An object literal

{ f1 : e1 , . . . , fn : en }

/* Functions */

case class Function(p: Option[String], params: List[(String,Typ)], tann: Option[Typ],

e1: Expr) extends Expr

Function(p , (x , τ), tann, e1 ) function p (x : τ)tann e1

case class Call(e1: Expr, args: List[Expr]) extends Expr

Call(e1 , e ) e1 (e )

/* Objects */

case class Obj(fields: Map[String, Expr]) extends Expr

Object(f : e ) { f : e }

case class GetField(e1: Expr, f: String) extends Expr

GetField(e1 , f ) e1 . f

/* Types */

case class TFunction(params: List[(String,Typ)], tret: Typ) extends Typ

TFunction(x : τ, τ0 ) (x : τ) τ0

case class TObj(tfields: Map[String, Typ]) extends Typ

TObj(f : τ) { f : τ }

Figure 2: 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.

is a comma-separted sequence of field names with initialization expressions surrounded by braces. Objects in this lab are more like records or C-structs as opposed to JavaScript objects, as we do not have any form of dynamic dispatch. Our objects in this lab are also immutable. The field read expression e1 . f evaluates e1 to an object value and then looks up the field named f . An object value is a sequence of field names associated with values. The type language τ includes base types for numbers, booleans, strings, and undefined, as well as constructed types for functions (x : τ) τ0 and objects { f1 : τ1 ; . . . ; fn : τn }.

As an aside, we have chosen syntax that is compatible with the TypeScript language that adds typing to JavaScript. TypeScript aims to be fully compatible with JavaScript, so it is not as strictly typed as JAVA SC R I P T Y in this lab.

In Figure 2, we show the updated and new AST nodes. We update Function and Call for multiple parameters/arguments. Object literals and field read expressions are represented by Object and GetField, respectively.

In this lab, we implement a type checker that is very similar to a big-step interpreter. Instead of computing the value of an expression by recursively computing the value of each sub- expression, we infer the type of an expression, by recursively inferring the type of each sub- expression. An expression is well-typed if we can infer a type for it.

Given its similarity to big-step evaluation, we can formalize a type inference algorithm in a similar way. In Figure 3, we define the judgment form Γ ` e : τ which says informally, In type environment Γ, expression e has type τ. We will implement a function

def typeInfer(env: Map[String,Typ], e: Expr): Typ

that corresponds directly to this judgment form. It takes as input a type environment env

T Y PE NE G

T Y PE NOT

T Y PE SE Q

Γ ` e : τ

T Y P E VA R

Γ ` x : Γ(x ) T Y PE AR I T H

Γ ` e 1 : number

Γ ` e1 : number

Γ ` e 1 : bool

Γ ` ! e1 : bool

Γ ` e 1 : τ 1 Γ ` e 2 : τ 2

Γ` e1 , e2 : τ2

T Y PE PLU S ST R I N G

Γ ` e 1 : number Γ ` e 2 : number bop {+, , , /}

Γ ` e1 bop e2 : number

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

Γ ` e 1 : string Γ ` e 2 : string

Γ ` e1 + e2 : string

Γ ` e 1 : number Γ ` e 2 : number bop {<, <=, >, >=}

Γ ` e1 bop e2 : bool

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

` e 1 : string Γ ` e 2 : string bop {<, <=, >, >=}

Γ ` e1 bop e2 : bool

T Y PE EQUA L I T Y

` e 1 : τ Γ ` e 2 : τ τ has no function types bop {===, ! ==}

Γ ` e1 bop e2 : bool

T Y PE AN D OR

T Y PE PR I N T

` e 1 : bool Γ ` e 2 : bool bop {&&, ||}

Γ ` e1 bop e2 : bool

T Y PE IF

Γ ` e 1 : bool Γ ` e 2 : τ Γ ` e 3 : τ

Γ ` e1 ? e2 : e3 : τ

Γ ` e 1 : τ 1

Γ ` console.log(e1 ) : Undefined

T Y PE CO N S T

Γ ` e 1 : τ 1 Γ[ x 7→ τ 1 ] ` e 2 : τ 2

Γ ` const x = e1 ; e2 : τ2

T Y PE CA L L

Γ ` e : (x1 : τ 1 , . . . , xn : τ n ) τ Γ ` e 1 : τ 1 · · · Γ ` e n : τ n

Γ ` e (e1 , . . . , en ) : τ

T Y PE OB J E C T

Γ ` e i : τ i (for all i )

Γ ` { . . . , fi : ei , . . . } : { . . . , fi : τi , . . . }

T Y PE GE T FI E L D

Γ ` e : { . . . , f : τ , . . . }

Γ ` e. f : τ

T Y P E N U M B E R

Γ ` n : number

T Y PE FU N C T I O N

T Y P E B O O L

Γ ` b : bool

T Y P E S T R I N G

Γ ` str : string

T Y P E U N D E FI N E D

Γ ` undefined : Undefined

Γ[ x1 7→ τ 1 ] · · · [ xn 7→ τ n ] ` e : τ τ 0 = (x1 : τ 1 , . . . , xn : τ n ) τ

Γ ` function (x1 : τ1 , . . . , xn : τn ) e : τ0

T Y PE FU N C T I O N AN N

Γ[ x1 7→ τ 1 ] · · · [ xn 7→ τ n ] ` e : τ τ 0 = (x1 : τ 1 , . . . , xn : τ n ) τ

Γ ` function (x1 : τ1 , . . . , xn : τn ) : τ e : τ0

T Y PE RE C FU N C T I O N

[ x 7→ τ 0 ][ x1 7→ τ 1 ] · · · [ xn 7→ τ n ] ` e : τ τ 0 = (x1 : τ 1 , . . . , xn : τ n ) τ

Γ ` function x (x1 : τ1 , . . . , xn : τn ) : τ e : τ0

Figure 3: Typing of JAVA SC R I P T Y.

(Γ) and an expression e (e ) returns a type Typ (τ). It is informative to compare these rules with the big-step operational semantics from Lab 3.

The T Y PE EQUA L I T Y is slightly informal in stating

τ has no function types .

We intend this statement to say that the structure of τ has no function types. The helper function hasFunctionTyp is intended to return true if a function type appears in the input and false if it does not, so this statement can be checked by taking the negation of a call to hasFunctionTyp.

To signal a type error, we will use a Scala exception

case class StaticTypeError(tbad: Typ, esub: Expr, e: Expr) extends Exception

where tbad is the type that is inferred sub-expression esub of input expression e. These arguments are used to construct a useful error message. We also provide a helper function err to simplify throwing this exception.

We suggest the following step-by-step order to complete typeInfer.

1. First, complete the cases for the basic expressions excluding Function, Call, Obj, and

GetField.

2. Then, work on these remaining cases. These cases use collections, so be sure to com- plete the previous question before attempting these cases. You can also work on step before finishing typeInfer. Hints: Helpful library methods here include map, foldLeft, zipped, foreach, and mapValues. You may want to use zipped in the Call case to match up formal parameters and actual arguments.

4. JavaScripty Small-Step Interpreter

In this question, we update substitute and step from Lab 3 for multi-parameter functions and objects. Because of type checking, the step cases can simplified greatly. We elim- inate the need to perform conversions and should no longer throw DynamicTypeError.

We introduce another Scala exception type

case class StuckError(e: Expr) extends Exception

that should be thrown when there is no possible next step. This exception looks a lot like DynamicTypeError except that the intent is that it should never be raised. It is intended to signal a coding error in our interpreter rather than an error in the JAVA SC R I P T Y test input.

In particular, if the JAVA SC R I P T Y expression e passed into step is closed and well-typed (i.e., judgment · ` e : τ holds meaning inferType(e ) does not throw StaticTypeError), then step should never throw a StuckError. This property of JAVA SC R I P T Y is known as type safety.

A small-step operational semantics is given in Figure 4. This semantics no longer has con- versions compared to Lab 3. It is much simpler because of type checking (e.g., even with the addition of objects, it fits on one page).

As specified, SE A RC H OB J E C T is non-deterministic. As we view objects as an unordered set of fields, it says an object expression takes can take a step by stepping on any of its component fields. To match the reference implementation, you should make the step go on the first non-value as given by the left-to-right iteration of the collection using Map.find.

We suggest the following step-by-step order to complete substitute and step.

1. First, complete the basic expression cases not given in the template (e.g., DO MI N U S,

DO IF TRU E).

2. Then, work on the object cases. These are actually simpler than the function cases.

Hint: Note that field names are different than variable names. Object expressions are not variable binding constructs–what does that mean about substitute for them?

3. Then, work on the function cases. Hints: You might want to use your mapFirst function from the warm-up question. Helpful library methods here include map, foldRight, zipped, and forall,

e e 0

DO NE G DO NOT

DOAR I T H

DO PLU S ST R I N G

n 0 = n

n n0

b 0 = ¬b

! b b0

D O S E Q

v1 , e2 e2

n 0 = n1 bop n2 bop {+, , , /}

n1 bop n2 n0

str 0 = str 1 + str 2

str1 + str2 str0

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

b 0 = n1 bop n2 bop {<, <=, >, >=}

n1 bop n2 b0

DO EQUA L I T Y

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

b 0 = (v 1 bop v 2 ) bop {===, ! ==}

v1 bop v2 b0

D O A N D T RU E

true && e2 e2

DO PR I N T

D O A N D FA L S E

false && e2 false

DO ORTRU E

true || e2 true

DO OR FA L S E

false || e2 e2

v1 printed

console.log(v1 ) undefined

DO CA L L

DO IF TRU E

true ? e2 : e3 e2

D O I F FA L S E

false ? e2 : e3 e3

DO CA L L RE C

D O C O N S T

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

v = function (x1 : τ 1 , . . . , xn : τ n )tann e v (v1 , . . . vn ) e [vn /xn ] · · · [v1 /x1 ]

1

SE A RC H UN A RY

v = function x (x1 : τ 1 , . . . , xn : τ n )tann e

v (v1 , . . . vn ) e [vn /xn ] · · · [v1 /x1 ][v /x ]

D O G E T F I E L D

{ f1 : v1 , . . . , fi : vi , . . . , fn : vn }. fi vi

e 1 e 0

1

uop e1 uop e 0

SE A RC H BI N A RY1

1

e 1 e 0

1

e1 bop e2 e 0 bop e2

SE A RC H IF

SE A RC H BI N A RY2

2

e 2 e 0

2

v1 bop e2 v1 bop e 0

1

SE A RC H CO N S T

SE A RC H PR I N T

1

e 1 e 0

1

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

SE A RC H CA L L1

1

e 1 e 0

1

e1 ? e2 : e3 e 0 ? e2 : e3

SE A RC H CA L L2

e 1 e 0

1

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

e e 0

e (e1 , . . . , en ) e 0 (e1 , . . . , en )

i

e i e 0

i

¡function p (x : τ) e ¢(v1 , . . . , vi 1 , ei , . . . , en ) ¡function p (x : τ) e ¢(v1 , . . . , vi 1 , e 0 , . . . , en )

SE A RC H OB J E C T

i

e i e 0

i

{ . . . , fi : ei , . . . } { . . . , fi : e 0 , . . . }

SE A RC H GE T FI E L D

1

e 1 e 0

1

e1 . f e 0 . f

Figure 4: Small-step operational semantics of JAVA SC R I P T Y