static evaluation of functional programs
Static evaluation underlies essentially all techniques for a priori semantic program manipulation, i.e. those that stop short of fully general execution. Included are such activities as type checking, partial evaluation, and, ultimately, optimized compilation. This paper describes a novel approach to static evaluation of programs in functional languages involving infinite data objects, i.e. those using normal order or lazy evaluation. Its principal features are abstract interpretation on a domain of demand patterns, and a notion of function reversal. The latter associates with each function f a derived function f' mapping demand patterns on f to demand patterns on its formal parameter. This is used for a comprehensive form of strictness analysis, aiding in efficient compilation. This analysis leads to a revised notion of basic block , appropriate as an intermediate representation for a normal order functional language. An implementation of the analysis technique in Prolog is sketched, as well as an effort currently underway to apply the technique to the generation of optimized G-machine code.
evaluation functional programming functional program semantic manipulation generation generation activation partial evaluation compilation paper functional languages data object normalization order feature abstraction interpretation pattern association map formalism analysis efficiency representation implementation prolog code general