CPS in Guile (Guile Reference Manual)

Warning: This is the manual of the legacy Guile 2.2 series. You may want to read the manual of the current stable series instead.

9.4.4.2 CPS in Guile

Guile’s CPS language is composed of continuations. A continuation is a labelled program point. If you are used to traditional compilers, think of a continuation as a trivial basic block. A program is a “soup” of continuations, represented as a map from labels to continuations.

Like basic blocks, each continuation belongs to only one function. Some continuations are special, like the continuation corresponding to a function’s entry point, or the continuation that represents the tail of a function. Others contain a term. A term contains an expression, which evaluates to zero or more values. The term also records the continuation to which it will pass its values. Some terms, like conditional branches, may continue to one of a number of continuations.

Continuation labels are small integers. This makes it easy to sort them and to group them into sets. Whenever a term refers to a continuation, it does so by name, simply recording the label of the continuation. Continuation labels are unique among the set of labels in a program.

Variables are also named by small integers. Variable names are unique among the set of variables in a program.

For example, a simple continuation that receives two values and adds them together can be matched like this, using the match form from (ice-9 match):

(match cont
  (($ $kargs (x-name y-name) (x-var y-var)
      ($ $continue k src ($ $primcall '+ (x-var y-var))))
   (format #t "Add ~a and ~a and pass the result to label ~a"
           x-var y-var k)))

Here we see the most common kind of continuation, $kargs, which binds some number of values to variables and then evaluates a term.

CPS Continuation: $kargs names vars term: Bind the incoming values to the variables vars, with original names names, and then evaluate term.

The names of a $kargs are just for debugging, and will end up residualized in the object file for use by the debugger.

The term in a $kargs is always a $continue, which evaluates an expression and continues to a continuation.

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

There are a number of expression kinds. Above you see an example of $primcall.

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

The variables that are used by $primcall, or indeed by any expression, must be defined before the expression is evaluated. An equivalent way of saying this is that predecessor $kargs continuation(s) that bind the variables(s) used by the expression must dominate the continuation that uses the expression: definitions dominate uses. This condition is trivially satisfied in our example above, but in general to determine the set of variables that are in “scope” for a given term, you need to do a flow analysis to see what continuations dominate a term. The variables that are in scope are those variables defined by the continuations that dominate a term.

Here is an inventory of the kinds of expressions in Guile’s CPS language, besides $primcall which has already been described. Recall that all expressions are wrapped in a $continue term which specifies their continuation.

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

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

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

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

CPS Expression: $branch kt exp

Evaluate the branching expression exp, and continue to kt with zero values if the test evaluates to true. Otherwise continue to the continuation named in the outer $continue term.

Only certain expressions are valid in a $branch. Compiling a $branch avoids allocating space for the test variable, so the expression should be evaluatable without temporary values. In practice this condition is true for $primcalls to null?, =, and similar primitives that have corresponding br-if-foo VM operations; see the source code for full details. When in doubt, bind the test expression to a variable, and branch on a $values expression that references that variable. The optimizer should inline the reference if possible.

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

There are two sub-languages of CPS, higher-order CPS and first-order CPS. The difference is that in higher-order CPS, there are $fun and $rec expressions that bind functions or mutually-recursive functions in the implicit scope of their use sites. Guile transforms higher-order CPS into first-order CPS by closure conversion, which chooses representations for all closures and which arranges to access free variables through the implicit closure parameter that is passed to every function call.

CPS Expression: $fun body: Continue with a procedure. body names the entry point of the function, which should be a $kfun. This expression kind is only valid in higher-order CPS, which is the CPS language before closure conversion.

CPS Expression: $rec names vars funs: Continue with a set of mutually recursive procedures denoted by names, vars, and funs. names is a list of symbols, vars is a list of variable names (unique integers), and funs is a list of $fun values. Note that the $kargs continuation should also define names/vars bindings.

The contification pass will attempt to transform the functions declared in a $rec into local continuations. Any remaining $fun instances are later removed by the closure conversion pass. By default, a closure is represented as an object built by a $closure expression.

CPS Expression: $closure label nfree: Build a closure that joins the code at the continuation named label with space for nfree free variables. The variables will be initialized later via free-set! primcalls. This expression kind is part of first-order CPS.

If the closure can be proven to never escape its scope then other lighter-weight representations can be chosen. Additionally, if all call sites are known, closure conversion will hard-wire the calls by lowering $call to $callk.

CPS Expression: $callk label proc args: Like $call, but for the case where the call target is known to be in the same compilation unit. label should denote some $kfun continuation in the program. In this case the proc is simply an additional argument, since it is not used to determine the call target at run-time.

At this point we have described terms, expressions, and the most common kind of continuation, $kargs. $kargs is used when the predecessors of the continuation can be instructed to pass the values where the continuation wants them. For example, if a $kargs continuation k binds a variable v, and the compiler decides to allocate v to slot 6, all predecessors of k should put the value for v in slot 6 before jumping to k. One situation in which this isn’t possible is receiving values from function calls. Guile has a calling convention for functions which currently places return values on the stack. A continuation of a call must check that the number of values returned from a function matches the expected number of values, and then must shuffle or collect those values to named variables. $kreceive denotes this kind of continuation.

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

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

CPS Data: $arity req opt rest kw allow-other-keys?

A data type declaring an arity. req and opt are lists of source names of required and optional arguments, respectively. rest is either the source name of the rest variable, or #f if this arity does not accept additional values. kw is a list of the form ((keyword name var) ...), describing the keyword arguments. allow-other-keys? is true if other keyword arguments are allowed and false otherwise.

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

Additionally, there are three specific kinds of continuations that are only used in function entries.

CPS Continuation: $kfun src meta self tail clause: Declare a function entry. src is the source information for the procedure declaration, and meta is the metadata alist as described above in Tree-IL’s <lambda>. self is a variable bound to the procedure being called, and which may be used for self-references. tail is the label of the $ktail for this function, corresponding to the function’s tail continuation. clause is the label of the first $kclause for the first case-lambda clause in the function, or otherwise #f.

CPS Continuation: $ktail: A tail continuation.

CPS Continuation: $kclause arity cont alternate: A clause of a function with a given arity. Applications of a function with a compatible set of actual arguments will continue to the continuation labelled cont, a $kargs instance representing the clause body. If the arguments are incompatible, control proceeds to alternate, which is a $kclause for the next clause, or #f if there is no next clause.