Re: good pictures vs. good stories (was: Re: CPS in Parrot)

[Robby Findler <address@hidden>]

One of the problems you're seeing is that ((call/cc call/cc) (call/cc
call/cc)) loops forever but without coming back to the same algebraic
expression, when using left-to-right order of evaluation. Under right
to left, it does repeat.

I built a tool for visualizing such things (it is an add on to
DrScheme). For this language, where order of evaluation is right to
left:

  e = (e e) | (abort e) | x | v
  v = call/cc | number | (lambda (x) e)
  c = (e c) | (c v) | hole

with these reductions:

  c[(abort e)] --> e
  c[(call/cc v)] --> c[(v (lambda (x) (abort c[x])))]
  c[((lambda (x) e) v)] --> c[...subtitute v for x in e...]

You get this reduction sequence:

  http://www.cs.uchicago.edu/~robby/callcccallcccallcccallcc.gif

The first nt (e) is the expression language and the second (v) is the
values. The third is the definition of evaluation contexts -- you can
think of it as specifying the order of evaluation (you can evaluate
inside the right part of an application with anything on the left, but
you can only evaluate the left side when you've finished the right hand
side) and it also represents continuations (ie, everything "else" to do
in a computation will always be a c -- the hole is what you passsed to
the continuation).

The first reduction throws away the context. The second reduction
duplicates the context, and packages it up as a function to be passed
around. The is the essence of call/cc. The final reduction is just
procedure application (using substitution).

Hopefully that helps a little bit.

Robby