Parallel Evaluation of Functional Programs

功能程序的并行评估

• 批准号: 01550278
• 负责人: TAKEICHI Masato
• 金额: $ 1.41万
• 依托单位: University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1989
• 资助国家: 日本
• 起止时间: 1989 至 1990
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-01550278/
• 关键词: Functional Program; Parallel Evaluation

We have studied a basic problem in constructing parallel evaluation system which supports functional programming. It is worth noting that recent development in hardware technology makes it practical to implement the evaluator of functional programs. It is true, however, that evaluators of functional languages implemented on conventional hardware run slower than those for procedural languages. In addition to this, it is known that there is a serious problem in evaluating functional programs in a sequential fashion. This is the reason why we study the way to evaluate functional programs in parallel.We discuss parallel functional programming from the programmer's point of view and present novel ideas on implementing functional languages for parallel machines. First of all, we show that simple annotation works effectively to control evaluation order of parallel functional programs. And we extend this idea to make an evaluator for distributed parallel computers such as transputer systems or the Intel Hypercube. We propose a construct to represent recursive environment structures on a processor network, which is an extension to the standard environment structure.Our research concludes with successful experimentation results to support these ideas.

研究了构造支持函数式程序设计的并行求值系统的一个基本问题。值得注意的是，在硬件技术的最新发展使得它实际上实现的功能程序的评估器。然而，在传统硬件上实现的函数式语言的求值器确实比过程式语言的求值器运行得慢。除此之外，已知在以顺序方式评估函数程序中存在严重的问题。这就是为什么我们研究的方法来评估功能的程序在并行。我们讨论并行功能编程从程序员的角度来看，并提出新的想法实现功能的语言并行机。首先，我们证明了简单的注释可以有效地控制并行函数式程序的求值顺序。我们扩展这个想法，使分布式并行计算机，如transputer系统或英特尔超立方体的评估。我们提出了一种在处理器网络上表示递归环境结构的结构，它是对标准环境结构的扩展，我们的研究得到了成功的实验结果来支持这些想法。

项目成果

Kaneko, K.: "Relation between Lambda Hoisting and Fully Lazy Lambda Lifting" 日本ソフトウェア科学会第7回大会論文集. 357-360 (1990)

Kaneko, K.：“Lambda 提升与完全惰性 Lambda 提升之间的关系”日本软件科学学会第七届年会论文集 357-360 (1990)。

武市 正人: "関数プログラミングの実際" コンピュ-タソフトウェア. 8. 3-11 (1991)

Masato Takeichi：《实用函数式编程》计算机软件。8. 3-11 (1991)

Takeichi, M: "Deriving a Functional Knuth-Morris-Pratt Algorithm by Transformation" Journal of Information Processing. Vol. 13. (1991)

Takeichi, M：“通过变换推导函数 Knuth-Morris-Pratt 算法”信息处理杂志。

Kaneko, K: "Relation between Lambda Hoisting and Fully Lazy Lambda Lifting," Proc. JSSST 7th Conf.,. 357-360 (1990)

Kaneko, K：“Lambda 提升与完全惰性 Lambda 提升之间的关系”，Proc。

Masato Takeichi: "Evaluation Partial Order and Synchronization Mechanisms in Parallel Functional Programs" 情報処理学会「フソトウェア基礎論」研究会論文集. 31-4. 1-10 (1989)

Masato Takeichi：“并行功能程序中的评估偏序和同步机制”日本信息处理学会“软件基础”研究组论文集 31-4（1989）。