[Guile-commits] GNU Guile branch, master, updated. v2.1.0-582-gbdad134

[Andy Wingo]

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU Guile".

http://git.savannah.gnu.org/cgit/guile.git/commit/?id=bdad13401611db73c57dcf8a1285b37e9b2ea31e

The branch, master has been updated
       via  bdad13401611db73c57dcf8a1285b37e9b2ea31e (commit)
      from  3652769585f6bb8f9feb4f5c03381a567f26b7f0 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit bdad13401611db73c57dcf8a1285b37e9b2ea31e
Author: Andy Wingo <address@hidden>
Date:   Sun Jan 12 15:31:35 2014 +0100

    Finish CPS documentation
    
    * doc/ref/compiler.texi (Continuation-Passing Style): Flesh out the
      documentation.

-----------------------------------------------------------------------

Summary of changes:
 doc/ref/compiler.texi |  343 +++++++++++++++++++++++++++++++++++--------------
 1 files changed, 245 insertions(+), 98 deletions(-)

diff --git a/doc/ref/compiler.texi b/doc/ref/compiler.texi
index e826438..4e24e8b 100644
--- a/doc/ref/compiler.texi
+++ b/doc/ref/compiler.texi
@@ -1,6 +1,6 @@
 @c -*-texinfo-*-
 @c This is part of the GNU Guile Reference Manual.
address@hidden Copyright (C)  2008, 2009, 2010, 2011, 2012, 2013
address@hidden Copyright (C)  2008, 2009, 2010, 2011, 2012, 2013, 2014
 @c   Free Software Foundation, Inc.
 @c See the file guile.texi for copying conditions.
 
@@ -533,7 +533,7 @@ compiler.
 @menu
 * An Introduction to CPS::
 * CPS in Guile::
-* Compiling CPS::
+* Building CPS::
 @end menu
 
 @node An Introduction to CPS
@@ -568,7 +568,7 @@ code:
 These labels also identify continuations.  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 @var{k6}.
+continue to apply it in @code{k6}.
 
 Which label has @code{k0} as its continuation?  It is either @code{k1}
 or @code{k2}.  Scheme does not have a fixed order of evaluation of
@@ -620,132 +620,279 @@ 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.
 
address@hidden Compiling CPS
+
+In CPS, there are no nested expressions.  Indeed, CPS even removes the
+concept of a stack.  All applications in CPS are in tail context.  For
+that reason, applications in CPS are jumps, not calls.  The @code{(k1)}
+above is nothing more than a @code{goto}.  @code{(k3 42)} is a
address@hidden with a value.  In this way, CPS bridges the gap between the
+lambda calculus and machine instruction sequences.
+
+On the side of machine instructions, Guile does still have a stack, and
+the @code{lambda} forms shown above do not actually result in one
+closure being allocated per subexpression at run-time.  Lambda
+expressions introduced by a CPS transformation can always be allocated
+as labels or basic blocks within a function.  In fact, we make a
+syntactic distinction between closures and continuations in the CPS
+language, and attempt to transform closures to continuations (basic
+blocks) where possible, via the @dfn{contification} optimization pass.
+
+Values bound by continuations are allocated to stack slots in a
+function's frame.  The compiler from CPS only allocates slots to values
+that are actually live; it's possible to have a value in scope but not
+allocated to a slot.
+
 @node CPS in Guile
 @subsubsection CPS in Guile
 
-Like Tree-IL, CPS is also a structured language, implemented with
-records not S-expressions.
+Guile's CPS language is composed of @dfn{terms}, @dfn{expressions},
+and @dfn{continuations}.
 
