TEACH BOOLEANS Aaron Sloman, Nov 1998 FIRST DRAFT! PLEASE REPORT ANY ERRORS TO A.Sloman@cs.bham.ac.uk CONTENTS - (Use g to access required sections) -- Introduction -- History of truth-values -- Unary and binary operations on booleans -- Booleans in Pop11 -- The notation -- Defining new predicates for use in conditions -- Surrogate booleans -- Examples using "not" -- NOTE for experts: non-boolean results of "and" and "or" -- Returning false to represent failure -- Recognising booleans: isboolean -- Booleans in other languages -- Booleans and conditionals -- not( ) and "unless" -- Booleans in loops -- Boolean operators in Pop-11 -- -- "not" in Pop-11 is just a procedure -- -- "and" and "or" in pop-11 are syntax operators -- WARNING: don't use "or" and "and" with PARTS of conditions -- Predicates -- Conditionals and the stack -- More examples of boolean expressions -- Equality tests: "=" and "==" are boolean operators -- Infix predicates on numbers -- User-defined recogniser predicates -- Procedures taking a boolean predicate as argument -- -- Defining find_one(list, pred) -> result -- -- Defining find_all(list, pred) -> found -- Note on procedures (functions) as "first class" objects -- Additional reading -- Introduction ------------------------------------------------------- A programming language always has a collection of data types which it makes available, possibly an extendable collection. E.g. Most languages allow you to create and manipulate objects of the following types: integers e.g. 0, 300, -300 real numbers (floating point numbers, decimals) e.g. 0.5, 300.0, -300.0, 1234.5e50 (see TEACH DECIMALS) strings e.g. 'astringofletters', 'asd*&*^^&*asdf asdfad junk' procedures and many also allow the use of lists, vectors, arrays, records, class hierarchies, etc. Those are the DATA TYPES supported by the language. (A full overview of the data types in Pop-11 is available in REF DATA, written for experts. A simpler overview is in Chapter 2 of the Pop-11 Primer.) BOOLEANS are a very special data type, either implicitly or explicitly available in all languages, since they are required for conditional instructions, which are available in all languages. However there is much diversity in the way those languages use booleans, and in some cases there is potential confusion because things which are not booleans are systematically interpreted as if they were booleans! Everyone who has ever defined a procedure using "if...then...." has some sort of implicit understanding of booleans, but not everyone has a fully explicit grasp of what is going on. Reading this file should help to deepen your understanding. Later some warnings are given, describing common mistakes involving the use of booleans. -- History of truth-values -------------------------------------------- The boolean objects true and false are sometimes referred to as "truth-values". The key ideas were first explored in depth by the 19th century British logician George Boole, which is where the name "boolean" comes from. Booleans are also sometimes called "truth-values" for reasons which will become clear. Boole showed that if you assume that there are two distinct objects, which we can call TRUE and FALSE, then there are interesting and useful ways of defining operations on them. For now we don't need to know what the objects are, just that there are two of them. They could be the numbers 1 and 0, the letters "T" and "F", two physical objects such as the moon and the sun, or two abstract objects analogous to numbers but different. The point is it doesn't matter WHAT they are, as long as there are only two of them. We'll temporarily use the single letters T and F to refer to them. Boole investigated truth-functional operators like "not", "and" and "or" which operate on and transform truth-values. The German logician Gottlob Frege extended Boole's ideas by showing that many linguistic expressions can be thought of as if they were functions or procedures that produce truth-values as results. E.g. A sentence of the form The ball is red could be interpreted as having the logical structure is_red(the_ball) where is_red is a procedure which takes in objects and returns the result true for objects with the colour red, and the result false for objects of any other colour. Such a procedure, which takes one or more inputs and returns a boolean result is called a PREDICATE. These ideas have had a profound influence not only on the development of logic but also on the development of computer programming languages. We'll start by explaining (briefly) how truth-functional operators work, and later discuss predicates, including "recogniser" procedures. All of these can play a role in the construction of conditional instructions in programming languages. They are also used in looping instructions to decide when looping behaviour should terminate. -- Unary and binary operations on booleans ---------------------------- The simplest operation on booleans is the function "NOT". It takes in a boolean (true or false) as input and returns the other one as its result. It can be defined thus: NOT(F) = T NOT(T) = F Alternatively, it can be defined as follows by a truth table, where "p" is a variable that ranges over the booleans, i.e. its value can be T or F. p NOT(p) T F F T This has exactly the same meaning as the two equations above. Some boolean operators take in more than one boolean (truth value) e.g. two of them, and return one result. A familiar example is AND, which can be defined by four equations, or a truth table with four rows: Equations: AND(T, T) = T AND(T, F) = F AND(F, T) = F AND(F, F) = F Truth table (where p and q are boolean variables): p q AND(p,q) T T T T F F F T F F F F (Check that all the possible combinations of values of p and q have been covered). Another familiar binary boolean operator is OR. It takes in two booleans and returns one, which is T if either or both of the inputs are T. Write down its equations and its truth table, to check that you understand. How many other binary boolean operators can be defined? To work out the answer note that in the truth table for a binary operator the first two columns are always the same: i.e. they have four rows covering all combinations of two truth values. Only the final column, containing four truth-values, can be varied from one operator to another. So the number of binary truth-functional operators is the same as the number of possile final columns composed only of Ts and Fs. How many is that? It should be clear that there are also ternary boolean operators which take three boolean values as input and return one as a result. More generally there are n-ary operators which take in n booleans and return one boolean result. How many rows does a truth-table for an n-ary boolean operator have? How many different possible n-ary boolean operators are there? The answers are at the end of this section. An example would be an operator which could be called ALL_6_TRUE which takes in six booleans, and returns T if all six are T, and returns F for all other cases. This is a generalisation of AND, which might have been defined as ALL_2_TRUE. How big would the truth table for ALL_6_TRUE have to be? Likewise we can think of OR as AT_LEAST_1_OF_2_TRUE and that could be generalised by replacing 2 with 3, or 4, or 5, etc. For our purposes, we can ignore n-ary operators where n is bigger than 2. It is useful to understand the unary operator NOT, and the binary operators AND and OR. ANSWERS to questions (it is not essential to understand this bit): 1. A binary operator has four rows, so there are four truth-values in its final column. If you consider all possible ways of filling that final column there are 2 choices for the first position, 2 for the second, and so on. So the total number of combinations is 2x2x2x2, i.e. 4 2 = 16 2. An n-ary operator has n columns. So each row has n truth-values. The previous argument shows that the number of possible combinations of n truth values, i.e. the number of rows will be: n 2 In Pop-11 that is written: 2**n So if there 3 columns there are 8 rows. If there are 4 columns there are 16 rows, and so on. n 3. If there are n columns there are 2 rows, so that is the number of locations in the final column. The total possible number of ways of filling up those locations, i.e. the total number of possible final columns for an n-ary operator is therefore: n 2 2 which, in Pop-11 is written 2**(2**n) Thus for n = 1, there are 2**(2**1) = 4 possible unary operators Thus for n = 2, there are 2**(2**2) = 16 possible unary operators Thus for n = 3, there are 2**(2**3) = 256 possible unary operators Thus for n = 4, there are 2**(2**4) = 65536 possible unary operators -- Booleans in Pop11 -------------------------------------------------- Pop-11 has two booleans. They are not words or strings or numbers or anything else. They are special objects. They have names which are the words "true" and "false" which are reserved Pop-11 identifiers. You can print out their values, thus: true => ** false => ** When the Pop-11 printing procedure prints a boolean it uses angle brackets, as in "", to remind you that these are special objects, not the words "true" or "false". You should not use the angle brackets to refer to the booleans: that is merely a printing convention. You simply use their names, as illustrated above, and below. Pop-11 has a number of built in procedures which can be used to operate on booleans, including "not", "and", "or", described below. However the most important fact about booleans is how they work in conditional expressions, or, in other words, their role in contexts like these: if then ... elseif then ... unless then ... The role of boolean expressions in conditionals is explained below. -- The notation ---------------------------------- I use "" to stand for any expression which Pop-11 treats as referring to a boolean. That includes the simplest boolean expressions, namely the expressions containing just the names of the the two truth-values true false and also more complex expressions, such as these, all of which evaluate to true or false (provided that the variables involved have appropriate values and do not cause mishaps): x = y x > 50 random(100) > 50 isword(item) isinteger(item) length(list1) > length(list2) list matches ![is_at ?x ?place] null(list) alphabefore(word1, word2) Note: in Pop-11 alphabefore is a binary predicate, returning true or false. It takes two words, or two strings, or a word and a string and returns true if the first argument is alphabetically earlier than the second, provided that the characters are all lower case or all uppercase. If some of the characters are uppercase and some are lower case, it treats the upper case characters as coming alphabetically before the lowercase characters because in Pop-11, like many other languages, characters are represented by their numeric ascii codes, and all the upper case characters correspond to smaller numbers for historical reasons. So alphabefore("dog", "cat") => ** alphabefore("Dog", "cat") => ** -- Defining new predicates for use in conditions ---------------------- It is often convenient to define new unary or binary predicates for use in conditional expressions. A unary predicate (like isstring, isnumber, isword, islist, null) can be used to test some object to see whether it is of a certain type or has a certain feature. A binary predicate takes two objects and performs some test comparing or relating them. Examples follow: define is_long_item(item) -> boole; ;;; recognises items of length > 30 if length(item) > 30 then true -> boole; else false -> boole; endif enddefine; is_long_item([a b c d]) => ** is_long_item('the length of a string is the number of characters')=> ** The above procedure definition can be abbreviated, thus: define is_long_item(item) -> boole; ;;; recognises items of length > 30 length(item) > 30 -> boole; enddefine; or even thus: define is_long_item(item); ;;; recognises items of length > 30 length(item) > 30 enddefine; Here is a definition of a binary predicate to decide whether the first item is longer than the second; define is_longer(item1, item2) -> boole; length(item1) > length(item2) -> boole; enddefine; is_longer([a [b c d e] f g], [a b c d]) => ** is_longer('cat', [the cat]) => ** (Why is that true?) -- Surrogate booleans ------------------------------------------------- Pop-11, like many other languages, has a feature which at first can be rather confusing, but turns out to be useful sometimes, namely, anything which is not a boolean is, in certain contexts, treated as a boolean. To be more precise it is treated as if it were the boolean true. Thus you could say that besides the real booleans, true and false, Pop-11 treats everything else as a boolean, a surrogate for true. Here is a demonstration: if 3 > 4 then "yes" else "no" endif => ** no if 5 > 4 then "yes" else "no" endif => ** yes if 5 then "yes" else "no" endif => ** yes if [cat] then "yes" else "no" endif => ** yes if false then "yes" else "no" endif => ** no if "false" then "yes" else "no" endif => ** yes Notice that in the last case, it treats the word "false", which is NOT a boolean (because it is a word) as true. In the preceding case it was using not the word "false" but the VALUE of the word "false" and the value is false, the boolean. Feeling confused? Try writing that down in your own words, without looking at the paragraph, then compare what you have written with what's there. NOTE: in treating all non-false items as surrogate booleans Pop-11 is not unusual. Even languages which don't have a boolean data-type have a special object which is treated as false (e.g. the integer 0 in C, or the empty list NIL in Lisp) tend to treat anything else as if it were true. Other languages are discussed below. What that means is that if a expression E occurs in the role of a condition (e.g. between "if" or "elseif" and "then", or between "until" and "do") then if E returns a non-false value when it is evaluated, it will produce the same effect as if it had produced true. We'll see below how this can be useful. -- Examples using "not" ----------------------------------------------- Another context in which a non-false expression will be treated as if it were true is as input to the procedure not: E.g. not(true) => ** not(99) => ** not("cat") => ** not([The cat sat on the mat]) => ** true and false => ** true and "cat" => ** cat false or 99 => ** 99 99 or false => ** 99 false or not(true) => ** Exercise: what will be the effect of a double negation on a non-boolean object: not( not([The cat sat on the mat]) ) => After deciding what value you think this should produce, try it. -- NOTE for experts: non-boolean results of "and" and "or" ------------ In pop-11, "and" and "or" are similar to "not" and "if ... then" in treating anything non-false as if it were true, except that when the result would normally have been true, they return the last argument treated as true, rather than true itself. Look carefully at these examples. true or false => ** 5 or false => ** 5 true and false => ** 5 and false => ** true and true => ** true and 5 => ** 5 If you don't follow this, it is probably best to ignore it for now. -- Returning false to represent failure ------------------------------- Because Pop-11 treats any non-false value value as true it is sometimes useful to write a program which attempts to solve a problem, and if it works, returns the object which is the solution (a number, or list, or word, etc.) but if it fails returns the boolean, false. For an example see the procedure solve_tower, in TEACH TOWER, or the procedure solve_problem in TEACH SEARCHING Here is an example: a procedure which searches down a list looking for a word. If it finds one it returns that word and stops. If it finds no words it returns false: define find_word(list) -> found; lvars item; for item in list do if isword(item) then item -> found; return() endif endfor; ;;; failed so false -> found enddefine; find_word([1 2 3 4 five six seven]) => ** five ;;; But strings are not words, so find_word([1 2 3 4 'five' 'six' 'seven']) => ** Because this sort of procedure returns the result false when it fails, it can be used inside a conditional, as follows. define check_word(list); lvars found; find_word(list) -> found; if found then [The word ^found was found] => else [No word was found] => endif; enddefine; Notice the two uses of the variable "found". First it is used as a conditional expression, between "if" and "then". Later it is used to insert its value in the list to be printed out. For the first purpose it is treated as a boolean or a surrogate boolean (when it is not false). For the second purpose it is treated as an ordinary variable whose value is a word. This procedure can be abbreviated a little, using Pop-11's non-destructive assignment arrow "->>" which does an assignment, like "->" and also leaves on the stack whatever it assigns. I.e. x ->> y; is equivalent to: x -> y; x; We can use "->>" in a conditional, as follows: define check_word(list); lvars found; if find_word(list) ->> found then [The word ^found was found] => else [No word was found] => endif; enddefine; check_word([1 2 3 4 five six seven]); ** [The word five was found] check_word([1 2 3 4 'five' 'six' 'seven']); ** [No word was found] (See TEACH STACK for more on the stack.) The above was a trivial example, but that sort of use of "->>" with a value that can be either false or a solution to a problem is often used in a multi-branch conditional expression, to reduce the need for nested conditionals, e.g. lvars found; if find_word(list) ->> found then [The word ^found was found] => elseif find_string(list) ->> found then [The string ^found was found] => elseif find_number(list) ->> found then [The number ^found was found] => else [No word string or number was found] => endif; Alternatively, without using "->>", this could be expressed far more verbosely, thus: lvars found; find_word(list) -> found; if found then [The word ^found was found] => else find_string(list) -> found; if found then [The string ^found was found] => else find_number(list) -> found; if found then [The number ^found was found] => else [No word string or number was found] => endif; endif; endif; This more deeply nested structure is harder to get right first time and is harder to read than the previous version. That is one reason why the non-destructive assignment arrow is often useful. -- Recognising booleans: isboolean ------------------------------------ As explained above, Pop-11 has a special data-type for booleans, and there are exactly TWO things of that type, true and false. The unary predicate isboolean is a RECOGNISER predicate because it recognises things of type boolean. It returns true if applied to them, and false if applied to anything else, just as isword recognises words and isinteger recognises numbers. isboolean(true) => ** isboolean(false) => ** isboolean(3 > 4) => ** isboolean(4 > 3) => ** ;;; But words and numbers are not booleans isboolean("true") => ** isboolean(0) => ** isword("true") => ** isnumber(0) => ** -- Booleans in other languages ---------------------------------------- Not all languages have a boolean data type. Instead they often have only "surrogate" booleans. In many other languages (e.g. C, C++, and the language Pop2 from which Pop-11 was derived) the numbers 1 and 0 are used as booleans. So instead of returning false, an operator in such a language would return 0, and instead of returning true it would return 1. In Pop-11 an expression of the form x > y will always return a boolean, true or false. In many other languages it will return 1 or 0. In the AI language Lisp (and its derivatives, like Scheme) there is also no boolean data type, but instead of numbers two words (known as symbols) are used as surrogate booleans, namely the word "T" and the word "NIL". The latter word is also used as the empty list, which in Pop-11 would be []. (NOTE: in Lisp, the symbols would be written using single quotes, as 'T' and 'NIL', or, omitting the closing quote, as 'T and 'NIL. Since Pop-11 uses the single quote for strings, I'll go on using the double quote when referring to Lisp symbols.) In other words, in Lisp-like languages, the empty list, namely the symbol "NIL", is treated as false, and the word "T" is treated as true. The reason for this choice is that it can make some list processing loops go faster, just as in other languages the use of 0 for false can make some arithmetic loops go faster. The language ML (available in Poplog as PML) has a boolean data type, with two instances, true and false, but it is much stricter than any of these other languages, in that it will not allow any other type of object to be the value of a conditional expression. For example, in ML if you type if 3*4 = 10+2 then "yes" else "no"; the outcome is: val it = "yes" : string But if you type if 99 then "yes" else "no"; You'll get the following Error: in expression if 99 then "yes" else "no" The value 99 : int is not a boolean It is arguable that ML is a "cleaner" and safer language than any of the others discussed here. (But perhaps not quite as flexible and easy to use as Pop11!) -- Booleans and conditionals ------------------------------------------ Why are booleans so important? Because they are used to control the behaviour of flexible programs which do not simply run a fixed set of instructions. If you solved the river crossing puzzle in TEACH RIVER you will have produced a fixed set of instructions which enable the farmer, the fox, the chicken and the grain to be moved to the opposite bank, without the chicken eating the grain or the fox eating the chicken. Your instructions did not need to TEST any condition and do one thing if the condition is satisfied (i.e. is true) and another if it is not satisfied (i.e. is false). The program is very rigid. Every time you run it it does the same thing. However if you developed an Eliza-like program as in TEACH RESPOND then in order to make it flexible you will have used a multi-branch conditional expression e.g. if input = [i hate computers] then [perhaps you hate yourself] -> result; elseif input = [are you intelligent?] then [do i seem intelligent?] -> result; elseif input matches [== can you ==] then [i will try to help] -> result; elseif input matches ![i want to ??x] then [i would not advise you to ^^x] -> result ..... The behaviour of such a program is not always exactly the same. What it does DEPENDS on whether the conditions between "if" or "elseif" and "then" come out true or not. I.e. it is a more FLEXIBLE, or CONTEXT SENSITIVE program than the river-crossing program, which simply has a fixed list of instructions. How was that flexibility achieved? Essentially it depended on the fact that the infix operators "=" and "matches" (each of which is a procedure taking in two arguments and producing one result) are boolean-valued. I.e. although their inputs don't need to be booleans they always produce a boolean result, i.e. true or false. You can check this: 3 = 4 => ** 3*4 = 4*3 => ** [the cat] matches [the cat] => ** [the cat] matches [= cat =] => ** What about [the cat] matches [== cat ==] => (Compose some more tests, work out their results, and get Pop-11 to check them for you.) -- not( ) and "unless" ------------------------------------ While we are on the topic of conditional instructions it is worth mentioning that Pop-11 provides the syntax word "unless" and its closing bracket "endunless" to enable you to avoid the use of "not" in Negative conditions. For instance a command of the form: if not( matches ) then .... endif; can be expressed as: unless matches then .... endunless; This is slightly more compact, and may be easier to read. Similarly expressions of the form: elseif not( ) then can always be replaced with: elseunless not( ) then This may sound odd, but remember that programming languages are not English, and when they sound like English that may be a cause of confusion! See HELP CONDITIONALS for more on this. -- Booleans in loops -------------------------------------------------- Booleans are used not only in conditional instructions but also in tests for termination of loops. These are implicitly conditional instructions. For example a looping expression of the form until do enduntil; is equivalent to repeat if then quitloop() endif; endrepeat; And while do endwhile; is equivalent to repeat if not() then quitloop() endif; endrepeat; Incidentally, the instruction if then quitloop() endif; can be abbreviated thus: quitif( ); and if not() then quitloop() endif; can be abbreviated as quitunless( ); (See also HELP LOOPS) -- Boolean operators in Pop-11 ---------------------------------------- -- -- "not" in Pop-11 is just a procedure not(true) => ** not(false) => ** Try applying not to more complex boolean expressions, and see what happens. Try applying it to other things, like numbers and words, and see how it treats them as surrogate booleans. -- -- "and" and "or" in pop-11 are syntax operators The words "and" and "or" in Pop-11 are partly like the binary boolean operators AND and OR mentioned above, except that they are defined as INFIX operators, which can be used only between their arguments, and they also have another subtle feature, which is that they don't do more work than necessary: true and true => ** true or false => ** not(true) or false => ** not(true) or not(false) => ** (Make sure you understand how those results are arrived at. Compose some more boolean expressions combining true, false, not, and and or, work out their truth-values and then use pop-11 to check that you have got them right.) What is meant by not doing more work than necessary? Consider the following, which uses the arithmetical operator + : true or "six" + "seven" => You may be surprised to find that that evaluates to TRUE, even though the expression "six" + "seven" would produce a mishap "six" + "seven" => ;;; MISHAP - NUMBER(S) NEEDED ;;; INVOLVING: six seven ;;; DOING : + ... When that erroneous bit of code occurs to the right of "or" it has no effect. The reason is this. In Pop-11 "or" is defined to check its first argument, and if that evaluates to something non-false, then it doesn't evaluate the second argument, since both "T or F" and "T or T" evaluate to T. So once T is on the left of "or" there is no point working out what is on the right. Likewise since both "F and T" and "F and F" evaluate to F, once a false value has been found on the left of "and" there is no point evaluating what is on the right, since whether it is T or F makes no difference. If the first argument of OR is true, then no matter what the second argument is, provided that it is a boolean, OR should return true. OR doesn't do any unnecessary evaluation of its arguments, and consequently it does not discover that its second argument would have produced a mishap. Likewise "and" in Pop-11 does not do any more evaluation than it needs to do, so where its first argument evaluates to false, it doesn't need to evaluate its second argument, because the result must be false. not(true) and "six" + "seven" => ** This "lazy" feature of "or" and "and" is very common in programming languages and can often lead to considerable efficiency gains, because computations to work out unnecessary information are avoided. If you use a typed language (Java or ML) the compiler would discover at compile time that "six" + "seven" is ill formed, and give a compile time error message. But in general the second argument to "or" or "and" might be something which sometimes does and sometimes does not give a run time error which the compiler cannot detect in advance. It may even be an expression whose evaluation never terminates (an infinite loop, whose termination condition is never true in certain contexts). No compiler can tell in general whether an expression terminates. (That is the halting problem.) All this can mean that the first argument for "and" or "or" can be used as a "guard" against an error in the second, e.g. false and ("cat" + "dog") => ** It is best to treat "and" and "or" as abbreviated versions of conditional expressions. I.e. the above is equivalent to if false then ("cat" + "dog") => else false => endif which produces the result false, and never runs the instructions after "then". Languages with this "lazy" feature which stops them going beyond the first argument to "or" and "and" can prevent a run time error turning up, or an infinite loop holding up the program, or a very long but irrelevant computation being performed. They do so because the second argument is ignored in those cases. This is often very useful, but will not be discussed further now. -- WARNING: don't use "or" and "and" with PARTS of conditions --------- A common mistake made by beginners (and some non-beginners when they are a bit tired...) is based on the following: you can combine conditionals using "or", and "and". People assume that you can also combine parts of a conditional, because that's what you would do in English, or some other natural language. For example we can say John is British if John was born in Britain or John was naturalised and this can be abbreviated to John is British if John was born in Britain or naturalised But that sort of abbreviation is not generally allowed in programming languages. Suppose you are testing a variable x and you want the same behaviour to be produced if its value is 5 as if it is 50. You can achieve this by including two conditional branches and repeating the relevant instruction. if x = 5 then process(x) elseif x = 50 then process(x) else ... To avoid writing the same action twice you can use "or" to join the two conditional expressions, as follows: if x = 5 or x = 50 then process(x) else ... Pop-11 will try the first test before "or" and if it comes out true will jump to after "then". If the first test is false, then it tries the test after "or", and if that is true it performs the action after "then". If both tests fail, then it performs the action after "else". You can us "or" several times to combine several tests. E.g. if x = 5 or x = 50 or x = 500 or y > x then process(x) It may be clearer to write each condition on a separate line. if x = 5 or x = 50 or x = 500 or y > x then process(x) The mistake people sometimes make is to repeat only part of the conditional expression after "or". E.g. if you write if x = 5 or 50 then process(x) you might expect someone who speaks English to interpret that as equivalent to if x = 5 or x = 50 then process(x) But computers DO NOT (YET) SPEAK ENGLISH. The first expression will do process(x) no matter what the value of x is. Why? Think about it before reading on. if x = 5 or 50 then process(x) will always do process(x) because the expression "x = 5 or 50" is always equivalent to TRUE (i.e. non-false) no matter what the value of x is. Check that out. On the other hand the expression "x = 5 or x = 50" will be false if x has any value other than 5 or 50. Similar comments can be made about joining conditions using "and". For example you may wish to do something if a list contains both the words "big" and "blue". You can write this as if member("big", list) and member("blue", list) then else endif; This is equivalent to the following more complex expression which does not use "and": if member("big", list) then if member("blue", list) then else endif; else endif; Check that this will perform action1 and action2 in the same situations as the previous version. However you cannot abbreviate the above as if member("big" and "blue", list) then else endif; even though in English you might say something like: if "big" and "blue" are members of the list then But Pop-11 is not a dialect of English. Likewise, don't replace things like if matches and matches then with if matches and then The behaviour will be quite different. Similarly with "or". -- Predicates --------------------------------------------------------- Extract from TEACH SETS2: Here is an introduction to an important concept from logic. A predicate is a procedure which produces the result TRUE or FALSE. I.e. its result is a "boolean" object. Standard predicates in POP11 include ISINTEGER, ISPROCEDURE, ATOM, ISWORD. These are "recogniser" predicates can be applied to any object at all, no matter what its type. Some predicates (like ODD and EVEN) defined below can be applied only to a restricted class of objects (e.g. numbers). Predicates are frequently used in IF or UNLESS expressions, e.g: IF ISINTEGER(X) THEN ... ELSE ... ENDIF UNLESS ISWORD(X) THEN ... ELSE ... ENDUNLESS That is because the conditional expression that occurs before THEN should evaluate to a result that is true or false. o If it is false then the instructions following THEN will not be obeyed. o If it is true, or anything else other than false, then the instructions after THEN will be obeyed. This means that in POP-11 any object can count as TRUE, as long as it is not the unique object FALSE. Here is a predicate to decide whether a number is bigger than ten: define aboveten(number) -> boolean; number > 10 -> boolean enddefine; Notice that this produces a result, which is left on the stack. The result is in fact the result of the operator ">", i.e. TRUE or FALSE. The operator ">" leaves its result on the Pop-11 stack. It is then assigned to the local variable boolean. However that is an output local so when aboveten finishes running the value of boolean is put on the stack. That is then the result of the whole procedure. Test it /* aboveten(3) => ** aboveten(10) => ** aboveten(11) => ** aboveten("cat") => ;;; MISHAP - NUMBER(S) NEEDED ;;; INVOLVING: cat 10 ;;; DOING : > aboveten .... */ Some people prefer the functional style of programming where an output local variable is not used, as here: define aboveten(number); number > 10 enddefine; I.e. the result of the procedure is whatever the result is of the expression number > 10 -- Conditionals and the stack ----------------------------------------- From the Pop11 Primer, Chapter 3: Previously we noticed that the use of a conditional like if x = 10 then x => endif depended on the fact that "=" is a predicate, i.e. a procedure producing a boolean result. This result is left on the stack. You can think of a conditional imperative of the form if then endif as being roughly equivalent to something like the following: 1. Put value of on stack 2. If the top element of the stack is true perform the , otherwise jump to after 'endif'. This means that if the expression between 'if' and 'then' produces no result, then an error will occur. For example, "3 = x" produces a boolean result, whereas the assignment "3 -> x" is simply an imperative, and does not produce a result, so: if 3 -> x then x => endif; ;;; MISHAP - ste: STACK EMPTY (missing argument? missing result?) The portion of Pop-11 between 'if' and 'then' produced no result. (If "->>" is used instead of "->" then a result is produced, as explained above.) Strictly speaking, Pop-11 is defined so that anything other than false can be used as equivalent to true in a condition: if 99 then 66 => endif; ** 66 For this reason it is sometimes convenient to define a procedure so that it returns either false or some object it is discovered. For example, a procedure which searches down a list looking for a word, and if it finds it returns that word as its result, otherwise returns false. We gave an example previously in the procedure find_word. For more on the Pop-11 virtual machine see TEACH VM -- More examples of boolean expressions ------------------------------- As explained above, two built in identifiers are provided to refer to the two boolean values: true, false => ** Many other expressions are capable of denoting boolean values, e.g. the result of applying a recogniser procedure to an arbitrary object, or the result of applying an equality test to two objects or an arithmetical comparison to two numbers. Here are several examples of boolean-valued expressions: true, false, 66 == 66, 66 == 99, 77 < 33, "cat" = "dog", isinteger(true), isboolean(99), isword("cat"), isstring('cat'), member(3, [a b c d]), list matches [you are ??words] -- Equality tests: "=" and "==" are boolean operators ----------------- Writing two expressions on either side of an equality operation produces a new expression, which denotes a truth-value, TRUE or FALSE. In other words = and == each take two arguments and produce one BOOLEAN result. 5 == 3 + 2 => ** [a b c] = [a] <> [b c] => ** [a b c] == [a] <> [b c] => ** The infix operator "==" is similar to "=" but applies a stricter equality test. The two things it is applied to must be the very same Pop-11 object. The operator "=" requires the two things to be exactly similar, but not necessarily the same object. So comparing two lists containing the same words will produce FALSE if "==" if used and TRUE if "=" is used. Similarly if two strings contain the same characters. This is explained further in HELP EQUAL. Words, unlike strings, are 'standardised' in a dictionary, so that you cannot have two different words with the same characters. If you attempt to type in a second one, Pop-11 will find the original in its dictionary, and assume you wanted to refer to it. So both the following are TRUE: "CAT" == "CAT" "CAT" = "CAT" By contrast only one of these is true. Which? 'CAT' == 'CAT' 'CAT' = 'CAT' The operators "/=" and "/==" are provided to reduce the need to use "not" with equality tests. E.g. if not(x = y) then if not(x == y) then can be abbreviated as if x /= y then if x /== y then (Note: "unless" could have been used instead, as explained above.) -- Infix predicates on numbers ---------------------------------------- Besides arithmetical operations that take numbers as arguments and produce numbers as results, Pop-11 includes various predicates for testing properties of numbers, or relations between numbers. These predicates all have boolean (i.e. true or false) results. The most widely used infix predicates are: OPERATOR PRECEDENCE DESCRIPTION > 6 test two numbers: TRUE if first greater than second. < 6 test two numbers: TRUE if first less than second. >= 6 test two numbers: TRUE if first greater than or equal to second. <= 6 test two numbers: TRUE if first less than or equal to second. == 7 Exact identity (i.e. the very same object in the machine.) /== 7 Not identical -- User-defined recogniser predicates --------------------------------- We previously saw that Pop-11 provides many "recogniser" predicates, e.g. isword, isinteger, isnumber, isstring, islist, isprocedure. Sometimes you want to recognise something more complex than an instance of a pop-11 data type. E.g. you may wish to define predicates called is_female and is_male which can be applied to database items about people of the form [mary age 20 sex female spouse john job programmer] [john age 22 sex male spouse mary job dressmaker] As long as you define your procedure so that it takes in the list and returns true or false, it can be used as a recogniser. -- Procedures taking a boolean predicate as argument ------------------ Recogniser predicates are often useful in connection with procedures that search for something in a list, or tree, or more complex structure. You can define a GENERIC procedure which given a structure and a recogniser predicate searches the structure for things recognised by the predicate. You can then use the same searching procedure to search for different sorts of things, by giving it different recogniser predicates, instead of having to redefine the procedure for each new type of search. Here are two examples. The first searches for the first item satisfying a recogniser, and the second makes a list of all the items which satisfy it. -- -- Defining find_one(list, pred) -> result We can define a procedure called find_one, which takes a list LIST and a unary predicate PRED and produces as a result either the boolean, false, or the first item in the list which satisfies PRED. find_one([a 1 b 2.5 c 3], isinteger) should return the integer 1 find_one([a 1 b 2.5 c 3], isword) should return the word "a" find_one([a 1 b 'bat' c 3], isstring) should return the string 'bat' find_one([a 1 b 'bat' c 3], isdecimal) should return the boolean false This can be defined as follows: define find_one(list, pred) -> result; ;;; apply pred to each item in the list and if the result ;;; is not false, then return that item. If no such item is ;;; found return false. lvars item; for item in list do if pred(item) then ;;; item satisfies pred, so make it the result, and ;;; finish item -> result; return() endif endfor; ;;; nothing found satisfying pred, so false -> result enddefine; Check that out on the test cases above. -- -- Defining find_all(list, pred) -> found Define a procedure called all_found, which takes a list LIST and a unary predicate PRED and produces as a result a list (possibly empty) containing all the elements of LIST which satisfy PRED. find_all([a 1 b 2 c 3], isinteger) should produce the result [1 2 3]. Try to instantiate the following schema, and test your procedure. define find_all(list, pred) -> found; lvars item; [% for item in list do if .... then .... endif endfor %] -> found; enddefine; -- Note on procedures (functions) as "first class" objects ------------ The procedures find_one and find_all are possible because Pop-11, like many other programming languages, allows procedures to take procedures as inputs. It also allows procedures to return procedures as results. In many languages the word "function" is used to refer to procedures which produce a result. Languages which have the power to define functions which take functions as inputs and return functions as results are sometimes described as "higher order" functional languages. They are also sometimes described as treating functions as "first class objects" especially if functions can also be stored in lists and other data-structures and new functions can be created while programs are running. Pop-11, Scheme, Lisp, ML, Miranda, and Haskell are examples of such languages. The advantage of higher order programming is that it often allows you to define "generic" procedures which can be applied to different sorts of objects, like find_one and find_all. An extremely useful example of a generic procedure in Pop-11 is syssort, described in HELP SYSSORT. It takes a list and a binary predicate and returns a new list which is sorted so that if any pair of objects in the list satisfy the predicate then the first one comes earlier in the list than the second. E.g. syssort([cat mouse dog bat elephant], alphabefore) => ** [bat cat dog elephant mouse] Another useful generic procedure is the concatenator <>. It not only concatenates lists, strings, words and vectors, but can also be used to concatenate procedures. Thus sqrt <> sqrt is a procedure which when applied to a number gets its fourth root. (sqrt <> sqrt)(16) => ** 2.0 rev <> rev is a procedure which when applied to a list produces the reverse of the reverse, i.e. a copy of the original list. (copylist would be far more efficient.) Languages which do not have this high order functional capability require other techniques of programming to be used instead. -- Additional reading ------------------------------------------------- See HELP * AND, HELP * OR, HELP * BOOLEAN TEACH SETS TEACH SETS2 TEACH FUNCTIONAL.STYLE HELP PML (If you want to know more about ML). HELP CLISP (If you want to know more about Lisp) --- $poplocal/local/teach/booleans --- Copyright University of Birmingham 1998. All rights reserved. ------