[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Stream-filter and space leaks



sperber@xxxxxxxxxxxxxxxxxxxxxxxxxxx (Michael Sperber [Mr.  Preprocessor]) writes:

> >>>>> "Matze" == Matthias Neubauer <neubauer@xxxxxxxxxxxxxxxxxxxxxxxxxx> writes:
> 
> Matze> The real problem is see is the following: as soon as I apply some kind
> Matze> of abstraction over STREAM-FILTER---which is something every Schemer
> Matze> wants to do of course---, hell breaks loose again. E.g., if I type 
> 
> Matze>    (define (filter-zero stream)
> Matze>      (stream-filter (lambda (x) (zero? x)) 
> Matze>                     stream))
>    
> Matze>    (stream-car (filter-zero (stream-from 1)))
> 
> Matze> in scsh, I will again see a space leak.
> 
> Matze> Considering all the major Scheme implementations, how common is it to
> Matze> use a flat closure representation for procedures?
> 
> This won't be solved by flat closures---the call to FILTER-ZERO is a
> non-tail call, and it'd be necessary to mark dead variables in
> continuation frames to make this not leak.

Your're right of course. There is not only the possibility that we
have to deal with closures that retain too many references but we can
also have continuation frames with this exact same deficiency.

Just for kicks, I just tested some Scheme implementations I had access
to to see how they'd behave in this respect. I tried

scsh 0.6.4 (Beta 1) | Scheme 48 0.57 | petite scheme 6.0a | MzScheme3m 203.6 | Larceny v1.0a1

Always in this very order, always without any special runtime
options. "ok" means that an example leads to a true endless loop,
"leaks" means that the system aborts after a while.


;; ex 1: simple loop

(let loop ((p (cons 1 2)))
  (let ((p2 (cons 1 2)))
    (set-cdr! p p2)
    (loop p2)))

;; ok | ok | ok | ok | ok


;; ex 2: almost the same but not quite ...

(let ((p (cons 1 2)))
  (let loop ((p p))
    (let ((p2 (cons 1 2)))
      (set-cdr! p p2)
      (loop p2))))

;; leaks | ok | ok | ok | ok


;; ex 3: closure check

(let ((p (cons 1 2)))
  (let ((fun (lambda (x) x)))
    (let loop ((p p))
      (let ((p2 (cons 1 2)))
	(set-cdr! p p2)
	(fun 42)
	(loop p2)))))

;; leaks | ok | ok | ok | ok


;; ex 4: continuation frame check

(let ((p1 (cons 1 2)))
  (let loop ((p p1))
    (let ((p2 (cons 1 2)))
      (set-cdr! p p2)
      (loop p2)))
  '42)

;; leaks | leaks | leaks | leaks | ok


Maybe this SRFI should require a Scheme implementation with a certain
safe-for-space property.  Or maybe every implementation of this SRFI
should at least state somehow how it behaves under implementations
with different safe-for-space properties.

Otherwise users will trip into the exact same problems I did when
filtering streams with scsh ...

Cheers

   Matthias

-- 
Matthias Neubauer                                       |
Universität Freiburg, Institut für Informatik           | tel +49 761 203 8060
Georges-Köhler-Allee 79, 79110 Freiburg i. Br., Germany | fax +49 761 203 8052