Printer Friendly

Koichi Furukawa.

KEIO UNIVERSITY

Three years prior to the start of FGCS, a committee investigated new information-processing technologies for the 1990s. More than a hundred researchers were involved in the discussions conducted during that time. Two main proposals emerged from the discussions. One was an architecture-oriented proposal focusing on more flexible and adaptive systems that can generate computers tuned to given specifications. The other was a software-oriented proposal aimed at redesigning programming languages and building a new software culture based on those new languages. After thorough feasibility studies were completed, we selected the latter approach because of its potential richness and its expected impact.

For the selection of the kernel programming language, one of the most important points was the adequacy of the language for knowledge information processing. From this point of view, there were two candidates: LISP and Prolog.

At that time, we had much programming experience in LISP. On the other hand, we were relatively new to Prolog. Fuchi (Keio University), a few other researchers from ETL, and I, began a joint research project on logic programming in late 1976. Fuchi was very interested in Prolog that I brought from SRI in 1976. It was a Prolog interpreter by Colmerauer, written in Fortran running on a DEC-10 computer. We were able to make it run on our computer and began a very preliminary study using the system. I wrote several programs on database indexing. After that, we obtained DEC-10 Prolog from David H.D. Warren. I wrote a program to solve the Rubik cube problem in DEC-10 Prolog [9]. It ran efficiently and solved the problem in a relatively short time (around 20 seconds). It is a kind of expert system in which the inference engine is a Production System realized efficiently by a tail-recursive Prolog program. From this experience, I became convinced that Prolog was the language for knowledge information processing.

What Caused the Shift from Prolog to GHC?

From the beginning of the project, we planned to introduce a series of (fifth-generation) kernel languages: the preliminary version, the first version, and second version of FGKL [9]. The preliminary version was a version of Prolog with some extensions to the modularization, meta-structure and relational database interface.

The direction of the first and final versions of FGKL was given in [9] at FGCS'81:

The first version of the FGKL will be designed, and its software simulator will be implemented during the first stage of the project. One of the goals of this version is a support mechanism for parallel execution.

A new parallel execution mechanism based on breadth first search of and/or graph has to be developed as well as exception handling of forced sequential execution.

The features extended to Prolog in the preliminary version should also be refined in this stage.

Another important extension to be introduced in this stage is concurrent programming capability; [12] developed a very high-level simulation language which incorporates a concurrency control mechanism into a Prolog-like language.

The design and implementation of the second and final version of FGKL will be completed by the end of the intermediate stage.

The main feature of the final version is the ability to deal with distributed knowledge bases. Since each knowledge base has its own problem-solving capability, cooperative problem solving will become very important. One of the basic mechanisms to realize the function is message passing [14]. Since concurrent programming needs interprocess communication, the primitive message-passing mechanism will have been developed by the end of the initial stage. The result of the research on knowledge representation languages and metainference systems will be utilized in this stage to specify those functions which FGKL is to provide, and to work out means to realize them.

In preparing the preceding material, I did not have a chance to read the paper by Clark and Gregory [5], proposing a concurrent logic programming language called Relational Language. Just after having read the paper, I believed that thier proposal was the direction we should follow because it satisfied most of the functional specifications of the first and second versions of FGKL, as cited.

I met Ehud Shapiro in Sweden and in France in 1982, and we found that we had common interests in concurrent logic programming. He proposed a new concurrent logic programming language called Concurrent Prolog [20]. This was more expressive than Relational Language in the sense that it was easy to write a Prolog interpreter in the language. Just after the conference, we invited him to continue our discussion. At ICOT, the KL1 design group tried to find the best solution to concurrent logic programming languages. We collaborated with Shapiro, and Clark and Gregory, who designed Relational Language and, late, PARLOG [4]. We also collaborated with Ken Kahn who was also very interested in concurrent logic programming. In 1983, we invited those researchers to ICOT at the same time and did extensive work on concurrent logic programming, mainly from two aspects: expressiveness and efficiency.

Concurrent Prolog is not efficient in realizing the atomic unification that is the origin of its expressiveness. It is particularly difficult to implement on it the distributed-memory architecture essential for scalable parallel processing.

On the other hand, PARLOG is less expressive, and it is impossible to write a simple Prolog metainterpreter in the language. Furthermore, mode declaration is needed to specify input/output mode. This restriction makes it possible to realize efficient implementation even on scalable distributed-memory architecture.

At that time, since it was very difficult to judge which of the two languages was better, we planned to pursue both Concurrent Prolog and PARLOG at the same time.

