ICFP

[Matthew Fluet]

> Matthew, are you interested in submitting the dominator-based contification
> algorithm to ICFP?

I think that sounds like a good idea.  Is there anything left to formalize
on the algorithm?  I think the analysis portion is pretty much set, but
would it make sense to formalize the actual transformation?  If we allow
mutual recursion for local functions, I guess it's fairly trivial.  If we
stick to the current CPS IL, it's a little more complicated (=? interesting).


Along those lines, I think I see how to do the actual transformation with
the parent version of the dominator analysis.  It requires a "bottom-up"
approach to performing the contification.  Here's a sketch:

let G' be the dominator tree
Remove the node Root (and associated edges) from G'
Remove any singleton node from G' (these are the Uncalled functions).

while there exists a node l such that all children of the node are leaves
do
  if l = Root, then done.
  let F = {f | f is a child of l}.
  remove all f in F from G'
  compute scc's of F.
  foreach C in scc's of F
   if C does not have a unique head,
    foreach g in C {
     remove g from F;
     foreach call (g, h) {
      if h in F, then remove h from F;
      if h is a node in G', then remove edge (_, h) in G'
     }
    }
   if C does have a unique head h
    nest g in C, g <> h appropriately and remove g from F
  contify all f in F in l
done

The intuition is that nothing needs to be contified in a leaf.  Therefore,
once a node has all leaves as children, each of those functions are ready
to be contified.  When some set of functions can't be contified because of
mutual recursion, immediately make any function they call uncontifiable
(either by kicking the function out of F or removing the incoming edge).
The reason we work in the bottom up manner is to ensure that any functions
contifiable in f are contified before we check wether or not f is part of
an uncontifiable mutually recursive set.

I think this can be extended to work with any "acyclic" safe analysis.
The analysis A will induce some G' such that there is an edge (l, f) if
A(f) = l in Jump U Fun.  Obviously any f such that A(f) = Uncalled can be
immediately removed from the function list.