f2c04ccdad 2021-03-03 1: COMMENT
f2c04ccdad 2021-03-03 2:
f2c04ccdad 2021-03-03 3: REDUCE INTERACTIVE LESSON NUMBER 6
f2c04ccdad 2021-03-03 4:
f2c04ccdad 2021-03-03 5: David R. Stoutemyer
f2c04ccdad 2021-03-03 6: University of Hawaii
f2c04ccdad 2021-03-03 7:
f2c04ccdad 2021-03-03 8:
f2c04ccdad 2021-03-03 9: COMMENT This is lesson 6 of 7 REDUCE lessons. A prerequisite is to
f2c04ccdad 2021-03-03 10: read an introductory text about LISP, such as "A Concise Introduction
f2c04ccdad 2021-03-03 11: to LISP" by David L. Matuszek, which is freely available at
f2c04ccdad 2021-03-03 12: https://www.cis.upenn.edu/~matuszek/LispText/lisp.html. Then
f2c04ccdad 2021-03-03 13: familiarize yourself with the Standard Lisp Report, which is freely
f2c04ccdad 2021-03-03 14: available via http://reduce-algebra.sourceforge.net/documentation.php.
f2c04ccdad 2021-03-03 15:
f2c04ccdad 2021-03-03 16: To avoid confusion between RLISP and the SYMBOLIC-mode algebraic
f2c04ccdad 2021-03-03 17: algorithms, this lesson will treat only RLISP. Lesson 7 deals with how
f2c04ccdad 2021-03-03 18: the REDUCE algebraic mode is implemented in RLISP and how the user can
f2c04ccdad 2021-03-03 19: interact directly with that implementation. That is why I suggested
f2c04ccdad 2021-03-03 20: that you run this lesson in RLISP rather than full REDUCE. If you
f2c04ccdad 2021-03-03 21: forgot or do not have a locally available separate RLISP, then please
f2c04ccdad 2021-03-03 22: switch now to symbolic mode by typing the statement SYMBOLIC.;
f2c04ccdad 2021-03-03 23:
f2c04ccdad 2021-03-03 24: symbolic;
f2c04ccdad 2021-03-03 25: pause;
f2c04ccdad 2021-03-03 26:
f2c04ccdad 2021-03-03 27: COMMENT Your most frequent mistakes are likely to be forgetting to quote
f2c04ccdad 2021-03-03 28: data examples, using commas as separators within lists, and not putting
f2c04ccdad 2021-03-03 29: enough levels of parentheses in your data examples.
f2c04ccdad 2021-03-03 30:
f2c04ccdad 2021-03-03 31: Having learnt from reading the Standard Lisp Report about the built-in
f2c04ccdad 2021-03-03 32: RLISP functions CAR, CDR, CONS, ATOM, EQ, NULL, LIST, APPEND, REVERSE,
f2c04ccdad 2021-03-03 33: DELETE, MAPLIST, MAPCON, LAMBDA, FLAG, FLAGP, PUT, GET, DEFLIST,
f2c04ccdad 2021-03-03 34: NUMBERP, ZEROP, ONEP, AND, EVAL, PLUS, TIMES, CAAR, CADR, etc., here
f2c04ccdad 2021-03-03 35: is an opportunity to reinforce the learning by practice. Write
f2c04ccdad 2021-03-03 36: expressions using CAR, CDR, CDDR, etc. (which are defined only through
f2c04ccdad 2021-03-03 37: 4 letters between C and R) to individually extract each atom from F,
f2c04ccdad 2021-03-03 38: where:;
f2c04ccdad 2021-03-03 39:
f2c04ccdad 2021-03-03 40: f := '((john . doe) (1147 hotel street) honolulu);
f2c04ccdad 2021-03-03 41: pause;
f2c04ccdad 2021-03-03 42:
f2c04ccdad 2021-03-03 43: COMMENT My solutions are CAAR F, CDAR F, CAADR F, CADADR F, CADDR CADR
f2c04ccdad 2021-03-03 44: F, and CADDR F.
f2c04ccdad 2021-03-03 45:
f2c04ccdad 2021-03-03 46: Although commonly the "." is only mentioned in conjunction with data, we
f2c04ccdad 2021-03-03 47: can also use it as an infix alias for CONS. Do this to build from F and
f2c04ccdad 2021-03-03 48: from the data 'MISTER the s-expression consisting of F with MISTER
f2c04ccdad 2021-03-03 49: inserted before JOHN.DOE;
f2c04ccdad 2021-03-03 50:
f2c04ccdad 2021-03-03 51: pause;
f2c04ccdad 2021-03-03 52:
f2c04ccdad 2021-03-03 53: COMMENT My solution is ('MISTER . CAR F) . CDR F.
f2c04ccdad 2021-03-03 54:
f2c04ccdad 2021-03-03 55: Enough of these inane exercises -- let's get on to something useful!
f2c04ccdad 2021-03-03 56: Let's develop a collection of functions for operating on finite sets.
f2c04ccdad 2021-03-03 57: We will let the elements be arbitrary s-expressions, and we will
f2c04ccdad 2021-03-03 58: represent a set as a list of its elements in arbitrary order, without
f2c04ccdad 2021-03-03 59: duplicates.
f2c04ccdad 2021-03-03 60:
f2c04ccdad 2021-03-03 61: Here is a function which determines whether its first argument is a
f2c04ccdad 2021-03-03 62: member of the set which is its second element;
f2c04ccdad 2021-03-03 63:
f2c04ccdad 2021-03-03 64: symbolic procedure memberp(elem, set1);
f2c04ccdad 2021-03-03 65: COMMENT Returns T if s-expression ELEM is a top-level element
f2c04ccdad 2021-03-03 66: of list SET1, returning NIL otherwise;
f2c04ccdad 2021-03-03 67: if null set1 then nil
f2c04ccdad 2021-03-03 68: else if elem = car set1 then t
f2c04ccdad 2021-03-03 69: else memberp(elem, cdr set1);
f2c04ccdad 2021-03-03 70:
f2c04ccdad 2021-03-03 71: memberp('blue, '(red blue green));
f2c04ccdad 2021-03-03 72:
f2c04ccdad 2021-03-03 73: COMMENT This function illustrates several convenient techniques for
f2c04ccdad 2021-03-03 74: writing functions which process lists:
f2c04ccdad 2021-03-03 75:
f2c04ccdad 2021-03-03 76: 1. To avoid the errors of taking the CAR or the CDR of an atom,
f2c04ccdad 2021-03-03 77: and to build self confidence while it is not immediately
f2c04ccdad 2021-03-03 78: apparent how to completely solve the problem, treat the trivial
f2c04ccdad 2021-03-03 79: cases first. For an s-expression or list argument, the most
f2c04ccdad 2021-03-03 80: trivial cases are generally when one or more of the arguments
f2c04ccdad 2021-03-03 81: are NIL, and a slightly less trivial case is when one or more
f2c04ccdad 2021-03-03 82: is an atom. (Note that we will get an error message if we use
f2c04ccdad 2021-03-03 83: MEMBERP with a second argument which is not a list. We could
f2c04ccdad 2021-03-03 84: check for this, but in the interest of brevity, I will not
f2c04ccdad 2021-03-03 85: strive to make our set-package give set-oriented error
f2c04ccdad 2021-03-03 86: messages.)
f2c04ccdad 2021-03-03 87: 2. Use CAR to extract the first element and use CDR to refer to
f2c04ccdad 2021-03-03 88: the remainder of the list.
f2c04ccdad 2021-03-03 89: 3. Use recursion to treat more complicated cases by extracting the
f2c04ccdad 2021-03-03 90: first element and using the same functions on smaller
f2c04ccdad 2021-03-03 91: arguments.;
f2c04ccdad 2021-03-03 92:
f2c04ccdad 2021-03-03 93: pause;
f2c04ccdad 2021-03-03 94:
f2c04ccdad 2021-03-03 95: COMMENT To make MEMBERP into an infix operator we make the declaration:;
f2c04ccdad 2021-03-03 96:
f2c04ccdad 2021-03-03 97: infix memberp;
f2c04ccdad 2021-03-03 98: '(john.doe) memberp '((fig.newton) fonzo (santa claus));
f2c04ccdad 2021-03-03 99:
f2c04ccdad 2021-03-03 100: COMMENT Infix operators associate left, meaning expressions of the form
f2c04ccdad 2021-03-03 101:
f2c04ccdad 2021-03-03 102: (operand1 operator operand2 operator ... operator operandN)
f2c04ccdad 2021-03-03 103:
f2c04ccdad 2021-03-03 104: are interpreted left-to-right as
f2c04ccdad 2021-03-03 105:
f2c04ccdad 2021-03-03 106: ((...(operand1 operator operand2) operator ...) operator operandN).
f2c04ccdad 2021-03-03 107:
f2c04ccdad 2021-03-03 108: Operators may also be flagged RIGHT by
f2c04ccdad 2021-03-03 109:
f2c04ccdad 2021-03-03 110: FLAG ('(op1 op2 ...), 'RIGHT).
f2c04ccdad 2021-03-03 111:
f2c04ccdad 2021-03-03 112: to give the interpretation
f2c04ccdad 2021-03-03 113:
f2c04ccdad 2021-03-03 114: (operand1 operator (operand2 operator (... operandN))...).
f2c04ccdad 2021-03-03 115:
f2c04ccdad 2021-03-03 116: Of the built-in operators, only ".", "*=", "+", and "*" associate right.
f2c04ccdad 2021-03-03 117:
f2c04ccdad 2021-03-03 118: If we had made the infix declaration before the function definition, the
f2c04ccdad 2021-03-03 119: latter could have begun with the more natural statement
f2c04ccdad 2021-03-03 120:
f2c04ccdad 2021-03-03 121: SYMBOLIC PROCEDURE ELEM MEMBERP SET.
f2c04ccdad 2021-03-03 122:
f2c04ccdad 2021-03-03 123: Infix functions can also be referred to by functional notation if one
f2c04ccdad 2021-03-03 124: desires. Actually, an analogous infix operator named MEMBER is
f2c04ccdad 2021-03-03 125: already built-into RLISP, so we will use MEMBER rather than MEMBERP
f2c04ccdad 2021-03-03 126: from here on. (But note that MEMBER returns the sublist beginning
f2c04ccdad 2021-03-03 127: with the first argument rather than T.);
f2c04ccdad 2021-03-03 128:
f2c04ccdad 2021-03-03 129: member(1147, cadr f);
f2c04ccdad 2021-03-03 130:
f2c04ccdad 2021-03-03 131: COMMENT Inspired by the simple yet elegant definition of MEMBERP, write
f2c04ccdad 2021-03-03 132: a function named SETP which uses MEMBER to check for a duplicate element
f2c04ccdad 2021-03-03 133: in its list argument, thus determining whether or not the argument of
f2c04ccdad 2021-03-03 134: SETP is a set;
f2c04ccdad 2021-03-03 135:
f2c04ccdad 2021-03-03 136: pause;
f2c04ccdad 2021-03-03 137:
f2c04ccdad 2021-03-03 138: COMMENT My solution is;
f2c04ccdad 2021-03-03 139:
f2c04ccdad 2021-03-03 140: symbolic procedure setp candidate;
f2c04ccdad 2021-03-03 141: COMMENT Returns T if list CANDIDATE is a set, returning NIL
f2c04ccdad 2021-03-03 142: otherwise;
f2c04ccdad 2021-03-03 143: if null candidate then t
f2c04ccdad 2021-03-03 144: else if car candidate member cdr candidate then nil
f2c04ccdad 2021-03-03 145: else setp cdr candidate;
f2c04ccdad 2021-03-03 146:
f2c04ccdad 2021-03-03 147: setp '(kermit, (cookie monster));
f2c04ccdad 2021-03-03 148: setp '(dog cat dog);
f2c04ccdad 2021-03-03 149:
f2c04ccdad 2021-03-03 150: COMMENT If you used a BEGIN-block, local variables, loops, etc., then
f2c04ccdad 2021-03-03 151: your solution is surely more awkward than mine. For the duration of
f2c04ccdad 2021-03-03 152: the lesson, try to do everything without groups, BEGIN-blocks, local
f2c04ccdad 2021-03-03 153: variables, assignments, and loops. Everything can be done using
f2c04ccdad 2021-03-03 154: function composition, conditional expressions, and recursion. It will
f2c04ccdad 2021-03-03 155: be a mind-expanding experience -- more so than transcendental
f2c04ccdad 2021-03-03 156: meditation, psilopsybin, and EST. Afterward, you can revert to your
f2c04ccdad 2021-03-03 157: old ways if you disagree.
f2c04ccdad 2021-03-03 158:
f2c04ccdad 2021-03-03 159: Thus endeth the sermon.
f2c04ccdad 2021-03-03 160:
f2c04ccdad 2021-03-03 161: Incidentally, to make the above definition of SETP work for non-list
f2c04ccdad 2021-03-03 162: arguments all we have to do is insert "ELSE IF ATOM CANDIDATE THEN
f2c04ccdad 2021-03-03 163: NIL" below "IF NULL CANDIDATE THEN T".
f2c04ccdad 2021-03-03 164:
f2c04ccdad 2021-03-03 165: Now try to write an infix procedure named SUBSETOF, such that SET1
f2c04ccdad 2021-03-03 166: SUBSETOF SET2 returns NIL if SET1 contains an element that SET2 does
f2c04ccdad 2021-03-03 167: not, returning T otherwise. You are always encouraged, by the way, to
f2c04ccdad 2021-03-03 168: use any functions that are already builtin, or that we have previously
f2c04ccdad 2021-03-03 169: defined, or that you define later as auxiliary functions.;
f2c04ccdad 2021-03-03 170:
f2c04ccdad 2021-03-03 171: pause;
f2c04ccdad 2021-03-03 172:
f2c04ccdad 2021-03-03 173: COMMENT My solution is;
f2c04ccdad 2021-03-03 174:
f2c04ccdad 2021-03-03 175: infix subsetof;
f2c04ccdad 2021-03-03 176: symbolic procedure set1 subsetof set2;
f2c04ccdad 2021-03-03 177: if null set1 then t
f2c04ccdad 2021-03-03 178: else if car set1 member set2 then cdr set1 subsetof set2
f2c04ccdad 2021-03-03 179: else nil;
f2c04ccdad 2021-03-03 180:
f2c04ccdad 2021-03-03 181: '(roof door) subsetof '(window door floor roof);
f2c04ccdad 2021-03-03 182: '(apple banana) subsetof '((apple cobbler) (banana creme pie));
f2c04ccdad 2021-03-03 183:
f2c04ccdad 2021-03-03 184: COMMENT Two sets are equal when they have identical elements, not
f2c04ccdad 2021-03-03 185: necessarily in the same order. Write an infix procedure named EQSETP
f2c04ccdad 2021-03-03 186: which returns T if its two operands are equal sets, returning NIL
f2c04ccdad 2021-03-03 187: otherwise.;
f2c04ccdad 2021-03-03 188:
f2c04ccdad 2021-03-03 189: pause;
f2c04ccdad 2021-03-03 190:
f2c04ccdad 2021-03-03 191: COMMENT The following solution introduces the PRECEDENCE declaration:;
f2c04ccdad 2021-03-03 192:
f2c04ccdad 2021-03-03 193: infix eqsetp;
f2c04ccdad 2021-03-03 194: precedence eqsetp, =;
f2c04ccdad 2021-03-03 195: precedence subsetof, eqsetp;
f2c04ccdad 2021-03-03 196: symbolic procedure set1 eqsetp set2;
f2c04ccdad 2021-03-03 197: set1 subsetof set2 and set2 subsetof set1;
f2c04ccdad 2021-03-03 198:
f2c04ccdad 2021-03-03 199: '(ballet tap) eqsetp '(tap ballet);
f2c04ccdad 2021-03-03 200: '(pine fir aspen) eqsetp '(pine fir palm);
f2c04ccdad 2021-03-03 201:
f2c04ccdad 2021-03-03 202: COMMENT The precedence declarations make SUBSETOF have a higher
f2c04ccdad 2021-03-03 203: precedence than EQSETP and make the latter have higher precedence than
f2c04ccdad 2021-03-03 204: "=", which is higher than "AND". Consequently, these declarations
f2c04ccdad 2021-03-03 205: enabled me to omit parentheses around "SET1 SUBSUBSETOF SET2" and
f2c04ccdad 2021-03-03 206: around "SET2 SUBSETOF SET1". All prefix operators have higher
f2c04ccdad 2021-03-03 207: precedence than any infix operator, and to inspect the ordering among
f2c04ccdad 2021-03-03 208: the latter, we merely inspect the value of the global variable named;
f2c04ccdad 2021-03-03 209:
f2c04ccdad 2021-03-03 210: preclis!*;
f2c04ccdad 2021-03-03 211:
f2c04ccdad 2021-03-03 212: COMMENT Now see if you can write a REDUCE infix function named
f2c04ccdad 2021-03-03 213: PROPERSUBSETOF, which determines if its left operand is a proper
f2c04ccdad 2021-03-03 214: subset of its right operand, meaning it is a subset which is not equal
f2c04ccdad 2021-03-03 215: to the right operand.;
f2c04ccdad 2021-03-03 216:
f2c04ccdad 2021-03-03 217: pause;
f2c04ccdad 2021-03-03 218:
f2c04ccdad 2021-03-03 219: COMMENT All of the above exercises have been predicates. In contrast,
f2c04ccdad 2021-03-03 220: the next exercise is to write a function called MAKESET, which returns
f2c04ccdad 2021-03-03 221: a list which is a copy of its argument, omitting duplicates.;
f2c04ccdad 2021-03-03 222:
f2c04ccdad 2021-03-03 223: pause;
f2c04ccdad 2021-03-03 224:
f2c04ccdad 2021-03-03 225: COMMENT How about:;
f2c04ccdad 2021-03-03 226:
f2c04ccdad 2021-03-03 227: symbolic procedure makeset lis;
f2c04ccdad 2021-03-03 228: if null lis then nil
f2c04ccdad 2021-03-03 229: else if car lis member cdr lis then makeset cdr lis
f2c04ccdad 2021-03-03 230: else car lis . makeset cdr lis;
f2c04ccdad 2021-03-03 231:
f2c04ccdad 2021-03-03 232: COMMENT As you may have guessed, the next exercise is to implement an
f2c04ccdad 2021-03-03 233: operator named INTERSECT, which returns the intersection of its set
f2c04ccdad 2021-03-03 234: operands.;
f2c04ccdad 2021-03-03 235:
f2c04ccdad 2021-03-03 236: pause;
f2c04ccdad 2021-03-03 237:
f2c04ccdad 2021-03-03 238: COMMENT Here is my solution:;
f2c04ccdad 2021-03-03 239:
f2c04ccdad 2021-03-03 240: infix intersect;
f2c04ccdad 2021-03-03 241: precedence intersect, subsetof;
f2c04ccdad 2021-03-03 242: symbolic procedure set1 intersect set2;
f2c04ccdad 2021-03-03 243: if null set1 then nil
f2c04ccdad 2021-03-03 244: else if car set1 member set2
f2c04ccdad 2021-03-03 245: then car set1 . cdr set1 intersect set2
f2c04ccdad 2021-03-03 246: else cdr set1 intersect set2;
f2c04ccdad 2021-03-03 247:
f2c04ccdad 2021-03-03 248: COMMENT Symbolic-mode REDUCE has a built-in function named SETDIFF,
f2c04ccdad 2021-03-03 249: which returns the set of elements which are in its first argument but
f2c04ccdad 2021-03-03 250: not the second. See if you can write an infix definition of a similar
f2c04ccdad 2021-03-03 251: function named DIFFSET.;
f2c04ccdad 2021-03-03 252:
f2c04ccdad 2021-03-03 253: pause;
f2c04ccdad 2021-03-03 254:
f2c04ccdad 2021-03-03 255: COMMENT Presenting --:;
f2c04ccdad 2021-03-03 256:
f2c04ccdad 2021-03-03 257: infix diffset;
f2c04ccdad 2021-03-03 258: precedence diffset, intersect;
f2c04ccdad 2021-03-03 259: symbolic procedure left diffset right;
f2c04ccdad 2021-03-03 260: if null left then nil
f2c04ccdad 2021-03-03 261: else if car left member right then cdr left diffset right
f2c04ccdad 2021-03-03 262: else car left . (cdr left diffset right);
f2c04ccdad 2021-03-03 263:
f2c04ccdad 2021-03-03 264: '(seagull wren condor) diffset '(wren lark);
f2c04ccdad 2021-03-03 265:
f2c04ccdad 2021-03-03 266: COMMENT The symmetric difference of two sets is the set of all
f2c04ccdad 2021-03-03 267: elements which are in only one of the two sets. Implement a
f2c04ccdad 2021-03-03 268: corresponding infix function named SYMDIFF. Look for the easy way!
f2c04ccdad 2021-03-03 269: There is almost always one for examinations and instructional
f2c04ccdad 2021-03-03 270: exercises.;
f2c04ccdad 2021-03-03 271:
f2c04ccdad 2021-03-03 272: pause;
f2c04ccdad 2021-03-03 273:
f2c04ccdad 2021-03-03 274: COMMENT Presenting --:;
f2c04ccdad 2021-03-03 275:
f2c04ccdad 2021-03-03 276: infix symdiff;
f2c04ccdad 2021-03-03 277: precedence symdiff, intersect;
f2c04ccdad 2021-03-03 278: symbolic procedure set1 symdiff set2;
f2c04ccdad 2021-03-03 279: append(set1 diffset set2, set2 diffset set1);
f2c04ccdad 2021-03-03 280:
f2c04ccdad 2021-03-03 281: '(seagull wren condor) symdiff '(wren lark);
f2c04ccdad 2021-03-03 282:
f2c04ccdad 2021-03-03 283: COMMENT We can use APPEND because the two set differences are
f2c04ccdad 2021-03-03 284: disjoint.
f2c04ccdad 2021-03-03 285:
f2c04ccdad 2021-03-03 286: The above set of exercises (exercises of set?) have all returned set
f2c04ccdad 2021-03-03 287: results. The cardinality, size, or length of a set is the number of
f2c04ccdad 2021-03-03 288: elements in the set. More generally, it is useful to have a function
f2c04ccdad 2021-03-03 289: which returns the length of its list argument, and such a function is
f2c04ccdad 2021-03-03 290: built-into RLISP. See if you can write a similar function named
f2c04ccdad 2021-03-03 291: SIZEE.;
f2c04ccdad 2021-03-03 292:
f2c04ccdad 2021-03-03 293: pause;
f2c04ccdad 2021-03-03 294:
f2c04ccdad 2021-03-03 295: COMMENT Presenting --:;
f2c04ccdad 2021-03-03 296:
f2c04ccdad 2021-03-03 297: symbolic procedure sizee lis;
f2c04ccdad 2021-03-03 298: if null lis then 0
f2c04ccdad 2021-03-03 299: else 1 + sizee cdr lis;
f2c04ccdad 2021-03-03 300:
f2c04ccdad 2021-03-03 301: sizee '(how marvelously concise);
f2c04ccdad 2021-03-03 302: sizee '();
f2c04ccdad 2021-03-03 303:
f2c04ccdad 2021-03-03 304: COMMENT Literal atoms, meaning atoms which are not numbers, are stored
f2c04ccdad 2021-03-03 305: uniquely in LISP and in RLISP, so comparison for equality of literal
f2c04ccdad 2021-03-03 306: atoms can be implemented by comparing their addresses, which is
f2c04ccdad 2021-03-03 307: significantly more efficient than a character-by-character comparison
f2c04ccdad 2021-03-03 308: of their names. The comparison operator "EQ" compares addresses, so
f2c04ccdad 2021-03-03 309: it is the most efficient choice when comparing only literal atoms.
f2c04ccdad 2021-03-03 310: The assignments
f2c04ccdad 2021-03-03 311:
f2c04ccdad 2021-03-03 312: N2 := N1 := 987654321,
f2c04ccdad 2021-03-03 313: S2 := S1 := '(FROG (SALAMANDER.NEWT)),
f2c04ccdad 2021-03-03 314:
f2c04ccdad 2021-03-03 315: make N2 have the same address as N1 and make S2 have the same address
f2c04ccdad 2021-03-03 316: as S1, but if N1 and N2 were constructed independently, they would not
f2c04ccdad 2021-03-03 317: generally have the same address, and similarly for S1 vs. S2. The
f2c04ccdad 2021-03-03 318: comparison operator "=", which is an alias for "EQUAL", does a general
f2c04ccdad 2021-03-03 319: test for identical s-expressions, which need not be merely two
f2c04ccdad 2021-03-03 320: pointers to the same address. Since "=" is built-in, compiled, and
f2c04ccdad 2021-03-03 321: crucial, I will define my own differently-named version denoted "..="
f2c04ccdad 2021-03-03 322: as follows:;
f2c04ccdad 2021-03-03 323:
f2c04ccdad 2021-03-03 324: pause;
f2c04ccdad 2021-03-03 325:
f2c04ccdad 2021-03-03 326: newtok '((!. !. !=) myequal);
f2c04ccdad 2021-03-03 327: infix eqatom, myequal;
f2c04ccdad 2021-03-03 328: precedence myequal, equal;
f2c04ccdad 2021-03-03 329: precedence eqatom, eq;
f2c04ccdad 2021-03-03 330: symbolic procedure s1 myequal s2;
f2c04ccdad 2021-03-03 331: if atom s1 then
f2c04ccdad 2021-03-03 332: if atom s2 then s1 eqatom s2
f2c04ccdad 2021-03-03 333: else nil
f2c04ccdad 2021-03-03 334: else if atom s2 then nil
f2c04ccdad 2021-03-03 335: else car s1 myequal car s2 and cdr s1 myequal cdr s2;
f2c04ccdad 2021-03-03 336: symbolic procedure a1 eqatom a2;
f2c04ccdad 2021-03-03 337: if numberp a1 then
f2c04ccdad 2021-03-03 338: if numberp a2 then zerop(a1-a2)
f2c04ccdad 2021-03-03 339: else nil
f2c04ccdad 2021-03-03 340: else if numberp a2 then nil
f2c04ccdad 2021-03-03 341: else a1 eq a2;
f2c04ccdad 2021-03-03 342:
f2c04ccdad 2021-03-03 343: COMMENT Here I introduced a help function named EQATOM, because I was
f2c04ccdad 2021-03-03 344: beginning to become confused by detail when I got to the line which
f2c04ccdad 2021-03-03 345: uses EQATOM. Consequently, I procrastinated on attending to some fine
f2c04ccdad 2021-03-03 346: detail by relegating it to a help function which I was confident could
f2c04ccdad 2021-03-03 347: be successfully written later. After completing MYEQUAL, I was
f2c04ccdad 2021-03-03 348: confident that it would work provided EQATOM worked, so I could then
f2c04ccdad 2021-03-03 349: turn my attention entirely to EQATOM, freed of further distraction by
f2c04ccdad 2021-03-03 350: concern about the more ambitious overall goal. It turns out that
f2c04ccdad 2021-03-03 351: EQATOM is a rather handy utility function anyway, and practice helps
f2c04ccdad 2021-03-03 352: develop good judgement about where best to so subdivide tasks. This
f2c04ccdad 2021-03-03 353: psychological divide-and-conquer programming technique is important in
f2c04ccdad 2021-03-03 354: most other programming languages too.
f2c04ccdad 2021-03-03 355:
f2c04ccdad 2021-03-03 356: "..=" is different from our previous examples in that "..=" recurses
f2c04ccdad 2021-03-03 357: down the CAR as well as down the CDR of an s-expression.;
f2c04ccdad 2021-03-03 358:
f2c04ccdad 2021-03-03 359: pause;
f2c04ccdad 2021-03-03 360:
f2c04ccdad 2021-03-03 361: COMMENT If a list has n elements, our function named MEMBERP or the
f2c04ccdad 2021-03-03 362: equivalent built-in function named MEMBER requires on the order of n
f2c04ccdad 2021-03-03 363: "=" tests. Consequently, the above definitions of SETP and MAKESET,
f2c04ccdad 2021-03-03 364: which require on the order of n membership tests, will require on the
f2c04ccdad 2021-03-03 365: order of n^2 "=" tests. Similarly, if the two operands have m and n
f2c04ccdad 2021-03-03 366: elements, the above definitions of SUBSETOF, EQSETP, INTERSECT,
f2c04ccdad 2021-03-03 367: DIFFSET, and SYMDIFF require on the order of m*n "=" tests. We could
f2c04ccdad 2021-03-03 368: decrease the growth rates to order of n and order of m+n respectively
f2c04ccdad 2021-03-03 369: by sorting the elements before giving lists to these functions. The
f2c04ccdad 2021-03-03 370: best algorithms sort a list of n elements in the order of n*log(n)
f2c04ccdad 2021-03-03 371: element comparisons, and this need be done only once per input set.
f2c04ccdad 2021-03-03 372: To do so we need a function which returns T if the first argument is
f2c04ccdad 2021-03-03 373: "=" to the second argument or should be placed to the left of the
f2c04ccdad 2021-03-03 374: second argument. Such a function, named ORDP, is already built-into
f2c04ccdad 2021-03-03 375: symbolic-mode REDUCE, based on the following rules:
f2c04ccdad 2021-03-03 376:
f2c04ccdad 2021-03-03 377: 1. Any number orders left of NIL.
f2c04ccdad 2021-03-03 378: 2. Larger numbers order left of smaller numbers.
f2c04ccdad 2021-03-03 379: 4. Literal atoms order left of numbers.
f2c04ccdad 2021-03-03 380: 3. Literal atoms order among themselves by address, as determined
f2c04ccdad 2021-03-03 381: by the built-in RLISP function named ORDERP.
f2c04ccdad 2021-03-03 382: 5. Non-atoms order left of atoms.
f2c04ccdad 2021-03-03 383: 6. Non-atoms order among themselves according to ORDP of their
f2c04ccdad 2021-03-03 384: CARs, with ties broken according to ORDP of their CDRs.
f2c04ccdad 2021-03-03 385:
f2c04ccdad 2021-03-03 386: Try writing an analogous function named MYORD, and, if you are in
f2c04ccdad 2021-03-03 387: REDUCE rather than RLISP, test its behavior in comparison to ORDP.;
f2c04ccdad 2021-03-03 388:
f2c04ccdad 2021-03-03 389: pause;
f2c04ccdad 2021-03-03 390:
f2c04ccdad 2021-03-03 391: COMMENT Whether or not we use sorted sets, we can reduce the
f2c04ccdad 2021-03-03 392: proportionality constant associated with the growth rate by replacing
f2c04ccdad 2021-03-03 393: "=" by "EQ" if the set elements are restricted to literal atoms.
f2c04ccdad 2021-03-03 394: However, with such elements we can use property-lists to achieve the
f2c04ccdad 2021-03-03 395: growth rates of the sorted algorithms without any need to sort the
f2c04ccdad 2021-03-03 396: sets. On any LISP system that is efficient enough to support REDUCE
f2c04ccdad 2021-03-03 397: with acceptable performance, the time required to access a property of
f2c04ccdad 2021-03-03 398: an atom is modest and very insensitive to the number of distinct atoms
f2c04ccdad 2021-03-03 399: in the program and data. Consequently, the basic technique for any of
f2c04ccdad 2021-03-03 400: our set operations is:
f2c04ccdad 2021-03-03 401:
f2c04ccdad 2021-03-03 402: 1. Scan the list argument or one of the two list arguments,
f2c04ccdad 2021-03-03 403: flagging each element as "SEEN".
f2c04ccdad 2021-03-03 404: 2. During the first scan, or during a second scan of the same
f2c04ccdad 2021-03-03 405: list, or during a scan of the second list, check each element
f2c04ccdad 2021-03-03 406: to see whether or not it has already been flagged, and act
f2c04ccdad 2021-03-03 407: accordingly.
f2c04ccdad 2021-03-03 408: 3. Make a final pass through all elements which were flagged to
f2c04ccdad 2021-03-03 409: remove the flag "SEEN". (Otherwise, we may invalidate later set
f2c04ccdad 2021-03-03 410: operations which utilize any of the same atoms.)
f2c04ccdad 2021-03-03 411:
f2c04ccdad 2021-03-03 412: We could use indicators rather than flags, but the latter are slightly
f2c04ccdad 2021-03-03 413: more efficient when an indicator would have only one value (such as
f2c04ccdad 2021-03-03 414: having "SEEN" as the value of an indicator named "SEENORNOT").
f2c04ccdad 2021-03-03 415:
f2c04ccdad 2021-03-03 416: As an example, here is INTERSECT defined using this technique;
f2c04ccdad 2021-03-03 417:
f2c04ccdad 2021-03-03 418: symbolic procedure intersect(s1, s2);
f2c04ccdad 2021-03-03 419: begin scalar ans, set2;
f2c04ccdad 2021-03-03 420: flag(s1, 'seen);
f2c04ccdad 2021-03-03 421: set2 := s2;
f2c04ccdad 2021-03-03 422: while set2 do <<
f2c04ccdad 2021-03-03 423: if flagp(car set2, 'seen) then ans := car set2 . ans;
f2c04ccdad 2021-03-03 424: set2 := cdr set2 >>;
f2c04ccdad 2021-03-03 425: remflag(s1, 'seen);
f2c04ccdad 2021-03-03 426: return ans
f2c04ccdad 2021-03-03 427: end;
f2c04ccdad 2021-03-03 428:
f2c04ccdad 2021-03-03 429: COMMENT Perhaps you noticed that, having used a BEGIN-block, group,
f2c04ccdad 2021-03-03 430: loop, and assignments, I have not practiced what I preached about
f2c04ccdad 2021-03-03 431: using only function composition, conditional expressions, and
f2c04ccdad 2021-03-03 432: recursion during this lesson. Well, now that you have had some
f2c04ccdad 2021-03-03 433: exposure to both extremes, I think you should always fairly consider
f2c04ccdad 2021-03-03 434: both together with appropriate compromises, in each case choosing
f2c04ccdad 2021-03-03 435: whatever is most clear, concise, and natural. For set operations
f2c04ccdad 2021-03-03 436: based on the property-list approach, I find the style exemplified
f2c04ccdad 2021-03-03 437: immediately above most natural.
f2c04ccdad 2021-03-03 438:
f2c04ccdad 2021-03-03 439: As your last exercise for this lesson, develop a file containing a
f2c04ccdad 2021-03-03 440: package for set operations based upon either property-lists or
f2c04ccdad 2021-03-03 441: sorting.
f2c04ccdad 2021-03-03 442:
f2c04ccdad 2021-03-03 443: This is the end of lesson 6. When you are ready to run the final
f2c04ccdad 2021-03-03 444: lesson 7, load a fresh copy of REDUCE.
f2c04ccdad 2021-03-03 445:
f2c04ccdad 2021-03-03 446: ;end;