address@hidden {Scheme Variable} <prompt> escape-only? tag body handler
address@hidden {External Representation} (prompt @var{escape-only?} @var{tag} 
@var{body} @var{handler})
+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.
+
address@hidden {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
 
address@hidden {Scheme Variable} $arity req opt rest kw allow-other-keys?
address@hidden {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
 
+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.
 
address@hidden {Scheme Variable} $letk conts body
address@hidden {External Representation} (letk @var{conts} @var{body})
address@hidden deftp
address@hidden {Scheme Variable} $continue k src exp
address@hidden {External Representation} (continue @var{k} @var{src} @var{exp})
address@hidden deftp
address@hidden {Scheme Variable} $letrec names syms funs body
address@hidden {External Representation} (letrec @var{names} @var{syms} 
@var{funs} @var{body})
address@hidden {CPS Term} $letrec names syms funs body
+Declare the mutually recursive set of functions denoted by @var{names},
address@hidden, 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
address@hidden values.  @var{syms} are globally unique.
 @end deftp
 
-;; Continuations
address@hidden {Scheme Variable} $cont k cont
address@hidden {External Representation} (cont k cont)
address@hidden deftp
address@hidden {Scheme Variable} $kif kt kf
address@hidden {External Representation} (kif kt kf)
address@hidden deftp
address@hidden {Scheme Variable} $ktrunc arity k
address@hidden {External Representation} (ktrunc arity k)
address@hidden deftp
address@hidden {Scheme Variable} $kargs names syms body
address@hidden {External Representation} (kargs names syms body)
address@hidden deftp
address@hidden {Scheme Variable} $kentry self tail clauses
address@hidden {External Representation} (kentry self tail clauses)
address@hidden deftp
address@hidden {Scheme Variable} $ktail
address@hidden {External Representation} (ktail)
address@hidden deftp
address@hidden {Scheme Variable} $kclause arity cont
address@hidden {External Representation} (kclause arity cont)
address@hidden deftp
+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.
 
-;; Expressions.
address@hidden {Scheme Variable} $void
address@hidden {External Representation} (void)
address@hidden {CPS Expression} $void
+Continue with the unspecified value.
 @end deftp
address@hidden {Scheme Variable} $const val
address@hidden {External Representation} (const val)
address@hidden deftp
address@hidden {Scheme Variable} $prim name
address@hidden {External Representation} (prim name)
address@hidden deftp
address@hidden {Scheme Variable} $fun src meta free body
address@hidden {External Representation} (fun src meta free body)
+
address@hidden {CPS Expression} $const val
+Continue with the constant value @var{val}.
 @end deftp
address@hidden {Scheme Variable} $call proc args
address@hidden {External Representation} (call proc args)
+
address@hidden {CPS Expression} $prim name
+Continue with the procedure that implements the primitive operation
+named by @var{name}.
 @end deftp
address@hidden {Scheme Variable} $primcall name args
address@hidden {External Representation} (primcall name args)
+
address@hidden {CPS Expression} $fun src meta free body
+Continue with a procedure.  @var{src} identifies the source information
+for the procedure declaration, and @var{meta} is the metadata alist as
+described above in Tree-IL's @code{<lambda>}.  @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{$kentry} @code{$cont} of the procedure
+entry.
 @end deftp
address@hidden {Scheme Variable} $values args
address@hidden {External Representation} (values args)
+
address@hidden {CPS Expression} $call 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
address@hidden should be a @code{$kreceive} or a @code{$ktail} instance.
 @end deftp
address@hidden {Scheme Variable} $prompt escape? tag handler pop
address@hidden {External Representation} (prompt escape? tag handler pop)
+
address@hidden {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
 
-;; Helper.
-            $arity
-            make-$arity
address@hidden {CPS Expression} $values args
+Pass the values named by the list @var{args} to the continuation.
address@hidden deftp
 
-            ;; Terms.
-            $letk $continue $letrec
address@hidden {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
address@hidden continuation.  Prompts are later popped by
address@hidden primcalls.
address@hidden deftp
 
-            ;; Continuations.
-            $cont
+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
address@hidden instance:
 
-            ;; Continuation bodies.
-            $kif $ktrunc $kargs $kentry $ktail $kclause
address@hidden {CPS Continuation Wrapper} $cont k cont
+Declare a continuation labelled @var{k}.  All references to the
+continuation will use this label.
address@hidden deftp
 
-            ;; Expressions.
-            $void $const $prim $fun $call $primcall $values $prompt
+The most common kind of continuation binds some number of values, and
+then evaluates a sub-term.  @code{$kargs} is this kind of simple
address@hidden
 
-            ;; Building macros.
-            let-gensyms
-            build-cps-term build-cps-cont build-cps-exp
-            rewrite-cps-term rewrite-cps-cont rewrite-cps-exp
address@hidden {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}.
address@hidden deftp
 
-            ;; Misc.
-            parse-cps unparse-cps
-            fold-conts fold-local-conts
+Variable names (the names in the @var{syms} of a @code{$kargs}) should
+be globally unique, and also disjoint from continuation labels.  To bind
+a value to a variable and then evaluate some term, you would continue
+with the value to a @code{$kargs} that declares one variable.  The bound
+value would then be available for use within the body of the
address@hidden
 
-cwcc
address@hidden {CPS Continuation} $kif kt kf
+Receive one value.  If it is true for the purposes of Scheme, branch to
+the continuation labelled @var{kt}, passing no values; otherwise, branch
+to @var{kf}.
address@hidden deftp
+
+For internal reasons, only certain terms may continue to a @code{$kif}.
+Compiling @code{$kif} avoids allocating space for the test variable, so
+it needs to be preceded by expressions that can test-and-branch without
+temporary values.  In practice this condition is true for
address@hidden to @code{null?}, @code{=}, and similar primitives that
+have corresponding @address@hidden VM operations; see the source
+code for full details.  When in doubt, bind the test expression to a
+variable, and continue to the @code{$kif} with a @code{$values}
+expression.  The optimizer should elide the @code{$values} if it is not
+needed.
 
-records, unlike early cps (rabbit, orbit)
+Calls out to other functions need to be wrapped in a @code{$kreceive}
+continuation in order to adapt the returned values to their uses in the
+calling function, if any.
+
address@hidden {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 @var{$kargs} continuation
+labelled @var{k}.  As a limitation specific to @code{$kreceive},
address@hidden may only contain required and rest arguments.
address@hidden deftp
+
address@hidden is a helper data structure used by @code{$kreceive} and
+also by @code{$kclause}, described below.
+
address@hidden {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.
address@hidden 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
address@hidden list are source names, not unique variable names.
address@hidden deftp
+
+Additionally, there are three specific kinds of continuations that can
+only be declared at function entries.
+
address@hidden {CPS Continuation} $kentry self tail clauses
+Declare a function entry.  @var{self} is a variable bound to the
+procedure being called, and which may be used for self-references.
address@hidden declares the @code{$cont} wrapping the @code{$ktail} for this
+function, corresponding to the function's tail continuation.
address@hidden is a list of @code{$kclause} @code{$cont} instances.
address@hidden deftp
+
address@hidden {CPS Continuation} $ktail
+A tail continuation.
address@hidden deftp
+
address@hidden {CPS Continuation} $kclause arity cont
+A clause of a function with a given arity.  Applications of a function
+with a compatible set of actual arguments will continue to @var{cont}, a
address@hidden @code{$cont} instance representing the clause body.
address@hidden deftp
+
+
address@hidden Building CPS
address@hidden 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:
address@hidden, @code{build-cps-cont}, and @code{build-cps-exp}.
+
+In the following interface definitions, consider variables containing
address@hidden 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
address@hidden in some contexts, to splice in a previously-built value;
+see the specifications below for full details.
+
address@hidden {Scheme Syntax} build-cps-term ,val
address@hidden {Scheme Syntax} build-cps-term ($letk (cont ...) term)
address@hidden {Scheme Syntax} build-cps-term ($letrec names syms funs term)
address@hidden {Scheme Syntax} build-cps-term ($continue k src exp)
address@hidden {Scheme Syntax} build-cps-exp ,val
address@hidden {Scheme Syntax} build-cps-exp ($void)
address@hidden {Scheme Syntax} build-cps-exp ($const val)
address@hidden {Scheme Syntax} build-cps-exp ($prim name)
address@hidden {Scheme Syntax} build-cps-exp ($fun src meta free body)
address@hidden {Scheme Syntax} build-cps-exp ($call proc (arg ...))
address@hidden {Scheme Syntax} build-cps-exp ($call proc args)
address@hidden {Scheme Syntax} build-cps-exp ($primcall name (arg ...))
address@hidden {Scheme Syntax} build-cps-exp ($primcall name args)
address@hidden {Scheme Syntax} build-cps-exp ($values (arg ...))
address@hidden {Scheme Syntax} build-cps-exp ($values args)
address@hidden {Scheme Syntax} build-cps-exp ($prompt escape? tag handler)
address@hidden {Scheme Syntax} build-cps-cont ,val
address@hidden {Scheme Syntax} build-cps-cont (k ($kargs (name ...) (sym ...) 
term))
address@hidden {Scheme Syntax} build-cps-cont (k ($kargs names syms term))
address@hidden {Scheme Syntax} build-cps-cont (k ($kif kt kf))
address@hidden {Scheme Syntax} build-cps-cont (k ($kreceive req rest kargs))
address@hidden {Scheme Syntax} build-cps-cont (k ($kentry self tail-cont 
,clauses))
address@hidden {Scheme Syntax} build-cps-cont (k ($kentry self tail-cont (cont 
...)))
address@hidden {Scheme Syntax} build-cps-cont (k ($kclause ,arity cont))
address@hidden {Scheme Syntax} build-cps-cont (k ($kclause (req opt rest kw 
aok?) cont))
+Construct a CPS term, expression, or continuation.
address@hidden deffn
 
address@hidden Compiling CPS
address@hidden Compiling CPS
+There are a few more miscellaneous interfaces as well.
 
-In CPS, there are no nested expressions.  Indeed, CPS even removes the
-concept of a stack.  All applications in CPS are in tail context.  For
-that reason, applications in CPS are jumps, not calls.  The @code{(k1)}
-above is nothing more than a @code{goto}.  @code{(k3 42)} is a
address@hidden with a value.  In this way, CPS bridges the gap between the
-lambda calculus and machine instruction sequences.
-
-On the side of machine instructions, Guile does still have a stack, and
-the @code{lambda} forms shown above do not actually result in one
-closure being allocated per subexpression at run-time.  Lambda
-expressions introduced by a CPS transformation can always be allocated
-as labels or basic blocks within a function.  In fact, we make a
-syntactic distinction between closures and continuations in the CPS
-language, and attempt to transform closures to continuations (basic
-blocks) where possible, via the @dfn{contification} optimization pass.
address@hidden {Scheme Procedure} make-arity req opt rest kw 
allow-other-keywords?
+A procedural constructor for @code{$arity} objects.
address@hidden deffn
 
-Values bound by continuations are allocated to stack slots in a
-function's frame.  The compiler from CPS only allocates slots to values
-that are actually live; it's possible to have a value in scope but not
-allocated to a slot.
address@hidden {Scheme Syntax} let-gensyms (sym ...) body ...
+Bind @var{sym...} to fresh names, and evaluate @var{body...}.
address@hidden deffn
 
address@hidden {Scheme Syntax} rewrite-cps-term val (pat term) ...
address@hidden {Scheme Syntax} rewrite-cps-exp val (pat exp) ...
address@hidden {Scheme Syntax} rewrite-cps-cont val (pat cont) ...
+Match @var{val} against the series of patterns @var{pat...}, using
address@hidden  The body of the matching clause should be a template in
+the syntax of @code{build-cps-term}, @code{build-cps-exp}, or
address@hidden, respectively.
address@hidden deffn
 
 @node Bytecode
 @subsection Bytecode


hooks/post-receive
-- 
GNU Guile