LOGIC PROGRAMMING LESSON 3 In this lesson, I introduce Prolog. So far, I have taught you some ideas of logic programming through "Logic", which superficially resembles English. I chose that route to avoid scaring you with the more formal notation of Prolog. But there are four good reasons why you should now learn Prolog, even though it looks more alien. ~2 (1) Logic looks like English - enough so that it fools some people into thinking the Tutor understands more than it does. For example, after typing in facts like "mary loves john", students often ask questions like "does mary love john?". Similarly, in inquiring about the skiing advisor in Supplement 1, some tried questions like "has eddie poor fitness?" when the correct form was "eddie has_fitness poor?". The Tutor does not understand these grammatical variants, or any others. Another example is that some students are tempted to think that the Tutor regards "mary not loves john" as the opposite to "mary loves john". That's not so: the Tutor will not recognise this as being negation. Prolog is un-English enough that you won't be fooled this way. Also, its brackets and other punctuation make the grammatical structure of Prolog statements clearly apparent - more so than that of Logic. ~3 (2) Prolog closely resembles formal logic. This helps you learn Prolog, if you already know logic; or learn formal logic, once you've learnt Prolog. ~4 (3) The complete Prolog language has more facilities than I've taught so far. If I were to teach them in Logic notation, I'd have to extend the logic programming tutor to translate all these into Logic. And before you could work on logic programming elsewhere, or read books written elsewhere, you'd have to learn Prolog anyway. ~5 (4) A subtle point, related to the last one. Prolog is a language for describing relations between objects - what I called "verbs" until the end of Supplement 1, when I introduced the accepted name, "predicates". Now, the syntax of Logic makes this easy when the relations affect two objects: you put one object before the predicate, and another after it. But what if you want to relate more than two objects, as in "Mary gave Fred a pocket calculator last Christmas" There are four pieces of information here: the giver, the recipient, the thing given, and the time. In Logic, there is no room to put all this information, because you only have two arguments. Prolog however, allows you to have as many as you want, and could express this sentence without any problem. ~6 Having justified learning Prolog, let's start. The Tutor can understand both Prolog and Logic, and can translate between one and the other, so a good way to begin Prolog is by asking it to show you the Prolog equivalent of some Logic facts. Please begin by restoring one of your old files or one of the examples, or by typing in about five conditional and unconditional facts about some topic. Then type the commands: prolog. show. The first command tells the tutor to work in Prolog, not in Logic. The second displays these facts, in Prolog. Compare with the Logic equivalents by typing logic. show. The "logic" command switches back to Logic. ~7 Now, type i am_using logic. prolog. am_using( i, prolog ). show. logic. show. and go on to the next section. ~8 Logic statements imitate the English "Subject Verb Object" schema. In contrast, Prolog ones begin with the verb (i.e. the predicate), following it with a bracket, two items (the arguments) separated by a comma, and finally a closing bracket. ~9 One similarity between Prolog and Logic is that names can't contain spaces. Thus, the Prolog sentence am using( i, prolog ). is wrong. You must either remove the space or replace it by an underline: amusing( i, prolog ). or am_using( i, prolog ). As in Logic, Prolog treats these two as DIFFERENT names: "amusing" isn't the same as "am_using". You must choose one or the other and use it consistently. I recommend using underlines if you are packing more than one word into a name, as in "am_using" or "is_a" or "has_body_part". ~10 Now to illustrate what happens if you put spaces in the wrong place. Switch mode to prolog if necessary (with the "prolog" command). Then type wro ng(this, fact) You will get a SYNTAX ERROR message; Logic telling you that the input is grammatically bad. That illustrates what I said in the previous section about spaces inside names. You have in fact seen syntax errors before, when you typed sentences the Tutor could not understand. The error messages generated for bad Prolog do look harder to understand than those generated for bad Logic. That's because I designed the Logic messages for novices, whereas the Prolog ones were intended for hardened hackers. However, one thing is common to both. If you type a bad Prolog fact, the Tutor will store it for later changing. And, as with Logic, it will show pointy brackets around the text. ~11 However, although spaces INSIDE things are bad, spaces BETWEEN them are alright. So you can type a fact like that below without its being misunderstood or rejected. We say that the Prolog language is what computists call FREE FORMAT, because spaces are allowed between items. You are also allowed to break the line between items: but once again, not inside them. So the spaces and line breaks below are OK: good( this, fact ). ~12 But, as a matter of programming style, note that the typographical freedom which free format allows is often abused. badly laid - out pro- grams can be difficult to read ,understand and , modify ! ~13 I've shown you how to write unconditional facts in Prolog. This works the same whether the items in brackets are names or variables - they still go inside the brackets, separated by commas. Variables still start with upper case, and names of things with lower case. This convention does not change between Prolog and Logic. If you examined how conditional facts look in Prolog, you'll have seen that the "if" becomes the ":-" symbol. In case that's not clear on screen, the first character is a colon (one dot on top of another), and the second is a minus (not an underline). So ":-" is how Prolog writes "if". Check this by switching into Logic, typing in a fact like john loves X if X likes wine. and observing its Prolog equivalent. ~14 Which should have come out as loves(john,X) :- likes(X,wine). You can see that the order of parts remains the same: what's before the "if" in Logic is before the ":-" in Prolog, and similarly for what's after it. You must not have a space in the middle of the :- symbol. This is incorrect: loves(john,X) : - likes(X,wine). ~15 Now, how is "and" translated? If you haven't already done so, try a conditional fact like mary loves X if X likes beer and X likes chip_butties. ~16 That should come out as loves(mary,X) :- likes(X,beer), likes(X,chip_butties). Notice that the "and" has become a comma. That's confusing, because comma also separates the items inside brackets. It would have been easier for us if "and" were written as "&". However, Prolog can tell the difference between the two uses of comma. The original implementors chose comma for "and" for historical reasons, (tr.: hardly anyone knows why, but everyone thinks it a pointless decision); this notation is now so widespread that no-one will change it just to make life easier. ~17 ( Actually, it seems that comma-meaning-and may derive from the notation used in formal grammars. If you have done any linguistics, you may have seen notations like sentence <-- noun_phrase, verb_phrase, noun_phrase meaning that A sentence can be a noun phrase followed by a verb phrase, followed by a noun phrase. Grammars are often written in this style. Prolog started life partly as a tool for the grammatical analysis of natural language, and in this incarnation it used comma as above. The notation appears to have been kept when it became a fully-fledged logic programming language. Comma-meaning-argument-separator is conventional mathematical usage. ~18 The use of ":-" for "if" is also obscure. Fernando Pereira, one of the experts behind Prolog, recalls that when the influential DEC-10 Prolog was being designed in the mid-70's, the symbol "<-" was considered for this purpose but rejected; it looked bad on many printers of the time because the "-" did not align with the point of the "<". In these days when almost every PC can display Japanese, it may seem odd that the proper logic symbols weren't available. But computer character sets used to be very limited. They started life in the punched-card machines devised by Herman Hollerith at the end of last century for the US Census. These only had the digits and two other characters. Somewhere around the 1930's, when such machines had become widely used in accounting, new ones were designed that could punch letters (capitals only, of course) as well as digits; sometime in the 1950's, some extra punctuation marks were added for use in commercial programming languages. Through all this, the same basic way of encoding characters as patterns of punched holes had continued! In the 1960's and 70's, the lower-case letters and some extra maths symbols got added, and character sets started to move away from the restrictions imposed by punched cards. But the large investment in existing computers, printers, and other equipment meant that they were never properly redesigned to suit the needs of logic, or indeed of anything else that went beyond the ideas in "total pay equals hours worked times hourly pay". ~19 To finish this historical digression with a story from Stephen J. Gould: Vets nowadays look after pet cats and dogs. The original vets tended farm animals, many of which were beasts of burden. Such beasts tend to be old, hence better able to carry a load: thus the derivation of "vet", from Latin "vetus" (old) through "veterinae" (cattle). Programming languages too abound in senseless signs of history. ) ~20 Now, can you guess how to ask questions in Prolog? In fact, they translate in the same way as facts, except that they end with a question mark and not a dot. So the Logic question mary loves john? would translate as loves(mary,john)? Please note that this convention of ending with a ? is peculiar to the Logic Programming Tutor - it does not carry over to Prolog without the Tutor, as you will learn later. In questions, "and" becomes a comma, just as in rules. ~21 When replying to questions, Prolog pauses after each answer. If the question contains variables, Prolog then asks you More (y/n) ? If you type "y" followed by RETURN, it will try and find another solution. If you type "n" followed by RETURN, it won't. Unlike Logic, it does not display all the solutions in one go. One reason for this is that sometimes you only want one solution. Looking for the others wastes computer time. Practice asking questions by restoring the "relations" knowledge base. Make sure you're in Prolog mode, and ask a question like is_a( Person, Sex )? See how the answers appear one by one. ~22 From now on, I want you to work in Prolog only. When you start up your Logic Programming Tutor, switch it into Prolog mode with the command "prolog" before doing anything else. You have now reached the end of the third lesson. Supplement 3 will give you some more practice with Prolog syntax.