Test 3 Solutions

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]

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

a.	Scala
b.	Pascal
c.	COBOL
d.	Fortran
e.	Lisp

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

}

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

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

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`

Problem 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) }

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

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

1 4 nil
3 5

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

Test 3 Solutions

Problem X3.1.

Problem X3.2.

Problem X3.3.

Problem X3.4.

Problem X3.5.

Problem X3.6.

Problem X3.7.

Problem X3.8.

Problem X3.9.

Problem X3.10.

Problem X3.11.