@c -*-texinfo-*-
@c This is part of the GNU Guile Reference Manual.
-@c Copyright (C) 2008, 2009, 2010, 2013
+@c Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015
@c Free Software Foundation, Inc.
@c See the file guile.texi for copying conditions.
@node Compiling to the Virtual Machine
@section Compiling to the Virtual Machine
-Compilers have a mystique about them that is attractive and
-off-putting at the same time. They are attractive because they are
-magical -- they transform inert text into live results, like throwing
-the switch on Frankenstein's monster. However, this magic is perceived
-by many to be impenetrable.
-
-This section aims to pay attention to the small man behind the
-curtain.
+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.
@xref{Read/Load/Eval/Compile}, if you're lost and you just wanted to
know how to compile your @code{.scm} file.
* Compiler Tower::
* The Scheme Compiler::
* Tree-IL::
-* GLIL::
-* Assembly::
-* Bytecode and Objcode::
+* Continuation-Passing Style::
+* Bytecode::
* Writing New High-Level Languages::
* Extending the Compiler::
@end menu
@node Compiler Tower
@subsection Compiler Tower
-Guile's compiler is quite simple, actually -- its @emph{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 (@pxref{Instruction Set}).
+Guile's compiler is quite simple -- its @emph{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 (@pxref{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.
+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, @code{(system base language)}:
They are registered with the @code{define-language} form.
@deffn {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]
+ [#: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 @code{#<language>} object, bound to @var{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:
+This syntax defines a @code{<language>} object, bound to @var{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:
@example
(define-language scheme
@end deffn
The interesting thing about having languages defined this way is that
-they present a uniform interface to the read-eval-print loop. This
+they present a uniform interface to the read-eval-print loop. This
allows the user to change the current language of the REPL:
@example
There is a notion of a ``current language'', which is maintained in the
@code{current-language} parameter, defined in the core @code{(guile)}
-module. This language is normally Scheme, and may be rebound by the
-user. The run-time compilation interfaces
+module. This language is normally Scheme, and may be rebound by the
+user. The run-time compilation interfaces
(@pxref{Read/Load/Eval/Compile}) also allow you to choose other source
and target languages.
@itemize
@item Scheme
@item Tree Intermediate Language (Tree-IL)
-@item Guile Lowlevel Intermediate Language (GLIL)
-@item Assembly
+@item Continuation-Passing Style (CPS)
@item Bytecode
-@item Objcode
@end itemize
-Object code may be serialized to disk directly, though it has a cookie
-and version prepended to the front. 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:
+As discussed before (@pxref{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:
@itemize
@item Value
@end itemize
-Compiling to @code{value} loads the object code into a procedure, and
-wakes the sleeping giant.
+Compiling to @code{value} loads the bytecode into a procedure, turning
+cold bytes into warm code.
Perhaps this strangeness can be explained by example:
-@code{compile-file} defaults to compiling to object code, because it
+@code{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 @code{compile} defaults to compiling to
-@code{value}, as its product re-enters the Guile world.
+Guile runtime; but @code{compile} defaults to compiling to @code{value},
+as its product re-enters the Guile world.
+
+@c FIXME: This doesn't work anymore :( Should we add some kind of
+@c special GC pass, or disclaim this kind of code, or what?
Indeed, the process of compilation can circulate through these
different worlds indefinitely, as shown by the following quine:
@node The Scheme Compiler
@subsection 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'' is given by the inventory of constructs provided by
-Tree-IL, the target language of the Scheme compiler: procedure
-applications, conditionals, lexical references, etc. This is described
-more fully in the next section.
+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
+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.
+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
@code{compile} procedure:
@lisp
(compile '(+ 1 2) #:from 'scheme #:to 'tree-il)
@result{}
- #<<application> src: #f
- proc: #<<toplevel-ref> src: #f name: +>
- args: (#<<const> src: #f exp: 1>
- #<<const> src: #f exp: 2>)>
-@end lisp
-
-Or, since Tree-IL is so close to Scheme, it is often useful to expand
-Scheme to Tree-IL, then translate back to Scheme. For that reason the
-expander provides two interfaces. The former is equivalent to calling
-@code{(macroexpand '(+ 1 2) 'c)}, where the @code{'c} is for
-``compile''. With @code{'e} (the default), the result is translated
-back to Scheme:
-
-@lisp
-(macroexpand '(+ 1 2))
-@result{} (+ 1 2)
-(macroexpand '(let ((x 10)) (* x x)))
-@result{} (let ((x84 10)) (* x84 x84))
+#<tree-il (call (toplevel +) (const 1) (const 2))>
@end lisp
-The second example shows that as part of its job, the macro expander
-renames lexically-bound variables. The original names are preserved
-when compiling to Tree-IL, but can't be represented in Scheme: a
-lexical binding only has one name. It is for this reason that the
-@emph{native} output of the expander is @emph{not} Scheme. There's too
-much information we would lose if we translated to Scheme directly:
-lexical variable names, source locations, and module hygiene.
-
-Note however that @code{macroexpand} does not have the same signature
-as @code{compile-tree-il}. @code{compile-tree-il} is a small wrapper
-around @code{macroexpand}, to make it conform to the general form of
-compiler procedures in Guile's language tower.
+@code{(compile @var{foo} #:from 'scheme #:to 'tree-il)} is entirely
+equivalent to calling the macro expander as @code{(macroexpand @var{foo}
+'c '(compile load eval))}. @xref{Macro Expansion}.
+@code{compile-tree-il}, the procedure dispatched by @code{compile} to
+@code{'tree-il}, is a small wrapper around @code{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:
@example
scheme@@(guile-user)> ,language tree-il
Happy hacking with Tree Intermediate Language! To switch back, type `,L scheme'.
-tree-il@@(guile-user)> (apply (primitive +) (const 32) (const 10))
+tree-il@@(guile-user)> (call (primitive +) (const 32) (const 10))
@result{} 42
@end example
@deftp {Scheme Variable} <void> src
@deftpx {External Representation} (void)
-An empty expression. In practice, equivalent to Scheme's @code{(if #f
+An empty expression. In practice, equivalent to Scheme's @code{(if #f
#f)}.
@end deftp
+
@deftp {Scheme Variable} <const> src exp
@deftpx {External Representation} (const @var{exp})
A constant.
@end deftp
+
@deftp {Scheme Variable} <primitive-ref> src name
@deftpx {External Representation} (primitive @var{name})
-A reference to a ``primitive''. A primitive is a procedure that, when
-compiled, may be open-coded. For example, @code{cons} is usually
+A reference to a ``primitive''. A primitive is a procedure that, when
+compiled, may be open-coded. For example, @code{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
@code{<module-ref>} and @code{<toplevel-ref>} expressions to
-@code{<primitive-ref>} expressions. The actual compilation pass
-has special cases for applications of certain primitives, like
-@code{apply} or @code{cons}.
+@code{<primitive-ref>} expressions. The actual compilation pass has
+special cases for calls to certain primitives, like @code{apply} or
+@code{cons}.
@end deftp
+
@deftp {Scheme Variable} <lexical-ref> src name gensym
@deftpx {External Representation} (lexical @var{name} @var{gensym})
-A reference to a lexically-bound variable. The @var{name} is the
+A reference to a lexically-bound variable. The @var{name} is the
original name of the variable in the source program. @var{gensym} is a
unique identifier for this variable.
@end deftp
+
@deftp {Scheme Variable} <lexical-set> src name gensym exp
@deftpx {External Representation} (set! (lexical @var{name} @var{gensym}) @var{exp})
Sets a lexically-bound variable.
@end deftp
+
@deftp {Scheme Variable} <module-ref> src mod name public?
@deftpx {External Representation} (@@ @var{mod} @var{name})
@deftpx {External Representation} (@@@@ @var{mod} @var{name})
otherwise it will be looked up among the module's private bindings,
and is serialized with @code{@@@@}.
@end deftp
+
@deftp {Scheme Variable} <module-set> src mod name public? exp
@deftpx {External Representation} (set! (@@ @var{mod} @var{name}) @var{exp})
@deftpx {External Representation} (set! (@@@@ @var{mod} @var{name}) @var{exp})
Sets a variable in a specific module.
@end deftp
+
@deftp {Scheme Variable} <toplevel-ref> src name
@deftpx {External Representation} (toplevel @var{name})
References a variable from the current procedure's module.
@end deftp
+
@deftp {Scheme Variable} <toplevel-set> src name exp
@deftpx {External Representation} (set! (toplevel @var{name}) @var{exp})
Sets a variable in the current procedure's module.
@end deftp
+
@deftp {Scheme Variable} <toplevel-define> src name exp
@deftpx {External Representation} (define (toplevel @var{name}) @var{exp})
Defines a new top-level variable in the current procedure's module.
@end deftp
+
@deftp {Scheme Variable} <conditional> src test then else
@deftpx {External Representation} (if @var{test} @var{then} @var{else})
A conditional. Note that @var{else} is not optional.
@end deftp
-@deftp {Scheme Variable} <application> src proc args
-@deftpx {External Representation} (apply @var{proc} . @var{args})
+
+@deftp {Scheme Variable} <call> src proc args
+@deftpx {External Representation} (call @var{proc} . @var{args})
A procedure call.
@end deftp
-@deftp {Scheme Variable} <sequence> src exps
-@deftpx {External Representation} (begin . @var{exps})
-Like Scheme's @code{begin}.
+
+@deftp {Scheme Variable} <primcall> src name args
+@deftpx {External Representation} (primcall @var{name} . @var{args})
+A call to a primitive. Equivalent to @code{(call (primitive @var{name})
+. @var{args})}. This construct is often more convenient to generate and
+analyze than @code{<call>}.
+
+As part of the compilation process, instances of @code{(call (primitive
+@var{name}) . @var{args})} are transformed into primcalls.
+@end deftp
+
+@deftp {Scheme Variable} <seq> src head tail
+@deftpx {External Representation} (seq @var{head} @var{tail})
+A sequence. The semantics is that @var{head} is evaluated first, and
+any resulting values are ignored. Then @var{tail} is evaluated, in tail
+position.
@end deftp
+
@deftp {Scheme Variable} <lambda> src meta body
@deftpx {External Representation} (lambda @var{meta} @var{body})
-A closure. @var{meta} is an association list of properties for the
-procedure. @var{body} is a single Tree-IL expression of type
-@code{<lambda-case>}. As the @code{<lambda-case>} clause can chain to
+A closure. @var{meta} is an association list of properties for the
+procedure. @var{body} is a single Tree-IL expression of type
+@code{<lambda-case>}. As the @code{<lambda-case>} clause can chain to
an alternate clause, this makes Tree-IL's @code{<lambda>} have the
expressiveness of Scheme's @code{case-lambda}.
@end deftp
+
@deftp {Scheme Variable} <lambda-case> req opt rest kw inits gensyms body alternate
@deftpx {External Representation} @
(lambda-case ((@var{req} @var{opt} @var{rest} @var{kw} @var{inits} @var{gensyms})@
@var{body})@
[@var{alternate}])
-One clause of a @code{case-lambda}. A @code{lambda} expression in
+One clause of a @code{case-lambda}. A @code{lambda} expression in
Scheme is treated as a @code{case-lambda} with one clause.
@var{req} is a list of the procedure's required arguments, as symbols.
@var{kw} is a list of the form, @code{(@var{allow-other-keys?}
(@var{keyword} @var{name} @var{var}) ...)}, where @var{keyword} is the
keyword corresponding to the argument named @var{name}, and whose
-corresponding gensym is @var{var}. @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.
+corresponding gensym is @var{var}. @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 @var{init} expression is evaluated in the lexical context of
previously bound variables, from left to right.
first all of the required arguments, then the optional arguments if
any, then the rest argument if any, then all of the keyword arguments.
-@var{body} is the body of the clause. If the procedure is called with
+@var{body} is the body of the clause. If the procedure is called with
an appropriate number of arguments, @var{body} is evaluated in tail
-position. Otherwise, if there is an @var{alternate}, it should be a
+position. Otherwise, if there is an @var{alternate}, it should be a
@code{<lambda-case>} expression, representing the next clause to try.
If there is no @var{alternate}, a wrong-number-of-arguments error is
signaled.
@end deftp
+
@deftp {Scheme Variable} <let> src names gensyms vals exp
@deftpx {External Representation} (let @var{names} @var{gensyms} @var{vals} @var{exp})
-Lexical binding, like Scheme's @code{let}. @var{names} are the
-original binding names, @var{gensyms} are gensyms corresponding to the
+Lexical binding, like Scheme's @code{let}. @var{names} are the original
+binding names, @var{gensyms} are gensyms corresponding to the
@var{names}, and @var{vals} are Tree-IL expressions for the values.
@var{exp} is a single Tree-IL expression.
@end deftp
+
@deftp {Scheme Variable} <letrec> in-order? src names gensyms vals exp
@deftpx {External Representation} (letrec @var{names} @var{gensyms} @var{vals} @var{exp})
@deftpx {External Representation} (letrec* @var{names} @var{gensyms} @var{vals} @var{exp})
A version of @code{<let>} that creates recursive bindings, like
Scheme's @code{letrec}, or @code{letrec*} if @var{in-order?} is true.
@end deftp
-@deftp {Scheme Variable} <dynlet> fluids vals body
-@deftpx {External Representation} (dynlet @var{fluids} @var{vals} @var{body})
-Dynamic binding; the equivalent of Scheme's @code{with-fluids}.
-@var{fluids} should be a list of Tree-IL expressions that will
-evaluate to fluids, and @var{vals} a corresponding list of expressions
-to bind to the fluids during the dynamic extent of the evaluation of
-@var{body}.
-@end deftp
-@deftp {Scheme Variable} <dynref> fluid
-@deftpx {External Representation} (dynref @var{fluid})
-A dynamic variable reference. @var{fluid} should be a Tree-IL
-expression evaluating to a fluid.
-@end deftp
-@deftp {Scheme Variable} <dynset> fluid exp
-@deftpx {External Representation} (dynset @var{fluid} @var{exp})
-A dynamic variable set. @var{fluid}, a Tree-IL expression evaluating
-to a fluid, will be set to the result of evaluating @var{exp}.
-@end deftp
-@deftp {Scheme Variable} <dynwind> winder body unwinder
-@deftpx {External Representation} (dynwind @var{winder} @var{body} @var{unwinder})
-A @code{dynamic-wind}. @var{winder} and @var{unwinder} should both
-evaluate to thunks. Ensure that the winder and the unwinder are called
-before entering and after leaving @var{body}. Note that @var{body} is
-an expression, without a thunk wrapper.
-@end deftp
-@deftp {Scheme Variable} <prompt> tag body handler
-@deftpx {External Representation} (prompt @var{tag} @var{body} @var{handler})
-A dynamic prompt. Instates a prompt named @var{tag}, an expression,
+
+@deftp {Scheme Variable} <prompt> escape-only? tag body handler
+@deftpx {External Representation} (prompt @var{escape-only?} @var{tag} @var{body} @var{handler})
+A dynamic prompt. Instates a prompt named @var{tag}, an expression,
during the dynamic extent of the execution of @var{body}, also an
-expression. If an abort occurs to this prompt, control will be passed
-to @var{handler}, a @code{<lambda-case>} expression with no optional
-or keyword arguments, and no alternate. The first argument to the
-@code{<lambda-case>} will be the captured continuation, and then all
-of the values passed to the abort. @xref{Prompts}, for more
-information.
+expression. If an abort occurs to this prompt, control will be passed
+to @var{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
+@var{escape-only?} is true, the handler should be a @code{<lambda>} with
+a single @code{<lambda-case>} body expression with no optional or
+keyword arguments, and no alternate, and whose first argument is
+unreferenced. @xref{Prompts}, for more information.
@end deftp
+
@deftp {Scheme Variable} <abort> tag args tail
@deftpx {External Representation} (abort @var{tag} @var{args} @var{tail})
An abort to the nearest prompt with the name @var{tag}, an expression.
@var{args} should be a list of expressions to pass to the prompt's
handler, and @var{tail} should be an expression that will evaluate to
-a list of additional arguments. An abort will save the partial
+a list of additional arguments. An abort will save the partial
continuation, which may later be reinstated, resulting in the
@code{<abort>} expression evaluating to some number of values.
@end deftp
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.
+compiler does. Users should not generate these expressions directly,
+unless they feel very clever, as the default analysis pass will generate
+them as necessary.
@deftp {Scheme Variable} <let-values> src names gensyms exp body
@deftpx {External Representation} (let-values @var{names} @var{gensyms} @var{exp} @var{body})
Like Scheme's @code{receive} -- binds the values returned by
evaluating @code{exp} to the @code{lambda}-like bindings described by
-@var{gensyms}. That is to say, @var{gensyms} may be an improper list.
+@var{gensyms}. That is to say, @var{gensyms} may be an improper list.
-@code{<let-values>} is an optimization of @code{<application>} of the
+@code{<let-values>} is an optimization of a @code{<call>} to the
primitive, @code{call-with-values}.
@end deftp
+
@deftp {Scheme Variable} <fix> src names gensyms vals body
@deftpx {External Representation} (fix @var{names} @var{gensyms} @var{vals} @var{body})
Like @code{<letrec>}, but only for @var{vals} that are unset
@code{fix} is an optimization of @code{letrec} (and @code{let}).
@end deftp
-Tree-IL implements a compiler to GLIL that recursively traverses
-Tree-IL expressions, writing out GLIL expressions into a linear list.
-The compiler also keeps some state as to whether the current
-expression is in tail context, and whether its value will be used in
-future computations. This state allows the compiler not to emit code
-for constant expressions that will not be used (e.g.@: docstrings), and
-to perform tail calls when in tail position.
+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.
-Most optimization, such as it currently is, is performed on Tree-IL
-expressions as source-to-source transformations. There will be more
-optimizations added in the future.
+Optimization passes performed on Tree-IL currently include:
-Interested readers are encouraged to read the implementation in
-@code{(language tree-il compile-glil)} for more details.
+@itemize
+@item Open-coding (turning toplevel-refs into primitive-refs,
+and calls to primitives to primcalls)
+@item Partial evaluation (comprising inlining, copy propagation, and
+constant folding)
+@item Common subexpression elimination (CSE)
+@end itemize
+
+In the future, we will move the CSE pass to operate over the lower-level
+CPS language.
+
+@node Continuation-Passing Style
+@subsection Continuation-Passing Style
+
+@cindex CPS
+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.
+
+@menu
+* An Introduction to CPS::
+* CPS in Guile::
+* Building CPS::
+* Compiling CPS::
+@end menu
+
+@node An Introduction to CPS
+@subsubsection An Introduction to CPS
+
+Consider the following Scheme expression:
+
+@lisp
+(begin
+ (display "The sum of 32 and 10 is: ")
+ (display 42)
+ (newline))
+@end lisp
+
+Let us identify all of the sub-expressions in this expression,
+annotating them with unique labels:
-@node GLIL
-@subsection GLIL
+@lisp
+(begin
+ (display "The sum of 32 and 10 is: ")
+ |k1 k2
+ k0
+ (display 42)
+ |k4 k5
+ k3
+ (newline))
+ |k7
+ k6
+@end lisp
+
+Each of these labels identifies a point in a program. One label may be
+the continuation of another label. For example, the continuation of
+@code{k7} is @code{k6}. This is because after evaluating the value of
+@code{newline}, performed by the expression labelled @code{k7}, we
+continue to apply it in @code{k6}.
+
+Which expression has @code{k0} as its continuation? It is either the
+expression labelled @code{k1} or the expression labelled @code{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 @code{k1} is @code{k2}, and the continuation of
+@code{k2} is @code{k0}.
+
+With this example established, we are ready to give an example of CPS in
+Scheme:
+
+@smalllisp
+(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))
+@end smalllisp
+
+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 @code{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, @code{k4}, takes any number of values and ignores them.
+Compare this to @code{k2}, which takes a single value; in this way we
+can say that @code{k1} is in a ``value'' context. Likewise @code{k6} is
+in tail context with respect to the expression as a whole, because its
+continuation is the tail continuation, @code{ktail}. CPS makes these
+details manifest, and gives them names.
+
+@node CPS in Guile
+@subsubsection CPS in Guile
+
+Guile's CPS language is composed of @dfn{terms}, @dfn{expressions},
+and @dfn{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.
+
+@deftp {CPS Term} $continue k src exp
+Evaluate the expression @var{exp} and pass the resulting values (if any)
+to the continuation labelled @var{k}. The source information associated
+with the expression may be found in @var{src}, which is either an alist
+as in @code{source-properties} or is @code{#f} if there is no associated
+source.
+@end deftp
-Guile Lowlevel Intermediate Language (GLIL) is a structured intermediate
-language whose expressions more closely approximate Guile's VM
-instruction set. Its expression types are defined in @code{(language
-glil)}.
+@deftp {CPS Term} $letk conts body
+Bind @var{conts}, a list of continuations (@code{$cont} instances), in
+the scope of the sub-term @var{body}. The continuations are mutually
+recursive.
+@end deftp
-@deftp {Scheme Variable} <glil-program> meta . body
-A unit of code that at run-time will correspond to a compiled
-procedure. @var{meta} should be an alist of properties, as in
-Tree-IL's @code{<lambda>}. @var{body} is an ordered list of GLIL
+Additionally, the early stages of CPS allow for a set of mutually
+recursive functions to be declared as a term. This @code{$letrec} type
+is like Tree-IL's @code{<fix>}. The contification pass will attempt to
+transform the functions declared in a @code{$letrec} into local
+continuations. Any remaining functions are later lowered to @code{$fun}
expressions.
+
+@deftp {CPS Term} $letrec names syms funs body
+Declare the mutually recursive set of functions denoted by @var{names},
+@var{syms}, and @var{funs} within the sub-term @var{body}. @var{names}
+and @var{syms} are lists of symbols, and @var{funs} is a list of
+@code{$fun} values. @var{syms} are globally unique.
@end deftp
-@deftp {Scheme Variable} <glil-std-prelude> nreq nlocs else-label
-A prologue for a function with no optional, keyword, or rest
-arguments. @var{nreq} is the number of required arguments. @var{nlocs}
-the total number of local variables, including the arguments. If the
-procedure was not given exactly @var{nreq} arguments, control will
-jump to @var{else-label}, if given, or otherwise signal an error.
-@end deftp
-@deftp {Scheme Variable} <glil-opt-prelude> nreq nopt rest nlocs else-label
-A prologue for a function with optional or rest arguments. Like
-@code{<glil-std-prelude>}, with the addition that @var{nopt} is the
-number of optional arguments (possibly zero) and @var{rest} is an
-index of a local variable at which to bind a rest argument, or
-@code{#f} if there is no rest argument.
-@end deftp
-@deftp {Scheme Variable} <glil-kw-prelude> nreq nopt rest kw allow-other-keys? nlocs else-label
-A prologue for a function with keyword arguments. Like
-@code{<glil-opt-prelude>}, with the addition that @var{kw} is a list
-of keyword arguments, and @var{allow-other-keys?} is a flag indicating
-whether to allow unknown keys. @xref{Function Prologue Instructions,
-@code{bind-kwargs}}, for details on the format of @var{kw}.
-@end deftp
-@deftp {Scheme Variable} <glil-bind> . vars
-An advisory expression that notes a liveness extent for a set of
-variables. @var{vars} is a list of @code{(@var{name} @var{type}
-@var{index})}, where @var{type} should be either @code{argument},
-@code{local}, or @code{external}.
-
-@code{<glil-bind>} expressions end up being serialized as part of a
-program's metadata and do not form part of a program's code path.
-@end deftp
-@deftp {Scheme Variable} <glil-mv-bind> vars rest
-A multiple-value binding of the values on the stack to @var{vars}. Iff
-@var{rest} is true, the last element of @var{vars} will be treated as
-a rest argument.
-
-In addition to pushing a binding annotation on the stack, like
-@code{<glil-bind>}, an expression is emitted at compilation time to
-make sure that there are enough values available to bind. See the
-notes on @code{truncate-values} in @ref{Procedure Call and Return
-Instructions}, for more information.
-@end deftp
-@deftp {Scheme Variable} <glil-unbind>
-Closes the liveness extent of the most recently encountered
-@code{<glil-bind>} or @code{<glil-mv-bind>} expression. As GLIL
-expressions are compiled, a parallel stack of live bindings is
-maintained; this expression pops off the top element from that stack.
-
-Bindings are written into the program's metadata so that debuggers and
-other tools can determine the set of live local variables at a given
-offset within a VM program.
-@end deftp
-@deftp {Scheme Variable} <glil-source> loc
-Records source information for the preceding expression. @var{loc}
-should be an association list of containing @code{line} @code{column},
-and @code{filename} keys, e.g.@: as returned by
-@code{source-properties}.
-@end deftp
-@deftp {Scheme Variable} <glil-void>
-Pushes ``the unspecified value'' on the stack.
-@end deftp
-@deftp {Scheme Variable} <glil-const> obj
-Pushes a constant value onto the stack. @var{obj} must be a number,
-string, symbol, keyword, boolean, character, uniform array, the empty
-list, or a pair or vector of constants.
-@end deftp
-@deftp {Scheme Variable} <glil-lexical> local? boxed? op index
-Accesses a lexically bound variable. If the variable is not
-@var{local?} it is free. All variables may have @code{ref},
-@code{set}, and @code{bound?} as their @var{op}. Boxed variables may
-also have the @var{op}s @code{box}, @code{empty-box}, and @code{fix},
-which correspond in semantics to the VM instructions @code{box},
-@code{empty-box}, and @code{fix-closure}. @xref{Stack Layout}, for
-more information.
-@end deftp
-@deftp {Scheme Variable} <glil-toplevel> op name
-Accesses a toplevel variable. @var{op} may be @code{ref}, @code{set},
-or @code{define}.
-@end deftp
-@deftp {Scheme Variable} <glil-module> op mod name public?
-Accesses a variable within a specific module. See Tree-IL's
-@code{<module-ref>}, for more information.
-@end deftp
-@deftp {Scheme Variable} <glil-label> label
-Creates a new label. @var{label} can be any Scheme value, and should
-be unique.
-@end deftp
-@deftp {Scheme Variable} <glil-branch> inst label
-Branch to a label. @var{label} should be a @code{<ghil-label>}.
-@code{inst} is a branching instruction: @code{br-if}, @code{br}, etc.
-@end deftp
-@deftp {Scheme Variable} <glil-call> inst nargs
-This expression is probably misnamed, as it does not correspond to
-function calls. @code{<glil-call>} invokes the VM instruction named
-@var{inst}, noting that it is called with @var{nargs} stack arguments.
-The arguments should be pushed on the stack already. What happens to
-the stack afterwards depends on the instruction.
-@end deftp
-@deftp {Scheme Variable} <glil-mv-call> nargs ra
-Performs a multiple-value call. @var{ra} is a @code{<glil-label>}
-corresponding to the multiple-value return address for the call. See
-the notes on @code{mv-call} in @ref{Procedure Call and Return
-Instructions}, for more information.
-@end deftp
-@deftp {Scheme Variable} <glil-prompt> label escape-only?
-Push a dynamic prompt into the stack, with a handler at @var{label}.
-@var{escape-only?} is a flag that is propagated to the prompt,
-allowing an abort to avoid capturing a continuation in some cases.
-@xref{Prompts}, for more information.
-@end deftp
-
-Users may enter in GLIL at the REPL as well, though there is a bit
-more bookkeeping to do:
-@example
-scheme@@(guile-user)> ,language glil
-Happy hacking with Guile Lowlevel Intermediate Language (GLIL)!
-To switch back, type `,L scheme'.
-glil@@(guile-user)> (program () (std-prelude 0 0 #f)
- (const 3) (call return 1))
-@result{} 3
-@end example
+A higher-order CPS program is a @code{$cont} containing a @code{$kfun}
+(see below), and the @code{$kfun} which contains clauses and those
+clauses contain terms. A first-order CPS program, on the other hand, is
+the result of closure conversion and does not contain nested functions.
+Closure conversion lifts code for all functions up to the top, collects
+their entry continuations as a list of @code{$cont} @code{$kfun}
+instances and binds them in a @code{$program}.
+
+@deftp {CPS Term} $program funs
+A first-order CPS term declaring a recursive scope for first-order
+functions in a compilation unit. @var{funs} is a list of @code{$cont}
+@code{$kfun} instances. The first entry in the list is the entry
+function for the program.
+@end deftp
-Just as in all of Guile's compilers, an environment is passed to the
-GLIL-to-object code compiler, and one is returned as well, along with
-the object code.
+Here is an inventory of the kinds of expressions in Guile's CPS
+language. Recall that all expressions are wrapped in a @code{$continue}
+term which specifies their continuation.
-@node Assembly
-@subsection Assembly
+@deftp {CPS Expression} $const val
+Continue with the constant value @var{val}.
+@end deftp
-Assembly is an S-expression-based, human-readable representation of
-the actual bytecodes that will be emitted for the VM. As such, it is a
-useful intermediate language both for compilation and for
-decompilation.
+@deftp {CPS Expression} $prim name
+Continue with the procedure that implements the primitive operation
+named by @var{name}.
+@end deftp
-Besides the fact that it is not a record-based language, assembly
-differs from GLIL in four main ways:
+@deftp {CPS Expression} $fun free body
+Continue with a procedure. @var{free} is a list of free variables
+accessed by the procedure. Early CPS uses an empty list for @var{free};
+only after closure conversion is it correctly populated. Finally,
+@var{body} is the @code{$kfun} @code{$cont} of the procedure entry.
+@end deftp
-@itemize
-@item Labels have been resolved to byte offsets in the program.
-@item Constants inside procedures have either been expressed as inline
-instructions or cached in object arrays.
-@item Procedures with metadata (source location information, liveness
-extents, procedure names, generic properties, etc) have had their
-metadata serialized out to thunks.
-@item All expressions correspond directly to VM instructions -- i.e.,
-there is no @code{<glil-lexical>} which can be a ref or a set.
-@end itemize
+@code{$fun} is part of higher-level CPS. After closure conversion,
+@code{$fun} instances are given a concrete representation. By default,
+a closure is represented as an object built by a @code{$closure}
+expression
-Assembly is isomorphic to the bytecode that it compiles to. You can
-compile to bytecode, then decompile back to assembly, and you have the
-same assembly code.
+@deftp {CPS Expression} $closure label nfree
+Build a closure that joins the code at the continuation named
+@var{label} with space for @var{nfree} free variables. The variables
+will be initialized later via @code{free-variable-set!} primcalls.
+@end deftp
-The general form of assembly instructions is the following:
+If the closure can be proven to never escape its scope then other
+lighter-weight representations can be chosen.
+
+@deftp {CPS Expression} $call proc args
+@deftpx {CPS Expression} $callk label proc args
+Call @var{proc} with the arguments @var{args}, and pass all values to
+the continuation. @var{proc} and the elements of the @var{args} list
+should all be variable names. The continuation identified by the term's
+@var{k} should be a @code{$kreceive} or a @code{$ktail} instance.
+
+@code{$callk} is for the case where the call target is known to be in
+the same compilation unit. @var{label} should be some continuation
+label, though it need not be in scope. In this case the @var{proc} is
+simply an additional argument, since it is not used to determine the
+call target at run-time.
+@end deftp
-@lisp
-(@var{inst} @var{arg} ...)
-@end lisp
+@deftp {CPS Expression} $primcall name args
+Perform the primitive operation identified by @code{name}, a well-known
+symbol, passing it the arguments @var{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.
+@end deftp
-The @var{inst} names a VM instruction, and its @var{arg}s will be
-embedded in the instruction stream. The easiest way to see assembly is
-to play around with it at the REPL, as can be seen in this annotated
-example:
+@deftp {CPS Expression} $values args
+Pass the values named by the list @var{args} to the continuation.
+@end deftp
-@example
-scheme@@(guile-user)> ,pp (compile '(+ 32 10) #:to 'assembly)
-(load-program
- ((:LCASE16 . 2)) ; Labels, unused in this case.
- 8 ; Length of the thunk that was compiled.
- (load-program ; Metadata thunk.
- ()
- 17
- #f ; No metadata thunk for the metadata thunk.
- (make-eol)
- (make-eol)
- (make-int8 2) ; Liveness extents, source info, and arities,
- (make-int8 8) ; in a format that Guile knows how to parse.
- (make-int8:0)
- (list 0 3)
- (list 0 1)
- (list 0 3)
- (return))
- (assert-nargs-ee/locals 0) ; Prologue.
- (make-int8 32) ; Actual code starts here.
- (make-int8 10)
- (add)
- (return))
-@end example
+@deftp {CPS Expression} $branch kt exp
+Evaluate the branching expression @var{exp}, and continue to @var{kt}
+with zero values if the test evaluates to true. Otherwise, in the false
+
+Only certain expressions are valid in a @var{$branch}. Compiling a
+@code{$branch} avoids allocating space for the test variable, so the
+expression should be evaluatable without temporary values. In practice
+this condition is true for @code{$primcall}s to @code{null?}, @code{=},
+and similar primitives that have corresponding @code{br-if-@var{foo}} VM
+operations; see the source code for full details. When in doubt, bind
+the test expression to a variable, and reference the variable in the
+@code{$branch} expression. The optimizer should inline the reference if
+possible.
+@end deftp
-Of course you can switch the REPL to assembly and enter in assembly
-S-expressions directly, like with other languages, though it is more
-difficult, given that the length fields have to be correct.
+@deftp {CPS Expression} $prompt escape? tag handler
+Push a prompt on the stack identified by the variable name @var{tag},
+which may be escape-only if @var{escape?} is true, and continue with
+zero values. If the body aborts to this prompt, control will proceed at
+the continuation labelled @var{handler}, which should be a
+@code{$kreceive} continuation. Prompts are later popped by
+@code{pop-prompt} primcalls.
+@end deftp
-@node Bytecode and Objcode
-@subsection Bytecode and Objcode
+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
+@code{$cont} instance:
-Finally, the raw bytes. There are actually two different ``languages''
-here, corresponding to two different ways to represent the bytes.
+@deftp {CPS Continuation Wrapper} $cont k cont
+Declare a continuation labelled @var{k}. All references to the
+continuation will use this label.
+@end deftp
-``Bytecode'' represents code as uniform byte vectors, useful for
-structuring and destructuring code on the Scheme level. Bytecode is
-the next step down from assembly:
+The most common kind of continuation binds some number of values, and
+then evaluates a sub-term. @code{$kargs} is this kind of simple
+@code{lambda}.
-@example
-scheme@@(guile-user)> (compile '(+ 32 10) #:to 'bytecode)
-@result{} #vu8(8 0 0 0 25 0 0 0 ; Header.
- 95 0 ; Prologue.
- 10 32 10 10 148 66 17 ; Actual code.
- 0 0 0 0 0 0 0 9 ; Metadata thunk.
- 9 10 2 10 8 11 18 0 3 18 0 1 18 0 3 66)
-@end example
+@deftp {CPS Continuation} $kargs names syms body
+Bind the incoming values to the variables @var{syms}, with original
+names @var{names}, and then evaluate the sub-term @var{body}.
+@end deftp
-``Objcode'' is bytecode, but mapped directly to a C structure,
-@code{struct scm_objcode}:
+Variable names (the names in the @var{syms} of a @code{$kargs}) should
+be unique among all other variable names. To bind a value to a variable
+and then evaluate some term, you would continue with the value to a
+@code{$kargs} that declares one variable. The bound value would then be
+available for use within the body of the @code{$kargs}.
+
+@deftp {CPS Continuation} $kreceive arity k
+Receive values on the stack. Parse them according to @var{arity}, and
+then proceed with the parsed values to the @code{$kargs} continuation
+labelled @var{k}. As a limitation specific to @code{$kreceive},
+@var{arity} may only contain required and rest arguments.
+@end deftp
-@example
-struct scm_objcode @{
- scm_t_uint32 len;
- scm_t_uint32 metalen;
- scm_t_uint8 base[0];
-@};
-@end example
+@code{$arity} is a helper data structure used by @code{$kreceive} and
+also by @code{$kclause}, described below.
+
+@deftp {CPS Data} $arity req opt rest kw allow-other-keys?
+A data type declaring an arity. @var{req} and @var{opt} are lists of
+source names of required and optional arguments, respectively.
+@var{rest} is either the source name of the rest variable, or @code{#f}
+if this arity does not accept additional values. @var{kw} is a list of
+the form @code{((@var{keyword} @var{name} @var{var}) ...)}, describing
+the keyword arguments. @var{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 @var{var}s in the
+@var{kw} list are source names, not unique variable names.
+@end deftp
+
+Additionally, there are three specific kinds of continuations that can
+only be declared at function entries.
+
+@deftp {CPS Continuation} $kfun src meta self tail clauses
+Declare a function entry. @var{src} is the source information for the
+procedure declaration, and @var{meta} is the metadata alist as described
+above in Tree-IL's @code{<lambda>}. @var{self} is a variable bound to
+the procedure being called, and which may be used for self-references.
+@var{tail} declares the @code{$cont} wrapping the @code{$ktail} for this
+function, corresponding to the function's tail continuation.
+@var{clause} is the first @code{$kclause} @code{$cont} instance for the
+first @code{case-lambda} clause in the function, or otherwise @code{#f}.
+@end deftp
+
+@deftp {CPS Continuation} $ktail
+A tail continuation.
+@end deftp
-As one might imagine, objcode imposes a minimum length on the
-bytecode. Also, the @code{len} and @code{metalen} fields are in native
-endianness, which makes objcode (and bytecode) system-dependent.
-
-Objcode also has a couple of important efficiency hacks. First,
-objcode may be mapped directly from disk, allowing compiled code to be
-loaded quickly, often from the system's disk cache, and shared among
-multiple processes. Secondly, objcode may be embedded in other
-objcode, allowing procedures to have the text of other procedures
-inlined into their bodies, without the need for separate allocation of
-the code. Of course, the objcode object itself does need to be
-allocated.
-
-Procedures related to objcode are defined in the @code{(system vm
-objcode)} module.
-
-@deffn {Scheme Procedure} objcode? obj
-@deffnx {C Function} scm_objcode_p (obj)
-Returns @code{#f} iff @var{obj} is object code, @code{#f} otherwise.
+@deftp {CPS Continuation} $kclause arity cont alternate
+A clause of a function with a given arity. Applications of a function
+with a compatible set of actual arguments will continue to @var{cont}, a
+@code{$kargs} @code{$cont} instance representing the clause body. If
+the arguments are incompatible, control proceeds to @var{alternate},
+which is a @code{$kclause} @code{$cont} for the next clause, or
+@code{#f} if there is no next clause.
+@end deftp
+
+@node Building CPS
+@subsubsection 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 @code{match}
+form from @code{(ice-9 match)}. @xref{Pattern Matching}. Construction
+is handled by a set of mutually recursive builder macros:
+@code{build-cps-term}, @code{build-cps-cont}, and @code{build-cps-exp}.
+
+In the following interface definitions, consider variables containing
+@code{cont} to be recursively build by @code{build-cps-cont}, and
+likewise for @code{term} and @code{exp}. Consider any other name to be
+evaluated as a Scheme expression. Many of these forms recognize
+@code{unquote} in some contexts, to splice in a previously-built value;
+see the specifications below for full details.
+
+@deffn {Scheme Syntax} build-cps-term ,val
+@deffnx {Scheme Syntax} build-cps-term ($letk (cont ...) term)
+@deffnx {Scheme Syntax} build-cps-term ($letrec names syms funs term)
+@deffnx {Scheme Syntax} build-cps-term ($continue k src exp)
+@deffnx {Scheme Syntax} build-cps-term ($program conts)
+@deffnx {Scheme Syntax} build-cps-exp ,val
+@deffnx {Scheme Syntax} build-cps-exp ($const val)
+@deffnx {Scheme Syntax} build-cps-exp ($prim name)
+@deffnx {Scheme Syntax} build-cps-exp ($fun src meta free body)
+@deffnx {Scheme Syntax} build-cps-exp ($call proc (arg ...))
+@deffnx {Scheme Syntax} build-cps-exp ($call proc args)
+@deffnx {Scheme Syntax} build-cps-exp ($primcall name (arg ...))
+@deffnx {Scheme Syntax} build-cps-exp ($primcall name args)
+@deffnx {Scheme Syntax} build-cps-exp ($values (arg ...))
+@deffnx {Scheme Syntax} build-cps-exp ($values args)
+@deffnx {Scheme Syntax} build-cps-exp ($prompt escape? tag handler)
+@deffnx {Scheme Syntax} build-cps-cont ,val
+@deffnx {Scheme Syntax} build-cps-cont (k ($kargs (name ...) (sym ...) term))
+@deffnx {Scheme Syntax} build-cps-cont (k ($kargs names syms term))
+@deffnx {Scheme Syntax} build-cps-cont (k ($kif kt kf))
+@deffnx {Scheme Syntax} build-cps-cont (k ($kreceive req rest kargs))
+@deffnx {Scheme Syntax} build-cps-cont (k ($kentry self tail-cont ,clauses))
+@deffnx {Scheme Syntax} build-cps-cont (k ($kentry self tail-cont (cont ...)))
+@deffnx {Scheme Syntax} build-cps-cont (k ($kclause ,arity cont))
+@deffnx {Scheme Syntax} build-cps-cont (k ($kclause (req opt rest kw aok?) cont))
+Construct a CPS term, expression, or continuation.
@end deffn
-@deffn {Scheme Procedure} bytecode->objcode bytecode
-@deffnx {C Function} scm_bytecode_to_objcode (bytecode)
-Makes a bytecode object from @var{bytecode}, which should be a
-bytevector. @xref{Bytevectors}.
+There are a few more miscellaneous interfaces as well.
+
+@deffn {Scheme Procedure} make-arity req opt rest kw allow-other-keywords?
+A procedural constructor for @code{$arity} objects.
@end deffn
-@deffn {Scheme Variable} load-objcode file
-@deffnx {C Function} scm_load_objcode (file)
-Load object code from a file named @var{file}. The file will be mapped
-into memory via @code{mmap}, so this is a very fast operation.
+@deffn {Scheme Syntax} let-gensyms (sym ...) body ...
+Bind @var{sym...} to fresh names, and evaluate @var{body...}.
+@end deffn
-On disk, object code has an sixteen-byte cookie prepended to it, to
-prevent accidental loading of arbitrary garbage.
+@deffn {Scheme Syntax} rewrite-cps-term val (pat term) ...
+@deffnx {Scheme Syntax} rewrite-cps-exp val (pat exp) ...
+@deffnx {Scheme Syntax} rewrite-cps-cont val (pat cont) ...
+Match @var{val} against the series of patterns @var{pat...}, using
+@code{match}. The body of the matching clause should be a template in
+the syntax of @code{build-cps-term}, @code{build-cps-exp}, or
+@code{build-cps-cont}, respectively.
@end deffn
-@deffn {Scheme Variable} write-objcode objcode file
-@deffnx {C Function} scm_write_objcode (objcode)
-Write object code out to a file, prepending the sixteen-byte cookie.
+@node Compiling CPS
+@subsubsection 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 @code{<lexical-set>}) are
+converted to being boxed values on the heap. @xref{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 @code{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.
+
+
+@node Bytecode
+@subsection Bytecode
+
+As mentioned before, Guile compiles all code to bytecode, and that
+bytecode is contained in ELF images. @xref{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 @code{(system vm assembler)} module, has a
+relatively straightforward imperative interface. It provides a
+@code{make-assembler} function to instantiate an assembler and a set of
+@code{emit-@var{inst}} procedures to emit instructions of each kind.
+
+The @code{emit-@var{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 @code{vector-length}, from @pxref{Miscellaneous Instructions}.
+It is documented as:
+
+@deftypefn Instruction {} vector-length u12:@var{dst} u12:@var{src}
+@end deftypefn
+
+Therefore the emit procedure has the form:
+
+@deffn {Scheme Procedure} emit-vector-length asm dst src
@end deffn
-@deffn {Scheme Variable} objcode->bytecode objcode
-@deffnx {C Function} scm_objcode_to_bytecode (objcode)
-Copy object code out to a bytevector for analysis by Scheme.
+All emit procedure take the assembler as their first argument, and
+return no useful values.
+
+The argument types depend on the operand types. @xref{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.
+
+@deffn {Scheme Procedure} emit-label asm label
+Define a label at the current program point.
+@end deffn
+
+@deffn {Scheme Procedure} emit-source asm source
+Associate @var{source} with the current program point.
+@end deffn
+
+@deffn {Scheme Procedure} emit-cache-current-module! asm module scope
+@deffnx {Scheme Procedure} emit-cached-toplevel-box asm dst scope sym bound?
+@deffnx {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 @var{module}, and associates
+it with a cache location identified by @var{scope}. The second takes a
+@var{scope}, and resolves the variable. @xref{Top-Level Environment
+Instructions}. The last does not need a cached module, rather taking
+the module name directly.
+@end deffn
+
+@deffn {Scheme Procedure} emit-load-constant asm dst constant
+Load the Scheme datum @var{constant} into @var{dst}.
@end deffn
-The following procedure is actually in @code{(system vm program)}, but
-we'll mention it here:
+@deffn {Scheme Procedure} emit-begin-program asm label properties
+@deffnx {Scheme Procedure} emit-end-program asm
+Delimit the bounds of a procedure, with the given @var{label} and the
+metadata @var{properties}.
+@end deffn
+
+@deffn {Scheme Procedure} emit-load-static-procedure asm dst label
+Load a procedure with the given @var{label} into local @var{dst}. This
+macro-instruction should only be used with procedures without free
+variables -- procedures that are not closures.
+@end deffn
+
+@deffn {Scheme Procedure} emit-begin-standard-arity asm req nlocals alternate
+@deffnx {Scheme Procedure} emit-begin-opt-arity asm req opt rest nlocals alternate
+@deffnx {Scheme Procedure} emit-begin-kw-arity asm req opt rest kw-indices allow-other-keys? nlocals alternate
+@deffnx {Scheme Procedure} emit-end-arity asm
+Delimit a clause of a procedure.
+@end deffn
+
+@deffn {Scheme Procedure} emit-br-if-symbol asm slot invert? label
+@deffnx {Scheme Procedure} emit-br-if-variable asm slot invert? label
+@deffnx {Scheme Procedure} emit-br-if-vector asm slot invert? label
+@deffnx {Scheme Procedure} emit-br-if-string asm slot invert? label
+@deffnx {Scheme Procedure} emit-br-if-bytevector asm slot invert? label
+@deffnx {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. @xref{The SCM Type in Guile}. Also,
+@xref{Branch Instructions}.
+@end deffn
-@deffn {Scheme Variable} make-program objcode objtable [free-vars=#f]
-@deffnx {C Function} scm_make_program (objcode, objtable, free_vars)
-Load up object code into a Scheme program. The resulting program will
-have @var{objtable} as its object table, which should be a vector or
-@code{#f}, and will capture the free variables from @var{free-vars}.
+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
+@code{#:to-file? #t} as part of the compiler options (@pxref{The Scheme
+Compiler}), the linker will align the resulting segments on page
+boundaries, and otherwise not.
+
+@deffn {Scheme Procedure} link-assembly asm #:page-aligned?=#t
+Link an ELF image, and return the bytevector. If @var{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.
@end deffn
-Object code from a file may be disassembled at the REPL via the
-meta-command @code{,disassemble-file}, abbreviated as @code{,xx}.
-Programs may be disassembled via @code{,disassemble}, abbreviated as
-@code{,x}.
+To write an image to disk, just use @code{put-bytevector} from
+@code{(ice-9 binary-ports)}.
Compiling object code to the fake language, @code{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.
+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 @code{(system vm loader)} module:
+
+@lisp
+(use-modules (system vm loader))
+@end lisp
+
+@deffn {Scheme Variable} load-thunk-from-file file
+@deffnx {C Function} scm_load_thunk_from_file (file)
+Load object code from a file named @var{file}. The file will be mapped
+into memory via @code{mmap}, so this is a very fast operation.
+@end deffn
+
+@deffn {Scheme Variable} load-thunk-from-memory bv
+@deffnx {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.
+@end deffn
+
+Additionally there are procedures to find the ELF image for a given
+pointer, or to list all mapped ELF images:
+
+@deffn {Scheme Variable} find-mapped-elf-image ptr
+Given the integer value @var{ptr}, find and return the ELF image that
+contains that pointer, as a bytevector. If no image is found, return
+@code{#f}. This routine is mostly used by debuggers and other
+introspective tools.
+@end deffn
+
+@deffn {Scheme Variable} all-mapped-elf-images
+Return all mapped ELF images, as a list of bytevectors.
+@end deffn
@node Writing New High-Level Languages
HCoop / bpt / guile.git / blobdiff