hoodwink.d enhanced
RSS
2.0
XHTML
1.0

RedHanded

A Callcc w/ Dill Havarti and Ham #

by why in inspect

An old one, but worth repeating if you’ve yet to understand continuations:

Say you’re in the kitchen in front of the refrigerator, thinking about a sandwitch. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwitch, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwitch. But fortunately, there’s a sandwitch on the counter, and all the materials used to make it are gone. So you eat it. :-)

A continuation doesn’t save data. It’s just a closure that closes over the execution stack (and any lexicals associated with it; thus the “I want a sandwitch” thought). If things change between the taking and invoking of the continuation, those things remain changed after invoking.

From the perl6 list.

said on 01 Feb 2005 at 14:27

Ok, I’ve seen these metaphores before (like the guy who chose the wrong road and so on…) and I understood the concept alright, but could you point me to some real code usage that actually wouldn’t be possible without continuations? (I’m not at all advocating against continuations, I just didn’t get it yet…)

said on 01 Feb 2005 at 14:38

You might want to look at Borges or Wee (with calcc).

Or seaside.

said on 01 Feb 2005 at 14:55

Binding.of_caller uses continuations. It works by capturing a continuation, specifying a trace function (via set_trace_func) letting the calling function return and captioning the new context (trace functions get contexts passed on most events and the context for a return is the context that was set before the call to that function) and invoking the continuation with the context as an argument as soon as the return event was triggered—it will find itself back at the beginning of the function, but this time it will have the context and just return it.

So technically a continuation even allows you to return from a method multiple times which is quite funky.

Perhaps you will also find the following code useful when using continuations:

# Creates a continuation in a way that is easier to use than callcc.
# On the initial call this will return the created Continuation and
# the arguments you gave to Continuation.create in an Array. If you
# then issue .call() on the Continuation execution will jump back to
# the point of time where you initially invoked Continuation.create,
# but this time it will return the Continuation and the arguments
# you supplied in an Array.
#
# You can supply a block instead of default arguments which will
# cause that block to be executed once and its result to be returned
# along side the created Continuation, but this form is confusing
# and does only rarely make sense.
#
# Here's a few samples:
#
#   # Count from 0 to 10
#   cc, counter = Continuation.create(0)
#   puts counter
#   cc.call(counter + 1) if counter < 10
#
#   # Implement something similar to Array#inject using Continuations.
#   # For simplicity's sake, this is not fully compatible with the real
#   # inject. Make sure that you understand Array#inject before you try
#   # to understand this.
#   class Array
#     def cc_inject(value = nil)
#       copy = self.clone
#       cc, result, item = Continuation.create(value, nil)
#       next_item = copy.shift
#       if result and item
#         # Aggregate the result using the block.
#         cc.call(yield(result, item), next_item)
#       elsif next_item
#         # item not yet set and Array is not empty:
#         # This means we did not get a value and thus need to use the
#         # first item from the Array before we can start using the
#         # block to aggregate the result.
#         cc.call(next_item, result)
#       end
#
#       return result
#    end
#  end
#  [1,2,3,4,5].cc_inject { |acc, n| acc + n } # => 15
def Continuation.create(*args, &block)
  args = [args] if not args.nil? and not args.is_a? Array # 1.6.8 compatibility
  cc = nil; result = callcc {|c| cc = c; block.call(cc) if block and args.empty?}
  result ||= args
  return *[cc, *result]
end
said on 01 Feb 2005 at 14:59

Consider the AMB function described here.

I’ve got a Ruby version of AMB laying around somewhere if Scheme puts you off.

said on 01 Feb 2005 at 15:26

dema said:

...could you point me to some real code usage that actually wouldn’t be possible without continuations?

Continuations don’t make the impossible possible. A continuation has access to the same resources your methods and blocks have. It’s just a tool.

But continuations allow you to place bookmarks in your code that you can skip between. To a degree, it frees you from the traditional line-by-line chronology of procedural programming.

said on 01 Feb 2005 at 15:54

Well, sometimes they do. ;)

said on 01 Feb 2005 at 21:00

Mikael Brockman’s Continuations on the Web is another great, easily understandable guide to continuations.

said on 02 Feb 2005 at 02:49

could you point me to some real code usage that actually wouldn’t be possible without continuations?

