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
......................

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, annotating them with unique labels:

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

Each of these labels identifies a point in a program.  One label may be the continuation of another label.  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 expression has k0 as its continuation?  It is either the expression labelled k1 or the expression labelled k2. Scheme does not have a fixed order of evaluation of arguments, though it does guarantee that they are evaluated in some order.  Unlike general Scheme, 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 simpler than full Scheme, because it makes things more explicit.

In the original program, the expression labelled k0 is in effect context.  Any values it returns are ignored.  In Scheme, this fact is implicit.  In CPS, we can see it explicitly 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
............

Guile's CPS language is composed of terms, expressions, and continuations.

A term can either evaluate an expression and pass the resulting values to some continuation, or it can declare local continuations and contain a sub-term in the scope of those continuations.

 -- CPS Term: $continue k src exp
     Evaluate the expression EXP and pass the resulting values (if any) to the continuation labelled K.  The source information associated with the expression may be found in SRC, which is either an alist as in source-properties or is #f if there is no associated source.

 -- CPS Term: $letk conts body
     Bind CONTS, a list of continuations ($cont instances), in the scope of the sub-term BODY.  The continuations are mutually recursive.

Additionally, the early stages of CPS allow for a set of mutually recursive functions to be declared as a term.  This $letrec type is like Tree-IL's <fix>.  The contification pass will attempt to transform the functions declared in a $letrec into local continuations.  Any remaining functions are later lowered to $fun expressions.

 -- CPS Term: $letrec names syms funs body
     Declare the mutually recursive set of functions denoted by NAMES, SYMS, and FUNS within the sub-term BODY.  NAMES and SYMS are lists of symbols, and FUNS is a list of $fun values.  SYMS are globally unique.

Here is an inventory of the kinds of expressions in Guile's CPS language.  Recall that all expressions are wrapped in a $continue term which specifies their continuation.

 -- CPS Expression: $void
     Continue with the unspecified value.

 -- CPS Expression: $const val
     Continue with the constant value VAL.

 -- CPS Expression: $prim name
     Continue with the procedure that implements the primitive operation named by NAME.

 -- CPS Expression: $fun src meta free body
     Continue with a procedure.  SRC identifies the source information for the procedure declaration, and META is the metadata alist as described above in Tree-IL's <lambda>.  FREE is a list of free variables accessed by the procedure.  Early CPS uses an empty list for FREE; only after closure conversion is it correctly populated. Finally, BODY is the $kentry $cont of the procedure entry.

 -- CPS Expression: $call proc args
 -- CPS Expression: $callk label proc args
     Call PROC with the arguments ARGS, and pass all values to the continuation.  PROC and the elements of the ARGS list should all be variable names.  The continuation identified by the term's K should be a $kreceive or a $ktail instance.

     $callk is for the case where the call target is known to be in the same compilation unit.  LABEL should be some continuation label, though it need not be in scope.  In this case the PROC is simply an additional argument, since it is not used to determine the call target at run-time.

 -- CPS Expression: $primcall name args
     Perform the primitive operation identified by name, a well-known symbol, passing it the arguments ARGS, and pass all resulting values to the continuation.  The set of available primitives includes all primitives known to Tree-IL and then some more; see the source code for details.

 -- CPS Expression: $values args
     Pass the values named by the list ARGS to the continuation.

 -- CPS Expression: $prompt escape? tag handler
     Push a prompt on the stack identified by the variable name TAG, which may be escape-only if ESCAPE? is true, and continue with zero values.  If the body aborts to this prompt, control will proceed at the continuation labelled HANDLER, which should be a $kreceive continuation.  Prompts are later popped by pop-prompt primcalls.

The remaining element of the CPS language in Guile is the continuation. In CPS, all continuations have unique labels.  Since this aspect is common to all continuation types, all continuations are contained in a $cont instance:

 -- CPS Continuation Wrapper: $cont k cont
     Declare a continuation labelled K.  All references to the continuation will use this label.

The most common kind of continuation binds some number of values, and then evaluates a sub-term.  $kargs is this kind of simple lambda.

 -- CPS Continuation: $kargs names syms body
     Bind the incoming values to the variables SYMS, with original names NAMES, and then evaluate the sub-term BODY.

