Equivalent Transformation by Safe Extension of Data Structures
Equivalent Transformation by Safe Extension of Data Structures
复制标题
通过数据结构的安全扩展进行等价转换
DOI：
10.1007/3-540-45575-2_15
复制
发表时间：
2001
影响因子：
--
通讯作者：
H. Mabuchi
中科院分区：
文献类型：
--
作者：
K. Akama;H. Koike;H. Mabuchi
等价变换是为程序提供合适的数据结构的一种方法。例如，使用列表的逻辑程序被转换成使用差分列表的等价程序。然而，列表和差异列表都是常用的术语，在这个意义上，在转换中没有引入新的数据结构。由于逻辑程序设计有固定的数据结构，称为术语，没有人可以发展理论基础，以引入新的数据结构到程序中，只要只讨论逻辑程序。在本文中，我们开发了一个理论基础的等效转换，引入新的数据结构。我们引入了一个数据结构的参数G，用它来描述具有不同数据结构的语言。通过改变这个参数（比如从G1到G2），我们可以讨论程序的数据结构变化。定义了数据结构的安全扩充概念，证明了数据结构的安全扩充能保持程序在数据结构上的意义。
Equivalent transformation has been proposed as a methodology for providing programs with appropriate data structures. For instance, logic programs which use lists are transformed into equivalent programs that use difference-lists. However lists and difference-lists are both usual terms and in this sense no new data structures are introduced in the transformation. Since logic programming has fixed data structure called terms, no one can develop theoretical foundations for introducing new data structures into programs as far as only logic programs are discussed. In this paper we develop a theoretical foundation of equivalent transformation that introduces new data structures. We introduce a parameter G for data structures, by which many languages with different data structures are characterized. By changing this parameter (say from G1 to G2) we can discuss data structure change for programs. We define a concept ofsaf e extension ofdata structures, and prove that the meaning ofa program on a data structure is preserved by safe extension of the data structure.