What are Logic Programming and Prolog?

Overview

There are many ways of organizing computations. Perhaps the most familiar paradigm is procedural: the program specifies a computation by saying how it is to be performed. FORTRAN, C, and even object-oriented languages fall under this general approach. Another paradigm is declarative: the program specifies a computation by giving the properties of a correct answer. Prolog and LDL are examples of declarative languages; since they emphasize the logical properties of a computation, they are often called logic programming languages. The declarative/procedural distinction is not rigid: Prolog of necessity incorporates some procedural features, for example to manage file input/output, and simple Boolean tests are common in FORTRAN and C. In the ``ideal'' (I should perhaps say ``ideal to logicians'') case, writing a declarative program is equivalent to defining a proof for a proposition (relationship). This ideal is not strictly met by Prolog because of the way it implements logical negation, and other declarative languages attempt to be more logical in a strict formal sense. Prolog implements a subset of second-order logic (that is, it can deal with sets as well as atomic propositions), and the language's flexibility permits propositions which lie well outside the boundaries of any classification of formal logical systems.

The Merits of Declarative Languages

The use of declarative languages offers three important advantages.

• Logic programming languages are inherently ``high-level'' because they focus on the computation's logic and not on its mechanics (which in fact are inaccessible to the programmer). The result is that they are well-suited to expressing complex ideas because the drudgery of memory management, stack pointers, etc., is left to the computational engine. Since the engine incorporates logical inferencing, it is already a powerful tool which can be exploited in developing inference engines specific to a particular universe of discourse (sometimes also called a domain). For Klotho, we've taken advantage of Prolog's inference engine and a few features specialized for the representation of natural languages to develop a grammatical approach to compound representation.

• Logic offers the opportunity to represent data both extensionally --- as an explicit fact (``Atom A is connected to Atom B with a single bond'') --- and intensionally --- as a rule which implicitly describes the fact (``Groups X and Y are connected in a cyclic structure''; processing the rule produces the A-B bond). In addition to representing many facts compactly (for example, reverse reactions are represented by a rule which reverses the extensional representation of the forward reaction), intensional representations lend themselves naturally to representations of mechanisms, or to ways of generating related representations. For example, Klotho represents SMILES strings, bond-edge descriptions, and adjacency lists (approximately equivalent to connection tables) by the graph grammar which generates these representations dynamically from the configuration rule.

• A consequence of the preceeding is that logic programming languages are particularly suited for rapidly prototyping data structures and code to express complex ideas. Reduced drudgery and compact expression means the developer --- and even the scientist! --- can concentrate on what should be represented and how. The use of the built-in inference engine permits rapid and straightforward evaluation of the code. We find repeatedly that difficulties in coding are due to vagueness and illogic in our thinking.

References

For more on logic programming, Prolog, and LDL, I recommend in approximately this order:

• introductions to Prolog and logic programming for non-computer scientists:

  • A Prolog Primer, Jean B. Rogers. Addison-Wesley, Reading MA, 1987.

  • Prolog. Programing for Artificial Intelligence, Ivan Bratko. Addison-Wesley, Wokingham, England, 1990.

  • Prolog Programing in Depth, Michael A. Covington, Donald Nute, and Andre' Vellino. Scott-Foresman and Co., Glenview IL, 1988.

• deeper, more elegant explications:

  • The Art of Prolog, Leon Sterling and Ehud Shapiro. MIT Press, Cambridge MA, 1986.

  • The Practice of Prolog, Leon Sterling, ed. MIT Press, Cambridge MA, 1990.

  • The Craft of Prolog, Richard A. O'Keefe. MIT Press, Cambridge MA, 1990.

• logic programming with an emphasis on natural language processing (aka grammars):

  • Prolog and Natural Language Analysis, Fernando C. N. Pereira and Stuart M. Shieber. CSLI, Stanford CA, 1987.

  • Programing in Prolog, W. F. Clocksin and C. S. Mellish. Springer-Verlag, Berlin, 1987.

• LDL

  • LDL: A Logical Language for Data and Knowledge Bases, Shamim Naqvi and Shalom Tsur. Computer Science Press, Rockville MD, 1989.

Back to Klotho's home page.