# Transforming CoreScheme? into A Normal Form

Compilers for higher order langauges often use different forms
of temporary representations of the program.

In A normal form the program source is linearized and all
temporary results are named. It is therefore easy to produce
assembler from normalized programs.

The linear time algorithm below transforms expressions in
CoreScheme? into A Normal Form. The algorithm is from
"The Essence of Compiling with Continuations" by
Cormac Flanagan, Amr Sabry, Bruce Duba and Matthias Felleisen.
The programming technique used was pionered by Danvy and Filinski.

The abstract syntax for CoreScheme? and the corresponding A normal
form is:

;; Abstract syntaks for Core Scheme (CS)
M ::= V Values
| (let (x M) M)
| (if0 M M M)
| (M M ... M)
| (O M ... M) Primitive Operations
V ::= c Constants
| x Variables
| (lambda x1 ... xn . M)
;; A-normalized CS
M ::= V (return)
| (let (x V) M) (bind)
| (if0 V M M) (branch)
| (V V1 ... Vn) (tail call)
| (let ((x (V V1 ... Vn))) M) (call)
| (O V1 ... Vn) (prim-op)
| (let ((x (O V1 ... Vn))) M) (prim-op)
V ::= c | x | (lambda x ... x . M) Values

(define (value? M)
(or (number? M) (symbol? M) (abstraction? M)))
(define (abstraction? M)
(and (pair? M) (eq? (car M) 'lambda)))
(define (prim-op? M)
(member M '(+ - * /)))
(require (lib "match.ss"))
(define (normalize-term M)
(normalize M (lambda (M) M)))
(define (normalize M k)
(match M
[`(lambda ,params ,body) (k `(lambda ,params ,(normalize-term body)))]
[`(let (,x ,M1) ,M2) (normalize M1 (lambda (N1) `(let (,x ,N1) ,(normalize M2 k))))]
[`(if0 ,M1 ,M2 ,M3) (normalize-name M1 (lambda (t) (k `(if0 ,t ,(normalize-term M2) ,(normalize-term M3)))))]
[`(,Fn . ,M*) (if (prim-op? Fn)
(normalize-name* M* (lambda (t*) (k `(,Fn . ,t*))))
(normalize-name Fn (lambda (t) (normalize-name* M* (lambda (t*) (k `(,t . ,t*)))))))]
[V (k V)]))
(define (normalize-name M k)
(normalize M
(lambda (N)
(if (value? N)
(k N)
(let ([t (new-var)])
`(let (,t ,N)
,(k t)))))))
(define (normalize-name* M* k)
(if (null? M*)
(k '())
(normalize-name (car M*)
(lambda (t)
(normalize-name* (cdr M*)
(lambda (t*)
(k `(,t . ,t*))))))))
(define new-var
(let ([count 0])
(lambda ()
(set! count (+ 1 count))
(string->symbol (string-append "t" (number->string count))))))

-- JensAxelSoegaard - 21 May 2004

What's the copyright on this? Do we need to get permission?

-- AntonVanStraaten - 21 May 2004

I'll find out.

-- JensAxelSoegaard - 22 May 2004