Tutorial on writing 'yield' [Was: Re: [plt-scheme] question about continuation example in "t-y-scheme in fixnum days"]

Hi Danny,
I couldn't thank you enough! I read very carefully
every single word, and I (hopefully ;)) understand
all, no further questions ;). Not only the question I
asked, but I learned a lot of other stuff: Indeed,
this was a very enjoyable read!

It took me a while to digest the material, but it was
really worth it. After this post, I also placed an
order for the complete "... Schemer" series by
Friedman ;), so he owes you ;).

Thank you so much!

Regards,

Nusret





--- Danny Yoo <dyoo at hkn.eecs.berkeley.edu> wrote:

> 
> 
> On Mon, 3 Apr 2006, nusret wrote:
> 
> > I'm learning Scheme and got a little bit confused
> after reading the tree
> > traversal example on Ch 13, "Jumps" of Teach
> yourself scheme in fixnum
> > days. (page 53 in the pdf file).
> 
> 
> Hi nusret,
> 
> 
> [Note: most of this comes from The Little Schemer;
> you might want to take
> a look at that book sometime: it covers this more
> comprehensively.
> 
> This post is a bit long; apologies!]
> 
> 
> 
> Perhaps it might help if we simplify the example to
> something slightly
> simpler: let's say that we'd like to write a
> generator to march through a
> list of items.  That is, let's say that we'd like
> some function called
> LIST->GENERATOR that behaves like this:
> 
>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> > (define elt-generator
>     (list->generator '(hello world) (lambda ()
> 'done)))
> > (elt-generator)
> 'hello
> > (elt-generator)
> 'world
> > (elt-generator)
> 'done
>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> 
> 
> 
> How can we go about doing this?  Here's one
> approach:
> 
>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> (module generator-example mzscheme
>   (provide list->generator)
>   (require (lib "list.ss"))
> 
>   ;; list->generator: (listof X) (-> Y) -> (union X
> Y)
>   ;; returns a generator function that, when called,
> returns successive
>   ;; elements of the list.  When the list is
> exhausted, returns the
>   ;; results of applying finished-thunk.
>   (define (list->generator list finished-thunk)
>     (letrec ([entry-point
>               (lambda ()
>                 (cond
>                   [(restoring-from-save?)
> (continue-from-restore-point!)]
>                   [else (do-work list)]))]
>              [saved-point (void)]
>              [restoring-from-save? (lambda () (not
> (void? saved-point)))]
>              [continue-from-restore-point! (lambda
> () (saved-point))]
>              [save-point! (lambda (f) (set!
> saved-point f))]
>              [do-work
>               (lambda (list)
>                 (cond
>                   [(empty? list) (finished-thunk)]
>                   [else
>                    (save-point! (lambda () (do-work
> (rest list))))
>                    (first list)]))])
>       entry-point)))
>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> 
> 
> We're not really using continuations yet, although
> we'll start to
> introduce it soon.  *grin*
> 
> But I hope the rest of the code is clear: we're
> iterating across the list,
> and right before we return elements back, we record
> what we need to do
> next, so that when we call the generator back, the
> entry-point can pick up
> where it left off.
> 
> Let's try it out:
> 
> ;;;;;;
> > (define elts (list->generator '(hello world)
> (lambda () 'done)))
> > (list (elts) (elts) (elts))
> (hello world done)
> ;;;;;;
> 
> 
> Ok, so it works.  But now let's slowly introduce
> elements of continuations
> into the system and see how far we can take this.
> 
> 
> First, let's use what we already know about
> "escaping" continuations and
> modify the entry point slightly, so that results
> that we compute are
> explicitely thrown up to the caller:
> 
>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>   (define (list->generator list finished-thunk)
>     (letrec ([entry-point
>               (lambda ()
>                 (call/cc (lambda (k)
>                            (set! caller k)
>                            (cond
>                              [(restoring-from-save?)
>                              
> (continue-from-restore-point!)]
>                              [else (do-work
> list)]))))]
>              [caller (void)]
>              [saved-point (void)]
>              [restoring-from-save? (lambda () (not
> (void? saved-point)))]
>              [continue-from-restore-point! (lambda
> () (saved-point))]
>              [save-point! (lambda (f) (set!
> saved-point f))]
>              [do-work
>               (lambda (list)
>                 (cond
>                   [(empty? list) (caller
> (finished-thunk))]
>                   [else
>                    (save-point! (lambda () (do-work
> (rest list))))
>                    (caller (first list))]))])
>       entry-point))
>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> 
> Here, we've made changes to ENTRY-POINT and DO-WORK,
> but this should still
> have the same effect as before.  do-work uses CALLER
> to throw values back,
> but otherwise, this shouldn't be too inescapable. 
> *grin*
> 
> 
> Next, let's look at DO-WORK:
> 
>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>              [do-work
>               (lambda (list)
>                 (cond
>                   [(empty? list) (caller
> (finished-thunk))]
>                   [else
>                    (save-point! (lambda () (do-work
> (rest list))))
>                    (caller (first list))]
>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> 
> 
> This almost looks like a simple list traversal using
> what we understand
> about structural recursion, except for the funky
> call to SAVE-POINT, where
> we're explicitely building a lambda that tells the
> system what to do next.
> 
> 
> Wouldn't it be nice if we didn't have to explicitely
> code that
> 
>     (lambda () (do-work (rest list)))
> 
> part?  It turns out that we can, if we take
> advantage of call/cc:
> 
>              [do-work
>               (lambda (lst)
>                 (cond
>                   [(empty? lst) (caller
> (finished-thunk))]
>                   [else
>                    (call/cc (lambda (k)
>                               (save-point! k)
>                               (caller (first lst))))
>                    (do-work (rest lst))]))]
> 
> 
=== message truncated ===


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com