Uses of Prolog in implementation of expert systems

Prolog is becoming a popular language in A. I. applications and particularly in the implementation of knowledge based expert systems. We have identified three different uses of Prolog: (1) building expert systems directly in ordinary Prolog, (2) using Prolog as the implementation language for an higher level of interpretation, and (3) extending Prolog with suitable features and directly using it. In this paper, we define the three uses in more details, compare them, and cite some concrete examples.     

A Prolog technology theorem prover

An extension of Prolog, based on the model elimination theorem-proving procedure, would permit production of a logically complete Prolog technology theorem prover capable of performing inference operations at a rate approaching that of Prolog itself.     

Prolog-ELF incorporating fuzzy logic

Prolog-ELF incorporating fuzzy logic and several useful functions into Prolog has been implemented as a basic language for building knowledge systems with uncertainty or fuzziness. Prolog-ELF inherits all the desirable basic features of Prolog. In addition to assertions with truth-values between 1.0 and 0.5 (0 for exceptional cases), fuzzy sets can be very easily manipulated. An application of fuzzy logical database is illustrated.     

Set abstraction—An extension of all solutions predicate in logic programming language

The concept of set abstraction is introduced as a simple analogy of that of lambda abstraction in the theory of lambda calculus. The set abstraction is concerned with two extensions concerning Prolog language features: “set expression” and “predicate variable.” It has been argued in the literature that the set expression extension to Prolog does really contribute to the power of the language, while the extension of predicate variables does not add anything to Prolog. Combining these two concepts of extensions to Prolog, we define “set abstraction” as the set expression in which predicate variables are allowed as data objects. In other words, the set abstraction gets involved in the higher order predicate logic. By showing some application examples, it is demonstrated that with the help of predicate variables set abstractions can nicely handle the issues of the second order predicate logic. Further, the implementation programs written in Prolog and Concurrent Prolog are presented.     

Design and simulation of a sequential Prolog machine

Prolog-X is an implemented portable interactive sequential Prolog system in which clauses are incrementally compiled for a virtual machine called the ZIP Machine. At present, the ZIP Machine is emulated by software, but it has been designed to permit easy implementation in microcode or hardware. Prolog-X running on the software-based emulator provides performance comparable with existing Prolog interpreters. To demonstrate its efficiency, compatibility, and comprehensiveness of implementation, Prolog-X has been used to compile and run several large applications programs. Several novel techniques are used in the implementation, particularly in the areas of the representation of therecordx database, the selection of clauses, and the compilation of arithmetic expressions.     

The occur-check problem in Prolog

We present a method for preprocessing Prolog programs so that their operational semantics will be given by the first-order predicate calculus. Most Prolog implementations do not use a full unification algorithm, for efficiency reasons. The result is that it is possible to create terms having loops in them, whose semantics is not adequately described by first-order logic. Our method finds places where such loops may be created, and adds tests to detect them. This should not appreciably slow down the execution of most Prolog programs.     

P-Prolog: A parallel logic language based on exclusive relation

This paper presents a parallel logic programming language named P-Prolog which is being developed as a logic programming language featuring both and- and or-parallelism. Compared with the other parallel logic programming languages, syntactic constructs such as read-only annotation,⁶⁾ mode declaration²⁾ and communication constraints⁷⁾ are not used in P-Prolog. A new concept introduced in P-Prolog is the exclusive relation of guarded Horn clauses. Advances included in P-prolog. are:

1. The synchronization mechanism can determine the direction of data flow dynamically.
2. Guarded Horn clauses can be interpreted as eitherdon’t care nondeterminism ordon’t know non-determinism.

A prototype interpreter of P-Prolog has been implemented in C-Prolog. We are now implementing a P-Prolog interpreter in the C language.     

Translating production rules into a forward reasoning Prolog program

Several attempts have been made to design a production system using Prolog. To construct a forward reasoning system, the rule interpreter is often written in Prolog, but its execution is slow. To develop an efficient production system, we propose a rule translation method where production rules are translated into a Prolog program and forward reasoning is done by the translated program. To translate the rules, we adopted the technique developed in BUP, the bottom-up parsing system in Prolog. Man-machine dialogue functions were added to the production system and showed the potential of our method to be applied to expert systems.     

Bounded-wait merge in Shapiro’s Concurrent Prolog

InA Subset of Concurrent Prolog and Its Interpreter (1983), E. Y. Shapiro introduces the language Concurrent Prolog. In his presentation, the problem of guaranteeing bounded-waiting during a merge operation is used as a programming example. Solutions are proposed for binary and n-ary merges. The solutions are, however, completely dependent on specific operational characteristics of a Concurrent Prolog machine or interpreter. This paper presents an alternate approach in which the property of bounded-waiting is incorporated into the semantics of the programs, demonstrable given only the computational model of the language. The solution strategy is to utilize the familiar systems programming techniques of block-on-input and busy-wait. This approach requires that the language be augmented with a metalogical predicate analogous to thevar(_) predicate of Sequential Prolog. The resultant programs are interesting and illustrative examples of Concurrent Prolog as a programming language.     

Sequential Prolog machine PEK

