[gambit-list] promises are leading to memory retention

Christian christian at pflanze.mine.nu
Fri May 25 01:11:00 EDT 2007


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))
     , at 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))))




More information about the Gambit-list mailing list