CSE 130, Fall 2012 Name/ID Instructor: Ranjit Jhala
Final Exam
Instructions: read these first!
Do not open the exam, turn it over, or look inside until you are told to begin.
Switch off cell phones and other potentially noisy devices.
Write your full name on the line at the top of this page. Do not separate pages.
You may refer to any printed materials, but no computational devices (such as laptops, calculators, phones, iPads, friends, enemies, pets, lovers).
Read questions carefully. Show all work you can in the space provided. Where limits are given, write no more than the amount specified.
The rest will be ignored.
Avoid seeing anyone else’s work or allowing yours to be seen.
Do not communicate with anyone but an exam proctor.
If you have a question, raise your hand.
When time is up, stop writing.
The points for each part are rough indication of the time that part should take.
Run LATEX again to produce the table
CSE 130, Fall 2012 Final Exam Page 1 of ?? 1. [?? points]
In each question below, we have given a Scala function with missing type information. Your job is to
1. fill in appropriate types (so the function will be accepted by the typechecker), 2. write down one set of suitable inputs (i.e. of the corresponding types),
3. write down the output corresponding to the input.
Hint: Recall that syntax for anonymous functions in Scala is (x1,…,xn) => e which is equivalent to Ocaml’s fun (x1,…,xn) -> e
(a) [2 points]
def plus(x: T1, y: T1): T2 = x + y
val out = plus(in1, in2)
T1 =
T2 =
in1 =
in2 =
out =
(b) [5 points]
def plussed(x: T1, y: T2): T3 = x + y(x)
val out = plussed(in1, in2)
T1 =
T2 =
T3 =
CSE 130, Fall 2012 Final Exam Page 2 of ?? in1 =
in2 =
out =
(c) [8 points]
def squash[A](xss: T1): T2 = {
for ( xs <- xss
;x <-xs) yield x
}
val out = squash(in)
T1 =
T2 =
in =
out =
(d) [10 points]
def reduce[A](xs: T1, f: T2): T3 = {
var acc = xs(0)
for (x <- xs.tail) {
acc = f(acc, x)
}
acc }
val out = reduce(in1, in2)
T1 =
CSE 130, Fall 2012
Final Exam
Page 3 of ??
T2 =
T3 =
in1 =
in2 =
out =
CSE 130, Fall 2012 Final Exam Page 4 of ?? (e) [10 points]
def explode[A](xs: T1): T2 = {
if (xs.isEmpty)
List(List())
else {
for ( ys <- explode(xs.tail)
; z <- List(List(), List(xs.head)) )
yield (z ++ ys)
}
}
val out = explode(in)
T1 =
T2 =
in =
out =
CSE 130, Fall 2012 Final Exam Page 5 of ?? 2. [?? points]
“MapReduce is a software framework introduced by Google to support distributed computing on large data sets on clusters of computers.” (From WikiPedia)
This question will give you a flavor of what it is like to program using the MapReduce model, using a simple Scala implementation.
(a) [7 points] Consider the function expand whose type is given at the bottom.
def expand[A, B](f: A => List[B], xs: Iterator[A]): Iterator[B] = {
for ( x <- xs
; y <- f(x) )
yield y
}
What is the value of ans below ?
val clone = (p => (0 until p._2).map(_ => p._1).toList)
val ans = expand(clone, Iterator((“a”, 1), (“b”, 2), (“c”, 3)))
(b) [8 points] Consider the function insert
def insert[K, V](table: Map[K, List[V]], key: K, v: V): Map[K, List[V]] = {
if table.contains(key) {
val vs = table(key)
table += (key -> v::vs)
} else {
table += (key -> List(v))
}
}
What is the value of ans below ?
val t = Map( “judynails” -> List(2)
, “larsumlaut” -> List(2, 2, 9)
, “caseylynch” -> List(3))
val ans = insert(t, “judynails”, 4)
Result:
Result:
CSE 130, Fall 2012 Final Exam Page 6 of ?? (c) [5 points] Consider the function group whose type is given at the bottom.
def group[K, V](kvs: Iterator[(K, V)]): Map[K, List[V]] = {
var table: Map[K, List[V]] = Map()
for ((k, v) <- kvs) {
table = insert(table, k, v)
}
table }
What is the value of ans below ?
val kvs = Iterator( ("judynails" , 3)
, ("larsumlaut", 8)
, ("caseylynch", 19)
, ("caseylynch", 12)
, ("larsumlaut", 7)
, ("judynails" , 6))
val ans = group(kvs)
(d) [10 points] Consider the function collapse whose type is given at the bottom.
def collapse[K, V](table: Map[K, List[V]], f: (V, V) => V): Map[K, V] = {
table.mapValues(reduce(_, f))
}
Hint: The reduce function is from Question 1(d).
Hint: The method ‘mapValues‘ (for Scala HashMaps) behaves as follows:
scala> Map(“one” -> 1, “two” -> 2).mapValues(_ + 100)
res: Map[String, Int] = Map(“one” -> 101, “two” -> 102)
What is the value of ans below ?
let table = Map( “judynails” -> List(9, 3)
, “larsumlaut” -> List(5, 2, 3)
, “caseylynch” -> List(3, 6)
)
val ans = collapse(table, (x, y) => x + y)
Result:
Result:
CSE 130, Fall 2012 Final Exam Page 7 of ?? (e) [10 points] Finally, consider the function mapReduce whose type is given at the bottom.
def mapReduce[E, K, V]( xs : Iterator[E]
, mapper : E => List[(K, V)]
, reducer: (V, V) => V ) : Map[K, V] = {
val kvs = expand(mapper, xs)
val table = group(kvs)
val out = collapse(table, reducer)
out
}
Intuitively, the mapReduce function takes the arguments:
• xs: which is a collection of values of type E, e.g. a collection of documents,
• mapper: which is a function that maps each E value to a list of key-value pairs, kvs of type List[K, V]. • reducer: An accumulation function that takes a “current accumulation” value of type V a “next value” of
type V and returns a new accumulated value of type V (e.g. like fold_left).
First, the mapper function is used to expand the list xs into a giant collection of key-value pairs kvs. Second, the expanded set of key-value pairs is grouped by the key to get table : Map[K, List[V]] Third, the reducer is used to reduce the list of values in each group in the table, and the reduced table out is returned. In the real implementation, each of the three steps of mapReduce is carried out in parallel across several (thousands of!) machines.
Assume that you are given the following:
type Doc // Definition is unimportant
val wwwdocs: Iterator[Doc] // The WWW as a Document collection
def docWords(d: Doc): List[String]
that is, a special type Doc, a collection of all WWW documents, and a function that returns a list of strings corresponding to the words in a given document. Your goal is to compute the frequency with which different words appear in documents on the Web. That is your goal is to compute a table wordCount: Map[String, Int] of the form
Map(w1 -> c1, w2 -> c2, …, wn -> cn)
where ci is the number of times the word wi appears in documents across the Web. Fill in the blanks below to
show how mapReduce. can be used to compute the word frequency table wordCount:
val wordcount = {
val fmap =
val fred =
mapReduce(wwwdocs, fmap, fred)
}
CSE 130, Fall 2012 Final Exam Page 8 of ??
3. [?? points] We will write several Scala functions to do simple manipulation of images represented by type type Image = List[List[Int]]
i.e. lists of lists of integers, with each integer representing a pixel. For example, the following would be a simple image of a smiley face.
val img1 = List( List(11, 0, 12)
, List( 0, 0, 0)
, List(13, 0, 14)
, List(15, 16, 17)) Wecanrefertoeachpixeloftheimagebyitshorizontalxandverticalycoordinate.Thetopleftcorneris(0, 0)and
coordinatesincreasetotherightanddown.Wecanaccesscoordinate(x,y)ofimg: Imageasimg(y)(x)
(a) [5 points] Fill in the body of the function square, which takes an image, and squares each integer in it. For
example,
scala> square(img1)
res: Image = List( List(121, 0, 144)
, List( 0, 0, 0)
, List(169, 0, 196)
, List(225, 256, 289))
Fill in the blanks below to obtain an implementation of square . def square(img: Image) : Image = {
for ( ___ <- ______________________________________ )
yield ____________________________________________
}
(b) [10 points] Next, fill in the body of the function crop, such that crop(img, x1, y1, x2, y2) returns an imagewhichonlycontainsthepixelsfromimgatcoordinates(x,y),wherex1 <= x < x2andy1 <= y < y2. (You can assume that all such coordinates exist in img.) For example,
scala> crop(img1,0,1,2,4)
res: Image = List( List(0, 0)
, List(13, 0)
, List(15, 16)) Fill in the blanks below to obtain an implementation of crop .
def crop(img: Image, x1:Int, y1: Int, x2:Int, y2: Int): Image = {
for ( ___ <- ______________________________________ )
yield ____________________________________________
}
CSE 130, Fall 2012 Final Exam Page 9 of ??
Hint: For a list xs the call xs.slice(lo, hi) returns the sub-list of the lo, lo+1, ..., hi-1-th ele- ments of xs For example,
scala> List(0, 10, 20, 30, 40, 50, 60, 70).slice(2, 6)
res: List[Int] = List(20, 30, 40, 50)
(c) [10 points] Next, let us write a helper function zip. Given lists l1 and l2, zip(l1,l2) returns a list of pairs. The nth element of the returned list is a pair consisting of the nth element of l1 and the nth element of l2. If one of the lists is smaller than the other, the returned list contains pairs only for indices that both lists have. For example,
scala> zip(List(1,2,3), List(4,5,6))
res: List[Int] = List((1, 4), (2, 5), (3, 6))
scala> zip(List(1,2,3), List(4,5))
res: List[Int] = List((1, 4), (2, 5)) Fill in the blanks below to obtain an implementation of zip .
def zip[A](l1: List[A], l2: List[B]): List[(A, B)] = {
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
}
(d) [10 points] Given two images img1 and img2 of the same size, add(img1, img2) returns an image where each pixel is the sum of the corresponding pixels from img1 and img2. For example,
scala> add(img1, img1)
res: Img = List(List(22, 0, 24),
List( 0, 0, 0),
List(26, 0, 28),
List(30, 32, 34))
Fill the implementation of add_imgs below. Hint: You may need another call to zip …
def add(img1: Image, img2: Image): Image = {
for ((r1, r2) <- zip(img1, img2))
yield _____________________________________________________
}
CSE 130, Fall 2012 Final Exam Page 10 of ?? 4. [?? points]
We say that one word is an anagram of another if reordering the letters of the first word results in the second word. Next, we will write a couple of Scala functions that determine if one word is a anagram of another.
Recall! In Scala, a String is in fact a collection of characters. Thus, we can do all the usual “collection-y” things to them, such as:
scala> val xs = “influx”
xs: java.lang.String = influx
scala> (xs(0), xs(1), xs(2))
res1: (Char, Char, Char) = (i,n,f)
scala> xs.head
res2: Char = i
scala> xs.tail
res2: String = nflux
scala> xs.length
res3: Int = 6
scala> xs.sorted
res4: String = filnux
scala> xs.isEmpty
res5: Boolean = false
scala> xs.reverse
res6: String = xulfni
scala> xs.slice(2, 5)
res7: String = flu
(a) [5 points] Fill in the body of the function isAnagram, which takes two Strings and checks if the first one is an anagram of the second.
scala> isAnagram(“influx”, “flunxi”)
res: Boolean = True
scala> isAnagram(“influx”, “flinux”)
res: Boolean = True
scala> isAnagram(“influx”, “XULFNI”)
res: Boolean = False
scala> isAnagram(“influx”, “linux”)
res: Boolean = False
// uppercase is different char
// missing ’f’
CSE 130, Fall 2012 Final Exam Page 11 of ?? Fill in the blanks below to obtain an implementation of isAnagram.
def isAnagram(src: String, dst: String) : Boolean =
(b) [7 points] Next, write a function that takes a word w, a character c and a position i and splices the character into the word at the given position. For example,
scala> spliceCharAt(“influx”, ’z’, 0)
res: String = zinflux
scala> spliceCharAt(“influx”, ’z’, 2)
res: inzflux
scala> spliceCharAt(“influx”, ’z’, 6)
res: influxz
Fill in the blanks below to obtain an implementation of spliceCharAt.
def spliceCharAt(w: String, c: Char, i: Int) : String=
(c) [8 points] Finally, we will write a function that returns an iterator over all the possible anagrams (permutations) generatable from a given String. When you are done, you should see the following behavior:
scala> anagrams(“dog”).toList
res: List[String] = List(dog, odg, ogd, dgo, gdo, god) Fill in the blanks below to obtain an implementation of anagrams.
def anagrams(w: String): Iterator[String] = if ( ) {
} else { for (
}
)
CSE 130, Fall 2012 Final Exam Page 12 of ??
5. [?? points] For this problem, you will write Prolog code that checks whether a given ML expression is well-scoped, that is, that every variable that is used in the expression is bound in the expression. That is, your prolog code will check, just by looking at the code, not by running it, whether or not your nanoML implementation would have thrown a Nano.MLFailure “Variable not bound: …”exception.
First, we shall encode nanoML expressions as Prolog terms via the following grammar.
expr ::=
| const(i)
| var(x)
| plus(expr,expr)
| leq(expr,expr)
| ite(expr,expr)
| letin(var(x),expr,expr) | fun(var(x),expr)
| app(expr,expr)
The table below shows several examples of Ocaml expressions, the Prolog term encoding that expression.
ML Expression
Prolog Expression Term
2
const(2)
x
var(x)
2+3
plus(const(2),const(3))
2 <= 3
leq(const(2),const(3))
fun x -> x <= 4
fun(var(x),leq(var(x),const(4)))
fun x -> fun y ->
if x then y else 0
fun(var(x),fun(var(y),
ite(var(x),var(y),const(0))))
let x = 10 in x
letin(var(x),const(10),var(x))
fun x ->
let y = x in
y+y
fun(var(x),
letin(var(y),var(x)
plus(var(y),var(y))))
(a) [10points] WriteaPrologpredicatereads(E,X)thatistrueifXisreadanywhereinsidetheexpressionE.When you are done, you should get the following behavior:
?- reads(plus(const(2),const(3)), x).
False.
?- reads(letin(var(x),const(1),var(a)), X). X=a
True.
?- reads(fun(var(x),plus(var(a),var(b))), X).
X = a;
X = b; True.
?- reads(fun(var(b),plus(var(a),var(b))), X).
X = a;
X = b; True.
CSE 130, Fall 2012 Final Exam Page 13 of ?? Write your solution by filling in the grid below. Hint: If you need an ”Or”, you may add extra rules where needed,
(or better, just use the ; operator.)
reads(const(I), X) :- 0 = 1. % i.e. false
reads(var(X), Y) :-
reads(plus(E1,E2), X) :-
reads(leq(E1,E2), X) :-
reads(ite(E1,E2,E3), X) :-
reads(letin(var(Y),E1,E2), X) :-
reads(fun(var(Y),E), X) :-
reads(app(E1,E2), X) :-
(b) [15 points] Write a Prolog predicate wellscoped(E) that is true if E is well-scoped, that is, each variable that is read is previously bound. When you are done, you should get the following behavior:
?- wellscoped(plus(var(a),const(3))).
False.
?- wellscoped(letin(var(a),const(1),plus(var(a),const(3)))).
True.
?- wellscoped(fun(var(b),plus(var(a),var(b)))).
False.
?- wellscoped(fun(var(b),fun(var(a), plus(var(a),var(b))))).
True.
?- wellscoped(app(fun(var(a),plus(var(a),const(1))), var(a))).
CSE 130, Fall 2012 Final Exam Page 14 of ?? False.
?- wellscoped(app(fun(var(a),plus(var(a),const(1))),
letin(var(a),const(1), var(a)))).
True.
Todefinewellscoped,writeahelperpredicatehelper(E, Xs)whichistrueifeveryvariablethatisreadin E either occurs in Xs or occurs bound inside E. With this, you can define wellscoped as:
wellscoped(E) :- helper(E, []).
Write your definition for helper by filling in the grid below.
Hint: You need not use reads. You may use the built-in predicate member(X,Ys) which returns true if the atom X appears in the list Ys.
helper(const(I), Xs) :- 0 = 0. % i.e. true
helper(var(X), Xs) :-
helper(plus(E1,E2), Xs) :-
helper(leq(E1,E2), Xs) :-
helper(ite(E1,E2,E3), Xs) :-
helper(letin(var(Y),E1,E2), Xs) :-
helper(fun(var(Y),E), Xs) :-
helper(app(E1,E2), Xs) :-