文档详情

Equivalent Transformation by Safe Extension of Data Structures (Extended Abstract).pdf

发布:2017-04-09约1.97万字共9页下载文档
文本预览下载声明
Equivalent Transformation by Safe Extension of Data Structures Extended Abstract Kiyoshi Akama and Hidekatsu Koike and Hiroshi Mabuchi Hokkaido University Kita  Nishi  Kitaku Sapporo  Japan akamacimshokudaiacjp  Hokkaido University Kita  Nishi  Kitaku Sapporo  Japan kokecimshokudaiacjp  Iwate Prefectural University  Sugo Takizawa Iwate  Japan mabusoftiwatepuacjp Abstract Equivalent transformation has been proposed as a method ology for providing programs with appropriate data structures For in stance logic programs which use lists are transformed into equivalent programs that use di erencelists However lists and di erencelists are both usual terms and in this sense no new data structures are introduced in the transformation Since logic programming has xed data structure called terms no one can develop theoretical foundations for introducing new data structures into programs as far as only logic programs are dis cussed In this paper we develop a theoretical foundation of equivalent transformation that introduces new data structures We introduce a pa rameter for data structures by which many languages with di erent data structures are characterized By changing this parameter say from to  we can discuss data structure change for programs We de ne a concept of safe extension of data structures and prove that the meaning of a program on a data structure is preserved by safe extension of the data structure Introduction Equivalent transformation is one of the most important methods for improving eciency of programs  Declarative programs such as logic and functional programs may be improved into more ecient ones by using unfolding folding goal replacement tupling and other transformations It is well known that eciency of computation depends on data structures In case of procedural programming languages it is taken for granted to adopt better data stru
显示全部
相似文档