[plt-scheme] call/cc puzzle

Indeed, grow produces the noise slower and slower. The explanation I labeled 
wrong because I did not see the growth, must be right then. Indeed, it does 
explain why the noise (rate of growth) slows down as more cycles are made. 
The time between subsequent calls to noisy-call/cc must increase linearily 
with the total number of times it has been called. This means that:

rate of growing = (/ constant (sqrt time)),
(time counter=n) = (* constant n n),
where time is measured from starting procedure grow.
I measured the times (within noisy-call/cc) and the results are in excellent 
agreement with my expectations.

Thanks Henk for the nice puzzle and Robby and Matthew for your expert 
clarification.
Jos

----- Original Message ----- 
From: "Matthew Flatt" <mflatt at cs.utah.edu>
To: "Jos Koot" <jos.koot at telefonica.net>
Cc: "Robby Findler" <robby at eecs.northwestern.edu>;
<plt-scheme at list.cs.brown.edu>
Sent: Tuesday, January 20, 2009 3:58 PM
Subject: Re: [plt-scheme] call/cc puzzle


> There's no fancy optimization of this example in PLT Scheme. It runs in
> unbounded space --- but *very* slowly.
>
> Compare the rate of output when running `grow' versus `stable' in
>
> (define counter 0)
>
> (define (noisy-call/cc f)
>   (set! counter (+ counter 1))
>   (cond
>    [(zero? (modulo counter 100))
>     (display counter) (newline)])
>   (call/cc f))
>
> (define (grow)
>   (let ([rator (call/cc call/cc)])
>     (rator
>      (call/cc noisy-call/cc))))
>
> (define (stable)
>   (let ([rand (call/cc call/cc)])
>     ((call/cc noisy-call/cc) rand)))
>
> I've used `let' in both variants to force a particular order of
> operation (and also used `cond' instead of `when', etc.) so you can try
> `grow' versus `stable' in implementations other than PLT Scheme. I saw
> the same qualitative difference between the two across all the
> implementations I tried.
>
>
> At Tue, 20 Jan 2009 14:47:14 +0100, "Jos Koot" wrote:
>> 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
>> >
>> >
>>
>> _________________________________________________
>>   For list-related administrative tasks:
>>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme