My mind and continuations, callcc seen graphically

After writing about the relative difficulties of callcc and 2ch, I kept pondering about the nature of the problem with callcc, or more precisely about the process used to solve problems using continuations. By now, most (well, many) people know about the CPS transformation, and callcc as a means to get hold of the implicit continuation (“the rest of the computation”), but we often have a hard time using continuations: there’s a large gap between analytical comprehension (understanding code which uses callcc) and the ability to actually synthesize a solution to a problem using callcc.

So I tried to analyze how I solved the original problem, deconstructing the process I didn’t consciously think about since I had already internalized it. When trying to solve this, I’m essentially trying to derive the static representation of the program (code) from the desired dynamic behavior. I know the solution is going to look like

        def open_block(fn)
A1        fh = _open(fn)
A2        yield fh
A3        _close(fh)
        end
        def open(fn)
B1        # magic
B2        open_block(fn) do |fh|
B3          # magic
          end
B4        # magic
        end
        def close(fh)
C1        # magic
        end
APP1    fh = open("foo")
APP2    whatever(fh)
APP3    close(fh)
APP4    puts "DONE"

and I want to find how to complete that code so that at run-time it behaves as follows

      code                        "natural" continuation
APP1    fh = open("foo")          B1
  B1        # magic               B2
  B2        open_block(fn)        A1
    A1        fh = _open(fn)      A2
    A2        yield fh            B3
      B3          # magic         A3
--------------------------------------   1st non-local jump
APP2    whatever(fh)              APP3
APP3    close(fh)                 C1
  C1        # magic               APP4
--------------------------------------   2nd non-local jump
    A3        _close(fh)          B4
    B4        # magic             APP2
--------------------------------------   3rd non-local jump
APP4    puts "DONE"

This can be represented graphically as

The diagram tells us a few things. First of all, it makes apparent that we’re going to need 3 callcc blocks, corresponding to the non-local jumps observed in the desired execution trace. Secondly, it indicates that the 3rd and last non-local jump is a “forward jump” that will require the continuation to be given by the second jump. If we forgot the last jump, we’d go back to whatever(fh), and then close(fh), looping forever.

This notation is very rough, and two major questions remain:

• is anything like that happening at some level in my mind at all? If not, how am I actually solving this, and can I systematize it?
• is it useful at all, i.e. can I find another callcc challenge whose solution I cannot just “see” right away, but easily solvable using a diagram like the above or an explicit listing of the desired execution?

I will try to apply this method to a different problem and refine it to match my mental process, assuming it can be methodized, or just make it more powerful, otherwise.

benevolent censor edit: reindented the code

I just used your diagram to make this:

def _open(fh)
  puts "In _open (A1)"
end
def _close(fh)
  puts "In _close (A3)"
end
def open_block(fn)
  fh = _open(fn)
  puts "A2"
  callcc do |c| 
    fn[:preclosecc] = c
    yield fh
  end
  _close(fh)
end
def open(fn)
  callcc do |c| fn[:postopencc] = c
    puts "B1"
    puts "B2"
    open_block(fn) do |fh|
      puts "B3"
      fn[:postopencc].call
    end
    puts "B4"
    fn[:postclosecc].call
  end
  fn
end
def close(fh)
  callcc do |c| fh[:postclosecc] = c
    puts "C1"
    fh[:preclosecc].call
  end
end
def whatever(fh)
end
puts  "APP1"
fh = open({ :name => "foo" })
puts "APP2"
whatever(fh)
puts "APP3"
close(fh)
puts "DONE APP4"

I have been enjoying doing callcc exercises lately with some friends. Cheers, –Rudi ([email protected])

mfp 2005-11-23 (Wed) 11:34:01

That’s interesting, in that it feels systematic, and flow control is explicitly attached to the filename+filehandler. On second thought, you’re cheating a bit because you changed #open_block 🙂 But the callcc block corresponding to :preclosecc can be moved into the block passed to #open_block (in #open); then this becomes equivalent to my solution. But it still looks nicer, if only because you’re labelling all non-local jumps.