[racket] A primitive more fundamental than a continuation?

On Dec 1, 2012, at 7:28 PM, Galler wrote:

> I've been thinking about a reified continuation:
> 
> The documentation (See Guide s10.3) says "A continuation is a value that
> encapsulates a piece of an expression context"


Someone should submit a doc bug report to the Guile people. The 'expression' should be replaced (or supplemented) with 'evaluation'. 



> I'm coming to the belief that the continuation is actually  "an ordered
> collection of computation-branches, with facilities provided to manipulate
> one member of the collection"
> 
> For example:
> 
> (+ (+ 1 2) (let/cc k 3) (+ 2 3))
> 
> which yields 11
> 
> If we were to capture  k in a module level variable *k*, we can substitute 4
> for the result of the third ordinal branch (counting from the left)
> 
> (*k* 4)
> 
> and get a value of 12, etc. Indeed, we can substitute any value for the
> third ordinal branch.
> 
> So my question is:
> 
> What's so special about the third branch?
> 
> Is there any reason I couldn't change the fourth branch, or second, or even
> first?
> 
> Put another way, why doesn't the reified continuation k expose the
> individual branches?


Some of your thinking is correct. Some is incorrect. 

Let's calculate with *some* fixed order (left to right, for another order say right to left or middle out you'd get similar results): 

(define *k* #f) (+ (+ 1 2) (let/cc k (save-k-in-*k*-and-return k 3)) (+ 2 3))
|--> 
(define *k* #f) (+ 3 (let/cc k (save-k-in-*k*-and-return k 3)) (+ 2 3))
|--> 
;; Now you have *k* bound to a procedure reflection of the evaluation context of (let/cc k ...). 
(define *k* (\ (x) (abort (+ 3 x (+ 2 3)))) (+ 3 3 (+ 2 3))
|--> 
(define *k* (\ (x) (abort (+ 3 x (+ 2 3)))) (+ 3 3 5)
|--> 
(define *k* (\ (x) (abort (+ 3 x (+ 2 3)))) 11 

Okay, let's play with *k* now. Well, as it is there are about four operators on procedures that you can use in our world: 
 -- application: (*k* ?)
 -- (procedure? *k*)
 -- (arity-includes *k*)
 -- (object-name *k*)
And that's it. So when we made the language design choice to reify evaluation contexts around (let/cc ...) as procedures, we determined what we could do. 

Now imagine that we lied. We don't really reify evaluation contexts as [continuation] procedures but as [continuation] objects with additional operations for inspecting and possibly mutating them. One could imagine that continuations are organized as a [abstract] sequence of [abstract] frames: 

  (+ 2 3)
  3
  +  

The language could then provide operations such as set-frame : Continuation Natural Value -> Continuation (or an imperative version thereof) and with this operation you could do this: 

 (set-frame *k* 2 -) 

and that would produce 

  (+ 2 3)
  3
  -

Before you do so, you might run (if (eq? (object-name (get-frame *k* 2)) '+) ... ...) to make sure you are really replacing the addition operator. 

What you canNOT do even in this world is visit the past and perform a different computation than (+ 1 2). The best you can do is change frame 2 so that it is 99 instead of 3 but that's not changing the computation. [Imagine the computation performed I/O or a set!.]

This idea shows up in Felleisen, Wand, Friedman, Duba, LISP 1988, "Abstract Continuations." 

MIT Scheme treats continuations as lists of frames, and SICM exploits this ability to perform mathematical operations on functions. In this context you can, for example, set-car! (cddr *k*) and then reflect *k* (and hope for the best). I admire people who program in this way but I am not sure I want to live in this world myself. 

-- Matthias