We now move from propositional logic to richer first-order logic, where propositions can involve non-propositional variables that may be universally or existentially quantified. We show how proof in first-order logic can be mechanized naively via Herbrand's theorem. We then introduce various refinements, notably unification, that help make automated proof more efficient.

First-order logic and its implementation

Propositional logic only allows us to build formulas from primitive propositions that may independently be true or false. However, this is too restrictive to capture patterns of reasoning where the truth or falsity of propositions depends on the values of non-propositional variables. For example, a typical proposition about numbers is ‘m < n’, and its truth depends on the values of m and n. If we simply introduce a distinct propositional variable for each such proposition, we lose the ability to interrelate different instances according to the variables they contain, e.g. to assert that ¬(m < nΛn < m). Firstorder (predicate) logic extends propositional logic in two ways to accommodate this need:

• the atomic propositions can be built up from non-propositional variables and constants using functions and predicates;

• the non-propositional variables can be bound with quantifiers.

We make a syntactic distinction between formulas, which are intuitively intended to be true or false, and terms, which are intended to denote ‘objects’ in the domain being reasoned about (numbers, people, sets or whatever). Terms are built up from (object-denoting) variables using functions. In discussions we use f(s, t, u) for a term built from subterms s, t and u using the function f, or sometimes infix notation like s + t rather than +(s, t) where it seems more natural or familiar.

Different kinds of errors can occur in a program, and it is useful to distinguish among them in order to track them down more quickly:

• Syntax errors are produced by Python when it is translating the source code into byte code. They usually indicate that there is something wrong with the syntax of the program. Example: Omitting the colon at the end of a def statement yields the somewhat redundant message SyntaxError: invalid syntax.

• Runtime errors are produced by the interpreter if something goes wrong while the program is running. Most runtime error messages include information about where the error occurred and what functions were executing. Example: An infinite recursion eventually causes the runtime error “maximum recursion depth exceeded.”

• Semantic errors are problems with a program that runs without producing error messages but doesn't do the right thing. Example: An expression may not be evaluated in the order you expect, yielding an incorrect result.

The first step in debugging is to figure out which kind of error you are dealing with. Although the following sections are organized by error type, some techniques are applicable in more than one situation.

SYNTAX ERRORS

Syntax errors are usually easy to fix once you figure out what they are. Unfortunately, the error messages are often not helpful. The most common messages are SyntaxError: invalid syntax and SyntaxError: invalid token, neither of which is very informative.

OBJECT-ORIENTED FEATURES

Python is an object-oriented programming language, which means that it provides features that support object-oriented programming.

It is not easy to define object-oriented programming, but we have already seen some of its characteristics:

• Programs are made up of object definitions and function definitions, and most of the computation is expressed in terms of operations on objects.

• Each object definition corresponds to some object or concept in the real world, and the functions that operate on that object correspond to the ways real-world objects interact.

For example, the Time class defined in Chapter 16 corresponds to the way people record the time of day, and the functions we defined correspond to the kinds of things people do with times. Similarly, the Point and Rectangle classes correspond to the mathematical concepts of a point and a rectangle.

So far, we have not taken advantage of the features Python provides to support object-oriented programming. These features are not strictly necessary; most of them provide alternative syntax for things we have already done. But in many cases, the alternative is more concise and more accurately conveys the structure of the program.

For example, in the Time program, there is no obvious connection between the class definition and the function definitions that follow. With some examination, it is apparent that every function takes at least one Time object as an argument.

THE STRANGE HISTORY OF THIS BOOK

In January 1999, I was preparing to teach an introductory programming class in Java. I had taught it three times and I was getting frustrated. The failure rate in the class was too high, and, even for students who succeeded, the overall level of achievement was too low.

One of the problems I saw was the books. I had tried three different books (and had read a dozen more), and they all had the same problems. They were too big, with too much unnecessary detail about Java and not enough high-level guidance about how to program. And they all suffered from the trap door effect: they would start out easy, proceed gradually, and then somewhere around Chapter 4 the bottom would fall out. The students would get too much new material, too fast, and I would spend the rest of the semester picking up the pieces.

Two weeks before the first day of classes, I decided to write my own book. I wrote one 10-page chapter a day for 13 days. I made some revisions on Day 14 and then sent it out to be photocopied.

My goals were:

• Keep it short. It is better for students to read 10 pages than not read 50 pages.

• Be careful with vocabulary. I tried to minimize the jargon and define each term at first use.

• […]