Origin for each line in Lesson_6.red from check-in 5f892713c3:

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

iCAS Bundled REDUCE Scripts
Homepage | GitHub Mirror | SourceHut Mirror | NotABug Mirror | Chisel Mirror | Chisel RSS ]