Update (March 29, 2021)

The design was simplified by changing handle to more closely match call-with-prompt. This eliminated some unnecessary (and probably confusing) explanatory text. I also added a footnote explaining the “lazy” design of the effectful DSL of part 3.

Introduction

This is an exploration of an extensible effects system implemented in Guile Scheme. It is based on a post by Oleg Kiselyov called Having an Effect¹. Most of the ideas described below are Oleg’s; the few original ones arose in the process of translating the original Haskell code to Guile Scheme. Like any translation, it presented many interesting problems, and the goal was to design a system which played to strengths of Scheme rather than try to reproduce Haskell idioms. The idea of a “reified abort” described in part 2, for example, was helpful in relating concepts to the Guile ecosystem.

This file is hosted on sourcehut as a literate code file and blog post, released into the public domain.

Part 1: Simulating Effects

The starting point for this implementation is the delimited control operators call-with-prompt and abort-to-prompt:

 -- Scheme Procedure: call-with-prompt tag thunk handler
     Set up a prompt, and call THUNK within that prompt.

     During the dynamic extent of the call to THUNK, a prompt named TAG
     will be present in the dynamic context, such that if a user calls
     ‘abort-to-prompt’ (see below) with that tag, control rewinds back
     to the prompt, and the HANDLER is run.

     HANDLER must be a procedure.  The first argument to HANDLER will be
     the state of the computation begun when THUNK was called, and
     ending with the call to ‘abort-to-prompt’.  The remaining arguments
     to HANDLER are those passed to ‘abort-to-prompt’.

 -- Scheme Procedure: abort-to-prompt tag val1 val2 ...
     Unwind the dynamic and control context to the nearest prompt named
     TAG, also passing the given values.

Consider the following library, which uses these operators to simulate a global state:

(use-modules (ice-9 match))

