The purpose of this dissertation is to demonstrate that higher-order functional programs can be transformed into zero-order intensional ones in a semantics preserving way. As there exists a straightforward execution model for the resulting intensional programs, the practical outcome of our research is a promising, well-defined implementation technique for functional languages. On the foundational side, the goal of our study is to bring new insights and a better understanding of the nature of functional programming.;The starting point of our research is the work of A. Yaghi (Yag84) and W. Wadge (Wad91), who were the first to define transformation algorithms from functional to intensional languages. More specifically, Yaghi studied the first-order subset of functional languages, while Wadge extended Yaghi's technique to apply to a significant class of higher-order functional programs. The main shortcoming of both these works is that the transformations they provide are semi-formal and consequently they lack a correctness proof. In particular, although the algorithm in (Yag84) is relatively easy to understand intuitively, the one in (Wad91) is much more complex, making in this way imperative the need for a precise formulation.;We start by revising, formalizing and giving a correctness proof of Yaghi's transformation algorithm for first-order functional programs. The formal definition we give is based on the idea that if two expressions in the source program are identical, then they are assigned identical intensional expressions during the translation. The correctness proof of the algorithm is established by showing that a function call in the extensional program has the same meaning as the intensional expression that results from its translation.;We then consider the translation of higher-order functional programs into zero-order intensional ones. We demonstrate that although Wadge's algorithm is in the right direction, it does not always preserve the semantics of the source programs. To overcome this deficiency, we define a richer target intensional language and an extended algorithm which compiles the source functional programs into zero-order programs of this new language. We develop the synchronic denotational semantics of the intensional language, based on which we give the correctness proof of the extended transformation algorithm.;The transformation algorithm developed in this dissertation can be used as the basis for new implementation strategies for functional languages. We propose two such strategies, one hashing-based and the other stack-based, and discuss their relative merits. We conclude by demonstrating that the transformation algorithm we propose offers a solution to the problem of implementing higher-order functions on dataflow machines.
展开▼
