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. ------