Please use this identifier to cite or link to this item:
|Title:||Safe fusion of functional expressions|
|Citation:||Chin, Wei-Ngan (1992). Safe fusion of functional expressions : 11-20. ScholarBank@NUS Repository.|
|Abstract:||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 generalize the deforestation technique to make it applicable to all first-order and higher-order functional programs. Our generalization 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 generalized transformation algorithm as a set of syntax-directed rewrite rules, illustrate it with examples, and provide an outline of its termination proof.|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Oct 19, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.