Monday, December 7, 2009

Typed call-with-current-continuation?

I ran into an interesting problem today. In certain use cases, make-generator fails to type correctly:


(define (make-generator producer)
(let ((ready #f)
;; just holding useless continuations
(caller (call/cc id))
(saved-point (call/cc id)))

(define (entry-point)
(call/cc
(lambda (k)
(set! caller k)
(if ready
(saved-point #f)
(producer yield)))))

(define (yield v)
(call/cc
(lambda (k)
(set! ready #t)
(set! saved-point k)
(caller v))))
entry-point
))


Note the call (saved-point #f). This is returning #f to a normally-ignored continuation:


(define (make-int-generator n)
(make-generator
(lambda (consumer)
(let loop ((n 0))
(consumer n)
(loop (+ n 1))))))


Depending on where you place a call to your consumer function, the continuation may or may not be ignored. I got different results depending on whether I called an external function to produce values, or an inline loop. I thought maybe by rewriting make-generator using lower-level prims putcc and getcc, I could make the problem go away.

Although it has simplified make-generator, the problem hasn't really gone away:



(define (make-generator producer)
(let ((ready #f)
;; holding useless continuations
(caller (getcc))
(saved-point (getcc))
)
(define (entry-point)
(set! caller (getcc))
(if ready
(putcc saved-point #u)
(producer yield)))
(define (yield v)
(set! saved-point (getcc))
(set! ready #t)
(putcc caller v))
entry-point
))


I made the problem go away by changing the type declaration for putcc:


(define (putcc k r)
(%%cexp (continuation 'a -> 'b) "(k=%s, %s)" k r))


It used to read (continuation 'a -> 'a), and if you look at the tiny bit of C code there that's exactly what it does. However. We're talking about continuations here. It's very difficult to wrap my head around what it does 'in the real world'.

I'm sure that my getcc/putcc are not new, they're just the obvious way to save and store continuations. Have I typed this correctly, or have I waved my hand? How do the other typed languages deal with this problem?

One solution I tried was to pass make-generator an extra argument, of the generated type, and use that for the call to saved-point. It feels wrong, but ultimately may be the cleanest approach.

1 comment:

  1. Urgh. The formatting is messed up in the code bits. Did I choose the wrong blogging platform?

    ReplyDelete