Possibilities and limitations of call-by-need space improvement
Possibilities and limitations of call-by-need space improvement
复制标题
按需呼叫空间改进的可能性和局限性
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
David Sands
中科院分区：
文献类型：
--
作者：
Jörgen Gustavsson;David Sands
看起来无害的程序转换可以很容易地改变惰性函数程序的空间复杂性。空间改进理论旨在描述那些保证不使任何规划的渐近空间复杂度恶化的局部规划变换。作者之前的工作介绍了空间改进关系，并证明了一些简单的局部变换律确实是空间改进。本文寻求以下问题的答案：改进关系中是否存在有趣的程序转换，如果存在，如何建立它们？我们证明了渐近空间改进关系在语义上表现不好，但强空间改进理论具有一个不动点归纳定理，该定理允许推导递归定义的改进性质。在这个工具的帮助下，我们通过考虑一系列经典的项目改造来探索空间改善的景观。
Innocent-looking program transformations can easily change the space complexity of lazy functional programs. The theory of space improvement seeks to characterize those local program transformations which are guaranteed never to worsen asymptotic space complexity of any program. Previous work by the authors introduced the space improvement relation and showed that a number of simple local transformation laws are indeed space improvements. This paper seeks an answer to the following questions: is the improvement relation inhabited by interesting program transformations, and, if so, how might they be established? We show that the asymptotic space improvement relation is semantically badly behaved, but that the theory of strong space improvement possesses a fixed-point induction theorem which permits the derivation of improvement properties for recursive definitions. With the help of this tool we explore the landscape of space improvement by considering a range of classical program transformation.