Variable names (the names in the SYMS of a $kargs) should be globally unique, and also disjoint from continuation labels.  To bind a value to a variable and then evaluate some term, you would continue with the value to a $kargs that declares one variable.  The bound value would then be available for use within the body of the $kargs.

 -- CPS Continuation: $kif kt kf
     Receive one value.  If it is true for the purposes of Scheme, branch to the continuation labelled KT, passing no values; otherwise, branch to KF.

For internal reasons, only certain terms may continue to a $kif. Compiling $kif avoids allocating space for the test variable, so it needs to be preceded by expressions that can test-and-branch without temporary values.  In practice this condition is true for $primcalls to null?, =, and similar primitives that have corresponding br-if-FOO VM operations; see the source code for full details.  When in doubt, bind the test expression to a variable, and continue to the $kif with a $values expression.  The optimizer should elide the $values if it is not needed.

Calls out to other functions need to be wrapped in a $kreceive continuation in order to adapt the returned values to their uses in the calling function, if any.

 -- CPS Continuation: $kreceive arity k
     Receive values on the stack.  Parse them according to ARITY, and then proceed with the parsed values to the $kargs continuation labelled K.  As a limitation specific to $kreceive, ARITY may only contain required and rest arguments.

$arity is a helper data structure used by $kreceive and also by $kclause, described below.

 -- CPS Data: $arity req opt rest kw allow-other-keys?
     A data type declaring an arity.  REQ and OPT are lists of source names of required and optional arguments, respectively. REST is either the source name of the rest variable, or #f if this arity does not accept additional values.  KW is a list of the form ((KEYWORD NAME VAR) ...), describing the keyword arguments.  ALLOW-OTHER-KEYS? is true if other keyword arguments are allowed and false otherwise.

     Note that all of these names with the exception of the VARs in the KW list are source names, not unique variable names.

Additionally, there are three specific kinds of continuations that can only be declared at function entries.

 -- CPS Continuation: $kentry self tail clauses
     Declare a function entry.  SELF is a variable bound to the procedure being called, and which may be used for self-references. TAIL declares the $cont wrapping the $ktail for this function, corresponding to the function's tail continuation. CLAUSES is a list of $kclause $cont instances.

 -- CPS Continuation: $ktail
     A tail continuation.

 -- CPS Continuation: $kclause arity cont
     A clause of a function with a given arity.  Applications of a function with a compatible set of actual arguments will continue to CONT, a $kargs $cont instance representing the clause body.

Building CPS
............

Unlike Tree-IL, the CPS language is built to be constructed and deconstructed with abstract macros instead of via procedural constructors or accessors, or instead of S-expression matching.

Deconstruction and matching is handled adequately by the match form from (ice-9 match).  See Pattern Matching.  Construction is handled by a set of mutually recursive builder macros: build-cps-term, build-cps-cont, and build-cps-exp.

In the following interface definitions, consider variables containing cont to be recursively build by build-cps-cont, and likewise for term and exp.  Consider any other name to be evaluated as a Scheme expression.  Many of these forms recognize unquote in some contexts, to splice in a previously-built value; see the specifications below for full details.

 -- Scheme Syntax: build-cps-term ,val
 -- Scheme Syntax: build-cps-term ($letk (cont ...) term)
 -- Scheme Syntax: build-cps-term ($letrec names syms funs term)
 -- Scheme Syntax: build-cps-term ($continue k src exp)
 -- Scheme Syntax: build-cps-exp ,val
 -- Scheme Syntax: build-cps-exp ($void)
 -- Scheme Syntax: build-cps-exp ($const val)
 -- Scheme Syntax: build-cps-exp ($prim name)
 -- Scheme Syntax: build-cps-exp ($fun src meta free body)
 -- Scheme Syntax: build-cps-exp ($call proc (arg ...))
 -- Scheme Syntax: build-cps-exp ($call proc args)
 -- Scheme Syntax: build-cps-exp ($primcall name (arg ...))
 -- Scheme Syntax: build-cps-exp ($primcall name args)
 -- Scheme Syntax: build-cps-exp ($values (arg ...))
 -- Scheme Syntax: build-cps-exp ($values args)
 -- Scheme Syntax: build-cps-exp ($prompt escape? tag handler)
 -- Scheme Syntax: build-cps-cont ,val
 -- Scheme Syntax: build-cps-cont (k ($kargs (name ...) (sym ...) term))
 -- Scheme Syntax: build-cps-cont (k ($kargs names syms term))
 -- Scheme Syntax: build-cps-cont (k ($kif kt kf))
 -- Scheme Syntax: build-cps-cont (k ($kreceive req rest kargs))
 -- Scheme Syntax: build-cps-cont (k ($kentry self tail-cont ,clauses))
 -- Scheme Syntax: build-cps-cont (k ($kentry self tail-cont (cont ...)))
 -- Scheme Syntax: build-cps-cont (k ($kclause ,arity cont))
 -- Scheme Syntax: build-cps-cont (k ($kclause (req opt rest kw aok?) cont))
     Construct a CPS term, expression, or continuation.

