Register Machines and Imperative Form
Table of Contents
1 Introduction
The purpose of these notes is to understand an important set of transformations that apply on programs that are already in tail form. Recall that a program is in tail form if every function call in the program is in tail position.
2 Boilerplate boilerplate
#lang racket (provide (all-defined-out)) (require rackunit)
3 Example: Factorial
We define and study the transformations on the factorial function.
3.1 Factorial test cases
(check-equal? (! 0) 1 "!:1") (check-equal? (! 3) 6 "!:2")
4 Factorial: tail form
We start with ! the factorial function defined in tail
form.
(define (!/acc n)
(letrec ([loop (lambda (i a)
(if (= 0 i)
a
(loop (sub1 i) (* a i))))])
(loop n 1)))
(define ! !/acc)
Notice that ! is in tail form.
5 Imperative form
It is worth examining how the identifiers i and a in the body of
loop are created and used. Notice that each call to loop creates
a new pair of identifiers i and a. The parameters i and a
are used in the inner call to loop. They are, however, never used
after the call. This is a consequence of the call to loop being
in tail position.
This observation creates an opportunity for the following important
transformation: It suffices to use exactly one pair of identifiers
across all the invocations of loop. In other words, it is possible
to `lift' the formal parameters out of the body of loop and declare
them separately via a let. i and a are now mutable variables,
i.e., they denote storage locations. In addition loop is now a zero
argument function. Parameter passing is now replaced by variable
initialization. The resultant program is now said to be in
imperative form.
(define (!/imp n)
(let ([i n] [a 1])
(letrec ([loop (lambda ()
(if (= 0 i)
a
(begin
(set! a (* a i))
(set! i (sub1 i))
(loop))))])
(loop))))
(define ! !/imp)
6 Goto form
Also, a zero-argument tail call is akin to a goto,
which merely transfers control to another point in the program.
(define (goto f) (f))
A further embellishment, done, emphasises the action of
returning from the function loop.
(define (done x) x)
The register form of the factorial program is obtained by
suitably inserting goto's and done's.
(define (!/goto n)
(let ([i n] [a 1])
(letrec ([loop (lambda ()
(if (= 0 i)
(done a) ; instead of a
(begin
(set! a (* a i))
(set! i (sub1 i))
(goto loop))))]) ; instead of (loop)
(goto loop))))
(define ! !/goto)
The program is now essentially a C program, with assignments,
and goto's!
7 An equivalent iterative C program
It is easy to transform the Scheme program, almost verbatim, into a C program:
#include<stdio.h>
int f(int n) {
int i = n;
int a = 1;
loop:
if (i == 0)
return a;
a = a*i;
i = i-1;
goto loop;
}
int main() {
printf("!(0) == %d\n", f(0));
printf("!(1) == %d\n", f(1));
printf("!(2) == %d\n", f(2));
printf("!(3) == %d\n", f(3));
}
8 Register machine form
A further transformation converts the program to register machine form.
Local variables now become global state variables, also
called register variables. A special register variable
*answer* stores the final answer.
(define uninitialized '_) (define *n* uninitialized) ; holds the input number (define *i* uninitialized) ; state variable (define *a* uninitialized) ; state variable (define *answer* uninitialized) ; holds the final answer
done now halts the program.
(define (done) (void))
All functions now are essentially `basic' blocks of code: They do not take any parameters, nor do they return anything. Execution within a basic block is a sequence of assignment statements or if statements. Control exits the basic block only through a goto or by falling through.
(define (init)
(begin
(set! *i* *n*)
(set! *a* 1)
(set! *answer* '_) ; uninitialized
(goto loop)))
(define (loop)
(if (= 0 *i*)
(begin
(set! *answer* *a*)
(goto done))
(begin
(set! *a* (* *a* *i*))
(set! *i* (sub1 *i*))
(goto loop))))
8.1 Interface and tests
!/reg begins by initialising the register *n* and then
going to init. All register variables, being top-level,
are available for inspection.
(define (!/reg n) ; interface
(begin
(set! *n* n)
(goto init)))
(define ! !/reg)
;;; unit tests
(begin
(!/reg 0)
(check-equal? *answer* 1 "!/reg 0"))
(begin
(!/reg 1)
(check-equal? *answer* 1 "!/reg 1"))
(begin
(!/reg 3)
(check-equal? *answer* 6 "!/reg 6"))
9 Stepper form
For a program in register form, it is very easy to set up things so that we can step through its execution.
The functions show and step are used as an interface to
carry out the stepping:
- show
- A function of no argument that displays the state of the computation.
- step
- A function of no argument that takes the computation one `step' forward.
9.1 Program Counter
The key observation is to introduce a new state variable register variable called pc, the program counter.
(define *pc* uninitialized)
The program counter points to the current code block.
There are three code blocks in the above example: init,
loop and done.
9.2 show displays computation state
show displays all the registers at any given point of time
in the computation.
(define show
(lambda ()
(printf "*n*: ~a~n" *n*)
(printf "*i*: ~a~n" *i*)
(printf "*a*: ~a~n" *a*)
(printf "*pc*: ~a~n" *pc*)
(printf "*answer*: ~a~n~n" *answer*)
(list *n* *i* *a* *pc* *answer*)))
9.3 goto updates the program counter
The role of goto now is to merely update the program
counter and yield control back to the top level.
(define (goto l) (set! *pc* l))
9.4 step executes one code block
step carries out a transition by executing the code
pointed to by *pc*.
(define (step) (*pc*))
The definitions of the code blocks init, loop and done
are unchanged.
9.5 Interface
The interface
(define (!/stepper n) ; interface, same !/reg
(begin
(set! *n* n)
(goto init)))
(define ! !/stepper)
9.6 Tests
;;; unit tests (test-case "(! 0)" (! 0) (check-equal? (show) (list 0 ; *n* '_ ; *i* '_ ; *a* init ; *pc* '_ ; *answer* )) (step) (check-equal? (show) (list 0 ; *n* 0 ; *i* 1 ; *a* loop ; *pc* '_ ; answer )) (step) (check-equal? (show) (list 0 ; *n* 0 ; *i* 1 ; *a* done ; *pc* 1 ; answer )))
10 Conclusion
Accumulator style programs are in tail form. We have seen how a program in tail form may be systematically transformed into an imperative form which closely resembles an iterative C program. The imperative form can further be transformed into a register machine form where all program variables are registers (i.e., global variables), all procedures are top level and they neither take arguments nor return values. The register form program may be transformed to a stepper form that allows one to step through the execution of the program, one basic block at a time.