<div dir="ltr">On Tue, Sep 23, 2008 at 2:25 PM, Joel J. Adamson <<a href="mailto:adamsonj@email.unc.edu">adamsonj@email.unc.edu</a>> <<a href="mailto:adamsonj@email.unc.edu">adamsonj@email.unc.edu</a>> wrote:<br>
>>>>>> "DR" == David Rush <<a href="mailto:kumoyuki@gmail.com">kumoyuki@gmail.com</a>> writes:<br>>    DR> The thing to remember about call/cc is that it potentially can<br>>    DR> duplicate large portions of the stack. 9 times out of 10 you<br>
>    DR> will be better off writing your code to using explicit CPS,<br>>    DR> anyway. (Less filling! Tastes Great!)<br>><br>> Hmmm...okay, then I'm getting more mixed messages about call/cc.  I know<br>
> I've read in more than one place that "any program written in CPS can be<br>> rewritten more efficiently using call-with-current-continuation..."  <br><br>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.<br>
<br>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.<br>
<br>The reasons for explicitly passing your own continuation functions are manifold:<br><br>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<br>
<br>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<br><br>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<br>
<br>4) it's good practice in developing your awareness of tail-call sites - which helps to keep your recursions clean<br><br>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:<br>
<br><span class="Apple-style-span" style="font-family: 'courier new', monospace;">(define (assoc-k tag a-list k-success k-fail)<br>  (if (null? a-list)<br>      (k-fail tag)</span><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">      (let* ((head (car a-list))</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">             (rest (cdr a-list))</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">             (head-tag (car head)))</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">         (if (equal? tag head-tag)</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">             (k-success head)</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">             (assoc-k tag rest k-success k-fail)</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">             ))))<br>
</span><br>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.</div>
<div><br>>    DR> Have you traced this program to see where it's allocating<br>>    DR> heavily?<br>><br>> What's the best way to do that?</div><div><br></div><div>Errr...print out data structures at key points of the program and see if they're bigger than you expect?</div>
<div><br></div><div>> Thanks a heap ;)<br></div><div><br></div><div>Don't make me Pun-ish you.</div><div><br></div><div>david rush</div><div>-- <br></div><div>GPG Public key at <a href="http://cyber-rush.org/drr/gpg-public-key.txt">http://cyber-rush.org/drr/gpg-public-key.txt</a><br>
<br></div></div>