Drill 6 Solutions

Consider this program. Match each piece of data to its location relative to entry's starting rsp, assuming we have not implemented tail call optimization.
```
(define (add3 x y z) (+ x (+ y z)))

(print (add3 1 2 3))
```
a. add3's return address:
- ( ) rsp - 0
- ( ) rsp - 8
- (X) rsp - 16
- ( ) rsp - 24
- ( ) rsp - 32
- ( ) rsp - 40
- ( ) rsp - 48
b. z:
- ( ) rsp - 0
- ( ) rsp - 8
- ( ) rsp - 16
- ( ) rsp - 24
- ( ) rsp - 32
- (X) rsp - 40
- ( ) rsp - 48
c. y:
- ( ) rsp - 0
- ( ) rsp - 8
- ( ) rsp - 16
- ( ) rsp - 24
- (X) rsp - 32
- ( ) rsp - 40
- ( ) rsp - 48
d. x:
- ( ) rsp - 0
- ( ) rsp - 8
- ( ) rsp - 16
- (X) rsp - 24
- ( ) rsp - 32
- ( ) rsp - 40
- ( ) rsp - 48
e. entry's return address:
- (X) rsp - 0
- ( ) rsp - 8
- ( ) rsp - 16
- ( ) rsp - 24
- ( ) rsp - 32
- ( ) rsp - 40
- ( ) rsp - 48
For the program above, match each piece of data to its location relative to add3's starting rsp.

a. x:
- ( ) rsp - 0
- (X) rsp - 8
- ( ) rsp - 16
- ( ) rsp - 24
- ( ) rsp - 32
- ( ) rsp - 40
- ( ) rsp - 48
b. y:
- ( ) rsp - 0
- ( ) rsp - 8
- (X) rsp - 16
- ( ) rsp - 24
- ( ) rsp - 32
- ( ) rsp - 40
- ( ) rsp - 48
c. z:
- ( ) rsp - 0
- ( ) rsp - 8
- ( ) rsp - 16
- (X) rsp - 24
- ( ) rsp - 32
- ( ) rsp - 40
- ( ) rsp - 48
d. add3's return address:
- (X) rsp - 0
- ( ) rsp - 8
- ( ) rsp - 16
- ( ) rsp - 24
- ( ) rsp - 32
- ( ) rsp - 40
- ( ) rsp - 48

Here's a program written in our language. Which of the function calls are in tail position?

(define (fib1 n)
(if (< n 2) n
    (+
    (fib1 (sub1 n)) ;; call 1
    (fib1 (- n 2)))) ;; call 2

(define (fib-helper x y n g)
(if (= n g) y
    (fib-helper y (+ x y) (add1 n) g))) ;; call 3

(define (fib2 n)
(if (< n 2) n
    (fib-helper 0 1 1 n))) ;; call 4

(define (mul x y)
(if (< x 0)
    (mul (- 0 x) (- 0 y)) ;; call 5
    (if (zero? x) 0
    (+ y (mul (sub1 x) y)))) ;; call 6

(define (mul-helper x y acc)
(if (zero? x) acc
    (mul-helper (sub1 x) y (+ y acc)))) ;; call 7

(define (* x y)
(if (< x 0)
    (mul-helper (- 0 x) (- 0 y) 0) ;; call 8
    (mul-helper x y 0))) ;; call 9

(define (fac1 n)
(if (= n 0) 1
    (* n (fac1 (sub1 n))))) ;; call 10

(define (fac-helper acc n g)
(if (< g n) acc
    (fac-helper (* n acc) (add1 n) g))) ;; call 11

(define (fac2 n)
(fac1-helper 1 1 n)) ;; call 12

call 1
call 2
call 3
call 4
call 5
call 6
call 7
call 8
call 9
call 10
call 11
call 12

rip is a register that contains a pointer to the current instruction being executed. That is, for example: when the processor executes mov rax, 4, this machine code instruction is stored at some memory address 0b101010100, and rip contains this address. When that execution is done rip is incremented to point to the next instruction.

Which of the following sequences of assembly instructions is equivalent to the single instruction "call read_num"?
- ( ) jmp read_num; sub rsp, 8; mov [rsp + 0], rip
- (X) sub rsp, 8; mov [rsp + 0], rip; jmp read_num
- ( ) mov [rsp + 0], rip; sub rsp, 8; jmp read_num
- ( ) jmp read_num; mov [rsp + 0], rip; sub rsp, 8