How to Make Programs from Problem Descriptions in the Equivalent Transformation Paradigm
Takahiko Ishikawa*, Kiyoshi Akama**, and Hiroshi Mabuchi***
*Division of System and Information Engineering, Hokkaido University, Kita-11 Nishi-5 Kita-ku Sapporo, 060-0811 Japan
**Information Instiative Center, Hokkaido University, Kita-11 Nishi-5 Kita-ku Sapporo, 060-0811 Japan
***Faculty of Software and Information Science, Iwate Prefectural University, 152-52 Sugo Takizawa, 020-0173 Japan
In the computation model of equivalent transformation (ET), problems are expressed by some declarative descriptions. Programs, which consist of equivalent transformation rules (ETRs), are made from the declarative descriptions, and applied to questions to solve them. The ET model can achieve various and efficient ways of problem-solving mainly due to the expressive power and priorities of ETRs. In this paper, we investigate and demonstrate, by solving a sample problem, how to make programs from problem descriptions in the ET paradigm. We introduce basic methods of generation and improvement of rules seeking for desirable ETRs. We can transform ETRs, preserving correctness of computation, through many manipulative techniques, i.e., changing from nondeterministic atoms into sequentially executable atoms, introducing multi-head rules, and adjusting priority of rules, by which we can effectively improve correct programs into both correct and more efficient programs.