| << Prev | - Up - | Next >> |
In the previous lectures we remarked that building structure through matching is a key idea in Prolog programming. Now that we know about recursion, we can give more interesting illustrations of this.
Nowadays, when human beings write numerals, they usually use decimal notation (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, and so on) but as you probably know, there are many other notations. For example, because computer hardware is generally based on digital circuits, computers usually use binary notation to represent numerals (0, 1, 10, 11, 100, 101, 110, 111, 1000, and so on), for the 0 can be implemented as as switch being off, the 1 as a switch being on. Other cultures use different systems. For example, the ancient Babylonians used a base 64 system, while the ancient Romans used a rather ad-hoc system (I, II, III, IV, V, VI, VII, VIII, IX, X). This last example shows that notational issues can be important. If you don't believe this, try figuring out a systematic way of doing long-division in Roman notation. As you'll discover, it's a frustrating task. In fact, the Romans had a group of professionals (analogs of modern accountants) who specialized in this.
Well, here's yet another way of writing numerals, which is sometimes used in mathematical logic. It makes use of just four symbols: 0, succ, and the left and right brackets. This style of numeral is defined by the following inductive definition:
0 is a numeral.
If X is a numeral, then so is succ(X).
As is probably clear, succ can be read as short for successor. That is, succ(X) represents the number obtained by adding one to the number represented by X. So this is a very simple notation: it simply says that 0 is a numeral, and that all other numerals are built by stacking succ symbols in front. (In fact, it's used in mathematical logic because of this simplicity. Although it wouldn't be pleasant to do household accounts in this notation, it is a very easy notation to prove things about.) Now, by this stage it should be clear that we can turn this definition into a Prolog program. The following knowledge base does this:
numeral(0).
numeral(succ(X)) :- numeral(X).So if we pose queries like
numeral(succ(succ(succ(0)))).we get the answer `yes'. But we can do some more interesting things. Consider what happens when we pose the following query:
numeral(X).That is, we're saying `Ok, show me some numerals'. Then we can have the following dialogue with Prolog:
X = 0 ;
X = succ(0) ;
X = succ(succ(0)) ;
X = succ(succ(succ(0))) ;
X = succ(succ(succ(succ(0)))) ;
X = succ(succ(succ(succ(succ(0))))) ;
X = succ(succ(succ(succ(succ(succ(0)))))) ;
X = succ(succ(succ(succ(succ(succ(succ(0))))))) ;
X = succ(succ(succ(succ(succ(succ(succ(succ(0)))))))) ;
X = succ(succ(succ(succ(succ(succ(succ(succ(succ(0))))))))) ;
X = succ(succ(succ(succ(succ(succ(succ(succ(succ(succ(0))))))))))
yes
Yes, Prolog is counting: but what's really important is how it's doing this. Quite simply, it's backtracking through the recursive definition, and actually building numerals using matching. This is an instructive example, and it is important that you understand it. The best way to do so is to sit down and try it out, with trace turned on.
Building and binding. Recursion, matching, and proof search. These are ideas that lie at the heart of Prolog programming. Whenever we have to generate or analyze recursively structured objects (such as these numerals) the interplay of these ideas makes Prolog a powerful tool. For example, in the next lecture we introduce lists, an extremely important recursive data structure, and we will see that Prolog is a natural list processing language. Many applications (computational linguistics is a prime example) make heavy use of recursively structured objects, such as trees and feature structures. So it's not particularly surprising that Prolog has proved useful in such applications.
| << Prev | - Up - | Next >> |