247: Syntactic Monads

by Marc Nieper-Wißkirchen

Status

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.

Received: 2023-10-08
Draft #1 published: 2023-10-12
Draft #2 published: 2023-12-13
Finalized: 2023-12-24
Revised to fix errata:
- 2024-02-11 (Fixed error (wrong meta-variable name) in description of let loops in define-syntactic-monad.)

Abstract

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.

Rationale

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⁶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)

Specification

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.

Implementation

The sample implementation is written in portable R⁶RS scheme. It can easily be ported to other Scheme systems supporting the syntax-case system.

Source for the sample implementation.

Acknowledgements

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.

Copyright

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.

Editor: Arthur A. Gleckler