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. Kenichi Asai, Ph.D.: He is a research associate at the Department of Computer Science, Faculty of Science, the University of Tokyo. He obtained his bachelors degree, masters degree, and doctor of Science from the University of Tokyo in 1990, 1992, and 1997, respectively. His research interests are in Programming Languages in general, in Partial Evaluation and Reflection in particular. He is a member of ACM, IPSJ, and JSSST.