code:
@c -*-texinfo-*-
@c This is part of the GNU Guile Reference Manual.
@c Copyright (C)  1996, 1997, 2000, 2001, 2002, 2003, 2004, 2009
@c   Free Software Foundation, Inc.
@c See the file guile.texi for copying conditions.

@page
@node Autoconf Support
@chapter Autoconf Support

When Guile is installed, a pkg-config description file and a set of
Autoconf macros is installed.  This chapter documents pkg-config and
Autoconf support, as well as the high-level guile-tool Autofrisk.

@menu
* Autoconf Background::         Why use autoconf?
* Autoconf Macros::             The GUILE_* macros.
* Using Autoconf Macros::       How to use them, plus examples.
* Autofrisk::                   AUTOFRISK_CHECKS and AUTOFRISK_SUMMARY.
* Using Autofrisk::             Example modules.af files.
@end menu

@node Autoconf Background
@section Autoconf Background

As explained in the @cite{GNU Autoconf Manual}, any package needs
configuration at build-time (@pxref{Top, ,Introduction,autoconf,The GNU
Autoconf Manual}).  If your package uses Guile (or uses a package that
in turn uses Guile), you probably need to know what specific Guile
features are available and details about them.

The way to do this is to write feature tests and arrange for their execution
by the @file{configure} script, typically by adding the tests to
@file{configure.ac}, and running @code{autoconf} to create @file{configure}.
Users of your package then run @file{configure} in the normal way.

Macros are a way to make common feature tests easy to express.
Autoconf provides a wide range of macros
(@pxref{Existing Tests,,,autoconf,The GNU Autoconf Manual}),
and Guile installation provides Guile-specific tests in the areas of:
program detection, compilation flags reporting, and Scheme module
checks.

@node Autoconf Macros
@section Autoconf Macros

@cindex pkg-config
@cindex autoconf

