Catonano writes:
> as in the subject
>
> I'm trying to get acquainted with this prompts thing. Can anyone indicate an
> example of use to me that is particuraly meaningful or expressive ?
What guile calls prompts and aborts, are generally found under the
heading of 'delimited continuations'. These are primitive control
operators that can be used to implement more complicated kinds of
control, such as backtracking, exceptions, generators,etc.
Generators tend to be a good starting point, as they have proven
themselves to be very useful in practice, and many programmers are
familiar with them. So we will take that as our example.
Say we want to be able to write a generator for the natural numbers,
then in python the way we would write this is
>>> def naturals():
... x = 0
... while True:
... yield x
... x += 1
...
>>> gen = naturals()
>>> gen
>>> next(gen)
0
>>> next(gen)
1
>>> next(gen)
2
>>> next(gen)
3
and so on. We might like to write something similar in scheme (only
without mixing up generators and functions like python does :P ). Our
hypothetical ideal syntax will be
(define naturals
(generator
(let loop ((x 0))
(yield x)
(loop (1+ x)
but for now, we'll go for the more modest
(make-generator (lambda (yield) ...))
and leave the syntactic sugar for later.
So, we need to write a function make-generator, of one argument (a
procedure taking a yield procedure), that returns a generator object.
When we call 'next' on this generator object, it will run the procedure
until it either comes to a 'yield' or it finishes normally. When it
comes to a yield, it isn't enough to just stop the computation, as we
need to be able to continue it again when we want more values. This
suggests we need a "continuable abort". Which is what the procedure
'abort-to-prompt' provides. We also need to be specify where to abort to
(i.e. the place where next was called), which is what 'call-with-prompt'
gives us.
So our first draft version of a generator becomes.
;; make-generator calls proc with a procedure that aborts the generator
;; continuably with the specified value
(define (make-generator proc)
(lambda () ;; we don't want generator to start immediately
(proc (lambda (escape-val)
;; prompts are tagged so we know which kind of prompt we are
;; aborting to
(abort-to-prompt 'generator-prompt escape-val)
(define (next generator)
(call-with-prompt 'generator-prompt
(lambda () ;; run generator
(generator))
(lambda (resume val) ;; just return val
val)))
but hang on, we don't have a way to associate resume procedure with the
generator.
To do this, we create a generator object, with a mutable resume
field. Which next will update when the generator returns.
(import (rnrs records syntactic)) ; my preferred record macro YMMV
(define-record-type (generator make-raw-generator generator?)
(fields (mutable next)))
now we update our 'make-generator' and 'next-generator' procedures to
take into account these generator objects.
(define (make-generator proc)
(make-raw-generator
(lambda ()
(proc (lambda (escape-val)
(abort-to-prompt 'generator-prompt escape-val))
(define (next generator)
(call-with-prompt 'generator-prompt
(lambda ()
(let ((next (generator-next generator)))
(next)))
(lambda (resume val)
(generator-next-set! generator resume)
val)))
Now we can define our natural number generator.
(define naturals
(make-generator
(lambda (yield)
(let loop ((i 0))
(yield i)
(loop (1+ i))
and test it out
scheme@(guile−user)> naturals
$8 = #
scheme@(guile−user)> (next naturals)
$9 = 0
scheme@(guile−user)> (next naturals)
$10 = 1
scheme@(guile−user)> (next naturals)
$11 = 2
scheme@(guile−user)> (next naturals)
$12 = 3
This generator implementation can be improved still further. Currently,
it behaves strangely if the procedure terminates
(define bug-gen
(make-generator
(lambda (yield)
(yield 'first)
(yield 'second)
(yield 'third)
'final)))
scheme@(guile−user)> (next bug-gen)
$17 = first
scheme@(guile−user)> (next bug-gen)
$18 = second
scheme@(guile−user)> (next bug-gen)
$19 = third
scheme@(guile−user)> (next bug-gen)
$20 = final
scheme@(guile−user)> (next bug-gen)
$21 = final
scheme@(guile−user)> (next bug-gen)
$22 = final
we'd like it to return an end-of-generator object in this case, so we
don't keep doing redundant computation.
(define-record-type end-of-generator)
So, if the generator returns normally, i.e. it doesn't abort, then we
modify the generator to indicate it is finished. And we take this into
account in 'next'.
(define-record-type (generator make-raw-generator generator?)
(fields (mutable finished?) (mutable next)))
(define (make-generator proc)
(make-raw-generator
#f
(lambda ()
(proc (lambda (escape-val)
(abort-to-prompt 'generator-prompt escape-val))
