# Final Solutions: Questions

Xf.1.

[8 pts] Define the term purely functional language. That is, what property must a language have to be called purely functional?

Xf.2.

[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 `**`.

Xf.3.

[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) ```
Xf.4.

[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).

Xf.5.

[8 pts] Using normal (lazy) evaluation order, reduce the following lambda expression to irreducible form, showing every intermediate step.

xy.x (x y)) ((λmn.m + n) 4) ((λz.2 ⋅ z) 3)
Xf.6.

[8 pts] For imperative languages such as Java or Python, why is lazy evaluation order essentially not an option for most computation?

Xf.7.

[10 pts] Explain what tail recursion is, with an example, and explain why tail-recursive functions are desirable in Haskell programs.

Xf.8.

[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 }
Xf.9.

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

Xf.10.

[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?

Xf.11.

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

Xf.12.

[8 pts] What is a possible output of the following Scala program? `import scala.actors._val self = Actor.selfval 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) ! 7computers(1) ! 2`

Xf.13.

[4 pts] In Smalltalk, what is the value of “`2 + 3 * 4 negated`”?

Xf.14.

[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;;`
Xf.15.

[8 pts] What perceived deficiencies of JavaScript motivate Google to introduce Dart as an alternative?

Xf.16.

[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}`
Xf.17.

[6 pts] One potential downside to a locking-based systems is convoying. Explain the circumstance under which this is a problem.

Xf.18.

[8 pts] List two features found in D that are not in C.

Xf.19.

[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?

Xf.20.

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

Xf.21.

[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

Xf.1.

A purely functional language must not have any constructs that change the state of the computer.

Xf.2.
`sumSquares = sum . map (** 2)`
Xf.3.
`Ord a => [a] -> a`
Xf.4.
```pathLength pts = sum (zipWith segLength pts (tail pts))   where segLength (x0, y0) (x1, y1) = ((x0 - x1) ** 2 + (y0 - y1) ** 2) ** 0.5 ```
Xf.5.
xy.x (x y)) ((λmn.m + n) 4) ((λz.2 ⋅ z) 3)
y.((λmn.m + n) 4) (((λmn.m + n) 4) y)) ((λz.2 ⋅ z) 3)
((λmn.m + n) 4) (((λmn.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
Xf.6.

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.

Xf.7.

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.

Xf.8.
k = n² − i²
Xf.9.

```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; } ```
Xf.10.

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.

Xf.11.
`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.`
Xf.12.
`937248`
Xf.13.
−20
Xf.14.
`[2;5;13;34]`
Xf.15.
TODO
Xf.16.
`47 41`
Xf.17.

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.

Xf.18.

Some notable features of D are garbage collection, templates, pure functions, type inferrence, array bounds checking.

Xf.19.

The `=` operator is used for initializing constants' values, whereas `:=` changes the value within a reference.

Xf.20.

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

Xf.21.

Erlang and OCaml (with partial credit for APL)