contification paper

[Stephen Weeks]

> Looking at the outline, I think we'll be good on length without bringing
> in handlers.  And, they are completely transparent to the analyses, so I
> don't think they add much in this context.

Agreed.

> On the other hand, we really should be a little more precise about cycles.
> For example, we could have the following:
> 
> fun fm () = ...
> fun f () = ... K (g) ...
> fun g () = ... f () ...
> 
> and A(f) = g, A(g) = K is safe, although not minimal, and not "acyclic" in
> the sense that the transformation can't be performed.  I'll think a little
> more about this and see if I can't hammer out something more precise.

How about we just use Reach in the definition of safety.  I.E.
	* if not(Reach(f)) then A(f) = Uncalled

After all, reachability is a trivial concept and any sane analysis would do this 
(okok I know an old implementation of the contifier didn't :-).

If we do this, we can get rid of acyclicity in the definition of safety,
although we may need to prove it later anyways since we need it for the
transformation.

> > Maybe type correctness of resulting program.
> 
> I thought about this, but this will mean complicating the CPS IL a little.
> On the other hand, it probably won't be too hard; a function contified in
> another function doesn't change types at all; a function contified at a
> continuation changes it's return type, but corresponding calls also
> change.

It hadn't even occurred to me that we could present the CPS IL without the type
system.  But I see it doesn't really matter for this optimization.  However, in
the interest of staying closer to MLton and the fact that typed ILs are popular,
I think I'd like to present the IL as typed, at least in the grammar.  We can
mostly elide the types later.

> > Maybe the right thing to compare is the five analyses
> > 
> > 	none	call	cont	call+cont	dom
> > 
> > I'm wavering on including call+cont.
> 
> I agree.  The results there aren't much different than anywhere else.

So we go with none, call, cont, dom and either present run times as a ratio
relative to none or relative to dom, I'm not sure which.

> > Is this for the dom based on A*/parent, right?  Should we instead report the
> > dom based on ancestor, with a note that it's actually weaker due to the mutual
> > recursion problem?

> Yes, it is based on A*/parent.  The fact that the transformation accepts
> any A* safe analysis doesn't affect the transformation that's done when
> the dominator analysis uses ancestor (i.e., we won't be able to contify
> those two functions in logic).  It's a trivial change to run the parent
> analysis (I should just extend the contifyStrategy control) and get the
> numbers there.

You mean "change to run the ancestor analysis", right?  I assume so.  Anyways,
the run times should be based on ancestor since that conforms to the safety
definition in the paper.

Hmmm.  I just thought of another possibility.  What if we use the A* safety
definition, the parent analysis, and your latest transformation, but still
pretend we have mutual recursion.  Maybe that's not too complicated.

> I'll make one other comment.  When run with the call analysis, the new
> transformation is not identical to the old transformation.  Essentially,
> this is another nesting issue: 
..
> Essentially, the old transformation just found the one outside call and
> dropped the definition in the closest set of definitions.  The new
> transformation know that g is to be contified in f, so it's added before
> the original local functions of f.  There's no difference in runtimes
> between the old and new transformations, and virtually no difference in
> code size.

Good.  So we can stick with the one transformation that works for any safe
analysis.  I think it's ok to present a slightly historically inaccurate call
analysis, possibly with an incomprehensibly vague note about nesting.