[plt-scheme] safe for space (

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Sat Feb 9 15:24:10 EST 2008

As of, MzScheme with the 3m memory manager (the default) and
with the JIT enabled (x86, x86_64, and PPC) is safe for space (modulo

"Safe for space" means that the asymptotic space complexity of a
program is consistent with a substitution model of evaluation. It's a
level of specification beyond "proper handling of tail recursion",
which essentially bounds only the size of the continuation.

So far, I know of only one realistic example in which a lack of space
safety created trouble: lazy streams. (See PR 8963.) But it may have
caused more trouble that was never identified as a safe-for-space
problem, and safe-for-space is obviously a property that you'd like to
have for reasoning about your program. The example below illustrates
the difference between and older versions.

Why now? Making MzScheme safe for space wasn't really practical until
we had precise GC (to make any sort of memory guarantees) and a
native-code compiler (since the interpreter is too tangled with the C
stack). With those pieces now well established in MzScheme, I finally
spent the couple of days needed to adjust the compiler.



#lang scheme

(define init-mem-use (current-memory-use))

(define (linear n in-l)
  (let ([l (cons (make-string 10000) 
                 ;; Copy all the old strings:
                 (map string-copy in-l))])
    (if (zero? n)
          (printf "~s\n" (- (current-memory-use) 
          (length l))
        ;; At this point, a safe-for-space
        ;; implementation has dropped the reference
        ;; to `in-l'. Old MzScheme retains a reference
        ;; to `in-l' until `+' is called.
        (+ 1 (linear (sub1 n) l)))))

;; If you change 50 to 100, the memory use should
;; double. In the old MzScheme, it goes up x4.
(linear 50 null)

Posted on the users mailing list.