On Tue, Sep 23, 2008 at 2:25 PM, Joel J. Adamson <adamsonj@email.unc.edu> <adamsonj@email.unc.edu> wrote:
>>>>>> "DR" == David Rush <kumoyuki@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