Recitation 23

Today: Tail Recursion and the Explicit Control Evaluator

Subroutines

    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

(save continue)
(assign continue (label AFTER))
(goto (label SUB))
AFTER
(restore continue)
(goto (reg continue))

(goto (label SUB))

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

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

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

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 theyare used inside the loop