Logic programming as the integrator of the Fifth Generation Computer Systems Project. (one of four articles in special logic programming section)

The Fifth Generation Computer Systems (FGCS) project began in 1982. Three years prior to its inception, over 100 researchers met in a series of discussions with a committee investigating new information processing technologies for the 1990s. Two main proposals emerged from those discussions. One was an architecture-oriented proposal focusing on more flexible and adaptive systems which can generate computers tuned to give specifications. The other was a software-oriented proposal aimed at redesigning programming languages and building a new software culture based on the new languages, where Prolog waas thoroughly investigated as the potential base for such programming languages. As a result of careful consideration, we adopted the latter proposal because of its technical richness and the potential of its achievements.

Programming languages play a very important role in information systems. Software has a tendency to accumulate and one of the most important complaints against new information systems is their lack of software compatibility with existing systems. This prevents the large amount of software developed so far to be transferred to the new systems. Changing the programming language does not facilitate software compatibility and therein lies a great handicap. After a very careful study of logic programming, we found it could provide a foundation for many different information processing activities such as programming, software engineering, database and knowledge information processing. As a result, we concluded that logic programming should become the new unifying principle in computer science.

Based on this conclusion, we proposed the FGCS project with logic programming as its key concept. The goal of the project was to establish knowledge information processing technology, as well as to significantly improve parallel computer technology. It was commonly believed that combining knowledge information processing and parallel processing would be very difficult to achieve. To solve this problem, we considered logic programming as a working hypothesis, and placed it between the two components. We expected logic programming to play the role of a connecting bridge.

During the project, we succeeded in developing a concurrent logic programming language called Guarded Horn Clauses (GHC), and have been developing our final target parallel computer, the Parallel Inference Machine (PIM). We are also developing programming methodologies for the language and a number of application programs written in the language. These results strongly confirm the appropriateness of our working hypothesis.

From a knowledge information processing viewpoint, our approach is based on higher level programming languages augmented by optimization techniques. We developed several optimization techniques for logic programming, such as partial evaluation, program transformation, and various lower level optimizations (e.g. tail recursion optimization).

Knowledge Information

Processing

in Logic Programming

Constraint logic programming is one of the most promising areas in the field of the logic programming. The domain of Prolog is extended to cover most artificial intelligence (AI) problems. The objective is to combine constraint satisfiaction and logic programming. The reasons for its success are 1) it is a straight-forward extension of Prolog by extending the notion of unification to deal with constraint satisfaction, and 2) it extends the scope of declarative programming to a wider class of problems such as linear equations and inequations by dealing with them in a way uniform with unification between terms.

From the constraint satisfaction viewpoint, it provides programming capabidlity to the description of the problem based on constraint satisfaction. Jaffar and Lassez [17] gave criteria for a constraint logic programming system to inherit important aspects of logic programming like soundness, completeness and fixpoint semantics. It is worth noting that constraint logic programming is derived by extending unification. We will discuss later how concurrent logic programming is derived by restricting unification.

To briefly explain our own constraint logic programming language, CAL [23] is a constraint logic programming language for dealing with nonlinear equations over complex nubmers, i.e. rational polynomial ring. The execution is based on the algorithm of computing the Groebner basis for a set of nonlinear equations. It is a term rewriting system and a version of the Knuth-Bendix completion. Let us show a simple example of using CAL in geometry. We try to deduce Heron's formula from a set of geometrical definitions of surfaces, right-angled triangles and general triangles.

An Example Program in CAL

surface(Base,Height,Area):- 2*Area = Base*Height. right [underscore] tri(X,Y,Z):-X[caret]2 + Y[caret]2 = Z[caret]2. tri(A,B,C,Area):- C = CA + CB, right [underscore] tri(CA,Height,A), right [underscore] tri(CB,Height,B), area(C,Height,Area).

The interpretation of the last clause defining a general triangle is shown in Figure 1. Note that CA or CB can be a negative number.

Heron's formula which expresses the area of a triangle by the lengths of three edges is obtained by executing the following query.

Query and Answer

? - tri(a,b,c,s). s[caret]2 = (-c[caret]4 + -1*a[caret]4 + 2* (2*b[caret]2*a[caret]2) + -1*b[caret]4+2*(2*c[caret]2*a[caret]2)+ 2*(2*c[caret]2*b[caret]2)/16

The execution of the goal, "?-tri(a,b,c,s)." proceeds as follows: 1) a set of constraints is collected during the execution of the goals. 2) the solver tries to solve the simultaneous equations by eliminating intermediate variables, CA, CB and Height. The variables are eliminated during computation of the Groebner Basis of the equations.

We studied the field of robot arm control to compute a desired amount of rotation and arm extension given the target position of the arm [25] using CAL. By treating …