Heap-allocated Literal Elimination

This transformation removes all ``heap-allocated'' literals from the program: Things like (quote (1 2)), a quoted list consisting of two cons cells. We do this by expressing these quoted literals in terms of simpler operations and constants. For example, the aforementioned (quote (1 2)) can also be expressed by (cons '1 (cons '2 '())).

Thus, this pass involves doing this ``destructuring'' on all the heap-allocated constants we brought up to the top of the expression in the analysis pass.

The main problem in this pass deals with symbols. Not only do we need to ``destructure'' symbols:

'foo ==> (string->uninterned-symbol (string #\f #\o #\o))

but we also need to make sure that different instances of quoted symbols refer to the same symbol data-structure. So, for example, the following transformation is not kosher:

(cons 'a '(a))
  ==> (let ((g97 'a) (g98 '(a)))
        (cons g97 g98))
  ==> (let ((g97 (string->uninterned-symbol (string #\a)))
            (g98 (cons (string->uninterned-symbol (string #\a))
                   '())))
        (cons g97 g98))

because (cons 'a '(a)) has the property that its car is eq? to its cadr, while the large let above does not have that property.

So this pass must not only destructure all heap-allocated quoted data, but also collect up all the symbols it uncovers while destructuring and bind those symbols to new variables.

(cons 'a '(a))
  ==> (let ((g97 'a) (g98 '(a)))
        (cons g97 g98))
  ==> (let ((g1000 (string->uninterned-symbol (string #\a)))))
        (let ((g97 g1000)
              (g98 (cons g1000 '())))
          (cons g97 g98)))

As a final note, this is the pass where we get rid of the outside let. So the final version of our test, (cons 'a '(a)) would be:

((lambda (g1000)
   '(free)
   ((lambda (g97 g98)
      '(free)
      (cons g97 g98))
    g1000
    (cons g1000 '())))
 (string->uninterned-symbol (string #\a)))

Skeleton

We'll let you sweat this one out. But you'll probably want to do something like this:

(define s-table '())    ; ((symbol gensym-variable) ...)

(define heap-literal-destruct
  (lambda (obj)
    (cond
      [(symbol? obj)
       (let ([entry (assq obj s-table)])
         (if (pair? entry)
             (cadr entry)
             (let ([v (gensym)])
               (set! s-table (cons (list obj v) s-table))
               v)))]
      [(or (boolean? obj) (number? obj) (char? obj) (null? obj))
       ... ]
      [(string? obj) ... ]
      [(pair? obj) ... ]
      [(vector? obj) ... ])))

Programs like this one form the reason that Scheme includes set!, so don't be shy about using it.

Examples

> (immediate-literal-form '(let ([#:g32 '"hi"]) #:g32))
((lambda (#:g32) '(free) #:g32) (string '#\h '#\i))
> (immediate-literal-form
  '(let ([#:g33 '(1 2)]) (lambda (f) '(free #:g33) (f #:g33))))
((lambda (#:g33)
   '(free)
   (lambda (f) '(free #:g33) (f #:g33)))
 (cons '1 (cons '2 '())))

ehilsdal@cs.indiana.edu