Then, Ueda investigated the details of these two languages. Finally, he proposed Guarded Horn Clauses (GHC) [22, 24]. It was about one year after the intensive collaboration. GHC is essentially very similar to Relational Language/PARLOG. One apparent difference is that GHC needs no mode declaration.

After deliberate investigation on this proposal, we decided to adopt GHC as the core of FGKL version 1.

The change of the language from Prolog to concurrent logic programming was, therefore, scheduled by us from the beginning, and the change was no surprise for me. However, it provided a considerable shock to the researchers and managers in the private companies that were collaborating with us. We needed to persuade them by showing them the new language's superiority over Prolog.

One serious defect of concurrent logic programming was the lack of automatic search capability, a shortcoming that is directly related to the notion of completeness of logic programming. In other words, we obtained the ability of concurrent programming in logic programming at the cost of automatic search capability.

The research topic of regaining this capability became one of the most important issues since the choice of GHC. We at last succeeded in solving this problem by devising several programming methodologies for an all-solution search after several years of research efforts [6, 19, 23].

Evaluation of the Current Results in Light of Early Expectations

My very early expectations are best summed up in [9] and [10]. I will evaluate the current research results by referring to the descriptions in these papers.

The former paper describes what we were striving for in mechanisms/functions of problem solving and inference as follows:

The mechanisms/functions of problem solving and inference that we have considered range from rather basic concepts such as list processing, pattern matching, chronological backtracking, and simple Horn clause deduction, to higher-level ones such as knowledge acquisition, inference by analogy, common sense reasoning, inductive inference, hypothetical reasoning, and metaknowledge deduction. Furthermore, high-speed knowledge information processing based on parallel-computation mechanisms and specialized hardware have been extensively investigated to enhance efficiency and make the whole system feasible.

The research project for problem solving and inference mechanisms is outlined as follows:

1. The design of the kernel language of the FGC (called FG-kernel language or simply FGKL): According to the current program, there will be three evolution stages for the development of FGKL to follow; the preliminary version for the first three years, the first version for the following four years and the second and final version for the last three years.

2. The development of basic software systems on the FGKL, including an intelligent programming system, a knowledge representation language, a metainference system, and an intelligent human-machine interface system.

3. (Ultimate goal of this project): The construction of knowledge information processing system (KIPS) by means of the basic software systems.

According to [9], four major components were proposed to realize the problem-solving and inference mechanisms: the FG-kernel language, an intelligent programming system, a knowledge representation language, and a metainference system. I will pick up these four items to evaluate the current research results in the light of my early expectations.

Also, there are several research results that we did not expect before, or even at the beginning of, the project. The two most important results are constraint logic programming and parallel theorem provers.

On the FG-Kernel Language

The most important component of this project is the FG-kernel language. In my very early expectations, I wanted to extend Prolog to incorporate concurrency as the first version of FGKL. However, concurrent logic programming is not a superset of Prolog. It does not have the automatic searching capability, and therefore it lacks the completeness of Prolog. Also, it is not upwardly compatible with Prolog. Fortunately, we largely succeeded in regaining the searching capability by devising programming techniques.

At the end of the initial stage and the beginning of the intermediate stage, we tried to design a second version of FGKL, named KL2, based on GHC/KL1. We designed a knowledge-programming language called Mandala [11], but we failed to build an efficient language processor for Mandala. The second candidate for KL2 was the concurrent constraint-programming language called Guarded Definite Clauses with Constraints (GDCC) [13]. We are working on developing an efficient language processor in GHC/KL1, but we have not succeeded so far.

We developed a parallel theorem prover called Model Generation Theorem Prover (MGTP) [8] in GHC/KL1. We adopted an efficient programming methodology for the all-solution search [6] to implement MGTP, and we succeeded in developing a very efficient bottom-up theorem prover for full first-order logic. Although MGTP demands range restrictedness in the problem description, it is widely applicable to many realistic applications. This system provides the possibility for the full first-order logic to be one of the higher-level programming languages on our parallel inference machine.

On an Intelligent Programming System

Regarding the second component, we emphasized the importance of intelligent programming to resolve the software crisis. We described it as follows:

One of the main targets of the FGCS project is to resolve the software crisis. In order to achieve the goal, it is essential to establish a well-founded software production methodology with which large-scale reliable programs can be developed with ease. The key technology will likely be modular programming, that is, a way to build programs by combining component modules. It has been already noted that the kernel language will provide constructs for modularization mechanisms, but to enhance the advantage a programming system should provide suitable support. The ultimate goal is that the support system will maintain a database with modules and knowledge on them to perform intelligent support for modular programming.

