A Method for Implementing Functional Programming Languages

这个项目的目的是提出一种实现函数式编程语言的新方法，并从复杂性的角度研究这种方法的算法方面。1979年，d.a。Turner将组合子应用到某个实际系统中，用于计算lambda表达式。他的系统不是很有效，因为输出的空间复杂度在n中至少是二次的，其中n是输入表达式的长度。1985年，作者提出了一种在O（n log n）空间中表示组合子图的新方法。在这个项目中，我们提出了另一种新的高效方法bc -链，它只需要n中的线性空间，即使在最坏的情况下。如果假设正常阶约简，就会产生一种新的约简算法，即使在最坏的情况下，该算法也能像标准的正常阶约简算法一样高效地运行。事实上，在一些计算实验中，据报道该算法在平均意义上至少和标准算法一样快。为了将输入表达式转换为组合子图，设计了一种新的算法，该算法在最坏的情况下运行时间为O（n log n）。可以证明该算法的空间复杂度为O（n log n）。本项目报告详细介绍了上述所有算法，构成了完整的翻译和执行基本算法集。报告还包含了一些有关问题复杂性的理论成果。

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.