[plt-scheme] Re: Puzzle about amb and memory

From: Mark Engelberg (mark.engelberg at gmail.com)
Date: Tue Apr 1 16:36:51 EDT 2008

Yeah, I meant that it looks to me like test-2 creates 70 continuations
that are all active at one time vs. 7.  Both versions create
considerably more continuations over the lifetime of the program.

test-1 is like each amb is a tree with 10 children (i.e., one
continuation as a backtrack position for 10 possible failures)
test-2 is like each amb is a binary tree with a depth of 10, one child
is a leaf, and the other child leading to the further tree (i.e., 10
continuations, each continuation handling one possible failure point).

In each version, you're nesting 7 times, thus my 7 vs. 70 claim.


On Tue, Apr 1, 2008 at 10:22 AM, Danny Yoo <dyoo at cs.wpi.edu> wrote:
> > I think the crux of the problem is that your test-1 creates 7
>  > continuations, and test-2 creates 70 continuations.  Apparently, 70
>  > continuations is enough to cause PLT Scheme to segfault, but 7 isn't.
>  Hi Mark,
>  But just creating continuations isn't going to exhaust memory, unless
>  those continuations can't be garbage collected.  For example:
>  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>  #lang scheme/base
>  ;; infinite loop through call/cc
>  (define (inf)
>    (define top #f)
>    (let/cc k
>      (set! top k))
>    (let/cc k2
>      (top)))
>  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>  runs perfectly well in bounded space even though it's busily creating
>  k2 continuations like mad.
>  My assumptions right now are that either the recursion either isn't tail,
>  or the continuations aren't getting collected.  I've pored at the amb
>  source code a bit, but I don't see yet anything wrong with regards to tail
>  calls.

Posted on the users mailing list.