[gambit-list] Help With Memory

David Rush kumoyuki at gmail.com
Wed Sep 24 10:30:58 EDT 2008


On Tue, Sep 23, 2008 at 2:25 PM, Joel J. Adamson <adamsonj at email.unc.edu> <
adamsonj at email.unc.edu> wrote:
>>>>>> "DR" == David Rush <kumoyuki at gmail.com> writes:
>    DR> The thing to remember about call/cc is that it potentially can
>    DR> duplicate large portions of the stack. 9 times out of 10 you
>    DR> will be better off writing your code to using explicit CPS,
>    DR> anyway. (Less filling! Tastes Great!)
>
> Hmmm...okay, then I'm getting more mixed messages about call/cc.  I know
> I've read in more than one place that "any program written in CPS can be
> rewritten more efficiently using call-with-current-continuation..."

Well, that statement requires a bit of context. If you're talking about
transforming your whole program by hand into CPS form and then using an
arbitrary continuation to escape from an inner loop, then call/cc is *way*
more efficient in terms of your own productivity. I'd be very surprised if
there is any implementation where using call/cc is as CPU-efficient as
explicitly passing continuation functions which are called from
tail-position in your code - which is what I think I remember seeing. And if
you capture a continuation via call/cc and then recurse you start getting
into the allocation issues.

Now IIRC, Gambit is actually pretty clever in it's call/cc stack management
strategy, but because of the C calling convention there are still spots
where you can cause chunks of stack to get copied. Marc has published a
number of papers on this topic and I'm quite sure I am doing a ton of
violence to his work.

The reasons for explicitly passing your own continuation functions are
manifold:

1) they help ensure the typological correctness of your program. Yes this is
Lisp and all, but it does mean that really smart compilers (e.g. Stalin) can
better optimize your code

2) it will reduce the number of errors you make because you will start
treating different cases differently instead of trying to cook up spurious
data hacks to conflate cases into a single return type

3) you will never have to worry about call-with-values again because you
have explicit control over the arity of all the continuations that matter

4) it's good practice in developing your awareness of tail-call sites -
which helps to keep your recursions clean

My personal poster-child case for explicit CPS is the assoc function, which
returns a pair? if the key is found in the a-list and #f if it is not. My
standard prelude now includes a super-sized version of this:

(define (assoc-k tag a-list k-success k-fail)
  (if (null? a-list)
      (k-fail tag)      (let* ((head (car a-list))
             (rest (cdr a-list))
             (head-tag (car head)))
         (if (equal? tag head-tag)
             (k-success head)
             (assoc-k tag rest k-success k-fail)
             ))))

which is great for about a zillion reasons (which are left as an exercise
for the reader). But please note: This is not a fully CPS-transformed
program; however it is a program where you pass in the explicit
continuations of the function call.

>    DR> Have you traced this program to see where it's allocating
>    DR> heavily?
>
> What's the best way to do that?

Errr...print out data structures at key points of the program and see if
they're bigger than you expect?

> Thanks a heap ;)

Don't make me Pun-ish you.

david rush
-- 
GPG Public key at http://cyber-rush.org/drr/gpg-public-key.txt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20080924/8c302b7d/attachment.htm>


More information about the Gambit-list mailing list