The Concatenate Vanishes
The Concatenate Vanishes
复制标题
连接消失
DOI：
--
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
P. Wadler
中科院分区：
文献类型：
--
作者：
P. Wadler
本文介绍了一个简单的转换，它可以消除程序中对concatenate（或“append”）运算符的许多调用。变换的一般形式是众所周知的，其中一个例子，变换反向函数，是一个经典。然而，据我所知，这种风格的转换以前没有系统化的方式在这里完成。该变换适合于编译器，并改善了一些程序的渐近时间复杂度从二次到线性。有一个语法测试可以确定转换何时成功消除连接操作。第1节描述了转换。第2节提供了示例。第3节描述了转型的好处。第四节介绍相关工作。第5节结束。
This note presents a trivial transformation that can eliminate many calls of the concatenate (or “append”) operator from a program. The general form of the transformation is well known, and one of the examples, transforming the reverse function, is a classic. However, so far as I am aware, this style of transformation has not previously been systematised in the way done here. The transformation is suitable for incorporation in a compiler, and improves the asymptotic time complexity of some programs from quadratic to linear. There is a syntactic test that determines when the transformation will succeed in eliminating a concatenate operation. Section 1 describes the transformation. Section 2 presents examples. Section 3 characterises the transformation’s benefits. Section 4 describes related work. Section 5 concludes.