*printable version*

# Final Solutions

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21]

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21]

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

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

[8 pts]
*Without using any identifiers to represent parameters*,
write a Haskell function

that finds the sum of squares of numbers in a list:
`sumSquares`

should return 50 (from 3² + 4² + 5²).
Recall that Haskell has a built-in function `sumSquares` [`3`, `4`, `5`]

that
returns the sum of the numbers in a list, and that it includes
the exponentiation operator `sum``**`

.

`sumSquares` **=** `sum` . `map` (** `2`)

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

`Ord a` **=>** [`a`] **->** `a`

[8 pts]
*Without using recursion* but feeling free to use Haskell's
built-in functions such as

and `foldl`

,
write a Haskell function `zipWith`

that takes a list of two-tuples representing points and returns
the total distance from each point to the next.
For example, `pathLength`

should
return 9, from adding 5 and 4, the distance from (0,0) to
(3,4) and then from (3,4) to (3,0).`pathLength` [(`0`,`0`), (`3`,`4`), (`3`,`0`)]

`pathLength pts` **=** `sum` (`zipWith segLength pts` (`tail pts`))

**where** `segLength` (`x0`, `y0`) (`x1`, `y1`) **=** ((`x0` - `x1`) ** `2` + (`y0` - `y1`) ** `2`) ** `0`.`5`

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

(λ`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

(λ

((λ

(λ

4 + ((λ

4 + (4 + ((λ

4 + (4 + (2 ⋅ 3)) = 4 + (4 + 6) = 4 + 10 = 14

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

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.

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

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.

[6 pts] What loop invariant allows you to prove the postcondition for the following?

{`k` = `n` * `n`;

`i` = `0`;

**while** (`i` != `n`) {

`k` = `k` - `2` * `i` - `1`;

`i` = `i` + `1`;

}

{

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

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

, leading to the following
equivalent fragment.`3` * `i`

**for** (`i` = `0`, `i3` = `0`; `i` < `n`; `i`++, `i3` += `3`) {

`scores`[`i3`] = `i`;

}

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

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

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.**struct**

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.

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

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

[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

`9`

3

7

2

4

8

[4 pts]
In Smalltalk, what is the value of
“

”?`2` + `3` * `4` `negated`

−20

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

`[2;5;13;34]`

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

TODO

[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

}

`47 41`

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

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.

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

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

[8 pts]
ALGOL 68 uses both `:=`

and

for assignment statements: both
“**=**

” and “`x` := `3`

” are valid ways to assign
the value 3 to `x` **=** `3`

. What distinguishes them?`x`

The

operator is used for initializing constants' values,
whereas **=**`:=`

changes the value within a reference.

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

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

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

Erlang and OCaml (with partial credit for APL)