CSCI 3155: Lab Assignment 4 Solved

The primary purpose of this lab to understand the interplay between type checking and evaluation. Concretely, we will extend JAVASCRIPTY 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.

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:

• Howwelldoesyoursubmissionanswerthequestions? 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:

• 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

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

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

Replace YourIdentiKey with your IdentiKey (e.g., I would submit Lab4-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 Lab4.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 lab4 https://github.com/bechang/pppl-labs.git lab4

A suggested way to get familiar with Scala is to do some small lessons with Scala Koans (http://www.scalakoans.org/). UsefulonesforLab4areAboutHigherOrderFunctions,AboutLists, AboutPartialFunctions, and AboutInfixPrefixAndPostfixOperators.

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

2. Warm-Up: Collections. To implement our interpreter for JAVASCRIPTY with objects, we will need to make use of collections from Scala’s library. One of the most fundamental operations 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 functions 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 Ninety-Nine Scala Problems: http://aperiodic.net/phil/scala/s-99/ .

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 provided 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

def foldLeft[A](z: A)(f: (A, Int) = A): A = { def loop(acc: A, t: Tree): A = t match { case Empty = ???

case Node(l, d, r) = ???

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

(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 in-order 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 with 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 JAVASCRIPTY. We will not permit any type conversions and will guarantee the absence of dynamic type errors.

In this lab, we extend JAVASCRIPTY with types, multi-parameter functions, and objects/records (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 }

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 mutation, dynamic extension, or dynamic dispatch. 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 a 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 JAVASCRIPTY in this lab.

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

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

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

| { f1 : v1,...,fn : vn } uop ::= -|!

bop ::= ,|+|-|*|/|===|!==|<|<=||=|&&|||
types
τ ::= number|bool|string|Undefined| (x : τ) ⇒τ0 | { f1 : τ1;...;fn : τn }
variables
x
numbers (doubles)
n
booleans strings
b ::= true|false

str
function names field names
p ::= x |ε f
type annotations
tann ::= : τ|ε
type environments
Γ ::= ·|Γ[x 7→τ]

Figure 1: Abstract Syntax of JAVASCRIPTY
| str |function p(x : τ)tann e1 | e0(e) | { f1 : e1,...,fn : en } | e1.f

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

expressions e ::= ···|(const(((x =(e(1(; e2(|((e(1)

|(function((p((x(:(τ)(tann e1 |function p(x : τ)tann { s1 return e1 } | (x : τ) = e

((

Figure 2: Concrete Syntax of JAVASCRIPTY

/* Functions */

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

Function(p, (x,τ), tann, e1) functionp(x : τ)tanne1 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 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.

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. We do, however, support the anonymous function form

(x : τ) = e1

from TypeScript, which is syntactic sugar for

function (x : τ) { return e1 } .

In Figure 3, 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.

Inthislab,weimplementatypecheckerthatisverysimilartoabig-stepinterpreter. Instead of computing the value of an expression by recursively computing the value of each subexpression, we infer the type of an expression, by recursively inferring the type of each subexpression. 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 4, 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 (Γ) 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.

Γ` e : τ

TYPEVAR



Γ` x : Γ(x)
TYPENEG

Γ`e1 : number

Γ`−e1 : number
TYPENOT

Γ`e1 : bool

Γ` !e1 : bool
TYPESEQ

Γ`e1 : τ1 Γ`e2 : τ2

Γ`e1 , e2 : τ2
TYPEARITH


TYPEPLUSSTRING
Γ`e1 : number Γ`e2 : number bop∈ {+,−,∗,/} Γ`e1 : string Γ`e2 : string

Γ`e1 bope2 : number Γ`e1 +e2 : string

TYPEINEQUALITYNUMBER

Γ`e1 : number Γ`e2 : number bop∈ {<,<=,,=}

Γ`e1 bope2 : bool

TYPEINEQUALITYSTRING

Γ`e1 : string

TYPEEQUALITY
Γ`e2 : string bop∈ {<,<=,,=}

Γ`e1 bope2 : bool
Γ`e1 : τ Γ`e2 : τ
τ has no function types bop∈ {===,! ==}

Γ`e1 bope2 : bool
TYPEANDOR

Γ`e1 : bool Γ`e2 : bool
TYPEPRINT bop∈ {&&,||} Γ`e1 : τ1
Γ`e1 bope2 : bool Γ`console.log(e1) : Undefined

TYPEIF TYPECONST

Γ`e1 : bool Γ`e2 : τ Γ`e3 : τ Γ`e1 : τ1 Γ[x 7→τ1] `e2 : τ2

Γ`e1 ? e2 : e3 : τ Γ`constx =e1; e2 : τ2

TYPECALL TYPEOBJECT

Γ`e : (x1 : τ1,...,xn : τn) ⇒τ Γ`e1 : τ1 ··· Γ`en : τn Γ`ei : τi (for all i)

Γ`e(e1,...,en) : τ
Γ` { ..., fi : ei,... } : { ..., fi : τi,... }
TYPEGETFIELD

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



Γ`e.f : τ Γ`n : number

TYPEFUNCTION
TYPEBOOL TYPESTRING



Γ`b : bool Γ`str : string
TYPEUNDEFINED Γ[x1 7→τ1]···[xn 7→τn] `e : τ τ0 = (x1 : τ1,...,xn : τn) ⇒τ



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

TYPEFUNCTIONANN

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

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

TYPERECFUNCTION

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

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

Figure 4: Typing of JAVASCRIPTY.

The TYPEEQUALITY 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, completethecasesforthebasicexpressionsexcludingFunction, Call, Obj, and GetField.

2. Then, work on these remaining cases. These cases use collections, so be sure to complete the previous question before attempting these cases. You can also work on step before finishing typeInfer.

Hints: Helpfullibrarymethodshereincludemap,foldLeft,zipped,foreach,andmapValues. 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 be greatly simplified. We eliminatetheneedtoperformconversionsandshouldnolongerthrowDynamicTypeError. 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 JAVASCRIPTY test input.

In particular, if the JAVASCRIPTY 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 JAVASCRIPTY is known as type safety.

A small-step operational semantics is given in Figure 5. This semantics no longer has conversions 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).

Asspecified, SEARCHOBJECT isnon-deterministic(why?). Asweviewobjectsasanunordered 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, import the cases from your Lab 3 step function (perhaps excluding Call) and simplify them to remove calls to conversions (e.g., toNumber) and cases that throw DynamicTypeError. Follow the small-step operational semantics in Figure 5 to see how to simplify your Lab 3 code (e.g., start with DONEG).

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 functionfromthewarm-upquestion. Helpfullibrarymethodshereincludemap,foldRight, zipped, and forall.


DONEG n0 =−n

−n −→n0
DONOT b0 =¬b

!b −→b0
DOSEQ v1 , e2 −→e2
DOARITH n0 =n1 bopn2 bop∈ {+,−,∗,/} n1 bopn2 −→n0
DOPLUSSTRING

str0 =str1+str2 str1 +str2 −→str0
e −→ e0

DOINEQUALITYNUMBER DOINEQUALITYSTRING b0 =n1 bopn2 bop∈ {<,<=,,=} b0 =str1 bopstr2 bop∈ {<,<=,,=}

n1 bopn2 −→b0 str1 bopstr2 −→b0

DOEQUALITY

b0 = (v1 bopv2) bop∈ {===,! ==} DOANDTRUE DOANDFALSE



v1 bopv2 −→b0 true && e2 −→e2 false && e2 −→false

DOPRINT DOORTRUE DOORFALSE v1 printed DOIFTRUE



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

DOCALL DOIFFALSE DOCONST v =function (x1 : τ1,...,xn : τn)tanne



false ? e2 : e3 −→e3 constx = v1; e2 −→e2[v1/x] v(v1,...vn) −→e[vn/xn]···[v1/x1]

DOCALLREC SEARCHUNARY v =functionx(x1 : τ1,...,xn : τn)tanne DOGETFIELD e1 −→e10

v(v1,...vn) −→e[vn/xn]···[v1/x1][v/x] { f1 : v1,..., fi : vi,..., fn : vn }.fi −→ vi uope1 −→uope10

SEARCHBINARY1 SEARCHBINARY2 SEARCHPRINT

e1 −→e10 e2 −→e20 e1 −→e10

e1 bope2 −→e10 bope2 v1 bope2 −→ v1 bope20 console.log(e1) −→console.log(e10 )

SEARCHIF SEARCHCONST SEARCHCALL1

e1 −→e10 e1 −→e10 e −→e0

e1 ? e2 : e3 −→e10 ? e2 : e3 constx =e1; e2 −→constx =e10 ; e2 e(e1,...,en) −→e0(e1,...,en)

SEARCHCALL2 ei −→ei0



¡functionp(x : τ)tanne¢(v1,...,vi−1,ei,...,en) −→¡functionp(x : τ)tanne¢(v1,...,vi−1,ei0,...,en)

SEARCHOBJECT

ei −→ei0

{ ..., fi : ei,... } −→ { ..., fi : ei0,... }
SEARCHGETFIELD e1 −→e10 e1.f −→e10 .f
Figure 5: Small-step operational semantics of JAVASCRIPTY