17.10.5 The WSD transformation algorithm

The WSD algorithm recognises some properties of the bindings to allow: less assignment operations, more efficient generation of unassigned function bindings in the same lexical contour.

When processing a letrec or letrec* core language form WSD classifies each binding into: unreferenced, simple, complex or fixable. Vicare’s implementation of WSD leaves unreferenced bindings alone, in this compiler pass, to be processed later by the source optimiser; an unreferenced binding is classified as simple. It also renames the category lambda into fixable.

The letrec transformation

If the form is a letrec: we do not care about the order of evaluation of the right–hand sides, so given the core language form:

(letrec ((?lhs ?rhs) ...) ?body)

we transform it into:

(let ((?simple.lhs ?simple.rhs) ...)
  (let ((?complex.lhs '#!void) ...)
    (let ((?fixable.lhs ?fixable.rhs) ...)
      (let ((?tmp ?complex.rhs) ...)
        (set! ?complex.lhs ?tmp) ...
        ?body))))

in which the ?complex.rhs expressions are evaluated in unspecified order. In recordised code, the input expression:

(recbind ((?lhs ?rhs) ...) ?body)

is transformed into:

(bind ((?simple.lhs ?simple.rhs) ...)
  (bind ((?complex.lhs '#!void) ...)
    (fix ((?fixable.lhs ?fixable.rhs) ...)
      (bind ((?tmp ?complex.rhs) ...)
        (assign ?complex.lhs ?tmp) ...
        ?body))))

The letrec* transformation

If the form is a letrec*: we do care about the order of evaluation of the right–hand sides, so given the core language form:

(letrec* ((?lhs ?rhs) ...) ?body)

we transform it into:

(let ((?simple.lhs ?simple.rhs) ...)
  (let ((?complex.lhs '#!void) ...)
    (let ((?fixable.lhs ?fixable.rhs) ...)
      (set! ?complex.lhs ?complex.rhs) ...
      ?body)))

in which the ?complex.rhs expressions are evaluated in the same order in which they appear in the core language form. In recordised code, the input expression:

(rec*bind ((?lhs ?rhs) ...) ?body)

is transformed into:

(bind ((?simple.lhs ?simple.rhs) ...)
  (bind ((?complex.lhs '#!void) ...)
    (fix ((?fixable.lhs ?fixable.rhs) ...)
      (assign ?complex.lhs ?complex.rhs) ...
      ?body)))

Notes

The really important thing about the WSD transformations is to generate reliable fix bindings definitions: the classification of “fixable” bindings must be reliable. This covers the very common case of library forms whose top level function definitions are unassigned; for example, the library:

(library (optimize-letrec-waddell-demo)
  (export a b c)
  (import (rnrs))
  (define (a) 1)
  (define (b) (a) 2)
  (define (c) (b) 3))

is transformed into:

(bind ()        ;simple
  (bind ()      ;complex
    (fix ((a_0 (lambda () '1))
          (b_0 (lambda () (seq (funcall a_0) '2)))
          (c_0 (lambda () (seq (funcall b_0) '3))))
      (funcall void))))

The algorithm’s implementation can be conservative and suboptimal in classifying bindings as complex, even though they could be simple or fixable, whenever the classification as simple or fixable requires too much work or is unreliable; in other words: when in doubt, just call it complex. One of the purposes of the SCC algorithm is exactly to improve such classification.