Hello
I have read SRFI-45 (Primitives for Expressing Iterative Lazy Algorithms by André van Tonder [1]), but I'm not sure whether I'm sharing his view on the necessity of the additional |lazy| operator; at least I don't think it is necessary for the stream-filter example, since one can code the iterative part without involving any (delay (force .. )) invocations. One just has to distinguish between two separate recursive calls. See my example below. (The |lazy| operator could still possibly be useful in situations where one is using code written by others where the iterative path isn't free from lazyness. Of for other kinds of freedom I'm not aware of right now, in the same way that tail call optimization has given freedom to new programming styles.)
[1] http://srfi.schemers.org/srfi-45/srfi-45.html
But to my disappointment, despite my belief that I could write stream-filter without the |lazy| operator, at first I couldn't get (t2 #f) to run without leaking. After much time spent debugging, I realized that it's very simple: the promise built by the outer delay in stream-filter is holding a thunk which captures the stream head. If this promise is forced, the inner, iterative loop runs, which is not by itself faulty, but which forces the stream whose head is still fixed in the thunk in the promise which is not yet freed. In my code below I've provided my own delay/force implementation to make this visible; uncommenting the line "uncomment this as a solution" makes the problem go away.
Now this technique of removing the thunk from the promise already before it is being run is of course a problem if the thunk is throwing an exception, because the promise is then broken. OTOH one could argue that leaving a promise broken in such cases is even a benefit (giving the warranty that the thunk is never ever being called more than once). (Maybe the exception could even be stored, and rethrown upon subsequent force calls; kind of like thread-join! works. Not sure how this could be done efficiently.)
Would changing the builtin promise be an option or would this break R5RS or some other standard? I'm also wondering if many cases for SRFI-45 is trying to provide a solution could really have been because of holding on to memory, not actually because of creating nested promises.
I'd be interested to hear your thoughts on the matter; maybe I should then post to the SRFI-45 discussion list.
BTW, the below code has to be run in the compiler. The interpreter will leak anyway. I guess it isn't releasing references to bindings in a scope at all before leaving the scope? Can't this be improved without lexical analysis?
If this leaking cannot be avoided by an interpreter, this is disappointing, since it means that lazy code always risks running into problems in the interpreter, and thus the interpreter cannot be used to deploy code in a productive environment. I had already planned using as much interpreted code as possible in production settings because it can be debugged much better (even "post-mortem" by capturing and serializing continuations; capturing continuation also works for compiled code of course, but one cannot step through the code and not access (only see) lexical bindings from the continuation frames). Maybe the debugging features of compiled code could be improved? Or maybe some hybrid approach including an (optional) lexical analysis could be taken for the interpreter?
Christian.
(define-macro (cj-delay body) `(vector #f (lambda () ,body)))
(define (cj-force p) (cond ((vector-ref p 1) => (lambda (thunk) ;;(vector-set! p 1 #f) ;; uncomment this as a solution. (let ((v (thunk))) (vector-set! p 0 v) (vector-set! p 1 #f) v))) (else (vector-ref p 0))))
(define-macro (F bindings . body) ;; my "macro-force-vars" `(let (,@(map (lambda (v) (if (symbol? v) `(,v (cj-force ,v)) (error "F: expecting symbol, got:" v))) bindings)) ,@body))
(define (stream-iota count #!optional (start 0) (step 1)) (if count (let rec ((val start) (count count)) (cj-delay (if (positive? count) (cons val (rec (+ val step) (- count 1))) '()))) (let rec ((val start)) (cj-delay (cons val (rec (+ val step)))))))
(define (stream-filter pred strm) (cj-delay ;; <-- this promise must not hold on to the thunk/strm. (let next ((strm strm)) (F (strm) (if (null? strm) '() (if (pair? strm) (if (pred (car strm)) (cons (car strm) (cj-delay (next (cdr strm)))) (next (cdr strm))) (error "improper stream:" strm)))))))
(define (stream-length strm) (let iter ((strm strm) (len 0)) (F (strm) (if (null? strm) len (if (pair? strm) (iter (cdr strm) (+ len 1)) (error "stream length" "improper stream:" strm))))))
(define (t1 n) (stream-length (stream-iota n)))
(define (t2 n) (stream-length (stream-filter (lambda (v) #f) (stream-iota n))))
Afficher les réponses par date