[plt-scheme] call/cc puzzle

My explanation of ((call/cc call/cc) (call/cc call/cc)).

Read this in CPS (continuation passing style)
For this purpose think in terms of meta-procedures EXEC and APPLY.

(EXEC code cont) ; cont=continuation.
Executes the code and passes the result to the cont.

(APPLY op rand cont) ; op is procedure/operator, rand is argument/operand.
Calls the op with the rand for its arg and passes the result to the cont.

Notice that (APPLY call/cc A B) --> (APPLY A B B).
Write ((call/cc call/cc) (call/cc call/cc)) as ((cc1 cc2) (cc3 cc4)).
Let `finish' be the continuation of the top form,
for instance the PLRE of a REPL (read-eval-print-loop),
but as we shall see the finish is never reached,
hence `finish' is irrelevant.
Notation: #i=x introduces #i# as short for x.

First a WRONG explanation:

(EXEC ((cc1 cc2) (cc3 cc4)) finish) =
(EXEC (cc1 cc2) #0=(λ (op) (EXEC (cc3 cc4) (λ (rand) (APPLY op rand finish)))))
(APPLY cc2 #0# #0#)
(APPLY #0# #0# #0#) =
(EXEC (cc3 cc4) #1=(λ (rand) (APPLY #0# rand finish)))
(APPLY cc4 #1# #1#)
(APPLY #1# #1# #1#)
(APPLY #0# #1# finish)
(EXEC (cc3 cc4) #2=(λ (rand) (APPLY #1# rand finish))) =
(APPLY cc4 #2# #2#)
(APPLY #2# #2# #2#)
(APPLY #1# #2# finish)
(APPLY #0# #2# finish)
(EXEC (cc3 cc4) #3=(λ (rand) (APPLY #2# finish))) =
(APPLY cc4 #3# #3#)
(APPLY #2# #3# finish)
(APPLY #1# #3# finish)
(APPLY #0# #3# finish)
(EXEC (cc3 cc4) #4=(λ (rand) (APPLY #3# rand finish))) =
(APPLY cc4 #4# #4#)
(APPLY #4# #4# #4#)
(APPLY #3# #4# finish)
(APPLY #2# #4# finish)
(APPLY #1# #4# finish)
(APPLY #0# #4# finish)
(EXEC (cc3 cc4) #5=(λ (rand) (APPLY #4# rand finish))) =
etc.

This suggests that ((call/cc call/cc) (call/cc call/cc)) would not run in bound space. However, it does, as on my small system can easily be verified by letting it run for some minutes. Apparently Scheme's designers and implementors ar more clever than shown above. I try again:

(EXEC ((cc1 cc2) (cc3 cc4)) finish) =
(EXEC (cc1 cc2) #0=(λ (op) (EXEC (cc3 cc4) (λ (rand) (APPLY op rand finish)))))
(APPLY cc2 #0# #0#)
(APPLY #0# #0# #0#)
#999=(EXEC (cc3 cc4) #1=(λ (rand) (APPLY #0# rand finish)))
(APPLY cc4 #1# #1#)
(APPLY #1# #1# #1#)
(APPLY #0# #1# finish)
(EXEC (cc3 cc4) #2=(λ (newrand) (APPLY #1# newrand finish))) =
(EXEC (cc3 cc4)
 (λ (newrand)
  (APPLY (λ (rand) (APPLY #0# rand finish)) newrand finish))) =
; Contract the continuation.
(EXEC (cc3 cc4) #1=(λ (rand) (APPLY #0# rand finish))) =
(EXEC (cc3 cc4) #1#) = #999# ; Space bound loop!

Is this a correct interpretation? It strikes me that DrScheme's Debug shows the WRONG behaviour. That may be due to the fact that debug has to extend each continuation such as to move its arrow and to display results and therefore cannot collaps the continuations. Correct?

Jos


  ----- Original Message ----- 
  From: Shriram Krishnamurthi 
  To: rafkind at cs.utah.edu 
  Cc: Scheme PLT 
  Sent: Saturday, January 17, 2009 8:38 PM
  Subject: Re: [plt-scheme] call/cc puzzle


  Just remember that putting a use of call/cc in a context changes the meaning of that use...


    snip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090119/f8a9d89a/attachment.html>