本文对我们近几年来在递归程序等价变换方面之一系列研究工作做了分类总结,所提出的一些新变换模式和技术进一步丰富了人们对横向程序变换技术的认识。 软件自动化是计算机科学的前沿课题之一,其主要研究途径有:演绎综合途径、程序变换途径、实例推广途径和过程化途径,其中尤以程序变换途径得到研究工作者更多的关注。程序变换大体上可分为横向变换和 纵向变换两大类,所谓横向变换是指在相似的抽象级上将一个语言成分转化为另一个与之等价但效率更高的语言成分。 横向程序变换的研究可追溯到1966年Cooper首次提出的Cooper变换,而英国爱丁堡大学的Burstall和Darlington的研究以及他们所研制的ZAP系统是目前这方面最有代表性的工作。 本文对横向程序变换作了较深入的探讨,其中有相当多一部分递归程序等价变换模式是笔者及其同事们近几年来陆续提出的。 我们将采用函数式递归程序模型作为讨论的基础(参阅[12]之第七章),并把递归程序变换模式分成若干类型加以阐述,限于篇幅,我们只简要叙述各类变换的输入模式、输出模式、可用性条件和应用示例,有关变换的正确性证明(采用结构归纳法)将不在此列出(感兴趣的读者可参阅有关文献)。