Recitation 21

Today: Register Machines

Motivation

We take point of view of
-- hardware designer
-- not computer programmer

ie, we view the program as a machine.

Of course, in practice
-- don't have a new physical machine for each program!
-- but evaluator machine can run all Scheme programs

What's missing from our description
-- memory management (ie, cons): talk about this later

Basics

To design a register machine, need
-- datapaths: registers and operations
-- controller: to sequence operations

Elements of a datapath
-- Constants
-- Registers
-- Operations
-- Buttons

Must have a button
-- breaking path between any pair of registers

Conditionals
-- special operation with true/false output
-- output is not connected
-- sent to special "condition register" used by controller

Controller
-- sequence of button presses with condition tests

Exercise

Design a datapath for
-- the factorial function

(define (fact n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product) (+ counter 1))))
  (iter 1 1))

Intuition
-- even though interpreter hangs a frame for each invocation of iter, can reuse product and counter
 

Machine Language Program

Program is
-- list of instructions and labels

Instruction is
-- goto, with form (goto (label label-name))
-- branch, with form
        (branch (label label-name))
-- test, with form
        (test (op operation-name) source source)
-- assignment, with form
        (assign target-registersource)
        (assign target-register operation source source)
-- source is (reg register-name) or (const constant-name)

Semantics of test/branch
-- effect of a test instruction is to set the condition register
-- branch is like a goto if condition register contains 1/true
-- branch is like a null instruction if condition register contains 0/false

Note
-- only one condition register
-- no necessary association between test and branch: if do sequence of tests, only last one matters

Exercise

Draw the datapath for this machine and figure out what it does.

(controller
      (test (op >) (reg a) (const 0))
      (branch (label X))
      (assign a (op -) (const 0) (reg a))
X
      (assign b (reg a)
    )

Exercise (Recitation Problem)

Draw the datapath and write the instruction sequence for the register machine that implements:

(define (max a b) (if (> a b) a b)

Input values in a and b
Output value in register out

Exercise

Translate the factorial program to a machine-language program.