|[ << ]||[ < ]||[ Up ]||[ > ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
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
<const> is a record type with two fields,
exp. Instances of this type are created via
Fields of this type are accessed via the
const-exp procedures. There is also a predicate,
See section 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 section 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
#<const src: #f exp: 3> expression would be:
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)> (apply (primitive +) (const 32) (const 10)) ⇒ 42
src fields are left out of the external representation.
One may create Tree-IL objects from their external representations via
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
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: <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,
consis 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
<primitive-ref>expressions. The actual compilation pass has special cases for applications of certain primitives, like
- 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.
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: <application> src proc args
- External Representation: (apply proc . args)
A procedure call.
- 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
- 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
lambdaexpression in Scheme is treated as a
case-lambdawith one clause.
req is a list of the procedure’s required arguments, as symbols. opt is a list of the optional arguments, or
#fif there are no optional arguments. rest is the name of the rest argument, or
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 a consequent, it should be a
<lambda-case>expression, representing the next clause to try. If there is no consequent, 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*if in-order? is true.
- Scheme Variable: <dynlet> fluids vals body
- External Representation: (dynlet fluids vals body)
Dynamic binding; the equivalent of Scheme’s
with-fluids. fluids should be a list of Tree-IL expressions that will evaluate to fluids, and vals a corresponding list of expressions to bind to the fluids during the dynamic extent of the evaluation of body.
- Scheme Variable: <dynref> fluid
- External Representation: (dynref fluid)
A dynamic variable reference. fluid should be a Tree-IL expression evaluating to a fluid.
- Scheme Variable: <dynset> fluid exp
- External Representation: (dynset fluid exp)
A dynamic variable set. fluid, a Tree-IL expression evaluating to a fluid, will be set to the result of evaluating exp.
- Scheme Variable: <dynwind> winder body unwinder
- External Representation: (dynwind winder body unwinder)
dynamic-wind. winder and unwinder should both evaluate to thunks. Ensure that the winder and the unwinder are called before entering and after leaving body. Note that body is an expression, without a thunk wrapper.
- Scheme Variable: <prompt> tag body handler
- External Representation: (prompt 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, a
<lambda-case>expression with no optional or keyword arguments, and no alternate. The first argument to the
<lambda-case>will be the captured continuation, and then all of the values passed to the abort. See section 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)
receive– binds the values returned by evaluating
lambda-like bindings described by gensyms. That is to say, gensyms may be an improper list.
<let-values>is an optimization of
<application>of the primitive,
- Scheme Variable: <fix> src names gensyms vals body
- External Representation: (fix names gensyms vals body)
<letrec>, but only for vals that are unset
fixis an optimization of
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.
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.
Interested readers are encouraged to read the implementation in
(language tree-il compile-glil) for more details.
|[ << ]||[ < ]||[ Up ]||[ > ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
This document was generated on February 3, 2012 using texi2html 5.0.