Code Simplification

The process of turning in some kind of parsed input into a form suitable for code-generation is sometimes called the ``front-end'' of the compiler. In our compiler, this process is divided up into a number of different passes:

Initial Simplification

One pass is necessary to transform the expression in source form into a simpler core form.

The only changes made in the expression are to quote all literals

11 ==> (quote 11)

to convert begin expressions into a form such that all begin expressions have only two sub-expressions,

(begin exp)       ==> exp
(begin exp0 exp+) ==> (begin exp0 (begin exp+))

to convert multiple-bodied lambdas into lambdas with only one body,

(lambda formals body+) ==> (lambda formals (begin body+))

and to simplify the let and letrec syntactic forms

(let ((var exp) ...)    ==> ((lambda (var ...) 
  body+)                        body+) 
                             exp ...)          

(letrec ((var exp) ...) ==> (let ((var #f) ...) 
  body+)                      (set! var exp) ...
                              body+)

In addition, some syntactic errors can (and should) be checked at this time:

(set! 10 3)
(lambda (x))
(lambda (a a) 3)
(a b . c)

Lexical errors such as free variables or assignments to primitives will be caught in the next pass.

A skeleton of this pass might look much like this:

(define core-convert
  (lambda (exp)
    (if (not (pair? exp))
	(cond
	  [(symbol? exp) ...]
	  [(or (number? exp) (boolean? exp) (string? exp) (char? exp))
	   ... ]
	  [else (error 'core-convert "Bad expression ~s" exp)])
	(record-case exp
	  [quote (obj) ... ]
	  [begin (e0 . exps) ... ]
	  [if (t c a) ... ]
	  [set! (v e) ... ]
	  [lambda (formals . bodies)
	   ... ]
	  [let (decls . bodies)
	    (let ([vars (map car decls)]
		  [vals (map cadr decls)])
	      (core-convert `((lambda ,vars ,@bodies) ,@vals)))]
	  [letrec (decls . bodies)
	    (let ([vars (map car decls)]
		  [vals (map cadr decls)])
	      (let ([holders (map (lambda (x) #f) vars)]
		    [assigns (map (lambda (v e) `(set! ,v ,e)) vars vals)])
		(core-convert `((lambda ,vars ,@assigns ,@bodies) ,@holders))))]
	  [else ... ]))))

Here are some examples of the core-convert function:

> (core-convert '3)
'3
> (core-convert 'a)
a
> (core-convert '#f)
'#f
> (core-convert '())

Error in core-convert: Bad expression ().
Type (debug) to enter the debugger.
> (core-convert ''())
'()
> (core-convert ''a)
'a
> (core-convert '(let ((x 3)) x))
((lambda (x) x) '3)
> (core-convert '(letrec ((x 5)) x))
((lambda (x) (begin (set! x '5) x)) '#f)
> (core-convert ''#(a b c))
'#3(a b c)
> (core-convert '(set! x (let ((x 3)) x)))
(set! x ((lambda (x) x) '3))
> (core-convert '(set! 3 8))

Error in core-convert: Bad expression (set! 3 8).
Type (debug) to enter the debugger.
> (core-convert '(lambda (a b c) d))
(lambda (a b c) d)
> (core-convert '(lambda (a a c) d))
>

ehilsdal@cs.indiana.edu