Chapter 14
Logic Programming
(1) No ducks waltz;
(2) No officers ever decline to waltz;
(3) All my poultry are ducks.1
(1) Every one who is sane can do Logic;
(2) No lunatics are fit to serve on a jury;
(3) None of your sons can do Logic.2
(Sets of Concrete Propositions, proposed as Premisses for Soriteses: Conclusions to be found—in footnotes)
— Lewis Carroll, Symbolic Logic, Part I: Elementary (1896)
The more I think about language, the more it amazes me that people ever understand each other at all.
—Kurt Gödel
For now, what is important is not finding the answer, but looking for it.
—Douglas R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid (1979)
IN contrast to an imperative style of programming, where the programmer specifies how to compute a solution to a problem, in a declarative style of programming, the programmer specifies what they want to compute, and the system uses a built-in search strategy to compute a solution. A simple and perhaps familiar example of declarative programming is the use of an embedded regular expression language within a programming language. For instance, when a programmer writes the Python expression ([a-z])([a-z])[a-z]21, the programmer is declaring what they want to match—in this case, strings consisting of five lowercase alphabetical character palindromes—-and not how to match those strings using for loops and string manipulation functions. In this chapter, we study the foundation of declarative programming3 in symbolic logic and Prolog—the most classical and widely studied programming language supporting a logic/declarative style of programming.
1. My poultry are not officers.
2. None of your sons are fit to serve on a jury.
3. We use the terms logic programming and declarative programming interchangeably in this chapter.