CSCI 3155: Lab Assignment #4 Solution

$30.00

Category:

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

 

  • Lab4Spec-YourIdentiKey.scala with any updates to your unit tests.
  • Lab4-YourIdentiKey.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, About- Lists, 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.

 

  1. 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 Scala’s library. One of the  most fundamental opera- tions that one  needs to perform with a collection is to iterate over the elements of the col- lection. 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 el- ements 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 pro- vided  for you.  Do not  call compressFold recursively or any other List library  meth- ods.

(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 in-order traversal are in strictly accending order (i.e., d1 < d2 < · · · < dn ).

Example:

 

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

res0: Boolean = false

 

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

 

 Γ ` 1 : number       Γ ` 2 : number       bop ∈ {+, −, ∗, /}

Γ ` e1 bop e2 : number

 

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

 Γ ` 1 : string        Γ ` 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

 

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

Γ ` e1 bop e2 : bool

 

T Y PE IF

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

Γ ` e1 ? e2 : e3 : τ

                     Γ  ` 1  : τ 1                      

Γ ` console.log(e1 ) : Undefined

 

T Y PE CO N S T

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

Γ ` const x = e1 ; e2 : τ2

 

T Y PE CA L L

 Γ ` e : (x1 : τ 1 , . . . , xn  : τ n ) τ     Γ ` 1 : τ 1          · · ·        Γ ` 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.

 

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

 

  1. JavaScripty Small-Step Interpreter

 

In this  question, we update substitute and  step from  Lab 3 for multi-parameter func- tions 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).

 

  1. 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?

  1. Then, work on the function cases. Hints: You might want to use your mapFirst func- tion 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

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

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

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

1

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

 

SE A RC H CA L L1

 

1

             e 1   0                        

1

e1 ? e2 : e3 −→ e 0    ? e2 : e3

 

SE A RC H CA L L2

                       e 1   0                                          

1

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

                  e e 0                                

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

 

i

                                                                       e i   0                                                                                                                                 

i

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

 

SE A RC H OB J E C T

i

                      e i   0                                       

i

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

SE A RC H GE T FI E L D

1

    e 1   0       

1

e1 . f −→ e 0  . f

 

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


error: Content is protected !!