Compiling to the Virtual Machine
================================

Compilers!  The word itself inspires excitement and awe, even among experienced practitioners.  But a compiler is just a program: an eminently hackable thing.  This section aims to to describe Guile's compiler in such a way that interested Scheme hackers can feel comfortable reading and extending it.

See Read/Load/Eval/Compile, if you're lost and you just wanted to know how to compile your .scm file.

Compiler Tower
--------------

Guile's compiler is quite simple -- its compilers, to put it more accurately.  Guile defines a tower of languages, starting at Scheme and progressively simplifying down to languages that resemble the VM instruction set (see Instruction Set).

Each language knows how to compile to the next, so each step is simple and understandable.  Furthermore, this set of languages is not hardcoded into Guile, so it is possible for the user to add new high-level languages, new passes, or even different compilation targets.

Languages are registered in the module, (system base language):

     (use-modules (system base language))

They are registered with the define-language form.

 -- Scheme Syntax: define-language
     [#:name] [#:title] [#:reader] [#:printer]
     [#:parser=#f] [#:compilers='()]
     [#:decompilers='()] [#:evaluator=#f]
     [#:joiner=#f] [#:for-humans?=#t]
     [#:make-default-environment=make-fresh-user-module]
     Define a language.

     This syntax defines a <language> object, bound to NAME in the current environment.  In addition, the language will be added to the global language set.  For example, this is the language definition for Scheme:

          (define-language scheme
            #:title	"Scheme"
            #:reader      (lambda (port env) ...)
            #:compilers   `((tree-il . ,compile-tree-il))
            #:decompilers `((tree-il . ,decompile-tree-il))
            #:evaluator	(lambda (x module) (primitive-eval x))
            #:printer	write
            #:make-default-environment (lambda () ...))

The interesting thing about having languages defined this way is that they present a uniform interface to the read-eval-print loop.  This allows the user to change the current language of the REPL:

     scheme@(guile-user)> ,language tree-il
     Happy hacking with Tree Intermediate Language!  To switch back, type `,L scheme'.
     tree-il@(guile-user)> ,L scheme
     Happy hacking with Scheme!  To switch back, type `,L tree-il'.
     scheme@(guile-user)>

Languages can be looked up by name, as they were above.

 -- Scheme Procedure: lookup-language name
     Looks up a language named NAME, autoloading it if necessary.

     Languages are autoloaded by looking for a variable named NAME in a module named (language NAME spec).

     The language object will be returned, or #f if there does not exist a language with that name.

Defining languages this way allows us to programmatically determine the necessary steps for compiling code from one language to another.

 -- Scheme Procedure: lookup-compilation-order from to
     Recursively traverses the set of languages to which FROM can compile, depth-first, and return the first path that can transform FROM to TO. Returns #f if no path is found.

     This function memoizes its results in a cache that is invalidated by subsequent calls to define-language, so it should be quite fast.

There is a notion of a ``current language'', which is maintained in the current-language parameter, defined in the core (guile) module.  This language is normally Scheme, and may be rebound by the user.  The run-time compilation interfaces (see Read/Load/Eval/Compile) also allow you to choose other source and target languages.

The normal tower of languages when compiling Scheme goes like this:

  * Scheme

  * Tree Intermediate Language (Tree-IL)

  * Continuation-Passing Style (CPS)

  * Bytecode

As discussed before (see Object File Format), bytecode is in ELF format, ready to be serialized to disk.  But when compiling Scheme at run time, you want a Scheme value: for example, a compiled procedure. For this reason, so as not to break the abstraction, Guile defines a fake language at the bottom of the tower:

  * Value

Compiling to value loads the bytecode into a procedure, turning cold bytes into warm code.

Perhaps this strangeness can be explained by example: compile-file defaults to compiling to bytecode, because it produces object code that has to live in the barren world outside the Guile runtime; but compile defaults to compiling to value, as its product re-enters the Guile world.

Indeed, the process of compilation can circulate through these different worlds indefinitely, as shown by the following quine:

     ((lambda (x) ((compile x) x)) '(lambda (x) ((compile x) x)))

The Scheme Compiler
-------------------

The job of the Scheme compiler is to expand all macros and all of Scheme to its most primitive expressions.  The definition of ``primitive expression'' is given by the inventory of constructs provided by Tree-IL, the target language of the Scheme compiler: procedure calls, conditionals, lexical references, and so on.  This is described more fully in the next section.

The tricky and amusing thing about the Scheme-to-Tree-IL compiler is that it is completely implemented by the macro expander.  Since the macro expander has to run over all of the source code already in order to expand macros, it might as well do the analysis at the same time, producing Tree-IL expressions directly.

Because this compiler is actually the macro expander, it is extensible. Any macro which the user writes becomes part of the compiler.

The Scheme-to-Tree-IL expander may be invoked using the generic compile procedure:

     (compile '(+ 1 2) #:from 'scheme #:to 'tree-il)
     =>
     #<tree-il (call (toplevel +) (const 1) (const 2))>

(compile FOO #:from 'scheme #:to 'tree-il) is entirely equivalent to calling the macro expander as (macroexpand FOO 'c '(compile load eval)).  See Macro Expansion. compile-tree-il, the procedure dispatched by compile to 'tree-il, is a small wrapper around macroexpand, to make it conform to the general form of compiler procedures in Guile's language tower.

Compiler procedures take three arguments: an expression, an environment, and a keyword list of options. They return three values: the compiled expression, the corresponding environment for the target language, and a ``continuation environment''. The compiled expression and environment will serve as input to the next language's compiler. The ``continuation environment'' can be used to compile another expression from the same source language within the same module.

For example, you might compile the expression, (define-module (foo)). This will result in a Tree-IL expression and environment. But if you compiled a second expression, you would want to take into account the compile-time effect of compiling the previous expression, which puts the user in the (foo) module. That is purpose of the ``continuation environment''; you would pass it as the environment when compiling the subsequent expression.

For Scheme, an environment is a module. By default, the compile and compile-file procedures compile in a fresh module, such that bindings and macros introduced by the expression being compiled are isolated:

     (eq? (current-module) (compile '(current-module)))
     => #f

     (compile '(define hello 'world))
     (defined? 'hello)
     => #f

     (define / *)
     (eq? (compile '/) /)
     => #f

Similarly, changes to the current-reader fluid (see current-reader) are isolated:

     (compile '(fluid-set! current-reader (lambda args 'fail)))
     (fluid-ref current-reader)
     => #f

Nevertheless, having the compiler and compilee share the same name space can be achieved by explicitly passing (current-module) as the compilation environment:

     (define hello 'world)
     (compile 'hello #:env (current-module))
     => world

Tree-IL
-------

Tree Intermediate Language (Tree-IL) is a structured intermediate language that is close in expressive power to Scheme. It is an expanded, pre-analyzed Scheme.

Tree-IL is ``structured'' in the sense that its representation is based on records, not S-expressions. This gives a rigidity to the language that ensures that compiling to a lower-level language only requires a limited set of transformations. For example, the Tree-IL type <const> is a record type with two fields, src and exp. Instances of this type are created via make-const. Fields of this type are accessed via the const-src and const-exp procedures. There is also a predicate, const?. See Records, for more information on records.

All Tree-IL types have a src slot, which holds source location information for the expression. This information, if present, will be residualized into the compiled object code, allowing backtraces to show source information. The format of src is the same as that returned by Guile's source-properties function. See Source Properties, for more information.

Although Tree-IL objects are represented internally using records, there is also an equivalent S-expression external representation for each kind of Tree-IL. For example, the S-expression representation of #<const src: #f exp: 3> expression would be:

     (const 3)

Users may program with this format directly at the REPL:

     scheme@(guile-user)> ,language tree-il
     Happy hacking with Tree Intermediate Language!  To switch back, type `,L scheme'.
     tree-il@(guile-user)> (call (primitive +) (const 32) (const 10))
     => 42

The src fields are left out of the external representation.

One may create Tree-IL objects from their external representations via calling parse-tree-il, the reader for Tree-IL. If any source information is attached to the input S-expression, it will be propagated to the resulting Tree-IL expressions. This is probably the easiest way to compile to Tree-IL: just make the appropriate external representations in S-expression format, and let parse-tree-il take care of the rest.

 -- Scheme Variable: <void> src
 -- External Representation: (void)
     An empty expression.  In practice, equivalent to Scheme's (if #f #f).

 -- Scheme Variable: <const> src exp
 -- External Representation: (const EXP)
     A constant.

 -- Scheme Variable: <primitive-ref> src name
 -- External Representation: (primitive NAME)
     A reference to a ``primitive''.  A primitive is a procedure that, when compiled, may be open-coded.  For example, cons is usually recognized as a primitive, so that it compiles down to a single instruction.

     Compilation of Tree-IL usually begins with a pass that resolves some <module-ref> and <toplevel-ref> expressions to <primitive-ref> expressions.  The actual compilation pass has special cases for calls to certain primitives, like apply or cons.

 -- Scheme Variable: <lexical-ref> src name gensym
 -- External Representation: (lexical NAME GENSYM)
     A reference to a lexically-bound variable.  The NAME is the original name of the variable in the source program. GENSYM is a unique identifier for this variable.

 -- Scheme Variable: <lexical-set> src name gensym exp
 -- External Representation: (set! (lexical NAME GENSYM) EXP)
     Sets a lexically-bound variable.

 -- Scheme Variable: <module-ref> src mod name public?
 -- External Representation: (@ MOD NAME)
 -- External Representation: (@@ MOD NAME)
     A reference to a variable in a specific module. MOD should be the name of the module, e.g. (guile-user).

     If PUBLIC? is true, the variable named NAME will be looked up in MOD's public interface, and serialized with @; otherwise it will be looked up among the module's private bindings, and is serialized with @@.

 -- Scheme Variable: <module-set> src mod name public? exp
 -- External Representation: (set! (@ MOD NAME) EXP)
 -- External Representation: (set! (@@ MOD NAME) EXP)
     Sets a variable in a specific module.

 -- Scheme Variable: <toplevel-ref> src name
 -- External Representation: (toplevel NAME)
     References a variable from the current procedure's module.

 -- Scheme Variable: <toplevel-set> src name exp
 -- External Representation: (set! (toplevel NAME) EXP)
     Sets a variable in the current procedure's module.

 -- Scheme Variable: <toplevel-define> src name exp
 -- External Representation: (define (toplevel NAME) EXP)
     Defines a new top-level variable in the current procedure's module.

 -- Scheme Variable: <conditional> src test then else
 -- External Representation: (if TEST THEN ELSE)
     A conditional. Note that ELSE is not optional.

 -- Scheme Variable: <call> src proc args
 -- External Representation: (call PROC . ARGS)
     A procedure call.

 -- Scheme Variable: <primcall> src name args
 -- External Representation: (primcall NAME . ARGS)
     A call to a primitive.  Equivalent to (call (primitive NAME) . ARGS).  This construct is often more convenient to generate and analyze than <call>.

     As part of the compilation process, instances of (call (primitive NAME) . ARGS) are transformed into primcalls.

 -- Scheme Variable: <seq> src head tail
 -- External Representation: (seq HEAD TAIL)
     A sequence.  The semantics is that HEAD is evaluated first, and any resulting values are ignored.  Then TAIL is evaluated, in tail position.

 -- Scheme Variable: <lambda> src meta body
 -- External Representation: (lambda META BODY)
     A closure.  META is an association list of properties for the procedure.  BODY is a single Tree-IL expression of type <lambda-case>.  As the <lambda-case> clause can chain to an alternate clause, this makes Tree-IL's <lambda> have the expressiveness of Scheme's case-lambda.

 -- Scheme Variable: <lambda-case> req opt rest kw inits gensyms body alternate
 -- External Representation:
     (lambda-case ((REQ OPT REST KW INITS GENSYMS)
     BODY)
     [ALTERNATE])
     One clause of a case-lambda.  A lambda expression in Scheme is treated as a case-lambda with one clause.

     REQ is a list of the procedure's required arguments, as symbols. OPT is a list of the optional arguments, or #f if there are no optional arguments. REST is the name of the rest argument, or #f.

     KW is a list of the form, (ALLOW-OTHER-KEYS? (KEYWORD NAME VAR) ...), where KEYWORD is the keyword corresponding to the argument named NAME, and whose corresponding gensym is VAR.  INITS are tree-il expressions corresponding to all of the optional and keyword arguments, evaluated to bind variables whose value is not supplied by the procedure caller. Each INIT expression is evaluated in the lexical context of previously bound variables, from left to right.

     GENSYMS is a list of gensyms corresponding to all arguments: first all of the required arguments, then the optional arguments if any, then the rest argument if any, then all of the keyword arguments.

     BODY is the body of the clause.  If the procedure is called with an appropriate number of arguments, BODY is evaluated in tail position.  Otherwise, if there is an ALTERNATE, it should be a <lambda-case> expression, representing the next clause to try. If there is no ALTERNATE, a wrong-number-of-arguments error is signaled.

 -- Scheme Variable: <let> src names gensyms vals exp
 -- External Representation: (let NAMES GENSYMS VALS EXP)
     Lexical binding, like Scheme's let.  NAMES are the original binding names, GENSYMS are gensyms corresponding to the NAMES, and VALS are Tree-IL expressions for the values. EXP is a single Tree-IL expression.

 -- Scheme Variable: <letrec> in-order? src names gensyms vals exp
 -- External Representation: (letrec NAMES GENSYMS VALS EXP)
 -- External Representation: (letrec* NAMES GENSYMS VALS EXP)
     A version of <let> that creates recursive bindings, like Scheme's letrec, or letrec* if IN-ORDER? is true.

 -- Scheme Variable: <prompt> escape-only? tag body handler
 -- External Representation: (prompt ESCAPE-ONLY? TAG BODY HANDLER)
     A dynamic prompt.  Instates a prompt named TAG, an expression, during the dynamic extent of the execution of BODY, also an expression.  If an abort occurs to this prompt, control will be passed to HANDLER, also an expression, which should be a procedure.  The first argument to the handler procedure will be the captured continuation, followed by all of the values passed to the abort.  If ESCAPE-ONLY? is true, the handler should be a <lambda> with a single <lambda-case> body expression with no optional or keyword arguments, and no alternate, and whose first argument is unreferenced.  See Prompts, for more information.

 -- Scheme Variable: <abort> tag args tail
 -- External Representation: (abort TAG ARGS TAIL)
     An abort to the nearest prompt with the name TAG, an expression. ARGS should be a list of expressions to pass to the prompt's handler, and TAIL should be an expression that will evaluate to a list of additional arguments.  An abort will save the partial continuation, which may later be reinstated, resulting in the <abort> expression evaluating to some number of values.

There are two Tree-IL constructs that are not normally produced by higher-level compilers, but instead are generated during the source-to-source optimization and analysis passes that the Tree-IL compiler does.  Users should not generate these expressions directly, unless they feel very clever, as the default analysis pass will generate them as necessary.

 -- Scheme Variable: <let-values> src names gensyms exp body
 -- External Representation: (let-values NAMES GENSYMS EXP BODY)
     Like Scheme's receive -- binds the values returned by evaluating exp to the lambda-like bindings described by GENSYMS.  That is to say, GENSYMS may be an improper list.

     <let-values> is an optimization of a <call> to the primitive, call-with-values.

 -- Scheme Variable: <fix> src names gensyms vals body
 -- External Representation: (fix NAMES GENSYMS VALS BODY)
     Like <letrec>, but only for VALS that are unset lambda expressions.

     fix is an optimization of letrec (and let).

Tree-IL is a convenient compilation target from source languages.  It can be convenient as a medium for optimization, though CPS is usually better.  The strength of Tree-IL is that it does not fix order of evaluation, so it makes some code motion a bit easier.

Optimization passes performed on Tree-IL currently include:

  * Open-coding (turning toplevel-refs into primitive-refs, and calls to primitives to primcalls)

  * Partial evaluation (comprising inlining, copy propagation, and constant folding)

  * Common subexpression elimination (CSE)

In the future, we will move the CSE pass to operate over the lower-level CPS language.

Continuation-Passing Style
--------------------------

Continuation-passing style (CPS) is Guile's principal intermediate language, bridging the gap between languages for people and languages for machines.  CPS gives a name to every part of a program: every control point, and every intermediate value.  This makes it an excellent medium for reasoning about programs, which is the principal job of a compiler.

An Introduction to CPS
......................

As an example, consider the following Scheme expression:

     (begin
       (display "The sum of 32 and 10 is: ")
       (display 42)
       (newline))

Let us identify all of the sub-expressions in this expression.  We give them unique labels, like K1, and annotate the original source code:

     (begin
       (display "The sum of 32 and 10 is: ")
       |k1      k2
       k0
       (display 42)
       |k4      k5
       k3
       (newline))
       |k7
       k6

These labels also identify continuations.  For example, the continuation of k7 is k6.  This is because after evaluating the value of newline, performed by the expression labelled k7, we continue to apply it in K6.

Which label has k0 as its continuation?  It is either k1 or k2.  Scheme does not have a fixed order of evaluation of arguments, although it does guarantee that they are evaluated in some order.  However, continuation-passing style makes evaluation order explicit.  In Guile, this choice is made by the higher-level language compilers.

Let us assume a left-to-right evaluation order.  In that case the continuation of k1 is k2, and the continuation of k2 is k0.

With this example established, we are ready to give an example of CPS in Scheme:

     (lambda (ktail)
       (let ((k1 (lambda ()
                   (let ((k2 (lambda (proc)
                               (let ((k0 (lambda (arg0)
                                           (proc k4 arg0))))
                                 (k0 "The sum of 32 and 10 is: ")))))
                     (k2 display))))
             (k4 (lambda _
                   (let ((k5 (lambda (proc)
                               (let ((k3 (lambda (arg0)
                                           (proc k7 arg0))))
                                 (k3 42)))))
                     (k5 display))))
             (k7 (lambda _
                   (let ((k6 (lambda (proc)
                               (proc ktail))))
                     (k6 newline)))))
         (k1))

Holy code explosion, Batman!  What's with all the lambdas?  Indeed, CPS is by nature much more verbose than ``direct-style'' intermediate languages like Tree-IL.  At the same time, CPS is more simple than full Scheme, in the same way that a Turing machine is more simple than Scheme, although they are semantically equivalent.

In the original program, the expression labelled k0 is in effect context.  Any values it returns are ignored.  This is reflected in CPS by noting that its continuation, k4, takes any number of values and ignores them.  Compare this to k2, which takes a single value; in this way we can say that k1 is in a ``value'' context. Likewise k6 is in tail context with respect to the expression as a whole, because its continuation is the tail continuation, ktail.  CPS makes these details manifest, and gives them names.

CPS in Guile
............

Like Tree-IL, CPS is also a structured language, implemented with records not S-expressions.

 -- Scheme Variable: <prompt> escape-only? tag body handler
 -- External Representation: (prompt ESCAPE-ONLY? TAG BODY HANDLER)

 -- Scheme Variable: $arity req opt rest kw allow-other-keys?

 -- Scheme Variable: $letk conts body
 -- External Representation: (letk CONTS BODY)

 -- Scheme Variable: $continue k src exp
 -- External Representation: (continue K SRC EXP)

 -- Scheme Variable: $letrec names syms funs body
 -- External Representation: (letrec NAMES SYMS FUNS BODY)

;; Continuations
 -- Scheme Variable: $cont k cont
 -- External Representation: (cont k cont)

 -- Scheme Variable: $kif kt kf
 -- External Representation: (kif kt kf)

 -- Scheme Variable: $ktrunc arity k
 -- External Representation: (ktrunc arity k)

 -- Scheme Variable: $kargs names syms body
 -- External Representation: (kargs names syms body)

 -- Scheme Variable: $kentry self tail clauses
 -- External Representation: (kentry self tail clauses)

 -- Scheme Variable: $ktail
 -- External Representation: (ktail)

 -- Scheme Variable: $kclause arity cont
 -- External Representation: (kclause arity cont)

;; Expressions.
 -- Scheme Variable: $void
 -- External Representation: (void)

 -- Scheme Variable: $const val
 -- External Representation: (const val)

 -- Scheme Variable: $prim name
 -- External Representation: (prim name)

 -- Scheme Variable: $fun src meta free body
 -- External Representation: (fun src meta free body)

 -- Scheme Variable: $call proc args
 -- External Representation: (call proc args)

 -- Scheme Variable: $primcall name args
 -- External Representation: (primcall name args)

 -- Scheme Variable: $values args
 -- External Representation: (values args)

 -- Scheme Variable: $prompt escape? tag handler pop
 -- External Representation: (prompt escape? tag handler pop)

;; Helper. $arity make-$arity

;; Terms. $letk $continue $letrec

;; Continuations. $cont

;; Continuation bodies. $kif $ktrunc $kargs $kentry $ktail $kclause

;; Expressions. $void $const $prim $fun $call $primcall $values $prompt

;; Building macros. let-gensyms build-cps-term build-cps-cont build-cps-exp rewrite-cps-term rewrite-cps-cont rewrite-cps-exp

;; Misc. parse-cps unparse-cps fold-conts fold-local-conts

cwcc

records, unlike early cps (rabbit, orbit)

Compiling CPS
.............

In CPS, there are no nested expressions.  Indeed, CPS even removes the concept of a stack.  All applications in CPS are in tail context.  For that reason, applications in CPS are jumps, not calls.  The (k1) above is nothing more than a goto.  (k3 42) is a goto with a value.  In this way, CPS bridges the gap between the lambda calculus and machine instruction sequences.

On the side of machine instructions, Guile does still have a stack, and the lambda forms shown above do not actually result in one closure being allocated per subexpression at run-time.  Lambda expressions introduced by a CPS transformation can always be allocated as labels or basic blocks within a function.  In fact, we make a syntactic distinction between closures and continuations in the CPS language, and attempt to transform closures to continuations (basic blocks) where possible, via the contification optimization pass.

Values bound by continuations are allocated to stack slots in a function's frame.  The compiler from CPS only allocates slots to values that are actually live; it's possible to have a value in scope but not allocated to a slot.

Bytecode
--------

See Object File Format.

TODO: document (system vm loader)

 -- Scheme Variable: load-thunk-from-file file
 -- C Function: scm_load_thunk_from_file (file)
     Load object code from a file named FILE. The file will be mapped into memory via mmap, so this is a very fast operation.

     On disk, object code is embedded in ELF, a flexible container format created for use in UNIX systems.  Guile has its own ELF linker and loader, so it uses the ELF format on all systems.

TODO: document load-thunk-from-memory

Compiling object code to the fake language, value, is performed via loading objcode into a program, then executing that thunk with respect to the compilation environment. Normally the environment propagates through the compiler transparently, but users may specify the compilation environment manually as well, as a module.

Writing New High-Level Languages
--------------------------------

In order to integrate a new language LANG into Guile's compiler system, one has to create the module (language LANG spec) containing the language definition and referencing the parser, compiler and other routines processing it. The module hierarchy in (language brainfuck) defines a very basic Brainfuck implementation meant to serve as easy-to-understand example on how to do this. See for instance http://en.wikipedia.org/wiki/Brainfuck for more information about the Brainfuck language itself.

Extending the Compiler
----------------------

At this point we take a detour from the impersonal tone of the rest of the manual.  Admit it: if you've read this far into the compiler internals manual, you are a junkie.  Perhaps a course at your university left you unsated, or perhaps you've always harbored a desire to hack the holy of computer science holies: a compiler.  Well you're in good company, and in a good position.  Guile's compiler needs your help.

There are many possible avenues for improving Guile's compiler. Probably the most important improvement, speed-wise, will be some form of native compilation, both just-in-time and ahead-of-time. This could be done in many ways. Probably the easiest strategy would be to extend the compiled procedure structure to include a pointer to a native code vector, and compile from bytecode to native code at run-time after a procedure is called a certain number of times.

The name of the game is a profiling-based harvest of the low-hanging fruit, running programs of interest under a system-level profiler and determining which improvements would give the most bang for the buck. It's really getting to the point though that native compilation is the next step.

The compiler also needs help at the top end, enhancing the Scheme that it knows to also understand R6RS, and adding new high-level compilers. We have JavaScript and Emacs Lisp mostly complete, but they could use some love; Lua would be nice as well, but whatever language it is that strikes your fancy would be welcome too.

Compilers are for hacking, not for admiring or for complaining about. Get to it!