Recitation 21

Today: Register Machines


Register machine
-- simplified version of a traditional computer architecture
-- instructions & registers
-- fixed repertoire of registers and kinds of instruction

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


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

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

-- sequence of button presses with condition tests


Design a datapath for
-- the factorial function

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

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

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


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

      (test (op >) (reg a) (const 0))
      (branch (label X))
      (assign a (op -) (const 0) (reg a))
      (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


Translate the factorial program to a machine-language program.

Daniel Jackson
November 17, 1999