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.

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

项目成果

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）。