[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