Program Transformation and OLDT
a Personal Perspective
Taisuke Sato
Tokyo Institute of Technology
Japan
Editor:
Enrico Pontelli
Warning: this article is compiled from my unreliable memory of the early days of program transformation in LP.
Long Long Ago
When I joined the Electrotechnical Laboratory (ETL), a research institute under the ministry of trade and industry in Japan more than thirty years ago, symbolic AI was on the rise. There was a strong group lead by Kazuhiro Fuchi, who initiated and orchestrated the Japanese Fifth Generation Computer System project (FGCS) starting in 1982, doing a variety of AI research from image understanding, speech recognition, natural language understanding, and so on.
What was lucky to me was that next year Koichi Furukawa, who became a deputy director of FGCS, brought Marseille Prolog into ETL after a visit to the Stanford Research Institute. I could have a chance of directly touching Prolog. Programs looked mysterious (predicate names were French!) and the interpreter written in FORTRAN ran very slowly but this new language seemed to promise an exciting future for me.
So I gradually shifted from Lisp that was the defacto standard AI language those days to Prolog that was born in Europe a couple years ago. In the mean time my research interest switched from natural language processing to Prolog. There were so many fun things to do from theory to application. In particular NAF (negation-as-failure) attracted me because firstly it was theoretically mysterious and secondly I simply believed that solving problems with NAF would lead to full first-order logic programming, the unexplored realm of logic programming. My problem was that I didn't have a concrete idea about negation.
An Encounter with Partial Evaluation
In spring 1982, I went to Kyoto. My purpose was to attend the RIMS Symposium on Software Science and Engineering and to give a talk on intelligent backtracking in Prolog. In retrospect, it was a sheer coincidence that Yoshihiko Futamurna working at Hitachi also attended the symposium. He gave a talk on partial evaluation and he was a tireless advocator of partial evaluation though I did not know anything about him.
He explained so called "Futamura projection" to us and demonstrated how to construct a compiler from an interpreter, or more ambitiously a complier-compiler by partial evaluation. It was my first exposure to unfold/fold transformation and it was an exciting experience: it looked as if a theory, partial evaluation, was going to achieve a real break through, the construction of mathematically correct compiler. Although he talked in the context of a functional programming, obviously his approach is applicable to Prolog. More to the point is that Prolog has unification that can eliminate all the difficulties in implementing a partial evaluator by say Lisp.
Being galvanized by the possibility of applying partial evaluation to logic programs, I returned to ETL in Tsukuba. I tried a couple of transformation examples manually following Futamura's talk.The first one, I still remember, was to derive a recursive program forinitial(X,Z) - X is an initial list of Z - from initial(X,Z):-append(X,Y,Z). It was done easily. Other examples (reverse, a string matcher, etc) were also easy. I was quickly convinced of the power of unfold/fold transformation.
A few days later, encouraged by this initial success, I consulted Hisao Tamaki on this emerging research subfield, unfold/fold transformation in logic programming. He was staying at ETL as a visiting scholar then and had a strong background in programming language and algorithm. He immediately showed strong interest and it was a natural consequence that we began working in close collaboration beyond going for drink together.
Meaning Preserving Transformation
After starting collaboration, we knew that logic program transformation was not no-man's land. Quite opposite. There was already a bunch of work. Burstall and Darlington published their famous paper on functional program transformation in 1977. Keith Clark and Sharon Sickel applied their work to logic program derivation in the same year. Christopher Hogger published a rather comprehensive paper on deductive derivation of logic programs in J.ACM in 1981.
We noticed however that their framework is axiomatic deduction, and hence while every computed goal by a transformed program is a logical consequence of the (if-and-only-if completion of) original program, the converse does not hold in general. In other words, the equivalence of transformed programs in the sense of the least model semantics was not established yet.
Next year, 1983, was a busy year. While publishing two papers on LP, one in New Generation Computing 1(1) and the other at ICALP in Barcelona, we continued to try to prove equivalence among transformed programs. The point was clear: if p(X):- q(X) is immediately folded by p(X):-q(X), we get p(X):-p(X), which must be avoided. We needed some condition that prevents this folding.
Tamaki eventually hit the necessary idea. He introduced "rank" of a ground atom A based on the size of the smallest proof tree of A and applied it to determine a foldable condition and thus completed an equivalence proof. In the end he submitted a paper on the equivalence proof to the 2nd ICLP in Uppsala and I submitted a paper on program synthesis using unfold/fold transformation and negation to the 1st FGCS conference in Tokyo.
Append Optimizer
The mechanism of unfold/fold transformation is general but real problems are specific. To fill the gap is equivalent to applying it to a concrete problem. After publishing the unfold/fold paper, we looked for the next target.
Tamaki again hit a smart idea, "Append Optimizer". The story goes like this. First we allow a user to write a logic program freely using append/3. But append/3 incurs redundancy (copy). So we remove it by the Append Optimizer which automatically introduces new data structure similar to difference list to eliminate data copy by append/3.
It has turned out however that the Append Optimizer requires the dependency analysis of variables in a program. Worse yet an analyzer for this purpose often goes into infinite call as it traces the execution of the source program without any input (goals are completely general). Now the problem is to stop this infinite call. The idea of tabling came out this moment. Indeed necessity is the mother of invention: tabling can stop infinite call.
Putting aside the Append Optimizer, he concentrated on formalizing tabling in logic programming. He finally proved the completeness of OLDT (OLD with Tabulation) and presented it at the 3rd ICLP in London in summer 1986 when I stayed at Imperial College as a visiting researcher from ETL.
Looking Back
Regrettably the Append Optimizer project was never resumed after its suspension. I do not remember the exact reason. Probably because I was more involved in extending unfold/fold transformation to non-definite clauses and he interest turned to concurrency.
Our collaboration continued until 1989 when we published two papers on logic program synthesis. Later Hisao Tamaki left LP and moved to Toronto to study algorithm and I slowly began moving toward non-deductive approaches in AI such as GA and machine learning.
Looking back, even had we not proposed, probably someone would have introduced unfold/fold transformation and tabling to LP anyway, but we are happy that we could help their introduction to LP, which is all I can say now.