(define state-prompt-tag (make-prompt-tag 'state))

(define (get-state)
  (abort-to-prompt state-prompt-tag 'get))

(define (put-state st)
  (abort-to-prompt state-prompt-tag 'put st))

(define (handle-state st thunk)
  (call-with-prompt state-prompt-tag
    thunk
    (lambda (cont . sig)
      (match sig
        (('get)
         (handle-state st (lambda () (cont st))))
        (('put st)
         (handle-state st (lambda () (cont st))))))))

We can use this library to perform stateful computations without any actual mutation:

(define (fresh)
  (let ((n (get-state)))
    (put-state (1+ n))
    n))

(define (label x)
  (cons x (fresh)))

(handle-state 0 (lambda () (map label '(a b c d e))))

; => ((a . 0) (b . 1) (c . 2) (d . 3) (e . 4))

The interface above is structured around two effects, which submit requests to read or write the state, and a handler, which receives these requests and delegates access to it. It relies on a well-known transformation from monadic style, in which the state is threaded through the program as an additional argument, to direct style using delimited control operators².

Of course, the same effect could be achieved using Guile’s support for fluids and dynamic state. Below, we describe a small system for extending Scheme with arbitrary effects without explicit use of continuations or other language-specific features. We then see how far we can push it, and achieve some results which may be surprising.

Part 2: Reifying Control

In the state example described in part 1, invoking an effectful function like get-state or put-state immediately aborts the current continuation. When this happens, control is transferred to a handler like handle-state, and the effect is “run” by plugging the continuation with a value from the context. As we saw, this process of “trampolining” between a running computation and its context is driven by the control operators abort-to-prompt and call-with-prompt. In part 2, we describe an alternate way of simulating effects which reifies this control pattern onto a data structure.

First, we define a record type which encapsulates the data communicated to the handler of call-with-prompt:

The first argument to HANDLER will be the state of the computation begun when THUNK was called, and ending with the call to ‘abort-to-prompt’. The remaining arguments to HANDLER are those passed to ‘abort-to-prompt’

This data structure thus represents a computation in progress: a continuation representing the “rest of the computation”, and a signature describing what needs to be done to continue.

(use-modules (srfi srfi-9))

(define-record-type <request>
  (%make-request cont sig)
  %request?
  (cont %request-continuation)
  (sig %request-signature))

Manually destructuring it violates the protocol we establish next, so consider these functions private.

Because we are embedding a new domain of values (effects) into Scheme, we need a way to distinguish these from “pure” values. A pure request has no continuation; its signature is a value which can move freely between the two domains using pure and lower.

(define (pure? req)
  (not (%request-continuation req)))

(define (pure x)
  (%make-request #f x))

(define (lower req)
  (if (%request-continuation req)
      (error "Attempt to lower an impure request")
      (%request-signature req)))

A request with a continuation is “impure”; its signature is a message whose meaning is determined by a handler, and its continuation will be used by that handler to control the computation.

Next, we establish the protocol for effects and handlers to communicate with each other via requests. Request, analogous to abort-to-prompt, sends a new effect request along a tagged channel.

(define (request tag . sig)
  (%make-request pure (cons tag sig)))

Handle, analogous to call-with-prompt, receives effect requests on a channel and attempts to handle them; effects communicated on other channels are ignored. The handler argument is just like in call-with-prompt: it receives the continuation and a signature describing the effect.

(define (handle tag req handler)
  (let loop ((req req))
    (if (pure? req)
        ;; already handled; return pure request
        req
        (let ((cont (%request-continuation req))
              (sig (%request-signature req)))
          (if (eq? tag (car sig))
              (apply handler cont (cdr sig))
              ;; not our effect to handle; wait for the next one
              (%make-request (compose loop cont) sig))))))

This establishes the interface for introducing and eliminating effect requests. Lastly, we define an interface for extending existing requests. A request is extended by composing it with a continuation; this continuation “waits” for the request to be handled, then constructs a second request from the value returned by the handler.

(define (extend req cont)
  (let loop ((req req))
    (if (pure? req)
        ;; effects handled; hand off control
        (cont (%request-signature req))
        ;; unhandled effects; wait for them to be handled
        (%make-request (compose loop (%request-continuation req))
                       (%request-signature req)))))

Those familiar with monads may recognize extend as monadic bind. One way to describe what is meant by extensible effects is to say that we only need to implement one monad. The request serves as a kind of “meta effect”; all other effects are defined in terms of it.

This completes the infrastructure necessary for writing effects and handlers. Part 3 constructs, piece by piece, an embedded language of effects. By the end, we hope that the reader will be left with a sense for how it all works and why it may be useful.

Part 3: Effectful DSL

Boolean logic

To demonstrate how effects communicate with handlers via requests, we start with a toy DSL which models boolean logic. This DSL will then be used to test later additions to the languages as we go.

Although boolean logic isn’t typically considered an effect, treating it as one is a useful exercise. Besides, we might find other benefits to relaxing our view on what constitutes an effect.

(define bool-tag '(bool))

Our boolean language has four primitive operations: the values true and false, logical negation and logical conjunction. True and false simply send requests for operations of the same name:

(define (true) (request bool-tag 'true))
(define (false) (request bool-tag 'false))

The negation function neg performs a similar request, except that it is parameterized by an input request; the conjunction function conj is parameterized by two input requests:

(define (neg bool)
  (extend bool
    (lambda (p)
      (request bool-tag 'neg p))))

(define (conj bool1 bool2)
  (extend bool1
    (lambda (p)
      (extend bool2
        (lambda (q)
          (request bool-tag 'conj p q))))))

Using extend, we bind on the value returned by a request’s handler before that handler is run, then continue the computation as if it were already handled. This is the essence of the embedding.

Taking a look at how Guile displays requests such as the one returned by true can be instructive:³

(true)

; => #<<request> cont: #<procedure pure (x)> sig: ((bool) true)>

The basic handler simply uses the Scheme embedding to provide the calculation with boolean logic. Like handle-state from part 1, bool-logic is recursive, handling further requests raised by the continuation.

(define (bool-logic req)
  (handle bool-tag
    req
    (lambda (cont . sig)
      (bool-logic
       (cont
        (match sig
          (('true) #t)
          (('false) #f)
          (('neg p) (not p))
          (('conj p q) (and p q))))))))

Another handler might represent this logic as a string, instead.

(define (bool-show req)
  (handle bool-tag
    req
    (lambda (cont . sig)
      (bool-show
       (cont
        (match sig
          (('true) "true")
          (('false) "false")
          (('neg p) (string-append "(not " p ")"))
          (('conj p q) (string-append "(and " p " " q ")"))))))))

We can use the earlier effects to derive new ones for logical disjunction and implication:

(define (impl bool1 bool2)
  (neg (conj bool1 (neg bool2))))

(define (disj bool1 bool2)
  (impl (neg bool1) bool2))

Now we can define some terms in this language, and interpret them in either of our handlers.

(define (btest b)
  (format #f "~a evaluates to ~a"
    (lower (bool-show b))
    (lower (bool-logic b))))

(btest (neg (true)))

; => (not true) evaluates to #f

(btest (disj (false) (neg (false))))

; => (not (and (not false) (not (not false)))) evaluates to #t

At any point in the program, we can inject Scheme booleans using pure.

(lower (bool-logic (impl (neg (pure #f)) (false))))

; => #f

(lower (bool-show (conj (true) (pure "true"))))

; => (and true true)

Errors

The first “proper” effect we’ll implement simulates raising an error. A program which encounters an error has to abort the current continuation and proceed from an earlier point.

(define error-tag '(error))

(define (fail)
  (request error-tag))

The maybe handler marks the point at which a computation should return on encountering an exception and provides an alternative, encoded lazily as a thunk:

(define (maybe thunk req)
  (handle error-tag
    req
    (lambda (_) (thunk))))

The derived effect satisfy returns the value returned by a request if it satisfies a predicate and fails otherwise:

(define (satisfy test req)
  (extend req
    (lambda (x)
      (if (test x) (pure x) (fail)))))

With errors implemented, we can write “safe” versions of the boolean operations defined earlier:

(define (safe-neg bool)
  (neg (satisfy boolean? bool)))

(define (safe-conj bool1 bool2)
  (conj (satisfy boolean? bool1) (satisfy boolean? bool2)))

(define (safe-disj bool1 bool2)
  (disj (satisfy boolean? bool1) (satisfy boolean? bool2)))

(define (safe-impl bool1 bool2)
  (impl (satisfy boolean? bool1) (satisfy boolean? bool2)))

A test shows how our system automatically propagates errors through the computation:

(lower
 (maybe (lambda () (pure "error"))
   (bool-logic
    (safe-impl
     (safe-neg (pure 'oops))
     (safe-neg (true))))))

; => error

Dynamic state

Now we briefly return to the state example of part 1, this time implemented in terms of requests. The syntax is almost exactly the same, with two exceptions. Put now has to be aware of effects, and state now has to decide what to do when it returns. Usually, we want to do something with the final state, so we package it up with the return value as a pair.

(define state-tag '(state))

(define (get)
  (request state-tag 'get))

(define (put req)
  (extend req
    (lambda (st)
      (request state-tag 'put st))))

(define (state st req)
  (if (pure? req)
      (pure (cons st (lower req)))
      (handle state-tag
        req
        (lambda (cont . sig)
          (match sig
            (('get) (state st (cont st)))
            (('put st) (state st (cont st))))))))

At this point we can write and interpret pretty convoluted computations without worrying about how they compose:

(lower
 (maybe (lambda () (pure "error"))
   (state #f
     (bool-logic
      (conj (put (neg (get)))
            (satisfy identity
                     (disj (get)
                           (false))))))))

; => '(#t . #t)

Higher-order Effects

Now that we’ve built a language capable of running computations involving complex interactions of effects, it may be a good idea to step back. We’ve already shown that the system is extensible in one sense: introducing new effects and handlers does not require rewriting earlier ones. On the other hand, we’ve lost some of the abstraction available in scheme.

For example, our example demonstrating the state implementation in part 1 can no longer be written in this language. Our language is first-order—although we have access to variables and functions by embedding it in Scheme, the effects system itself lacks these powerful means of abstraction. The question is, can we implement higher-order effects?

Surprisingly, we can. Oleg Kiselyov demonstrates how in the Having an Effect post mentioned above. We translate it to Scheme below. Anyone who has implemented Lisp in Lisp will probably recognize the basic form, except that functions and variables are modeled as effects.

(define higher-order-tag '(higher-order))

(define (variable sym)
  (request higher-order-tag 'var sym))

(define (function sym body)
  (request higher-order-tag 'fun sym body))

(define (higher-order req)
  (let loop ((env '()) (req req))
    (handle higher-order-tag
      req
      (lambda (cont . sig)
        (loop env
              (match sig
                (('var sym)
                 (match (assq sym env)
                   (#f (fail))
                   ((_ . x) (cont x))))
                (('fun sym body)
                 (cont (lambda (x)
                         (loop (cons (cons sym x) env)
                               body))))))))))

Now all we need is an effectful application function:

(define (ap fun val)
  (extend (satisfy procedure? fun)
    (lambda (f)
      (extend val f))))

And we can talk about higher-order effects and an effectful lambda calculus! Here is an identity function:

(define (id) (function 'x (variable 'x)))

(lower (higher-order (ap (id) (pure 0))))

; => 0

And here is a higher-order function which negates the value returned by its input function (like Guile’s invert):

(define (inv)
  (function 'f
    (function 'p
      (ap (variable 'f)
          (neg (variable 'p))))))

Applying inv to id yields neg again:

(define (neg*) (ap (inv) (id)))

(btest (higher-order (ap (neg*) (false))))

; => (not false) evaluates to #t

And Beyond?

There’s a lot more we could do with the language described in part 3; nondeterminism, streams and logic programming are interesting to implement, for example. As well, we could remove a lot of the monadic boilerplate with some nice syntax and relegate extend to an internal interface. A good exercise is to write an effectful let form (hint: there are at least two different ways of doing so, one which uses syntax-rules and one which doesn’t). Finally, the system we implemented has a serious efficiency problem related to how we represented continuations; the solution is not hard, and rather interesting in its own right⁴.

We’ll leave it here for now, however. Hopefully the system has demonstrated its flexibility: we were able to write complex programs involving side-effects in a fully modular way. Extending it is as simple as writing new effects with request, and writing interpreters for them using handle. Supporting higher-order effects also provides a means of abstracting effects, analogous to that provided by lambda.