Implementing Generators: A delimited continuations tutorial

Generators?

Generators are great. They let you write functions that can be paused then continued on the next call. Generators statefully model iterators, like in Python. Generators can also implement cooperative multitasking: each generator represents a process, each process does some work, then pauses, and a scheduler calls each process in rotation. In fact, Andy Wingo, Guile maintainer, wrote about such a system here.

If Guile scheme had a generator expression syntax, it would probably look like this

(define count
  (generator ()
    (let loop ((i start))
      (yield i)
      (loop (1+ i)))))

and work like the following Python:

def count (i=0):
    while True:
        yield i
        i+=1

The function count, if called with no arguments, will return 0 the 0th call, then 1 on the next call, then 2, and so on.

(count)         ;=>0
(count)         ;=>1
(count)         ;=>2
(count)         ;=>3

The function count steps through one iteration of an infinite loop each call.

We need a form of control flow that can leave a block of code and come back to it later. For this purpose, Guile provides the delimited continuation, also called a prompt.

Delimited continuations?

Delimited continuations are a general form of control flow, a common denominator between generators, coroutines, and exceptions.

Delimited continuations let you pause some code, abort back to a previous caller that can catch the abort (like an exception), and give you the option to continue from where you paused later (like a generator).

To demonstrate how delimited continuations work in Guile, lets walk through some examples.

The first step is to define a prompt tag. Guile will use the prompt tag to match an abort with a handler.

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

To pause, we use the function abort-to-prompt, which takes a prompt tag:

(abort-to-prompt example-tag)

pauses the current computation and escapes to a handler, specifically an example-tag handler.

You set up a prompt handler with call-with-prompt which takes

(call-with-prompt
    the-prompt-tag
  the-thunk-to-run
  the-handler-called-if-thunk-aborts)

This will only catch aborts with a matching the-prompt-tag. When calling the handler, Guile passes it a continuation, a function that continues the paused computation if called.

Putting it all together, you get

(call-with-prompt example-tag
  ;; call this thunk
  (lambda ()
    (1+
     (abort-to-prompt example-tag)))    ; pause
  ;; handler (what to do after paused)
  (lambda (continue)                      ; aka continuation
    (continue 3)))

This code sets up an example-tag handler and then calls the first argument, a thunk. The thunk gets ready to add one, but before it can, it aborts to the example-tag handler.

The handler decides to continue, supplying the value 3. The thunk was about to add 1 before pausing, so when supplied 3, it calculates (1+ 3), evaluating to 4.

You can pass additional values to the handler when pausing:

(call-with-prompt example-tag
  (lambda ()
    (1+ (abort-to-prompt example-tag
                         'I 'can 'return 'these)))
  (lambda (_ . rest)
    rest))

This return the list (I can return these). The function 1+ is never called because we ignore the continuation.

Continuations are powerful because they are first-class functions we call, save, or throw away. We can even save the continuation outside of the prompt handler, which we will need to implement generators.

Implementing generators

the key mechanism

First, we need a tag:

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

For convenience, define yield:

(define (yield arg)
  (abort-to-prompt yield-tag arg))

