A Parallel Unification
Mi Lu · 1990
he field of artificial intelligence is gaining in popularity and actively expanding into many areas of application. AI served as the basis for T Japan’s Fifth-Generation Computer Project with the primary goal of replacing traditional von Neumann computers with machines that could reason, learn, and associate. These machines can also infer, decide, and understand speech, written text, and pictures.’ Prolog and Lisp are the two primary languages available to AI programmers and knowledge-base developers. Prolog’s statements in the form of logic propositions, its argument-matching capability, and its nondeterministic and database-management features make it very suitable for AI and expert system applications. However, Prolog is time-consuming and very inefficient when run on sequential general-purpose machines. Abe et al.* note that Prolog’s performance drops to one tenth of the performance of procedural languages (such as C and Pascal) when executed by a generalpurpose computer. This fact basically explains why expert systems and other AI-application programs implemented in Prolog run very slowly on traditional general-purpose computers. Researchers traced the sources of Prolog’s inefficiency and slow execution on these machines to two algorithms: unification and backtracking. These algorithms serve as the basis for Prolog and other logic programming interpreters. We define the unification operation later. Backtracking is the operation conducted by Prolog interpreters as soon as they fail to go forward in solving the current goal. In the process of backtracking, the interpreter moves up the computation tree to explore different paths that may lead to a solution of the current goal. The execution times of these two algorithms must improve to speed up the runtime of logic programs. In addition to being frequently used in logic programming, unification has applications in databases, proving theorems, expert and knowledgebased systems, and natural language and image processing. The unification operation attempts to make two terms equivalent and often generates conditions for this equivalence to hold. These conditions appear in the alternate forms of variable substitutions or variable bindings. For instance, the unification of the two terms, f(X, a) and f(b, a), in which