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

f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT
f2c04ccdad 2021-03-03 trnsz@pobox.c:  
f2c04ccdad 2021-03-03 trnsz@pobox.c:                   REDUCE INTERACTIVE LESSON NUMBER 6
f2c04ccdad 2021-03-03 trnsz@pobox.c:  
f2c04ccdad 2021-03-03 trnsz@pobox.c:                          David R. Stoutemyer
f2c04ccdad 2021-03-03 trnsz@pobox.c:                          University of Hawaii
f2c04ccdad 2021-03-03 trnsz@pobox.c:  
f2c04ccdad 2021-03-03 trnsz@pobox.c:  
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT This is lesson 6 of 7 REDUCE lessons.  A prerequisite is to
f2c04ccdad 2021-03-03 trnsz@pobox.c: read an introductory text about LISP, such as "A Concise Introduction
f2c04ccdad 2021-03-03 trnsz@pobox.c: to LISP" by David L. Matuszek, which is freely available at
f2c04ccdad 2021-03-03 trnsz@pobox.c: https://www.cis.upenn.edu/~matuszek/LispText/lisp.html.  Then
f2c04ccdad 2021-03-03 trnsz@pobox.c: familiarize yourself with the Standard Lisp Report, which is freely
f2c04ccdad 2021-03-03 trnsz@pobox.c: available via http://reduce-algebra.sourceforge.net/documentation.php.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: To avoid confusion between RLISP and the SYMBOLIC-mode algebraic
f2c04ccdad 2021-03-03 trnsz@pobox.c: algorithms, this lesson will treat only RLISP.  Lesson 7 deals with how
f2c04ccdad 2021-03-03 trnsz@pobox.c: the REDUCE algebraic mode is implemented in RLISP and how the user can
f2c04ccdad 2021-03-03 trnsz@pobox.c: interact directly with that implementation.  That is why I suggested
f2c04ccdad 2021-03-03 trnsz@pobox.c: that you run this lesson in RLISP rather than full REDUCE.  If you
f2c04ccdad 2021-03-03 trnsz@pobox.c: forgot or do not have a locally available separate RLISP, then please
f2c04ccdad 2021-03-03 trnsz@pobox.c: switch now to symbolic mode by typing the statement SYMBOLIC.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic;
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Your most frequent mistakes are likely to be forgetting to quote
f2c04ccdad 2021-03-03 trnsz@pobox.c: data examples, using commas as separators within lists, and not putting
f2c04ccdad 2021-03-03 trnsz@pobox.c: enough levels of parentheses in your data examples.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Having learnt from reading the Standard Lisp Report about the built-in
f2c04ccdad 2021-03-03 trnsz@pobox.c: RLISP functions CAR, CDR, CONS, ATOM, EQ, NULL, LIST, APPEND, REVERSE,
f2c04ccdad 2021-03-03 trnsz@pobox.c: DELETE, MAPLIST, MAPCON, LAMBDA, FLAG, FLAGP, PUT, GET, DEFLIST,
f2c04ccdad 2021-03-03 trnsz@pobox.c: NUMBERP, ZEROP, ONEP, AND, EVAL, PLUS, TIMES, CAAR, CADR, etc., here
f2c04ccdad 2021-03-03 trnsz@pobox.c: is an opportunity to reinforce the learning by practice.  Write
f2c04ccdad 2021-03-03 trnsz@pobox.c: expressions using CAR, CDR, CDDR, etc. (which are defined only through
f2c04ccdad 2021-03-03 trnsz@pobox.c: 4 letters between C and R) to individually extract each atom from F,
f2c04ccdad 2021-03-03 trnsz@pobox.c: where:;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: f := '((john . doe) (1147 hotel street) honolulu);
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT My solutions are CAAR F, CDAR F, CAADR F, CADADR F, CADDR CADR
f2c04ccdad 2021-03-03 trnsz@pobox.c: F, and CADDR F.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Although commonly the "." is only mentioned in conjunction with data, we
f2c04ccdad 2021-03-03 trnsz@pobox.c: can also use it as an infix alias for CONS.  Do this to build from F and
f2c04ccdad 2021-03-03 trnsz@pobox.c: from the data 'MISTER the s-expression consisting of F with MISTER
f2c04ccdad 2021-03-03 trnsz@pobox.c: inserted before JOHN.DOE;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT My solution is ('MISTER . CAR F) . CDR F.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Enough of these inane exercises -- let's get on to something useful!
f2c04ccdad 2021-03-03 trnsz@pobox.c: Let's develop a collection of functions for operating on finite sets.
f2c04ccdad 2021-03-03 trnsz@pobox.c: We will let the elements be arbitrary s-expressions, and we will
f2c04ccdad 2021-03-03 trnsz@pobox.c: represent a set as a list of its elements in arbitrary order, without
f2c04ccdad 2021-03-03 trnsz@pobox.c: duplicates.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Here is a function which determines whether its first argument is a
f2c04ccdad 2021-03-03 trnsz@pobox.c: member of the set which is its second element;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure memberp(elem, set1);
f2c04ccdad 2021-03-03 trnsz@pobox.c:    COMMENT Returns T if s-expression ELEM is a top-level element
f2c04ccdad 2021-03-03 trnsz@pobox.c:       of list SET1, returning NIL otherwise;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    if null set1 then nil
f2c04ccdad 2021-03-03 trnsz@pobox.c:       else if elem = car set1 then t
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else memberp(elem, cdr set1);
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: memberp('blue, '(red blue green));
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT This function illustrates several convenient techniques for
f2c04ccdad 2021-03-03 trnsz@pobox.c: writing functions which process lists:
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c:    1.  To avoid the errors of taking the CAR or the CDR of an atom,
f2c04ccdad 2021-03-03 trnsz@pobox.c:        and to build self confidence while it is not immediately
f2c04ccdad 2021-03-03 trnsz@pobox.c:        apparent how to completely solve the problem, treat the trivial
f2c04ccdad 2021-03-03 trnsz@pobox.c:        cases first.  For an s-expression or list argument, the most
f2c04ccdad 2021-03-03 trnsz@pobox.c:        trivial cases are generally when one or more of the arguments
f2c04ccdad 2021-03-03 trnsz@pobox.c:        are NIL, and a slightly less trivial case is when one or more
f2c04ccdad 2021-03-03 trnsz@pobox.c:        is an atom.  (Note that we will get an error message if we use
f2c04ccdad 2021-03-03 trnsz@pobox.c:        MEMBERP with a second argument which is not a list.  We could
f2c04ccdad 2021-03-03 trnsz@pobox.c:        check for this, but in the interest of brevity, I will not
f2c04ccdad 2021-03-03 trnsz@pobox.c:        strive to make our set-package give set-oriented error
f2c04ccdad 2021-03-03 trnsz@pobox.c:        messages.)
f2c04ccdad 2021-03-03 trnsz@pobox.c:    2.  Use CAR to extract the first element and use CDR to refer to
f2c04ccdad 2021-03-03 trnsz@pobox.c:        the remainder of the list.
f2c04ccdad 2021-03-03 trnsz@pobox.c:    3.  Use recursion to treat more complicated cases by extracting the
f2c04ccdad 2021-03-03 trnsz@pobox.c:        first element and using the same functions on smaller
f2c04ccdad 2021-03-03 trnsz@pobox.c:        arguments.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT To make MEMBERP into an infix operator we make the declaration:;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: infix memberp;
f2c04ccdad 2021-03-03 trnsz@pobox.c: '(john.doe) memberp '((fig.newton) fonzo (santa claus));
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Infix operators associate left, meaning expressions of the form
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c:    (operand1 operator operand2 operator ... operator operandN)
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: are interpreted left-to-right as
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c:    ((...(operand1 operator operand2) operator ...) operator operandN).
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Operators may also be flagged RIGHT by
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c:    FLAG ('(op1 op2 ...), 'RIGHT).
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: to give the interpretation
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c:    (operand1 operator (operand2 operator (... operandN))...).
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Of the built-in operators, only ".", "*=", "+", and "*" associate right.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: If we had made the infix declaration before the function definition, the
f2c04ccdad 2021-03-03 trnsz@pobox.c: latter could have begun with the more natural statement
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c:    SYMBOLIC PROCEDURE ELEM MEMBERP SET.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Infix functions can also be referred to by functional notation if one
f2c04ccdad 2021-03-03 trnsz@pobox.c: desires.  Actually, an analogous infix operator named MEMBER is
f2c04ccdad 2021-03-03 trnsz@pobox.c: already built-into RLISP, so we will use MEMBER rather than MEMBERP
f2c04ccdad 2021-03-03 trnsz@pobox.c: from here on.  (But note that MEMBER returns the sublist beginning
f2c04ccdad 2021-03-03 trnsz@pobox.c: with the first argument rather than T.);
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: member(1147, cadr f);
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Inspired by the simple yet elegant definition of MEMBERP, write
f2c04ccdad 2021-03-03 trnsz@pobox.c: a function named SETP which uses MEMBER to check for a duplicate element
f2c04ccdad 2021-03-03 trnsz@pobox.c: in its list argument, thus determining whether or not the argument of
f2c04ccdad 2021-03-03 trnsz@pobox.c: SETP is a set;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT My solution is;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure setp candidate;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    COMMENT Returns T if list CANDIDATE is a set, returning NIL
f2c04ccdad 2021-03-03 trnsz@pobox.c:       otherwise;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    if null candidate then t
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else if car candidate member cdr candidate then nil
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else setp cdr candidate;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: setp '(kermit, (cookie monster));
f2c04ccdad 2021-03-03 trnsz@pobox.c: setp '(dog cat dog);
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT If you used a BEGIN-block, local variables, loops, etc., then
f2c04ccdad 2021-03-03 trnsz@pobox.c: your solution is surely more awkward than mine.  For the duration of
f2c04ccdad 2021-03-03 trnsz@pobox.c: the lesson, try to do everything without groups, BEGIN-blocks, local
f2c04ccdad 2021-03-03 trnsz@pobox.c: variables, assignments, and loops.  Everything can be done using
f2c04ccdad 2021-03-03 trnsz@pobox.c: function composition, conditional expressions, and recursion.  It will
f2c04ccdad 2021-03-03 trnsz@pobox.c: be a mind-expanding experience -- more so than transcendental
f2c04ccdad 2021-03-03 trnsz@pobox.c: meditation, psilopsybin, and EST.  Afterward, you can revert to your
f2c04ccdad 2021-03-03 trnsz@pobox.c: old ways if you disagree.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Thus endeth the sermon.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Incidentally, to make the above definition of SETP work for non-list
f2c04ccdad 2021-03-03 trnsz@pobox.c: arguments all we have to do is insert "ELSE IF ATOM CANDIDATE THEN
f2c04ccdad 2021-03-03 trnsz@pobox.c: NIL" below "IF NULL CANDIDATE THEN T".
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Now try to write an infix procedure named SUBSETOF, such that SET1
f2c04ccdad 2021-03-03 trnsz@pobox.c: SUBSETOF SET2 returns NIL if SET1 contains an element that SET2 does
f2c04ccdad 2021-03-03 trnsz@pobox.c: not, returning T otherwise.  You are always encouraged, by the way, to
f2c04ccdad 2021-03-03 trnsz@pobox.c: use any functions that are already builtin, or that we have previously
f2c04ccdad 2021-03-03 trnsz@pobox.c: defined, or that you define later as auxiliary functions.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT My solution is;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: infix subsetof;
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure set1 subsetof set2;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    if null set1 then t
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else if car set1 member set2 then cdr set1 subsetof set2
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else nil;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: '(roof door) subsetof '(window door floor roof);
f2c04ccdad 2021-03-03 trnsz@pobox.c: '(apple banana) subsetof '((apple cobbler) (banana creme pie));
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Two sets are equal when they have identical elements, not
f2c04ccdad 2021-03-03 trnsz@pobox.c: necessarily in the same order.  Write an infix procedure named EQSETP
f2c04ccdad 2021-03-03 trnsz@pobox.c: which returns T if its two operands are equal sets, returning NIL
f2c04ccdad 2021-03-03 trnsz@pobox.c: otherwise.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT The following solution introduces the PRECEDENCE declaration:;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: infix eqsetp;
f2c04ccdad 2021-03-03 trnsz@pobox.c: precedence eqsetp, =;
f2c04ccdad 2021-03-03 trnsz@pobox.c: precedence subsetof, eqsetp;
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure set1 eqsetp set2;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    set1 subsetof set2  and  set2 subsetof set1;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: '(ballet tap) eqsetp '(tap ballet);
f2c04ccdad 2021-03-03 trnsz@pobox.c: '(pine fir aspen) eqsetp '(pine fir palm);
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT The precedence declarations make SUBSETOF have a higher
f2c04ccdad 2021-03-03 trnsz@pobox.c: precedence than EQSETP and make the latter have higher precedence than
f2c04ccdad 2021-03-03 trnsz@pobox.c: "=", which is higher than "AND".  Consequently, these declarations
f2c04ccdad 2021-03-03 trnsz@pobox.c: enabled me to omit parentheses around "SET1 SUBSUBSETOF SET2" and
f2c04ccdad 2021-03-03 trnsz@pobox.c: around "SET2 SUBSETOF SET1".  All prefix operators have higher
f2c04ccdad 2021-03-03 trnsz@pobox.c: precedence than any infix operator, and to inspect the ordering among
f2c04ccdad 2021-03-03 trnsz@pobox.c: the latter, we merely inspect the value of the global variable named;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: preclis!*;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Now see if you can write a REDUCE infix function named
f2c04ccdad 2021-03-03 trnsz@pobox.c: PROPERSUBSETOF, which determines if its left operand is a proper
f2c04ccdad 2021-03-03 trnsz@pobox.c: subset of its right operand, meaning it is a subset which is not equal
f2c04ccdad 2021-03-03 trnsz@pobox.c: to the right operand.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT All of the above exercises have been predicates.  In contrast,
f2c04ccdad 2021-03-03 trnsz@pobox.c: the next exercise is to write a function called MAKESET, which returns
f2c04ccdad 2021-03-03 trnsz@pobox.c: a list which is a copy of its argument, omitting duplicates.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT How about:;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure makeset lis;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    if null lis then nil
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else if car lis member cdr lis then makeset cdr lis
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else car lis . makeset cdr lis;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT As you may have guessed, the next exercise is to implement an
f2c04ccdad 2021-03-03 trnsz@pobox.c: operator named INTERSECT, which returns the intersection of its set
f2c04ccdad 2021-03-03 trnsz@pobox.c: operands.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Here is my solution:;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: infix intersect;
f2c04ccdad 2021-03-03 trnsz@pobox.c: precedence intersect, subsetof;
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure set1 intersect set2;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    if null set1 then nil
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else if car set1 member set2
f2c04ccdad 2021-03-03 trnsz@pobox.c:       then car set1 . cdr set1 intersect set2
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else cdr set1 intersect set2;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Symbolic-mode REDUCE has a built-in function named SETDIFF,
f2c04ccdad 2021-03-03 trnsz@pobox.c: which returns the set of elements which are in its first argument but
f2c04ccdad 2021-03-03 trnsz@pobox.c: not the second.  See if you can write an infix definition of a similar
f2c04ccdad 2021-03-03 trnsz@pobox.c: function named DIFFSET.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Presenting --:;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: infix diffset;
f2c04ccdad 2021-03-03 trnsz@pobox.c: precedence diffset, intersect;
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure left diffset right;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    if null left then nil
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else if car left member right then cdr left diffset right
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else car left . (cdr left diffset right);
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: '(seagull wren condor) diffset '(wren lark);
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT The symmetric difference of two sets is the set of all
f2c04ccdad 2021-03-03 trnsz@pobox.c: elements which are in only one of the two sets.  Implement a
f2c04ccdad 2021-03-03 trnsz@pobox.c: corresponding infix function named SYMDIFF.  Look for the easy way!
f2c04ccdad 2021-03-03 trnsz@pobox.c: There is almost always one for examinations and instructional
f2c04ccdad 2021-03-03 trnsz@pobox.c: exercises.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Presenting --:;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: infix symdiff;
f2c04ccdad 2021-03-03 trnsz@pobox.c: precedence symdiff, intersect;
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure set1 symdiff set2;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    append(set1 diffset set2, set2 diffset set1);
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: '(seagull wren condor) symdiff '(wren lark);
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT We can use APPEND because the two set differences are
f2c04ccdad 2021-03-03 trnsz@pobox.c: disjoint.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: The above set of exercises (exercises of set?) have all returned set
f2c04ccdad 2021-03-03 trnsz@pobox.c: results.  The cardinality, size, or length of a set is the number of
f2c04ccdad 2021-03-03 trnsz@pobox.c: elements in the set.  More generally, it is useful to have a function
f2c04ccdad 2021-03-03 trnsz@pobox.c: which returns the length of its list argument, and such a function is
f2c04ccdad 2021-03-03 trnsz@pobox.c: built-into RLISP.  See if you can write a similar function named
f2c04ccdad 2021-03-03 trnsz@pobox.c: SIZEE.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Presenting --:;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure sizee lis;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    if null lis then 0
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else 1 + sizee cdr lis;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: sizee '(how marvelously concise);
f2c04ccdad 2021-03-03 trnsz@pobox.c: sizee '();
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Literal atoms, meaning atoms which are not numbers, are stored
f2c04ccdad 2021-03-03 trnsz@pobox.c: uniquely in LISP and in RLISP, so comparison for equality of literal
f2c04ccdad 2021-03-03 trnsz@pobox.c: atoms can be implemented by comparing their addresses, which is
f2c04ccdad 2021-03-03 trnsz@pobox.c: significantly more efficient than a character-by-character comparison
f2c04ccdad 2021-03-03 trnsz@pobox.c: of their names.  The comparison operator "EQ" compares addresses, so
f2c04ccdad 2021-03-03 trnsz@pobox.c: it is the most efficient choice when comparing only literal atoms.
f2c04ccdad 2021-03-03 trnsz@pobox.c: The assignments
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c:    N2 := N1 := 987654321,
f2c04ccdad 2021-03-03 trnsz@pobox.c:    S2 := S1 := '(FROG (SALAMANDER.NEWT)),
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: make N2 have the same address as N1 and make S2 have the same address
f2c04ccdad 2021-03-03 trnsz@pobox.c: as S1, but if N1 and N2 were constructed independently, they would not
f2c04ccdad 2021-03-03 trnsz@pobox.c: generally have the same address, and similarly for S1 vs. S2.  The
f2c04ccdad 2021-03-03 trnsz@pobox.c: comparison operator "=", which is an alias for "EQUAL", does a general
f2c04ccdad 2021-03-03 trnsz@pobox.c: test for identical s-expressions, which need not be merely two
f2c04ccdad 2021-03-03 trnsz@pobox.c: pointers to the same address.  Since "=" is built-in, compiled, and
f2c04ccdad 2021-03-03 trnsz@pobox.c: crucial, I will define my own differently-named version denoted "..="
f2c04ccdad 2021-03-03 trnsz@pobox.c: as follows:;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: newtok '((!. !. !=) myequal);
f2c04ccdad 2021-03-03 trnsz@pobox.c: infix eqatom, myequal;
f2c04ccdad 2021-03-03 trnsz@pobox.c: precedence myequal, equal;
f2c04ccdad 2021-03-03 trnsz@pobox.c: precedence eqatom, eq;
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure s1 myequal s2;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    if atom s1 then
f2c04ccdad 2021-03-03 trnsz@pobox.c:       if atom s2 then s1 eqatom s2
f2c04ccdad 2021-03-03 trnsz@pobox.c:       else nil
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else if atom s2 then nil
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else car s1 myequal car s2 and cdr s1 myequal cdr s2;
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure a1 eqatom a2;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    if numberp a1 then
f2c04ccdad 2021-03-03 trnsz@pobox.c:       if numberp a2 then zerop(a1-a2)
f2c04ccdad 2021-03-03 trnsz@pobox.c:       else nil
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else if numberp a2 then nil
f2c04ccdad 2021-03-03 trnsz@pobox.c:    else a1 eq a2;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Here I introduced a help function named EQATOM, because I was
f2c04ccdad 2021-03-03 trnsz@pobox.c: beginning to become confused by detail when I got to the line which
f2c04ccdad 2021-03-03 trnsz@pobox.c: uses EQATOM.  Consequently, I procrastinated on attending to some fine
f2c04ccdad 2021-03-03 trnsz@pobox.c: detail by relegating it to a help function which I was confident could
f2c04ccdad 2021-03-03 trnsz@pobox.c: be successfully written later.  After completing MYEQUAL, I was
f2c04ccdad 2021-03-03 trnsz@pobox.c: confident that it would work provided EQATOM worked, so I could then
f2c04ccdad 2021-03-03 trnsz@pobox.c: turn my attention entirely to EQATOM, freed of further distraction by
f2c04ccdad 2021-03-03 trnsz@pobox.c: concern about the more ambitious overall goal.  It turns out that
f2c04ccdad 2021-03-03 trnsz@pobox.c: EQATOM is a rather handy utility function anyway, and practice helps
f2c04ccdad 2021-03-03 trnsz@pobox.c: develop good judgement about where best to so subdivide tasks.  This
f2c04ccdad 2021-03-03 trnsz@pobox.c: psychological divide-and-conquer programming technique is important in
f2c04ccdad 2021-03-03 trnsz@pobox.c: most other programming languages too.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: "..=" is different from our previous examples in that "..=" recurses
f2c04ccdad 2021-03-03 trnsz@pobox.c: down the CAR as well as down the CDR of an s-expression.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT If a list has n elements, our function named MEMBERP or the
f2c04ccdad 2021-03-03 trnsz@pobox.c: equivalent built-in function named MEMBER requires on the order of n
f2c04ccdad 2021-03-03 trnsz@pobox.c: "=" tests.  Consequently, the above definitions of SETP and MAKESET,
f2c04ccdad 2021-03-03 trnsz@pobox.c: which require on the order of n membership tests, will require on the
f2c04ccdad 2021-03-03 trnsz@pobox.c: order of n^2 "=" tests.  Similarly, if the two operands have m and n
f2c04ccdad 2021-03-03 trnsz@pobox.c: elements, the above definitions of SUBSETOF, EQSETP, INTERSECT,
f2c04ccdad 2021-03-03 trnsz@pobox.c: DIFFSET, and SYMDIFF require on the order of m*n "=" tests.  We could
f2c04ccdad 2021-03-03 trnsz@pobox.c: decrease the growth rates to order of n and order of m+n respectively
f2c04ccdad 2021-03-03 trnsz@pobox.c: by sorting the elements before giving lists to these functions.  The
f2c04ccdad 2021-03-03 trnsz@pobox.c: best algorithms sort a list of n elements in the order of n*log(n)
f2c04ccdad 2021-03-03 trnsz@pobox.c: element comparisons, and this need be done only once per input set.
f2c04ccdad 2021-03-03 trnsz@pobox.c: To do so we need a function which returns T if the first argument is
f2c04ccdad 2021-03-03 trnsz@pobox.c: "=" to the second argument or should be placed to the left of the
f2c04ccdad 2021-03-03 trnsz@pobox.c: second argument.  Such a function, named ORDP, is already built-into
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic-mode REDUCE, based on the following rules:
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c:    1.  Any number orders left of NIL.
f2c04ccdad 2021-03-03 trnsz@pobox.c:    2.  Larger numbers order left of smaller numbers.
f2c04ccdad 2021-03-03 trnsz@pobox.c:    4.  Literal atoms order left of numbers.
f2c04ccdad 2021-03-03 trnsz@pobox.c:    3.  Literal atoms order among themselves by address, as determined
f2c04ccdad 2021-03-03 trnsz@pobox.c:        by the built-in RLISP function named ORDERP.
f2c04ccdad 2021-03-03 trnsz@pobox.c:    5.  Non-atoms order left of atoms.
f2c04ccdad 2021-03-03 trnsz@pobox.c:    6.  Non-atoms order among themselves according to ORDP of their
f2c04ccdad 2021-03-03 trnsz@pobox.c:        CARs, with ties broken according to ORDP of their CDRs.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: Try writing an analogous function named MYORD, and, if you are in
f2c04ccdad 2021-03-03 trnsz@pobox.c: REDUCE rather than RLISP, test its behavior in comparison to ORDP.;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: pause;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Whether or not we use sorted sets, we can reduce the
f2c04ccdad 2021-03-03 trnsz@pobox.c: proportionality constant associated with the growth rate by replacing
f2c04ccdad 2021-03-03 trnsz@pobox.c: "=" by "EQ" if the set elements are restricted to literal atoms.
f2c04ccdad 2021-03-03 trnsz@pobox.c: However, with such elements we can use property-lists to achieve the
f2c04ccdad 2021-03-03 trnsz@pobox.c: growth rates of the sorted algorithms without any need to sort the
f2c04ccdad 2021-03-03 trnsz@pobox.c: sets.  On any LISP system that is efficient enough to support REDUCE
f2c04ccdad 2021-03-03 trnsz@pobox.c: with acceptable performance, the time required to access a property of
f2c04ccdad 2021-03-03 trnsz@pobox.c: an atom is modest and very insensitive to the number of distinct atoms
f2c04ccdad 2021-03-03 trnsz@pobox.c: in the program and data.  Consequently, the basic technique for any of
f2c04ccdad 2021-03-03 trnsz@pobox.c: our set operations is:
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c:    1.  Scan the list argument or one of the two list arguments,
f2c04ccdad 2021-03-03 trnsz@pobox.c:        flagging each element as "SEEN".
f2c04ccdad 2021-03-03 trnsz@pobox.c:    2.  During the first scan, or during a second scan of the same
f2c04ccdad 2021-03-03 trnsz@pobox.c:        list, or during a scan of the second list, check each element
f2c04ccdad 2021-03-03 trnsz@pobox.c:        to see whether or not it has already been flagged, and act
f2c04ccdad 2021-03-03 trnsz@pobox.c:        accordingly.
f2c04ccdad 2021-03-03 trnsz@pobox.c:    3.  Make a final pass through all elements which were flagged to
f2c04ccdad 2021-03-03 trnsz@pobox.c:        remove the flag "SEEN".  (Otherwise, we may invalidate later set
f2c04ccdad 2021-03-03 trnsz@pobox.c:        operations which utilize any of the same atoms.)
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: We could use indicators rather than flags, but the latter are slightly
f2c04ccdad 2021-03-03 trnsz@pobox.c: more efficient when an indicator would have only one value (such as
f2c04ccdad 2021-03-03 trnsz@pobox.c: having "SEEN" as the value of an indicator named "SEENORNOT").
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: As an example, here is INTERSECT defined using this technique;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: symbolic procedure intersect(s1, s2);
f2c04ccdad 2021-03-03 trnsz@pobox.c:    begin scalar ans, set2;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    flag(s1, 'seen);
f2c04ccdad 2021-03-03 trnsz@pobox.c:    set2 := s2;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    while set2 do <<
f2c04ccdad 2021-03-03 trnsz@pobox.c:       if flagp(car set2, 'seen) then ans := car set2 . ans;
f2c04ccdad 2021-03-03 trnsz@pobox.c:       set2 := cdr set2 >>;
f2c04ccdad 2021-03-03 trnsz@pobox.c:    remflag(s1, 'seen);
f2c04ccdad 2021-03-03 trnsz@pobox.c:    return ans
f2c04ccdad 2021-03-03 trnsz@pobox.c:    end;
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: COMMENT Perhaps you noticed that, having used a BEGIN-block, group,
f2c04ccdad 2021-03-03 trnsz@pobox.c: loop, and assignments, I have not practiced what I preached about
f2c04ccdad 2021-03-03 trnsz@pobox.c: using only function composition, conditional expressions, and
f2c04ccdad 2021-03-03 trnsz@pobox.c: recursion during this lesson.  Well, now that you have had some
f2c04ccdad 2021-03-03 trnsz@pobox.c: exposure to both extremes, I think you should always fairly consider
f2c04ccdad 2021-03-03 trnsz@pobox.c: both together with appropriate compromises, in each case choosing
f2c04ccdad 2021-03-03 trnsz@pobox.c: whatever is most clear, concise, and natural.  For set operations
f2c04ccdad 2021-03-03 trnsz@pobox.c: based on the property-list approach, I find the style exemplified
f2c04ccdad 2021-03-03 trnsz@pobox.c: immediately above most natural.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: As your last exercise for this lesson, develop a file containing a
f2c04ccdad 2021-03-03 trnsz@pobox.c: package for set operations based upon either property-lists or
f2c04ccdad 2021-03-03 trnsz@pobox.c: sorting.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: This is the end of lesson 6.  When you are ready to run the final
f2c04ccdad 2021-03-03 trnsz@pobox.c: lesson 7, load a fresh copy of REDUCE.
f2c04ccdad 2021-03-03 trnsz@pobox.c: 
f2c04ccdad 2021-03-03 trnsz@pobox.c: ;end;

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