Chui’s counterpoint

An old post, but a good one (via Etymon):

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. :-)

Field’s medallist winner Terence Tao explains how parallel universes and quantum mechanics can be possible by way of Tomb Raider.

In trying to come up with a classical conceptual model in which to capture these non-classical phenomena, we eventually hit upon using the idea of using computer games as an analogy. The exact choice of game is not terribly important, but let us pick Tomb Raider - a popular game from about ten years ago (back when I had the leisure to play these things), in which the heroine, Lara Croft, explores various tombs and dungeons, solving puzzles and dodging traps, in order to achieve some objective. It is quite common for Lara to die in the game, for instance by failing to evade one of the traps. (I should warn that this analogy will be rather violent on certain computer-generated characters.)

Via Will Farr Via Planet Scheme

A colleague introduced me to the amb operator. The best reference is Teach Yourself Scheme in Fixnum days.

(define-macro amb
  (lambda alts...
    `(let ((+prev-amb-fail amb-fail))
       (call/cc
        (lambda (+sk)

          ,@(map (lambda (alt)
                   `(call/cc
                     (lambda (+fk)
                       (set! amb-fail
                         (lambda ()
                           (set! amb-fail +prev-amb-fail)
                           (+fk 'fail)))
                       (+sk ,alt))))
alts...)

          (+prev-amb-fail))))))

In BASIC,
(amb 10 20 30)
roughly translates to

100 REM ------- AMB 1 2 3 -----------
102 PREV_FAIL = SAVE_PREV_GOTO
105 ON ERROR GOTO 115
110 RETURN 10
115 ON ERROR GOTO 125
120 RETURN 20
125 ON ERROR GOTO 13
130 RETURN 30
135 ON ERROR GOTO PREV_FAIL
140 RAISE ERROR
200 REM ------ AMB ----------------
210 RAISE ERROR

Paul Graham’s take on Lisp without the nail clippings is RTML, the templating language which powers Yahoo Store.

My-Name ()
TITLE "My Name Is"
BODY
  TEXT "Hello, my name is "
  LINEBREAK
  IMAGE source RENDER text @name
                      text-color red
                      font-size 20

Heard of call with current continuation and never grokked it? Here is a worked introduction to call/cc in BASIC.

10  REM ---- MAIN -------
20  PRINT "MAIN 1"
30  GOSUB 110
40 PRINT "MAIN 2"
100 REM --- FOOA ------
110 PRINT " FOOA 1"
120 GOSUB 220
130 PRINT " FOOA 2"
140 RETURN
200 REM --- FOOB ------
210 PRINT "  FOOB 1"
220 PRINT "  FOOB 2"
230 RETURN

When you run the program, you get this.

MAIN 1
 FOOA 1
  FOOB 1
  FOOB 2
 FOOA 2
MAIN 2

Alright, let’s consider what’s going on here

Main calls FOOA, which in turn calls FOOB

+-------+
| MAIN 1|
+-------+
    |
    |   +----------+
    +-->|  FOOA 1  |
        +----------+
             |
             |         +-----------+
             +-------->|  FooB 1   |
                       +-----------+

and then FOOB returns to FOOA, which in turn returns to MAIN

+-------+
| MAIN 2|
+-------+
    ^
    |   +----------+
    +-->|  FOOA  2 |
        +----------+
             ^
             |         +-----------+
             +---------|  FooB 2   |
                       +-----------+

If we draw a vertical timeline, this is what happens

+-------+
| MAIN 1|
+-------+
    |
    |   +----------+
    +-->|  FOOA 1  |
        +----------+
             |
             |         +-----------+
             +-------->|  FooB 1   |
                       +-----------+
                            |
                            |
                            v
                       +-----------+
             +---------|  FooB 2   |
             |         +-----------+
             v
        +----------+
    +---|  FOOA  2 |
    |   +----------+
    v
+-------+
| MAIN 2|
+-------+

Take another look at the vertical timeline. The entire program could actually have been constructed entirely of GOTOs. GOSUB and RETURN is actually a special case of GOTO. Conversely, we can also say GOTO is a special case of GOSUB/RETURN.

Here is a possible implementation of GOTO as a special case of GOSUB.

(code copied from the top so that you don't have to scroll)
10  REM ---- MAIN -------
20  PRINT "MAIN 1"
30  GOSUB 110
40  PRINT "MAIN 2"
100 REM --- FOOA ------
110 PRINT " FOOA 1"
120 GOSUB 220
130 PRINT " FOOA 2"
140 RETURN

When line 30 calls line 110, line 30 could pass an additional argument with a value of ‘40′ (which is the next line to be executed after FOOA returns). When the BASIC interpreter encounters a RETURN statement at line 140, it GOSUB to line 40.

(pregnant pause here)

OK, now your head is spinning. You might ask: GOSUB without returns? Wouldn’t that blow the stack? Or … argue that Chui is cheating, because BASIC doesn’t have local variables in functions. Just bear with me one more moment.

In structured programming, say if you could pass in ‘40′ as well as a pointer to the list of local variables in the current function. Then when FOOA returns it can call GOSUB 40, passing in the list of local variables passed in earlier from MAIN. Of course, this may mean that the local variables live on the heap instead of a stack, and you need alternate garbage collection algorithms. (For instance, when refcount of the variable list goes back down to 0, then free the memory.)

OK, now that we have given form to a concept, what are we going to call this ‘40′ and the ‘list-of-local-variables’ ? Answer: current continuation. Call-with-current-continuation converts the remaining code in the calling function into a closure (which is a function that has preinitialized local variables), and passes this closure to the function it is calling.

(pregnant pause)

With explicit access to the a continuation, you can optionally choose not to call it, or even to call it again and again. It is counterintuitive, but being able to call continuations can actually make the program logic more transparent in cooperative multitasking. But that’s for another day.

What about performance? Calling functions can be expensive, isn’t it? Remember that GOSUB and GOTO are equivalent? Guy Steele had shown in a paper titled “Lambda the Ultimate GOTO”, that there is a standard series of steps for a compiler to transform function-calling into equivalent GOTOs.

Questions? comments?