[bitc-dev] Polymorphism through polyinstantiation -- take2

[Swaroop Sridhar]

The take-1 algorithm had a few drawbacks:

i) It forms the bigAST from all the definitions known in the entire 
program, rather than doing it `on-demand' one-output point at a time. In 
this sense, it is one-shot-compiler friendly and may not scale to an 
interactive interpreter.

ii) It mutates the big-AST in place, and is thus not "functional" in 
style -- something that is much desired keeping the next version of the 
compiler in mind.

iii) It needs a post-instantiation dependency analysis and re-ordering 
as the definitions are not emitted on a demand-driven basis.

To ameliorate these problems, a new algorithm is proposed:

The idea is to divide the compiler into:

frontend: parser, type-inference
midend: the (poly)instantiator
backend: closure-conversion, SSA transformation, C-emission.

The front end is done one unit of compilation at a time, or, in an 
interactive environment, one top level form at a time. The front end 
pulls in other dependent interfaces and also processes them. After the 
frontend is completely done, the midend comes into play. It receives a 
set of FQNs that must be instantiated in this pass. It starts out from 
these as roots and constructs the unified-AST (which is a smaller 
version of the big-AST) on an on-demand basis. Then, it passes this 
unified-AST to the backend, which can again process this as a single 
unit of compilataion.

Below, I give the algorithm for specialization used in our new scheme. 
In this scheme, there is no todo-list -- the algorithm recursively acts 
on itself. However, it maintains a work-list to ensure that recursive 
definitions do not cause the instantiator to go into an infinite loop. 
As is practice, it takes in a definition and the desired type.

1) See if the desired identifier has been instantiated for the desired
    type by searching the target (unified-AST) environment. If found,
    just return.

2) Examine the worklist whether we are in the process of instantiating
    the current definition, if so emit a declaration, and exit.

3) Copy the incoming AST -- always copy the definition (rather than the
    declaration) if one exists.

4) Clamp the type of this AST to the desired type by introducing a
    qualifier.

    ex, to instantiate id to (fn (bool) bool), we write:
    (define id:(fn (bool) bool) (lambda (x) x))

5) Mangle the name of the identifier being defined depending on the
    desired type, and also change any recursive usages of the same name
    within the current definition.

   ex: (define id#fn_4bool_4bool:(fn (bool) bool) (lambda (x) x))

6) R&T the new definition in the *original* environment -- that was
    saved as a pointer in its AST -- so that the types in the body of the
    definition get clamped aiding further instantiation. After successful
    R&T, throw away any changes to the environment.

7) Add the mangled name (id#fn_bool_bool) onto the worklist.

8) Recursively instantiate the body

9) After the current form has been completely instantiated, add it to
    the target (big-AST) environment, and R&T there.

10) Remove the current definition from the worklist, exit.

In the next mail, I will post a small problem and then a solution to it 
(obviously, take-3).

Swaroop.