CWS paper
Stephen Weeks
MLton@sourcelight.com
Wed, 6 Dec 2000 11:54:11 -0800 (PST)
> I was looking at contify.fun and was curious about the extra analysis
> regarding sccs. It's because of cases like the following:
>
> fun f () = ... g () ...
> fun g () = ... f () ...
> fun h () = ... f () ... g () ...
>
> in which the continuation based analysis would mark f and g as
> contifiable, but the CPS IL doesn't support mutually recursive local
> functions, so either only contify one of them or contify neither.
> (correct?)
Almost. It contifies *both* or neither. Here's the relevant snippet of the
mail I sent to John.
> A final point. You may have noticed that MLton's CPS IL doesn't directly
> support mutually recursive continuation declaration. This could cause problems
> when contifying a block of functions that share the same continuation, as
> determined by the continuation based analysis. However, because continuation
> declarations can be nested, it is possible to define mutually recursive
> continuations by nesting one within another. This approach was sufficient to
> contify all of the functions in all of the benchmarks detected as contifiable
> the continuation based analysis.
For your particular example above, it would contify neither, because f and g are
both called from outside (unless it could contify h within f or g as well).
> The call based analysis never needed to worry about this, because the
> single non-tail use in another function marked precisely where the
> contified function needed to go; although you might have "cascades" of
> contifiable functions, there was a clear dependency.
Right.
> Looking back at Steve's original message comparing the call based and
> continuation based analysis, I have the impression that a case like above,
> while possible, never appeared in the benchmarks.
Right. I.E. it never happened that the analysis determined that a function was
called with a single continuation but the function could not be contified due to
the lack of directly mutual recursive functions. However, there were a few
cases where the scc stuff was necessary in order to nest mutually recursive
functions.