recitation 25: the stack, subroutines & recursion

-------------------------------------------------------------------------------
continue register:  (assign continue (label after-call))
  - the "return point"

indirect branch:  (goto (reg continue))
  - can go to different places (e.g. back where we came from)
  - why do we need this to implement subroutines & recursion?

direct branch:  (goto (label done))
  - jumps to fixed location (always the same place)

save & restore:
  - protect values in registers that will be reused, so that 
    deferred operations can be completed after the recursive call.
  - register memory vs stack memory - what's the difference?

stack depth & iterative/recursive processes
  - can determine the stack depth needed for some computation
  - max stack depth = space required (usually)

subroutine contract:
  - what registers hold the input values & the return point
  - what register will hold the output value
  - what other registers will be modified
  - what happens to the stack?

-------------------------------------------------------------------------------
recipe for making a procedure call
  - save the registers you don't want clobbered (including continue)
  - assign values to procedure input registers
  - assign the continue register to the return-label
  - goto the start of the procedure

at procedure call return-label
  - use the output
  - restore the registers (in reverse order)

"calling conventions"

  - the caller must save & restore everything that is important, 
    the caller puts the return address in the continue register, 
    the stack is returned unchanged

  - the callee must save & restore everything that is important, 
    the caller puts the return address on the top of the stack, 
    the return address is removed from the stack (otherwise unchanged).

  - others possible!  (and may be more efficient in some cases)

"call frame"
  - section of the stack which corresponds to a procedure call

-------------------------------------------------------------------------------
tail recursion (iteration)
  - no work after call except (goto (reg continue))
  - don't need to use the stack
  - this is why we can say iterative algorithms use constant space

* can you optimize this code?
     
  ...
  (save continue)
  (assign continue (label after-call))
  (goto (label <some-procedure>))
after-call
  (restore continue)
  (goto (reg continue))
  ...

-------------------------------------------------------------------------------
* run the code below by hand keeping track of the registers & stack
  start with:   program counter = 1,  continue = foo, 
                condition = #t,  n = 3,  val = 0

  (controller
 1   (assign continue (label done))
   loop
 2   (test (op <) (reg n) (const 2))
 3   (branch (label base-case))
 4   (save continue)
 5   (assign continue (label after-1))
 6   (save n)                           
 7   (assign n (op -) (reg n) (const 1))
 8   (goto (label loop))         
   after-1                       
 9   (restore n)
10   (restore continue)
11   (assign n (op -) (reg n) (const 2))
12   (save continue)
13   (assign continue (label after-2))
14   (save val)                  
15   (goto (label loop))
   after-2                       
16   (assign n (reg val))        
17   (restore val)               
18   (restore continue)
19   (assign val (op +) (reg val) (reg n)) 
20   (goto (reg continue))       
   base-case
21   (assign val (reg n))        
22   (goto (reg continue))
   done)

* what does this code compute?  write the contract for this code.

* can you optimize this code?  (sicp ex 5.6)

* do we always restore values into the registers they were saved from?
  what should happen?  can we optimize the code using this?  (sicp ex 5.11)

-------------------------------------------------------------------------------
* write the register machine code and contract for each of the scheme
  procedures below:

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

(define (expt b n)
  (define (expt-iter counter product)
    (if (= counter 0)
        product
        (expt-iter (- counter 1)
                   (* b product))))
  (expt-iter n 1))

-------------------------------------------------------------------------------
* write scheme code & register machine code to do exponentiation by
  successive addition. 

-------------------------------------------------------------------------------