Final Solutions: Questions
[8 pts] Define the term purely functional language. That is, what property must a language have to be called purely functional?
[8 pts]
Without using any identifiers to represent parameters,
write a Haskell function
sumSquares that finds the sum of squares of numbers in a list:
sumSquares [3, 4, 5] should return 50 (from 3² + 4² + 5²).
Recall that Haskell has a built-in function sum that
returns the sum of the numbers in a list, and that it includes
the exponentiation operator **.
[6 pts] What is the most general type for the following Haskell function?
f [x] = x
f (x : y : rest) = f ((if x < y then x else y) : rest)
[8 pts]
Without using recursion but feeling free to use Haskell's
built-in functions such as foldl and zipWith,
write a Haskell function pathLength
that takes a list of two-tuples representing points and returns
the total distance from each point to the next.
For example, pathLength [(0,0), (3,4), (3,0)] should
return 9, from adding 5 and 4, the distance from (0,0) to
(3,4) and then from (3,4) to (3,0).
[8 pts] Using normal (lazy) evaluation order, reduce the following lambda expression to irreducible form, showing every intermediate step.
(λx.λy.x (x y)) ((λm.λn.m + n) 4) ((λz.2 ⋅ z) 3)[8 pts] For imperative languages such as Java or Python, why is lazy evaluation order essentially not an option for most computation?
[10 pts] Explain what tail recursion is, with an example, and explain why tail-recursive functions are desirable in Haskell programs.
[6 pts] What loop invariant allows you to prove the postcondition for the following?
{ n ≥ 1 }k = n * n;
i = 0;
while (i != n) {
k = k - 2 * i - 1;
i = i + 1;
}
{ k = 0 }
[8 pts] Give a code example illustrating the optimization technique of strength reduction. Your example should include fragments representing before and after the optimization is applied; the fragments may be in C, Java, Python, or ARM assembly language.
[8 pts] JavaScript programs create objects without designating them as members of a particular class. Nonetheless, some JavaScript interpreters go to quite a bit of effort to “discover” which class a variable belongs to through the notion of hidden classes. How does spending this effort at runtime to discover a class help with improving runtime performance?
[8 pts]
In Prolog, write a predicate largest3(A, B, C, X) that applies
when X is the largest of A, B, and C.
For instance, given largest3(3, 8, 5, X), the only possible
solution is X = 8.
[8 pts]
What is a possible output of the following Scala program?
import scala.actors._
val self = Actor.self
val computers:Array[Actor] = Array(self, self, self, self, self, self)
for (i <- 1 until 6) {
computers(i) = Actor.actor {
while(true) {
Actor.receive {
case j:Int =>
if (i < 3) {
computers(2 * i) ! (j * 3) % 10
computers(2 * i + 1) ! (j * 7) % 10
} else {
println(j);
}
}
}
}
}
computers(1) ! 7
computers(1) ! 2
[4 pts]
In Smalltalk, what is the value of
“2 + 3 * 4 negated”?
[6 pts]
Given the below OCaml function definition, what is the value of
exec [2;3;5;8;13;21;34]?
let rec exec lst = match lst with
| ([] | [_]) as I -> I
| h :: _ :: t -> h :: exec t;;
[8 pts] What perceived deficiencies of JavaScript motivate Google to introduce Dart as an alternative?
[6 pts]
What is returned by s(6, 7) based on the following Go
function definition?
func s(x, y float64) (a, b float64) {
a = x * y + 5
b = x + 5 * y
return
}
[6 pts] One potential downside to a locking-based systems is convoying. Explain the circumstance under which this is a problem.
[8 pts] List two features found in D that are not in C.
[8 pts]
ALGOL 68 uses both := and = for assignment statements: both
“x := 3” and “x = 3” are valid ways to assign
the value 3 to x. What distinguishes them?
[6 pts]
If n holds the vector [2, 3, 5, 7],
what is the value of the APL expression
11ר2↓n?
Explain your answer.
[4 pts] Of the ten languages presented by students (ALGOL, APL, D, Dart, Erlang, Go, Lua, OCaml, Scala, Smalltalk), which two are closest to the functional paradigm as demonstrated by Haskell?
Final Solutions: Solutions
A purely functional language must not have any constructs that change the state of the computer.
sumSquares = sum . map (** 2)
Ord a => [a] -> a
pathLength pts = sum (zipWith segLength pts (tail pts))
where segLength (x0, y0) (x1, y1) = ((x0 - x1) ** 2 + (y0 - y1) ** 2) ** 0.5
(λy.((λm.λn.m + n) 4) (((λm.λn.m + n) 4) y)) ((λz.2 ⋅ z) 3)
((λm.λn.m + n) 4) (((λm.λn.m + n) 4) ((λz.2 ⋅ z) 3))
(λn.4 + n) ((λn.4 + n) ((λz.2 ⋅ z) 3))
4 + ((λn.4 + n) ((λz.2 ⋅ z) 3))
4 + (4 + ((λz.2 ⋅ z) 3))
4 + (4 + (2 ⋅ 3)) = 4 + (4 + 6) = 4 + 10 = 14
Lazy evaluation renders it difficult to predict when a function call will actually be evaluated. Consider code like f(g(x)). In a lazy-evaluation language, g(x) will not actually be computed until f requires its parameter value. If f and g both have side effects (like displaying to the screen or changing some memory), then you could have some side effects of f occurring before the side effects of g and some after. Being able to understand the order in which side effects occur is essential to imperative programming.
Tail recursion is recursion where the recursive call is the absolute last element of the computation. In this case, a compiler can automatically convert the function definition into one using iteration instead, resulting in faster code while also reducing the possibility of overflowing the stack. This is particularly significant for Haskell, where the language encourages even the simplest iterations to be done with recursion, so the gain of a compiler eliminating tail recursion is quite large.
Suppose we start with this fragment:
for (i = 0; i < n; i++) {
scores[3 * i] = i;
}
Strength reduction would insert a new variable that is
maintained to match 3 * i, leading to the following
equivalent fragment.
for (i = 0, i3 = 0; i < n; i++, i3 += 3) {
scores[i3] = i;
}
A class can describe how each individual object
is laid out in memory. Thus, rather than have each object be a
hash table mapping names to values, the interpreter can lay the
object out as a struct with fields at fixed offsets.
Since hash tables take significantly more memory than a struct,
we can save a lot of memory by having just the one hash table as
part of the hidden class shared by many objects.
Also, it means that we can conceivably improved speed: In a loop iterating through several objects accessing the same field or method, the interpreter can determine the offset of the information for each object just once and then quickly retrieve the information at that offset for every object in the loop.
largest3(A, B, C, A) :- A >= B, A >= C.
largest3(A, B, C, B) :- B >= A, B >= C.
largest3(A, B, C, C) :- C >= A, C >= B.
9
3
7
2
4
8
[2;5;13;34]
47 41
If multiple threads happen to obtain and release a similar sequence of locks, the slowest of the threads will end up holding back several threads behind it even though the others could perhaps work much more quickly through the sequence.
Some notable features of D are garbage collection, templates, pure functions, type inferrence, array bounds checking.
The = operator is used for initializing constants' values,
whereas := changes the value within a reference.
The vector [55, 77]. The expression first drops the first two
elements from n, resulting in [5, 7].
It then multiplies 11 by each element of the list,
leading to [55, 77].
Erlang and OCaml (with partial credit for APL)