Recitation 22

Today: Stacks and Recursion in the Register Machine

In recitation 3, we didn't get as far as tail recursion. More next time.
In recitation 4, we finished all this material.

Subroutines

Here's a subroutine that increments a number.

    increment
        (assign sum (op +) (reg sum) (const 1))
        (goto (reg continue))

Note new goto form: indirect jump.
-- look up a label in register
-- then jump to it

How do you use the subroutine? For example, if you'd written the
instruction

(inc sum)

with the expectation that it would increment the contents of the
sum register, but then discovered that there was no inc instruction,
what would you write instead?

        (assign continue (label after-call))
        (goto (label increment))
    after-call

Key ideas:

1. need to put number to be incremented in sum register
2. need to put return address in register continue

Sample use, increments twice from 0:

        (assign sum (const 0))
        (assign continue (label after-call-1))
        (goto (label increment))
    after-call-1
        (assign continue (label after-call-2))
        (goto (label increment))
    after-call-2

Contracts

What did we need to know about the subroutine?
-- where args and return values go
-- where return label goes

A more subtle point
-- subroutine may use registers that caller has values in
-- no notion of "local variables"!
-- so must also know which registers may be damaged
-- will see can avoid writing registers by using stack

Consider a subroutine for multiplication:

    mul
        (assign result (const 0))
      start
        (test (op =) (reg y) (const 0))
        (branch (reg continue))
        (assign result (op +) (reg result) (reg x))
        (assign y (op -) (reg y) (const 1))
        (goto (label start))

This does something potentially bad:
-- changes the value of y

So caller must save the register y if it plans to use
the value again.

By the way, we've been happily picking names for registers as if there was an unbounded
number of them. In practice, there's a small finite number, so registers have
to be reused. A compiler takes symbolic names (such as continue and sum) and
maps them to physical registers (R0, R1, ...).

Stacks

Extend machine with stack. Unlike registers, provides (almost) unbounded memory.
Stack is LIFO: last in, first out.

New instructions are:

(save register) take value in register and push it on the stack
(restore register) pop value off stack and put in register

Can put numbers and labels on the stack. We'll do both:
-- numbers to save values of registers inside subroutines
-- labels to remember where to go back to after a subroutine call.

Exercises:

What are the values in each register after ...?

    (assign x (const 0))
    (assign y (const 1))
    (save x)
    (save y)
    (restore x)
    (restore y)

Now consider this:

    (assign x (const 0))
    (assign y (const 1))
    (save x)
    (save y)
    (restore y)
    (restore x)

Note that

(save R)
(restore R)

is a no-op and can be optimized away.

We can use the stack to solve our multiplication problem. We just save the resister
y before the call and restore it after:

Instead of
(assign result (op *) (reg x) (reg y))

we would have
        (save y)
        (assign continue (label after-call))
        (goto (label multiply))
    after-call
        (restore y)

Recursive Subroutine Calls

Start by looking at the behaviour of a recursive procedure such as factorial:

(define (fact n)
(if (= n 1) 1
(* n (fact (- n 1)))))

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 1))
(* 3 2)
6

Where do all the pending computations get stored?
-- on the stack

Let's study the translation of factorial: it's about the simplest recursive procedure
(but its machine language translation is rather verbose!):

(controller
(assign continue (label halt))

fact
        (test (op =) (reg n) (const 1))
        (branch (label b-case))
        (save continue)
        (save n)
        (assign n (op -) (reg n) (const 1))
        (assign continue (label r-done))
        (goto (label fact))

r-done
        (restore n)
        (restore continue)
        (assign val (op *) (reg n) (reg val))
        (goto (reg continue))

b-case
(assign val (const 1))
(goto (reg continue))
halt)

We drew a picture to explain what was going on.

Tail Recursion (Recitation Problem)

Suppose the last thing a procedure does is call increment:

        (assign sum (const 0))
        (save continue)
        (assign continue (label after-call))
        (goto (label increment))
    after-call
        (restore continue)
        (goto continue)
        ...
    increment
        (assign sum (op +) (reg sum) (const 1))
        (goto (reg continue))

What's going on with the continue register?
-- caller saves it on the stack and stores label after-call in it
-- increment returns to label in register continue
-- caller just restores register, and jumps to its label

Result
-- call to increment is RECURSIVE

If we translated like this, an iterative procedure such as

(define (f x)
(if (= x 0) 1 (f (- x 1))))

would have recursive behaviour!

To eliminate this problem, we can optimize the code:
-- have increment jump back to the caller's caller
-- replace
        (assign sum (const 0))
        (save continue)
        (assign continue (label after-call))
        (goto (label increment))
    after-call
        (restore continue)
        (goto continue)
by
        (assign sum (const 0))
        (goto (label increment))

Recitation Problem

Instead of being able to do
    (assign val (op *) (reg n) (reg val))
in the middle of fact, assume we have to call a subroutine:
    multiply:
        input: x, y, continue
        output:   val
        writes:   x
        stack:   unchanged

Change the code for fact to do this
Do as few additional saves and restores as possible
You are allowed to change the contract for fact if you want to
Hint: use the tail-call optimization

Daniel Jackson
November 19, 1999