Concerning modularization, we developed ESP, Extended Self-contained Prolog [2], which features module construction in an object-oriented flavor. We succeeded in developing our operating system. SYMPOS [2], entirely in ESP. The result shows the effectiveness of the module system in ESP. However, ESP is not a pure logic programming language. It is something like a mixture of Prolog and Smalltalk. The module system originated in Smalltalk. In a sense, we adopted a practical approach to obtaining modularity for developing the operating system by ourselves.

Later, we developed an operating system for PIM, called PIMOS, in KL1 [3]. We extended GHC by adding a meta-control mechanism called Shoen (a Japanese word meaning an ancient regional government) for creating users' programming environments. By utilizing the Shoen mechanism, we succeeded in developing an operating system that runs on PIM.

For the ultimate goal of an intelligent programming system, we tried to develop component technologies such as partial evaluation, program transformation, program verification, and algorithmic debugging. We even tried to integrate them in a single system called Argus. However, we could not attain the goal for real applications.

On a Knowledge Representation Language

Since the issue of knowledge representation was discussed in much greater detail in [10], I will use that description as a reference:

The goal of this work is to develop cooperative knowledge-based systems in which problems are solved by the cooperation of intelligent agents with distributed knowledge sources. An intelligent agent works as if it were an excellent librarian, knowing where the relevant knowledge sources exist, how to use them to get necessary information, and even how to solve the problem.

With the future progress of knowledge-engineering technology, it can be expected that the size of knowledge bases in practical use will become bigger and bigger. We think the approach aiming at the cooperative knowledge-based edge-based systems is a solution of the problem: how to manage the growing scale of knowledge base in real problems. As the knowledge sources distribute over the knowledgeable agents, inference and problem solving should be executed cooperatively over those distributed knowledge sources.

The research project for knowledge base mechanisms is outlined as follows:

1. The development of a knowledge representation system: the design of a knowledge representation language (called Fifth Generation Knowledge Representation Language, FGKRL in short) and support systems for the knowledge base building are planned at the initial stage of the project.

2. Basic research on knowledge acquisition: this system is the key to the cooperative knowledge-based system.

3. Basic research on distributed problem solving.

4. Design of the external knowledge bases: the intelligent interface between a central problem solver and external knowledge bases is the key issue of this work. Relational algebra may be an interface language at least in the earlier stages of the project.

In our research into knowledge bases, we focused on developing a knowledge representation language, rather than pursuing its architectural aspect (including a cooperative knowledge base). In this respect, very little research was done in the project for pursuing knowledge base architecture.

From the viewpoint of an inference mechanism associated with a knowledge base, we expected a mixture of a production system and a frame-oriented system as described in [9]:

The image of the knowledge representation language we have in mind can be more or less regarded as a mixture of a production system and a frame-oriented system. Our aim is to implement such a sophisticated language on FGKL. . . .

However, it is difficult to efficiently implement a frame-oriented system on Prolog because of its lack of structuring concepts. The proposed extension for structuring mechanisms such as modality and metacontrol is expected to solve the problem.

If we paraphrase this as a mixture of a declarative knowledge representation scheme having a uniform inference engine and a knowledge representation scheme for structural information, we can claim we attained the expectation. We developed a powerful knowledge representation language called Quixote [18,25], based on the idea of representation of structural information and constraint satisfaction as its uniform inference engine. The result is not truly satisfactory in the sense that it cannot be executed efficiently in concurrent/parallel environments, so far.

On a Metainference System

In the original plan, a metainference system had an important role in realizing intelligent human-machine and machine-machine interfaces, as described here:

A metainference system serves a semantic interpreter between a person and a machine and also between two different machines. The interpreter must understand natural language and human mental states, as well as machine language and machine status.

We intend to solve several apparently different problems in a single framework of the metainference system. The problems we consider include: (1) knowledge acquisition, (2) problem-solving control, (3) belief revision, (4) conversation control, (5) program modification, (6) accessing external databases, (7) reorganizing external databases.

A metainference system makes use of knowledge about (a) inference rules, (b) representation of objects, (c) representation of functions/predicates, and (d) reasoning strategies to solve the problems we have listed.

