$30.00

## Description

The purpose of this assignment is to warm-up with Scala and to refresh preliminaries from prior courses.

Find a partner. You will work on this assignment in pairs. Feel free to use the Piazza forum to locate a partner; otherwise we can assign one to you. Each student is 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.

We use the following evaluation guideline in this course.

*B**oth ** **your** **ideas** **and ** **also** **the** **clarity ** **with** **which** **they** **a**r**e** **e**xp**r**essed ** **matte**r**—both** **in **your** **E**nglish** **p**r**ose** **and** **your** **c**ode!*

*W**e** **will** **consider ** **the** **foll**o**wing** **criteria** **in** **our** **g**r**ading:*

• How well does your submission answer the questions? *F**or** **e**xample,** **a** **common **mistake** **is** **to** **gi**v**e** **an ** **e**xample** **when** **a** **question** **asks for** **an ** **e**xplanation. ** **A**n **e**xample** **may ** **be** **useful** **in** **your** **e**xplanation,** **but** **it** **should** **not** **take** **the** **place** **of **the** **e**xpl**a**n**ati**o**n**.*

• How clear is your submission? *I**f** **we** **cannot** **understand** **what** **you** **a**r**e** **t**r**y**ing **to** **sa**y**,** **then ** **we** **cannot** **gi**v**e** **you** **points** **for** **it. ** **T**r**y** **r**eading **your** **answer** **aloud** **to **yourself ** **or** **a** **friend;** **this** **technique** **is** **often ** **a** **g**r**eat** **way** **to** **identify** **holes** **in** **y**our **r**easoning. ** **F**or** **code,** **not ** **e**v**e**r**y** **p**r**og**r**am** **that ** **“wo**r**ks” ** **dese**r**v**es full ** **c**r**edit. ** **W**e **must** **be** **able** **to** **r**ead** **and** **understand** **your** **intent.** **M**ake** **su**r**e** **you** **state** **any** **p**r**e- **conditions** **or** **in**v**ariants** **for** **your** **functions **(either ** **in** **comments,** **as** **asse**r**ti**ons, **or** **as** *require *clauses** **as** **app**r**opriat**e).*

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.

**S****ubmission**** ****I****nst****r****uctions. **** **Here’s what you need to complete in your pull request:

• Lab1.md include your answers to the written questions. This file should be formatted using the Markdown markup language.

1

• Lab1.scala with your answers to the coding exercises.

• Lab1.jsy with a challenging test case for your JAVA SC R I P T Y interpreter.

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 inter– view 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**** ****S****ta****r****ted. **** **Take a look at the pull request we be starting for your team. Because we are still setting up GitHub, you can also take a look at the assignment (lab1.zip) as it is posted on Piazza.