There are a few more miscellaneous interfaces as well.

 -- Scheme Procedure: make-arity req opt rest kw allow-other-keywords?
     A procedural constructor for $arity objects.

 -- Scheme Syntax: let-gensyms (sym ...) body ...
     Bind SYM... to fresh names, and evaluate BODY....

 -- Scheme Syntax: rewrite-cps-term val (pat term) ...
 -- Scheme Syntax: rewrite-cps-exp val (pat exp) ...
 -- Scheme Syntax: rewrite-cps-cont val (pat cont) ...
     Match VAL against the series of patterns PAT..., using match.  The body of the matching clause should be a template in the syntax of build-cps-term, build-cps-exp, or build-cps-cont, respectively.

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

Compiling CPS in Guile has three phases: conversion, optimization, and code generation.

CPS conversion is the process of taking a higher-level language and compiling it to CPS.  Source languages can do this directly, or they can convert to Tree-IL (which is probably easier) and let Tree-IL convert to CPS later.  Going through Tree-IL has the advantage of running Tree-IL optimization passes, like partial evaluation.  Also, the compiler from Tree-IL to CPS handles assignment conversion, in which assigned local variables (in Tree-IL, locals that are <lexical-set>) are converted to being boxed values on the heap.  See Variables and the VM.

After CPS conversion, Guile runs some optimization passes.  The major optimization performed on CPS is contification, in which functions that are always called with the same continuation are incorporated directly into a function's body.  This opens up space for more optimizations, and turns procedure calls into goto.  It can also make loops out of recursive function nests.

At the time of this writing (2014), most high-level optimization in Guile is done on Tree-IL.  We would like to rewrite many of these passes to operate on CPS instead, as it is easier to reason about CPS.

The rest of the optimization passes are really cleanups and canonicalizations.  CPS spans the gap between high-level languages and low-level bytecodes, which allows much of the compilation process to be expressed as source-to-source transformations.  Such is the case for closure conversion, in which references to variables that are free in a function are converted to closure references, and in which functions are converted to closures.  There are a few more passes to ensure that the only primcalls left in the term are those that have a corresponding instruction in the virtual machine, and that their continuations expect the right number of values.

Finally, the backend of the CPS compiler emits bytecode for each function, one by one.  To do so, it determines the set of live variables at all points in the function.  Using this liveness information, it allocates stack slots to each variable, such that a variable can live in one slot for the duration of its lifetime, without shuffling.  (Of course, variables with disjoint lifetimes can share a slot.)  Finally the backend emits code, typically just one VM instruction, for each continuation in the function.

Bytecode
--------

As mentioned before, Guile compiles all code to bytecode, and that bytecode is contained in ELF images.  See Object File Format, for more on Guile's use of ELF.

To produce a bytecode image, Guile provides an assembler and a linker.

The assembler, defined in the (system vm assembler) module, has a relatively straightforward imperative interface.  It provides a make-assembler function to instantiate an assembler and a set of emit-INST procedures to emit instructions of each kind.

The emit-INST procedures are actually generated at compile-time from a machine-readable description of the VM.  With a few exceptions for certain operand types, each operand of an emit procedure corresponds to an operand of the corresponding instruction.

Consider vector-length, from see Miscellaneous Instructions. It is documented as:

 -- Instruction: vector-length u12:DST u12:SRC