(define next #f)
(call-with-prompt yield-tag
  (lambda ()
    (let loop ((i 0))
      (yield i)
      (loop (1+ i))))
  (lambda (continue return-val)
    ;; capture the continuation for later use
    (set! next continue)
    return-val))

This evaluates to 0 and saves the continuation in next; however, calling (next) will error because it tries to abort without a corresponding prompt handler.

So let’s abstract a function to set up the prompt:

(define (call-with-yield-prompt f)
  (call-with-prompt yield-tag
    f
    (lambda (continue return-val)
      (set! next continue)
      return-val)))

Now we can define a count:

(define count
  (lambda ()
    (let loop ((i 0))
      (yield i)
      (loop (1+ i)))))
(define next count)

(call-with-yield-prompt next)           ;=> 0
(call-with-yield-prompt next)           ;=> 1
(call-with-yield-prompt next)           ;=> 2

That’s the key mechanism we need. This code works like we wanted. It is close to the exact syntax we were after. We are almost done. But there’s problem: this program stores the generator’s state in a global variable. We need to encapsulate that to have more than one generator in use at a time.

But first, one quick generalization: unlike Python, Guile has multiple return values. We should support those. Here’s a variadic yield:

(define (yield . args)
  (apply abort-to-prompt yield-tag args))

and a prompt handler ready for multiple return values:

(define (call-with-yield-prompt f)
  (call-with-prompt yield-tag
    f
    (lambda (continue . return-vals)
      (set! next continue)
      (apply values return-vals))))

Final form

Ultimately we will want a macro to give us our desired generator syntax. But we should use a plain function to do the heavy lifting. It needs to set up a local version of everything we just did:

(define (make-generator ???)
  (define yield-tag (make-prompt-tag 'yield))
  (define (yield . args)
    (apply abort-to-prompt yield-tag args))
  (define next ???)
  (define (call-with-yield-prompt f)
    (call-with-prompt yield-tag
      f
      (lambda (continue . return-vals)
        (set! next continue)
        (apply values return-vals))))
  (lambda args
    ???))

This is the general shape of a function that creates generators. But we need a way for a user to pass in a generator’s definition. Like before, we can build a generator from a function that assumes a yield prompt handler has already been set up. Something along the lines of

(define count
  (make-generator
   (lambda ()
     (let loop ((i 0))
       (yield i)
       (loop (1+ i))))))

But this won’t work. The function make-generator must be able to hand its local yield to the function passed in. This passed function must take a yield parameter. To keep that plumbing separate from the generator’s arguments, we can use a function that takes yield and returns the function we will build the generator from:

(define count
  (make-generator
   (lambda (yield)
     (lambda ()
       (let loop ((i 0))
         (yield i)
         (loop (1+ i)))))))

Let’s change the name of make-generator to make-generator-passing-yield to document this calling convention. Here’s its final implementation:

(define (make-generator-passing-yield generator-defn-fn)
  (define yield-tag (make-prompt-tag 'yield))
  (define (yield . args)
    (apply abort-to-prompt yield-tag args))
  (define next (generator-defn-fn yield))
  (define (call-with-yield-prompt f)
    (call-with-prompt yield-tag
      f
      (lambda (continue . return-vals)
        (set! next continue)
        (apply values return-vals))))
  (lambda args
    (call-with-yield-prompt
     (lambda () (apply next args)))))

Let’s revisit count:

(define count
  (make-generator-passing-yield
   (lambda (yield)
     (lambda ()
       (let loop ((i 0))
         (yield i)
         (loop (1+ i)))))))

This is unwieldy but it works:

(count)                      ;=>0
(count)                      ;=>1
(count)                      ;=>2
(count)                      ;=>3

The make-generator-passing-yield and the outer (lambda (yield) ...) are boilerplate. But after the second lambda, this is character-for-character identical with the ideal generator syntax we started with.

Syntactic sugar

Macros let us abstract away this boilerplate. First, we need to make yield into a keyword. In Guile, the simplest way to do this is with a syntax parameter:

(define-syntax-parameter yield
  (lambda (stx)
    (syntax-violation
     'yield
     "Yield is undefined outside of a generator expression"
     stx)))

Now trying to use yield outside of a generator expression will error (you can still use yield as a local variable name).

But we can use syntax-parameterize to give yield meaning inside of a generator expression:

(define-syntax-rule (generator args body ...)
  (make-generator-passing-yield
   (lambda (yield%)
     (syntax-parameterize ((yield (identifier-syntax yield%)))
       (lambda args body ...)))))

And the generator expression

(define count
  (generator ()
    (let loop ((i start))
      (yield i)
      (loop (1+ i)))))

works as desired!

What if yield means something in the language of the domain

In 97 things every programmer should know, Dan North advises to “code in the language of the domain”, comparing the code samples

if (portfolioIdsByTraderId.get(trader.getId())
    .containsKey(portfolio.getId())) {...}

and the equivalent but immediately readable

if (trader.canView(portfolio)) {...}

This is in line with the classic lisp advice to build the language up to understand what you want to say instead of lowering your thoughts down to the language.

Some domains, finance or farming for example, use yield as jargon. Using our generator expressions in such codebases introduces ambiguity: is yield domain jargon or a language keyword?

What can we do? What should we do?

Nothing

This is what Python does. Trying to run yield=3 errors. This might be good enough for us. It’s likely that there’s different kinds of yields (crop yields, financial yields). A more specific name on the client side might be fine.

Guile’s module system

Guile’s module system allows accessing through a long name with @ or through a #:prefix in the client’s use-modules declaration.

Just add

(define-module (generator)
  #:export (generator yield))

at the top of the file. Then clients can say

(define count
  ((@ (generator) generator) ()
   (let loop ((i 0))
     ((@ (generator) yield) i)
     (loop (1+ i)))))

or the much more ergonomic

(load "generator.scm")
(use-modules ((generator) #:prefix gen.))
(define count
  (gen.generator ()
    (let loop ((i 0))
      (gen.yield i)
      (loop (1+ i)))))

Let the user supply a keyword

We can let users supply a yield keyword:

(define-syntax-rule (generator yield-keyword args body ...)
  (make-generator-passing-yield
   (lambda (yield-keyword)
     (lambda args body ...))))

In general, letting client code decide the names that a macro will inject into its scope is a good idea. Implicitly defining variables in macros means programmers have to remember bespoke context-sensitive keywords. As I always say “when in doubt, don’t silently inject names into client code’s scope”.

But yield is the standard name for this operation. In the wikipedia page for generators, almost all languages with syntax for generators use the keyword yield. Consider a call site for this version of generator:

(generator yield ()
  (let loop ((i 0))
    (yield i)
    (loop (1+ i))))

In the typical case, yield adds noise. In the worst case, code is obfuscated.

(generator floop ()
  (let loop ((i 0))
    (floop i)
    (loop (1+ i))))

We could rectify the situation by having a version of generator that defaults to yield yet allows users to supply their own name, but now this simple macro is getting complicated.

So, which one?

In my opinion, choice 2, using the module system, is best. It adds the necessary flexibility with minimal complexity. People who don’t need it don’t even need to think about it. And yield will be called some variant of the word yield.

See also

• The Guile manual’s entry on prompts
• Andy Wingo has some good blog posts
  • Guile and delimited continuations goes over delimited continuations and their implementation.
  • Growing fibers goes over using delimited continuations to implement fibers (cooperative lightweight threads)
• Handling Control, The paper Andy Wingo cites as the paper proposing the version of delimited continuations Guile uses.