# Recitation 23

### Today: Tail Recursion and the Explicit Control Evaluator

Ideas
-- Contracts
-- Tail recursion
-- EC evaluator

### Subroutines

Here's a subroutine:

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

Exercise: write its contract
-- note which registers are smashed
-- where input and output go
-- whether stack is affected
-- where return address goes

Write an iterative subroutine with this contract that uses mul:

factorial:
input:  x, y, continue
output:  val
writes:  x and y
stack:   unchanged

Steps:
-- Write iterative Scheme code
-- Translate to machine-language instructions
-- Do tail-recursion optimization

### Tail Recursion Optimization

Transform
(save continue)
(assign continue (label AFTER))
(goto (label SUB))
AFTER
(restore continue)
(goto (reg continue))
to
(goto (label SUB))
What's going on?
-- last thing subroutine P does is to call subroutine Q
-- after call to Q, no real work to do
-- so have Q jump back to P's caller directly

Analogy
-- you want gift for your brother
-- have Amazon send to you, then you send to your brother
-- better just to give Amazon your brother's address

But if there's work to do, can't optimize
-- you might want to add a birthday card with a personal message

### Effect of Tail Recursion Optimization

Compare runtime behaviours of unoptimized and optimized factorial.
Look at stack pushes and pops.
-- how much stack space required for factorial N?

Why is tail recursion worth knowing about?
-- allows Scheme to omit loops: recursion is no less efficient
-- interesting example of an optimization: small change, big effect

### EC Evaluator

What it is
-- A machine language implementation of the evaluator

Why we show it to you
-- Make connection to hardware more concrete
-- Should help you understand how Scheme actually runs

Caveats
-- Still not low-level enough to execute on a machine
-- Uses very abstract operations (eg for syntactic manipulations): would have to replace these by instructions
-- Haven't discussed memory management yet

Tail recursion optimization
-- subtle, because you need to see where it's ESSENTIAL so that evaluating an iterative program will actually result in an iterative process

Other interesting aspects
-- A carefully optimized machine language program for you to study
-- Several clever (but obscure) optimizations

We looked at some code samples from the lecture and discussed their features:

Sample code: ev-if

ev-if
(save exp)
(save env)
(save continue)
(assign continue (label ev-if-decide))
(assign exp (op if-predicate) (reg exp))
(goto (label eval-dispatch))
ev-if-decide
(restore continue)
(restore env)
(restore exp)
(test (op true?) (reg val))
(branch (label ev-if-consequent))
ev-if-alternative
(assign exp (op if-alternative) (reg exp))
(goto (label eval-dispatch))
ev-if-consequent
(assign exp (op if-consequent) (reg exp))
(goto (label eval-dispatch))
Note:
Normal recursive call to eval for predicate
Tail-call optimization in both consequent and alternative
no saves or restores
necessary so loop in fact, eg, is iterative

Sample code: ev-sequence

ev-sequence
(assign exp (op first-exp) (reg unev))
(test (op last-exp?) (reg unev))
(branch (label ev-sequence-last-exp))
(save unev)
(save env)
(assign continue (label ev-sequence-continue))
(goto (label eval-dispatch))
ev-sequence-continue
(restore env)
(restore unev)
(assign unev (op rest-exps) (reg unev))
(goto (label ev-sequence))
ev-sequence-last-exp
(restore continue)
(goto (label eval-dispatch))
Note:
Tail-call optimization on eval of last expression in sequence

Result should be in val, but never use val
tail call to eval puts final result in val
results of earlier calls to eval are ignored

Why have return point on top of stack?
avoid saving and restoring every time around loop
purely a performance optimization
can't do the same with unev and env because they are used inside the loop

Daniel Jackson
November 24, 1999