<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META http-equiv=Content-Type content="text/html; charset=utf-8"> <META content="MSHTML 6.00.6000.16788" name=GENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=#ffffff> <DIV><FONT face="Courier New" size=2>My explanation of ((call/cc call/cc) (call/cc call/cc)).</FONT></DIV> <DIV> </DIV> <DIV><FONT face="Courier New" size=2>Read this in CPS (continuation passing style)<BR>For this purpose think in terms of meta-procedures EXEC and APPLY.</FONT></DIV> <DIV> </DIV> <DIV><FONT face="Courier New" size=2>(EXEC code cont) ; cont=continuation.<BR>Executes the code and passes the result to the cont.</FONT></DIV> <DIV> </DIV> <DIV><FONT face="Courier New" size=2>(APPLY op rand cont) ; op is procedure/operator, rand is argument/operand.<BR>Calls the op with the rand for its arg and passes the result to the cont.</FONT></DIV> <DIV> </DIV> <DIV><FONT face="Courier New" size=2>Notice that (APPLY call/cc A B) --> (APPLY A B B).<BR>Write ((call/cc call/cc) (call/cc call/cc)) as ((cc1 cc2) (cc3 cc4)).<BR>Let `finish' be the continuation of the top form,<BR>for instance the PLRE of a REPL (read-eval-print-loop),<BR>but as we shall see the finish is never reached,<BR>hence `finish' is irrelevant.<BR>Notation: #i=x introduces #i# as short for x.</FONT></DIV> <DIV> </DIV> <DIV><FONT face="Courier New" size=2>First a <FONT color=#ff0000>WRONG</FONT> explanation:</FONT></DIV> <DIV><FONT face="Courier New" size=2></FONT> </DIV> <DIV><FONT face="Courier New" size=2>(EXEC ((cc1 cc2) (cc3 cc4)) finish) =<BR>(EXEC (cc1 cc2) #0=(λ (op) (EXEC (cc3 cc4) (λ (rand) (APPLY op rand finish)))))<BR>(APPLY cc2 #0# #0#)<BR>(APPLY #0# #0# #0#) =<BR>(EXEC (cc3 cc4) #1=(λ (rand) (APPLY #0# rand finish)))<BR>(APPLY cc4 #1# #1#)<BR>(APPLY #1# #1# #1#)<BR>(APPLY #0# #1# finish)<BR>(EXEC (cc3 cc4) #2=(λ (rand) (APPLY #1# rand finish))) =<BR>(APPLY cc4 #2# #2#)<BR>(APPLY #2# #2# #2#)<BR>(APPLY #1# #2# finish)<BR>(APPLY #0# #2# finish)<BR>(EXEC (cc3 cc4) #3=(λ (rand) (APPLY #2# finish))) =<BR>(APPLY cc4 #3# #3#)<BR>(APPLY #2# #3# finish)<BR>(APPLY #1# #3# finish)<BR>(APPLY #0# #3# finish)<BR>(EXEC (cc3 cc4) #4=(λ (rand) (APPLY #3# rand finish))) =<BR>(APPLY cc4 #4# #4#)<BR>(APPLY #4# #4# #4#)<BR>(APPLY #3# #4# finish)<BR>(APPLY #2# #4# finish)<BR>(APPLY #1# #4# finish)<BR>(APPLY #0# #4# finish)<BR>(EXEC (cc3 cc4) #5=(λ (rand) (APPLY #4# rand finish))) =<BR>etc.</FONT></DIV> <DIV> </DIV> <DIV><FONT face="Courier New" size=2>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:</FONT></DIV> <DIV> </DIV> <DIV><FONT face="Courier New" size=2>(EXEC ((cc1 cc2) (cc3 cc4)) finish) =<BR>(EXEC (cc1 cc2) #0=(λ (op) (EXEC (cc3 cc4) (λ (rand) (APPLY op rand finish)))))<BR>(APPLY cc2 #0# #0#)<BR>(APPLY #0# #0# #0#)<BR>#999=(EXEC (cc3 cc4) #1=(λ (rand) (APPLY #0# rand finish)))<BR>(APPLY cc4 #1# #1#)<BR>(APPLY #1# #1# #1#)<BR>(APPLY #0# #1# finish)<BR>(EXEC (cc3 cc4) #2=(λ (newrand) (APPLY #1# newrand finish))) =<BR>(EXEC (cc3 cc4)<BR> (λ (newrand)<BR>  (APPLY (λ (rand) (APPLY #0# rand finish)) newrand finish))) =<BR>; <FONT color=#800000><STRONG>Contract the continuation</STRONG></FONT>.</FONT></DIV> <DIV><FONT face="Courier New" size=2>(EXEC (cc3 cc4) #1=(λ (rand) (APPLY #0# rand finish))) =<BR>(EXEC (cc3 cc4) #1#) = #999# ; Space bound loop!</FONT></DIV> <DIV> </DIV> <DIV><FONT face="Courier New" size=2>Is this a correct interpretation? It strikes me that DrScheme's Debug shows the <FONT color=#ff0000>WRONG </FONT>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?</FONT></DIV> <DIV> </DIV> <DIV><FONT face="Courier New" size=2>Jos</FONT></DIV> <DIV> </DIV> <DIV><FONT face="Courier New" size=2></FONT> </DIV> <BLOCKQUOTE style="PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px"> <DIV style="FONT: 10pt arial">----- Original Message ----- </DIV> <DIV style="BACKGROUND: #e4e4e4; FONT: 10pt arial; font-color: black"><B>From:</B> <A title=sk@cs.brown.edu href="mailto:sk@cs.brown.edu">Shriram Krishnamurthi</A> </DIV> <DIV style="FONT: 10pt arial"><B>To:</B> <A title=rafkind@cs.utah.edu href="mailto:rafkind@cs.utah.edu">rafkind@cs.utah.edu</A> </DIV> <DIV style="FONT: 10pt arial"><B>Cc:</B> <A title=plt-scheme@list.cs.brown.edu href="mailto:plt-scheme@list.cs.brown.edu">Scheme PLT</A> </DIV> <DIV style="FONT: 10pt arial"><B>Sent:</B> Saturday, January 17, 2009 8:38 PM</DIV> <DIV style="FONT: 10pt arial"><B>Subject:</B> Re: [plt-scheme] call/cc puzzle</DIV> <DIV><BR></DIV> <P>Just remember that putting a use of call/cc in a context changes the meaning of that use...</P> <P> <BLOCKQUOTE>snip</BLOCKQUOTE></BLOCKQUOTE></BODY></HTML>