Binding-Time Analysis for Both Static and Dynamic Expressions
This paper presents a specializer and a binding-time analyzer for
a functional language where expressions are allowed to be used as both
static and dynamic.
With both static and dynamic expressions, data structures can be
statically accessed while they are residualized at the same time.
Previously, such data structures were treated as completely dynamic,
which prevented their components from being accessed statically.
The technique presented in this paper effectively allows data
structures to be lifted which was prohibited in the conventional
partial evaluators.
The binding-time analysis is formalized as a type system and the
solution is obtained by solving constraints generated by the type
system.
We prove the correctness of the constraint solving algorithm and
show that the algorithm runs efficiently in almost linear time.