Emulating GOTO in Scheme with continuations

In his 1968 letter, A case against the GO TO statement (known only by that name), Dijkstra said “[t]he go to statement as it stands is just too primitive, it is too much an invitation to make a mess of one’s program.” Unfortunately, scheme programmers aren’t given that invitation. That’s no fair! Fortunately, scheme has a procedure, call/cc, that we can use to emulate the control flow that GOTO provides. We can use syntactic abstraction to invite scheme programmers to make a mess of their programs in a limited context.

How `GOTO` works

Odds are, you know how GOTO works, but let’s briefly review. Perhaps you’ve seen a BASIC program that looks something like this:

10 PRINT "Hello, world!"
20 GOTO 10

This, as you may have guessed, outputs:

Hello, world!
Hello, world!
Hello, world!
Hello, world!
...

…forever.

Normally, control proceeds from the lowest line number to the highest line number, but the GOTO statement “jumps” to the given line, no matter where it is. (Forgive my imprecision, this is a basic tutorial, not a BASIC tutorial.)

You’re more likely to see goto in C:

void do_something() {
    char *important_stuff = (char*)malloc(/* ... */);
    FILE *important_file  = fopen(/* ... */);
    
    // do stuff...
    if (errno != 0) goto cleanup;
    
    // do more stuff...
    if (errno != 0) goto cleanup;

    printf("Success!\n");
    
    // control falls through even if everything goes well

cleanup:
    free(important_stuff);
    fclose(important_file);
}

Using goto here lets us avoid repeating the cleanup logic. Not my thing, but this is what most goto fans like. In C, goto uses labels: instead of line numbers, and it can’t leave the function, but otherwise it is substantially similar to BASIC’s GOTO.

Hopefully you understand goto now. It lets you jump around. The second thing you need to understand before we can implement goto with call/cc is how call/cc works.

How `call/cc` works

call/cc is short for call-with-current-continuation. call/cc takes one argument, a procedure, and returns the result of applying that procedure with the current continuation as an argument.

What is “the current continuation?” Let’s start with an example.

