[<<][plt][>>][..]
Thu Mar 26 20:46:22 CET 2009

Using control/prompt

Using prompt and control it's possible to turn a data traversal into
an element generator.  For example, iterate over all elements in an
xml tree, and prodice a sequence of (list path element):

;; Generate all elements + (reverse) path.
(define (element-generator top-e)
  (define (next)
    (let down ((e top-e)
               (p '()))
      (control k
               (set! next k)
               (list p e))
      (for ((e (element-content e)))
           (when (element? e)
             (down e (cons (element-name e) p))))
      #f))
  (lambda ()
    (prompt (next))))


Now I wonder, can we create a sequence directly without mutation and
going from generator -> lazy list?  The (element . k) pair can
probably be instantiated as a data item.

;; A glist is either a pair of (element . generator-thunk) or '()
;; The thunk generates the tail of the list.
(define (element->glist top-e)
  (prompt
   (let down ((e top-e)
              (p '()))
     (control k
              (cons (list p e)
                    (lambda () (prompt (k)))))
     (for ((e (element-content e)))
          (when (element? e)
            (down e (cons (element-name e) p))))
     '())))

(define glist-null? null)
(define glist-car   car)
(define (glist-cdr gl) ((cdr gl)))

This can be combined with memoization by wrapping the continuation in
a promise instead of a thunk.

;; Directly convert a traversal program into a lazy list, a memoized
;; version of the glist above.


(define (element->ll top-e)
  (prompt
   (let down ((e top-e)
              (p '()))
     (control k
              (delay
                (cons (list p e)
                      (prompt (k)))))
     (for ((e (element-content e)))
          (when (element? e)
            (down e (cons (element-name e) p)))))
   (delay '())))


Abstracted with macros this becomes:

(define-syntax-rule (ll-yield x)
  (control k (delay (cons x (prompt (k))))))
(define-syntax-rule (ll-begin . body)
  (prompt (begin . body) (delay '())))

(define (element->ll top-e)
  (ll-begin
   (let down ((e top-e) (p '()))
     (ll-yield (list p e))
     (for ((e (element-content e)))
          (when (element? e)
            (down e (cons (element-name e) p)))))))


This allows construction of lazy lists from lazy list comprehensions,
giving a simple composition mechanism:

(ll-begin
  (for ((x (in-lazy-list other-ll)))
    (ll-yield (+ 1 x))))



[Reply][About]
[<<][plt][>>][..]