I used continuations in RHDL to implement concurrent process statements. It would have taken a lot more code to do it otherwise, but it was probably possible. You can find a link to RHDL on the RAA .

BTW : You should really see the movie “Run Lola Run” to help understand continuations. ;-)

said on 02 Feb 2005 at 06:55

There’s a page about continuations and callcc on the Merd site, but although it gives several examples, I haven’t got it yet. I think the difficulties I have involve holding in my head: what is saved and restored from the closure; what is going on with the return value; the fact the jump backwards can come from anywhere, and seems unstructured; and what parts will not be changed with the “jump back in time”—which is really only the other part to what is saved.

I think they would be really useful in creating a search program performing like prolog. But I haven’t quite figured out how to do that.

said on 02 Feb 2005 at 13:24

One of my favourite ‘practical’ uses of Ruby continuations is in the Generator library, to convert an internal iterator to an external one.

said on 02 Feb 2005 at 16:51

funny, i just wrote about generator.rb and how it works: Iterators, Generators and Continuations in Ruby

said on 02 Feb 2005 at 17:57

Sam: No you are great!!!

hgs:

Only these things are saved by callcc: the complete stack, and the instruction pointer. In other words, it saves all local variables, and it saves the code position where it was executing—nothing more.

So if you want to shield something from callcc: put it on the heap. Or, in other words: make it an instance variable.

You could say that callcc ignores your objects. It only cares about methods. Which makes sense, ‘cause it’s stolen from a language without objects.

And what goes on with the return value? The tricky thing here, is: there are two ways to return from the block you pass to callcc.

One way is to just not call the continuation, and let the block return like any other block.

The other way is to call the continuation. That’s a shortcut. It lets you hop right out with the return value.

And you can take the shortcut with you. You can save it away in a hash table, or whatever—and then return from the callcc, even hours after you’ve left the method that called callcc! Even after you’ve returned from that very same block a hundred times before! And that’s what’s so cool about callcc.

said on 10 Feb 2005 at 11:20

Mikael, You talk about it saving local variables and using instance vars to shield from callcc. Are you saying that when you do continuation.call() then @x will not be restored to its old value, but y, if local, will. That seems to be what is happening, but “[I’m] not thinking fourth-dimensionally!!”, to quote Back to the Future :-)

Thank you.

said on 11 Feb 2005 at 05:18

Dug around a bit last night and found Continuations Made Simple and Illustrated which together with Jim Weirich’s Kata Two Worked (continued)—Continuation Passing Style make it somewhat clearer what is happening. These, to summarize, suggest that continuations really get their power when there is more than one, and if you consider them as “when I finished some function, I’d like to continue from here”. Now, you could normally do that with a return and a case statement, except that continuations allow you to end up in a different method than that from which you started, and allow you to do so from anywhere. The Generator discussed in links above relies on this.

The Continuation Passing Style examples show how continuing or backtracking based on success or failure are facilitated by this technique. You pass two continuations to the function, and it will pick which one to call depending on the result. So instead of relying on a return from a method call to get you back to where you were in the call stack, you can get anywhere you have previously specified, even if that place is not on the current call stack. Thus, instead of being stuck on one branch of a tree of calls, which is what a stack would provide, you can jump to another branch.

The genre of time-travel films is filled with cases where the protagonist can take some information about consequences back with them. The ability to pass parameters to acontinuation.call(x) allow this to be done simply. However going back with a continuation only “undoes” the call stack and restores local variables, so this is different from undoing the whole of the future, as time-travel ought to permit. So it is better to think of it as searching a different area, aware that the previous search did take place. A continuation is a closure with a call stack (I think, it is certainly descibed as a superset of a closure): it carries where it was as well as what it contains.

Hope this helps someone.

said on 16 Sep 2005 at 07:44

Why does this Ruby program print “Calling our Continue object” twice?

def cc
    puts "do A" 
    callcc {|cont| 
   puts "taking a break" 
        return cont
    }
    puts "do B" 
end
puts "Calling cc, getting a Continue object" 
cont = cc()
puts "Calling our Continue object" 
cont.call if cont
puts "end of work\n" 


output:


Calling cc, getting a Continue object
do A
taking a break
Calling our Continue object
do B
Calling our Continue object
end of work

Comments are closed for this entry.