contification patent

[Stephen Weeks]

Sorry, full text of the patent is at 
	http://164.195.100.11/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1='5881291'.WKU.&OS=PN/5881291&RS=PN/5881291

I finished reading it.  Here's my notes.

--------------------------------------------------------------------------------
Patent 5881291
System for conversion of loop functions in continuation-passing style.

The paper describes contification on a scheme-like CPS IL with lambdas and
explicit continuations.  It defines a predicate "is-a-loop-p" that takes a set
of lambdas (NCLEs = Non-Continuation Lambda Expressiosn) and a continuation
(variable or lambda) and determines if all lambdas in the set always return to
that continuation.  This is a simple forall condition over the set.  is-a-loop-p 
extends the set of lambdas if necessary (and possible) to find a set that shares 
the continuation.

Next, the paper defines a transformation, "convert-loop", that takes a set of
lambdas that share a continuation and moves them to just after the continuation
is defined.  It also rewrites all calls to those lambdas into tail calls,
essentially turning them into continuations.

Finally, the paper gives a couple of simple examples, factorial and examples
where a function's continuation is the join point of an if-test.

The main thing missing from the paper is a practical way to find the sets of
lambdas sharing a continuation.  It just gives the predicates.
--------------------------------------------------------------------------------

So, it's definitely doing contification.  Their is-a-loop-p predicate seems to
accept sets found by both call-based and continuation based approaches (and the
dominator approach as well).  Like I noted, they don't give any kind of
algorithm (dominators, static analysis, whatever) for finding the sets of
lambdas to contify.  I think Reppy had something to add with his
continuation-based analysis.  I think we have something to add with
dominator-based analysis.

As to patent infringement, I don't see a lot in their work beyond what was in
Kelsey's March 95 paper (and an even earlier NEC tech report, IIRC) and ideas
that were present in his compilers from way before, I would guess.  The only
thing I can possibly think of is the idea of moving a group of functions to just 
after the continuation is defined, but Kelsey may have done that as well.
Anyways, I'm not a lawyer, but I find it hard to believe the patent would stand
a challenge given the prior existing work.  I notice that they did not cite any
Kelsey work after 1986, so they probably weren't aware of it.