TEACH SETS                                 Revised Aaron Sloman Nov 1989
                                               Slightly revised Oct 2001

             An INTRODUCTION TO SET MANIPULATION USING LISTS
             ===============================================

CONTENTS

 -- Introduction
 -- Differences between lists and sets
 -- Prerequisites for this teach file
 -- A first example
 -- Checking whether a person has a property
 -- Defining iselement with a "for" loop
 -- Re-doing iselement as a recursive program
 -- Using the matcher to define iselement recursively
 -- How to do it
 -- Words need to be quoted to refer to themselves
 -- Defining the procedure ismale
 -- A procedure to test for two properties: happyman
 -- Finding an item with a property
 -- Using valof
 -- A schema for FINDONE
 -- How to specify a procedure
 -- Specifying internal and external semantics
 -- Using ENTER procheader
 -- Specifying FINDONE
 -- FINDALL
 -- Digression: findintegers
 -- Now let's return to findall
 -- A schema for FINDALL
 -- If you need help
 -- It still doesn't work?
 -- A set of properties: findset
 -- Help with recursive issubset
 -- Some advice on testing
 -- Returning to FINDSET
 -- If you needed help
 -- A different findset
 -- Further reading

-- Introduction -------------------------------------------------------

One common use of a  list is to represent a  set of objects. It is  then
possible to  write programs  that  perform operations  on the  list,  to
represent operations on  the set  represented. The empty  list []  would
then represent the empty set. Sets of sets are then represented as lists
of lists, and operations  on sets of  sets can also  then be defined  as
operations on lists.

For example, the following are common operations on objects (represented
here as O1, O2, O3, ....) and sets represented here as S1, S2, S3, ...):

(1) Test whether O1 is a member of the set S1

(2) Test whether the set S1 is a subset of the set S2

(3) Given an object O1 and a set S1, containing O1, create set S2
containing all the elements of S1 except O1

(4) Given two sets S1 and S2, create the "union" set S3, containing
all the elements that are EITHER in S1 or S2 (or both).

(5) Given two sets S1 and S2 create the "intersection" set S3,
containing all the elements that are in BOTH S1 and S2.

(6) Generalize (4) and (5) as follows: given S, a set containing sets
S1, S2, S3 ... Sn as its elements, create the union of all of S1 to Sn
or the intersection of all of S1 to Sn.

(7) Given two sets S1 and S2, create the "difference" set S3, such that
S3 contains all the objects in S1 that are not in S2

(8) Given an object O1 and a set S containing sets S1, S2,... Sn, create
a new set of sets containing all and only the sets that contain O1.

(9) Define a predicate (a procedure returning a boolean --- true or false
--- result) which tests whether O is a member of S.

(10) Define a predicate which tests whether S1 is a subset of S2.

(11) Define a predicate which tests whether S1 intersects S2, i.e.
whether they have any elements in common (so that their intersection is
not the empty set).

(12) Define a predicate which tests whether S1 and S2 are the same set,
i.e. contain exactly the same elements (not necessarily represented in
the same order in the lists representing the sets).

(13) Given a set S1 and a predicate P create a set S2 containing all the
elements of S1 that satisfy the predicate P (i.e. the set of all the
objects such that P returns true when applied to them).

(14) Given a set S and a predicate P, define a new predicate that
returns true if and only if every object in S satisfies P.

(15) Given a set S and a predicate P define a new predicate that returns
true if at least ONE object in S satisfies P, and false if none do.

(16) Given a set S and a predicate P define a counting procedure that
returns an integer N such that N is the number of objects in S that
satisfy the predicate P.

