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 an introductory text about LISP, such as "A Concise Introduction to LISP" by David L. Matuszek, which is freely available at https://www.cis.upenn.edu/~matuszek/LispText/lisp.html. Then familiarize yourself with the Standard Lisp Report, which is freely available via http://reduce-algebra.sourceforge.net/documentation.php. 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 putting enough levels of parentheses in your data examples. Having learnt from reading the Standard Lisp Report 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 (operand1 operator operand2 operator ... operator operandN) are interpreted left-to-right as ((...(operand1 operator operand2) operator ...) 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. (But note that MEMBER returns the sublist beginning with the first argument rather than T.); 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 have higher precedence 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;