A powerful strategy for deriving efficient programs by transformation
A powerful strategy for deriving efficient programs by transformation
复制标题
通过转型获得高效计划的强大策略
DOI：
10.1145/800055.802044
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
A. Pettorossi
中科院分区：
文献类型：
--
作者：
A. Pettorossi
我们提出了一种通过从递归方程规范转换来得出有效的迭代程序的方法。
在第一阶段，我们在[BUD77，PET77]中应用“ Tupling策略”，并在程序转换领域暗中使用了该策略。出现在程序规范中。
在第二阶段，我们应用已知的方法将线性递归转换为迭代（避免使用堆栈）[WAS73]，并在递归模式和流程图模式之间进行等效结果。
通过各种示例，我们展示了转换过程中上述阶段的破坏如何允许推导有效的迭代算法。
这些例子包括E. Dijkstra教授和其他作者的挑战。
We present a method for deriving efficient iterative programs by transformation from recursive equation specifications. It consists of two phases: i) the transformation of general recursive programs into linear recursive ones, and ii) the transformation of linear recursive programs into iterative ones.
In the first phase we apply the “tupling strategy” studied in [BUD77, Pet77], and implicitly used by other authors in the area of program transformation. That strategy enables us to introduce linear recursive functions, instead of the general recursive ones occurring in program specifications.
In the second phase we apply known methods for transforming linear recursion into iteration (avoiding the use of stacks) [WaS73], and equivalence results between recursive schemas and flowchart schemas.
Through various examples we show how the breaking of the transformation process into the above mentioned phases allows the derivation of efficient iterative algorithms.
Those examples include challenges by Prof. E. Dijkstra and other authors. Through our method we were also able to improve some recent results for eliminating redundant calls in recursive programs [Coh83].