Re: prompts: any example ?

[Ian Price <ianprice90@googlemail.com>]

Catonano <catonano@gmail.com> 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
<generator object naturals at 0x930fa2c>
>>> 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 = #<r6rs:record:generator>
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))))))

(define (next generator)
  (if (generator-finished? generator)
      (make-end-of-generator)
      (call-with-prompt 'generator-prompt
        (lambda ()
          (let ((next (generator-next generator)))
            (call-with-values next
              (lambda args
                (generator-finished?-set! generator #t)
                (apply values args)))))
        (lambda (resume val)
          (generator-next-set! generator resume)
          val))))

Now we don't do extra work when the generator is finished

scheme@(guile−user)> (define bug-gen
  (make-generator
    (lambda (yield)
      (yield 'first)
      (yield 'second)
      (yield 'third)
      'final)))
scheme@(guile−user)> (next bug-gen)
$32 = first
scheme@(guile−user)> (next bug-gen)
$33 = second
scheme@(guile−user)> (next bug-gen)
$34 = third
scheme@(guile−user)> (next bug-gen)
$35 = final
scheme@(guile−user)> (next bug-gen)
$36 = #<r6rs:record:end−of−generator>
scheme@(guile−user)> (next bug-gen)
$37 = #<r6rs:record:end−of−generator>

Finally, some syntactic sugar instead of using make-generator

(define-syntax-parameter yield
  (lambda (stx)
    (syntax-violation 'yield "yield used outside of a generator form" stx)))

(define-syntax-rule (generator body rest ...)
  (make-generator
    (lambda (yield*)
      (syntax-parameterize ((yield (syntax-rules ()
                                     ((yield val)
                                      (yield* val)))))
        body
        rest ...))))

Now, we can just write

(define naturals
  (generator
    (let loop ((x 0))
      (yield x)
      (loop (1+ x)))))

instead of

(define naturals
  (make-generator
    (lambda (yield)
      (let loop ((x 0))
        (yield x)
        (loop (1+ x))))))

Some conclusions
================

Firstly, I apologise for the style, this was, with minor editing, how it
came to mind. Second, perhaps this should be packaged up so that I don't
keep reinventing it every time someone wants an example of continuations
in practice. And thirdly, below are some gists for other examples
including (sigh) a previously written generator example (though it uses
shift/reset).

I hope this has been useful. Defining your own control structures is
something you will need to, and probably should do, only rarely. You'll
generally know when that is since you will be trying to do something
crazy, or having to write in a convoluted programming style.

https://gist.github.com/1548531 - monadic reflection
https://gist.github.com/1381107 - continuations for web programming
https://gist.github.com/1381091 - simple generators.

-- 
Ian Price

"Programming is like pinball. The reward for doing it well is
the opportunity to do it again" - from "The Wizardy Compiled"