Equivalent Transformation by Safe Extension of Data Structures (Extended Abstract).pdf
文本预览下载声明
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
akama cimshokudaiacjp
Hokkaido University Kita Nishi Kitaku Sapporo Japan
koke cimshokudaiacjp
Iwate Prefectural University Sugo Takizawa Iwate Japan
mabu softiwatepuacjp
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 dierencelists
However lists and dierencelists 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 dierent
data structures are characterized
By changing this parameter
say from
to we can discuss data structure change for programs
We dene 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
e ciency of programs Declarative programs such as logic and functional
programs may be improved into more e cient ones by using unfolding folding
goal replacement tupling and other transformations
It is well known that e ciency of computation depends on data structures
In case of procedural programming languages it is taken for granted to adopt
better data stru
显示全部