Constraint-based binding-time analysis has been pioneered by Henglein [19]. His main contribution is the efficient linear-time implementation of type reconstruction. His algorithm is the basis of our algorithm. His work in turn has been influenced by Gomard's work on partial type inference [16]. Bondorf and Jørgensen took up Henglein's ideas on constraint normalization to build a binding-time analysis for Similix [7]. Their system is closest to ours. However, whereas our analysis is systematically derived from a two-level type system, theirs is constructed by inspection of the specializer. Our analysis is more powerful as it deals with variadic functions, enables functional arguments and results of operators, and can be used to guide the choice of representations in the specializer.
In our treatment of eval we assume that the argument is an ordinary base type value and leave the connection to the type of the result unconstrained: It can be whatever the context expects it to be. There are also type systems to ensure the type correctness of computed code [28]. These approaches could be used to provide more precise types for eval.
Consel and Danvy [9] deal with a problem similar to the representation problem. They propose to split a program into three parts prior to specialization proper: completely static combinators, completely dynamic combinators, and the part which is actually subject to specialization. Our type system can also be used to identify completely static parts and it can also remove interpretive overhead in other places.
Birkedal and Welinder [2] treat partial evaluation for standard ML. Their binding-time analysis is also monovariant and constraint-based. Their additions to Henglein's framework concern mainly pattern matching. Another interesting point of their work is their proposed treatment of exceptions. However, their proposal is not implemented and it appears that our treatment of call/cc subsumes their treatment of exceptions.
Heintze's set-based analysis [18] is amenable to the analysis of higher-order languages in the presence of side-effects and control features. Its variant for binding-time analysis (by Malmkjaer, Heintze, and Danvy [25]) can therefore also be employed to analyze programs using call/cc. However, it is not clear how their specializer would handle call/cc.
Recently, more liberal type-based approaches to binding-time analysis and partial evaluation have been developed. Our analysis is monovariant and performs binding-time coercions only on base types. The work of Dussart, Mossin, and Henglein [20,15] pursues polymorphic binding-time type systems where functions can be used at more than one binding time. Danvy, Malmkjær, and Palsberg [13,14] consider binding-time coercions at higher types, product types, and sum types. Danvy [12] even introduces a type-driven scheme which achieves specialization only through the use of binding-time coercions.
Danvy [11] considers the relation between partial evaluation and reflection. He states that partial evaluation collapses two levels in a tower of interpreters and thus removes reflective procedures mediating between the collapsed levels.