Musing about using Scheme, PLT, and the zwizwa/plt library. Entry: plt scheme: sequences, generators and lazy lists Date: Thu Mar 26 17:02:12 CET 2009 Looking for a standard lazy list implementation that will work well as an intermediate step to transform generators -> sequences. The problem is in these conflicting requirements: * 'make-do-sequence needs to lookahead in the sequence: know if there's an element before the next is generated. This needs a 1-level deep lookahead buffer when translating generators to squences. * generators are easily built using prompt/control but can't know end-of-sequence beforehand. Maybe this is best replaced with the lazy list structure in lazy scheme: it uses delayed constructors, (not delayed tails). The code then becomes: ;; Convert generator to lazy list (define (generator->lazy-list g [done? not]) (let next () (delay (let ((item (g))) (if (done? item) '() (cons item (next))))))) ;; Convert lazy list to sequence. (define (in-lazy-list ll) (make-do-sequence (lambda () (define (ll-car x) (car (force x))) (define (ll-cdr x) (cdr (force x))) (define (ll-more? x) (pair? (force x))) (values ll-car ll-cdr ll ll-more? void void)))) ;; Composition. (define (in-generator g [done? not]) (in-lazy-list (generator->lazy-list g done?))) The deeper conclusion is this: lazy lists (static) are better behaved than generators (dynamic). Entry: control/prompt Date: Thu Mar 26 20:46:22 CET 2009 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)))) Entry: zipper Date: Fri Mar 27 12:16:42 CET 2009 Using lazy lists as in the previous example only allows the consumption of a data structure. How can we use this to update/create new trees? Starting from a map function instead of a for-each functions, we create the zipper data structure. http://okmij.org/ftp/Scheme/zipper-in-scheme.txt (define-struct zipper (element yield)) (define (collection->zipper map collection) (reset (map (lambda (el) (shift k (make-zipper el k))) collection))) So, is it fair to say a zipper is a symmetric (bi-directional) coroutine and a lazy list an assymetric (uni-directional) coroutine? At the traversal side, the other side is represented by the mapped procedure, while on the zipper side the iterator is represented by the delimited continuation. Entry: Union types Date: Mon Mar 30 10:05:36 CEST 2009 Are union types possible in PLT scheme outside of typed scheme? No: elements of a union are types in themselves, and exist independently of the union. Entry: structs Date: Tue Mar 31 12:40:52 CEST 2009 Is it possible to create a derived struct given a prototype? (define-struct a (x)) (define-struct (b a) (y)) can we make an instance of struct b without knowing a? This probably needs delegation (a 'super field) instead of subclassing. Entry: visitor Date: Sun Apr 12 16:27:15 CEST 2009 http://calculist.blogspot.com/2008/05/functional-visitor-pattern.html This simple traversal language instructs the fold either to continue (Cont), to skip all descendants of the current node (Skip), or to abort the traversal entirely (Stop). Entry: generator end of sequence Date: Fri Apr 17 10:04:50 CEST 2009 Generators need a unique value to indicate end-of-stream. #f is convenient but probably not a good idea. Entry: multiple values and sequences Date: Fri Apr 17 11:09:46 CEST 2009 For lazy lists, it's not possible (by their definition: linked cons cells contain only a single value in the CAR position). PLT's sequences (which are generators) do support them. As mentioned before: the problem with multiple values is channeling the end-of-sequence value and the multiple values through the same channel. The scheme's sequence api has different functions for these. The simplest solution seems to be to: - stick with lazy lists as basic abstraction. - use an "unpacking" iterator: (in-lazy-list ll values) I'm adding a form "in-producer" which couples a multiple values generating body in terms of (yield . args) with a multiple values producing sequence. Entry: zipper and sequences Date: Fri Apr 17 11:25:34 CEST 2009 Sequences are uni-directional, zipper is bi-directional. However, is there a way to unify both in the same construct? Something like for/list or for/fold? This is not the right question. The right question is: how to relate processes that communicate through channels with zippers and lazy data structures. Entry: fold vs. explicit tail recursion Date: Sun Apr 19 00:49:38 CEST 2009 I often find myself writing tail recursive loops, accumulating results in (multiple) stacks, then reversing them in the end. Is this pattern necessary? I guess what I'm looking for is an "unpacked" fold, where individually named state objects get passed during iteration. This makes sense for a left fold. Does it also work for a right fold? Entry: syntax-case & introduced identifiers Date: Fri Apr 24 09:27:24 CEST 2009 A good thing about syntax-case is that it can introduce identifiers whenever a quoted syntax object does not refer to a pattern variable. However, if such a symbol is is a reference position, you will find out only at expansion time of the macro that the identifier is not defined. Why is this? Why can't this be known at macro compile time (i.e. the for-template includes should have it, no?) Is this because the compiler can't know whether the identifier is in a binding position (in which case it is legal) or a reference position (in which case it needs to be defined in the context in which the macro is expanded) ? Entry: imperative struct update Date: Sun Apr 26 13:14:18 CEST 2009 I've been looking for this for a while.. Using introspection it should be possible to create a macro that updates a struct functionally, but with field accessors.. I think it's in machine.ss Entry: immutable cyclic structures Date: Sat May 2 23:15:35 CEST 2009 self-refence with immutable structures is only possible with lazyness. however, PLT scheme contains the 'shared form, much like 'let but for data structure bindings. as long as references are guarded by list/struct constructors, this form can create cyclic structures. (shared ((ones (cons 1 ones))) ones) This works with the (immutable) native data types and mutable structs. Entry: immutable hash tables Date: Tue May 5 10:22:50 CEST 2009 From the PLT Scheme reference manual: 3.13 Hash Tables "A hash table (or simply hash) maps each of its keys to a single value. For a given hash table, keys are equivalent via equal?, eqv?, or eq?, and keys are retained either strongly or weakly (see Weak Boxes). A hash table is also either mutable or immutable; immutable tables support constant-time functional update. I didn't know about the immutable constant-time functional update. That's pretty cool! I wonder how it is implemented. Red-black trees [1] [2]. [1] http://groups.google.com/group/plt-scheme/browse_thread/thread/d6da66d2bb3855e6/445f23588930fc90?lnk=raot [2] http://en.wikipedia.org/wiki/Red-black_tree