The most relevant work we noticed after the project started was the amalgamation of language and metalanguage in logic programming by Bowen and Kowalski. Combining this approach with well-known metaprogramming techniques to build a Prolog interpreter, we built an experimental knowledge assimilation system in Prolog [15, 17]. We treated the notion of integrity constraint as a kind of metaknowledge in the system and succeeded in developing an elegant knowledge assimilation system using metaprogramming techniques. One serious problem was the inefficiency of metaprograms caused by the interpretive execution steps. Takeuchi [21] applied partial evaluation to metaprograms and succeeded in removing interpretive steps from their execution steps. This was one of the most exciting results we obtained during the preliminary stage of the project. It is interesting to note that this result was observed around the same time (the end of 1984) as another important result, the invention of GHC by Ueda.

We also pursued advanced AI functions within the Prolog framework. They include nonmonotonic reasoning, hypothetical reasoning, analogical reasoning, and inductive inference.

However, most research output, including the knowledge assimilation system was not integrated into the concurrent logic programming framework. Therefore, very little was produced for final fifth-generation computer systems based on PIM.

An exception is a parallel bottom-up theorem prover called MGTP, and application systems running on it. An example of such applications is hypothetical reasoning. I expect this approach will attain my original goal of "high-speed knowledge information processing based on parallel computation mechanisms and specialized hardware" in the near future.

How ICOT Worked and Managed the Project

Research activity is like a chemical reaction. We need to prepare the research environment carefully to satisfy the reaction conditions. If the preparation is good, the reaction will start automatically. In the case of research activity, the reaction conditions are (1) an appropriate research subject (knowledge information processing and parallel processing), (2) an appropriate research discipline (logic programming), (3) sufficiently good researchers, (4) several key persons, and (5) appropriate research management.

The importance of the research subject is considerable, and the success of our project is due mainly to the selection of the research topics, that is, knowledge information processing and parallel processing, and the selection of logic programming as the research discipline.

At the establishment of the ICOT research center, the director of ICOT, Kazuhiro Fuchi, posed one restriction on the selection of researchers: that is, the researchers must be under 35 years old when they join ICOT. We made another effort to select good researchers from private companies associated with the project by designating researchers whose talent was known to us from their earlier work.

The overall activity of ICOT covered both basic research and systems development. An important aspect related to this point is a good balance of these two basically different activities. The number of researchers involved in these two activities was about the same at the beginning. The latter gradually increased to around twice as many as the former. The technology transfer of basic research results into the systems development group was performed very smoothly by reorganizing the structure of ICOT and moving researchers from the basic research group into the systems development group. A typical example is the development of GHC in the basic research group, and the later development of KL1, Multi-PSI, and PIM in the systems development group.

In the basic research group, we intentionally avoided research management except for serious discussions on research subjects. I personally played the role of critic (and catalyst), and tried to provide positive suggestions on basic research subjects.

We were very fortunate, since we received unexpected feedback from abroad at the beginning of the project. National and international collaboration greatly helped us to create a highly stimulating research environment. ICOT became a world center of logic-programming research. Almost all distinguished researchers in the logic-programming field visited us and exchanged ideas. Also, we received strong support from national researchers through working groups.

Concluding Remarks

Logic programming is a rich enough topic to support a 10-year project. During this decade, it produced new research subjects such as concurrent LP, constraint LP, deductive databases, program analysis, program transformation, nonmonotonic reasoning in LP frameworks, abduction, and inductive logic programming.

Concurrent logic programming was the right choice for balancing efficient parallel processing with expressiveness.

We succeeded in boosting the amount of logic programming research all over the world, which further benefited our own project.

Logic programming now covers almost all aspects of computer science, including both software and hardware. It provides one of the best approaches to general concurrent/parallel processing.

Further research will focus on new applications. Complex inversion problems, including abductive inference and the solving of nonlinear equations by Grodner are good candidates that will require heavy symbolic computation and parallel processing.

References

[1.] Bowen, K.A. and Kowalski, R.A. Amalgamating language and metalanguage in logic programming. In Logic Programming. Academic Press, New York, 1982, pp. 153-172.

[2.] Chikayama, T. Programming in ESP--Experiences with SIMPOS. In Programming of Future Generation Computers. North-Holland, Amsterdam, 1988.

[3.] Chikayama, T., Sato, H. and Miyazaki, T. Overview of the Parallel Inference Machine Operating System (PIMOS). In Proceedings of the International Conference on Fifth Generation Computing Systems 1988 (Tokyo). 1988.

[4.] Clark, K.L. and Gregory, S. PARLOG: Parallel programming in logic. ACM. Trans. Program Lang. Syst. 8, 1 (1986).

[5.] Clark, K.L. and Gregory, S. A relational language for parallel programming. In Proceedings of the ACM Conference on Functional Programming Languages and Computer Architecture. ACM, New York, 1981.

