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

;;; Translating from CoreScheme to A Normal Form

(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 '(+ - * /)))

;; Example
; > (normalize-term '(+ (+ 2 2) (let (x 1) (- x))))
;  (let (t1 (+ 2 2))
;    (let (x 1)
;      (let (t2 (- x))
;        (+ t1 t2))))


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

Contributors

-- JensAxelSoegaard - 21 May 2004

Comments

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

-- AntonVanStraaten - 21 May 2004

I'll find out.

-- JensAxelSoegaard - 22 May 2004

CookbookForm
TopicType:	Pearl
ParentTopic:	Pearls?
Next Topic:

PLT Scheme	SISC
Scheme48	SCM
MIT Scheme	scsh
JScheme	Kawa
Chicken	Guile
Bigloo	Tiny
Gambit	LispMe
Gauche	Chez

s c h e m a t i c s : c o o k b o o k

Transforming CoreScheme? into A Normal Form

Contributors

Comments