[plt-scheme] call/cc puzzle

Neither did I expect ((call/cc call/cc) (call/cc call/cc)) to run in bound 
space, but I had it run on my 1.8 Ghz, 1Mb RAM single processor machine for 
over 15 minutes without noticing any substantial increase of memory usage. 
That's why I looked for an explanation of space bound behaviour.
Jos

----- Original Message ----- 
From: "Robby Findler" <robby at eecs.northwestern.edu>
To: "Jos Koot" <jos.koot at telefonica.net>
Cc: "Shriram Krishnamurthi" <sk at cs.brown.edu>; <rafkind at cs.utah.edu>; 
"Scheme PLT" <plt-scheme at list.cs.brown.edu>
Sent: Monday, January 19, 2009 8:22 PM
Subject: Re: [plt-scheme] call/cc puzzle


As far as I am able to tell, when you evaluate left-to-right,
((call/cc call/cc) (call/cc call/cc)) should be a non-tail-recursive
loop (right-to-left requires constant space). Perhaps Matthew has done
something fancy to mzscheme to be able to optimize something somehow
to make it tail recursive, or perhaps it is a bug.

Robby

On Mon, Jan 19, 2009 at 10:03 AM, Jos Koot <jos.koot at telefonica.net> wrote:
> 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
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>