A Method for Implementing Functional Programming Languages

点击翻译按钮获取中文摘要

The purpose of this project is to propose a new method for implementing functional programming languages and to study algorithmic aspects of this method from the complexity viewpoint.In 1979 D.A. Turner applied combinators to a certain practical system for evaluating lambda expressions. His system is not quite efficient in the sense that the space complexity of output is at least quadratic in n, where n is the length of input expressions. In 1985 the author presented a new method for representing combinator graphs in O(n log n) space.In this project another new efficient method called BC-chains is proposed, which requires only linear space in n even in the worst case. Provided the normal order reduction is assumed, this leads to a new reduction algorithm, which can be proved to run as efficiently as the standard normal order reduction algorithm even in the worst case. In fact, in some computing experiment, this algorithm is reported to run at least as fast as the standard one in the average sense as well.For translating input expressions to combinator graphs, a new algorithm is devised, which runs in O(n log n) time in the worst case. The space complexity of this algorithm can be proved to be O(n log n).The report of this project describes the details of all the algorithms mentioned above, which constitute the complete set of basic algorithms for translation as well as for execution. The report also contains some theoretical results on the complexity of related problems.