(17) Given a set S some of whose elements are sets, and some of them
have elements as sets, and some of those sets have elements of sets,
i.e. so that sets can occur to arbitrary depth, create a new set
containing all the "atomic objects" (i.e. the non-sets) that are either
in S or in one of the elements of S or one of the elements of the
elements of S or .... (In short if we think of S as a tree of sets,
create the set of the "leaves" or "tips" of the tree, sometimes called
its "fringe".

These are just illustrations of operations on sets that are often  found
to be useful. There are many more. You could try to extend this list.

AI programming languages often provide built-in or library procedures
that perform these tasks. However, it often turns out that a particular
operation that you require is not available, so it is useful to develop
the techniques required for building procedures to perform such
operations on sets. This will also help to develop general programming
techniques. The exercises in this teach file, in TEACH SETS2 and in
TEACH LISTQUESTIONS are designed to help you develop these techniques.


-- Differences between lists and sets ---------------------------------

Notice that lists are not exactly like sets: for example the items in a
list have an order, whereas sets are just collections of things without
any particular order. Further, lists may have repeated elements, as in

    [Fred John Mary Fred Sue]

whereas sets contain each item only once. For these reasons the use of
lists to represent sets requires some care. For example you can't simply
form the union of two sets S1 and S2 (i.e. the set containing everything
that is in at least one of S1 and S2) simply by concatenating the
corresponding two lists, for that could produce repeated elements, as in

    [Tom Dick Sue] <> [Dick Mary Joe] =>
    ** [Tom Dick Sue Dick Mary Joe]

Similarly, because the order of elements is immaterial in sets, the
two lists

    [Tom Dick Sue]   [Sue Tom Dick]

would represent the same set. So you cannot use the equality tester
"=" or the match operator "matches" to test for whether two sets are
the same.

    [Tom Dick Sue] = [Sue Tom Dick] =>
    ** <false>


-- Prerequisites for this teach file ----------------------------------

Before trying these exercises,  you should be fluent  in the use of  the
editor and know how to mark ranges in files in order to copy them,  load
them etc (TEACH  * MARK, TEACH  * LMR). It  will also be  useful if  you
worked through the following:

TEACH * RESPOND teaches the use of conditionals.

TEACH * LISTS, * DEFINE, * VARS, * MATCHES, * ARROW,
The section on lists in TEACH * PERCENT.

TEACH * ARITH       introduces some "loop" instructions
TEACH * RECURSE1    introduces recursion

You may also find that TEACH * STACK is useful.


-- A first example ----------------------------------------------------

Suppose we want to store  information about several people,  declaring a
variable for each person, and then  assigning a list of descriptions  to
that variable.

E.g. if John is male, happy, single, a clerk and tall, then we could do
the following.

    vars john;
    [male happy single clerk tall] -> john;

and similar things for other people. We could then have a list called
"people" with the names of all the people, e.g.

    vars people;
    [john ethel mary fred] -> people;

You could declare variables and  construct suitable lists of  properties
for the other people. (For now, let's not worry about whether this  is a
GOOD  way  to  represent  information  about  people.  Choosing  a  good
representation for a particular task is often very difficult, and  there
are very many different ways the same information can be represented  in
a computer.)

We now have  the following situation:  the variable "people"  contains a
list of names of people, and for each person the name is also a variable
containing a  list  of  properties  of that  person.  For  example,  The
variable "john" represents information about about John. We should now
be able to write programs to examine those lists, in order to answer
questions, for example:

    Does John have the property "tall" ?
    Does Ethel have the properties "rich" and "clever"?
    Does Fred have either the property "rich" or the property "clever"?

Additional tasks that  you might require  a program to perform would  be
such things as "find all the people  who are tall" (i.e. make a list  of
their names), or "find all  the people who are  tall and either rich  or
happy".

Try thinking about how these tasks break down into sub-tasks. This  will
help you anticipate some of the  problems discussed in the rest of  this
file.

-- Checking whether a person has a property ---------------------------

How can a program check whether a person has a property (using the above
representation of properties)?

We see immediately from the list  assigned to "john" that John is  tall,
but that it is not  known whether he is fat.  How? When asked, a  person
might say  something like  the  following: "Well  I  look at  the  list,
starting at the left  hand end and  going along the  list to the  right,
until I come across  the appropriate word.  If I get to  the end of  the
list before finding the word, I know the property isn't in the list."

Pop-11 includes a built in procedure member, that can be used to perform
this test (try it):

    member("tall", john) =>
    ** <true>
    member("fat", john) =>
    ** <false>

For now, suppose the procedure member  did not exist, and you  therefore
had to define a procedure  called "iselement" that behaved like  member.
How would you do it?

-- Defining iselement with a "for" loop -------------------------------

One easy way  is to use  the built-in "for"  loop mechanism that  Pop-11
provides, that enables you to use the format

    for <variable> in <list> do <actions> endfor;

So you could define a procedure called iselement thus

    define iselement(item, list) -> result;
        ;;; take in one item, and a list, and return a truth value,
        ;;; true if the item is in the list, otherwise false.

        lvars element;

        for element in list do
            if element = item then
                ;;; found it
                true -> result;
                return();           ;;; leave the procedure now
            endif;
        endfor;

        ;;; failed to find the item in the list so
        false -> result;
    enddefine;

(Not all  the  semi-colons  are essential  -  those  immediately  before
closing brackets like "endif", "endfor" and "enddefine" can be omitted.)

Type that in and test it with various combinations of arguments:

    iselement(3, [1 2 3 4]) =>
    iselement(3, [1 2 3]) =>
    iselement(1, [1 2 3 4]) =>
    iselement(3, []) =>          ;;; always check the "empty list case

    vars john;
    [male happy single clerk tall] -> john;
    iselement("tall", john) =>


-- Re-doing iselement as a recursive program --------------------------

Now consider  how you  might  have written  the procedure  iselement  if
Pop-11 had not contained any  looping constructs, like "for ...  endfor"
or "while .... endwhile", "until ... enduntil" etc.

We are going to  assume that "if" is  available (as introduced in  TEACH
RESPOND), and that procedures can be  defined and "called", not only  by
other procedures,  but also  by themselves.  We'll see  that, as  if  by
magic, the procedure iselement can call itself, in order to get the same
effect as a looping instruction.  This is called "recursion". Later  you
will learn that recursion is useful  in some cases where loops would  be
very clumsy.

Before  proceeding you  must  know  about  output  local  variables  (as
explained in TEACH DEFINE). You  will also need to  know how to use  the
procedure HD to  get the  first element  of a list,  and TL  to get  the
"tail" i.e. a list composed of  all but the first element, as  explained
in TEACH LISTS. Thus, if "list" is a variable whose value is a list, and
"item" is another variable,  whose value is anything  (e.g. a word)  the
expression

    item = hd(list)

is a "boolean" (i.e. true or false) expression that will be true if  the
first element  of list  is  the same  thing  as item,  otherwise  false.
(Experienced programmers may  like to look  at HELP *  EQUAL to see  how
POP-11 deals with different kinds of equality.)

Using these ideas, let's  work up to a  new definition of the  procedure
iselement.

Imagine the procedure iselement is running  and that it has input  local
variables item and list, and an output local variable called result, and
the input variables have been given values thus:

    vars item, list;
    3 -> item;
    [1 2 3 4] -> list;

How can  we check  if item  is in  the list?  We can  first see  if  the
following is true

    item = hd(list)

is it?

If it is true, then all the  procedure iselement has to do is to  assign
true to its output local variable, and then stop.

Otherwise, if it isn't true, then it can do the same test on the tail of
the list, i.e.

    item = hd(tl(list))

If that is true it  can assign true to result  and stop. If not then  it
has to check the next thing in the list

    item = hd(tl(tl(list)))

But how many times will it have to do this? Without knowing the lengths
of the lists we can't tell. And if we want the procedure to work on
lists of ANY length, then we need some way of going on indefinitely.

Now, if the  procedure we  are defining  already has  an instruction  to
compare item  with  hd(list)  (as above),  then  instead  of  explicitly
looking at the head  of the tail of  the list and then  the head of  the
tail of the tail, etc, it can just call itself "recursively". There's
the magic (until you get used to it).

Thus we can come up with the following schema (which has a bug, but will
work in some cases):

    define iselement(item, list) -> result;

        if item = hd(list) then
            true -> result;
        elseif iselement(item, tl(list)) then
            ;;; the item was found (somewhere) in the recursive call, so
            true -> result;
        endif;

    enddefine;

Try  defining  that.  Notice  that  the  embedded  (recursive)  call  of
iselement has to take TWO arguments, because iselement is being  defined
as a procedure that takes two arguments. Notice also that the  recursive
call can succeed (produce TRUE) not  just because the very next  element
in the list matches item, but because a later one did.

It should already be clear that something is wrong, because there is  no
case in which FALSE is assigned to the result.

Nevertheless, you can compile that procedure then test it:

    iselement(3, [1 2 3 4]) =>
    iselement(3, [1 3]) =>

So far so good. You can even see how it works if you trace the procedure
and redo those commands.

    trace iselement;
    iselement(3, [1 2 3 4]) =>
etc.

But suppose you search for something that isn't in the list - what
happens?

    iselement(99, [1 2 3]) =>

    > iselement 99 [1 2 3]
    !> iselement 99 [2 3]
    !!> iselement 99 [3]
    !!!> iselement 99 []

    ;;; MISHAP - NON-EMPTY LIST NEEDED
    ;;; INVOLVING:  []
    ;;; DOING    :  hd iselement iselement iselement iselement ...

When iselement failed to find  99 at the head  of the original list,  it
went into recursion and tried on the tail. So it then failed to find  it
at the head of that, and recursed again. Eventually it tried to  compare
99 with the head of  the empty list.

But hd([])  produced  an error  (see  TEACH LISTS).  And  the  procedure
aborted.

Clearly the  procedure  iselement  has  to be  able  to  cope  with  the
"terminating" case when it gets the empty list as its second argument.

You might think that all  you need is to add  an extra "else" clause  to
deal with the case where list is the empty list, thus:

    define iselement(item, list) -> result;

        if item = hd(list) then
            true -> result;
        elseif iselement(item, tl(list)) then
            true -> result;
        else
            false -> result;
        endif;

    enddefine;

You can try that  and test it  on the same examples  as before, and  you
will find that it  still eventually produces an  error when the item  is
not in the list, because it eventually  gets down to the empty list  and
tries to take the hd of the list.

I.e. the "else" clause comes  TOO LATE in the  procedure - at least  too
late to handle  the empty list,  because the error  produced by  testing
hd([]) has already occurred.

It is possible to get round this using the matcher, which doesn't
produce an error, but can do the test.


-- Using the matcher to define iselement recursively ------------------

Instead of

        if item = hd(list) then

we can do

        if list matches [^item ==] then

This condition is true if the list starts with item, no matter what
comes after it, even if nothing comes after it.

This is a bit wasteful,  as we have to  build a pattern containing  item
every time, in order to do the comparison, but never mind that for now.

Try the following and test it:

    define iselement(item, list) -> result;

        lvars item, list, result;

        if list matches [^item ==] then
            true -> result;
        elseif iselement(item, tl(list)) then
            true -> result;
        else
            false -> result;
        endif;

    enddefine;

If you try  that you  will now  find that  instead of  getting an  error
message from hd saying  NON-EMPTY LIST NEEDED you  will get it from  tl,
because of the line containing tl(list).

You could overcome that problem by again using the pattern matcher
and using an extra variable to dig out the tail of the list, thus

    define iselement(item, list) -> result;

        lvars rest;  ;;; new variable for tail of list

        if list matches [^item ==] then
            true -> result;
        elseif list matches ![= ??rest] and iselement(item, rest) then
            true -> result;
        else
            false -> result;
        endif;

    enddefine;

Notice the use of "and" to join two conditions to form a more complex
condition.

Now test it as before

    iselement(99, [1 2 3]) =>
    iselement(3, [1 2 3 4]) =>
    iselement(3, []) =>
    iselement("tall", john) =>
    iselement("fat", john) =>

It works, but  it's pretty  clumsy. It  needs the  extra local  variable
(rest) for the second call of the matcher and we have to make a  special
list containing the item for the first test.

We can avoid all that if instead of starting by testing the head or  the
tail of the list, we check whether it has a head or tail. I.e. FIRST see
if the  list  is empty.  If  it is  empty,  what should  the  result  of
iselement be?

-- How to do it -------------------------------------------------------

Try completing the following schema.

     define iselement(item, list) -> result;
       if  <the list is empty> then
            false -> result;
       elseif  <the item is the first element of the list> then
            true -> result;
       else
            <use ISELEMENT to search for the item in the TL of the
            list and assign the outcome to RESULT>
       endif
     enddefine;

So, at each  stage of the  process there are  three options, either  the
list is empty, or the  item is the first element  of the list, or it  is
not and  we have  to try  the tail!  The above  schema represents  these
options, using the IF statement.

By putting the test for the empty  list near the beginning we make  sure
that if it IS empty, the procedure stops and does not try testing the hd
or the tl of the list.

That is one of many possible schemas for the required procedure.

If you have managed to define a procedure, test it:
    iselement(3, [ 1 2 3 4])=>
    iselement("tall", john) =>
    iselement("fat", john) =>

These tests should each produce **<true> or **<false>

If  you  did  not   manage  to  complete   that  schema  for   iselement
successfully, look at TEACH SETS1.

If you find the example hard to follow you could try TEACH RECURSION for
some more examples and explanation.

-- Words need to be quoted to refer to themselves ---------------------

The list john included the word "single". So try this

     john=>

     iselement(single, john) =>

You will find that Pop-11 declares "single" as a variable, gives it an
"undef object" as a value, and then iselement fails to find the undef
object in the list john. So its result is false.

In order to get the desired effect, i.e. searching for the word "single"
itself in the list, rather than its value as a variable, you have to
enclose it in double quots (i.e. WORD quotes, not string quotes):

     iselement("single", john) =>

It should now work.

Can you explain why
     iselement("single","john") =>

does not work? If not, ask for help. The difference between a word and a
list is crucial.

Compare
     iselement("single", valof("john")) =>

That works, because, if "john" is the name of a variable, then
    valof("john")
and
    john

are equivalent Pop-11 expressions denoting the value of the variable.
(Actually, if you use sections later on you will find that they are not
equivalent in all contexts.)

Try experimenting with ISELEMENT,  creating several more variables  like
"john" and checking that the ISELEMENT process does in fact work. E.g.

    vars mary;
    [female happy married teacher thin tall] -> mary;

    iselement("male", mary) =>

-- Defining the procedure ismale --------------------------------------

If your program frequently needs to check whether something has the
property male, then you can define a procedure called "ismale" to
do this:

    define ismale(person) -> result;
        ;;; Person is a list of words. Return true if the
        ;;; list contains "male" otherwise return false.

        iselement("male", person) -> result;

    enddefine;

Test it:

    ismale(john) =>
    ismale(mary) =>

Define a similar procedure called "ishappy" which takes a list of words
as input and returns true if the list contains "happy" otherwise false.

-- A procedure to test for two properties: happyman -------------------

Try writing a procedure called HAPPYMAN which takes a single argument, a
list, and returns  TRUE if  that list represents  a happy  man. I.e.  it
should test for whether the list  contains both "happy" and "male".  The
easiest method is to use the two procedures ismale and ishappy,  defined
in terms of iselement.

You could also try defining it directly in terms of iselement. Either
way the following schema should work:

    define happyman(list) -> result;

       if  <list represents a male> then
            if <list represents a happy thing> then
                true -> result
            else
                false -> result
            endif
        else
            false -> result
        endif

    enddefine

Test your procedure:

     happyman(john)=>
     happyman([ male old hungry])=>
     happyman(mary) =>


Some questions:

(a) Why did the above schema need TWO "else"s.

(b) The nested IF ... ENDIF expression does a test, and if it is
    true assigns true to result and if it is false, assigns false
    to result. Can it be written so that it achieves the same thing
    without using IF at all?

(c) Can you write the whole procedure without using IF at all. Just
    use "and", and assign the result of "and" to result?

    Use the fact that if <E1> is an expression and <E2> is an
    expression, then
        <E1> and <E2>
    is also an expression with a result that is FALSE if both <E1> and
    <E2> have the value false, otherwise it has the same value as <E2>.
    So you can use imperatives of the form

        <E1> and <E2> -> result;

(If <E1> is false, the whole thing is false without <E2> being
evaluated. This is often useful for preventing an error that
will occur if the preconditions of <E2> are not satisfied.)

("OR" is another useful infix "boolean" operator.
    See HELP * AND, HELP * OR, HELP * BOOLEAN)


-- Finding an item with a property ------------------------------------

Suppose we had a list of people thus:

    vars people;

    [john ethel mary fred] -> people;

    vars john, ethel, mary, fred;

    [male happy single clerk tall] -> john;
    [female unhappy single prime_minister ] -> ethel;
    [female happy married teacher thin tall] -> mary;
    [male small typist old] -> fred;

where each element of the list of people has been declared as an
ordinary variable and assigned a list representing the person. A
question one might want to ask is "do you know of a happy person?" or
"do you know of a clerk?". The answer should be either the name of the
person or FALSE.

More precisely, suppose we want to define a procedure called "findone"
that takes a word, representing a property, and a list of names of
people, and then returns true or false, thus:

    findone("male", people) =>
    ** john
    findone("old", people) =>
    ** fred
    findone("female", [john fred]) =>
    ** false

The procedure findone  must look at  each item in  the list (its  second
argument), and can use iselement to see  if the property name is in  the
corresponding list of properties. But how does it get the  corresponding
list of properties?

The items in the list are WORDS, and there are lists of properties
corresponding to them as their VALUES. To deal with this you need to
know about the built in Pop-11 procedure "valof", which, when given a
word that has been declared as a variable, returns its value.

-- Using valof --------------------------------------------------------

Assuming that the above declarations and assignments have been compiled,
try the following:

     "john" =>
     john =>
     valof("john") =>
     valof(john) =>

It should be clear that the second and third of these have the same
effect. Now consider

    vars item;
    "john" -> item;

What will the following print? (Try to work it out before trying):

    item =>
    valof(item) =>
    valof("item") =>

VALOF produces an error if you apply it to anything but a word. Now  try
all these:

     vars list;
     [john ethel] -> list;
     "list" =>
     list =>
     valof("list") =>
     hd(list) =>
     valof(hd(list)) =>
     valof(list) =>

If you are not  thoroughly confused, you should  now have the  following
model (remembering  that  inside list  brackets  words are  quoted,  not
replaced by  their values  -- unless  you  use "^"  or "^^"  or  percent
signs):

"list"
  |
  +--valof--->[john  ethel]
                 |     |
                 |     +-valof-->[female unhappy single prime_minister]
                 |
                 +-valof-->[male happy single clerk tall]

The list called -people- can be thought of in the same way, except that
it would require a bigger diagram.

Thus if our procedure findone is to search down a list of words naming
people, then test for the corresponding property, it has to use valof on
each name to get at the list of properties.

-- A schema for FINDONE -----------------------------------------------

Although findone could be defined using "for ... endfor" like the  first
version of  "iselement" above,  it is  a useful  exercise to  try  using
recursion.

Below is  a schema  for findone.

You should be able to use the procedure iselement defined above, in  the
ELSEIF line. You will also have to use valof(hd(list)). Don't be worried
by the fact both iselement and findone both use a local variable "list".
Because it is  local in  both cases,  the two  uses of  "list" will  not
interact. Each procedure  effectively has its  own "private" version  of
the variable.

Try completing this schema:

    define findone(prop, list) -> result;
       if  <no more in the list> then
            false -> result
       elseif  <valof first element has property> then
            <first element> -> result
       else
            findone(prop, tl(list) -> result
       endif
     enddefine;


-- How to specify a procedure ------------------------------------------

In thinking about designing a procedure like FINDONE you have to  have a
very clear idea of  what you are trying  to do. Produce a  specification
for the procedure before you try writing any Pop-11 code.

The specification for a procedure should contain the following items,
each set out with its own sub-heading, for clarity.

(a) A specification of the type(s) of arguments (if any), e.g.
    "it takes a list of words and an integer"
    "it takes a list (of anything) and a procedure of one
     argument producing an integer as a result"
     etc.

(b) A specification of the type(s) of outputs (if any) e.g.
    "it produces a list of integers"
    "it produces either false or an integer"
    "it produces two results, a list and a boolean (true or false)"
    etc.

NB the  specification  of types  of  inputs  and outpus  should  not  be
concerned with what they look like  when typed in or printed out.  (E.g.
it is not relevant  to talk about commas  and spaces and list  brackets:
these are not  objects that will  be in the  machine when the  procedure
runs). So the  arguments should be  specified in terms  of the kinds  of
objects (integers, words, lists, lists of  lists, etc) that will be  put
on the stack as input(s) for the procedure, and similarly the outputs.

In specifying the TYPES of inputs and outputs you don't say how the
output is derived from the input. That comes in the next section when
you say WHAT the procedure does.

(c) A description of WHAT the procedure does - without saying HOW it
    does it. This should say how the results are related to the input,
    without describing the method by which the results are produced.

    This section should also include a specification of any side-effects
    the procedure may produce (i.e. effects it has other than taking
    arguments off the stack or putting results on the stack.

    Side-effects could include reading something from the terminal,
    printing something to the terminal, changing a file, changing the
    value of a global variable, such as "database") - though in general
    changing global variables is something to be avoided if possible,
    as it can lead to obscure errors.

(d) Some typical test cases, with an indication of what the procedure
    does with them (not how it does it). The test cases should include
    "limiting" or "extreme" test cases, e.g. empty lists as input, lists
    of only one argument, lists where the item searched for is at the
    beginning, lists where it is at the end, lists that don't contain
    what is searched for, etc. Selecting a good range of test cases is
    not always easy, but is crucial to good design. The test cases can
    be described using simulated program executions, e.g.

    iselement(99, []) =>
    ** <false>
    iselement(99, [99]) =>
    ** <true>
    iselement(99, [a b 3 4 c d]) =>
    ** <false>
    iselement(99, [a b 96 c 97 d 99]) =>
    ** <true>
    iselement(99, [a [99] b]) =>
    ** <false>

    and so on.

(e)  When  you  have  specified  all  that  you  can  begin  to  write a
description of  HOW the  procedure  should work  in  order to  meet  its
specification. E.g.

    iselement takes a word W and a list L and it searches down the
    list checking to see if any item in the list is the same as W.
    If it finds such an item it terminates the search and returns
    TRUE as its result. If it gets to the end of L without finding
    W it returns FALSE as its result.

Notice  that  the  specification  does   not  say  anything  about   the
programming language used, it does not include any bits of code, and  it
is written using concepts that should  be clear to someone who does  not
know the programming language.


-- Specifying internal and external semantics -------------------------

In chapter 2 of the Pop-11 Primer (TEACH PRIMER, also accessible online
as
    http://www.cs.bham.ac.uk/research/poplog/primer/ )

a distinction is made between the internal semantics of a program and
the external semantics.

The internal semantics of a program is concerned with which objects and
processes inside the computer are referred to by the program code.

Some programs which deal with a particular domain of application also
have an external semantics if they refer to entities, within that
domain.

In the specification of iselement above only the internal semantics were
referred to, e.g. :

    "it takes a list of words and an integer"

    "it produces a list of integers"

However in some cases the words may refer to people and the integer may
refer to an age or a salary. In the context of a project or application
program, the comments explaining a procedure may need to state both the
internal and the external semantics of the input and output variables
and the procedure (e.g. "it returns a list of vectors of words and
numbers, representing all the employees whose salary is less than that
given").

-- Using ENTER procheader ---------------------------------------------

To simplify the task of producing a header comment it is useful to use
the VED command ENTER procheader, described in HELP VED_PROCHEADER
which is available at Birmingham or at the FreePoplog site:
     http://www.cs.bham.ac.uk/research/poplog/freepoplog.html



-- Specifying FINDONE -------------------------------------------------

(a) Types of arguments
    FINDONE takes two arguments, a word and a list of words, naming
    people. The words in the list should already have been declared as
    Pop-11 variables and their values should be lists of words
    indicating properties of people.

(b) Type of output
    FINDONE produces either FALSE or a word as its output

(c) What the procedure does.
    Given a word W and a list of people's names P it produces the
    first name in P that denotes a list containing W. If there is
    no such name it produces FALSE.

    It has no side effects.

(d) Typical test cases

    findone("happy", []) =>
    ** <false>

    ;;; assume lists -john- and -ethel- etc exist as defined above
    findone("female", [john ethel]) =>
    ** ethel

    findone("rich", [john ethel]) =>
    ** <false>

    vars people;
    [john ethel mary fred] -> people;

     findone("typist", people) =>
    ** fred

     findone("angry", people) =>
    ** <false>

Now  try  writing  the  code  for   FINDONE,  so  that  it  meets   this
specification, using the SCHEMA presented above, or any other method you
like.

When finished write down a description of HOW it does it, along the
lines illustrated with the description of iselement under (e) in the
previous section.


-- FINDALL ------------------------------------------------------------

It's harder to answer questions of the form "Find all the people who are
clerks", for example:

     findall("male", people) =>
    ** [john fred]
    findall("rich", people) =>
    ** []

In order to solve this task you have to know how to traverse a list,
testing each element, and make a list of all those that pass the test.

-- Digression: findintegers -------------------------------------------

Here, for example, is a procedure that takes a list and returns a list
of all the integers in it. We use the built in procedure "isinteger"
which produces TRUE if applied to an integer, and FALSE if applied to
anything else. (An integer is a "whole" number, positive or negative,
e.g. 0 3 999 -5 -392, but not 3.5 or -77.111).


    define findintegers(list) -> result;

        lvars item;

        [% for item in list do
            if isinteger(item) then item endif
           endfor
        %] -> result

    enddefine;


Notice that the line

            if isinteger(item) then item endif

puts things on the stack if and only if they are integers, and the  list
brackets with percents [% ...  %] make a list  of everything put on  the
stack, between them. Because the percents are used, the list brackets do
not quote all the enclosed text: instead the text is treated as  program
and the program is run. See the list examples in TEACH PERCENT.

Try that out

    findintegers([1 2 3 cat mouse 99 6]) =>
    ** [1 2 3 99 6]
    findintegers([one 1 two 2]) =>
    ** [1 2]
    findintegers([one two three]) =>
    ** []

Try some other tests. E.g. what should it do with the empty list?

Doing it recursively is a bit more  tricky if you have not met the  idea
previously. Try completing the following schema, replacing the dots  and
the bits of English in angle brackets, with bits of Pop-11:

    define findintegers(list) -> result;

        if list = [] then
            .... -> result

        elseif isinteger(hd(list)) then

            <find the integers in the tail of the list, stick
                the head of the list on the front> -> result
        else
            .... -> result

        endif

    enddefine;

Notice that  there are  two recursive  calls here.  Try completing  that
schema, and then test it on the above examples, with tracing where
necessary to help you understand what is going on.

You can do it with  only one recursive call if  you use an extra  nested
conditional and modify it thus:

    define findintegers(list) -> result;

        if list = [] then
            .... -> result
        else
            findintegers(tl(list)) -> result;

            if isinteger(hd(list)) then
                <add the hd of the list to the front of result>
            endif

        endif

    enddefine;

Once again, try completing that schema, and then test it on all the
previous examples of findinteger.

-- Now let's return to findall ----------------------------------------

Findall is supposed to take a word W, and a list L of people, i.e. a
list of names of lists,. It should return a list of names, i.e. the
names of people whose descriptions include the word W.

     findall("male", people) =>

That should print out something like:

    ** [john fred]

You could try using the "for item in list" format with [% ... %] to make
a list of all the things found that satisfy the test of the form

    if iselement(prop, valof(hd(list))) then

as in the iterative definition of findintegers.

Alternatively try doing it recursively, on the model of the recursive
definition of findintegers.

Remember that before you start trying to write the Pop-11 definition for
the procedure  it is  essential to  be  clear about  what you  want  the
procedure  to  do.  Follow  the  example  given  above,  and  write  the
specification in steps (a) to (e) as was done above for "iselement" (and
"findone").

Examine all the test cases carefully and make sure that your plan for it
covers all the cases. Make sure that it always returns a list, even if
it's the empty list.

If you use recursion make sure that you give the recursive call the
correct types of inputs (see the specification for the inputs), and also
make sure that you use the result of the recursive call properly (i.e.
the list it produces).

-- A schema for FINDALL -----------------------------------------------

Here is a suitable  recursive schema for  findall. Remember that  you'll
have to use iselement as  well as the procedure valof  on the hd of  the
list (as in findone, above).

    define findall(prop, list) -> result;

        if  <list is empty> then

            [] -> result;   ;;; i.e. empty set is result

        else
            <get all the items in the tail of the list that
                have the property> -> result;

            if <the first item in the list has the property> then
                <add it to the front of the result>
            endif;

        endif;
    enddefine;

Try testing it, with

     findall("female", people) =>
     ** [ethel mary]

and other examples. To see what is going on trace findall and iselement.


-- If you need help ---------------------------------------------------------

If you didn't succeed, try completing this:

    define findall(prop, list) -> result;
        if  <list is empty> then
            [] -> result;   ;;; i.e. empty set is result
        else
            findall(prop, tl(list)) -> result;
            if <the first item in the list has the property> then
                ;;; add it to the result
                [^(hd(list)) ^^result] -> result;
            endif;
        endif;
    enddefine;

N.B. When  you  complete the  second  conditional, VALOF  is  needed  as
before, so that,  for example,  ISELEMENT looks in  the list  associated
with "john", not in the word "john" itself.

Test your procedure. Try Tracing it and ISELEMENT, when you do.


-- It still doesn't work? ---------------------------------------------

If you didn't manage, try typing in this

     define findall(prop, list) -> result;

       if  list = [] then
           [] -> result
       else
           findall(prop, tl(list)) -> result;

           ;;; Got all the things from the tail. Check whether the hd
           ;;; of the list needs to be added to the front of result

           if iselement(prop, valof(hd(list))) then
                ;;; create a new result list, using the hd of the list
                ;;; and the old result, got from the recursive call

                [^(hd(list))  ^^result] -> result
            endif;
       endif;
     enddefine;

Then try:
     trace findall;
     findall("happy", people) =>
     findall("female", people) =>


Try other tests. If you haven't traced ISELEMENT trace it too - though
you may get a lot of printout.


-- A set of properties: findset ---------------------------------------

A yet harder task is to find ALL the people with a set of properties, for
example:

     findset([male happy], people) =>

In order to do  this you will  need to define  a procedure that  takes a
list of properties and a person (in the form of a list) and then returns
true if the person has all the properties.

E.g. suppose  we call  it has_all, then

    has_all([male tall], john) =>
    ** <true>
    has_all([female tall], john) =>
    ** <false>

What should we do if the first list is empty?
    has_all([], john) =>

It turns out to be convenient to  assume that if increasing the list  of
properties provides a  tougher, more restrictive,  test, then having  an
empty list of properties means that everyone passes the test. I.e.

    has_all([], john) =>
    ** <true>

And the same would apply to mary, ethel etc.

The only really tricky bit is

    <the person has all the properties>.

You may  find it  useful to  define a  procedure called  ISSUBSET  which
checks if every element of  one list is in  another. It should take  two
sets and see  if all the  elements of  the first are  ISELEMENTs of  the
second. can then write:

       elseif issubset(proplist, valof(hd(thinglist)))

Try defining ISSUBSET iteratively (using "for item in littleset do ...")
and recursively.


-- Help with recursive issubset ---------------------------------------

Here is a recursive schema for ISSUBSET:

     define issubset(littleset, bigset) -> result;

       if  <littleset is empty> then
            <result is TRUE>
       elseif  <head of littleset is in bigset> then
            if <tail of littleset is a subset of bigset> then
                <result is TRUE>
            else
                <result is FALSE>
            endif
       else
            <result is FALSE>
       endif

     enddefine;

Try completing that. Test it, then use it to define FINDSET. Then test
FINDSET, tracing everything.

-- Some advice on testing ---------------------------------------------

An important point: whenever you define a new procedure TEST it. Try  to
make sure it works  on all the limiting  cases, e.g. empty lists,  lists
with "target" items at the beginning or at the end, lists with only  one
item, etc.  Try to  make sure  you have  covered all  the  significantly
different cases in your tests. Plan those tests BEFORE you write the
procedure definition, so that you can use them in thinking about what
the procedure has to do, i.e. you can make sure it covers all the
different cases that can arise.

NEVER type in a long list of procedures and then try testing them all by
running one high  level procedure that  runs all the  others. That  will
ensure that you waste a lot of time searching for obscure bugs.

Keep a set of test cases in the file, e.g. in comment brackets

    /*
        test1
        test2
        .....
    */

so that you can conveniently re-run the tests if you change the program.
ALWAYS re-run them after every change. Make sure that the first tests
are SIMPLE ones, so that if procedure doesn't work on them it should be
easier to find out why not.

By including the test cases in a comment, you can safely load the  whole
file without running the tests every time.

-- Returning to FINDSET -----------------------------------------------

What should we get with an empty list of properties:

    findset([], people) =>

It all depends on how you interpret that command. Depending how you  had
defined your procedures, POP-11 is likely  to interpret it to mean  find
the set of people without any constraint at all, i.e. it will  produce a
list of ALL the people. This is  quite natural if you think of the  fact
that adding more properties will REDUCE the list of people. E.g. if  you
give the property "happy" then that  selects the subset that are  happy.
If you give the properties "happy"  and "male" then the second  property
will (usually) select an even smaller subset from the first.

So if you have no properties it  should not reduce the list at all.  The
above definition of issubset is consistent with that line of thought.

The procedure FINDSET takes a list of properties and a list of things. It is
to 'return' a list of those things which have ALL the given properties. Here
is a recursive schema for FINDSET:

     define findset(proplist, thinglist) -> result;
       if  <thinglist is empty> then
            <the result is the empty set>
       else
            ;;; recursively call findset on the tail
            <get all the things in the tail of thinglist that have
            all the properties> -> result;

            ;;; now use issubset to see if the head of thinglist should
            ;;; be included in the result
            if <valof hd of thinglist has all the properties> then
                <add it to result> -> result
            endif

       endif
     enddefine;

It may look VERY odd that you have to work on the tail before the  head.
At first it  may appear  that the  procedure can't  do anything  because
nothing can get added to the result till everything else has been added.

But the crucial point is that ultimately the recursion gets down to  the
empty list [],  and this final  recursive call returns  a result of  [],
after which it works  back through thinglist from  right to left as  the
recursion unwinds, adding items to the result if they satisfy the  test.
You should be able to see this by tracing the procedure.
(The "sum" example in TEACH RECURSION is similar.)

Try completing that, and test it if you succeed.



-- If you needed help -------------------------------------------------

If you didn't manage try completing this template:

     define findset(proplist, thinglist) -> result;
       if  <thinglist is empty> then
            [] -> result
       else
            ;;; recursively call findset on the tail
            <get all the things in the tail of thinglist that have
            all the properties> -> result;

            ;;; Now use issubset to see if the head of thinglist should
            ;;; be included in the result
            if issubset(proplist, valof(hd(thinglist)) then
                [^(hd(thinglist) ^^result] -> result
            endif
       endif
     enddefine;


-- A different findset ------------------------------------------------

Can you understand this alternative definition of FINDSET, which makes
use of the previously defined FINDALL:

    define findset(proplist, thinglist) -> result;

        if  proplist == [] then
            thinglist -> result
        else
            findset(tl(proplist), findall(hd(proplist), thinglist))
                -> result
        endif
    enddefine;

(This assumes that you have already defined FINDALL)

Try defining and testing it, tracing everything to see how it works.

Incidentally, the Pop-11 system includes a procedure MEMBER, which  does
what your procedure ISELEMENT does. So  you don't really need to  define
your own. You can  change all occurrences of  ISELEMENT above to  MEMBER
(except in the definition of ISELEMENT).

NOTE: the above procedure uses "==" in the test. That is because the
empty list [] is a unique object and therefore the test can come out
true ONLY if the value of proplist is exactly that object. There is no
need to test whether it is a similar type of object with similar
contents, as "=" does. So using "==" saves time.

For more on that topic see
    HELP EQUAL

and HELP EFFICIENCY

-- Further reading ----------------------------------------------------

Several teach files have been mentioned already, including

TEACH * LISTS, * RECURSION

Additional exercises on list processing can be found in
TEACH * RECURSE2
TEACH * RECURSE3
TEACH * LISTQUESTIONS
TEACH * SETS2   -- takes you through a collection "set" operations.

See the POP-11 Primer, chapter 6, also available online at

    http://www.cs.bham.ac.uk/research/poplog/primer/

There are additional list processing exercises in some of the books
listed in the file HELP *POPREFS:

    Laventhol
        (e.g. chapter 5)
and
    Barrett, Ramsay and Sloman
        (e.g. chapter 7)

Both books may be out of print by now. Also they use an older syntax for
Pop-11, which still works, though often the new syntax is clearer.

    --- C.all/teach/sets
    --- Copyright University of Sussex 1989. All rights reserved. ----------

--- $poplocal/local/teach/sets
--- Copyright University of Birmingham 2001. All rights reserved. ------