[6.] Fuchi, K. An Impression of KL1 programming--from my experience with writing parallel provers. In Proceedings of the KL1Programming Workshop '90. ICOT, Tokyo, 1990. In Japanese.

[7.] Fuchi, K. and Furukawa, K. The Role of Logic Programming in the Fifth Generation Computer Project. Vol. 5, No. 1, New Generation Computing, Ohmsha-Springer, Tokyo, 1987.

[8.] Fujita, H. and Hasegawa, R. A model generation theorem prover in KL1 using a ramified-stack algorithm. In Proceedings of the Eighth International Conference on Logic Programming (Paris). 1991.

[9.] Furukawa, K., Nakajima, R., Yonezawa, A., Goto., S. and Aoyama, A. Problem solving and inference mechanisms. In Proceedings of the International Conference on the Fifth Generation Computer Systems 1981 (Tokyo, 1981).

[10.] Furukawa, K., Nakajima, R., Yonezawa, A., Goto, S. and Aoyama, A. Knowledge base mechanisms. In Proceedings of the Eighth International Conference on Logic Programming (Tokyo, 1981).

[11.] Furukawa, K., Takeuchi, A., Kunifuji, S., Yasukawa, H., Ohki, M. and Ueda, K. Mandala: A logic based knowledge programming system. In Proceedings of the International Conference on the Fifth Generation Computer Systems (Tokyo, 1984). Ohmsha-North-Holland, Tokyo, 1984, pp. 613-622.

[12.] Futo, I. and Szeredi, P. T-Prolog: A Very High Level Simulation System--General Information Manual. SZ. K. I. 1011 Budapest I. Iskola Utca 8, 1981.

[13.] Hawley, D. and Aiba, A. Guarded definite clauses with constraints--Preliminary report. Tech. Rep. TR-713, ICOT, Tokyo, 1991.

[14.] Hewitt, C. Viewing control structure as patterns of passing messages. Artifi, Intell, 8, 3 (1977).

[15.] Kitakami, H., Kunifuji, S., Miyachi, T. and Furukawa, K. A methodology for implementation of a knowledge acquisition system. In Proceedings of the IEEE 1984 International Symposium on Logic Programming (1984). IEEE Computer Society Press, Los Alamitos, Calif.

[16.] Manthey, R and Bry, F. SATCHMO: A theorem prover implemented in Prolog. In Proceedings of CADE-88 (Argonne, Ill., 1988).

[17.] Miyachi, T., Kunifuji, S., Kitakami, H., Furukawa, K., Takeuchi, A. and Yokota, H. A knowledge assimilation method for logic databases. In Proceedings of the IEEE 1984 International Symposium on Logic Programming. IEEE Computer Society Press, Los Alamitos, Calif., 1984, pp. 118-125.

[18.] Morita, Y., Haniuda, H. and Yokota, K. Object identity in Quixote. Tech. Rep. TR-601, ICOT, Tokyo, 1990.

[19.] Okumura, A. and Matsumoto, Y. Parallel programming with layered streams. In Proceedings of the Fourth Symposium on Logic Programming (San Francisco, 1987), pp. 343-350.

[20.] Shapiro, E.Y. A subset of concurrent Prolog and its interpreter. Tech. Rep. TR-003, Institute for New Generation Computer Technology, Tokyo, 1983.

[21.] Takeuchi, A. and Furukawa, K. Partial evaluation of Prolog programs and its application to meta programming. In Proceedings of IFIP'86 (1986). North-Holland, Amsterdam.

[22.] Ueda, K. Guarded Horn Clauses. In Logic Programming '85, E. Wada, Ed. Lecture Notes in Computer Science, vol. 221, Springer-Verlag, New York, 1986.

[23.] Ueda, K. Making exhaustive search programs deterministic. In Proceedings of the Third International Conference on Logic Programming (1986). Springer-Verlag, New York.

[24.] Ueda, K. and Chikayama, T. Design of the Kernel Language for the Parallel Inference Machine. Comput. J. 33, 6 (1990), 494-500.

[25.] Yasukawa, H. and Yokota, K. Labeled graphs as semantics of objects. Tech. Rep. TR-600, ICOT, Tokyo, 1990.
COPYRIGHT 1993 Association for Computing Machinery, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1993 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Technical; The 5th Generation Project: Personal Perspectives; goals and outcome of research project
Author:Furukawa, Koichi
Publication:Communications of the ACM
Article Type:Cover Story
Date:Mar 1, 1993
Words:4132
Previous Article:Robert Kowalski.
Next Article:Kazunori Ueda.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters