;;; -*- Mode:gate; Fonts:(HL12 HL12I HL12B CPTFONTB HL12BI HL12B HL12I ) -*- =Node: Introduction to List Structure Concepts =Text: 3INTRODUCTION TO LIST STRUCTURE CONCEPTS* This chapter discusses functions that manipulate conses, and higher-level structures made up of conses such as lists and trees. It also discusses hash tables and resources, which are related facilities. A 1cons* is a primitive Lisp data object that is extremely simple: it knows about two other objects, called its 1car* and its 1cdr*. A list is recursively defined to be the symbol 2nil*, or a cons whose cdr is a list. A typical list is a chain of conses: the cdr of each is the next cons in the chain, and the cdr of the last one is the symbol 2nil*. The cars of each of these conses are called the 1elements* of the list. A list has one element for each cons; the empty list, 2nil*, has no elements at all. Here are the printed representations of some typical lists: 3(foo bar) ;This list has two elements.* 3(a (b c d) e) ;This list has three elements.* Note that the second list has three elements: 2a*, 2(b c d)*, and 2e*. The symbols 2b*, 2c*, and 2d* are 1not* elements of the list itself. (They are elements of the list which is the second element of the original list.) A 1dotted list* is like a list except that the cdr of the last cons does not have to be 2nil*. This name comes from the printed representation, which includes a ``dot'' character (period). Here is an example: 3(a b . c)* This dotted list is made of two conses. The car of the first cons is the symbol 2a*, and the cdr of the first cons is the second cons. The car of the second cons is the symbol 2b*, and the cdr of the second cons is the symbol 2c*. A tree is any data structure made up of conses whose cars and cdrs are other conses. The following are all printed representations of trees: 3(foo . bar)* 3((a . b) (c . d))* 3((a . b) (c d e f (g . 5) s) (7 . 4))* These definitions are not mutually exclusive. Consider a cons whose car is 2a* and whose cdr is 2(b (c d) e)*. Its printed representation is 3(a b (c d) e)* It can be thought of and treated as a cons, or as a list of four elements, or as a tree containing six conses. You can even think of it as a dotted list whose last cons just happens to have 2nil* as a cdr. Thus, lists and dotted lists and trees are not fundamental data types; they are just ways of thinking about structures of conses. A circular list is like a list except that the cdr of the last cons, instead of being 2nil*, is the first cons of the list. This means that the conses are all hooked together in a ring, with the cdr of each cons being the next cons in the ring. These are legitimate Lisp objects, but dealing with them requires special techniques; straightforward tree-walking recursive functions often loop infinitely when given a circular list. The printer is is an example of both aspects of the handling of circular lists: if 2*print-circle** is non-2nil* the printer uses special techniques to detect circular structure and print it with a special encoding, but if 2*print-circle** is 2nil* the printer does not check for circularity and loops infinitely unless 2*print-level** or 2*print-length** imposes a ``time limit''. See 4(READPRINT-1)Options that Control Printing* for more information on 2*print-circle** and related matters. The Lisp Machine internally uses a storage scheme called 1cdr-coding* to represent conses. This scheme is intended to reduce the amount of storage used in lists. The use of cdr-coding is invisible to programs except in terms of storage efficiency; programs work the same way whether or not lists are cdr-coded or not. Several of the functions below mention how they deal with cdr-coding. You can completely ignore all this if you want. However, if you are writing a program that allocates a lot of conses and you are concerned with storage efficiency, you may want to learn about the cdr-coded representation and how to control it. The cdr-coding scheme is discussed in 4(MANLISTSTR-1)Cdr-Coding*. =Node: Conses =Text: 3CONSES car* 1x* Returns the car of 1x*. Example: 3(car '(a b c)) => a cdr* 1x* Returns the cdr of 1x*. Example: 3(cdr '(a b c)) => (b c)* Officially 2car* and 2cdr* are only applicable to conses and locatives. However, as a matter of convenience, 2car* and 2cdr* of 2nil* return 2nil*. 2car* or 2cdr* of anything else is an error. 3c* 1...r* 1x* All of the compositions of up to four 2car*'s and 2cdr*'s are defined as functions in their own right. The names of these functions begin with 2c* and end with 2r*, and in between is a sequence of 2a*'s and 2d*'s corresponding to the composition performed by the function. Example: 3(cddadr x) 2is the same as* (cdr (cdr (car (cdr x))))* The error checking for these functions is exactly the same as for 2car* and 2cdr* above. 3cons* 1x* 1y* 2cons* is the primitive function to create a new cons, whose car is 1x* and whose cdr is 1y*. Examples: 3(cons 'a 'b) => (a . b)* 3(cons 'a (cons 'b (cons 'c nil))) => (a b c)* 3(cons 'a '(b c d)) => (a b c d) ncons* 1x* 2(ncons 1x*)* is the same as 2(cons 1x* nil)*. The name of the function is from ``nil-cons''. 3xcons* 1x* 1y* 2xcons* (``exchanged cons'') is like 2cons* except that the order of the arguments is reversed. Example: 3(xcons 'a 'b) => (b . a) cons-in-area* 1x* 1y* 1area-number* Creates a cons in a specific 1area*. (Areas are an advanced feature of storage management, explained in chapter 4(AREAS-0)Areas*; if you aren't interested in them, you can safely skip all this stuff). The first two arguments are the same as the two arguments to 2cons*, and the third is the number of the area in which to create the cons. Example: 3(cons-in-area 'a 'b my-area) => (a . b) ncons-in-area* 1x* 1area-number* 2(ncons-in-area 1x area-number*)* = 2(cons-in-area 1x* nil 1area-number*)* 3xcons-in-area* 1x* 1y* 1area-number* 2(xcons-in-area 1x y area-number*) = (cons-in-area 1y x area-number*)* 3push* 1item* 1place* 1Macro* Adds an element 1item* to the front of a list that is stored in 1place*. A new cons is allocated whose car is 1item* and whose cdr is the old contents of 1place*. This cons is stored into 1place*. The form 3(push (hairy-function x y z) variable)* replaces the commonly-used construct 3(setq variable (cons (hairy-function x y z) variable))* and is intended to be more explicit and esthetic. 1place* can be any form that 2setf* can store into. For example, 3(push x (get y z))* 3 ==> (putprop y (cons x (get y z)) z)* The returned value of 2push* is not defined. 3pop* 1place* 1Macro* Removes an element from the front of the list that is stored in 1place*. It finds the cons in 1place*, stores the cdr of the cons back into 1place*, and returns the car of that cons. 1place* can be any form that 2setf* can store into. Example: 3(setq x '(a b c))* 3(pop x) => a* 3x => (b c)* The backquote reader macro facility is also generally useful for creating list structure, especially mostly-constant list structure, or forms constructed by plugging variables into a template. It is documented in the chapter on macros; see 4(MACROS-0)Macros*. 3car-location* 1cons* 2car-location* returns a locative pointer to the cell containing the car of 1cons*. Note: there is no 2cdr-location* function; it is difficult because of the cdr-coding scheme (see 4(MANLISTSTR-1)Cdr-Coding*). Instead, the cons itself serves as a kind of locative to its cdr (see 4(LOCATIVES-1)Cells and Locatives*). The functions 2rplaca* and 2rplacd* are used to make alterations in already-existing list structure; that is, to change the cars and cdrs of existing conses. The structure is altered rather than copied. Exercise caution when using these functions, as strange side-effects can occur if they are used to modify portions of list structure which have become shared unbeknownst to the programmer. The 2nconc*, 2nreverse*, 2nreconc*, 2nbutlast* and 2delq* functions and others, described below, have the same property, because they call 2rplaca* or 2rplacd*. 3rplaca* 1x* 1y* Changes the car of 1x* to 1y* and returns (the modified) 1x*. 1x* must be a cons or a locative. 1y* may be any Lisp object. Example: 3(setq g '(a b c))* 3(rplaca (cdr g) 'd) => (d c)* 2Now3 g => (a d c) rplacd** 1x* 1y* Changes the cdr of 1x* to 1y* and returns (the modified) 1x*. 1x* must be a cons or a locative. 1y* may be any Lisp object. Example: 3(setq x '(a b c))* 3(rplacd x 'd) => (a . d)* 2Now3 x => (a . d)** 2(setf (car 1x*) 1y*)* and 2(setf (car 1x*) 1y*)* are much like 2rplaca* and 2rplacd*, but they return 1y* rather than 1x*. =Node: Lists =Text: 3LISTS list* &rest 1args* Constructs and returns a list of its arguments. Example: 3(list 3 4 'a (car '(b . c)) (+ 6 -2)) => (3 4 a b 4)* 3list* could have been defined by: 3(defun list (&rest args)* 3 (let ((list (make-list (length args))))* 3 (do ((l list (cdr l))* 3 (a args (cdr a)))* 3 ((null a) list)* 3 (rplaca l (car a))))) list** &rest 1args* 2list** is like 2list* except that the last cons of the constructed list is dotted. It must be given at least one argument. Example: 3(list* 'a 'b 'c 'd) => (a b c . d)* This is like 3(cons 'a (cons 'b (cons 'c 'd)))* More examples: 3(list* 'a 'b) => (a . b)* 3(list* 'a) => a length* 1list-or-array* Returns the length of 1list-or-array*. The length of a list is the number of elements in it; the number of times you can cdr it before you get a non-cons. Examples: 3(length nil) => 0* 3(length '(a b c d)) => 4* 3(length '(a (b c) d)) => 3* 3(length "foobar") => 6* 2length* could have been defined by: 3(defun length (x)* 3 (if (arrayp x) (array-active-length x)* 3 (do ((n 0 (1+ n))* 3 (y x (cdr y)))* 3 ((null y) n)))) list-length* 1list* Returns the length of 1list*, or 2nil* if 1list* is circular. (The function 2length* would loop forever if given a circular list.) 3first* 1list* 3second* 1list* 3third* 1list* 3fourth* 1list* 3fifth* 1list* 3sixth* 1list* 3seventh* 1list* These functions take a list as an argument, and return the first, second, etc. element of the list. 2first* is identical to 2car*, 2second* is identical to 2cadr*, and so on. The reason these names are provided is that they make more sense when you are thinking of the argument as a list rather than just as a cons. 3rest* 1list* 3rest1* 1list* 3rest2* 1list* 3rest3* 1list* 3rest4* 1list* 2rest1n** returns the rest of the elements of a list, starting with element 1n* (counting the first element as the zeroth). Thus 2rest* or 2rest1* is identical to 2cdr*, 2rest2* is identical to 2cddr*, and so on. The reason these names are provided is that they make more sense when you are thinking of the argument as a list rather than just as a cons. 3endp* 1list* Returns 2t* if 1list* is 2nil*, 2nil* if 1list* is a cons cell. Signals an error if 1list* is not a list. This is the way Common Lisp recommends for terminating a loop which 2cdr*'s down a list. However, Lisp Machine system functions generally prefer to test for the end of the list with 2atom*; it is regarded as a feature that these functions do something useful for dotted lists. 3nth* 1n* 1list* 2(nth 1n* 1list*)* returns the 1n*'th element of 1list*, where the zeroth element is the car of the list. If 1n* is greater than the length of the list, 2nil* is returned. Examples: 3(nth 1 '(foo bar gack)) => bar* 3(nth 3 '(foo bar gack)) => nil* Note: this is not the same as the InterLisp function called 2nth*, which is similar to but not exactly the same as the Lisp Machine function 2nthcdr*. Also, some people have used macros and functions called 2nth* of their own in their Maclisp programs, which may not work the same way; be careful. 3nth* could have been defined by: 3(defun nth (n list)* 3 (do ((i n (1- i))* 3 (l list (cdr l)))* 3 ((zerop i) (car l)))) nthcdr* 1n* 1list* 2(nthcdr 1n* 1list*)* cdrs 1list* 1n* times, and returns the result. Examples: 3(nthcdr 0 '(a b c)) => (a b c)* 3(nthcdr 2 '(a b c)) => (c)* In other words, it returns the 1n*'th cdr of the list. If 1n* is greater than the length of the list, 2nil* is returned. This is similar to InterLisp's function 2nth*, except that the InterLisp function is one-based instead of zero-based; see the InterLisp manual for details. 2nthcdr* could have been defined by: 3(defun nthcdr (n list)* 3 (do ((i 0 (1+ i))* 3 (list list (cdr list)))* 3 ((= i n) list))) last* 1list* 2last* returns the last cons of 1list*. If 1list* is 2nil*, it returns 2nil*. Note that 2last* is unfortunately 1not* analogous to 2first* (2first* returns the first element of a list, but 2last* doesn't return the last element of a list); this is a historical artifact. Examples: 3(setq x '(a b c d))* 3(last x) => (d)* 3(rplacd (last x) '(e f))* 3x => '(a b c d e f)* 2last* could have been defined by: 3(defun last (x)* 3 (cond ((atom x) x)* 3 ((atom (cdr x)) x)* 3 ((last (cdr x))))) list-match-p* 1object* 1pattern* 1Macro* 1object* is evaluated and matched against 1pattern*; the value is 2t* if it matches, 2nil* otherwise. 1pattern* is made with backquotes (4(MACROS-1)Backquote*); whereas normally a backquote expression says how to construct list structure out of constant and variable parts, in this context it says how to match list structure against constants and variables. Constant parts of the backquote expression must match exactly; variables preceded by commas can match anything but set the variable to what was matched. (Some of the variables may be set even if there is no match.) If a variable appears more than once, it must match the same thing (2equal* list structures) each time. 2,ignore* can be used to match anything and ignore it. For example, 2`(x (,y) . ,z)* is a pattern that matches a list of length at least two whose first element is 2x* and whose second element is a list of length one; if a list matches, the 2caadr* of the list is stored into the value of 1y* and the 2cddr* of the list is stored into 1z*. Variables set during the matching remain set after the 2list-match-p* returns; in effect, 2list-match-p* expands into code which can 2setq* the variables. If the match fails, some or all of the variables may already have been set. Example: 3(list-match-p foo* 3 `((a ,x) ,ignore . ,c))* is 2t* if 2foo*'s value is a list of two or more elements, the first of which is a list of two elements; and in that case it sets 2x* to 2(cadar foo)* and 2c* to 2(cddr foo)*. An equivalent expression would be 3(let ((tem foo))* 3 (and (consp tem)* 3 (consp (car tem))* 3 (eq (caar tem) 'a)* 3 (consp (cdar tem))* 3 (progn (setq x (cadar tem)) t)* 3 (null (cddar tem))* 3 (consp (cdr tem))* 3 (setq c (cddr tem))))* but 3list-match-p* is faster. 2list-match-p* generates highly optimized code using special instructions. 3list-in-area* 1area-number* &rest 1args* 2list-in-area* is exactly the same as 2list* except that it takes an extra argument, an area number, and creates the list in that area. 3list*-in-area* 1area-number* &rest 1args* 2list*-in-area* is exactly the same as 2list** except that it takes an extra argument, an area number, and creates the list in that area. 3make-list* 1length* &key 1area* 1initial-element* Creates and returns a list containing 1length* elements. 1length* should be a fixnum. 1area*, if specified, is the area in which to create the list (see 4(AREAS-0)Areas*). If it is 2nil*, the area used is the value of 2working-storage-area*. 1initial-element* is stored in each element of the new list. 2make-list* always creates a cdr-coded list (see 4(MANLISTSTR-1)Cdr-Coding*). Examples: 3(make-list 3) => (nil nil nil)* 3(make-list 4 :initial-element 7) => (7 7 7 7)* The keyword 2:initial-value* may be used in place of 2:initial-element*. When 2make-list* was originally implemented, it took exactly two arguments: the area and the length. This obsolete form is still supported so that old programs can continue to work, but the new keyword-argument form is preferred. 3circular-list* &rest 1args* Constructs a circular list whose elements are 2args*, repeated infinitely. 2circular-list* is the same as 2list* except that the list itself is used as the last cdr, instead of 2nil*. 2circular-list* is especially useful with 2mapcar*, as in the expression 3(mapcar (function +) foo (circular-list 5))* which adds each element of 2foo* to 5. 3circular-list* could have been defined by: 3(defun circular-list (&rest elements)* 3 (setq elements (copylist* elements))* 3 (rplacd (last elements) elements)* 3 elements) copylist* 1list* &optional 1area* 3copy-list* 1list* &optional 1area* Returns a list which is 2equal* to 1list*, but not 2eq*. 2copylist* does not copy any elements of the list, only the conses of the list itself. The returned list is fully cdr-coded (see 4(MANLISTSTR-1)Cdr-Coding*) to minimize storage. If 1list* is dotted, that is, if 2(cdr (last 1list*))* is a non-2nil* atom, then the copy also has this property. You may optionally specify the area in which to create the new copy. 3copylist** 1list* &optional 1area* This is the same as 2copylist* except that the last cons of the resulting list is never cdr-coded (see 4(MANLISTSTR-1)Cdr-Coding*). This makes for increased efficiency if you 2nconc* something onto the list later. 3copyalist* 1list* &optional 1area* 3copy-alist* 1list* &optional 1area* 2copyalist* is for copying association lists (see 4(MANLISTSTR-2)Tables*). The 1list* is copied, as in 2copylist*. In addition, each element of 1list* which is a cons is replaced in the copy by a new cons with the same car and cdr. You may optionally specify the area in which to create the new copy. 3append* &rest 1lists* The arguments to 2append* are lists. The result is a list which is the concatenation of the arguments. The arguments are not changed (cf. 2nconc*). Example: 3(append '(a b c) '(d e f) nil '(g)) => (a b c d e f g)* 2append* makes copies of the conses of all the lists it is given, except for the last one. So the new list shares the conses of the last argument to append, but all of the other conses are newly created. Only the lists are copied, not the elements of the lists. A version of 2append* which only accepts two arguments could have been defined by: 3(defun append2 (x y)* 3 (cond ((null x) y)* 3 ((cons (car x) (append2 (cdr x) y)) )))* The generalization to any number of arguments could then be made (relying on car of 2nil* being 2nil*): 3(defun append (&rest args)* 3 (if (< (length args) 2) (car args)* 3 (append2 (car args)* 3 (apply (function append) (cdr args)))))* These definitions do not express the full functionality of 2append*; the real definition minimizes storage utilization by turning all the arguments that are copied into one cdr-coded list. To copy a list, use 2copylist* (see 4(MANLISTSTR-1)Lists*); the old practice of using 2append* to copy lists is unclear and obsolete. 3nconc* &rest 1lists* 2nconc* takes lists as arguments. It returns a list which is the arguments concatenated together. The arguments are changed, rather than copied (cf. 2append*, 4(MANLISTSTR-1)Lists*). Example: 3(setq x '(a b c))* 3(setq y '(d e f))* 3(nconc x y) => (a b c d e f)* 3x => (a b c d e f)* Note that the value of 2x* is now different, since its last cons has been 2rplacd*'d to the value of 2y*. If the 2nconc* form were evaluated again, it would yield a piece of circular list structure, whose printed representation would be 2(a b c d e f d e f d e f ...)*, repeating forever. 2nconc* could have been defined by: 3(defun nconc (x y) ;2for simplicity, this definition** 3 (cond ((null x) y) ;2only works for 2 arguments.** 3 (t (rplacd (last x) y) ;2hook y onto *x* 3 x))) ;2and return the modified x.* revappend* 1x* 1y* 2(revappend 1x y*)* is exactly the same as 2(nconc (reverse 1x*) 1y*)* except that it is more efficient. Both 1x* and 1y* should be lists. 2revappend* could have been defined by: 3(defun revappend (x y)* 3 (cond ((null x) y)* 3 (t (revappend (cdr x) (cons (car x) y))))) nreconc* 1x* 1y* 2(nreconc 1x y*)* is exactly the same as 2(nconc (nreverse 1x*) 1y*)* except that it is more efficient. Both 1x* and 1y* should be lists. 2nreconc* could have been defined by: 3(defun nreconc (x y)* 3 (cond ((null x) y)* 3 ((nreverse1 x y)) ))* using the same 2nreverse1* as above. 3butlast* 1list* &optional 1(n* 311)** This creates and returns a list with the same elements as 1list*, excepting the last 1n* elements. Examples: 3(butlast '(a b c d)) => (a b c)* 3(butlast '(a b c d) 3) => (a)* 3(butlast '(a b c d) 4) => nil* 3(butlast nil) => nil* The name is from the phrase ``all elements but the last''. 3nbutlast* 1list* &optional 1(n* 311)** This is the destructive version of 2butlast*; it changes the cdr of the last cons but 1n* of the list to 2nil*. The value is 1list*, as modified. If 1list* does not have more than 1n* elements then it is not really changed and the value is 2nil*. Examples: 3(setq foo '(a b c d))* 3(nbutlast foo) => (a b c)* 3foo => (a b c)* 3(nbutlast foo 2) => (a)* 3foo => (a)* 3(nbutlast foo) => nil* 3foo => (a) firstn* 1n* 1list* Returns a list of length 1n*, whose elements are the first 1n* elements of 2list*. If 1list* is fewer than 1n* elements long, the remaining elements of the returned list are 2nil*. Examples: 3(firstn 2 '(a b c d)) => (a b)* 3(firstn 0 '(a b c d)) => nil* 3(firstn 6 '(a b c d)) => (a b c d nil nil) nleft* 1n* 1list* &optional 1tail* Returns a ``tail'' of 1list*, i.e. one of the conses that makes up 1list*, or 2nil*. 2(nleft 1n* 1list*)* returns the last 1n* elements of 1list*. If 1n* is too large, 2nleft* returns 1list*. 2(nleft 1n* 1list* 1tail*)* takes cdr of 1list* enough times that taking 1n* more cdrs would yield 1tail*, and returns that. You can see that when 1tail* is 2nil* this is the same as the two-argument case. If 1tail* is not 2eq* to any tail of 1list*, 2nleft* returns 2nil*. Examples: 3(setq x '(a b c d e f))* 3(nleft 2 x) => (e f)* 3(nleft 2 x (cddddr x)) => (c d e f) ldiff* 1list* 1tail* 1list* should be a list, and 1tail* should be one of the conses that make up 1list*. 2ldiff* (meaning `list difference') returns a new list, whose elements are those elements of 1list* that appear before 1tail*. Examples: 3(setq x '(a b c d e))* 3(setq y (cdddr x)) => (d e)* 3(ldiff x y) => (a b c)* 3(ldiff x nil) => (a b c d e)* 3(ldiff x x) => nil* but 3(ldiff '(a b c d) '(c d)) => (a b c d)* since the 2tail* was not 3eq* to any part of the 2list*. 3car-safe* 1object* 3cdr-safe* 1object* 3caar-safe* 1object* 3cadr-safe* 1object* 3cdar-safe* 1object* 3cddr-safe* 1object* 3caddr-safe* 1object* 3cdddr-safe* 1object* 3cadddr-safe* 1object* 3cddddr-safe* 1object* 3nth-safe* 1n* 1object* 3nthcdr-safe* 1n* 1object* Return the same things as the corresponding non-2safe* functions, except 2nil* if the non-2safe* function would get an error. These functions are about as fast as the non-2safe* functions. The same effect could be had by handling the 2sys:wrong-type-argument* error, but that would be slower. Examples: 3(car-safe '(a . b)) => a* 3(car-safe nil) => nil* 3(car-safe 'a) => nil* 3(car-safe "foo") => nil* 3(cadr-safe '(a . b)) => nil* 3(cadr-safe 3) => nil* =Node: Cons Cells as Trees =Text: 3CONS CELLS AS TREES copytree* 1tree* &optional 1area* 3copy-tree* 1tree* &optional 1area* 2copytree* copies all the conses of a tree and makes a new maximally cdr-coded tree with the same fringe. If 1area* is specified, the new tree is constructed in that area. 3tree-equal* 1x* 1y* &key 1test* 1test-not* Compares two trees recursively to all levels. Atoms must match under the function 1test* (which defaults to 2eql*). Conses must match recursively in both the car and the cdr. If 1test-not* is specified instead of 1test*, two atoms match if 1test-not* returns 2nil*. 3subst* 1new* 1old* 1tree* 2(subst 1new old tree*)* substitutes 1new* for all occurrences of 1old* in 1tree*, and returns the modified copy of 1tree*. The original 1tree* is unchanged, as 2subst* recursively copies all of 1tree* replacing elements 2equal* to 1old* as it goes. Example: 3(subst 'Tempest 'Hurricane* 3 '(Shakespeare wrote (The Hurricane)))* 3 => (Shakespeare wrote (The Tempest))* 2subst* could have been defined by: 3(defun subst (new old tree)* 3 (cond ((equal tree old) new) ;2if item equal to old, replace.** 3 ((atom tree) tree) ;2if no substructure, return arg.** 3 ((cons (subst new old (car tree)) ;2otherwise recurse.** 3 (subst new old (cdr tree))))))* Note that this function is not destructive; that is, it does not change the car or cdr of any already-existing list structure. To copy a tree, use 2copytree* (see 4(MANLISTSTR-1)Cons Cells as Trees*); the old practice of using 2subst* to copy trees is unclear and obsolete. 3cli:subst* 1new* 1old* 1tree* &key 1test* 1test-not* 1key* The Common Lisp version of 2subst* replaces with 1new* every atom or subtree in 1tree* which matches 1old*, returning a new tree. List structure is copied as necessary to avoid clobbering parts of tree. This differs from the traditional 2subst* function, which always copies the entire tree. 1test* or 1test-not* is used to do the matching. 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*. The first argument to the 1test* or 1test-not* function is always 1old*. The second argument is normally a leaf or subtree of 1tree*. However, if 1key* is non-2nil*, then it is called with the subtree as argument, and the result of this becomes the second argument to the 1test* or 1test-not* function. Because 2(subst nil nil 1tree*)* is a widely used idiom for copying a tree, even though it is obsolete, there is no practical possibility of installing this function as the standard 2subst* for a long time. 3nsubst* 1new* 1old* 1tree* &key 1test* 1test-not* 1key* 2nsubst* is a destructive version of 2subst*. The list structure of 1tree* is altered by replacing each occurrence of 1old* with 1new*. No new list structure is created. The keyword arguments are as in 2cli:subst*. A simplified version of 2nsubst*, handling only the three required arguments, could be defined as 3(defun nsubst (new old tree)* 3 (cond ((eql tree old) new) ;2If item matches old, replace.** 3 ((atom tree) tree) ;2If no substructure, return arg.** 3 (t ;2Otherwise, recurse.** 3 (rplaca tree (nsubst new old (car tree)))* 3 (rplacd tree (nsubst new old (cdr tree)))* 3 tree))) subst-if* 1new* 1predicate* 1tree* &key 1key* Replaces with 1new* every atom or subtree in 1tree* which satisfies 1predicate*. List structure is copied as necessary so that the original tree is not modified. 1key*, if non-2nil*, is a function applied to each tree node to get the object to match against. If 1key* is 2nil* or omitted, the tree node itself is used. 3subst-if-not* 1new* 1predicate* 1tree* &key 1key* Similar, but replaces tree nodes which 1do not* satisfy 1predicate*. 3nsubst-if* 1new* 1predicate* 1tree* &key 1key* 3nsubst-if-not* 1new* 1predicate* 1tree* &key 1key* Like 2subst-if* and 2subst-if-not* except that they destructively modify 1tree* itself and return it, creating no new list structure. 3sublis* 1alist* 1tree* &key 1test* 1test-not* 1key* Performs multiple parallel replacements on 1tree*, returning a new tree. 1tree* itself is not modified because list structure is copied as necessary. If no substitutions are made, the result is 1tree*. 1alist* is an association list (see 4(MANLISTSTR-2)Tables*). Each element of 1alist* specifies one replacement; the car is what to look for, and the cdr is what to replace it with. 1test*, 1test-not* and 1key* control how matching is done between nodes of the tree (cons cells or atoms) and objects to be replaced. See 2cli:subst*, above, for the details of how they work. The first argument to 1test* or 1test-not* is the car of an element of 1alist*. Example: 3(sublis '((x . 100) (z . zprime))* 3 '(plus x (minus g z x p) 4))* 3 => (plus 100 (minus g zprime 100 p) 4)* A simplified sublis could be defined by: 3(defun sublis (alist tree)* 3 (let ((tem (assq tree alist)))* 3 (cond (tem (cdr tem))* 3 ((atom tree) tree)* 3 (t* 3 (let ((car (sublis alist (car tree)))* 3 (cdr (sublis alist (cdr tree))))* 3 (if (and (eq (car tree) car) (eq (cdr tree) cdr))* 3 tree* 3 (cons car cdr))))))) nsublis* 1alist* 1tree* &key 1test* 1test-not* 1key* 2nsublis* is like 2sublis* but changes the original tree instead of allocating new structure. A simplified nsublis could be defined by: 3(defun nsublis (alist tree)* 3 (let ((tem (assq tree alist)))* 3 (cond (tem (cdr tem))* 3 ((atom tree) tree)* 3 (t (rplaca tree (nsublis alist (car tree)))* 3 (rplacd tree (nsublis alist (cdr tree)))* 3 tree))))* =Node: Cdr-Coding =Text: 3CDR-CODING* This section explains the internal data format used to store conses inside the Lisp Machine. Casual users don't have to worry about this; you can skip this section if you want. It is only important to read this section if you require extra storage efficiency in your program. The usual and obvious internal representation of conses in any implementation of Lisp is as a pair of pointers, contiguous in memory. If we call the amount of storage that it takes to store a Lisp pointer a `word', then conses normally occupy two words. One word (say it's the first) holds the car, and the other word (say it's the second) holds the cdr. To get the car or cdr of a list, you just reference this memory location, and to change the car or cdr, you just store into this memory location. Very often, conses are used to store lists. If the above representation is used, a list of 1n* elements requires two times 1n* words of memory: 1n* to hold the pointers to the elements of the list, and 1n* to point to the next cons or to 2nil*. To optimize this particular case of using conses, the Lisp Machine uses a storage representation called 1cdr-coding* to store lists. The basic goal is to allow a list of 1n* elements to be stored in only 1n* locations, while allowing conses that are not parts of lists to be stored in the usual way. The way it works is that there is an extra two-bit field in every word of memory, called the 1cdr-code* field. There are three meaningful values that this field can have, which are called 2cdr-normal*, 2cdr-next*, and 2cdr-nil*. The regular, non-compact way to store a cons is by two contiguous words, the first of which holds the car and the second of which holds the cdr. In this case, the cdr-code of the first word is 2cdr-normal*. (The cdr-code of the second word doesn't matter; as we will see, it is never looked at.) The cons is represented by a pointer to the first of the two words. When a list of 1n* elements is stored in the most compact way, pointers to the 1n* elements occupy 1n* contiguous memory locations. The cdr-codes of all these locations are 2cdr-next*, except the last location whose cdr-code is 2cdr-nil*. The list is represented as a pointer to the first of the 1n* words. Now, how are the basic operations on conses defined to work based on this data structure? Finding the car is easy: you just read the contents of the location addressed by the pointer. Finding the cdr is more complex. First you must read the contents of the location addressed by the pointer, and inspect the cdr-code you find there. If the code is 2cdr-normal*, then you add one to the pointer, read the location it addresses, and return the contents of that location; that is, you read the second of the two words. If the code is 2cdr-next*, you add one to the pointer, and simply return that pointer without doing any more reading; that is, you return a pointer to the next word in the 1n*-word block. If the code is 2cdr-nil*, you simply return 2nil*. If you examine these rules, you will find that they work fine even if you mix the two kinds of storage representation within the same list. How about changing the structure? Like 2car*, 2rplaca* is very easy; you just store into the location addressed by the pointer. To do 2rplacd* you must read the location addressed by the pointer and examine the cdr-code. If the code is 2cdr-normal*, you just store into the location one greater than that addressed by the pointer; that is, you store into the second word of the two words. But if the cdr-code is 2cdr-next* or 2cdr-nil*, there is a problem: there is no memory cell that is storing the cdr of the cons. That is the cell that has been optimized out; it just doesn't exist. This problem is dealt with by the use of 1invisible pointers*. An invisible pointer is a special kind of pointer, recognized by its data type (Lisp Machine pointers include a data type field as well as an address field). The way they work is that when the Lisp Machine reads a word from memory, if that word is an invisible pointer then it proceeds to read the word pointed to by the invisible pointer and use that word instead of the invisible pointer itself. Similarly, when it writes to a location, it first reads the location, and if it contains an invisible pointer then it writes to the location addressed by the invisible pointer instead. (This is a somewhat simplified explanation; actually there are several kinds of invisible pointer that are interpreted in different ways at different times, used for things other than the cdr-coding scheme.) Here's how to do 2rplacd* when the cdr-code is 2cdr-next* or 2cdr-nil*. Call the location addressed by the first argument to 2rplacd* 1l*. First, you allocate two contiguous words in the same area that 1l* points to. Then you store the old contents of 1l* (the car of the cons) and the second argument to 2rplacd* (the new cdr of the cons) into these two words. You set the cdr-code of the first of the two words to 2cdr-normal*. Then you write an invisible pointer, pointing at the first of the two words, into location 1l*. (It doesn't matter what the cdr-code of this word is, since the invisible pointer data type is checked first, as we will see.) Now, whenever any operation is done to the cons (2car*, 2cdr*, 2rplaca*, or 2rplacd*), the initial reading of the word pointed to by the Lisp pointer that represents the cons finds an invisible pointer in the addressed cell. When the invisible pointer is seen, the address it contains is used in place of the original address. So the newly-allocated two-word cons is used for any operation done on the original object. Why is any of this important to users? In fact, it is all invisible to you; everything works the same way whether or not compact representation is used, from the point of view of the semantics of the language. That is, the only difference that any of this makes is a difference in efficiency. The compact representation is more efficient in most cases. However, if the conses are going to get 2rplacd*'ed, then invisible pointers will be created, extra memory will be allocated, and the compact representation will degrade storage efficiency rather than improve it. Also, accesses that go through invisible pointers are somewhat slower, since more memory references are needed. So if you care a lot about storage efficiency, you should be careful about which lists get stored in which representations. You should try to use the normal representation for those data structures that will be subject to 2rplacd* operations, including 2nconc* and 2nreverse*, and the compact representation for other structures. The functions 2cons*, 2xcons*, 2ncons*, and their area variants make conses in the normal representation. The functions 2list*, 2list**, 2list-in-area*, 2make-list*, and 2append* use the compact representation. The other list-creating functions, including 2read*, currently make normal lists, although this might get changed. Some functions, such as 2sort*, take special care to operate efficiently on compact lists (2sort* effectively treats them as arrays). 2nreverse* is rather slow on compact lists, currently, since it simple-mindedly uses 2rplacd*, but this may be changed. 2(copylist 1x*)* is a suitable way to copy a list, converting it into compact form (see 4(MANLISTSTR-1)Lists*).