Lab Assignment #1 Solution

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

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.

Submission Instructions. Heres 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 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. 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 Basics: Binding 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 val pi = 3.14

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

3 val 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 val x = 3

2 def f(x: Int): Int =

3 x match {

4 case 0 => 0

5 case x => {

6 val y = x + 1

7 ({

8 val x = y + 1

9 y

10 } * f(x 1))

11 }

12 }

13 val 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 Basics: Typing. 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 val (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

e1 : τ1 because

. . .

e2 : τ2 because

. . .

where e1 and e2 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. Run-Time Library. 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.

Instructor 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 true if and only if exactly one of a or b is true. For practice, do not use the Boolean operators. Instead, only use the ifelse expression and the Boolean literals (i.e., true or false).

Instructor Solution: 4 lines (including 1 line for a closing brace).

4. Run-Time Library: Recursion.

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

Instructor 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 Newtons method (also known as NewtonRaphson).

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 x0 be an initial guess for a root of f . Then, Newtons method specifies a se- quence of approximations x0 , x1 , . . . with the following recursive equation:1

f (xn )

n

xn+1 = xn f 0 (x ) .

The square root of a real number c for c > 0, written pc , is a positive 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 .

Thus, the following recursive equation defines a sequence of approximations for pc :

n

x 2 c

xn+1 = xn

i. First, implement a function sqrtStep

.

2xn

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 pc (i.e., computes xn

xn ).

Instructor Solution: 1 line.

ii. Next, implement a function sqrtN

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

+1 from

that computes the nth approximation xn from an initial guess x0 . 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., vars)—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. Instructor 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 xn 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.

Instructor Solution: 5 lines (including 1 line for a closing brace and 1 line for a

require).

5. Data Structures Review: Binary Search Trees.

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 classes and case objects:

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.

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

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

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

Instructor Solution: 10 lines (including 2 lines for closing braces).

6. JavaScripty Interpreter: Numbers.

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,e1 ) uop e1

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

Binary(bop, e1 ) e1 bop e2

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 Googles 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 program 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 abstract syntax trees (ASTs). What strings are considered JAVA SC R I P T Y programs is called the concrete syntax of JAVA SC R I P T Y, while the trees (or terms) that are JAVA SC R I P T Y programs is called the abstract 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 parsing.

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 classes and case objects. The correspondence between the concrete syntax and the abstract syntax representation is shown in Figure 1.

(a)

Interpreter 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 value 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!