Peter Lodewijk Van Roy

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-90-600
November 1990

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/CSD-90-600.pdf

The purpose of this dissertation is to provide constructive proof that the logic programming language Prolog can be implemented an order of magnitude more efficiently than the best previous systems, so that its speed approaches imperative languages such as C for a significant class of problems. The driving force in the design is to encode each occurrence of a general feature of Prolog as simply as possible. The resulting system, Aquarius Prolog, is about five times faster than Quintus Prolog, a high performance commercial system, on a set of representative programs. The design is based on the following ideas:

(1) Reduce instruction granularity. Use an execution model, the Berkeley Abstract Machine(BAM), that retains the good features of the Warren Abstract Machine (WAM), a standard execution model for Prolog, but is more easily optimized and closer to a real machine.

(2) Exploit determinism. Compile deterministic programs with efficient conditional branches. Most predicates written by human programmers are deterministic, yet previous systems often compile them in an inefficient manner by simulating conditional branching with backtracking.

(3) Specialize unification. Compile unification to the simplest possible code. Unification is a general pattern-matching operation that can do many things in the implementation: pass parameters, assign values to variables, allocate memory, and do conditional branching.

(4) Dataflow analysis. Derive type information by global dataflow analysis to support these ideas.

Because of limitations of the dataflow analysis, the system is not yet competitive with the C language for all programs. I outline the work that is needed to close the remaining gap.

Advisor: Alvin M. Despain

BibTeX citation:

@phdthesis{Van Roy:CSD-90-600,
    Author = {Van Roy, Peter Lodewijk},
    Title = {Can Logic Programming Execute as Fast as Imperative Programming?},
    School = {EECS Department, University of California, Berkeley},
    Year = {1990},
    Month = {Nov},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/5686.html},
    Number = {UCB/CSD-90-600},
    Abstract = {The purpose of this dissertation is to provide constructive proof that the logic programming language Prolog can be implemented an order of magnitude more efficiently than the best previous systems, so that its speed approaches imperative languages such as C for a significant class of problems. The driving force in the design is to encode each occurrence of a general feature of Prolog as simply as possible. The resulting system, Aquarius Prolog, is about five times faster than Quintus Prolog, a high performance commercial system, on a set of representative programs. The design is based on the following ideas: <p>(1) Reduce instruction granularity. Use an execution model, the Berkeley Abstract Machine(BAM), that retains the good features of the Warren Abstract Machine (WAM), a standard execution model for Prolog, but is more easily optimized and closer to a real machine. <p>(2) Exploit determinism. Compile deterministic programs with efficient conditional branches. Most predicates written by human programmers are deterministic, yet previous systems often compile them in an inefficient manner by simulating conditional branching with backtracking. <p>(3) Specialize unification. Compile unification to the simplest possible code. Unification is a general pattern-matching operation that can do many things in the implementation: pass parameters, assign values to variables, allocate memory, and do conditional branching. <p>(4) Dataflow analysis. Derive type information by global dataflow analysis to support these ideas. <p>Because of limitations of the dataflow analysis, the system is not yet competitive with the C language for all programs. I outline the work that is needed to close the remaining gap.}
}

EndNote citation:

%0 Thesis
%A Van Roy, Peter Lodewijk
%T Can Logic Programming Execute as Fast as Imperative Programming?
%I EECS Department, University of California, Berkeley
%D 1990
%@ UCB/CSD-90-600
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/5686.html
%F Van Roy:CSD-90-600