Re: Multiple values Eli Barzilay 16 Oct 2006 21:26 UTC
On Oct 15, Eli Barzilay wrote: > > FWIW, here is an implementation of lazy/eager/delay/force that works > with multiple values. [...] Another implementation. This one uses a different solution than the srfi code. The main idea is adding a `force*' operation, that intuitively has the meaning of an iterated `force': (define (force* x) (if (promise? x) (force* (force x)) x)) Just as the srfi describes, there are certain infinite computation chains that lead to holding a a growing linked list of promises in memory, each promise pointing at the next (p1 -> p2 -> p3 -> ...), and `force*' is working at the end of this list, and keep extending it. The srfi-45 solution is (roughly, adapted to `force*') to add another layer of reference (the box wrapper) so when `force*' gets to p2, it will set p1 to be an alias of p2, and then the computation continues with p1 (so if nobody holds on to p2, it will get collected). (No infinite list can be generated from these aliases.) The solution below works without the extra box wrapper. The idea is that when `force*' gets to p2, it swaps the contents of the two promises so that p2 points at p1, and p1 has the thunk with the rest of the computation. The same thing happens now: the computation continues with p1, and if nobody holds on to p2 it can be collected. Again, all of p2, p3, ... will point at p1, so no infinite list is created. ;; uses a promise implementation with a single thunk/value-list slot `p' (define (force* x) (if (promise? x) (let loop ([v (force x)]) (if (promise? v) (begin (set-promise-p! x (promise-p v)) (set-promise-p! v (list x)) (loop (force x))) v)) x)) This is fine behavior for `force*' because it does not distinguish promises from their values: if force(p1) = p2, then force*(p1) = force*(p2), and swapping them is not visible if you use only `force*'. This is particularly useful for a lazy language implementation, where distinguishing a promise from its value does not make sense. It is, however, not behaving well if you do care to distinguish promises and values -- for example: > (define r (delay 1)) > (define s (delay r)) > (force r) 1 > (force* s) 1 > (force r) #<struct:promise> ; <-- different > (force* r) 1 ; <-- but ok if you only use `force*' Other than that, it is a fine solution -- passes all of the srfi tests (using only `delay', and using `force*' instead of `force'). To implement the functionality of srfi-45, this distinction needs to be kept. One way to achieve this is to have a second implementation of promises that is used to wrap the built-in type. So the new type (promise*) is similar to the built in one (promise) and its `force*' operation works as above -- using `force' for a final built-in promise. The result is: a new form for delaying computation (equivalent to `lazy'), and a new `force*' that flattens such promise chains as well as `force'ing plain promises (so it's equivalent to srfi 45's `force'). This is implemented in the following module for PLT (and easily adapted to other implementations). The code passes all of the tests in the srfi document. (module force* mzscheme (provide lazy (rename force* force)) (define-struct promise* (p)) (define-syntax lazy (syntax-rules () [(lazy exp) (make-promise* (lambda () exp))])) (define (force-once p) (let ([v (promise*-p p)]) (if (procedure? v) (let* ([v (v)] [v* (promise*-p p)]) (if (procedure? v*) (begin (set-promise*-p! p (list v)) v) (car v*))) (car v)))) (define (force* x) (cond [(promise*? x) (let loop ([v (force-once x)]) (cond [(promise*? v) (set-promise*-p! x (promise*-p v)) (set-promise*-p! v (list x)) (loop (force-once x))] [(promise? v) (force v)] [else v]))] [(promise? x) (force x)] [else (raise-type-error 'force "promise*" x)])) ) -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://www.barzilay.org/ Maze is Life!