New Generation Computing, 20(2002)27-51
Ohmsha, Ltd. and Springer-Verlag

Binding-time Analysis for Both Static and Dynamic Expressions

Kenichi ASAI
Department of Information Science, Faculty of Science,
The University of Tokyo
7-3-1 Hongo Bunkyo-ku 113-0033 Japan
"Information and Human Activity," PRESTO, JST
asai@is.s.u-tokyo.ac.jp

Received 18 June 2001
Revised manuscript received 19 July 2001

Abstract

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.

Keywords: Partial Evaluation, Offline Specialization, Binding-Time Analysis, Type System, Functional Languages.

[Back]