COMMENT
REDUCE INTERACTIVE LESSON NUMBER 6
David R. Stoutemyer
University of Hawaii
COMMENT This is lesson 6 of 7 REDUCE lessons. A prerequisite is to
read the pamphlet "An Introduction to LISP", by D. Lurie'.
To avoid confusion between RLISP and the SYMBOLIC-mode algebraic
algorithms, this lesson will treat only RLISP. Lesson 7 deals with how
the REDUCE algebraic mode is implemented in RLISP and how the user can
interact directly with that implementation. That is why I suggested
that you run this lesson in RLISP rather than full REDUCE. If you
forgot or do not have a locally available separate RLISP, then please
switch now to symbolic mode by typing the statement SYMBOLIC;
SYMBOLIC;
PAUSE;
COMMENT Your most frequent mistakes are likely to be forgetting to quote
data examples, using commas as separators within lists, and not puttng
enough levels of parentheses in your data examples.
Now that you have learned from your reading about the built-in RLISP
functions CAR, CDR, CONS, ATOM, EQ, NULL, LIST, APPEND, REVERSE, DELETE,
MAPLIST, MAPCON, LAMBDA, FLAG, FLAGP, PUT, GET, DEFLIST, NUMBERP, ZEROP,
ONEP, AND, EVAL, PLUS, TIMES, CAAR, CADR, etc., here is an opportunity
to reinforce the learning by practice.: Write expressions using CAR,
CDR, CDDR, etc., (which are defined only through 4 letters between C and
R), to individually extract each atom from F, where;
F := '((JOHN . DOE) (1147 HOTEL STREET) HONOLULU);
PAUSE;
COMMENT My solutions are CAAR F, CDAR F, CAADR F, CADADR F,
CADDR CADR F, and CADDR F.
Although commonly the "." is only mentioned in conjunction with data, we
can also use it as an infix alias for CONS. Do this to build from F and
from the data 'MISTER the s-expression consisting of F with MISTER
inserted before JOHN.DOE;
PAUSE;
COMMENT My solution is ('MISTER . CAR F) . CDR F .
Enough of these inane exercises -- let's get on to something useful!
Let's develop a collection of functions for operating on finite sets.
We will let the elements be arbitrary s-expressions, and we will
represent a set as a list of its elements in arbitrary order, without
duplicates.
Here is a function which determines whether its first argument is a
member of the set which is its second element;
SYMBOLIC PROCEDURE MEMBERP(ELEM, SET1);
COMMENT Returns T if s-expression ELEM is a top-level element
of list SET1, returning NIL otherwise;
IF NULL SET1 THEN NIL
ELSE IF ELEM = CAR SET1 THEN T
ELSE MEMBERP(ELEM, CDR SET1);
MEMBERP('BLUE, '(RED BLUE GREEN));
COMMENT This function illustrates several convenient techniques for
writing functions which process lists:
1. To avoid the errors of taking the CAR or the CDR of an atom, and
to build self confidence while it is not immediately apparent how to
completely solve the problem, treat the trivial cases first. For an
s-expression or list argument, the most trivial cases are generally
when one or more of the arguments are NIL, and a slightly less
trivial case is when one or more is an atom. (Note that we will get
an error message if we use MEMBERP with a second argument which is
not a list. We could check for this, but in the interest of brevity,
I will not strive to make our set-package give set-oriented error
messages.)
2. Use CAR to extract the first element and use CDR to refer to the
remainder of the list.
3. Use recursion to treat more complicated cases by extracting the
first element and using the same functions on smaller arguments.;
PAUSE;
COMMENT To make MEMBERP into an infix operator we make the declaration;
INFIX MEMBERP;
'(JOHN.DOE) MEMBERP '((FIG.NEWTON) FONZO (SANTA CLAUS));
COMMENT Infix operators associate left, meaning expressions of the form
(operator1 operator operand2 operator ... operandN)
are interpreted as
((...(operand1 operator operand2) operator ... operandN).
Operators may also be flagged RIGHT by
FLAG ('(op1 op2 ...), 'RIGHT) .
to give the interpretation
(operand1 operator (operand2 operator (... operandN))...).
Of the built-in operators, only ".", "*=", "+", and "*" associate right.
If we had made the infix declaration before the function definition, the
latter could have begun with the more natural statement
SYMBOLIC PROCEDURE ELEM MEMBERP SET .
Infix functions can also be referred to by functional notation if one
desires. Actually, an analogous infix operator named MEMBER is already
built-into RLISP, so we will use MEMBER rather than MEMBERP from here
on;
MEMBER(1147, CADR F);
COMMENT Inspired by the simple yet elegant definition of MEMBERP, write
a function named SETP which uses MEMBER to check for a duplicate element
in its list argument, thus determining whether or not the argument of
SETP is a set;
PAUSE;
COMMENT My solution is;
SYMBOLIC PROCEDURE SETP CANDIDATE;
COMMENT Returns T if list CANDIDATE is a set, returning NIL
otherwise;
IF NULL CANDIDATE THEN T
ELSE IF CAR CANDIDATE MEMBER CDR CANDIDATE THEN NIL
ELSE SETP CDR CANDIDATE;
SETP '(KERMIT, (COOKIE MONSTER));
SETP '(DOG CAT DOG);
COMMENT If you used a BEGIN-block, local variables, loops, etc., then
your solution is surely more awkward than mine. For the duration of the
lesson, try to do everything without groups, BEGIN-blocks, local
variables, assignments, and loops. Everything can be done using
function composition, conditional expressions, and recursion. It will
be a mind-expanding experience -- more so than transcendental
meditation, psilopsybin, and EST. Afterward, you can revert to your old
ways if you disagree.
Thus endeth the sermon.
Incidentally, to make the above definition of SETP work for non-list
arguments all we have to do is insert "ELSE IF ATOM CANDIDATE THEN NIL"
below "IF NULL CANDIDATE THEN T".
Now try to write an infix procedure named SUBSETOF, such that SET1
SUBSETOF SET2 returns NIL if SET1 contains an element that SET2 does
not, returning T otherwise. You are always encouraged, by the way, to
use any functions that are already builtin, or that we have previously
defined, or that you define later as auxiliary functions;
PAUSE;
COMMENT My solution is;
INFIX SUBSETOF;
SYMBOLIC PROCEDURE SET1 SUBSETOF SET2;
IF NULL SET1 THEN T
ELSE IF CAR SET1 MEMBER SET2 THEN CDR SET1 SUBSETOF SET2
ELSE NIL;
'(ROOF DOOR) SUBSETOF '(WINDOW DOOR FLOOR ROOF);
'(APPLE BANANA) SUBSETOF '((APPLE COBBLER) (BANANA CREME PIE));
COMMENT Two sets are equal when they have identical elements, not
necessarily in the same order. Write an infix procedure named
EQSETP which returns T if its two operands are equal sets, returning
NIL otherwise;
PAUSE;
COMMENT The following solution introduces the PRECEDENCE declaration;
INFIX EQSETP;
PRECEDENCE EQSETP, =;
PRECEDENCE SUBSETOF, EQSETP;
SYMBOLIC PROCEDURE SET1 EQSETP SET2;
SET1 SUBSETOF SET2 AND SET2 SUBSETOF SET1;
'(BALLET TAP) EQSETP '(TAP BALLET);
'(PINE FIR ASPEN) EQSETP '(PINE FIR PALM);
COMMENT The precedence declarations make SUBSETOF have a higher
precedence than EQSETP and make the latter have higher precedence than
"=", which is higher than "AND",. Consequently, these declarations
enabled me to omit parentheses around "SET1 SUBSUBSETOF SET2" and around
"SET2 SUBSETOF SET1". All prefix operators are higher than any infix
operator, and to inspect the ordering among the latter, we merely
inspect the value of the global variable named;
PRECLIS!*;
COMMENT Now see if you can write a REDUCE infix function named
PROPERSUBSETOF, which determines if its left operand is a proper subset
of its right operand, meaning it is a subset which is not equal to the
right operand;
PAUSE;
COMMENT All of the above exercises have been predicates. In contrast,
the next exercise is to write a function called MAKESET, which returns
a list which is a copy of its argument, omitting duplicates;
PAUSE;
COMMENT How about;
SYMBOLIC PROCEDURE MAKESET LIS;
IF NULL LIS THEN NIL
ELSE IF CAR LIS MEMBER CDR LIS THEN MAKESET CDR LIS
ELSE CAR LIS . MAKESET CDR LIS;
COMMENT As you may have guessed, the next exercise is to implement an
operator named INTERSECT, which returns the intersection of its set
operands;
PAUSE;
COMMENT Here is my solution;
INFIX INTERSECT;
PRECEDENCE INTERSECT, SUBSETOF;
SYMBOLIC PROCEDURE SET1 INTERSECT SET2;
IF NULL SET1 THEN NIL
ELSE IF CAR SET1 MEMBER SET2
THEN CAR SET1 . CDR SET1 INTERSECT SET2
ELSE CDR SET1 INTERSECT SET2;
COMMENT Symbolic-mode REDUCE has a built-in function named SETDIFF,
which returns the set of elements which are in its first argument but
not the second. See if you can write an infix definition of a similar
function named DIFFSET;
PAUSE;
COMMENT Presenting --;
INFIX DIFFSET;
PRECEDENCE DIFFSET, INTERSECT;
SYMBOLIC PROCEDURE LEFT DIFFSET RIGHT;
IF NULL LEFT THEN NIL
ELSE IF CAR LEFT MEMBER RIGHT THEN CDR LEFT DIFFSET RIGHT
ELSE CAR LEFT . (CDR LEFT DIFFSET RIGHT);
'(SEAGULL WREN CONDOR) DIFFSET '(WREN LARK);
COMMENT The symmetric difference of two sets is the set of all elements
which are in only one of the two sets. Implement a corresponding infix
function named SYMDIFF. Look for the easy way! There is almost always
one for examinations and instructional exercises; PAUSE;
COMMENT Presenting --;
INFIX SYMDIFF;
PRECEDENCE SYMDIFF, INTERSECT;
SYMBOLIC PROCEDURE SET1 SYMDIFF SET2;
APPEND(SET1 DIFFSET SET2, SET2 DIFFSET SET1);
'(SEAGULL WREN CONDOR) SYMDIFF '(WREN LARK);
COMMENT We can use APPEND because the two set differences are disjoint.
The above set of exercises (exercises of set?) have all returned set
results. The cardinality, size, or length of a set is the number of
elements in the set. More generally, it is useful to have a function
which returns the length of its list argument, and such a function is
built-into RLISP. See if you can write a similar function named SIZEE;
PAUSE;
COMMENT Presenting --;
SYMBOLIC PROCEDURE SIZEE LIS;
IF NULL LIS THEN 0
ELSE 1 + SIZEE CDR LIS;
SIZEE '(HOW MARVELOUSLY CONCISE);
SIZEE '();
COMMENT Literal atoms, meaning atoms which are not numbers, are stored
uniquely in LISP and in RLISP, so comparison for equality of literal
atoms can be implemented by comparing their addresses, which is
significantly more efficient than a character-by-character comparison of
their names. The comparison operator "EQ" compares addresses, so it is
the most efficient choice when comparing only literal atoms. The
assignments
N2 := N1 := 987654321,
S2 := S1 := '(FROG (SALAMANDER.NEWT)),
make N2 have the same address as N1 and make S2 have the same address as
S1, but if N1 and N2 were constructed independently, they would not
generally have the same address, and similarly for S1 vs. S2. The
comparison operator "=", which is an alias for "EQUAL", does a general
test for identical s-expressions, which need not be merely two pointers
to the same address. Since "=" is built-in, compiled, and crucial, I
will define my own differently-named version denoted ".=" as follows:;
PAUSE;
NEWTOK '((!. !=) MYEQUAL);
INFIX EQATOM, MYEQUAL;
PRECEDENCE MYEQUAL, EQUAL;
PRECEDENCE EQATOM,EQ;
SYMBOLIC PROCEDURE S1 MYEQUAL S2;
IF ATOM S1 THEN
IF ATOM S2 THEN S1 EQATOM S2
ELSE NIL
ELSE IF ATOM S2 THEN NIL
ELSE CAR S1 MYEQUAL CAR S2 AND CDR S1 MYEQUAL CDR S2;
SYMBOLIC PROCEDURE A1 EQATOM A2;
IF NUMBERP A1 THEN
IF NUMBERP A2 THEN ZEROP(A1-A2)
ELSE NIL
ELSE IF NUMBERP A2 THEN NIL
ELSE A1 EQ A2;
COMMENT Here I introduced a help function named EQATOM, because I was
beginning to become confused by detail when I got to the line which uses
EQATOM. Consequently, I procrastinated on attending to some fine detail
by relegating it to a help function which I was confident could be
successfully written later. After completing MYEQUAL, I was confident
that it would work provided EQATOM worked, so I could then turn my
attention entirely to EQATOM, freed of further distraction by concern
about the more ambitious overall goal. It turns out that EQATOM is a
rather handy utility function anyway, and practice helps develop good
judgement about where best to so subdivide tasks. This psychological
divide-and-conquer programming technique is important in most other
programming languages too.
".=" is different from our previous examples in that ".=" recurses down
the CAR as well as down the CDR of an s-expression;
PAUSE;
COMMENT
If a list has n elements, our function named MEMBERP or the equivalent
built-in function named MEMBER requires on the order of n "=" tests.
Consequently, the above definitions of SETP and MAKESET, which require
on the order of n membership tests, will require on the order of n**2
"=" tests. Similarly, if the two operands have m and n elements, the
above definitions of SUBSETOF, EQSETP, INTERSECT, DIFFSET, and
SYMDIFF require on the order of m*n "=" tests. We could decrease the
growth rates to order of n and order of m+n respectively by sorting the
elements before giving lists to these functions. The best algorithms
sort a list of n elements in the order of n*log(n) element comparisons,
and this need be done only once per input set. To do so we need a
function which returns T if the first argument is "=" to the second
argument or should be placed to the left of the second argument. Such a
function, named ORDP, is already built-into symbolic-mode REDUCE, based
on the following rules:
1. Any number orders left of NIL.
2. Larger numbers order left of smaller numbers.
4. Literal atoms order left of numbers.
3. Literal atoms order among themselves by address, as determined
by the built-in RLISP function named ORDERP.
5. Non-atoms order left of atoms.
6. Non-atoms order among themselves according to ORDP of their
CARs, with ties broken according to ORDP of their CDRs.
Try writing an analogous function named MYORD, and, if you are in
REDUCE rather than RLISP, test its behavior in comparison to ORDP;
PAUSE;
COMMENT Whether or not we use sorted sets, we can reduce the
proportionality constant associated with the growth rate by replacing
"=" by "EQ" if the set elements are restricted to literal atoms.
However, with such elements we can use property-lists to achieve the
growth rates of the sorted algorithms without any need to sort the
sets. On any LISP system that is efficient enough to support REDUCE
with acceptable performance, the time required to access a property of
an atom is modest and very insensitive to the number of distinct
atoms in the program and data. Consequently, the basic technique
for any of our set operations is:
1. Scan the list argument or one of the two list arguments,
flagging each element as "SEEN".
2. During the first scan, or during a second scan of the same
list, or during a scan of the second list, check each element
to see whether or not it has already been flagged, and act
accordingly.
3. Make a final pass through all elements which were flagged to
remove the flag "SEEN". (Otherwise, we may invalidate later set
operations which utilize any of the same atoms.)
We could use indicators rather than flags, but the latter are slightly
more efficient when an indicator would have only one value (such as
having "SEEN" as the value of an indicator named "SEENORNOT").
As an example, here is INTERSECT defined using this technique;
SYMBOLIC PROCEDURE INTERSECT(S1, S2);
BEGIN SCALAR ANS, SET2;
FLAG(S1, 'SEEN);
SET2 := S2;
WHILE SET2 DO <<
IF FLAGP(CAR SET2, 'SEEN) THEN ANS := CAR SET2 . ANS;
SET2 := CDR SET2 >>;
REMFLAG(S1, 'SEEN);
RETURN ANS
END;
COMMENT Perhaps you noticed that, having used a BEGIN-block, group,
loop, and assignments, I have not practiced what I preached about
using only function composition, conditional expressions, and
recursion during this lesson. Well, now that you have had some
exposure to both extremes, I think you should always fairly
consider both together with appropriate compromises, in each case
choosing whatever is most clear, concise, and natural. For set
operations based on the property-list approach, I find the style
exemplified immediately above most natural.
As your last exercise for this lesson, develop a file containing a
package for set operations based upon either property-lists or sorting.
This is the end of lesson 6. When you are ready to run the final lesson
7, load a fresh copy of REDUCE.
;END;