Therefore the emit procedure has the form:

 -- Scheme Procedure: emit-vector-length asm dst src

All emit procedure take the assembler as their first argument, and return no useful values.

The argument types depend on the operand types.  See Instruction Set. Most are integers within a restricted range, though labels are generally expressed as opaque symbols.

There are a few macro-instructions as well.

 -- Scheme Procedure: emit-label asm label
     Define a label at the current program point.

 -- Scheme Procedure: emit-source asm source
     Associate SOURCE with the current program point.

 -- Scheme Procedure: emit-cache-current-module! asm module scope
 -- Scheme Procedure: emit-cached-toplevel-box asm dst scope sym bound?
 -- Scheme Procedure: emit-cached-module-box asm dst module-name sym public? bound?
     Macro-instructions to implement caching of top-level variables.  The first takes the current module, in the slot MODULE, and associates it with a cache location identified by SCOPE.  The second takes a SCOPE, and resolves the variable.  See Top-Level Environment Instructions.  The last does not need a cached module, rather taking the module name directly.

 -- Scheme Procedure: emit-load-constant asm dst constant
     Load the Scheme datum CONSTANT into DST.

 -- Scheme Procedure: emit-begin-program asm label properties
 -- Scheme Procedure: emit-end-program asm
     Delimit the bounds of a procedure, with the given LABEL and the metadata PROPERTIES.

 -- Scheme Procedure: emit-load-static-procedure asm dst label
     Load a procedure with the given LABEL into local DST.  This macro-instruction should only be used with procedures without free variables -- procedures that are not closures.

 -- Scheme Procedure: emit-begin-standard-arity asm req nlocals alternate
 -- Scheme Procedure: emit-begin-opt-arity asm req opt rest nlocals alternate
 -- Scheme Procedure: emit-begin-kw-arity asm req opt rest kw-indices allow-other-keys? nlocals alternate
 -- Scheme Procedure: emit-end-arity asm
     Delimit a clause of a procedure.

 -- Scheme Procedure: emit-br-if-symbol asm slot invert? label
 -- Scheme Procedure: emit-br-if-variable asm slot invert? label
 -- Scheme Procedure: emit-br-if-vector asm slot invert? label
 -- Scheme Procedure: emit-br-if-string asm slot invert? label
 -- Scheme Procedure: emit-br-if-bytevector asm slot invert? label
 -- Scheme Procedure: emit-br-if-bitvector asm slot invert? label
     TC7-specific test-and-branch instructions.  The TC7 is a 7-bit code that is part of a heap object's type.  See The SCM Type in Guile.  Also, see Branch Instructions.

The linker is a complicated beast.  Hackers interested in how it works would do well do read Ian Lance Taylor's series of articles on linkers. Searching the internet should find them easily.  From the user's perspective, there is only one knob to control: whether the resulting image will be written out to a file or not.  If the user passes #:to-file? #t as part of the compiler options (see The Scheme Compiler), the linker will align the resulting segments on page boundaries, and otherwise not.

 -- Scheme Procedure: link-assembly asm #:page-aligned?=#t
     Link an ELF image, and return the bytevector.  If PAGE-ALIGNED? is true, Guile will align the segments with different permissions on page-sized boundaries, in order to maximize code sharing between different processes.  Otherwise, padding is minimized, to minimize address space consumption.

To write an image to disk, just use put-bytevector from (ice-9 binary-ports).

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.  Procedures to load images can be found in the (system vm loader) module:

     (use-modules (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.

 -- Scheme Variable: load-thunk-from-memory bv
 -- C Function: scm_load_thunk_from_memory (bv)
     Load object code from a bytevector.  The data will be copied out of the bytevector in order to ensure proper alignment of embedded Scheme values.

Additionally there are procedures to find the ELF image for a given pointer, or to list all mapped ELF images:

 -- Scheme Variable: find-mapped-elf-image ptr
     Given the integer value PTR, find and return the ELF image that contains that pointer, as a bytevector.  If no image is found, return #f.  This routine is mostly used by debuggers and other introspective tools.

 -- Scheme Variable: all-mapped-elf-images
     Return all mapped ELF images, as a list of bytevectors.

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!