prompts: any example ?

prompts: any example ?

[Catonano]

[-- Attachment #1: Type: text/plain, Size: 172 bytes --]

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 ?

Thanks

[-- Attachment #2: Type: text/html, Size: 192 bytes --]

Re: prompts: any example ?

[Ian Price]

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"

Re: prompts: any example ?

[Ludovic Courtès]

Hi Ian,

Excellent illustration, thank you!

Ian Price <ianprice90@googlemail.com> skribis:

> https://gist.github.com/1548531 - monadic reflection

Could you expound on this one?  I can feel the greatness, but I don’t
fully grasp it.  :-)

Ludo’.

Re: prompts: any example ?

[Ian Price]

ludo@gnu.org (Ludovic Courtès) writes:

> Hi Ian,
>
> Excellent illustration, thank you!
>
> Ian Price <ianprice90@googlemail.com> skribis:
>
>> https://gist.github.com/1548531 - monadic reflection
>
> Could you expound on this one?  I can feel the greatness, but I don’t
> fully grasp it.  :-)

Yes, and it doesn't help that it is missing a bunch of helpers :) I no
longer have the original file, so I can't even remember if I stomped out
the bugs in it(probably not).

The trick comes from, I think, Filinski's "Representing Monads",
although it has been quite a while since I've read it. Instead of monads
being represented by the usual 'bind' and 'unit' functions, or the
(categorical?) definition of 'unit', 'fmap', 'join', they are instead
represented by two operators 'reflect' and 'reify'. 

reify : (() -> a) -> m a
reflect : m a -> a

reify takes a function that returns a value, and returns a monadic
value i.e. it lifts a pure expression to an effectful one.

reflect takes a monadic value and returns the value. i.e. it lowers the
effectful value into the pure layer.

This representation has two nice properties. Firstly, we get direct
style back :-). This one is important to me, and reflects the
fundamental reason why we need continuations: To rescue us from the
horror of forced styles :).

 The second one, which I don't think he mentioned in that paper (maybe
in "representing layered monads"?) is that tagged delimited
continuations actually allow us to use multiple monads quite naturally,
without the need to invent things like monad transformers. In that
example, I quite naturally mix the reader and state monads.

It isn't quite perfect: the 'do-rename' function is not pretty, some
functions like 'with-extended-environment' need to take a thunk, and
without inference we need a different named reflect/reify for each
monad, but it seems relatively useful and I was quite obsessed with it
for a time.

-- 
Ian Price

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

Re: prompts: any example ?

[Ian Price]

Ian Price <ianprice90@googlemail.com> writes:

> The trick comes from, I think, Filinski's "Representing Monads",
> although it has been quite a while since I've read it. Instead of monads
> being represented by the usual 'bind' and 'unit' functions, or the
> (categorical?) definition of 'unit', 'fmap', 'join', they are instead
> represented by two operators 'reflect' and 'reify'. 
>
> reify : (() -> a) -> m a
> reflect : m a -> a
>
> reify takes a function that returns a value, and returns a monadic
> value i.e. it lifts a pure expression to an effectful one.
>
> reflect takes a monadic value and returns the value. i.e. it lowers the
> effectful value into the pure layer.

One thing I forgot to mention is that there is a simple way to turn the
unit/bind representation into the reify/reflect representation, and you
see it at the top of the gist.

(define (reify thunk)
  (reset (return (thunk))))

(define (reflect m)
  (shift k (>>= m k)))

only I used tagged variants of shift/reset instead to allow mixing (as
already mentioned)

-- 
Ian Price

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

Re: prompts: any example ?

[Catonano]

2012-03-03 9:08 GMT+01:00 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.
>

So, yes, I'm replying to a post of 2012. In 2016

Back then I couldn't understand Ian's example and I was upset and ashamed
to admit it

I actually understood it a few days ago. Maybe helped by another example
made without the shift reset but rather with the plain call/cc

Since then I even gave a course teaching the SICP to a bunch of teens, in a
local computers club. It was brave of me and incredibly fun

I'm trying again getting acquainted with Guile, now. Not only because of
Guix

So, hello again, guilers