Safe fusion of functional expressions
Safe fusion of functional expressions
复制标题
功能表达式的安全融合
DOI：
10.1145/141471.141494
复制
发表时间：
1992
影响因子：
0.5
通讯作者：
W. Chin
中科院分区：
文献类型：
--
作者：
W. Chin
大型功能程序通常是通过将每个大任务分解为较小的任务来构建的，这些任务可以通过更简单的功能执行。已经发现，这种开发程序的层次结构风格可提高程序员的生产率，因为较小的功能更容易构建和重复使用。但是，以这种方式编写的程序往往效率较低。可以创建不必要的中间数据结构。可能需要更多功能调用。
为了减少这种绩效惩罚，沃德勒提出了一种称为森林砍伐的转换算法，该算法可以自动将某些组成的表达式融合在一起，以消除中间树状的数据结构。但是，他的技术仅适用于一阶表达式的子集。
本文将概括森林砍伐技术，以使其适用于所有一阶和高级功能程序。通过采用模型进行安全融合，我们将每个功能视为生产者及其参数作为消费者，使我们的概括成为可能。通过此模型，提出了静态程序属性，以将生产者和消费者分类为安全或不安全。此分类用于识别可以安全融合/消除的子题材。我们将广义转换算法作为一组语法指导的重写规则，用示例说明并提供其终止证明的概述。
Large functional programs are often constructed by decomposing each big task into smaller tasks which can be performed by simpler functions. This hierarchical style of developing programs has been found to improve programmers' productivity because smaller functions are easier to construct and reuse. However, programs written in this way tend to be less efficient. Unnecessary intermediate data structures may be created. More function invocations may be required.
To reduce such performance penalties, Wadler proposed a transformation algorithm, called deforestation, which could automatically fuse certain composed expressions together in order to eliminate intermediate tree-like data structures. However, his technique is only applicable to a subset of first-order expressions.
This paper will generalise the deforestation technique to make it applicable to all first-order and higher-order functional programs. Our generalisation is made possible by the adoption of a model for safe fusion which views each function as a producer and its parameters as consumers. Through this model, static program properties are proposed to classify producers and consumers as either safe or unsafe. This classification is used to identify sub-terms that can be safely fused/eliminated. We present the generalised transformation algorithm as a set of syntax-directed rewrite rules, illustrate it with examples, and provide an outline of its termination proof.