High-Performance Logic Programming with the Aquarius Prolog Compiler

Reviewer: Yu-Wen Tung

Codes generated by the Aquarius Prolog compiler can be executed faster than other Prolog code, and may be as fast as C code for a restricted class of problems. To demonstrate the ideas behind Aquarius and present the performance results, this paper is organized into six sections. All except the fifth section are well organized and easy to read. The first two sections provide an excellent tutorial for novices in logic programming and Prolog, but can safely be skipped by other readers. The third section describes the Warren Abstract Machine, on which previous Prolog implementations are based. The next section states the performance difficulties that prevent such implementations from becoming a rival to imperative languages. These difficulties include costly backtracking, unnecessary copying of large data structures, and architectural mismatches. Section 5 describes how the Aquarius compiler overcomes the above difficulties . One major idea is its use of an improved execution model called the Berkeley Abstract Machine. This model has an efficient instruction set that allows the compiler to apply expensive operations such as dereferencing and trailing only when necessary. Other techniques employed by Aquarius include finding type information by global analysis and exploiting determinism extensively. The last section presents some significant performance results. Aquarius is typically two or three times faster than Quintus and BIM systems in execution, although its compilation time may be long and it does not generate the most compact code among the three. As for the performance comparison to C, Aquarius beat C on three out of four test programs. It is not clear, however, whether this result implies that Prolog can be made as efficient as an imperative language, which seems to be a major message of this paper. Nevertheless, the paper is worth reading.