Test 3 Solutions: Questions

X3.1.

[15 pts] In class we've seen snippets of code from APL, BASIC, C, C++, COBOL, Fortran, Haskell, Java, JavaScript, Lisp, Lua, Pascal, Prolog, Python, Ruby, Scala, and Smalltalk. Identify in which language each of the following is written.

a.def fact(n: Int): Int = (1 to n) reduceLeft (_ * _)
b.function fact(n : integer) : integer;
var
    i, r: integer;
begin
    r := 1;
    for i := 1 to n do
        r := r * i;
    fact := r
end;
c.MOVE 1 TO FACT
PERFORM VARYING I FROM 1 BY 1 UNTIL I = N
  MULTIPLY I BY FACT
END-PERFORM
d.   INTEGER FUNCTION FACT(N)
   K = 1
   DO 10 I = 1, N
   K = K * I
10 CONTINUE
   FACT = K
   RETURN
   END
e.(defun fact (n) (if (= n 1) 1 (* n (fact (- n 1)))))
X3.2.

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

(λf.λy.f (y + 1)) (λz.z²) ((λx.x + x) 3)
X3.3.

[10 pts] Using recursive descent parsing, write a Haskell function matchS of type IO Int that reads successive characters from the input using getChar and results in −1 if the input does not match the grammar S → ‘(’ S ‘)’ S | ‘1’ and otherwise results in the number of 1's in the input. For instance, given the input “((1)1)1”, the function should result in 3 wrapped in an IO monad; but the result should be −1 given the input “((1)1(1”.

X3.4.

[8 pts] Rewrite the following C code into equivalent C code illustrating strength reduction. Explain your answer.

for (i = 0; i < n; i++) {
    a[7 * i] = 7 * n;
}
X3.5.

[8 pts] Explain what function inlining is and how this compiler optimization improves runtime performance of a program.

X3.6.

[10 pts] In ARM assembly language, each arithmetic instruction changes the first-listed register to a value computed based on the following one or two arguments.

MOV R0, #1
ADD R1, R0, R0
MUL R2, R0, R1
ORR R3, R1, R2
SUB R4, R0, R2
AND R1, R3, R4

a. Draw an interference graph indicating conflicts between registers.

b. Rewrite the ARM assembly code using three registers, and explain how it is derived from the interference graph.

X3.7.

[8 pts] Explain the notion of just-in-time compilation as it relates to JavaScript interpreters.

X3.8.

[10 pts] Using only the comparison operators and basic pattern matching, define a Prolog predicate max(L, M) that applies whenever M is the maximum element in the list L of integers. For example, max([4, 6, 3], M) should lead to discovering the value 6 for M.

X3.9.

[8 pts] Define what Prolog's cut operator (!) does.

X3.10.

[8 pts] Explain what happens when the following Scala program is executed, including a description of how actors send messages between each other.

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 {
        var k: Int = (i * 7) % 10
        if (i < 3) {
            Actor.receive { case j: Int => k = k + j }
            Actor.receive { case j: Int => k = k + j }
        }
        computers(i / 2) ! k
    }
}
Actor.receive { case j: Int => println(j) }
X3.11.

[8 pts] What is the output of the following Lua code fragment? (When no value is associated with a key, the Lua interpreter returns nil.)

a = { x = 1, z = 2 }
b = { x = 3, y = 4 }
setmetatable(a, { __index = b })
b.x = 5
print(a.x, a.y, b.z)
a.x = nil  -- deletes the key "x" from "a"
b.y = 6
print(a.x, a.y)

Test 3 Solutions: Solutions

X3.1.
a.Scala
b.Pascal
c.COBOL
d.Fortran
e.Lisp
X3.2.
(λf.λy.f (y + 1)) (λz.z²) ((λx.x + x) 3) ⇒ (λy.(λz.z²) (y + 1)) ((λx.x + x) 3)
⇒ (λz.z²) (((λx.x + x) 3) + 1)
⇒ (((λx.x + x) 3) + 1)²
⇒ ((3 + 3) + 1)²
⇒ (6 + 1)²
⇒ 7²
⇒ 49
X3.3.
matchS =
    do  c <- getChar
        if c == '(' then
            do  sub0 <- matchS
                if sub0 < 0 then
                    return (-1)
                else
                    do  c <- getChar
                        if c == ')' then
                            do  sub1 <- matchS
                                return (if sub1 < 0 then -1 else sub0 + sub1)
                        else
                            return (-1)
        else if c == '1' then
            return 1
        else
            return (-1)
X3.4.

Rather than multiply each i by 7, the compiler introduces a new variable i7 and maintains the invariant that i7 is always 7 * i: When i is increased by 1, i7 increases by 7. In this way, we can replace a multiplication in each iteration with an addition instead.

for (i = 0, i7 = 0; i < n; i++, i7 += 7) {
    a[i7] = 7 * n;
}

(The other multiplication “7 * i” can be removed through common subexpression elimination, but this is an entirely different type of optimization.)

X3.5.

Given a code fragment C including a function F, a compiler would typically generate assembly code to enter into a subroutine corresponding to F. With function inlining, the compiler considers integrating F's body directly into the code generated for C, thus removing the overhead related to subroutine entry/exit.

For example, given the following pair of C function definitions, below is the straightforward translation of dist followed by a version that illustrates function inlining.

int sq(x) {
  return x * x;
}

int dist(x, y) {
  return sq(x - y);
} 		dist SUB R0, R0, R1
     STMDB SP!, {LR}
     BL sq
     LDMIA SP!, {PC}
sq   MUL R0, R0, R0
     MOV PC, LR 		dist SUB R0, R0, R1
     MUL R0, R0, R0
     MOV PC, LR
X3.6.
a.
a.

One possible coloring is to assign one color to R0; to assign the second color to both R1's and R3; and to assign the third color to R2 and R4. In rewriting the program, we'll use R0 for the first color, R1 for the second, and R2 for the third.

MOV R0, #1
ADD R1, R0, R0
MUL R2, R0, R1
ORR R1, R1, R2
SUB R2, R0, R2
AND R1, R1, R2
X3.7.

As the interpreter executes the program using its in-memory representation, it discovers which fragments of code are used most heavily, and it spends time translating these fragments to optimized machine language so that subsequent attempts to execute a fragment can be executed directly in machine language rather than through tree traversal.

X3.8.
max([X], X).
max([H | T], H) :- max(T, X), H >= X.
max([H | T], X) :- max(T, X), H < X.
X3.9.

The resolution engine will not backtrack beyond the cut operator: As it binds variables in matching predicates, once it reaches the cut operator it won't change any of those variable bindings it has made by the time it reached the operator.

X3.10.

The five created actors (in indices 1 through 6 of the array) each computer their own initial value for k (1: 7, 2: 4, 3: 1, 4: 8, 5: 5). Actors 3, 4, 5 simply send their numbers to actors 1, 2, and 2 respectively. Actor 2 receives numbers from 4 and 5 (values 8 and 5), adds them into its k (initially 4), and sends the sum (17) to actor 1. Actor 1 receives numbers from 2 and 3 (values 17 and 1), adds them into its k (initially 7), and sends the sum (25) to actor 0. Actor 0 receives this number and displays it, resulting in the output of “25”.

X3.11.
1 4 nil
3 5