On this page:
<fake-dw2>
<make-file>
<for-use>
<loop-use>
<cwif1>
<generator>
<try>
<attempt1>
<cwif2>
<attempt2>
<cwif3>
<attempt3>
1 Yo! It’s almost time to go!
<*>

2013-10-07: Saving State with Dynamic Wind

The source for this post is online at 2013-10-07-fseek.rkt.

Categories: Racket Continuations

dynamic-wind is a function that allows you to write code that is "robust" in the face of time travel through continuations. We wrote about it once before but there’s more to be said.

-

dynamic-wind works by taking three functions that I call before-f, body, and after-f. dynamic-wind guarantees that whenever body is called, before-f was just called and whenever body exits after-f will be called. Finally, the value returned is the same body.

In a programming language without exceptions, you could implement it via:

(define (dynamic-wind before-f body after-f)
  (begin (before-f)
         (begin0 (body)
                 (after-f))))

But because exceptions may occur inside of body and cause control to jump past after-f, it has to be written more like:

(define (dynamic-wind before-f body after-f)
  (define raised? #f)
  (define raise-v #f)
  (begin (before-f)
         (begin0 (with-handlers ([exn?
                                  (λ (x)
                                    (set! raised? #t)
                                    (set! raise-v x))])
                   (body))
                 (after-f)
                 (when raised? (raise raise-v)))))

But things are even more complicated with escape continuations and continuation aborts, because control could leave body without throwing an exception. Furthermore, body could capture a continuation and give to the outside. If it were ever called, then we would go back inside body and thus need to re-run before-f. This is why dynamic-wind needs to be a primitive of Racket.

So, given this primer, what’s the point of dynamic-wind? It is normally described as being used to ensure that body sees a consistent view of state despite time travel. Let’s see how true that is.

First, we’ll need a temporary file with some values in it:

(define f (make-temporary-file))
(with-output-to-file f
  #:exists 'replace
  (λ ()
    (for ([i (in-range 5)])
      (write (list i)))))
 
(check-equal?
 (file->list f)
 '((0) (1) (2) (3) (4)))

Now, let’s write a function that allows another function to reliably read from this file. We’ll call the function call-with-input-file*. It’s job is to open a file, give it to a function, and close it if the function exits. We to ensure that the function’s use of the file is robust in the face of time travel. Here’s a simple use:

(check-equal?
 (call-with-input-file* f
   (λ (ip)
     (for/list ([v (in-port read ip)])
       v)))
 '((0) (1) (2) (3) (4)))

If we want to expand away the use of for/list and in-port, this is the same as:

(check-equal?
 (call-with-input-file* f
   (λ (ip)
     (let loop ()
       (define v (read ip))
       (if (eof-object? v)
         empty
         (cons v (loop))))))
 '((0) (1) (2) (3) (4)))

The most obvious way to write this function is as follows:

(define (call-with-input-file* p f)
  (define ip #f)
  (dynamic-wind
      (λ ()
        (set! ip (open-input-file p)))
      (λ ()
        (f ip))
      (λ ()
        (close-input-port ip)
        (set! ip #f))))

Let’s see how well this version handles time travel! We’ll use racket/generator to simulate time travel. This module provides generators that can gradually return streams of values. Whenever a value is returned (with yield), we go back to the context of the caller (an exit) and whenever a value is requested we go back to the context of the generator (a jump).

Our generator will gradually read each one of the values in the file and yield them until it reaches the end, which it will signal with #f. We’ll construct a list of all the things yielded. However, notice that we also iterate through the naturals up to 6. Remember that there are only 5 values in the file though, so the in-producer should end first!

(define f-generator
  (generator ()
             (call-with-input-file* f
               (λ (ip)
                 (let loop ()
                   (define v (read ip))
                   (if (eof-object? v)
                     (yield #f)
                     (begin (yield v)
                            (loop))))))))
(for/list ([v (in-producer f-generator #f)]
           [i (in-range 6)])
  v)

We’ll put this in a macro to try it out with different implementations of call-with-input-file*.

<try> ::=
(define-syntax-rule (try-generator call-with-input-file*)
  (let ()
    <generator>))

If we try this with our first attempt, then it fails with the error input port is closed because the continuation closes over the particular port it was given the first time, which is now closed.

(check-exn
 (λ (x) (regexp-match #rx"input port is closed" (exn-message x)))
 (λ () (try-generator call-with-input-file*)))

We could fix this two ways. The best way would be to change call-with-input-file* so it gave a box with an input port inside, to expose that the port can change. However we’d have to rewrite <generator> to do that, so let’s just turn call-with-input-file* into a macro that knows the structure of its argument and can directly modify the argument:

(define-syntax-rule (call-with-input-file*/macro p (λ (ip) body ...))
  (let ()
    (define ip #f)
    (dynamic-wind
        (λ ()
          (set! ip (open-input-file p)))
        (λ ()
          body ...)
        (λ ()
          (close-input-port ip)
          (set! ip #f)))))

This will ensure that the body of the generator will get the correct input port every time it gets control. Unfortunately when we run the test, we find that it returns a list of 6 0 lists! This is one too many and it’s always the first value!

(check-equal?
 (try-generator call-with-input-file*/macro)
 '((0) (0) (0) (0) (0) (0)))

If we didn’t include the in-range in our test, then it would have been an infinite loop!

The problem is that our use of dynamic-wind doesn’t restore all the state. In particular, it doesn’t restore the position within the file that we were reading! We can fix that, of course, using file-position:

(define-syntax-rule (call-with-input-file*/macro+fseek p (λ (ip) body ...))
  (let ()
    (define ip #f)
    (define pos 0)
    (dynamic-wind
        (λ ()
          (set! ip (open-input-file p))
          (file-position ip pos))
        (λ ()
          body ...)
        (λ ()
          (set! pos (file-position ip))
          (close-input-port ip)
          (set! ip #f)))))

After this change, our generator example returns the appropriate number of values and all the right ones too!

(check-equal?
 (try-generator call-with-input-file*/macro+fseek)
 '((0) (1) (2) (3) (4)))

1 Yo! It’s almost time to go!

But first let’s remember what we learned today!

dynamic-wind is necessary in a world of continuations to write code robust against time travel.

Sometimes being robust against time travel means exposing that time travel is possible and things can change from beneath the code using mutation.

It is not always obvious what state needs to be preserved across continuation jumps.

If you’d like to run this exact code at home, you should put it in this order:

<*> ::=
(require racket/list
         racket/file
         rackunit
         racket/generator)
 
(let ()
  (let () <fake-dw1> (void))
  (let () <fake-dw2> (void)))
 
<make-file>
 
<cwif1>
<for-use>
<loop-use>
<try>
<attempt1>
 
<cwif2>
<attempt2>
 
<cwif3>
<attempt3>
 
(delete-file f)