Unification based FP Interpreters

Document Type

Article

Publication Date

11-1992

Abstract

A specification is given for the functional programming language FP using an attribute grammar formalism that defines a message passing protocol. Derivations in the grammar specify the complete evaluation of an FP program. The message passing provides a functional type checking capability. To avoid the overhead associated with message passing, the grammar is designed so that each FP primitive function and functional form receives and transmits a single message during the compilation. The language specification provides the framework for the construction of two FP interpreters.An interpreter using an innermost first evaluation strategy, the standard evaluation approach for functional composition, is implemented in Prolog. The rules of the language specification are directly translated into Prolog grammar rules. The message passing and type checking are achieved using the unification of variables in the Prolog grammar rules.The innermost first strategy requires the compilation and evaluation of the subfunctions and functional forms that comprise an FP function. A second interpreter, using the parallel logic programming language PARLOG, was constructed to incorporate eager evaluation into the analysis of an FP function. Eager evaluation is accomplished by transmitting partial results (incompletely constructed lists) throughout the evaluation structure. Whenever the partial results contain sufficient information to determine a value, these are used as input to the subfunctions that comprise the FP function being evaluated. Adding eager evaluation alters the degree of error preservation and requires a modification of the definition of FP.

DOI

10.1145/141018.141042

Find in your library

Off-Campus WSU Users


Share

COinS