The sequential Prolog machine PEK currently under development is described. PEK is an experimental machine designed for high speed execution of Prolog programs. The PEK machine is controlled by horizontal-type microinstructions. The machine includes bit slice microprocessor elements comprising a microprogram sequencer and ALU, and possesses hardware circuits for unification and backtracking. The PEK machine consists of a host processor (MC68000) and a backend processor (PEK engine). A Prolog interpreter has been developed on the machine and the machine performance evaluated. A single inference can be executed in 89 microinstructions, and execution speed is approximately 60–70 KLIPS.     

Compiling OR-parallelism into AND-parallelism

This paper suggests a general method for compiling OR-parallelism into AND-parallelism. An interpreter for an AND/OR-parallel language written in the AND-parallel subset of the language induces a source-to-source transformation from the full language into the AND-parallel subset. This transformation can be identified and implemented as a special purpose compiler or applied using a general purpose partial evaluator. The method is demonstrated to compile a variant of Concurrent Prolog into an AND-parallel subset of the language called Flat Concurrent Prolog (FCP). It is also shown applicable to the compilation of OR-parallel Prolog to FCP. The transformation identified is simple and efficient. The performance of the method is discussed in the context of programming examples. These compare well with conventionally compiled Prolog programs.     

Temporal logic based hardware description and its verification with Prolog

Techniques of hierarchical specification and verification of hardware with temporal logic and Prolog are presented by example. Both hardware designs in gates and state-diagrams are translated into a relation between the present and the next state, which is represented in Prolog.¹⁾ Specifications are constructed by temporal logic that can express state sequences (e.g. timing diagrams) easily and also are translated into a relation between the present and the next state in Prolog. The verification method is based upon the temporal logic decision procedure in Ref. 2) and, referring to the relation tables between the present state and the next state, the verifier can reason in both directions—forward and backward in temporal sequences. Prolog has very powerful pattern matching, and its automatic backtracking capabilities facilitate easy-to-write verifier programs. It is concluded that a total verification system handling various design levels can be constructed with temporal logic and Prolog.     

Knowledge information processing language: ShapeUp

A new logic programming language, ShapeUp, is developed. ShapeUp is an expanded Prolog system with string matching facilities. The language has been developed to give programmers a new computer programming environment, especially for knowledge information processing. This area includes natural language comprehension and intelligent text processing systems with better man-machine interfaces. For this kind of application, character string data play a principal part rather than conventional numerical data. In ShapeUp, string patterns are introduced as Prolog ‘terms’. Their matching process is performed inside the unification. Thus, a program is far simpler and easier to write and read in ShapeUp, than in conventional Prolog systems, and program size is extremely reduced.     

Partial evaluation of metaprograms in a “multiple worlds” logic language

This paper describes a partial evaluation system specifically designed to be used as an automatic compilation tool for metaprograms in a KBMS (EPSILON) based on Prolog. EPSILON main underlying concepts are the extension of Prolog with theories (“multiple worlds”) and the use of metaprogramming as the basic technique to define new inference engines and tools. Our partial evaluator is oriented towards theories and metainterpreter specialization. Being designed to be used as an automatic compiler, it does not require declarations from the user to control the unfolding process. It handles full Prolog and provides also an elegant solution to the problem of the partial evaluation of incomplete and self-modifying programs, by exploiting the multiple worlds feature added to Prolog. EPSILON partial evaluation system turned out to be a very useful and powerful tool to combine the low cost and the flexibility of metaprogramming with the performance requirements of a practical knowledge based system.     

Spreadsheets with Incremental Queries as a user interface for logic programming

We believe that currently marketed programs leave unexploited much of the potential of the spreadsheet interface. The purpose of our work is to obtain suggestions for wider application of this interface by showing how to obtain its main features as a subset of logic programming. Our work is based on two observations. The first is that spreadsheets would already be a useful enhancement to interactive languages such as APL and Basic. Although Prolog is also an interactive language, this interface cannot be used in the same direct way. Hence our second observation: the usual query mechanism of Prolog does not provide the kind of interaction this application requires. But it can be provided by the Incremental Query, a new query mechanism for Prolog. The two observations together yield the spreadsheet as a display of the state of the substitution of an incremental query in Prolog. Recalculation of dependent cells is achieved by automatic modification of the query in response to a new increment that would make it unsolvable without the modification.     

Towards a pipelined Prolog processor

This paper describes the design of a Prolog machine architecture and organization. Our objective was to determine the maximum performance attainable by a sequential Prolog machine for “reasonable” cost. The paper compares the organization to both general purpose micro-coded machines and reduced instruction set machines. Hand timings indicate a peak performance rate of 450 K LIPS (logical inferences per second) is well within current technology limitations and 1 M LIPS is potentially feasible.     

Architecture of a Reduction-Based Parallel Inference Machine: PIM-R

This paper presents a highly parallel machine architecture for logic programs. We propose a Reduction-Based Parallel Inference Machine: PIM-R and describe the parallel execution mechanisms for PIM-R to run Prolog and Concurrent Prolog programs and sofware simulation results. PIM-R uses the structure-copy method. It also uses the only reducible goal copy method, a unique process-structuring method, and the reverse compaction method to decrease the amount, of copying and various copyingrelated operations and the number of packets passing through the network. PIM-R architecture features include the distributed shared memory for Concurrent Prolog, network nodes for efficient packet distribution, and the structure memory to store a part of structured data for reducing the copying overhead.