by Marc Nieper-Wißkirchen
This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-247@nospamsrfi.schemers.org
. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.
define-syntactic-monad
.)This SRFI extends Scheme with a simple mechanism to implicitly add formal arguments to procedure definitions and to implicitly add arguments to procedure calls. Contrary to parameters (also known as fluids or dynamically bound variables), which can be used for the same purpose, no runtime overhead is generated.
Thanks to its proper tail calls, Scheme is an excellent programming language for describing state machines. In a finite state machine, each state is modelled by a procedure and each state transition by a tail call to one of these procedures. In more general state machines, states are parameterized by values of a list of state variables. Each procedure accepts the current values of the state variables as arguments and each tail call is done with possibly updated values of the state variables.
Consider the following example of an interpreter for a simple programming language dealing with three stacks:
(define run (lambda (prog a b c) (define a->b (lambda (prog a b c) (run prog (cdr a) (cons (car a) b) c))) (define a->c (lambda (prog a b c) (run prog (cdr a) b (cons (car a) c)))) (define b->a (lambda (prog a b c) (run prog (cons (car b) a) (cdr b) c))) (define b->c (lambda (prog a b c) (run prog a (cdr b) (cons (car b) c)))) (define c->a (lambda (prog a b c) (run prog (cons (car c) a) b (cdr c)))) (define c->b (lambda (prog a b c) (run prog a (cons (car c) b) (cdr c)))) (if (null? prog) (values a b c) (let ([ins (car prog)] [prog (cdr prog)]) (case ins [(a->b) (a->b prog a b c)] [(a->c) (a->c prog a b c)] [(b->a) (b->a prog a b c)] [(b->c) (b->c prog a b c)] [(c->a) (c->a prog a b c)] [(c->b) (c->b prog a b c)])))))
In this example, the state variables
are prog
, a
, b
,
and c
, which are threaded through the
code. While the semantics of the code are very clear,
syntactically it exhibits two problems: Firstly, it doesn't
scale when we extend the interpreter with more registers, that
is state variables because we have to change every procedure
definition and every procedure call. Secondly, at each
transition step only a subset of the state variables are
updated, yet we have to list all state variables at each procedure call.
Using the mechanism provided by this SRFI, we can rewrite the
interpreter with the following code, which does not exhibit the
two problems. At runtime, the code behaves exactly as the
previous code. By convention, the names for syntactic monads
begin with the character $
. (Locally defined
syntactic monads are often just named $
.)
(define-syntactic-monad $ prog a b c) (define run ($ lambda () ($ define (a->b) ($ run ([a (cdr a)] [b (cons (car a) b)]))) ($ define (a->c) ($ run ([a (cdr a)] [c (cons (car a) c)]))) ($ define (b->a) ($ run ([a (cons (car b) a)] [b (cdr b)]))) ($ define (b->c) ($ run ([b (cdr b)] [c (cons (car b) c)]))) ($ define (c->a) ($ run ([a (cons (car c) a)] [c (cdr c)]))) ($ define (c->b) ($ run ([b (cons (car c) b)] [c (cdr c)]))) (if (null? prog) (values a b c) (let ([ins (car prog)] [prog (cdr prog)]) (case ins [(a->b) ($ a->b)] [(a->c) ($ a->c)] [(b->a) ($ b->a)] [(b->c) ($ b->c)] [(c->a) ($ c->a)] [(c->b) ($ c->b)])))))
Iterative and recursive loops are a particular case of state
machines, which can also benefit from defining a syntactic monad.
As examples, we give an implementation of the partition
procedure found in SRFI 1 and R^{6}RS and of the factor
procedure found in Kent Dybvig's The Scheme Programming Language.
(define partition (lambda (pred ls) (define-syntactic-monad $ in out) (let f ([ls ls]) (if (null? ls) ($ values ([in '()] [out '()])) ($ let*-values ([() (f (cdr ls))]) (let ([x (car ls)]) (if (pred x) ($ values ([in (cons x in)])) ($ values ([out (cons x out)]))))))))) (partition symbol? '(one 2 3 four five 6)) ; => (one four five) (2 3 6)
(define factor (lambda (n) (define-syntactic-monad $ n i) ($ let f ([i 2]) (cond [(>= i n) (list n)] [(integer? (/ n i)) (cons i ($ f [(n (/ n i))]))] [else ($ f [(i (+ i 1))])])))) (factor 3628800) ; => (2 2 2 2 2 2 2 2 3 3 3 3 5 5 7)
The following definition is exported by the (srfi
:247)
and (srfi :247 syntactic-monads)
libraries.
(define-syntactic-monad syntactic
monad name
formal …)
The define-syntactic-monad
form defines a
syntactic monad.
A define-syntactic-monad
form is a definition and
can appear anywhere any
other definition
can
appear.
Syntactic monad name
and
the formals
must all be
identifiers.
Syntactic monad name
is
bound as a syntactic keyword.
The formals
, taken as
symbols, become the state variable names of the
syntactic monad defined. At use sites
of syntactic monad name
,
each state variable name defines a corresponding state
variable, which is an implicit identifier with the state
variable name as its symbolic name and which contains the same
contextual information as the
keyword syntactic monad
name
in the macro use. An identifier is
the same as a state variable if binding the
identifier would shadow free references to the state variable.
The list of state variables (in the order of the state variable
names) at use sites of syntactic monad
name
is denoted by state
variable …
.
Example:
(define-syntactic-monad $ a b)
The keyword syntactic monad
name
defined by the define-syntactic-monad
definition can be used in
the following ways (every other use is a syntax violation):
(syntactic monad
name lambda formals
body)
is equivalent
to (lambda
(state
variable …
. formals) body)
.
Example:
(($ lambda (c) (list a b c)) 1 2 3) ; => (1 2 3)
(syntactic monad name define
(name
. formals) body)
is equivalent to (define name
(syntactic monad
name lambda formals body)
.
Example:
($ define (f c d) (list a b c d)) (f 1 2 3 4) ; => (1 2 3 4)
(syntactic monad name
case-lambda
[formals body] …)
is equivalent to (case-lambda [(state
variable …
. formals) body] …)
Example:
(($ case-lambda [() (list a b)]) 1 2) ; => (1 2)
(syntactic monad name let*-values
([formals init] …) body)
is equivalent to (let*-values ([(state
variable …
. formals) init] …) body)
Example:
($ let*-values ([(c) (values 1 2 3)] [() (values a (+ b c))]) (list a b)) ; => (1 5)
(syntactic monad
name procedure expression
(binding
…) argument
expression …)
is equivalent to a procedure call of the
form (procedure expression
state variable
expression … argument
expression
…)
. Here,
each binding
is of the
form [variable expression]
where each variable
must
be the same as one of the state variables. It is also a syntax
violation if one of the variables
appears more than once amongst
the variables
.
The state variable
expressions
are a list of expressions
corresponding to the state variables. For
each variable
, which is
a state variable, the
corresponding state variable
expression
is
the expression
corresponding to
the variable
. For the
state variables that do not appear amongst
the variables
, the
corresponding state variable
expression
is a variable reference to the same
state variable.
Example:
(let ([a 1]) ($ list ([b 2]) 4)) ; => (1 2 4)
(syntactic monad
name procedure expression)
is equivalent to
(syntactic monad
name procedure expression
())
.
Example:
(let ([a 1] [b 6]) ($ list)) ; => (1 6)
(syntactic monad name
let loop variable
([variable init] …) body)
is equivalent to
(let loop variable ([state variable state variable init]
… [other variable other variable init] …)
body)
. Here, for
each state variable
appearing among
the variables
, the
corresponding state variable
init
is the
corresponding init
. For each state
variable
not appearing among
the variables
, the
corresponding state variable
init
is a variable reference to the same state
variable. The other
variables
are
the variables
that are
not state variables in that order.
The other inits
are the
corresponding inits
.
Example:
(let ([a 1]) ($ let loop ([c 3] [b 2]) (if (= a 2) (list a b c) (loop 2 (+ b 6) (+ c 7))))) ; => (2 8 10)
Note: In (define-syntactic-monad syntactic-monad-name formal …)
,
only the names of
the formals
are
significant.
The sample implementation is written in portable
R^{6}RS scheme. It can easily be ported to other Scheme
systems supporting the syntax-case
system.
This SRFI was inspired from and would not exist without the
prior appearance of a form
of define-syntactic-monad
in the source code of
Chez Scheme.
© 2023 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.