Next: , Previous: Principles of Compilation, Up: Principles of Compilation

5.1 Expansion and Analysis

  1. Macros defined by defmacro and all the quasiquotes are expanded and compiled into equivalent form without macros and quasiquotes.

    For example, `(a , x) will be converted to (cons 'a (cons x '())).

  2. Define-s with the nonessential syntax like
              (define (foo x) ...)

    are converted to defines with the essential syntax

              (define foo (lambda (x) ...))

    Non-top-level defines are converted into equivalent letrec-s.

  3. Variables are renamed to avoid name clashes, so that any local variable may have a whole procedure as its scope. This renaming also converts let-s to let*-s. Variables which do not introduce potential name clashes are not renamed. For example,
              (define (foo x y)
                 (let ((x y)
                       (z x))
                   (let* ((x (+ z x)))

    is converted to

              (define foo
                (lambda (x y)
                  (let* ((x__1 y)
                         (z x)
                         (x__2 (+ z x__1)))
  4. In case the set of procedures defined in one letrec is actually not wholly mutually recursive (eg, f1 calls f2, but f2 does not call f1, or there are three procedures, f1, f2, f3 so that f1 and f2 are mutually recursive but f3 is not called from f1 or f2 and it does not call them, etc), it is possible to minimize the number of additional variables passed to procedures.

    Thus letrec-s are split into ordered chunks using dependency analysis and topological sorting, to reduce the number of mutually passed variables. Wherever possible, letrec-s are replaced by let*-s inside these chunks.

  5. Normalization is performed. This converts a majority of scheme control procedures like cond, case, or, and into equivalent terms using a small set of primitives. New variables may be introduced in this phase.

    In case a procedure like or or and occurs in the place where its value is treated as a boolean (eg. first argument of if), it is converted into an analogous boolean-returning procedure, which will finally be represented by an analogous C procedure (eg. || or &&).

    Associative procedures are converted into structures of corresponding nonassociative procedures. List is converted to a structure of cons-s.

    Map and for-each with more than two arguments are converted into an equivalent do-cycle. map-s and for-each-s with two arguments are treated as if they were defined in the compiled file – the definitions map1 and for-each1 are automatically included, if needed.

    There is an option in hobbit.scm to make all map-s and for-each-s be converted into equivalent do-loops, avoiding the use of map1 and/or for-each1 altogether.

  6. Code is analysed for determining which primitive names and compiled procedure names are assumed to be redefinable.
  7. Analysing HOP clonability: hobbit will find a list of clonable HOP-s with information about higher-order arguments.

    Criterias for HOP clonability are given in the section 6.4.

  8. Analysis of liftability: hobbit will determine which lambda-terms have to be built as real closures (implemented as a vector where the first element is a pointer to a function and the rest contain values of environment variables or environment blocks of surrounding code) and which lambda-terms are liftable.

    Liftability analysis follows the criterias given in section 6.5 and 6.6.