(define cont #f)
(begin
  (+ 1 (call/cc
         (lambda (k)
           (set! cont k)
           0)))
  (display "The number is: ")
  (write (cont 41))
  (newline))

You might call this example contrived. That is because I contrived it to be an example. Let’s run it anyway. It outputs:

The number is: The number is: The number is: ...

…forever‽

cont is actually something like

(define cont
  (lambda (x)
    (+ 1 x)
    (display "The number is: ")
    (write (cont 41))
    (newline)))

In this form, the unconditional recursion is obvious.

Continuations are a lot like procedures, but they don’t necessarily come back to where you called them. This example demonstrates that difference in behavior:

(define (displayln obj)
  (display obj)
  (newline))

(define cont #f)

(displayln
  (call/cc 
    (lambda (k)
      (set! cont k)
      "cont set")))

(begin
  (displayln "procedure called")
  (displayln "after procedure call")
  (cont "continuation called")
  (displayln "after continuation call"))

This outputs

cont set
procedure called
after procedure call
continuation called

Notice how after calling a procedure, in this case displayln, the output continues but not after calling cont.
When we call cont with a new value, it’s like we ran the same code but chose another value—this is the principle that underlies the ambiguous choice operator.

The k that call/cc calls its argument with represents, roughly, the rest of the computation. The “current continuation” is what will be executed next at the point that call/cc is called.

Incidentally, this helps me understand scheme’s multiple return values; (values v1 v2 ...) is just (call/cc (lambda (k) (k v1 v2 ...))).

I recommend reading about continuations in Dybvig’s The Scheme Programming Language if you’re (justly) dissatisfied with my explanation or just want to learn more precisely how they work and their applications.

We now have a decent understand of how call/cc works, so let’s finally use it to implement goto in scheme!

`goto` in scheme

Here you go:

(define-syntax with-goto
  (syntax-rules ()
    [(_ goto rest ...)
     (let ()
       (define goto #f)
       (%labels rest ...)
       (call/cc
        (lambda (k)
          (set! goto
            (lambda (label) (k (label))))
          rest ...)))]))

(define-syntax %labels
  (syntax-rules ()
    [(_) (begin)]
    [(_ (_ ...) rest ...) (%labels rest ...)]
    [(_ label rest ...)
     (begin
       (define (label) rest ...)
       (%labels rest ...))]))

Let’s run that with our favorite R⁶RS implementation (mine is Chez Scheme):

(with-goto goto
  loop (display "Hello, world!\n")
  (goto loop))

Hello, world!
Hello, world!
Hello, world!
Hello, world!
...

Here’s an example that doesn't loop forever:

(let ([x 1])
  (with-goto go
    (go loop)
    double
    (set! x (* 2 x))
    loop
    (display x) (newline)
    (when (< x 1000)
      (go double))
    (display "done\n")))

It outputs:

I’ll explain this macro one part at a time.

First, (define-syntax goto (syntax-rules () [...])) defines goto as a syntax transformer (more precise name for a macro) using the syntax-rules pattern-matching language. The () after syntax-rules is the empty list of literals; we don't have any special words here, so it doesn't apply. You can read more about how syntax-rules works in TSPL, but we'll only be using the most basic features here. The important thing is to know that matched names are replaced in the output and that x ... matches/splices zero or more expressions. Also, syntax-rules is hygienic, so don’t stress about name collisions.

Then, we match (_ goto rest ...). Anything else is a syntax error. The _ is for with-goto (we do not want to repeat ourselves).

We output a big let expression. Notice how the second example uses go instead of goto? That's because the first element in with-goto is the name of the goto procedure. We define it as false because we will set it later.

Next, we pass the body (rest ...) to %labels, which deserves its own heading.

Extracting labels

%labels is a syntax transformer with three cases:

(_) Nothing is passed: (begin) (do nothing)
(_ (_ ...) rest ...) A list is passed: Ignore it and process rest .... We treat expressions of the form (x ...) as statements, not labels.
(_ label rest ...) Finally, a label!

When we encounter a label, we define a thunk (procedure that takes no arguments) with the rest of the arguments as its body, like so:

(define (label) rest ...)

Putting it all together,

(%labels
  a
  (display 1)
  b
  (display 2)
  c
  (display 3))

(morally) expands to

(begin
  (define (a)
    (display 1)
    b
    (display 2)
    c
    (display 3))
    
  (define (b)
    (display 2)
    c
    (display 3))

  (define (c) (display 3)))

(The leftover labels have no effect)

This helper on its own is a really crappy way to define functions with shared tails, so let’s bring it all together.

Going to

We have our labels as functions, but what for? If we call these procedures, they will return control to us, so they aren’t like C labels at all. Well, remember how I said that continuations don’t necessarily come back to where you called them?” We’re going to exploit that property to implement goto. We wrap the body of with-goto in (call/cc (lambda (k) ...)).

Inside the body, if we call k like (k (label)) we effectively replace the body with the result of calling label. We accomplished a jump!

(set! goto (lambda (label) (k (label)))) makes goto do exactly this (note that function arguments have to be evaluated before the procedure call takes place). We use (define goto #f) combined with a set! because the labels we defined earlier need to be able to see the goto function.

This is what our first with-goto looks like when we expand it:

(let ()
  (define goto #f)
  (define (loop) (display "Hello, world!\n") (goto loop))
  (call/cc
    (lambda (k)
      (set! goto (lambda (label) (k (label))))
      loop
      (display "Hello, world!\n")
      (goto loop))))

It is in fact expanded slightly differently and more efficiently, it does not use unbounded stack space AFAIK, which makes sense because we aren’t actually increasing the depth of the callstack when we goto.

To demonstrate that fact and that labels are values, here is one last program. Make an educated guess about what it does before running it, and see if you can make any general statements about its output (other than “the output never ends”).

(with-goto go
  a
  (display "A")
  b
  (display "B")
  (go (if (zero? (random 2)) a b)))

Conclusion

This is useless. There are a lot of cool things that you can implement with call/cc, but this is dumb! There is a lot of nonsense that you can do with this implementation (try messing with nested with-goto or storing goto elsewhere). Still, I hope you learned a bit about call/cc and what building abstractions with it can look like.

Emulating GOTO in Scheme with continuations

How GOTO works

How call/cc works

goto in scheme