265: The CFG Language265: The CFG Languageby Marc Nieper-Wißkirchen
This SRFI is currently in draft status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-265@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.
This SRFI defines a language to describe control-flow graphs (CFGs) suitable for formulating iterative and recursive algorithms. Using the notion of a CFG term, this language can be seamlessly embedded in the Scheme language. Complex CFG terms can be composed from simple CFG terms.
The language described in this SRFI is not meant to be directly used in programs but by library authors to build abstractions like loop facilities on top of it.
Withdraw SRFI 242 as soon as SRFI 265 is finalized. SRFI 265's title deliberately coincides with SRFI 242's title.
The planned SRFI on loops should be submitted during the draft period of this SRFI so that it can point to the loop SRFI.
In the Scheme language, procedures (and thus jump labels, according to lambda-the-ultimate philosophy) are first-class entities. In a certain sense, this makes the control-flow graph of a Scheme program a dynamic and not static entity.
The CFG language described in this SRFI, on the other hand, describes a static control-flow graph. For the applications where this is sufficient, this has the advantage that the control-flow graph can be readily statically reasoned about, allowing one, in particular, to define variable scope in terms of it.
The CFG language itself is useful for describing iterative and recursive algorithms more clearly than it is possible in the Scheme language through tail calls and (multiple) return values. Its raison d'être, however, is that more specialized languages like that of a loop facility can be easily built on top of it.
The origin of the CFG language described in this SRFI is Olin
Shiver's paper The Anatomy of a Loop: A story of scope and
control. In his paper, he makes two important
points: The main iterative control construct in Scheme is a tail
call. While a tail call as a goto that passes arguments
is a pretty powerful construct, it is also as low-level as a
goto. His first point is that this implies that it is not the
right tool to write down iterative algorithms in a high-level
fashion. This fact has stimulated the search for loop
facilities allowing one to express iterative algorithms more
abstractly and more composably. His second point is that just as
the scoping of variables is well-defined in the Scheme
language, a well-defined model of (loop) variable scoping is
needed for loop facilities as well. For this, he formulates a
new scoping rule, namely that binders dominate references.
While not all surface syntax has been adopted from Olin Shiver's paper, the core of the language described here subsumes his conception. The addition of a facility to handle not only iterative but also recursive algorithms is a new invention in this SRFI. This addresses a third perceived shortcoming of the Scheme language. Recursive algorithms in Scheme are based on the fact that Scheme procedures return values, possibly multiple ones. However, as soon as more than one value needs to be returned and each recursion step only needs to modify one of them, a position-only identification of return values becomes unclear and leads to repetition of code. Instead, the CFG language in this SRFI gives names to intermediate results and allows parallel processing of them.
Thanks to Scheme's expressive macro system, the CFG language can be seamlessly implemented in the standard Scheme language, fully respecting Scheme semantics.
The author plans to submit a SRFI describing an extensible loop facility built on the CFG language defined in this SRFI in the future.
The CFG syntax
keywords label*, labels, and
call of SRFI 242 have been renamed
to let*, letrec, and go,
respectively. Similarly, bind of SRFI 242 has
been renamed to let-values, and the single-value
variant let, including its named form, has been
added. Unlike the CFG keywords of SRFI 242, let,
let-values, let*, and
letrec use the corresponding Scheme keyword
bindings.
The execute CFG term of SRFI 242 has been replaced
by branch. Instead of evaluating a procedure
expression and passing it anonymous successor procedures as
arguments, branch evaluates an expression with
named targets bound to the successor procedures.
The roles of the halt and finally CFG
terms of SRFI 242 have been divided between
return-values and defer. An empty
return takes the place of halt, but
propagates its incoming CFG state instead of discarding it. A
non-empty return-values can introduce any number of groups
of bindings at once, whereas each SRFI 242
finally term introduced one group. The
sequencing-after-return role of SRFI 242's
finally is provided by defer. For
single-value bindings, derived return and
finally forms complement return-values
and finally-values. The binding-list syntax of the
new finally forms differs from that of SRFI 242.
SRFI 242 distinguished loop variables, defined on forward flow, from return variables, defined on backward flow, and gave them separate scope rules based on dominance and strict post-dominance, respectively. This SRFI treats them as one kind of CFG variable and replaces the separate rules with one scope and visibility rule.
The permute syntax of SRFI 242 has been split
into permute and permute/tail, which
have the semantics described in The Anatomy of a
Loop. In particular, pending pairs introduced by
permute/tail now carry forward across
go terms to all labels.
The execute, halt, and
finally CFG terms of SRFI 242 could be evaluated
within and materialize a non-empty pending set. It is instead
a syntax violation for branch, both return forms,
or defer to be potentially called within a
non-empty pending set.
The starred versions of define-cfg-syntax
and define-cfg-label have been removed.
The syntax of free references to labels defined
by define-cfg-label has been changed
from label
to (label).
The formal semantics now describes CFG terms as being called directly within a pending set and with a CFG state. SRFI 242 instead described CFG terms as being evaluated during expansion to produce CFG blocks that were later called at run time.
Static and dynamic labels are no longer distinguished.
The sample implementation no longer depends on SRFI 213 and is a portable R6RS implementation. The language is also designed to be implementable in pure R7RS.
We start with two complex examples before we begin with a gentle introduction from the beginning.
The following expression evaluates to an (iterative) procedure that takes a list of integers and returns two values, the number of even and the number of odd values in the list.
(lambda (n*)
(cfg
(let f ([n* n*] [e 0] [o 0])
(branch ([(next n n*)
(branch ([(even e) (go f)]
[(odd o) (go f)])
(if (odd? n)
(odd (+ o 1))
(even (+ e 1))))]
[(done)
(return-values [(e o) (values e o)])])
(if (null? n*)
(done)
(next (car n*) (cdr n*)))))
(values e o)))
The following expression evaluates to a (recursive) procedure that takes a list of integers and returns two values, the sublist of even values and the sublist of odd values.
(lambda (n*)
(cfg
(let f ([n* n*])
(branch ([(next n n*)
(branch ([(even)
(finally ([e* (cons n e*)])
(go f))]
[(odd)
(finally ([o* (cons n o*)])
(go f))])
(if (odd? n) (odd) (even)))]
[(done)
(return-values [(e* o*) (values '() '())])])
(if (null? n*)
(done)
(next (car n*) (cdr n*)))))
(values e* o*)))
cfg formA cfg expression lets control flow along the edges
of a control-flow graph (CFG) defined by the cfg
expression, potentially binding so-called CFG variables, until
a return or return-values CFG term is
reached. Then, control flows
backwards along the edges previously taken, potentially making
further CFG-variable bindings. A defer CFG term may
call another CFG term after its last CFG term returns. Finally
a Scheme expression is evaluated in an environment extended by
these bindings, and its
values are returned.
The general form of a cfg expression is
(cfg cfg
term result expression)
where the cfg term describes
the CFG and result
expression is an arbitrary Scheme expression.
The simplest CFG is just one consisting of an empty
return CFG term:
(return)
For example, we have
(cfg (return) (+ 1 2))3
as the control flow along this CFG, which has no edges, immediately stops, leading on to the evaluation of the result expression.
Return and return-values CFG terms are
used to bind CFG variables. Their syntax is:
(return [variable expression] …)
(return-values [formals expression] …)
Return is the single-value counterpart of
return-values. When control enters either term, the (Scheme)
expressions are evaluated
to yield values that are bound as CFG variables to the
respective variables or formals.
For example, return-values supports a dotted
formals:
(cfg
(return-values [(x . y) (values 1 2 3)])
(list x y)(1 (2 3))
A more complicated example is the following:
(let ([x 1])
(cfg
(defer ([(finish y)
(return [y y])])
(let-values ([(y) (+ x 2)])
(finish y))
(return [x (+ x 1)]))
(list x y)))(2 4)
A defer CFG term calls its last CFG term first.
After this CFG term has returned, the Scheme expression is
evaluated with the CFG variables visible in the returned CFG
state. Each target, such
as finish above, is bound to a procedure in this
expression. The expression must tail-call
exactly one target. Calling (finish y) resumes
forward control with the corresponding CFG term.
In the example, the last CFG term binds the CFG
variable x to 2. This binding is
visible in (+ x 2), so finish is
invoked with 4. The corresponding CFG term receives
the binding of x as part of the current CFG state.
The target formal y is an ordinary Scheme variable,
lexically scoped over the corresponding target CFG term and bound
to the explicitly passed value. The return term then
defines a CFG variable also named y.
A binding made by the last CFG term is also directly visible in the corresponding CFG term:
(cfg
(defer ([(finish)
(return [result (+ r 1)])])
(finish)
(return [r 8]))
result)9
The general syntax of a defer CFG term is:
(defer
([(target . formals)
cfg term] …)
expression
cfg term)
Targets use ordinary procedure-call semantics. Thus, several
arguments can be passed with (finish x y), and a list
of arguments can be passed with
(apply finish argument-list).
When a defer term is only needed to bind CFG
variables after its last CFG term returns, the derived
finally and finally-values forms are more
concise. Their syntax is:
(finally
([variable expression]
...) cfg term)
(finally-values
([formals expression]
...) cfg term)
The CFG term is called first. After it returns, the expressions are evaluated in an unspecified order with its visible CFG-variable bindings, and their values are bound as CFG variables in parallel. Thus, the earlier example can be written more simply as:
(let ([x 1])
(cfg
(finally ([y (+ x 2)])
(return [x (+ x 1)]))
(list x y)))(2 4)
While defer CFG terms are used to perform
actions after their last CFG term returns, branch
CFG terms perform actions during the initial forward flow
through the CFG. The syntax of a branch CFG term is given by
(branch
([(target . formals)
cfg term] …)
expression)
Each target is bound to a procedure accepting arguments according
to its formals. When the
forward control flow through the CFG reaches a
branch CFG term, the expression is evaluated and
must tail-call one of the targets. Targets use ordinary
procedure-call semantics and can, for example, be passed to
apply.
Control flow then proceeds with the
corresponding cfg
term:
(let ([x 1] [y 2])
(cfg
(defer ([(finish y)
(return [y y])])
(finish (+ x 3))
(branch ([(e) (return)])
(begin
(set! x y)
(e))))
(list x y)))(2 5)
In this example, the forward control flow passes through
the defer CFG term before it reaches
the branch block. The expression is
evaluated in the environment where x is bound
to 1 and y is bound to 2.
The tail call to e lets the control flow continue
with the empty return CFG term, from where it flows
backward. The backward control flow passes through
the branch CFG term before the defer expression is
evaluated. It invokes finish with the result
of (+ x 3), and the corresponding CFG term binds the
CFG variable y to that result, 5.
Branch CFG terms are used to create CFGs with
branches. For this, more than one cfg
term has to be provided. Consider the following example:
(let ([x 1] [y 2])
(cfg
(branch ([(e1) (return)]
[(e2) (return [x 3])])
(if (odd? y) (e1) (e2)))
(+ x 10)11
Here, the control flow exiting the branch CFG term
can proceed along two possible edges, e1
and e2, depending on the parity of y
in this example. It stands out that the value of the example
expression is not 13, as one might have expected,
but 11. In other words, the binding
of x that is visible in (+ x 10) is
the let binding of x and not the
CFG-variable binding introduced in
the second return CFG term. To understand this, we have
to introduce the rule by which the scope of definitions made by
both return forms is determined. During backward flow, a CFG
term (and, likewise, the
result expression) is in the
scope of such a CFG variable if and only if a definition of the
variable post-dominates the CFG term, that is if every possible
control-flow path starting at the CFG term and ending at a CFG
term in either return form passes through such a definition.
Such a binding does not exist
during the original forward flow before its definition. It is
visible during backward flow and, when a defer term
resumes forward control, enters the corresponding CFG term as
part of the same CFG state. In the example above,
there is a (statically possible) control-flow path from the entry
block to the first return CFG term that does not
pass through a definition of the CFG
variable x. Compare with the following two
examples:
(let ([x 1] [y 2])
(cfg
(branch ([(e1) (return [x #f])]
[(e2) (return [x 3])])
(if (odd? y) (e1) (e2)))
(+ x 10)13
(let ([x 1] [y 2])
(cfg
(finally ([x 3])
(branch ([(e1) (return)]
[(e2) (return)])
(if (odd? y) (e1) (e2))))
(+ x 10)))13
So far, we haven't talked about
the formals that appear in
a branch CFG term. Using these, we can bind CFG
variables during forward control flow. The value to which a
CFG variable is bound
when control flow leaves along an edge of
a branch CFG term is passed as an argument to
the tail-called target that corresponds to the edge:
(let ([x 1])
(cfg
(branch ([(e x) (return [y (+ x 3)])])
(e (+ x 2)))
y)6
In (+ x 2), the variable x
is let-bound to 1, and in (+ x
3) the binding as a CFG variable to (+ 1 2)
is visible.
While the scoping rule for definitions made by both return forms
is based on the post-dominance relation, the
scoping rule for definitions made on forward edges is based on
the dominance relation: A CFG term is in the scope of a CFG
variable if definitions of this variable dominate
the CFG term, that is if all possible control flow paths
starting at the entry of the whole CFG and ending at the CFG
block pass through a definition of the variable, which happens
along an edge exiting a branch CFG term. Such a
binding remains in the CFG state during backward flow until the
CFG term called with that binding returns. A CFG term
corresponding to a target of a defer CFG term is
called with the CFG state returned by the last CFG term unchanged.
The target's formals are ordinary Scheme variables, lexically scoped
over that target CFG term; they are not bindings in the CFG state.
In the following example, the definitions of
the CFG variable x do not dominate the expression (+ x 3):
(let ([x 1] [y 2])
(cfg
(branch ([(e1 x) (return [y (+ x 2)])]
[(e2) (return [y (+ x 3)])])
(if (odd? y) (e1 5) (e2)))
y))4
The expressions in both return forms and in defer
CFG terms are evaluated with all CFG variables visible at that
point. A later binding shadows an earlier same-named binding,
independently of which CFG term made either binding. In the
following example, x is the outer Scheme variable
bound to 1 in (+ x 1). The forward CFG
binding is 2 in (+ x 3). The returned
CFG binding is 5 in (+ x 2); the target
call passes 7, which is visible as an ordinary Scheme
formal in the target term. The subsequent return
defines a CFG binding of x to 7, so
x is 7 in (+ x 4):
(let ([x 1])
(cfg
(branch ([(e x)
(defer ([(finish x)
(return [x x])])
(finish (+ x 2))
(return [x (+ x 3)]))])
(e (+ x 1)))
(+ x 4)))11
Other CFG terms that can be used to define CFG variables on
forward flow are let-values and let.
Their syntax is:
(let-values
([formals expression]
...) cfg term)
(let
([variable expression]
...) cfg term)
(let label
([variable expression]
...) cfg term)
When the forward control flow reaches a let-values CFG
term, the expressions are
evaluated in the same environment in which
the expression
of a branch CFG term would be evaluated. Then,
all formals are bound in parallel, and the CFG-variable bindings
become visible in the cfg
term, with which the forward control flow
proceeds. The let CFG term is the single-value
variant of let-values. These terms are analogous to
the Scheme expressions with the same names, but bind CFG
variables instead of Scheme variables. In the named
let form, label
is recursively bound in the cfg
term, and control initially proceeds to it with the
new CFG-variable bindings.
(let ([x 1] [y 2])
(cfg
(let-values ([(x y) (values y x)])
(return-values [(x y) (values x y)]))
(list x y)))(2 1)
When each expression produces exactly one value, the same
bindings can be written with let:
(let ([x 1] [y 2])
(cfg
(let ([x y]
[y x])
(return-values [(x y) (values x y)]))
(list x y)))(2 1)
In order to construct more interesting examples, we need to be
able to introduce loops in control-flow graphs. This is
possible with the use of letrec CFG terms, which have
the following syntax:
(letrec
([label cfg
term] …) body cfg
term)
where each label is an
identifier. A letrec CFG term binds
the labels to
the cfg terms, and this
binding is visible within the cfg
terms and the body cfg
term, much like the semantics of
the letrec expression for Scheme code. When
(forward) control flow enters a letrec CFG term,
the control flow is passed to the body
cfg term.
Control can flow to the cfg
term using go CFG terms with the
corresponding label. The syntax of a go CFG term
is:
(go label)
Labels occupy a different namespace than variables (of any kind) or keywords. Labels are lexically scoped.
(let ([x 1])
(cfg
(letrec ([x (return [x x])])
(go x))
x))1
In the following example (adapted from Olin Shiver's paper),
the return CFG term is dominated by definitions of
the CFG variable y. When the control flows through
the label la, the CFG variable y is
bound before going to la; otherwise, when the control
flows through the label lb, the CFG
variable y is bound before going
to lj:
(let ([x 1]
[f (lambda (y) (set! x y))]
[g (lambda (y) (set! x (- y 1)))])
(cfg
(letrec ([lj (return [y (+ y 10)])]
[la (branch ([(e1) (go lj)])
(begin (f y) (e1)))]
[lb (branch ([(e1 y) (go lj)])
(begin (g x) (e1 (* x x))))])
(branch ([(e1 y) (go la)]
[(e2) (go lb)])
(if (odd? x)
(e1 (+ x 1))
(e2))))
(list x y)))(2 12)
A CFG term corresponding to a defer target can
use go to restart forward flow at a statically bound
label:
(let ([retry? #t])
(cfg
(letrec ([l
(defer ([(again) (go l)]
[(done) (return)])
(if retry?
(begin
(set! retry? #f)
(again))
(done))
(return [result 42]))])
(go l))
result))42
The last CFG term returns before the expression is
evaluated. On its first evaluation, again
re-enters the CFG term at the same static label. On the second,
done calls the corresponding empty
return CFG term, which adds no new CFG-variable bindings,
so the binding returned by the last CFG term remains visible.
Let* is another binding construct for CFG labels;
it has a similar relation to letrec as
Scheme's let* has to Scheme's letrec.
In particular, the binding of a label by let* is not
visible within the CFG term bound by the label but only further to
the right. The syntax of let* does not differ from
the letrec syntax:
(let*
([label cfg
term] …) body cfg
term)
The semantics of let* can be explained through
the following rule: Replace all occurrences
of (go label)
in body cfg term
by cfg term when the
binding of the
corresponding label is not
(lexically) shadowed by another label binding.
(cfg
(let* ([l (return [x 42])]
[l (go l)])
(go l))
x)42
In principle, the same replacement semantics works
for letrec but may give an infinite tree in that
case.
The next CFG term that needs to be discussed
is permute. Its general syntax is:
(permute
([label cfg
term] …) body cfg
term)
When the forward control flow enters a permute CFG
term, the cfg terms
together with their labels
are dynamically permuted, and control then passes to the then
first CFG term. Within the lexical scope of this CFG term, the
corresponding label is
bound so that when it is jumped to, control proceeds to the then
second cfg term and so on
until the then final cfg
term is reached whose accompanying label is bound
so that when called, control finally proceeds to
the body cfg term
term.
(cfg
(permute ([p (let ([x 10])
(go p))]
[p (let ([y 20])
(go p))])
(return [z (list x y)]))
z)(10 20)
So far, the permute CFG term just looks like an
inside-out let* form up to the permutation that
is involved. The permute CFG term's purpose comes
from the non-determinism it introduces. In the above example,
the sequencing of the two let CFG terms is not
determined, i.e. whether the forward control flow first passes
through the lexically first let CFG term and then
through the lexically second, or vice versa. In the above
example, it does not matter. In general, the non-determinism
shows up through the binding of CFG variables. The
definition of x by the first let CFG
term does not dominate the second let CFG term
(more precisely, the CFG term it describes), because a possible
control flow (coming from a different sequencing) coming from
the entry passes the second CFG term before the first. This is
demonstrated in the following two examples:
(let ([x 1])
(cfg
(permute ([p (let ([x 2])
(go p))]
[p (let ([y x])
(go p))])
(return [z (list x y)]))
z))(2 1)
(let ([x 1])
(cfg
(permute ([p (finally ([y x])
(go p))]
[p (finally ([x 2])
(go p))])
(return))
(list x y)))(2 1)
The final CFG term that needs to be discussed
is permute/tail. It is like permute
except that the permutation property
of permute/tail CFG terms also propagates to the
bodies of let* and letrec forms and
through going to labels:
(let ([x 1] [y 10])
(cfg
(permute/tail ([p (let ([x 2])
(go p))])
(letrec ()
(let* ([p (permute ([p (let ([z (list x y)])
(go p))])
(return-values [(x y z) (values x y z)]))])
(permute/tail ([p (let ([y x])
(go p))])
(go p)))))
(list x y z)))(2 1 (1 10))
The final concept we need to explain are macros for
the cfg form. Like define-syntax is
used to define Scheme macros, we use
the define-cfg-syntax definition here, which is an ordinary Scheme definition and of the following form:
(define-cfg-syntax cfg keyword transformer expression)
When the expander processes a cfg form, it expands
CFG macro uses, which look like Scheme macro uses except
that a cfg keyword is used
instead of a
(Scheme) keyword. CFG
macros are expanded by the usual Scheme macro
expansion algorithm. An example is worth a thousand words:
(define-cfg-syntax loop
(lambda (stx)
(syntax-case stx ()
[(_ n-expr lp-lbl loop-cfg-term body-cfg-term)
(identifier? #'lp-lbl)
#'(let lp-lbl ([n n-expr])
(branch ([(loop n) loop-cfg-term]
[(done) body-cfg-term])
(if (zero? n)
(done)
(loop (- n 1)))))])))
(cfg
(let ([n 0])
(loop 10 next
(let ([n (+ n 2)])
(go next))
(return [n n])))
n)20
The example above also demonstrates the usual hygiene
provisions of (Scheme) macros; the variable n
introduced in the macro is effectively renamed so that it
doesn't shadow the variable n in the macro use.
This hygiene is also the reason why the label next
has to be given as an argument to the macro. One can actually
get rid of this as the following example shows:
(define-cfg-label next)
(define-cfg-syntax loop
(lambda (stx)
(syntax-case stx ()
[(_ n-expr loop-cfg-term body-cfg-term)
#'(let ([n n-expr])
(letrec ([(next)
(branch ([(loop n) loop-cfg-term]
[(done) body-cfg-term])
(if (zero? n)
(done)
(loop (- n 1))))])
(go (next))))])))
(cfg
(let ([n 0])
(loop 10
(let ([n (+ n 2)])
(go (next)))
(return [n n])))
n)20
Here, we used the define-cfg-label definition, whose syntax is simply:
(define-cfg-label free-label)
(Free-label is
syntactically an identifier.) This definition
binds free-label in the
label binding space to a fresh label
and (free-label) is
replaced by this label
in letrec, let*, and go
CFG terms where free-label
is in scope.
The identifiers defined in this section are exported by
the (srfi :265 cfg) and the (srfi :265)
libraries in case of an R6RS system and by
the (srfi 265) library in case of an R7RS
system.
Remark: This section is a formal account of the syntax
and semantics of the cfg form. It should not be
misunderstood as a gentle introduction, which was given in the
previous section.
In order to describe the computation model of the CFG language, which is not the same computation model underlying Scheme (but can be expressed in the latter as the portable implementation shows), a couple of primitive notions have to be introduced, that is the grammatical context in which they are used. Their semantic meaning only follows from the context in which they are used below.
A CFG term is a syntactic construct in the CFG language that can be called within a pending set and with a CFG state. The result of this call is again a CFG state.
A CFG state is a sequence of bindings of CFG variables to Scheme values.
A pending set is a finite set of pairs consisting of a CFG label and a CFG term.
A CFG label is an identifier.
A CFG variable is defined in a CFG
term and is associated with an identifier. The
target formals of branch and the formals of
let-values, as well as the variables of
let, define CFG variables on forward flow. The
formals of return-values and
finally-values, as well as the variables of
return and finally, define CFG
variables on backward flow.
These are definitions of the same kind of variable. The
target formals of defer are ordinary, lexically
scoped Scheme variables and do not define CFG variables.
A CFG term occurs in the scope of a CFG variable if the CFG term will potentially only be called with CFG states in which the CFG variable is bound.
The visible CFG-variable bindings of a CFG term in a CFG state are those bindings in the CFG state whose CFG variables are in the scope of the CFG term and which are not shadowed by later bindings in the CFG state associated with the same identifier.
By abuse of language, extending an environment by the visible CFG-variable bindings in a CFG state means extending the environment by binding the identifiers associated with the visible CFG-variable bindings to fresh locations initially holding the values to which the CFG variables are bound in the CFG state.
Each entry is of one of two categories, “syntax” or “cfg syntax”. The first category is as in R6RS and R7RS, while an entry of the second category describes a syntactic construct in the CFG language.
A label is either
a free label reference of the
form (free label) or a
simple label of the
form identifier. The
corresponding CFG label is
the identifier.
Syntactically, a free
label is
an identifier.
(cfg cfg term result expression)Syntax: Cfg
term is an arbitrary CFG
term. Result expression
is an arbitrary Scheme expression.
Semantics: During expand-time, the CFG macros (see
below) occurring in the cfg
term are recursively expanded in lexical order
so that no macro uses remain. Then, free label references
(see below) are expanded so that only simple labels
remain.
A cfg expression is evaluated by first calling
the cfg term within
an empty pending set and with an empty CFG state. The
environment of the cfg expression is then
extended by binding the visible CFG variables of the
returned CFG state. Finally,
the result expression
is evaluated in this extended environment and its values
returned as the results of the cfg
expression.
The simplest cfg expression just returns some
value(s). (Both return forms and the other cfg terms are described
in the next subsection.) For example:
(cfg (return) 'done)done
Using a return-values cfg term, CFG variables can be
bound that can be used in the result
expression:
(let ([x 1])
(cfg (return-values [(x y) (values (+ x 1) (+ x 2))])
(list x y)))(2 3)
CFG variables can also be bound on the forward edges of
branch terms:
(let ([x 1])
(cfg (branch ([(e x) (return [res x])])
(e (+ x 1)))
res))2
Branch CFG terms can have more than one successor.
During evaluation, one control path is (dynamically) chosen:
(let ([x 1])
(cfg (branch ([(e1) (return [res 'even])]
[(e2 a) (return [res a])])
(if (even? x) (e1) (e2 'odd)))
res))odd
Due to the scope of a CFG variable defined on forward flow, the
return CFG term
in the second branch cannot simply be factored into an enclosing
defer CFG term because its Scheme expression is
evaluated after the CFG term called with the binding of
a has returned, so that variable is no
longer in scope:
(let ([a 'outer]
[x 1])
(cfg (defer ([(finish res)
(return [res res])])
(finish a)
(branch ([(e1) (return [res 'even])]
[(e2 a) (return)])
(if (even? x) (e1) (e2 'odd)))
res))outer
And due to the post-dominance rule for the definition made by
return, the
enclosing defer cannot simply be left out because
the entry block would no longer be post-dominated by a definition of
the CFG variable res:
(let ([res 'outer]
[x 1])
(cfg (branch ([(e1) (return)]
[(e2 a) (return [res a])])
(if (even? x) (e1) (e2 'odd)))
res))outer
The main reason for defining CFG variables on forward flow is
that the CFG language allows writing loops. This can be done
particularly conveniently with named let:
(cfg (let f ([x 1] [a 1])
(branch ([(e1) (return [res a])]
[(e2 x a) (go f)])
(if (> x 6)
(e1)
(e2 (+ x 1) (* a x)))))
res)720
Finally, permute and permute/tail CFG
terms can be used to create sequences of CFG terms so that CFG
variables introduced in these blocks do not
have the other blocks of this sequence in scope (comparable to
scoping rules of the let expression of Scheme):
(let ([x 'outer] [y 'outer])
(cfg (let* ([c (permute ([p (finally ([y 'inner])
(let ([a x]) (go p)))])
(return [a a]))])
(permute/tail ([(p) (finally ([b y])
(let ([x 'inner]) (go p)))])
(go c)))
(list a b)))(outer outer)
(Using permute/tail, permutation sequences carry
forward across calls to labels introduced
by let* and letrec.)
The following entries describe the primitive CFG terms. Simple labels do not occupy the same namespace as keywords and all kind of variables. That is, within the same scope, an identifier can be bound as a simple label and as a variable or keyword, and local bindings of either kind do not shadow other bindings of the other kind.
(branch
([(target . formals)
cfg term] …)
expression)
There must be at least one
target. Each
target must be an
identifier, and the targets must be pairwise distinct. It
is a syntax violation if a branch CFG term may
potentially be called within a non-empty pending set.
The branch CFG term defines a CFG variable on
forward flow for each variable in the formals.
Each target is
hygienically bound as a variable whose value is a procedure
accepting arguments according to its
formals. The region of
these bindings is the expression.
When the branch CFG term is called with a CFG
state, the environment of the surrounding cfg
expression is extended by the visible CFG-variable
bindings. The expression
is then evaluated in tail context in this extended
environment. Exactly one target must be called, and the
call must be a tail call; the implementation is not
required to detect a violation of this requirement. When a
target is called, the CFG state is extended by binding the
CFG variables associated with
the formals to the
arguments of the call, and the
corresponding cfg term
is then tail-called with the extended CFG state. The new
bindings remain in the CFG state during forward flow and on
the subsequent backward path until the corresponding CFG term
returns, at which point they are removed from the state.
The resulting CFG state is then returned.
The branch CFG term potentially calls
each cfg term, which
is relevant for the definition of scope.
(return-values [formals
expression] …)It is a syntax violation if a return-values CFG term may
potentially be called with a non-empty pending set.
The return-values CFG term defines a CFG variable on
backward flow
for each variable
in each formals.
When the return-values CFG term is called with a CFG
state, the environment of the surrounding cfg
expression is extended by the visible CFG-variable
bindings. The expressions
are then evaluated in an unspecified order in this extended
environment. The CFG-variable bindings defined by the
return-values CFG term are not in scope in any of these
expressions; an earlier binding associated with the same
identifier may nevertheless be visible there. None of the
expressions is required to be in tail context. The CFG
state is then extended with bindings of
the CFG variables associated with each
formals to the
values received from evaluating the corresponding expression,
and the extended state is returned, beginning backward
control flow. In
particular, (return-values) adds no bindings and
returns the state it received.
(letrec
([label cfg term]
…) body cfg term)
It is a syntax violation if
a label occurs more
than once.
Each label is bound
to the corresponding cfg
term. These bindings are visible in
all cfg terms and in
the body cfg term and
shadow lexically earlier bindings of label
there.
When the letrec CFG term is called within a
pending set and a CFG state, it tail-calls
the body cfg term within
the pending set and with this CFG state and the resulting CFG
state is returned.
(let*
([label cfg term]
…) body cfg term)
Each label is bound
to the corresponding cfg
term. These bindings are visible in all
lexically following cfg
terms, respectively, and in
the body cfg term and
shadow lexically earlier bindings of label
there.
When the letrec CFG term is called within a
pending set and a CFG state, it tail calls
the body cfg term with
the pending set and this CFG state and the resulting CFG
state is returned.
(go label)It is an undefined violation
if label is not bound as a label.
When the go CFG term is called within a pending
set and with a CFG state, the CFG term to
which label is bound
is tail-called within the pending set and with the CFG state
and the resulting CFG state is returned.
(defer
([(target . formals)
cfg term] …)
expression
cfg term)
There must be at least one
target. Each
target must be an
identifier, and the targets must be pairwise distinct. It
is a syntax violation if a defer CFG term may
potentially be called within a non-empty pending set.
Each variable in a
target's formals is an
ordinary Scheme variable. Its lexical region is the
corresponding cfg term.
It is not visible in the
expression, the last
cfg term, or a CFG term
corresponding to another target, and it does not define a
CFG variable.
Each target is
hygienically bound as a variable whose value is a procedure
accepting arguments according to its
formals. The region of
these bindings is the expression.
Exactly one target must be called while evaluating the
expression, and the call
must be a tail call; the implementation is not required to
detect a violation of this requirement.
When the defer CFG term is called with a CFG
state, the last
cfg term is called
within an empty pending set and with this CFG state.
This call is not in tail context. After it returns a CFG
state, the environment of the surrounding
cfg expression is extended by the visible
CFG-variable bindings of the returned state. The
expression is
evaluated in tail context in this environment.
When a target is called, its
formals are bound to the
arguments according to ordinary Scheme procedure-call
semantics, and the
corresponding cfg term
is called within an empty pending set and with the CFG state
returned by the last CFG term unchanged. This call is not
in tail context. Thus, bindings
made by return-values in the last CFG term enter the
corresponding CFG term without having to be passed through
the target's formals. Dynamic
extents established while evaluating the
expression remain
active while the corresponding CFG term is
called.
When the corresponding CFG term returns, the procedure call
finishes and the ordinary lexical bindings of its formals
cease to be in scope. The returned CFG state is returned
by the defer term. A later binding produced
by the corresponding CFG term shadows a visible same-named
binding produced by the last CFG term.
The defer CFG term potentially calls the
last cfg term and every
cfg term corresponding
to a target,
which is relevant for the definition of scope.
(permute ([label cfg term] …)
body cfg term)When a permute CFG term is called within a
pending set and in a CFG state,
the [label cfg
term] pairs are added to the pending set and
the pairs of the pending set are then non-deterministically
ordered into a list. All but the
last label of the pairs
are bound to the cfg
term of the following pair and
the label of the last
pair is bound to the body cfg
term. Each such binding of a label is visible in
the cfg term of the
label's pair and
shadows lexically earlier bindings of
the label.
The cfg term of the first
pair is then tail-called within an empty pending set and
with the CFG state and the resulting CFG state is returned.
(permute/tail ([label cfg term] …)
body cfg term)When a permute/tail CFG term is called within a
pending set and in a CFG state,
the [label cfg
term] pairs are added to the pending set.
The body cfg term
is then tail-called within the extended pending set and
with the CFG state and the resulting CFG state is returned.
If a cfg expression is in tail context,
the result expression is in
tail context as well.
The following entries describe CFG terms that can be converted into primitive CFG terms.
Although let and let-values are derived
CFG terms, their identifiers are already bound as Scheme
keywords. An implementation must therefore recognize these
bindings directly instead of defining them through
define-cfg-syntax.
(return
[variable expression]
...)Effectively equivalent to
(return-values
[(variable)
expression] ...).
(let-values
([formals expression]
...) cfg term)It is a syntax violation if a let-values term may
potentially be called within a non-empty pending set.
The let-values CFG term
defines a CFG variable on forward flow for
each variable in the
formals.
When the let-values CFG term is called with a CFG
state, the environment of the surrounding cfg
expression is extended by the visible CFG-variable
bindings.
The expressions are
then evaluated in an unspecified order in this extended
environment to yield values. The
CFG state is then extended by binding the CFG variables
associated with
the formals to the
corresponding values, and the cfg term is then
tail-called with the extended CFG state. The new bindings
remain in the CFG state until the called CFG term returns, at
which point they are removed, and the resulting CFG state is
returned.
It is a syntax violation if
the variables over
all formals are not
pairwise different.
(let
([variable expression]
...) cfg term)(let label
([variable expression]
...) cfg term)The first form is effectively equivalent to
(let-values
([(variable)
expression] ...)
cfg term).
The second form is effectively equivalent to
(letrec
([label
cfg term])
(let
([variable
expression] ...)
(go label))).
(finally-values
([formals expression]
...) cfg term)It is a syntax violation if a
finally-values term may
potentially be called within a non-empty pending set.
The finally-values CFG
term defines a CFG variable on backward flow for each
variable in the
formals.
When the finally-values CFG term is called with
a CFG state, the cfg term
is called within an empty pending set and with that CFG
state. This call is not in tail context. When the CFG term
returns, the environment of the surrounding cfg
expression is extended by the CFG-variable bindings visible
in the returned CFG state.
The expressions are then
evaluated in an unspecified order in this extended
environment to yield values. The returned CFG state is
extended by binding the CFG variables associated with the
formals to the
corresponding values, and the extended CFG state is
returned. The new bindings are not visible in any of the
expressions.
It is a syntax violation if the
variables over all
formals are not pairwise
different.
(finally
([variable expression]
...) cfg term)Effectively equivalent to
(finally-values
([(variable)
expression] ...)
cfg term).
The Scheme syntax described in this section
are definitions, which may
appear anywhere other definitions may appear.
Keyword bindings established by these definitions are visible
throughout the body in which they appear, except where shadowed
by other bindings, and nowhere else, just like variable bindings
established by define. All bindings established by
a set of definitions are visible within the definitions
themselves.
(cfg keyword datum …)(cfg keyword datum … . datum)cfg keyword
Before executing a cfg
expression, these CFG macro uses are expanded by
the syntax expander into core CFG terms just as Scheme macro
uses are expanded into core forms. In particular,
a CFG transformer is like a Scheme transformer.
(define-cfg-syntax cfg keyword transformer expression)Binds cfg keyword to
the value transformer
expression, which must evaluate, at
macro-expansion time, to a CFG transformer.
(define-cfg-label free label)Binds the free label to a fresh label.
Whenever
(free label) appears
as a label, it is
expanded into the fresh label to which it is bound before the
containing cfg expression is executed.
The following example defines a CFG keyword that can be used
like let to unconditionally bind CFG variables:
(define-cfg-syntax simple-let
(lambda (stx)
(syntax-case stx ()
[(_ ([id init] ...) cfg)
(for-all identifier? #'(id ...))
#'(branch ([(e id ...) cfg])
(e init ...))])))
(cfg (simple-let ([x 1] [y 2])
(return [res (+ x y)]))
res)3
A probably more useful CFG macro is the following one:
(define-cfg-syntax return-variables
(lambda (stx)
(syntax-case stx ()
[(_ return-var ...)
(for-all identifier? #'(return-var ...))
#'(return [return-var return-var] ...)])))
(cfg (simple-let ([x 1]) (return-variables x))
x)1
The label definition feature is demonstrated in the following example:
(define-cfg-label p)
(define-syntax permuting
(lambda (stx)
(syntax-case stx ()
[(_ cfg-term ... result-expr)
#'(cfg (permute ([(p) cfg-term] ...)
(return [res result-expr]))
res)])))
(permuting (simple-let ([x 99]) (go (p))) x)99
The sample implementation is a portable R6RS implementation written without knowledge of Olin Shiver's original code.
The sample implementation in the git repository is configured for Chez Scheme.
Git repository for the sample implementation.
This SRFI would not exist if there hadn't been Olin Shiver's paper The Anatomy of a Loop. In fact, almost all of the mental effort needed for this SRFI was already provided by him. This does not imply that he does or does not endorse this SRFI.
It was Jens Axel Søgaard who reminded me of Olin Shiver's paper, which I had once read but then forgotten about.
During the draft period, Wolfgang Corcoran-Mathe read the specification thoroughly and found a number of small bugs and inconsistencies, which could then be fixed.
This SRFI is a direct descendant of SRFI 242, by the same author.
© 2025 Marc Nieper-Wißkirchen.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.