GNU Guile provides a @dfn{pkg-config} description file, which contains
all the information necessary to compile and link C applications that
use Guile.  The @code{pkg-config} program is able to read this file
and provide this information to application programmers; it can be
obtained at @url{http://pkg-config.freedesktop.org/}.

The following command lines give respectively the C compilation and link
flags needed to build Guile-using programs:

@example
pkg-config guile-@value{EFFECTIVE-VERSION} --cflags
pkg-config guile-@value{EFFECTIVE-VERSION} --libs
@end example

To ease use of pkg-config with Autoconf, pkg-config comes with a
convenient Autoconf macro.  The following example looks for Guile and
sets the @code{GUILE_CFLAGS} and @code{GUILE_LIBS} variables
accordingly, or prints an error and exits if Guile was not found:

@findex PKG_CHECK_MODULES

@example
PKG_CHECK_MODULES([GUILE], [guile-@value{EFFECTIVE-VERSION}])
@end example

Guile comes with additional Autoconf macros providing more information,
installed as @file{@var{prefix}/share/aclocal/guile.m4}.  Their names
all begin with @code{GUILE_}.

@c see Makefile.am
@include autoconf-macros.texi

@node Using Autoconf Macros
@section Using Autoconf Macros

Using the autoconf macros is straightforward: Add the macro "calls" (actually
instantiations) to @file{configure.ac}, run @code{aclocal}, and finally,
run @code{autoconf}.  If your system doesn't have guile.m4 installed, place
the desired macro definitions (@code{AC_DEFUN} forms) in @file{acinclude.m4},
and @code{aclocal} will do the right thing.

Some of the macros can be used inside normal shell constructs: @code{if foo ;
then GUILE_BAZ ; fi}, but this is not guaranteed.  It's probably a good idea
to instantiate macros at top-level.

We now include two examples, one simple and one complicated.

The first example is for a package that uses libguile, and thus needs to know
how to compile and link against it.  So we use @code{GUILE_FLAGS} to set the
vars @code{GUILE_CFLAGS} and @code{GUILE_LDFLAGS}, which are automatically
substituted in the Makefile.

@example
In configure.ac:

  GUILE_FLAGS

In Makefile.in:

  GUILE_CFLAGS  = @@GUILE_CFLAGS@@
  GUILE_LDFLAGS = @@GUILE_LDFLAGS@@

  myprog.o: myprog.c
          $(CC) -o $@ $(GUILE_CFLAGS) $<
  myprog: myprog.o
          $(CC) -o $@ $< $(GUILE_LDFLAGS)
@end example

The second example is for a package of Guile Scheme modules that uses an
external program and other Guile Scheme modules (some might call this a "pure
scheme" package).  So we use the @code{GUILE_SITE_DIR} macro, a regular
@code{AC_PATH_PROG} macro, and the @code{GUILE_MODULE_AVAILABLE} macro.

@example
In configure.ac:

  GUILE_SITE_DIR

  probably_wont_work=""

  # pgtype pgtable
  GUILE_MODULE_AVAILABLE(have_guile_pg, (database postgres))
  test $have_guile_pg = no &&
      probably_wont_work="(my pgtype) (my pgtable) $probably_wont_work"

  # gpgutils
  AC_PATH_PROG(GNUPG,gpg)
  test x"$GNUPG" = x &&
      probably_wont_work="(my gpgutils) $probably_wont_work"

  if test ! "$probably_wont_work" = "" ; then
      p="         ***"
      echo
      echo "$p"
      echo "$p NOTE:"
      echo "$p The following modules probably won't work:"
      echo "$p   $probably_wont_work"
      echo "$p They can be installed anyway, and will work if their"
      echo "$p dependencies are installed later.  Please see README."
      echo "$p"
      echo
  fi

In Makefile.in:

  instdir = @@GUILE_SITE@@/my

  install:
        $(INSTALL) my/*.scm $(instdir)
@end example

@node Autofrisk
@section Autofrisk

The @dfn{guile-tools autofrisk} command looks for the file @file{modules.af}
in the current directory and writes out @file{modules.af.m4} containing
autoconf definitions for @code{AUTOFRISK_CHECKS} and @code{AUTOFRISK_SUMMARY}.
@xref{Autoconf Background}, and @xref{Using Autoconf Macros}, for more info.

The modules.af file consists of a series of configuration forms (Scheme
lists), which have one of the following formats:

@example
  (files-glob PATTERN ...)                      ;; required
  (non-critical-external MODULE ...)            ;; optional
  (non-critical-internal MODULE ...)            ;; optional
  (programs (MODULE PROG ...) ...)              ;; optional
  (pww-varname VARNAME)                         ;; optional
@end example

@var{pattern} is a string that may contain "*" and "?" characters to be
expanded into filenames.  @var{module} is a list of symbols naming a module,
such as `(srfi srfi-1)'.  @var{varname} is a shell-safe name to use instead of
@code{probably_wont_work}, the default.  This var is passed to `AC_SUBST'.
@var{prog} is a string that names a program, such as "gpg".

Autofrisk expands the @code{files-glob} pattern(s) into a list of files, scans
each file's module definition form(s), and constructs a module dependency
graph wherein modules defined by @code{define-module} are considered
@dfn{internal} and the remaining, @dfn{external}.  For each external module
that has an internal dependency, Autofrisk emits a
@code{GUILE_MODULE_REQUIRED} check (@pxref{Autoconf Macros}), which altogether
form the body of @code{AUTOFRISK_CHECKS}.

@code{GUILE_MODULE_REQUIRED} causes the @file{configure} script to exit with
an error message if the specified module is not available; it enforces a
strong dependency.  You can temper dependency strength by using the
@code{non-critical-external} and @code{non-critical-internal} configuration
forms in modules.af.  For graph edges that touch such non-critical modules,
Autofrisk uses @code{GUILE_MODULE_AVAILABLE}, and arranges for
@code{AUTOFRISK_SUMMARY} to display a warning if they are not found.

The shell code resulting from the expansion of @code{AUTOFRISK_CHECKS} and
@code{AUTOFRISK_SUMMARY} uses the shell variable @code{probably_wont_work} to
collect the names of unfound non-critical modules.  If this bothers you, use
configuration form @code{(pww-name foo)} in modules.af.

Although Autofrisk does not detect when a module uses a program (for example,
in a @code{system} call), it can generate @code{AC_PATH_PROG} forms anyway if
you use the @code{programs} configuration form in modules.af.  These are
collected into @code{AUTOCONF_CHECKS}.

@xref{Using Autofrisk}, for some modules.af examples.

@node Using Autofrisk
@section Using Autofrisk

Using Autofrisk (@pxref{Autofrisk}) involves writing @file{modules.af} and
adding two macro calls to @file{configure.in}.  Here is an example of the
latter:

@example
AUTOFRISK_CHECKS
AUTOFRISK_SUMMARY
@end example

Here is an adaptation of the second "GUILE_*" example (@pxref{Using Autoconf
Macros}) that does basically the same thing.

@example
(files-glob "my/*.scm")
(non-critical-external (database postgres))
(programs ((my gpgutils) "gpg"))        ;; (my gpgutils) uses "gpg"
@end example

If the SRFI modules (@pxref{SRFI Support}) were a separate package, we could
use @code{guile-tools frisk} to find out its dependencies:

@example
$ guile-tools frisk srfi/*.scm
13 files, 18 modules (13 internal, 5 external), 9 edges

x (ice-9 and-let-star)
			 regular	(srfi srfi-2)
x (ice-9 syncase)
			 regular	(srfi srfi-11)
x (ice-9 rdelim)
			 regular	(srfi srfi-10)
x (ice-9 receive)
			 regular	(srfi srfi-8)
			 regular	(srfi srfi-1)
x (ice-9 session)
			 regular	(srfi srfi-1)
@end example

Then, we could use the following modules.af to help configure it:

@example
(files-glob "srfi/*.scm")
(non-critical-external          ;; relatively recent
  (ice-9 rdelim)
  (ice-9 receive)
  (ice-9 and-let-star))
(pww-varname not_fully_supported)
@end example

@c autoconf.texi ends here


code:
@c -*-texinfo-*-
@c This is part of the GNU Guile Reference Manual.
@c Copyright (C)  2008, 2009, 2010
@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.

@xref{Read/Load/Eval/Compile}, if you're lost and you just wanted to
know how to compile your @code{.scm} file.

@menu
* Compiler Tower::
* The Scheme Compiler::
* Tree-IL::
* GLIL::
* Assembly::
* Bytecode and Objcode::
* 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}).

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, @code{(system base language)}:

@example
(use-modules (system base language))
@end example

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] [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:

@example
(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 () ...))
@end example
@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
allows the user to change the current language of the REPL:

@example
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)>
@end example

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

@deffn {Scheme Procedure} lookup-language name
Looks up a language named @var{name}, autoloading it if necessary.

Languages are autoloaded by looking for a variable named @var{name} in
a module named @code{(language @var{name} spec)}.

The language object will be returned, or @code{#f} if there does not
exist a language with that name.
@end deffn

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

@deffn {Scheme Procedure} lookup-compilation-order from to
Recursively traverses the set of languages to which @var{from} can
compile, depth-first, and return the first path that can transform
@var{from} to @var{to}. Returns @code{#f} if no path is found.

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

There is a notion of a ``current language'', which is maintained in
the @code{*current-language*} fluid. 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.

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

@itemize
@item Scheme
@item Tree Intermediate Language (Tree-IL)
@item Guile Lowlevel Intermediate Language (GLIL)
@item Assembly
@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:

@itemize
@item Value
@end itemize

Compiling to @code{value} loads the object code into a procedure, and
wakes the sleeping giant.

Perhaps this strangeness can be explained by example:
@code{compile-file} defaults to compiling to object code, 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.

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

@example
((lambda (x) ((compile x) x)) '(lambda (x) ((compile x) x)))
@end example

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

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, @code{(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 @code{(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 @code{compile}
and @code{compile-file} procedures compile in a fresh module, such
that bindings and macros introduced by the expression being compiled
are isolated:

@example
(eq? (current-module) (compile '(current-module)))
@result{} #f

(compile '(define hello 'world))
(defined? 'hello)
@result{} #f

(define / *)
(eq? (compile '/) /)
@result{} #f
@end example

Similarly, changes to the @code{current-reader} fluid (@pxref{Loading,
@code{current-reader}}) are isolated:

@example
(compile '(fluid-set! current-reader (lambda args 'fail)))
(fluid-ref current-reader)
@result{} #f
@end example

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

@example
(define hello 'world)
(compile 'hello #:env (current-module))
@result{} world
@end example

@node Tree-IL
@subsection 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 @code{<const>} is a record type with two fields, @code{src} and
@code{exp}. Instances of this type are created via @code{make-const}.
Fields of this type are accessed via the @code{const-src} and
@code{const-exp} procedures. There is also a predicate, @code{const?}.
@xref{Records}, for more information on records.

@c alpha renaming

All Tree-IL types have a @code{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 @code{src} is the same as that
returned by Guile's @code{source-properties} function. @xref{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, an the S-expression representation
of @code{#<const src: #f exp: 3>} expression would be:

@example
(const 3)
@end example

Users may program with this format directly at the REPL:

@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))
@result{} 42
@end example

The @code{src} fields are left out of the external representation.

One may create Tree-IL objects from their external representations via
calling @code{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 @code{parse-tree-il}
take care of the rest.

@deftp {Scheme Variable} <void> src
@deftpx {External Representation} (void)
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
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}.
@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
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})
A reference to a variable in a specific module. @var{mod} should be
the name of the module, e.g. @code{(guile-user)}.

If @var{public?} is true, the variable named @var{name} will be looked
up in @var{mod}'s public interface, and serialized with @code{@@};
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})
A procedure call.
@end deftp
@deftp {Scheme Variable} <sequence> src exps
@deftpx {External Representation} (begin . @var{exps})
Like Scheme's @code{begin}.
@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
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
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{opt} is a list of the optional arguments, or @code{#f} if there
are no optional arguments. @var{rest} is the name of the rest
argument, or @code{#f}.

@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 argumens, 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.

@var{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.

@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 a @var{consequent}, it should be a
@code{<lambda-case>} expression, representing the next clause to try.
If there is no @var{consequent}, 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
@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{in-order?} @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,
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.
@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
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.

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

@code{<let-values>} is an optimization of @code{<application>} of 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{lambda} expressions.

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

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
@code{(language tree-il compile-glil)} for more details.

@node GLIL
@subsection GLIL

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 {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
expressions.
@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

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.

@node Assembly
@subsection Assembly

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.

Besides the fact that it is not a record-based language, assembly
differs from GLIL in four main ways:

@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

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.

The general form of assembly instructions is the following:

@lisp
(@var{inst} @var{arg} ...)
@end lisp

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:

@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

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.

@node Bytecode and Objcode
@subsection Bytecode and Objcode

Finally, the raw bytes. There are actually two different ``languages''
here, corresponding to two different ways to represent the bytes.

``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:

@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

``Objcode'' is bytecode, but mapped directly to a C structure,
@code{struct scm_objcode}:

@example
struct scm_objcode @{
  scm_t_uint32 len;
  scm_t_uint32 metalen;
  scm_t_uint8 base[0];
@};
@end example

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

On disk, object code has an sixteen-byte cookie prepended to it, to
prevent accidental loading of arbitrary garbage.
@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.
@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.
@end deffn

The following procedure is actually in @code{(system vm program)}, but
we'll mention it here:

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

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.

@node Writing New High-Level Languages
@subsection Writing New High-Level Languages

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

@node Extending the Compiler
@subsection Extending the Compiler

At this point, we break with the impersonal tone of the rest of the
manual, and make an intervention. 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 sublimated 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, butq 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!

license: mit


code:
@c -*-texinfo-*-
@c This is part of the GNU Guile Reference Manual.
@c Copyright (C)  1996, 1997, 2000, 2001, 2002, 2003, 2004, 2010
@c   Free Software Foundation, Inc.
@c See the file guile.texi for copying conditions.

@node Data Representation
@section Data Representation

Scheme is a latently-typed language; this means that the system cannot,
in general, determine the type of a given expression at compile time.
Types only become apparent at run time.  Variables do not have fixed
types; a variable may hold a pair at one point, an integer at the next,
and a thousand-element vector later.  Instead, values, not variables,
have fixed types.

In order to implement standard Scheme functions like @code{pair?} and
@code{string?} and provide garbage collection, the representation of
every value must contain enough information to accurately determine its
type at run time.  Often, Scheme systems also use this information to
determine whether a program has attempted to apply an operation to an
inappropriately typed value (such as taking the @code{car} of a string).

Because variables, pairs, and vectors may hold values of any type,
Scheme implementations use a uniform representation for values --- a
single type large enough to hold either a complete value or a pointer
to a complete value, along with the necessary typing information.

The following sections will present a simple typing system, and then
make some refinements to correct its major weaknesses. We then conclude
with a discussion of specific choices that Guile has made regarding
garbage collection and data representation.

@menu
* A Simple Representation::
* Faster Integers::
* Cheaper Pairs::
* Conservative GC::
* The SCM Type in Guile::
@end menu

@node A Simple Representation
@subsection A Simple Representation

The simplest way to represent Scheme values in C would be to represent
each value as a pointer to a structure containing a type indicator,
followed by a union carrying the real value. Assuming that @code{SCM} is
the name of our universal type, we can write:

@example
enum type @{ integer, pair, string, vector, ... @};

typedef struct value *SCM;

struct value @{
  enum type type;
  union @{
    int integer;
    struct @{ SCM car, cdr; @} pair;
    struct @{ int length; char *elts; @} string;
    struct @{ int length; SCM  *elts; @} vector;
    ...
  @} value;
@};
@end example
with the ellipses replaced with code for the remaining Scheme types.

This representation is sufficient to implement all of Scheme's
semantics.  If @var{x} is an @code{SCM} value:
@itemize @bullet
@item
  To test if @var{x} is an integer, we can write @code{@var{x}->type == integer}.
@item
  To find its value, we can write @code{@var{x}->value.integer}.
@item
  To test if @var{x} is a vector, we can write @code{@var{x}->type == vector}.
@item
  If we know @var{x} is a vector, we can write
  @code{@var{x}->value.vector.elts[0]} to refer to its first element.
@item
  If we know @var{x} is a pair, we can write
  @code{@var{x}->value.pair.car} to extract its car.
@end itemize

@node Faster Integers
@subsection Faster Integers

Unfortunately, the above representation has a serious disadvantage.  In
order to return an integer, an expression must allocate a @code{struct
value}, initialize it to represent that integer, and return a pointer to
it.  Furthermore, fetching an integer's value requires a memory
reference, which is much slower than a register reference on most
processors.  Since integers are extremely common, this representation is
too costly, in both time and space.  Integers should be very cheap to
create and manipulate.

One possible solution comes from the observation that, on many
architectures, heap-allocated data (i.e., what you get when you call
@code{malloc}) must be aligned on an eight-byte boundary. (Whether or
not the machine actually requires it, we can write our own allocator for
@code{struct value} objects that assures this is true.) In this case,
the lower three bits of the structure's address are known to be zero.

This gives us the room we need to provide an improved representation
for integers.  We make the following rules:
@itemize @bullet
@item
If the lower three bits of an @code{SCM} value are zero, then the SCM
value is a pointer to a @code{struct value}, and everything proceeds as
before.
@item
Otherwise, the @code{SCM} value represents an integer, whose value
appears in its upper bits.
@end itemize

Here is C code implementing this convention:
@example
enum type @{ pair, string, vector, ... @};

typedef struct value *SCM;

struct value @{
  enum type type;
  union @{
    struct @{ SCM car, cdr; @} pair;
    struct @{ int length; char *elts; @} string;
    struct @{ int length; SCM  *elts; @} vector;
    ...
  @} value;
@};

#define POINTER_P(x) (((int) (x) & 7) == 0)
#define INTEGER_P(x) (! POINTER_P (x))

#define GET_INTEGER(x)  ((int) (x) >> 3)
#define MAKE_INTEGER(x) ((SCM) (((x) << 3) | 1))
@end example

Notice that @code{integer} no longer appears as an element of @code{enum
type}, and the union has lost its @code{integer} member.  Instead, we
use the @code{POINTER_P} and @code{INTEGER_P} macros to make a coarse
classification of values into integers and non-integers, and do further
type testing as before.

Here's how we would answer the questions posed above (again, assume
@var{x} is an @code{SCM} value):
@itemize @bullet
@item
  To test if @var{x} is an integer, we can write @code{INTEGER_P (@var{x})}.
@item
  To find its value, we can write @code{GET_INTEGER (@var{x})}.
@item
  To test if @var{x} is a vector, we can write:
@example
  @code{POINTER_P (@var{x}) && @var{x}->type == vector}
@end example
  Given the new representation, we must make sure @var{x} is truly a
  pointer before we dereference it to determine its complete type.
@item
  If we know @var{x} is a vector, we can write
  @code{@var{x}->value.vector.elts[0]} to refer to its first element, as
  before.
@item
  If we know @var{x} is a pair, we can write
  @code{@var{x}->value.pair.car} to extract its car, just as before.
@end itemize

This representation allows us to operate more efficiently on integers
than the first.  For example, if @var{x} and @var{y} are known to be
integers, we can compute their sum as follows:
@example
MAKE_INTEGER (GET_INTEGER (@var{x}) + GET_INTEGER (@var{y}))
@end example
Now, integer math requires no allocation or memory references. Most real
Scheme systems actually implement addition and other operations using an
even more efficient algorithm, but this essay isn't about
bit-twiddling. (Hint: how do you decide when to overflow to a bignum?
How would you do it in assembly?)

@node Cheaper Pairs
@subsection Cheaper Pairs

However, there is yet another issue to confront. Most Scheme heaps
contain more pairs than any other type of object; Jonathan Rees said at
one point that pairs occupy 45% of the heap in his Scheme
implementation, Scheme 48. However, our representation above spends
three @code{SCM}-sized words per pair --- one for the type, and two for
the @sc{car} and @sc{cdr}. Is there any way to represent pairs using
only two words?

Let us refine the convention we established earlier.  Let us assert
that:
@itemize @bullet
@item
  If the bottom three bits of an @code{SCM} value are @code{#b000}, then
  it is a pointer, as before.
@item
  If the bottom three bits are @code{#b001}, then the upper bits are an
  integer.  This is a bit more restrictive than before.
@item
  If the bottom two bits are @code{#b010}, then the value, with the bottom
  three bits masked out, is the address of a pair.
@end itemize

Here is the new C code:
@example
enum type @{ string, vector, ... @};

typedef struct value *SCM;

struct value @{
  enum type type;
  union @{
    struct @{ int length; char *elts; @} string;
    struct @{ int length; SCM  *elts; @} vector;
    ...
  @} value;
@};

struct pair @{
  SCM car, cdr;
@};

#define POINTER_P(x) (((int) (x) & 7) == 0)

#define INTEGER_P(x)  (((int) (x) & 7) == 1)
#define GET_INTEGER(x)  ((int) (x) >> 3)
#define MAKE_INTEGER(x) ((SCM) (((x) << 3) | 1))

#define PAIR_P(x) (((int) (x) & 7) == 2)
#define GET_PAIR(x) ((struct pair *) ((int) (x) & ~7))
@end example

Notice that @code{enum type} and @code{struct value} now only contain
provisions for vectors and strings; both integers and pairs have become
special cases.  The code above also assumes that an @code{int} is large
enough to hold a pointer, which isn't generally true.

Our list of examples is now as follows:
@itemize @bullet
@item
  To test if @var{x} is an integer, we can write @code{INTEGER_P
  (@var{x})}; this is as before.
@item
  To find its value, we can write @code{GET_INTEGER (@var{x})}, as
  before.
@item
  To test if @var{x} is a vector, we can write:
@example
  @code{POINTER_P (@var{x}) && @var{x}->type == vector}
@end example
  We must still make sure that @var{x} is a pointer to a @code{struct
  value} before dereferencing it to find its type.
@item
  If we know @var{x} is a vector, we can write
  @code{@var{x}->value.vector.elts[0]} to refer to its first element, as
  before.
@item
  We can write @code{PAIR_P (@var{x})} to determine if @var{x} is a
  pair, and then write @code{GET_PAIR (@var{x})->car} to refer to its
  car.
@end itemize

This change in representation reduces our heap size by 15%.  It also
makes it cheaper to decide if a value is a pair, because no memory
references are necessary; it suffices to check the bottom two bits of
the @code{SCM} value.  This may be significant when traversing lists, a
common activity in a Scheme system.

Again, most real Scheme systems use a slightly different implementation;
for example, if GET_PAIR subtracts off the low bits of @code{x}, instead
of masking them off, the optimizer will often be able to combine that
subtraction with the addition of the offset of the structure member we
are referencing, making a modified pointer as fast to use as an
unmodified pointer.

@node Conservative GC
@subsection Conservative Garbage Collection

Aside from the latent typing, the major source of constraints on a
Scheme implementation's data representation is the garbage collector.
The collector must be able to traverse every live object in the heap, to
determine which objects are not live, and thus collectable.

There are many ways to implement this. Guile's garbage collection is
built on a library, the Boehm-Demers-Weiser conservative garbage
collector (BDW-GC). The BDW-GC ``just works'', for the most part. But
since it is interesting to know how these things work, we include here a
high-level description of what the BDW-GC does.

Garbage collection has two logical phases: a @dfn{mark} phase, in which
the set of live objects is enumerated, and a @dfn{sweep} phase, in which
objects not traversed in the mark phase are collected. Correct
functioning of the collector depends on being able to traverse the
entire set of live objects.

In the mark phase, the collector scans the system's global variables and
the local variables on the stack to determine which objects are
immediately accessible by the C code. It then scans those objects to
find the objects they point to, and so on. The collector logically sets
a @dfn{mark bit} on each object it finds, so each object is traversed
only once.

When the collector can find no unmarked objects pointed to by marked
objects, it assumes that any objects that are still unmarked will never
be used by the program (since there is no path of dereferences from any
global or local variable that reaches them) and deallocates them.

In the above paragraphs, we did not specify how the garbage collector
finds the global and local variables; as usual, there are many different
approaches.  Frequently, the programmer must maintain a list of pointers
to all global variables that refer to the heap, and another list
(adjusted upon entry to and exit from each function) of local variables,
for the collector's benefit.

The list of global variables is usually not too difficult to maintain,
since global variables are relatively rare. However, an explicitly
maintained list of local variables (in the author's personal experience)
is a nightmare to maintain. Thus, the BDW-GC uses a technique called
@dfn{conservative garbage collection}, to make the local variable list
unnecessary.

The trick to conservative collection is to treat the stack as an
ordinary range of memory, and assume that @emph{every} word on the stack
is a pointer into the heap.  Thus, the collector marks all objects whose
addresses appear anywhere in the stack, without knowing for sure how
that word is meant to be interpreted.

In addition to the stack, the BDW-GC will also scan static data
sections. This means that global variables are also scanned when looking
for live Scheme objects.

Obviously, such a system will occasionally retain objects that are
actually garbage, and should be freed. In practice, this is not a
problem. The alternative, an explicitly maintained list of local
variable addresses, is effectively much less reliable, due to programmer
error. Interested readers should see the BDW-GC web page at
@uref{http://www.hpl.hp.com/personal/Hans_Boehm/gc}, for more
information.

@node The SCM Type in Guile
@subsection The SCM Type in Guile

Guile classifies Scheme objects into two kinds: those that fit entirely
within an @code{SCM}, and those that require heap storage.

The former class are called @dfn{immediates}.  The class of immediates
includes small integers, characters, boolean values, the empty list, the
mysterious end-of-file object, and some others.

The remaining types are called, not surprisingly, @dfn{non-immediates}.
They include pairs, procedures, strings, vectors, and all other data
types in Guile. For non-immediates, the @code{SCM} word contains a
pointer to data on the heap, with further information about the object
in question is stored in that data.

This section describes how the @code{SCM} type is actually represented
and used at the C level. Interested readers should see
@code{libguile/tags.h} for an exposition of how Guile stores type
information.

In fact, there are two basic C data types to represent objects in
Guile: @code{SCM} and @code{scm_t_bits}.

@menu
* Relationship between SCM and scm_t_bits::
* Immediate objects::
* Non-immediate objects::
* Allocating Cells::
* Heap Cell Type Information::
* Accessing Cell Entries::
@end menu

@node Relationship between SCM and scm_t_bits
@subsubsection Relationship between @code{SCM} and @code{scm_t_bits}

A variable of type @code{SCM} is guaranteed to hold a valid Scheme
object.  A variable of type @code{scm_t_bits}, on the other hand, may
hold a representation of a @code{SCM} value as a C integral type, but
may also hold any C value, even if it does not correspond to a valid
Scheme object.

For a variable @var{x} of type @code{SCM}, the Scheme object's type
information is stored in a form that is not directly usable.  To be able
to work on the type encoding of the scheme value, the @code{SCM}
variable has to be transformed into the corresponding representation as
a @code{scm_t_bits} variable @var{y} by using the @code{SCM_UNPACK}
macro.  Once this has been done, the type of the scheme object @var{x}
can be derived from the content of the bits of the @code{scm_t_bits}
value @var{y}, in the way illustrated by the example earlier in this
chapter (@pxref{Cheaper Pairs}).  Conversely, a valid bit encoding of a
Scheme value as a @code{scm_t_bits} variable can be transformed into the
corresponding @code{SCM} value using the @code{SCM_PACK} macro.

@node Immediate objects
@subsubsection Immediate objects

A Scheme object may either be an immediate, i.e. carrying all necessary
information by itself, or it may contain a reference to a @dfn{cell}
with additional information on the heap.  Although in general it should
be irrelevant for user code whether an object is an immediate or not,
within Guile's own code the distinction is sometimes of importance.
Thus, the following low level macro is provided:

@deftypefn Macro int SCM_IMP (SCM @var{x})
A Scheme object is an immediate if it fulfills the @code{SCM_IMP}
predicate, otherwise it holds an encoded reference to a heap cell.  The
result of the predicate is delivered as a C style boolean value.  User
code and code that extends Guile should normally not be required to use
this macro.
@end deftypefn

@noindent
Summary:
@itemize @bullet
@item
Given a Scheme object @var{x} of unknown type, check first
with @code{SCM_IMP (@var{x})} if it is an immediate object.
@item
If so, all of the type and value information can be determined from the
@code{scm_t_bits} value that is delivered by @code{SCM_UNPACK
(@var{x})}.
@end itemize

There are a number of special values in Scheme, most of them documented
elsewhere in this manual. It's not quite the right place to put them,
but for now, here's a list of the C names given to some of these values:

@deftypefn Macro SCM SCM_EOL
The Scheme empty list object, or ``End Of List'' object, usually written
in Scheme as @code{'()}.
@end deftypefn

@deftypefn Macro SCM SCM_EOF_VAL
The Scheme end-of-file value.  It has no standard written
representation, for obvious reasons.
@end deftypefn

@deftypefn Macro SCM SCM_UNSPECIFIED
The value returned by expressions which the Scheme standard says return
an ``unspecified'' value.

This is sort of a weirdly literal way to take things, but the standard
read-eval-print loop prints nothing when the expression returns this
value, so it's not a bad idea to return this when you can't think of
anything else helpful.
@end deftypefn

@deftypefn Macro SCM SCM_UNDEFINED
The ``undefined'' value.  Its most important property is that is not
equal to any valid Scheme value.  This is put to various internal uses
by C code interacting with Guile.

For example, when you write a C function that is callable from Scheme
and which takes optional arguments, the interpreter passes
@code{SCM_UNDEFINED} for any arguments you did not receive.

We also use this to mark unbound variables.
@end deftypefn

@deftypefn Macro int SCM_UNBNDP (SCM @var{x})
Return true if @var{x} is @code{SCM_UNDEFINED}.  Note that this is not a
check to see if @var{x} is @code{SCM_UNBOUND}.  History will not be kind
to us.
@end deftypefn

@node Non-immediate objects
@subsubsection Non-immediate objects

A Scheme object of type @code{SCM} that does not fulfill the
@code{SCM_IMP} predicate holds an encoded reference to a heap cell.
This reference can be decoded to a C pointer to a heap cell using the
@code{SCM2PTR} macro.  The encoding of a pointer to a heap cell into a
@code{SCM} value is done using the @code{PTR2SCM} macro.

@c (FIXME:: this name should be changed)
@deftypefn Macro {scm_t_cell *} SCM2PTR (SCM @var{x})
Extract and return the heap cell pointer from a non-immediate @code{SCM}
object @var{x}.
@end deftypefn

@c (FIXME:: this name should be changed)
@deftypefn Macro SCM PTR2SCM (scm_t_cell * @var{x})
Return a @code{SCM} value that encodes a reference to the heap cell
pointer @var{x}.
@end deftypefn

Note that it is also possible to transform a non-immediate @code{SCM}
value by using @code{SCM_UNPACK} into a @code{scm_t_bits} variable.
However, the result of @code{SCM_UNPACK} may not be used as a pointer to
a @code{scm_t_cell}: only @code{SCM2PTR} is guaranteed to transform a
@code{SCM} object into a valid pointer to a heap cell.  Also, it is not
allowed to apply @code{PTR2SCM} to anything that is not a valid pointer
to a heap cell.

@noindent
Summary:
@itemize @bullet
@item
Only use @code{SCM2PTR} on @code{SCM} values for which @code{SCM_IMP} is
false!
@item
Don't use @code{(scm_t_cell *) SCM_UNPACK (@var{x})}!  Use @code{SCM2PTR
(@var{x})} instead!
@item
Don't use @code{PTR2SCM} for anything but a cell pointer!
@end itemize

@node Allocating Cells
@subsubsection Allocating Cells

Guile provides both ordinary cells with two slots, and double cells
with four slots.  The following two function are the most primitive
way to allocate such cells.

If the caller intends to use it as a header for some other type, she
must pass an appropriate magic value in @var{word_0}, to mark it as a
member of that type, and pass whatever value as @var{word_1}, etc that
the type expects.  You should generally not need these functions,
unless you are implementing a new datatype, and thoroughly understand
the code in @code{<libguile/tags.h>}.

If you just want to allocate pairs, use @code{scm_cons}.

@deftypefn Function SCM scm_cell (scm_t_bits word_0, scm_t_bits word_1)
Allocate a new cell, initialize the two slots with @var{word_0} and
@var{word_1}, and return it.

Note that @var{word_0} and @var{word_1} are of type @code{scm_t_bits}.
If you want to pass a @code{SCM} object, you need to use
@code{SCM_UNPACK}.
@end deftypefn

@deftypefn Function SCM scm_double_cell (scm_t_bits word_0, scm_t_bits word_1, scm_t_bits word_2, scm_t_bits word_3)
Like @code{scm_cell}, but allocates a double cell with four
slots.
@end deftypefn

@node Heap Cell Type Information
@subsubsection Heap Cell Type Information

Heap cells contain a number of entries, each of which is either a scheme
object of type @code{SCM} or a raw C value of type @code{scm_t_bits}.
Which of the cell entries contain Scheme objects and which contain raw C
values is determined by the first entry of the cell, which holds the
cell type information.

@deftypefn Macro scm_t_bits SCM_CELL_TYPE (SCM @var{x})
For a non-immediate Scheme object @var{x}, deliver the content of the
first entry of the heap cell referenced by @var{x}.  This value holds
the information about the cell type.
@end deftypefn

@deftypefn Macro void SCM_SET_CELL_TYPE (SCM @var{x}, scm_t_bits @var{t})
For a non-immediate Scheme object @var{x}, write the value @var{t} into
the first entry of the heap cell referenced by @var{x}.  The value
@var{t} must hold a valid cell type.
@end deftypefn

@node Accessing Cell Entries
@subsubsection Accessing Cell Entries

For a non-immediate Scheme object @var{x}, the object type can be
determined by reading the cell type entry using the @code{SCM_CELL_TYPE}
macro.  For each different type of cell it is known which cell entries
hold Scheme objects and which cell entries hold raw C data.  To access
the different cell entries appropriately, the following macros are
provided.

@deftypefn Macro scm_t_bits SCM_CELL_WORD (SCM @var{x}, unsigned int @var{n})
Deliver the cell entry @var{n} of the heap cell referenced by the
non-immediate Scheme object @var{x} as raw data.  It is illegal, to
access cell entries that hold Scheme objects by using these macros.  For
convenience, the following macros are also provided.
@itemize @bullet
@item
SCM_CELL_WORD_0 (@var{x}) @result{} SCM_CELL_WORD (@var{x}, 0)
@item
SCM_CELL_WORD_1 (@var{x}) @result{} SCM_CELL_WORD (@var{x}, 1)
@item
@dots{}
@item
SCM_CELL_WORD_@var{n} (@var{x}) @result{} SCM_CELL_WORD (@var{x}, @var{n})
@end itemize
@end deftypefn

@deftypefn Macro SCM SCM_CELL_OBJECT (SCM @var{x}, unsigned int @var{n})
Deliver the cell entry @var{n} of the heap cell referenced by the
non-immediate Scheme object @var{x} as a Scheme object.  It is illegal,
to access cell entries that do not hold Scheme objects by using these
macros.  For convenience, the following macros are also provided.
@itemize @bullet
@item
SCM_CELL_OBJECT_0 (@var{x}) @result{} SCM_CELL_OBJECT (@var{x}, 0)
@item
SCM_CELL_OBJECT_1 (@var{x}) @result{} SCM_CELL_OBJECT (@var{x}, 1)
@item
@dots{}
@item
SCM_CELL_OBJECT_@var{n} (@var{x}) @result{} SCM_CELL_OBJECT (@var{x},
@var{n})
@end itemize
@end deftypefn

@deftypefn Macro void SCM_SET_CELL_WORD (SCM @var{x}, unsigned int @var{n}, scm_t_bits @var{w})
Write the raw C value @var{w} into entry number @var{n} of the heap cell
referenced by the non-immediate Scheme value @var{x}.  Values that are
written into cells this way may only be read from the cells using the
@code{SCM_CELL_WORD} macros or, in case cell entry 0 is written, using
the @code{SCM_CELL_TYPE} macro.  For the special case of cell entry 0 it
has to be made sure that @var{w} contains a cell type information which
does not describe a Scheme object.  For convenience, the following
macros are also provided.
@itemize @bullet
@item
SCM_SET_CELL_WORD_0 (@var{x}, @var{w}) @result{} SCM_SET_CELL_WORD
(@var{x}, 0, @var{w})
@item
SCM_SET_CELL_WORD_1 (@var{x}, @var{w}) @result{} SCM_SET_CELL_WORD
(@var{x}, 1, @var{w})
@item
@dots{}
@item
SCM_SET_CELL_WORD_@var{n} (@var{x}, @var{w}) @result{} SCM_SET_CELL_WORD
(@var{x}, @var{n}, @var{w})
@end itemize
@end deftypefn

@deftypefn Macro void SCM_SET_CELL_OBJECT (SCM @var{x}, unsigned int @var{n}, SCM @var{o})
Write the Scheme object @var{o} into entry number @var{n} of the heap
cell referenced by the non-immediate Scheme value @var{x}.  Values that
are written into cells this way may only be read from the cells using
the @code{SCM_CELL_OBJECT} macros or, in case cell entry 0 is written,
using the @code{SCM_CELL_TYPE} macro.  For the special case of cell
entry 0 the writing of a Scheme object into this cell is only allowed
if the cell forms a Scheme pair.  For convenience, the following macros
are also provided.
@itemize @bullet
@item
SCM_SET_CELL_OBJECT_0 (@var{x}, @var{o}) @result{} SCM_SET_CELL_OBJECT
(@var{x}, 0, @var{o})
@item
SCM_SET_CELL_OBJECT_1 (@var{x}, @var{o}) @result{} SCM_SET_CELL_OBJECT
(@var{x}, 1, @var{o})
@item
@dots{}
@item
SCM_SET_CELL_OBJECT_@var{n} (@var{x}, @var{o}) @result{}
SCM_SET_CELL_OBJECT (@var{x}, @var{n}, @var{o})
@end itemize
@end deftypefn

@noindent
Summary:
@itemize @bullet
@item
For a non-immediate Scheme object @var{x} of unknown type, get the type
information by using @code{SCM_CELL_TYPE (@var{x})}.
@item
As soon as the cell type information is available, only use the
appropriate access methods to read and write data to the different cell
entries.
@end itemize

@c Local Variables:
@c TeX-master: "guile.texi"
@c End:


code:
@c -*-texinfo-*-
@c This is part of the GNU Guile Reference Manual.
@c Copyright (C)  1996, 1997, 2000, 2001, 2002, 2003, 2004
@c   Free Software Foundation, Inc.
@c See the file guile.texi for copying conditions.

@node Expect
@section Expect

The macros in this section are made available with:

@lisp
(use-modules (ice-9 expect))
@end lisp

@code{expect} is a macro for selecting actions based on the output from
a port.  The name comes from a tool of similar functionality by Don Libes.
Actions can be taken when a particular string is matched, when a timeout
occurs, or when end-of-file is seen on the port.  The @code{expect} macro
is described below; @code{expect-strings} is a front-end to @code{expect}
based on regexec (see the regular expression documentation).

@defmac expect-strings clause @dots{}
By default, @code{expect-strings} will read from the current input port.
The first term in each clause consists of an expression evaluating to
a string pattern (regular expression).  As characters
are read one-by-one from the port, they are accumulated in a buffer string
which is matched against each of the patterns.  When a
pattern matches, the remaining expression(s) in
the clause are evaluated and the value of the last is returned.  For example:

@lisp
(with-input-from-file "/etc/passwd"
  (lambda ()
    (expect-strings
      ("^nobody" (display "Got a nobody user.\n")
                 (display "That's no problem.\n"))
      ("^daemon" (display "Got a daemon user.\n")))))
@end lisp

The regular expression is compiled with the @code{REG_NEWLINE} flag, so
that the ^ and $ anchors will match at any newline, not just at the start
and end of the string.

There are two other ways to write a clause:

The expression(s) to evaluate
can be omitted, in which case the result of the regular expression match
(converted to strings, as obtained from regexec with match-pick set to "")
will be returned if the pattern matches.

The symbol @code{=>} can be used to indicate that the expression is a
procedure which will accept the result of a successful regular expression
match.  E.g.,

@lisp
("^daemon" => write)
("^d(aemon)" => (lambda args (for-each write args)))
("^da(em)on" => (lambda (all sub)
                  (write all) (newline)
                  (write sub) (newline)))
@end lisp

The order of the substrings corresponds to the order in which the
opening brackets occur.

A number of variables can be used to control the behaviour
of @code{expect} (and @code{expect-strings}).
Most have default top-level bindings to the value @code{#f},
which produces the default behaviour.
They can be redefined at the
top level or locally bound in a form enclosing the expect expression.

@table @code
@item expect-port
A port to read characters from, instead of the current input port.
@item expect-timeout
@code{expect} will terminate after this number of
seconds, returning @code{#f} or the value returned by expect-timeout-proc.
@item expect-timeout-proc
A procedure called if timeout occurs.  The procedure takes a single argument:
the accumulated string.
@item expect-eof-proc
A procedure called if end-of-file is detected on the input port.  The
procedure takes a single argument: the accumulated string.
@item expect-char-proc
A procedure to be called every time a character is read from the
port.  The procedure takes a single argument: the character which was read.
@item expect-strings-compile-flags
Flags to be used when compiling a regular expression, which are passed
to @code{make-regexp} @xref{Regexp Functions}.  The default value
is @code{regexp/newline}.
@item expect-strings-exec-flags
Flags to be used when executing a regular expression, which are
passed to regexp-exec @xref{Regexp Functions}.
The default value is @code{regexp/noteol}, which prevents @code{$}
from matching the end of the string while it is still accumulating,
but still allows it to match after a line break or at the end of file.
@end table

Here's an example using all of the variables:

@smalllisp
(let ((expect-port (open-input-file "/etc/passwd"))
      (expect-timeout 1)
      (expect-timeout-proc
        (lambda (s) (display "Times up!\n")))
      (expect-eof-proc
        (lambda (s) (display "Reached the end of the file!\n")))
      (expect-char-proc display)
      (expect-strings-compile-flags (logior regexp/newline regexp/icase))
      (expect-strings-exec-flags 0))
   (expect-strings
     ("^nobody"  (display "Got a nobody user\n"))))
@end smalllisp
@end defmac

@defmac expect clause @dots{}
@code{expect} is used in the same way as @code{expect-strings},
but tests are specified not as patterns, but as procedures.  The
procedures are called in turn after each character is read from the
port, with two arguments: the value of the accumulated string and
a flag to indicate whether end-of-file has been reached.  The flag
will usually be @code{#f}, but if end-of-file is reached, the procedures
are called an additional time with the final accumulated string and
@code{#t}.

The test is successful if the procedure returns a non-false value.

If the @code{=>} syntax is used, then if the test succeeds it must return
a list containing the arguments to be provided to the corresponding
expression.

In the following example, a string will only be matched at the beginning
of the file:

@lisp
(let ((expect-port (open-input-file "/etc/passwd")))
  (expect
     ((lambda (s eof?) (string=? s "fnord!"))
        (display "Got a nobody user!\n"))))
@end lisp

The control variables described for @code{expect-strings} also
influence the behaviour of @code{expect}, with the exception of
variables whose names begin with @code{expect-strings-}.
@end defmac