;;; -*- Mode:gate; Fonts:(HL12 HL12I HL12B CPTFONTB HL12BI HL12B HL12I ) -*- =Node: Tables =Text: 3TABLES* Zetalisp includes functions which simplify the maintenance of tabular data structures of several varieties. The simplest is a plain list of items There are functions to add (2cons*), remove (2delete*, 2delq*, 2del*, 2del-if*, 2del-if-not*, 2remove*, 2remq*, 2rem*, 2rem-if*, 2rem-if-not*), and search for (2member*, 2memq*, 2mem*) items in a list. 1Association lists* are very commonly used. An association list is a list of conses. The car of each cons is a ``key'' and the cdr is a ``datum'', or a list of associated data. The functions 2assoc*, 2assq*, 2ass*, 2memass*, and 2rassoc* may be used to retrieve the data, given the key. For example, 3((tweety . bird) (sylvester . cat))* is an association list with two elements. Given a symbol representing the name of an animal, it can retrieve what kind of animal this is. 1Structured records* can be stored as association lists or as stereotyped cons-structures where each element of the structure has a certain car-cdr path associated with it. However, these are better implemented using structure macros (see 4(DEFSTRUCT-0)Defstruct*) or as flavors (4(FLAVOR-0)Objects, Message Passing, and Flavors*). Simple list-structure is very convenient, but may not be efficient enough for large data bases because it takes a long time to search a long list. Zetalisp includes hash table facilities for more efficient but more complex tables (see 4(MANLISTSTR-3)Introduction to Hash Tables*), and a hashing function (2sxhash*) to aid users in constructing their own facilities. =Node: Lists as Tables =Text: 3LISTS AS TABLES memq* 1item* 1list* Returns 2nil* if 1item* is not one of the elements of 1list*. Otherwise, it returns the sublist of 1list* beginning with the first occurrence of 1item*; that is, it returns the first cons of the list whose car is 1item*. The comparison is made by 2eq*. Because 2memq* returns 2nil* if it doesn't find anything, and something non-2nil* if it finds something, it is often used as a predicate. Examples: 3(memq 'a '(1 2 3 4)) => nil* 3(memq 'a '(g (x a y) c a d e a f)) => (a d e a f)* Note that the value returned by 2memq* is 2eq* to the portion of the list beginning with 2a*. Thus 2rplaca* on the result of 2memq* may be used, if you first check to make sure 2memq* did not return 2nil*. Example: 3(let ((sublist (memq x z))) ;2Search for x in the list z.** 3 (if (not (null sublist)) ;2If it is found,** 3 (rplaca sublist y))) ;2Replace it with y.** memq could have been defined by: 3(defun memq (item list)* 3 (cond ((null list) nil)* 3 ((eq item (car list)) list)* 3 (t (memq item (cdr list)))))* 2memq* is hand-coded in microcode and therefore especially fast. It is equivalent to 2cli:member* with 2eq* specified as the 1test* argument. 3member* 1item* 1list* 2member* is like 2memq*, except 2equal* is used for the comparison, instead of 2eq*. Note that the 2member* function of Common Lisp, which is 2cli:member*, is similar but thoroughly incompatible (see below). 2member* could have been defined by: 3(defun member (item list)* 3 (cond ((null list) nil)* 3 ((equal item (car list)) list)* 3 (t (member item (cdr list))))) cli:member* 1item* 1list* &key 1test* 1test-not* 1key* The Common Lisp 2member* function. It is like 2memq* or 2member* except that there is more generality in how elements of 1list* are matched against 1item*--and the default is incompatible. 1test*, 1test-not* and 1key* are used in matching the elements, just as described under 2cli:subst* (see 4(MANLISTSTR-1)Cons Cells as Trees*). If neither 1test* nor 1test-not* is specified, the default is to compare with 2eql*, whereas 2member* compares with 2equal*. Usually 1test* is a commutative predicate such as 2eq*, 2equal*, 2=*, 2char-equal* or 2string-equal*. It can also be a non-commutative predicate. The predicate is called with 1item* as its first argument and the element of 1list* as its second argument. Example: 3(cli:member 4 '(1.5 2.5 2 3.5 4.5 8) :test '<) => (4.5 8) member-if* 1predicate* 1list* &key 1key* Searches the elements of 1list* for one which satisfies 1predicate*. If one is found, the value is the tail of 1list* whose car is that element. Otherwise the value is 2nil*. If 1key* is non-2nil*, then 1predicate* is applied to 2(funcall 1key* 1element*)* rather than to the element itself. 3member-if-not* 1predicate* 1list* &key 1key* Searches for an element which does not satisfy 1predicate*. Otherwise like 2member-if*. 3mem* 1predicate* 1item* 1list* Is equivalent to 3(cli:member 1item* 1list* :test 1predicate*)* The function 2mem* antedates 2cli:member*. 3find-position-in-list* 1item* 1list* Searches 1list* for an element which is 2eq* to 1item*, like 2memq.* However, it returns the numeric index in the list at which it found the first occurence of 1item*, or 2nil* if it did not find it at all. This function is sort of the complement of 2nth* (see 4(MANLISTSTR-1)Lists*); like 2nth*, it is zero-based. Examples: 3(find-position-in-list 'a '(a b c)) => 0* 3(find-position-in-list 'c '(a b c)) => 2* 3(find-position-in-list 'e '(a b c)) => nil* See also the generic sequence function 2position* (4(GENERIC-1)Searching for Elements*). 3find-position-in-list-equal* 1item* 1list* Is like 2find-position-in-list*, except that the comparison is done with 2equal* instead of 2eq*. 3tailp* 1sublist* 1list* Returns 2t* if 1sublist* is a sublist of 1list* (i.e. one of the conses that makes up 1list*). Otherwise returns 2nil*. Another way to look at this is that 2tailp* returns 2t* if 2(nthcdr 1n* 1list*)* is 1sublist*, for some value of 1n*. 2tailp* could have been defined by: 3(defun tailp (sublist list)* 3 (do list list (cdr list) (null list)* 3 (if (eq sublist list)* 3 (return t)))) delq* 1item* 1list* &optional 1n* 2(delq 1item list*)* returns the 1list* with all occurrences of 1item* removed. 2eq* is used for the comparison. The argument 1list* is actually modified (2rplacd*'ed) when instances of 1item* are spliced out. 2delq* should be used for value, not for effect. That is, use 3(setq a (delq 'b a))* rather than 3(delq 'b a)* These two are 1not* equivalent when the first element of the value of 2a* is 2b*. 2(delq 1item list n*)* is like 2(delq 1item list*)* except only the first 1n* instances of 1item* are deleted. 1n* is allowed to be zero. If 1n* is greater than or equal to the number of occurrences of 1item* in the list, all occurrences of 1item* in the list are deleted. Example: 3(delq 'a '(b a c (a b) d a e)) => (b c (a b) d e)* 2delq* could have been defined by: 3(defun delq (item list &optional (n -1))* 3 (cond ((or (atom list) (zerop n)) list)* 3 ((eq item (car list))* 3 (delq item (cdr list) (1- n)))* 3 (t (rplacd list (delq item (cdr list) n)))))* If the third argument (1n*) is not supplied, it defaults to 2-1* which is effectively infinity since it can be decremented any number of times without reaching zero. 3delete* 1item* 1list* &optional 1n* 2delete* is the same as 2delq* except that 2equal* is used for the comparison instead of 2eq*. Common Lisp programs have a different, incompatible function called 2delete*; see 4(GENERIC-1)Removing Elements from Sequences*. This function may be useful in non-Common-Lisp programs as well, where it can be referred to as 2cli:delete*. 3del* 1predicate* 1item* 1list* &optional 1n* 2del* is the same as 2delq* except that it takes an extra argument which should be a predicate of two arguments, which is used for the comparison instead of 2eq*. 2(del 'eq a b)* is the same as 2(delq a b)*. See also 2mem*, 4(MANLISTSTR-2)Lists as Tables*. Use of 2del* is equivalent to 3(cli:delete 1item* 1list* :test 1predicate*) remq* 1item* 1list* &optional 1n* 2remq* is similar to 2delq*, except that the list is not altered; rather, a new list is returned. Examples: 3(setq x '(a b c d e f))* 3(remq 'b x) => (a c d e f)* 3x => (a b c d e f)* 3(remq 'b '(a b c b a b) 2) => (a c a b) remove* 1item* 1list* &optional 1n* 2remove* is the same as 2remq* except that 2equal* is used for the comparison instead of 2eq*. Common Lisp programs have a different, incompatible function called 2remove*; see 4(GENERIC-1)Removing Elements from Sequences*. This function may be useful in non-Common-Lisp programs as well, where it can be referred to as 2cli:remove*. 3rem* 1predicate* 1item* 1list* &optional 1n* 2rem* is the same as 2remq* except that it takes an extra argument which should be a predicate of two arguments, which is used for the comparison instead of 2eq*. 2(rem 'eq a b)* is the same as 2(remq a b)*. See also 2mem*, 4(MANLISTSTR-2)Lists as Tables*. The function 2rem* in Common Lisp programs is actually 2cli:rem*, a remainder function. See 4(NUMBERS-1)Arithmetic*. 3subset* 1predicate* 1list* 3rem-if-not* 1predicate* 1list* 1predicate* should be a function of one argument. A new list is made by applying 1predicate* to all of the elements of 1list* and removing the ones for which the predicate returns 2nil*. One of this function's names (2rem-if-not*) means ``remove if this condition is not true''; i.e. it keeps the elements for which 1predicate* is true. The other name (2subset*) refers to the function's action if 1list* is considered to represent a mathematical set. Example: 3(subset #'minusp '(1 2 -4 2 -3)) => (-4 -3) subset-not* 1predicate* 1list* 3rem-if* 1predicate* 1list* 1predicate* should be a function of one argument. A new list is made by applying 1predicate* to all of the elements of 1list* and removing the ones for which the predicate returns non-2nil*. One of this function's names (2rem-if*) means ``remove if this condition is true''. The other name (2subset-not*) refers to the function's action if 1list* is considered to represent a mathematical set. 3del-if* 1predicate* 1list* 2del-if* is just like 2rem-if* except that it modifies 1list* rather than creating a new list. 3del-if-not* 1predicate* 1list* 2del-if-not* is just like 2rem-if-not* except that it modifies 1list* rather than creating a new list. See also the generic sequence functions 2delete-if*, 2delete-if-not*, 2remove-if* and 2remove-if-not* (4(GENERIC-1)Removing Elements from Sequences*). 3every* 1list* 1predicate* &optional 1step-function* Returns 2t* if 1predicate* returns non-2nil* when applied to every element of 1list*, or 2nil* if 1predicate* returns 2nil* for some element. If 1step-function* is present, it replaces 2cdr* as the function used to get to the next element of the list; 2cddr* is a typical function to use here. In Common Lisp programs, the name 2every* refers to a different, incompatible function which serves a similar purpose. It is documented in the manual under the name 2cli:every*. See 4(GENERIC-1)Mapping On Sequences*. 3some* 1list* 1predicate* &optional 1step-function* Returns a tail of 1list* such that the car of the tail is the first element that the 1predicate* returns non-2nil* when applied to, or 2nil* if 1predicate* returns 2nil* for every element. If 1step-function* is present, it replaces 2cdr* as the function used to get to the next element of the list; 2cddr* is a typical function to use here. In Common Lisp programs, the name 2some* refers to a different, incompatible function which serves a similar purpose. It is documented in the manual under the name 2cli:some*. See 4(GENERIC-1)Mapping On Sequences*. =Node: Lists as Sets =Text: 3LISTS AS SETS* A list can be used to represent an unordered set of objects, simply by using it in a way that ignores the order of the elements. Membership in the set can be tested with 2memq* or 2member*, and some other functions in the previous section also make sense on lists representing sets. This section describes several functions specifically intended for lists that represent sets. It is often desirable to avoid adding duplicate elements in the list. The set functions attempt to introduce no duplications, but do not attempt to eliminate duplications present in their arguments. If you need to make absolutely certain that a list contains no duplicates, use 2remove-duplicates* or 2delete-duplicates* (see 4(GENERIC-1)Removing Elements from Sequences*). 3subsetp* 1list1* 1list2* &key 1test* 1test-not* 1key* 2t* if every element of 1list1* matches some element of 1list2*. The keyword arguments control how matching is done. Either 1test* or 1test-not* should be a function of two arguments. Normally it is called with an element of 1list1* as the first argument and an element of 1list2* as the second argument. If 1test* is specified, a match happens when 1test* returns non-2nil*; otherwise, if 1test-not* is specified, a match happens when it returns 2nil*. If neither is specified, then 2eql* is used for 1test*. If 1key* is non-2nil*, it should be a function of one argument. 1key* is applied to each list element to get a key to be passed to 1test* or 1test-not* instead of the element. 3adjoin* 1item* 1list* &key 1test* 1test-not* 1key* Returns a list like 1list* but with 1item* as an additional element if no existing element matches item. It is done like this: 3(if (cli:member (if 1key* (funcall 1key* 1item*) 1item*)* 3 1list* 1other-args*...)* 3 1list** 3 (cons 1item* 1list*))* The keyword arguments work as in 2subsetp*. 3pushnew* 1item* 1list-place* &key 1test* 1test-not* 1key* 1Macro* Pushes 1item* onto 1list-place* unless 1item* matches an existing element of the value stored in that place. Equivalent to 3(setf 1list-place** 3 (adjoin 1item* 1list-place* 1keyword-args*...))* except for order of evaluation. Compare with 2push*, 4(MANLISTSTR-1)Conses*. 3union* 1list* &rest 1more-lists* Returns a list representing the set which is the union of the sets represented by the arguments. Anything which is an element of at least one of the arguments is also an element of the result. Each element of each list is compared, using 2eq*, with all elements of the other lists, to make sure that no duplications are introduced into the result. As long as no individual argument list contains duplications, the result does not either. It is best to use 2union* with only two arguments so that your code will not be sensitive to the difference between the traditional version of 2union* and the Common Lisp version 2cli:union*, below. 3intersection* 1list* &rest 1more-lists* If lists are regarded as sets of their elements, 2intersection* returns a list which is the intersection of the lists which are supplied as arguments. If 1list* contains no duplicate elements, neither does the value returned by 2intersection*. Elements are compared using 2eq*. It is best to use 2intersection* with only two arguments so that your code will not be sensitive to the difference between the traditional version of 2intersection* and the Common Lisp version 2cli:intersection*, below. 3nunion* 1list* &rest 1more-lists* If lists are regarded as sets of their elements, 2nunion* modifies 1list* to become the union of the lists which are supplied as arguments. This is done by adding on, at the end, any elements of the other lists that were not already in 1list*. If none of the arguments contains any duplicate elements, neither does the value returned by 2nunion*. Elements are compared using 2eq*. It is not safe to assume that 1list* has been modified properly in place, as this will not be so if 1list* is 2nil*. Rather, you must store the value returned by 2nunion* in place of 1list*. It is best to use 2nunion* with only two arguments so that your code will not be sensitive to the difference between the traditional version of 2nunion* and the Common Lisp version 2cli:nunion*, below. 3nintersection* 1list* &rest 1more-lists* Like 2intersection* but produces the value by deleting elements from 1list* until the desired result is reached, and then returning 1list* as modified. It is not safe to assume that 1list* has been modified properly in place, as this will not be so if the first element was deleted. Rather, you must store the value returned by 2nintersection* in place of 1list*. It is best to use 2nintersection* with only two arguments so that your code will not be sensitive to the difference between the traditional version of 2nintersection* and the Common Lisp version 2cli:nintersection*, below. 3cli:union* 1list1* 1list2* &key 1test* 1test-not* 1key* 3cli:intersection* 1list1* 1list2* &key 1test* 1test-not* 1key* 3cli:nunion* 1list1* 1list2* &key 1test* 1test-not* 1key* 3cli:nintersection* 1list1* 1list2* &key 1test* 1test-not* 1key* The Common Lisp versions of the above functions, which accept only two sets to operate on, but permit additional arguments to control how elements are matched. These keyword arguments work the same as in 2subsetp*. 3set-difference* 1list1* 1list2* &key 1test* 1test-not* 1key* Returns a list which has all the elements of 1list1* which do not match any element of 1list2*. The keyword arguments control comparison of elements just as in 2subsetp*. The result contains no duplicate elements as long as 1list1* contains none. 3set-exclusive-or* 1list1* 1list2* &key 1test* 1test-not* 1key* Returns a list which has all the elements of 1list1* which do not match any element of 1list2*, and also all the elements of 1list2* which do not match any element of 1list1*. The keyword arguments control comparison of elements just as in 2subsetp*. The result contains no duplicate elements as long as neither 1list1* nor 1list2* contains any. 3nset-difference* 1list1* 1list2* &key 1test* 1test-not* 1key* Like 2set-difference* but destructively modifies 1list1* to produce the value. See the caveat in 2nintersection*, above. 3nset-exclusive-or* 1list1* 1list2* &key 1test* 1test-not* 1key* Like 2set-exclusive-or* but may destructively modify both 1list1* and 1list2* to produce the value. See the caveat in 2nintersection*, above. =Node: Association Lists =Text: 3ASSOCIATION LISTS* In all the alist-searching functions, alist elements which are 2nil* are ignored; they do not count as equivalent to 2(nil . nil)*. Elements which are not lists cause errors. 3pairlis* 1cars* 1cdrs* &optional 1tail* 2pairlis* takes two lists and makes an association list which associates elements of the first list with corresponding elements of the second list. Example: 3(pairlis '(beef clams kitty) '(roast fried yu-shiang))* 3 => ((beef . roast) (clams . fried) (kitty . yu-shiang))* If 1tail* is non-2nil*, it should be another alist. The new alist continues with 1tail* following the newly constructed mappings. 2pairlis* is defined as: 3(defun pairlis (cars cdrs &optional tail)* 3 (nconc (mapcar 'cons cars cdrs) tail)) acons* 1acar* 1acdr* 1tail* Returns 2(cons (cons 1acar* 1acdr*) 1tail*)*. This adds one additional mapping from 1acar* to 1acdr* onto the alist 1tail*. 3assq* 1item* 1alist* 2(assq 1item alist*)* looks up 1item* in the association list (list of conses) 1alist*. The value is the first cons whose car is 2eq* to 1x*, or 2nil* if there is none such. Examples: 3(assq 'r '((a . b) (c . d) (r . x) (s . y) (r . z)))* 3 => (r . x)* 3(assq 'fooo '((foo . bar) (zoo . goo))) => nil* 3(assq 'b '((a b c) (b c d) (x y z))) => (b c d)* It is okay to 2rplacd* the result of 2assq* as long as it is not 2nil*, if your intention is to ``update'' the ``table'' that was 2assq*'s second argument. Example: 3(setq values '((x . 100) (y . 200) (z . 50)))* 3(assq 'y values) => (y . 200)* 3(rplacd (assq 'y values) 201)* 3(assq 'y values) => (y . 201)* A common trick is to say 2(cdr (assq x y))*. Since the cdr of 2nil* is guaranteed to be 2nil*, this yields 2nil* if no pair is found (or if a pair is found whose cdr is 2nil*.) assq could have been defined by: 3(defun assq (item list)* 3 (cond ((null list) nil)* 3 ((eq item (caar list)) (car list))* 3 ((assq item (cdr list))) )) assoc* 1item* 1alist* 2assoc* is like 2assq* except that the comparison uses 2equal* instead of 2eq*. Example: 3(assoc '(a b) '((x . y) ((a b) . 7) ((c . d) .e)))* 3 => ((a b) . 7)* 2assoc* could have been defined by: 3(defun assoc (item list)* 3 (cond ((null list) nil)* 3 ((equal item (caar list)) (car list))* 3 ((assoc item (cdr list))) )) cli:assoc* 1item* 1alist* &key 1test* 1test-not* The Common Lisp version of 2assoc*, this function returns the first element of 1alist* which is a cons whose car matches 1item*, or 2nil* if there is no such element. 1test* and 1test-not* are used in comparing elements, as in 2cli:subst* (4(MANLISTSTR-1)Cons Cells as Trees*), but note that there is no 1key* argument in 2cli:assoc*. 2cli:assoc* is incompatible with the traditional function 2assoc* in that, like most Common Lisp functions, it uses 2eql* by default rather than 2equal* for the comparison. 3ass* 1predicate* 1item* 1alist* 2ass* is the same as 2assq* except that it takes an extra argument which should be a predicate of two arguments, which is used for the comparison instead of 2eq*. 2(ass 'eq a b)* is the same as 2(assq a b)*. See also 2mem*, 4(MANLISTSTR-2)Lists as Tables*. This function is part of The 2mem*, 2rem*, 2del* series, whose names were chosed partly because they created a situation in which this function simply had to be called 2ass*. It's too bad that 2cli:assoc* is so general and subsumes 2ass*, which is equivalent to 3(cli:assoc 1item* 1alist* :test 1predicate*) assoc-if* 1predicate* 1alist* Returns the first element of 1alist* which is a cons whose car satisfies 1predicate*, or 2nil* if there is no such element. 3assoc-if-not* 1predicate* 1alist* Returns the first element of 1alist* which is a cons whose car does not satisfy 1predicate*, or 2nil* if there is no such element. 3memass* 1predicate* 1item* 1alist* 2memass* searches 1alist* just like 2ass*, but returns the portion of the list beginning with the pair containing 1item*, rather than the pair itself. 2(car (memass 1x y z*)) = (ass 1x y z*)*. See also 2mem*, 4(MANLISTSTR-2)Lists as Tables*. 3rassq* 1item* 1alist* 3rassoc* 1item* 1alist* 3rass* 1predicate* 1item* 1alist* 3cli:rassoc* 1item* 1alist* &key 1test* 1test-not* 3rassoc-if* 1predicate* 1alist* 3rassoc-if-not* 1predicate* 1alist* The reverse-association functions are like 2assq*, 2assoc*, etc. but match or test the cdrs of the alist elements instead of the cars. For example, 2rassq* could have been defined by: 3(defun rassq (item in-list) * 3 (do l in-list (cdr l) (null l) * 3 (and (eq item (cdar l)) * 3 (return (car l))))) sassq* 1item* 1alist* 1fcn* 2(sassq 1item alist fcn*)* is like 2(assq 1item alist*)* except that if 1item* is not found in 1alist*, instead of returning 2nil*, 2sassq* calls the function 1fcn* with no arguments. 2sassq* could have been defined by: 3(defun sassq (item alist fcn)* 3 (or (assq item alist)* 3 (apply fcn nil)))* 2sassq* and 2sassoc* (see below) are of limited use. These are primarily leftovers from Lisp 1.5. 3sassoc* 1item* 1alist* 1fcn* 2(sassoc 1item alist fcn*)* is like 2(assoc 1item alist*)* except that if 1item* is not found in 1alist*, instead of returning 2nil*, 2sassoc* calls the function 1fcn* with no arguments. 2sassoc* could have been defined by: 3(defun sassoc (item alist fcn)* 3 (or (assoc item alist)* 3 (apply fcn nil)))* =Node: Stack Lists =Text: 3STACK LISTS* When you are creating a list that will not be needed any more once the function that creates it is finished, it is possible to create the list on the stack instead of by consing it. This avoids any permanent storage allocation, as the space is reclaimed as part of exiting the function. By the same token, it is a little risky; if any pointers to the list remain after the function exits, they will become meaningless. These lists are called 1temporary lists* or 1stack lists*. You can create them explicitly using the special forms 2with-stack-list* and 2with-stack-list**. 2&rest* arguments also sometimes create stack lists. If a stack list, or a list which might be a stack list, is to be returned or made part of permanent list-structure, it must first be copied (see 2copylist*, 4(MANLISTSTR-1)Lists*). The system cannot detect the error of omitting to copy a stack list; you will simply find that you have a value that seems to change behind your back. 3with-stack-list* 1(variable* 1element...)* 1body...* 1Special Form* 3with-stack-list** 1(variable* 1element...* 1tail)* 1body...* These special forms create stack lists that live inside the stack frame of the function that they are used in. You should assume that the stack lists are only valid until the special form is exited. 3(with-stack-list (foo x y)* 3 (mumblify foo))* is equivalent to 3(let ((foo (list x y)))* 3 (mumblify foo))* except for the fact that 2foo*'s value in the first example is a stack list. The list created by 2with-stack-list** looks like the one created by 2list**. 1tail*'s value becomes the ultimate cdr rather than an element of the list. Here is a practical example. 2condition-resume* (see 4(DEBUGGING-3)Nonlocal Proceed Types*) might have been defined as follows: 3(defmacro condition-resume (handler &body body)* 3 `(with-stack-list* (eh:condition-resume-handlers* 3 ,handler eh:condition-resume-handlers)* 3 . ,body))* It is an error to do 2rplacd* on a stack list (except for the tail of one made using 2with-stack-list**). 2rplaca* works normally. 3sys:rplacd-wrong-representation-type* (3error*) 1Condition* This is signaled if you 2rplacd* a stack list (or a list overlayed with an array or other structure). =Node: Property Lists =Text: 3PROPERTY LISTS* From time immemorial, Lisp has had a kind of tabular data structure called a 1property list* (plist for short). A property list contains zero or more entries; each entry associates from a keyword symbol (called the 1property name*, or sometimes the 1indicator*) to a Lisp object (called the 1value* or, sometimes, the 1property*). There are no duplications among the property names; a property-list can have only one property at a time with a given name. This is very similar to an association list. The important difference is that a property list is an object with a unique identity; the operations for adding and removing property-list entries are side-effecting operations which alter the property-list rather than making a new one. An association list with no entries would be the empty list 2()*, i.e. the symbol 2nil*. There is only one empty list, so all empty association lists are the same object. Each empty property-list is a separate and distinct object. The implementation of a property list is a memory cell containing a list with an even number (possibly zero) of elements. Each pair of elements constitutes a 1property*; the first of the pair is the name and the second is the value. (It would have been possible to use an alist to hold the pairs; this format was chosen when Lisp was young.) The memory cell is there to give the property list a unique identity and to provide for side-effecting operations. The term `property list' is sometimes incorrectly used to refer to the list of entries inside the property list, rather than the property list itself. This is regrettable and confusing. How do we deal with ``memory cells'' in Lisp? That is, what kind of Lisp object is a property list? Rather than being a distinct primitive data type, a property list can exist in one of three forms: 1. Any cons can be used as a property list. The cdr of the cons holds the list of entries (property names and values). Using the cons as a property list does not use the car of the cons; you can use that for anything else. 2. The system associates a property list with every symbol (see 4(SYMBOLS-1)The Property List*). A symbol can be used where a property list is expected; the property-list primitives automatically find the symbol's property list and use it. 3. A flavor instance may have a property list. The property list functions operate on instances by sending messages to them, so the flavor can store the property list any way it likes. See 4(FLAVOR-5)Property List Operations*. 4. A named structure may have a property list. The property list functions automatically call 2named-structure-invoke* when a named structure is supplied as the property list. See 4(DEFSTRUCT-2)Named Structures*. 5. A property list can be a memory cell in the middle of some data structure, such as a list, an array, an instance, or a defstruct. An arbitrary memory cell of this kind is named by a locative (see 4(LOCATIVES-0)Locatives*). Such locatives are typically created with the 2locf* special form (see 4(EVAL-2)locf*). Property lists of the first kind are called 1disembodied* property lists because they are not associated with a symbol or other data structure. The way to create a disembodied property list is 2(ncons nil)*, or 2(ncons 1data*)* to store 1data* in the car of the property list. Suppose that, inside a program which deals with blocks, the property list of the symbol 2b1* contains this list (which would be the value of 2(symbol-plist 'b1)*): 3 (color blue on b6 associated-with (b2 b3 b4))* The list has six elements, so there are three properties. The first property's name is the symbol 2color*, and its value is the symbol 2blue*. One says that ``the value of 2b1*'s 2color* property is 2blue*'', or, informally, that ``2b1*'s 2color* property is 2blue*.'' The program is probably representing the information that the block represented by 2b1* is painted blue. Similarly, it is probably representing in the rest of the property list that block 2b1* is on top of block 2b6*, and that 2b1* is associated with blocks 2b2*, 2b3*, and 2b4*. 3get* 1plist* 1property-name* &optional 1default-value* 2get* looks up 1plist*'s 1property-name* property. If it finds such a property, it returns the value; otherwise, it returns 1default-value*. If 1plist* is a symbol, the symbol's associated property list is used. For example, if the property list of 2foo* is 2(baz 3)*, then 3(get 'foo 'baz) => 3* 3(get 'foo 'zoo) => nil* 3(get 'foo 'baz t) => 3* 3(get 'foo 'zoo t) => t getl* 1plist* 1property-name-list* 2getl* is like 2get*, except that the second argument is a list of property names. 2getl* searches down 1plist* for any of the names in 1property-name-list*, until it finds a property whose name is one of them. If 1plist* is a symbol, the symbol's associated property list is used. 2getl* returns the portion of the list inside 1plist* beginning with the first such property that it found. So the car of the returned list is a property name, and the 2cadr* is the property value. If none of the property names on 1property-name-list* are on the property list, 2getl* returns 2nil*. For example, if the property list of 2foo* were 3(bar (1 2 3) baz (3 2 1) color blue height six-two)* then 3(getl 'foo '(baz height))* 3 => (baz (3 2 1) color blue height six-two)* When more than one of the names in 1property-name-list* is present in 1plist*, which one 2getl* returns depends on the order of the properties. This is the only thing that depends on that order. The order maintained by 2putprop* and 2defprop* is not defined (their behavior with respect to order is not guaranteed and may be changed without notice). 3putprop* 1plist* 1x* 1property-name* This gives 1plist* an 1property-name*-property of 1x*. After this is done, 2(get 1plist** 1property-name2)** returns 1x*. If 1plist* is a symbol, the symbol's associated property list is used. Example: 3(putprop 'nixon t 'crook)* It is more modern to write 3(setf (get 1plist* 1property-name*) 1x*)* which avoids the counterintuitive order in which 2putprop* takes its arguments. 3defprop* 1symbol* 1x* 1property-name* 1Special Form* 2defprop* is a form of 2putprop* with unevaluated arguments, which is sometimes more convenient for typing. Normally only a symbol makes sense as the first argument. Example: 3(defprop foo bar next-to)* is the same as 3(putprop 'foo 'bar 'next-to) remprop* 1plist* 1property-name* This removes 1plist*'s 1property-name* property, by splicing it out of the property list. It returns that portion of the list inside 1plist* of which the former 1property-name*-property was the car. 2car* of what 2remprop* returns is what 2get* would have returned with the same arguments. If 1plist* is a symbol, the symbol's associated property list is used. For example, if the property list of 2foo* was 3(color blue height six-three near-to bar)* then 3(remprop 'foo 'height) => (six-three near-to bar)* and 2foo*'s property list would be 3(color blue near-to bar)* If 1plist* has no 1property-name*-property, then 2remprop* has no side-effect and returns 2nil*. 3getf* 1place* 1property* &optional 1default* 1Macro* Equivalent to 2(get (locf 1place*) 1property* 1default*)*, except that 2getf* is defined in Common Lisp, which does not have 2locf* or locatives of any kind. 2(setf (getf 1place* 1property*) 1value*)* can be used to store properties into the property list at 1place*. 3remf* 1place* 1property* 1Macro* Equivalent to 2(remprop (locf 1place*) 1property*)*, except that 2remf* is defined in Common Lisp. 3get-properties* 1place* 1list-of-properties* 1Macro* Like 2(getl (locf 1place*) 1list-of-properties*)* but returns slightly different values. Specifically, it searches the property list for a property name which is 2memq* in 1list-of-properties*, then returns three values: 1propname* the property name found 1value* the value of that property 1cell* the property list cell found, whose car is 1propname* and whose cadr is 1value*. If nothing is found, all three values are 2nil*. It is possible to continue searching down the property list by using 2cddr* of the third value as the argument to another call to 2get-properties*.