A suggested way to get familiar with Scala is to do some small lessons with Scala Koans (http://www.scalakoans.org/). For your convenience, the Scala Koans package is included in the code pack under the koans/ sub-directory. For this lab, we suggest that you consider looking at the AboutAsserts, AboutLiteralBooleans, AboutLiteralNumbers, AboutLiteralStrings, AboutMethods, AboutRecursion, AboutTuples, AboutCaseClasses, and AboutPatternMatching koans.

1. **Scala**** ****B****asics:**** ****B****inding**** ****and**** ****Scope**. For each the following uses of names, give the line where that name is bound. Briefly explain your reasoning (in no more than 1–2 sentences).

(a) Consider the following Scala code.

*1 ** ***v****al **** **pi = 3.14

*2 ** ***def **** **circumference(r: Double): Double = {

*3 ** ***v****al **** **pi = 3.14159

*4 ** *2.0 * pi * r

*5 ** *}

*6 ** ***def **** **area(r: Double): Double =

*7 ** *pi * r * r

The use of pi at line 4 is bound at which line? The use of pi at line 7 is bound at which line?

(b) Consider the following Scala code.

*1 ** ***v****al **** **x = 3

*2 ** ***def **** **f(x: Int): Int =

*3 ** *x **match **** **{

*4 ** ***case **** **0 **=> **** **0

*5 ** ***case **** **x **=> **** **{

*6 ** ***v****al **** **y = x + 1

*7 ** *({

*8 ** ***v****al **** **x = y + 1

*9 ** *y

*10 ** *} * f(x – 1))

*11 ** *}

*12 ** *}

*13 ** ***v****al **** **y = x + f(x)

The use of x at line 3 is bound at which line? The use of x at line 6 is bound at which line? The use of x at line 10 is bound at which line? The use of x at line 13 is bound at which line?

2. **Scala**** ****B****asics:**** ****T****yping**. In the following, I have left off the return type of function g. The body of g is well-typed if we can come up with a valid return type. Is the body of g well-typed?

*1 ** ***def **** **g(x: Int) = {

*2 ** ***v****al **** **(a, b) = (1, (x, 3))

*3 ** ***if **** **(x == 0) (b, 1) **else **** **(b, a + 2)

*4 ** *}

If so, give the return type of g and explain how you determined this type. For this explaina- tion, first, give the types for the names a and b. Then, explain the body expression using the following format:

*e** *: *τ** *because

*e*_{1} : *τ*_{1} because

. . .

*e*_{2} : *τ*_{2} because

. . .

where *e*_{1} and *e*_{2} are subexpressions of *e** *. Stop when you reach values (or names). As an example of the suggested format, consider the plus function:

**def **** **plus(x: Int, y: Int) = x + y

Yes, the body expression of plus is well-typed with type Int.

x + y : Int because

x : Int y : Int

3. **R****un-****T****ime**** ****Libra****r****y**. Most languages come with a standard library with support for things like data structures, mathematical operators, string processing, etc. Standard library func- tions may be implemented in the object language (perhaps for portability) or the meta lan- guage (perhaps for implementation efficiency).

For this question, we will implement some library functions in Scala, our meta language, that we can imagine will be part of the run-time for our object language interpreter. In actuality, the main purpose of this exercise is to warm-up with Scala.

(a) Write a function abs

**def **** **abs(n: Double): Double

that returns the absolute value of n. This a function that takes a value of type Double and returns a value of type Double. This function corresponds to the JavaScript library function Math.abs.

**I****nst****r****uctor**** ****Solution**: 1 line. (b) Write a function xor

^{def }** **^{xor(a:} ^{Boolean,} ^{b:} ^{Boolean):} ^{Boolean}

that returns the exclusive-or of a and b. The exclusive-or returns **t****r****ue **if and only if exactly one of a or b is **t****r****ue**. For practice, do not use the Boolean operators. Instead, only use the **if**–**else**** **expression and the Boolean literals (i.e., **t****r****ue**** **or **fals****e**).

**I****nst****r****uctor**** ****Solution**: 4 lines (including 1 line for a closing brace).

4. **R****un-****T****ime**** ****Libra****ry****:**** ****R****ec****u****rsion**.

(a) Write a recursive function repeat

**def **** **repeat(s: String, n: Int): String

where repeat(s, n) returns a string with n copies of s concatenated together. For example, repeat(“a”,3) returns “aaa“. This function corresponds to the function goog.string.repeat in the Google Closure library.

**I****nst****r****uctor**** ****Solution**: 4 lines (including 1 line for a closing brace).

(b) In this exercise, we will implement the square root function—Math.sqrt in the JavaScript standard library. To do so, we will use Newton’s method (also known as Newton–Raphson).

Recall from Calculus that a root of a differentiable function can be iteratively approx- imated by following tangent lines. More precisely, let *f ** *be a differentialable function, and let *x*_{0 } be an initial guess for a root of *f** *. Then, Newton’s method specifies a se- quence of approximations *x*_{0} , *x*_{1} , . . . with the following recursive equation:^{1}

_{f}* *_{(}_{x}_{n}* *_{)}

*n*

^{x}^{n}^{+}^{1} ^{=} ^{x}^{n}* *^{−} _{f}* *^{0} _{(}_{x }* *_{)} ^{.}

_{The} _{squa}_{r}_{e} _{r}_{oot} _{of} _{a} _{r}_{eal} _{number} _{c}* *_{for} _{c}* *_{>} _{0,} _{w}_{r}_{itten} ^{p}_{c}* *_{,} _{is} _{a} _{positi}_{v}_{e} _{x}* *_{such} _{that} _{x}* *^{2} _{=} _{c}* *_{.}

Thus, to compute the square root of a number *c** *, we want to find the positive root of the function:

_{f}* *_{(}_{x}* *_{)} _{=} _{x}* *^{2} _{−} _{c}* *_{.}

_{Thu}_{s}_{, the} _{foll}_{o}_{wing} _{r}_{ecursi}_{v}_{e} _{equation} _{defines} _{a} _{sequence} _{of} _{app}_{r}_{o}_{ximations} _{for} ^{p}_{c}* *_{:}

__n__

__ ___{x}* *^{2}__ ___{−}__ ___{c}

^{x}_{n}_{+}_{1} ^{=} ^{x}_{n}* *^{−}

i. First, implement a function sqrtStep

_{.}

^{2}^{x}_{n}

**def **** **sqrtStep(c: Double, xn: Double): Double

^{1} The following link is a refresher video on this algorithm: http://www.youtube.com/watch?v=1uN8cBGVpfs, January 2012

that takes one step of approximation in computing ^{p}*c** *(i.e., computes *x*_{n}

*x*_{n}* *).

**I****nst****r****uctor**** ****Solution**: 1 line.

ii. Next, implement a function sqrtN

**def **** **sqrtN(c: Double, x0: Double, n: Int): Double

_{+}_{1} from

that computes the *n*th approximation *x*_{n}* *from an initial guess *x*_{0} . You will want to call sqrtStep implemented in the previous part.

Challenge yourself to implement this function using recursion and no mutable variables (i.e., **v****ar**s)—you will want to use a recursive helper function. It is also quite informative to compare your recursive solution with one using a **while**** **loop. **I****nst****r****uctor**** ****Solution**: 7 lines (including 2 lines for closing braces and 1 line for a require).

iii. Now, implement a function sqrtErr

**def **** **sqrtErr(c: Double, x0: Double, epsilon: Double): Double

that is very similar to sqrtN but instead computes approximations *x*_{n }* *until the approximation error is within *ε** *(epsilon), that is,

*n*

|*x** *^{2} − *c** *| < *ε** *.

You can use your absolute value function abs implemented in a previous part. A wrapper function sqrt is given in the template that simply calls sqrtErr with a choice of x0 and epsilon.

Again, challenge yourself to implement this function using recursion and compare your recursive solution to one with a **while**** **loop.

**I****nst****r****uctor**** ****Solution**: 5 lines (including 1 line for a closing brace and 1 line for a

require).

5. **D****ata**** ****S****t****r****uctu****r****es**** ****R****evie****w****:**** ****B****ina****r****y**** ****Sea****r****ch**** ****T****r****ee****s**.

In this question, we will review implementing operations on binary search trees from Data Structures. Balanced binary search trees are common in standard libraries to implement collections, such as sets or maps. For example, the Google Closure library for JavaScript has goog.structs.AvlTree. For simplicity, we will not worry about balancing in this question.

Trees are important structures in developing interpreters, so this question is also critical practice in implementing tree manipulations.

A binary search tree is a binary tree that satisfies an ordering invariant. Let *n** *be any node in a binary search tree whose data value is *d** *, left child is *l** *, and right child is *r** *. The ordering invariant is that all of the data values in the subtree rooted at *l** *must be < *d** *, and all of the data values in the subtree rooted at *r** *must be ≥ *d** *.

We will represent a binary trees containing integer data using the following Scala **case**** ****c****la****ss**es and **case**** ****obj****e****ct**s:

**sealed **** ****abstract**** ****class **** **IntTree

**case **** ****object **** **Empty **extends **** **IntTree

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

A IntTree is either Empty or a Node with left child l, data value d, and right child r. For this question, we will implement the following four functions.

(a) The function repOk

**def **** **repOk(t: IntTree): Boolean

checks that an instance of IntTree is valid binary search tree. In other words, it checks using a traversal of the tree the ordering invariant. This function is useful for testing your implementation. A skeleton of this function has been provided for you in the template.

**I****nst****r****uctor**** ****Solution**: 7 lines (including 2 lines for closing braces). (b) The function insert

^{def }** **^{insert(t:} ^{IntTree,} ^{n:} ^{Int):} ^{IntTree}

inserts an integer into the binary search tree. Observe that the return type of insert is a IntTree. This choice suggests a functional style where we construct and return a new output tree that is the input tree t with the additional integer n as opposed to destructively updating the input tree.

**I****nst****r****uctor**** ****Solution**: 4 lines (including 1 line for a closing brace). (c) The function deleteMin

^{def }** **^{deleteMin(t:} ^{IntTree):} ^{(IntTree,} ^{Int)}

deletes the smallest data element in the search tree (i.e., the leftmost node). It returns both the updated tree and the data value of the deleted node. This function is intended as a helper function for the delete function. Most of this function is provided in the template.

**I****nst****r****uctor**** ****Solution**: 9 lines (including 2 lines for closing braces and 1 line for a require). (d) The function delete

**def **** **delete(t: IntTree, n: Int): IntTree

removes the first node with data value equal to n. This function is trickier than insert because what should be done depends on whether the node to be deleted has children or not. We advise that you take advantage of pattern matching to organize the cases.

**I****nst****r****uctor**** ****Solution**: 10 lines (including 2 lines for closing braces).

6. **J****a****v****a****Sc****r****i****pty**** ****I****n****t****erp****r****e****te****r****:**** ****N****umb****e****rs**.

JavaScript is a complex language and thus difficult to build an interpreter for it all at once. In this course, we will make some simplifications. We consider subsets of JavaScript and incrementally examine more and more complex subsets during the course of the semester. For clarity, let us call the language that we implement in this course JAVA SC R I P T Y.

For the moment, let us define JAVA SC R I P T Y to be a proper subset of JavaScript. That is, we may choose to omit complex behavior in JavaScript, but we want any programs that we admit in JAVA SC R I P T Y to behave in the same way as in JavaScript.

**sealed **** ****abstract**** ****class **** **Expr

**case **** ****class **** **N(n: Double) **extends **** **Expr

N(*n*) *n*

**case **** ****class **** **Unary(uop: Uop, e1: Expr) **extends **** **Expr

Unary(*uop*,*e*_{1} ) *uop** **e*_{1}

**case **** ****class **** **Binary(bop: Bop, e1: Expr, e2: Expr) **extends **** **Expr

Binary(*bop*, *e*_{1} ) *e*_{1} *bop** **e*_{2}

**sealed **** ****abstract**** ****class **** **Uop

**case **** ****object **** **Neg **extends **** **Uop

Neg −

**sealed **** ****abstract**** ****class **** **Bop

**case **** ****object **** **Plus **extends **** **Bop

Plus +

**case **** ****object **** **Minus **extends **** **Bop

Minus −

**case **** ****object **** **Times **extends **** **Bop

Times ∗

**case **** ****object **** **Div **extends **** **Bop

Div /

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

In actuality, there is not one language called JavaScript but a set of closely related languages that may have slightly different semantics. In deciding how a JAVA SC R I P T Y program should behave, we will consult a reference implementation that we fix to be Google’s V8 JavaScript Engine. We will run V8 via Node.js, and thus, we will often need to write little test JavaScript programs and run it through Node.js to see how the test should behave.

In this lab, we consider an arithmetic sub-language of JavaScript (i.e., an extremely basic calculator). The first thing we have to consider is how to represent a JAVA SC R I P T Y *p**r**og**r**am **as** **data ** *in Scala, that is, we need to be able to represent a program in our object/source language JAVA SC R I P T Y as data in our meta/implementation language Scala.

To a JAVA SC R I P T Y programmer, a JAVA SC R I P T Y program is a text file—a string of charac- ters. Such a representation is quite cumbersome to work with as a language implementer. Instead, language implementations typically work with trees called *abst**r**act** **syntax** **t**r**ees *(ASTs). What strings are considered JAVA SC R I P T Y programs is called the *conc**r**ete** **syntax** *of JAVA SC R I P T Y, while the trees (or *term**s*) that are JAVA SC R I P T Y programs is called the *abst**r**a**c**t **synatx** *of JAVA SC R I P T Y. The process of converting a program in concrete syntax (i.e., as a string) to a program in abstract syntax (i.e., as a tree) is called *parsi**ng*.

For this lab, a parser is provided for you that reads in a JAVA SC R I P T Y program-as-a-string and converts into an abstract syntax tree. We will represent abstract syntax trees in Scala using **case**** ****class**es and **case**** ****object**s. The correspondence between the concrete syntax and the abstract syntax representation is shown in Figure 1.

(a)

**I****nterp****r****eter**** ****1. **** **Implement the eval function

**def **** **eval(e: Expr): Double

that evaluates a JAVA SC R I P T Y expression e to the Scala double-precision floating point number corresponding to the *v**alue ** *of e.

Consider a JAVA SC R I P T Y program *e** *; imagine *e** *stands for the concrete syntax or text of the JAVA SC R I P T Y program. This text is parsed into a JAVA SC R I P T Y AST e, that is, a Scala value of type Expr. Then, the result of eval is a Scala number of type Double and should match the interpretation of *e** *as a JavaScript expression. These distinctions can be subtle but learning to distinguish between them will go a long way in making sense of programming languages.

At this point, you have implemented your first language interpreter!