Delimited continuations do dynamic-wind

Oleg's argument against call/cc links to one of his lesser known posts, Delimited continuations do dynamic-wind. In it he first shows how to implement yielding generators in terms of delimited control, and then shows how such generators lead to a natural definition of dynamic-wind, in userland, whereas with undelimited continuations, dynamic-wind has to be primitive.

(This is not entirely true. Kernel can implement dynamic-wind in userland, too, by means of its guarded undelimited continuations. And in Scheme 48, dynamic-wind is also implemented in userland with undelimited continuations, albeit in terms of a slightly lower level API than call/cc. Same is true for other Schemes, such as MIT Scheme. And probably the earliest definition of dynamic-wind, in Embedding Continuations in Procedural Objects is also in userland, so I'm a bit confused actually, as to why Oleg considers dynamic-wind primitive...)

Back to Oleg's generators in terms of delimited control. While one may argue against first-class continuations, whether delimited or not, I think having them in the language is great for quickly prototyping different ideas, such as generators. This has always been a forte of Lisp, and so high-powered control flow operations seem a good fit for the language, even if their runtime cost may be slightly higher than a more specialized, native implementation of some specific control feature, such as generators.

The basic ideas of generators are: you have a block of code, the generator, which may either normally return a value by means of reaching the end of the block, or it may intermittently yield a value. To call a generator, we need a boundary around it, so we wrap it in a prompt with reset. Yielding suspends the generator, capturing its delimited continuation up to the prompt, and delivers the value and this continuation to the caller, outside the boundary. Value and continuation are wrapped up in a special record type, so the caller can distinguish yields from an ordinary return, which doesn't wrap the value in any way (and neither provides a continuation for resuming, obviously). (This could probably be handled more elegantly with Racket's abort handlers.)

In this Gist, I've commented Oleg's implementation of generators and dynamic-wind.

	;; See http://okmij.org/ftp/continuations/implementations.html#dynamic-wind
	;; and http://axisofeval.blogspot.com/2012/08/delimited-continuations-do-dynamic-wind.html
	;; Slight trick here: use identity of yield-record-tag function as the actual tag
	(define (yield-record-tag) yield-record-tag)
	(define (make-yield-record v k)
	(list yield-record-tag v k))
	;; Yield simply aborts up to the generator's caller, delivering to it
	;; the yielded value and the continuation for resuming after the call
	;; to yield.
	(define (yield v) (shift k (make-yield-record v k)))
	;; I think this should really be a procedure and not a macro, for clarity.
	;; Anyway, try-yield receives whatever a generator either returned ordinarily,
	;; or yielded, and takes it apart. If it's an ordinary returned value, it
	;; executes the on-r expression. If it's a yield record, containing a value
	;; and resume continuation, execute the on-y block. We'll see this in action
	;; below.
	(define-syntax try-yield
	(syntax-rules ()
	((try-yield exp (r on-r) (v k on-y))
	(let ((exp-r exp))
	(if (and (pair? exp-r) (eq? (car exp-r) yield-record-tag))
	(let ((v (cadr exp-r)) (k (caddr exp-r))) on-y)
	(let ((r exp-r)) on-r))))))
	;; Here's a for loop for looping over the values yielded by a generator.
	;; It takes a generator thunk, and a body function taking a yielded value.
	;; It wraps a prompt around the generator with reset. Then it takes apart
	;; what the generator returned: if it's an ordinary value R, return it. If it's
	;; yield record containing a value V and a resumption continuation K, call
	;; the body function with the value, and after that resume our loop, returning
	;; #f to the yield call inside the generator (here one could also pass another
	;; value back into the generator).
	(define (for-loop generator body)
	(let loop ((thr (reset (generator))))
	(try-yield thr
	(r r)
	(v k
	(begin
	(body v)
	(loop (k #f)))))))
	;; For example, this will print 1 and 2:
	(for-loop
	(lambda () (yield 1) (yield 2))
	(lambda (v) (display v)))
	;; Dynamic-wind ain't difficult either (in Oleg's file this is called
	;; dyn-wind-yield but I've called it dynamic-wind here for clarity.)
	;; Dynamic-wind must itself be used inside a generator prompt, if the
	;; protected thunk may yield.
	;; It simply calls the before thunk, protected thunk, and after thunk in order.
	;; If the protected thunk returned ordinarily, its result value R is returned.
	;; If it yielded, dynamic-wind also yields (the value yielded by the
	;; protected thunk). When the outside code reenters, passing the value REENTER,
	;; we again perform the before and after thunks, but this time with a new
	;; protected thunk that passes the reentered value to the original protected
	;; thunk's continuation, K.
	(define (dynamic-wind before-thunk thunk after-thunk)
	(let loop ((th (lambda () (reset (thunk)))))
	(before-thunk)
	(let ((res (th)))
	(after-thunk)
	(try-yield res
	(r r) ; return the result
	(v k
	(let ((reenter (yield v)))
	(loop (lambda () (k reenter)))))))))

view raw dyn-wind-commentary.scm hosted with ❤ by GitHub

I think it's a great example of how simple it is to add specific control flow features to a language with general (delimited) continuations.

Oh, and in typical Oleg style, the article then goes on about how you can implement call/cc in terms of generators, which makes his dynamic-wind compatible with existing Scheme examples using call/cc.