re CWS paper

[Stephen Weeks]

> Note,  in  some  sense the example you sent me: a tail-position if where each
> branch is a tail-call to f (these being the only calls to f) seems more  like
> a place where the problem is that the CPS conversion didn't perform some kind
> of common-sub-expression elimination.  I.e., convert
> 
>     if ???
>        then g (AAA)
>        else g (BBB)
> to
>     g (if ???
>           then AAA
>           else BBB)

This particular example could be optimized away by the CPS converter, but in
general, I don't see why an optimization will be able to eliminate multiple
calls to g that happen to have the same continuation.

> I still don't see any case where call-based will do it but continuation-based
> won't.  Looking at your example:
> 
>     fun f () = let ... in loop () end
>     fun loop () = let ... in loop () end
>     fun g () = ...  K1 (f ()) ...  K2 (f ()) ...
> 
> it  is  just  that  the  call-based version is willing to duplicate f when it
> makes the two new continuations that are K1 o f and K2 of f? 

No.  Call based brings loop inside f.  It does not duplicate f.  Continuation
based does nothing on this example.

> From this point of
> view, the call-based analysis  approximates  the  continuation-based  one  by
> noting  that only one external call and all internal calls being tail => only
> one continuation.

You have a different notion of continuation based than the one in Reppy's paper
or currently in MLton.  The example above shows a case that continuation based
analysis in MLton misses.

> Looking at the final example you gave (where neither analysis will contify)
> 
>     fun f () = ... g () ... g () ...
>     fun g () = ... f () ...
>     fun h () = ... K1 (f ()) ... K2 (f ()) ...
> 
> are the two calls to g in f tail calls?  

Yes.

> If so then clearly the continuation-
> based  analysis WILL contify g in f. 

No.  It will not.  The analysis will determine that the set of continuations
that g is called with is {K1,K2}.

> Note, the continuation that you look at
> is JUST the local part of the continuation, not the full continuation.  I.e.,
> in any procedure all continuations end with a return or a tail-call.  (I have
> to think about ones that end in raise going outside.)  I guess that there  is
> a  phase  ordering  problem,  but  it seems to me that the continuation-based
> analysis clearly says that g can be contified in f.  Who cares what the stack
> part of the continuation is?

I think I understand what you are getting at when you say the "local part of the
continuation".  What if, for the purposes of analysis, you think of every tail
call within f as a call with a special continuation that is the "return
continuation" for f.  Then the continuation based analysis will determine that g
has a single continuation (return inside f) and will be able to contify g.  That
sounds nice.  It gets the first example as well.  Hmmm.  Cool.  I think that
does subsume the call based analysis.