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 names of the keywords halt
and finally are still open to bikeshedding. For
example, defer may be a better choice
than finally.
The do CFG keyword is in accordance with
Olin Shiver's The Anatomy of a Loop. The syntax of
the do CFG macro differs from the syntax of
the do Scheme keyword. This makes automatic
indentation by editors complicated (but may usually be
distinguishable because the CFG keyword do
usually appears in the form (do (lambda ...)
...), which is not the case for
Scheme's do. Does this warrant renaming the CFG
keyword?
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, call
and execute of SRFI 242 have been renamed
to let*, letrec, go
and do, respectively, in accordance with The
Anatomy of a Loop. Similarly, bind of SRFI
242 has been renamed to indep.
The permute syntax of SRFI 242 has been split
into permute and permute/tail, which have the semantics as described in
The Anatomy of a Loop. In
particular, permute/tail permutation sequences
now carry forward across jumps to all labels.
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 semantics of the CFG language is explained differently.
Static and dynamic labels are no longer distinguished.
The SRFI is now implementable in pure R6RS as well as 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
(letrec [(f (do (lambda (next done)
(if (null? n*)
(done)
(next (car n*) (cdr n*))))
[(n n*)
(do (lambda (even odd)
(if (odd? n)
(odd (+ o 1))
(even (+ e 1))))
[(e) (go f)]
[(o) (go f)])]
[()
(finally (e o) (values e o) (halt))]))]
(do (lambda (start) (start n* 0 0)) [(n* e o) (go f)]))
(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
(letrec [(f (do (lambda (next done)
(if (null? n*)
(done)
(next (car n*) (cdr n*))))
[(n n*)
(do (lambda (even odd)
(if (odd? n)
(odd)
(even)))
[()
(finally (e*) (cons n e*) (go f))]
[()
(finally (o*) (cons n o*) (go f))])]
[()
(finally (e* o*) (values '() '()) (halt))]))]
(do (lambda (start) (start n*)) [(n*) (go f)]))
(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 loop variables, until
a halt CFG term is reached. Then, control flows
backwards along the edges previously taken, potentially binding
so-called return variables. 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 a halt
CFG term, whose syntax simply is:
(halt)
For example, we have
(cfg (halt) (+ 1 2))3
as the control flow along this CFG, which has no edges, immediately stops, leading on to the evaluation of the return expression.
A finally CFG term is used to bind return
variables. The general syntax of a finally block
is:
(finally formals expression cfg
term)
When control enters the finally it describes,
control is passed to the cfg
term first. When control finally flows backwards,
the (Scheme) expression is
evaluated to yield values that are bound as return variables to
the formals. For example,
we have:
(cfg
(finally (x . y) (values 1 2 3)
(halt))
(list x y)(1 (2 3))
A more complicated example is the following:
(let ([x 1])
(cfg
(finally (y) (+ x 2)
(finally (x) (+ x 1)
(halt)))
(list x y)))(2 4)
Here, control flows first from top to bottom and then
backwards. The finally CFG terms bind the return
variables during the backward flow. The expression (+ x
1) sees no binding of a return variable, only the outer
binding of x. On the other hand, the
expression (+ x 2) sees the binding
of x as a return variable by the
inner finally CFG term.
While finally CFG terms are used to perform
actions during the backward control flow, do
CFG terms perform actions during the initial forward flow
through the CFG. The syntax of a do CFG term is given by
(do procedure expression [formals cfg term] …)
where procedure
expression is a Scheme expression that must
evaluate to a procedure accepting as many arguments as there
are cfg terms in
the do CFG term. When the forward control flow
through the CFG reaches a do CFG term, this
procedure is called and should tail-call one of its arguments.
Control flow then proceeds with the
corresponding cfg
term:
(let ([x 1] [y 2])
(cfg
(finally (y) (+ x 3)
(do (lambda (e)
(set! x y)
(e))
[() (halt)]))
(list x y)))(2 5)
In this example, the forward control flow passes through
the finally CFG term before it reaches
the do block. The procedure 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 halt CFG term, from where it flows
backward. The backward control flow passes through
the do CFG term before the (+ x
3) is evaluated and the return variable y is
bound to the result 5.
Do 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
(do (lambda (e1 e2)
(if (odd? y) (e1) (e2)))
[() (halt)]
[() (finally (x) 3 (halt))])
(+ x 10)11
Here, the control flow exiting the do 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
binding as a return variable introduced in
the finally CFG term. To understand this, we have
to introduce the rule by with which the scope of return
variables is determined. A CFG term (and, likewise,
the result expression) are
in the scope of a return variable if and only if this CFG term
post-dominates definitions of this return variable, that is if
all possible control flow paths starting at the CFG term and
ending at a halt CFG term pass through a
definition of the return variable, which happens along the entry
edge of a finally CFG term. In the example above,
this is not the case. There is a (statically possible)
control-flow path from the entry block to the
first halt CFG term that does not pass through
a finally CFG term defining the return
variable x. Compare with the following two
examples:
(let ([x 1] [y 2])
(cfg
(do (lambda (e1 e2)
(if (odd? y) (e1) (e2)))
[() (finally (x) #f (halt))]
[() (finally (x) 3 (halt))])
(+ x 10)13
(let ([x 1] [y 2])
(cfg
(finally (x) 3
(do (lambda (e1 e2)
(if (odd? y) (e1) (e2)))
[() (halt))]
[() (halt))]))
(+ x 10)13
So far, we haven't talked about
the formals that appear in
a do CFG term. Using these, we can bind a
different kind of variables, namely so-called loop variables.
One can think of loop variables as being defined during forward
control flow and return variables as being defined during
backward flow. The value to which a loop variable is bound
when control flow leaves along an edge of
a do CFG term is passed as an argument to
the tail-called procedure that corresponds to the edge:
(let ([x 1])
(cfg
(do (lambda (e)
(e (+ x 2)))
[(x) (finally (y) (+ x 3) (halt))])
y)6
In (+ x 2), the variable x
is let-bound to 1, and in (+ x
3) the binding as a loop variable to (+ 1 2)
is visible.
While the scoping rule of return variables is based on the
post-dominance relation, the scoping rule for loop variables is
based on the dominance relation: A CFG term is in the scope of
a loop variable if definitions of this loop 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 loop variable, which
happens along an edge exiting a do CFG term.
In the following example, the definitions of
the loop variable x do not dominate the expression (+ x 3):
(let ([x 1] [y 2])
(cfg
(do (lambda (e1 e2)
(if (odd? y) (e1 5) (e2)))
[(x) (finally (y) (+ x 2) (halt))]
[() (finally (y) (+ x 3) (halt))])
y))4
The expressions in the finally CFG terms are
evaluated with loop and return variables in scope. If a loop
and a return variable have the same name and both are in scope,
the return variable shadows the loop variable. In the following
example, x is bound to 1 in (+ x
1), bound to 2 in (+ x 3),
bound to 5 in (+ x 2) and bound
to 7 in (+ x 4):
(let ([x 1])
(cfg
(do (lambda (e)
(e (+ x 1)))
[(x) (finally (x) (+ x 2)
(finally (x) (+ x 3)
(halt)))])
(+ x 4)11
Another CFG term that can be used to define loop variables is
indep. Its syntax is:
(indep
([formals expression]
...) cfg term)
When the forward control flow reaches a indep CFG
term, the expressions are
evaluated in the same environment in which
the procedure expression
of an do CFG term would be evaluated. Then,
all formals are bound in parallel, and the loop variable bindings
become visible in the cfg
term, with which the forward control flow
proceeds. The indep CFG term is similar to
the let-values Scheme expression, which binds
multiple Scheme variables in parallel.
(let ([x 1] [y 2])
(cfg
(indep ([(x) y]
[(y) x])
(finally (x y) (values x y) (halt)))
(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 (finally (x) x (halt))])
(go x))
x))1
In the following example (adapted from Olin Shiver's paper),
the finally CFG term is dominated by definitions of
the loop variable y. When the control flows through
the label la, the loop variable y is
bound before going to la; otherwise, when the control
flows through the label lb, the loop
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 (finally y (+ y 10) (halt))]
[la (do (lambda (e1)
(f y) (e1))
[() (go lj)])]
[lb (do (lambda (e1)
(g x) (e1 (* x x)))
[(y) (go lj)])])
(do (lambda (e1 e2)
(if (odd? x)
(e1 (+ x 1))
(e2)))
[(y) (go la)]
[() (go lb)]))
(list x y)))(2 12)
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 (finally (x) 42 (halt))]
[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 (indep ([(x) 10])
(go p))]
[p (indep ([(y) 20])
(go p))])
(finally (z) (list x y) (halt)))
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 indep CFG terms is not
determined, i.e. whether the forward control flow first passes
through the lexically first indep 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 loop and return variables. The
definition of x by the first indep CFG
term does not dominate the second indep 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 (indep ([(x) 2])
(go p))]
[p (indep ([(y) x])
(go p))])
(finally (z) (list x y) (halt)))
z))(2 1)
(let ([x 1])
(cfg
(permute ([p (finally ([y] x)
(go p))]
[p (finally ([x] 2)
(go p))])
(halt))
(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 (indep ([(x) 2])
(go p))])
(letrec ()
(let* ([p (permute ([p (indep ([(z) (list x y)])
(go p))])
(finally (x y z) (values x y z) (halt)))])
(permute/tail ([p (indep ([(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)
#'(indep ([(n) n-expr])
(letrec ([lp-lbl
(do (lambda (loop done)
(if (zero? n)
(done)
(loop (- n 1))))
[(n) loop-cfg-term]
[() body-cfg-term])])
(go lp-lbl)))])))
(cfg
(indep ([(n) 0])
(loop 10 next
(indep ([(n) (+ n 2)])
(go next))
(finally (n) n (halt))))
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)
#'(indep ([(n) n-expr])
(letrec ([(next)
(do (lambda (loop done)
(if (zero? n)
(done)
(loop (- n 1))))
[(n) loop-cfg-term]
[() body-cfg-term])])
(go (next))))])))
(cfg
(indep ([(n) 0])
(loop 10
(indep ([(n) (+ n 2)])
(go (next)))
(finally (n) n (halt))))
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 loop and return 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.
Loop and return variables are defined in CFG terms and are associated with an identifier. A CFG term occurs in the scope of a loop or return variable if the CFG term will potentially only be called with CFG states in which the loop variable is bound.
The visible loop and return variable bindings of a CFG term in a CFG state is the set of bindings in the CFG state of those loop and return variables that are in the scope of the CFG term and that are not shadowed by later bindings in the CFG state of loop and return variables, respectively, that are also in the scope of the CFG term and are associated with the same identifier.
By abuse of language, extending an environment by the visible loop or return variable bindings in a CFG state means extending the environment by binding the identifiers associated with the visible loop or return variable bindings to fresh locations initially holding the values to which the loop or return 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 return 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 halts and returns
some value(s). (The halt and the other cfg terms are
described in the next subsection.) For example:
(cfg (halt) 'done)done
Using a finally cfg term, return variables can be
bound that can be used in the result
expression:
(let ([x 1])
(cfg (finally (x y) (values (+ x 1) (+ x 2))
(halt))
(list x y)))(2 3)
Loop variables are bound through do terms:
(let ([x 1])
(cfg (do (lambda (e)
(e (+ x 1)))
[(x) (finally (res) x (halt))])
res))2
Do CFG terms can have more than one successor.
During evaluation, one control path is (dynamically) chosen:
(let ([x 1])
(cfg (do (lambda (e1 e2)
(if (even? x) (e1) (e2 'odd)))
[() (finally (res) 'even (halt))]
[(a) (finally (res) a (halt))])
res))odd
Due to loop variable scoping, the second finally
cannot simply be hoisted because it would no longer be
(statically) dominated by the introduction of the loop
variable a:
(let ([a 'outer]
[x 1])
(cfg (finally (res) a
(do (lambda (e1 e2)
(if (even? x) (e1) (e2 'odd)))
[() (finally (res) 'even (halt))]
[(a) (halt)]))
res))outer
And due to return-variable scoping, the
first finally cannot simply be left out because the
entry block would no longer post-dominate an introduction of
the res return variable:
(let ([res 'outer]
[x 1])
(cfg (do (lambda (e1 e2)
(if (even? x) (e1) (e2 'odd)))
[() (halt)]
[(a) (finally (res) a (halt))])
res))outer
Loop variables are called loop variables because the main
reason for the CFG language is that it allows writing loops.
This can be done with letrec CFG terms. Here, we
also use the indep CFG term to bind loop
variables easily:
(cfg (letrec ([f (do (lambda (e1 e2)
(if (> x 6)
(e1)
(e2 (+ x 1) (* a x))))
[() (finally (res) a (halt))]
[(x a) (go f)])])
(indep ([(x) 1]
[(a) 1])
(go f)))
res)720
Finally, permute and permute/tail CFG
terms can be used to create sequences of CFG terms so that loop
variables and return 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
(indep ([(a) x]) (go p)))])
(finally (a) a (halt)))])
(permute/tail [(p (finally (b) y
(indep ([(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.
(do procedure
expression
[formals cfg term]
…)
It is a syntax violation if a do CFG term may
potentially be called within a non-empty pending set.
The do CFG term defines a loop variable for each variable in the formals.
When the do CFG term is called with a CFG
state, the environment of the surrounding cfg
expression is extended by the visible loop variable
bindings. The procedure
expression is then evaluated in this extended
environment to yield a procedure value. This procedure is
then tail-called with as many procedure arguments as there
are cfg terms. The
procedure should call one of the arguments exactly once and
the call should be a tail call. In the continuation of this
tail call, the CFG state is then extended by binding the
loop 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 and the
resulting CFG state is returned.
The do CFG term potentially calls
each cfg term, which
is relevant for the definition of scope.
(halt)It is a syntax violation if a halt CFG term may
potentially be called with a non-empty pending set.
When the (halt) CFG term is called, it returns
an empty CFG state.
(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.
(finally cfg
formals expression cfg
term)
It is a syntax violation if a finally CFG term may
potentially be called within a non-empty pending set.
The finally CFG term defines a return variable
for each variable
in formals.
When the finally CFG term is called with a CFG
state, the environment of the surrounding cfg
expression is extended by the visible loop variable
bindings. Then, the
cfg term is called
with the CFG state to return a CFG state. The extended
environment is then further extended by the visible return
variables in the returned CFG state. Then,
the expression is
evaluated in the doubly extended environment, the returned
CFG state extended by binding the return variables
associated with
the formals to the
values received from evaluating
the expression, and
the extended CFG state is then returned.
(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.
(indep
([formals expression]
...) cfg term)It is a syntax violation if a indep term may
potentially be called within a non-empty pending set.
The indep CFG term
defines a loop variable for
each variable in the
formals.
When the indep CFG term is called with a CFG
state, the environment of the surrounding cfg
expression is extended by the visible loop 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 loop variables
associated with
the formals to the
corresponding values, and the cfg term is then
tail-called with the extended CFG state, and the resulting
CFG state is returned.
It is a syntax violation if
the variables over
all formals are not
pairwise different.
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 indep to unconditionally bind loop variables:
(define-cfg-syntax simple-indep
(lambda (stx)
(syntax-case stx ()
[(_ ([id init] ...) cfg)
(for-all identifier? #'(id ...))
#'(do (lambda (e)
(e init ...))
[(id ...) cfg])])))
(cfg (simple-indep ([x 1] [y 2])
(finally (res) (+ x y) (halt)))
res)3
A probably more useful CFG macro is the following one:
(define-cfg-syntax return
(lambda (stx)
(syntax-case stx ()
[(_ return-var ...)
(for-all identifier? #'(return-var ...))
#'(finally (return-var ...) (values return-var ...) (halt))])))
(cfg (simple-indep ([x 1]) (return 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] ...)
(finally (res) result-expr (halt)))
res)])))
(permuting (simple-indep ([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.