|The Revised Maclisp Manual||Page A-8|
A cons is a primitive data structure capable of holding exactly two things. There are two parts to a cons: the car (left half) and the cdr (right half). Conses are also referred to as dotted pairs because the input notation “(x . y)” describes a cons. The function CONS constructs conses, and the functions CAR and CDR access the two objects stored in the cons.
(cons 'a 'b) => (a . b)
The most common use of a cons in Lisp is to create a structure called a list. The symbol NIL is defined to denote the empty list. All other lists are conses whose car is any object and whose cdr is a list. The car is sometimes called the “head” or “first” of the list. The cdr is sometimes called the “tail” or “rest” of the list. For convenience, Lisp employs a shorthand notation for lists: Any dotted pair whose cdr is a list will display without the dot and without the parens around the cdr. So
The form... Is displayed by PRINT as... (A . (B C D)) (A B C D) (A . (B C)) (A B C) (A . (B)) (A B) (A . NIL) (A)
The last example makes sense if you remember NIL can also be written as (). So the list
((X Y Z) W (L M . N) Q)
Is really the same as
Both denote a list whose car is the list (X Y Z) and whose cdr is the list (W (L M . N) Q). Each of those things is in turn a list. This datastructure lends itself nicely to recursive descriptions of algorithms.
Lists like (L M . N) which have no trailing NIL are sometimes called “dotted lists.” They are not what is called a “proper list.” Like all conses, however, they are of type LIST and the LISTP predicate will return true for them.
|CONS||Function||(CONS q1 q2)|
(NCONS 'A) => (A)
|XCONS||Function||(XCONS q1 q2)|
(XCONS 'A 'B) => (B . A)
Returns the left half of a CONS. For hunks, returns the cxr-1 (not defined on one-length hunks). CAR of an atomic symbol (see documentation of the variable CAR) is not defined. The car of NIL is guaranteed to be NIL.
(CAR '(A B)) => A
(CAR '(1 . 2)) => 1
(CAR '((A B) (C D))) => (A B)
Returns the right half of a CONS. For hunks, returns the cxr-0. The CDR of an atomic symbol (see documentation of the variable CDR) is its property list; the PLIST function should be used to access this pointer in “modern” code. The cdr of NIL is guaranteed to be NIL.
(CDR '(A B)) => (B)
(CDR '(1 . 2)) => 2
(CDR '((A B) (C D))) => ((C D))
Short names for CAR/CDR compositions are provided in Maclisp up to four levels. e.g., (CAAR l) is like (CAR (CAR l)) and (CADAAR l) is like (CAR (CDR (CAR (CAR l)))). If any of these functions receive an argument of NIL or prematurely encounter NIL while CAR/CDRing through their argument, they are still guaranteed to return NIL.
|LIST||Function||(LIST q1 q2 q3 ...)|
LIST constructs and returns a list of the values of its arguments.
|LIST*||Function||(LIST* q1 q2 q3 ...)|
(LIST* 'A) => A
(LIST* 'A 'B) => (A . B)
(LIST* 'A 'B 'C) => (A B . C)
(LENGTH '(A B C D)) => 4
(LENGTH '(A (B C) D)) => 3
Same function as NOT. For clarity, use NULL when expecting q to be a list. Use NOT when q may be arbitrary. The difference is purely semantic, but semantic differences are important if you are to understand your code. It makes perfect sense to say something like (NOT (NULL x)) instead of simply x in a predicate position; this provides visual information to the reader that x is a list which might be null and is no less inefficient, since they compile to exactly the same code.
Different implementations do different things with this.
In PDP-10 Maclisp, (LISTP q) is the same as:
This behavior is, incidentally, compatible with Common Lisp.
In Multics Maclisp, (LISTP q) is the same as:
List Element Selectors
Returns the last dotted pair of its argument list, l, which must be NIL or a well-formed list. To get the last element, use (CAR (LAST l)). The behavior of LAST on lists which aren't well-formed, such as (A B . C), is not defined by the language and should not be relied upon, especially across implementations.
(last '(a b c d)) => (D)
(last '()) => NIL
|NTH||Function||(NTH i l)|
(NTH 3 '(A B C D)) => D
|NTHCDR||Function||(NTHCDR i l)|
(NTHCDR 3 '(A B C D E)) => (D E)
|APPEND||Function||(APPEND l1 l2 l3 ...)|
The arguments to append are lists. The result is a list which is the concatenation of the arguments. To avoid modifying the arguments, copies are made of all but the last.
See also: NCONC
(append '(a b c) '(d e f) nil '(g)) => (A B C D E F G) (setq new (append (setq leader '(a b c)) (setq trailer '(d e f)))) => (A B C D E F) ;; Append copies when necessary rather than modifying its inputs. ;; If it doesn't need to copy, it won't, so the last argument is never copied. (list leader (eq leader new) (eq (cdddr new) trailer)) => ((A B C) NIL T)
The expression (APPEND x NIL) is frequently found in code. This is not the same as just x. It copies the conses making up the toplevel list in x. Some Lisp dialects offer a function named COPYLIST which accomplishes this task. In Maclisp, COPYLIST could be defined by:
Given a list as argument, reverse creates a new list whose elements are the elements of its argument taken in reverse order. Reverse does not modify its argument, unlike nreverse which is faster but does modify its argument.
(REVERSE '(A (B C) D)) => (D (B C) A)
|ASSOC||Function||(ASSOC object alist)|
|ASSQ||Function||(ASSQ object alist)|
|SASSOC||Function||(SASSOC object l f)|
The reason that f does not receive an argument of the missing object is for compatibility with the Lisp 1.5 dialect. As a result, this function is almost never used. Most people prefer to write simply:
|SASSQ||Function||(SASSQ object l f)|
;; ASSQ is usually used for entries keyed by symbols. (setq x (assq 'r (setq db '((a . b) (c d e) (r . x) (s . y) (r . z))))) => (R . X) (assq 'c db) => (C D E) ; i.e., (C . (D E)) (setf (cdr x) 'new) => NEW (assq 'r db) => (R . NEW) (setf (car x) 'foo) => FOO (assq 'r db) => (R . Z) (assq 'k db) => NIL ;; ASSOC is usually used for entries keyed by non-symbols (assoc 3127. '((103. . (abc)) (2125. . foo) (3127. . something))) => (3127. . SOMETHING) (assoc '(a b) '((a b c) ((a b c) b) ((a b) d))) => ((A B) D)
|DELETE||Function||(DELETE q l [i])|
If no i is specified, returns the list l with all top-level occurrences of q removed. EQUAL is used for the comparison. The argument l is actually modified (RPLACD'ed) when instances of q are spliced out. If i is given, only the first i instances of q are deleted. If i is zero, no occurrences will be deleted; if i is greater than (or, of course, equal to) the number of occurrences of q in l, all occurrences of q in l will be deleted.
Warning: Users are cautioned not to rely on the side-effect of this result unless they understand how it can differ from the return value. The return value is guaranteed to have all requested elements removed, but the side-effect on the second argument may not have been this severe; leading element(s) which are EQUAL to the element being deleted will not have been actually spliced out of the second argument.
(DEFUN DELETE (Q L &OPTIONAL (N -1. N?)) (COND ((NOT N?) (*DELETE Q L)) ;defined elsewhere in this manual ((FIXP N) (COND ((BIGP N) (ERROR '|UNACCEPTABLE NUMERIC VALUE| N 'WRNG-TYPE-ARG)) ((OR (NULL L) (< N 1)) L) ((EQUAL Q (CAR L)) (DELETE Q (CDR L) (1- N))) (T (RPLACD L (DELETE Q (CDR L) N))))) (T (ERROR '|NON-NUMERIC VALUE| N 'WRNG-TYPE-ARG))))
|DELQ||Function||(DELQ q l [i])|
(setq x '(a a b a c (a b) d a e)) => (A A B A C (A B) D A E) (setq y (delq 'a x)) => (B C (A B) D E) ;; It is possible that the input to DELETE or DELQ may be modified but that all occurrences ;; will not be removed. In particular, leading elements will not have been removed. x (A A B C (A B) D E) ;; Only the return value is guaranteed to have been correct. y (B C (A B) D E)
|MAP||Function||(MAP f l1 l2 ...)|
The first argument to map is a function, and the remaining arguments are lists. Map “cdrs down” the lists, applying the function to successive cdrs of the lists each time. The first value tried is the whole list and the value returned by map is its second argument. Map stops as soon as one of the lists is exhausted.
;; Simple example (map #'print '(a b c)) (A B C) (B C) (C) => (A B C)
There are more examples on the next page.
|MAPLIST||Function||(MAPLIST f l1 l2 ...)|
Like MAP except that the return value is a list of the results of each application of the function.
|MAPCON||Function||(MAPCON f l1 l2 ...)|
;; A complex example -- Bubble Sort ;; This example courtesy of Richard Bryan (defun sort-a-list (ll predicate) (map #'(lambda (l) (map #'(lambda (m) (if (not (funcall predicate (car l) (car m))) (rplaca l (prog1 (car m) (rplaca m (car l)))))) l)) ll) ll) => SORT-A-LIST (setq test-list '(this is a test)) => (THIS IS A TEST) (sort-a-list test-list #'alphalessp) => (A IS TEST THIS) test-list => (A IS TEST THIS) ;; Another example -- comparing the results of the same function ;; through each of several mappers. (defun f (x) (list (length x) x)) => F (mapcar #'f '((a b c) (d e f) (g h i))) => ((3 (A B C)) (3 (D E F)) (3 (G H I))) (maplist #'f '((a b c) (d e f) (g h i))) => ((3 ((A B C) (D E F) (G H I))) (2 ((D E F) (G H I))) (1 ((G H I)))) (mapcon #'f '((a b c) (d e f) (g h i))) => (3 ((A B C) (D E F) (G H I)) 2 ((D E F) (G H I)) 1 ((G H I)))
|MAPC||Function||(MAPC f l1 l2 ...)|
Just like MAP except that the function is applied to successive elements of the lists rather than to the lists themselves. For use in place of MAPCAR when result won't be needed. MAPC returns l1, but it is poor form to rely on that from code.
|MAPCAR||Function||(MAPCAR f l1 l2 ...)|
Mapcar is like mapc except that the return value is a list of the results of each application of the function.
|MAPCAN||Function||(MAPCAN f l1 l2 ...)|
;; An example of MAPC (defun print-elements (a-list) (mapc #'print a-list) 'done) => PRINT-ELEMENTS (print-elements '((a b c) d (4 . 5))) (A B C) D (4 . 5) => DONE ;; A sophisticated MAPCAR example -- Matrix Transpose (DEFUN TRANSPOSE (M) ;This example courtesy of Vaughan Pratt (LEXPR-FUNCALL #'MAPCAR #'LIST M)) => TRANSPOSE (TRANSPOSE '((A B C) (D E F) (G H I))) => ((A D G) (B E H) (C F I)) (TRANPOSE '((A B C) (D E F))) => ((A D) (B E) (C F)) ;; An example of MAPCAN as a filter (defun filter (predicate list) (mapcan #'(lambda (x) (if (funcall predicate x) (ncons x))) list)) => FILTER (filter #'plusp '(1 3 -3 4 5 0 2)) => (1 3 4 5 2) (filter #'symbolp '(1 a 3 () 4.0 (a list))) => (A NIL)
List Membership Operators
|MEMBER||Function||(MEMBER object l)|
Returns NIL if object is not a member of the list, l. Otherwise, it returns the portion of l beginning with the first occurrence of object. The comparison is made by EQUAL. l is searched on the top level only. Note that the value returned by MEMBER is EQ to the portion of the list beginning with x. Thus RPLACA on the result of MEMBER may be used, if the a check is made to ensure that MEMBER did not return NIL.
|MEMQ||Function||(MEMQ object l)|
Like member, except EQ is used for the comparison.
Destructive List Utilities
|NCONC||Function||(NCONC l1 l2 l3 ...)|
Takes lists as arguments. It returns a list which is the arguments concatenated together. The arguments are modified, rather than copied (as APPEND would do). This entails bashing the tails of all non-null arguments, other than the last.
Reverses its argument list, l. l is destroyed by RPLACD's all through the list.
|NRECONC||Function||(NRECONC l1 l2)|
Same as (NCONC (NREVERSE l1) l2). Provided mainly because it is considerably more efficient to do these two operations at the same time than to do them separately. The argument l1 is effectively destroyed in this process.
;; Assign some variables (setq x '(a b c) y '(d e f) z '(g h i)) => (G H I) (setq new (nconc x y)) => (A B C D E F) ;; Unlike APPEND, NCONC can modify its argument (list x (eq x new)) => ((A B C D E F) T) ;; NREVERSE modifies its argument (and anything sharing structure ;; with its argument) in a rather bizarre way! (setq new (nreverse x)) => (F E D C B A) (list new x y) => ((F E D C B A) (A) (D C B A)) ;; NRECONC (setq newer (nreconc new z)) => (A B C D E F G H I) (list newer new) => ((A B C D E F G H I) (F G H I)) ;; For comparison, a similar sequence with non-destructive operators (setq xx '(a b c) xy '(d e f) xz '(g h i)) => (G H I) (setq xnew (append xx xy)) => (A B C D E F) (list xx (eq xx xnew)) => ((A B C) NIL) (setq xnew (reverse xx)) => (C B A) (list xnew xx xy) => ((C B A) (A B C) (D E F)) (setq xnewer (append (reverse xnew) xz)) => (A B C G H I) (list xnewer xnew) => ((A B C G H I) (C B A))
|RPLACA||Function||(RPLACA l object)|
|RPLACD||Function||(RPLACD l object)|
(setq x '(a b c) y (cdr x)) => (B C) (rplaca (cdr x) 'new) => (NEW C) (list x y) => ((A NEW C) (NEW C)) (rplacd y '(x y z)) => (NEW X Y Z) (list x y (setq z (cddr y))) => ((A NEW X Y Z) (NEW X Y Z) (Y Z)) (rplacd (cdr y) '(foo . bar)) => (X FOO . BAR) (list x y z) => ((A NEW X FOO . BAR) (NEW X FOO . BAR) (Y Z)) (rplaca y 'something) => (SOMETHING X FOO . BAR) (list x y z) => ((A SOMETHING X FOO . BAR) (SOMETHING X FOO . BAR) (Y Z))
|DISPLACE||Function||(DISPLACE l q)|
If q is a list, RPLACA's l with (CAR q) and RPLACD's it with (CDR q). This gives the effect of making l look like q. If q is an atom, (PROGN q) is used as the pattern to displace into l. The resulting form is returned.
Note: Not recommended for l's which are non-code or are code that will be broken by having the displace ignored. When pure (read-only) structure is encountered, there is controversy among the implementors about whether DISPLACE should signal an error or just return the replacement without trying to RPLACA it in. Currently, the RPLACA is not tried.
;; First some simple examples to illustrate the important points... (setq a '(a b) b '(c d)) => (C D) (setq new (displace a b)) => (C D) (list a b (eq a b) (eq new a) (eq new b)) => ((C D) (C D) NIL T NIL) (setq new (displace a 'x)) => (PROGN X) (list a new (eq a new)) => ((PROGN X) (PROGN X) T) ;; Here's another example, this time using DISPLACE from inside ;; a MACRO definition. If you used DEFMACRO, you wouldn't need ;; to bother with DISPLACE, but this gives you an idea of how ;; you can write displacing macros yourself if you don't like DEFMACRO. (macro plus2 (x) (displace x `(plus ,(cadr x) 2))) => PLUS2 (setq foo '(plus2 3)) => (PLUS2 3) (eval foo) => 5 foo => (PLUS 3 2)
The SORT Family
|SORT||Function||(SORT q f)|
SORT is used to sort an aggregate quantity q, which must be a list or an array, according to some ordering predicate f. The sort technique used is a quicksort. The input, q, is destructively modified.
f should be a function of two arguments, the domain of which includes all objects in the list or array. Thus if the array contains only atomic symbols, the predicate need only work with atomic symbols, but if the array also contains arbitrary S-expressions, the predicate must work for them as well. The predicate should return true iff the first argument is strictly less than the second (in some appropriate sense).
The SORT function proceeds to sort the contents of the array under the ordering imposed by the predicate, and returns its first argument. Note that since sorting requires many comparisons, and thus many calls to the predicate, sorting will be much faster if the predicate is a compiled function rather than interpreted.
|SORTCAR||Function||(SORTCAR q f)|
|SUBLIS||Function||(SUBLIS substitutions q)|
SUBLIS makes substitutions for atomic symbols in an S-expression. The first argument to SUBLIS is a list of dotted pairs. The second argument is an S-expression. The return value is the S-expression with atoms that are the car of a dotted pair replaced by the cdr of that dotted pair. The argument is not modified --- new conses are created where necessary and only where necessary, so the newly created structure shares as much of its substructure as possible with the old. For example, if no successful substitutions are made, the result is eq to SUBLIS's second argument.
Note: The car of each pair in the substitutions must be a symbol. The substitution algorithm depends on this. To substitute for other than symbols, use SUBST or write your own variant of SUBLIS which is more general.
See also: SUBST
(sublis '((x . 100) (z . zprime)) '(plus x (difference g z x p) q)) => (PLUS 100 (DIFFERENCE G ZPRIME 100 P) Q) ;; In fact, SUBLIS and SUBST are not quite the right thing ;; for arbitrary code substitutions because they may blindly ;; enter places you might wish they didn't. (sublis '((x . 100.)) '(list 'x 'is x)) => (LIST (QUOTE 100) (QUOTE IS) 100.) ;Not (LIST (QUOTE X) ...) ;; Example showing how SUBLIS's partial sharing works. (setq result (sublis '((x . y)) (setq input '((x y z) (a b) (x m) d e f)))) => ((Y Y Z) (A B) (Y M) D E F) (list (eq (car input) (car result)) (eq (cadr input) (cadr result)) (eq (caddr input) (caddr result)) (eq (cdr input) (cdr result)) (eq (cddr input) (cddr result)) (eq (cdddr input) (cdddr result))) => (NIL T NIL NIL NIL T)
The SUBLIS property is used internally to the SUBLIS function for marking symbols to be substituted for. The way it is used is very non-standard and it is not intended that the user try to take advantage of this property; we document it so you'll know not to store your own data on a property by this name.
|SUBST||Function||(SUBST new old form)|
The usage (SUBST NIL NIL form) is probably one of the most common places where SUBST is seen used. In this context, it just copies all levels of conses in form, returning the copy. In some dialects, this is given a name (such as COPYTREE in Lisp Machine Lisp). A Maclisp compatibility version of COPYTREE could be written as:
In Multics Maclisp, EQ is used instead of EQUAL in the test for replacement by SUBST. It is a bug that there is this divergence, but no attempt has been made to standardize to one or the other definition.
In fact, none of the major Lisp dialects seem to agree much on what the right thing for SUBST to do is when new or old is a non-symbol. Just to illustrate the discrepancy, consider the following examples from various Lisp dialects (data correct Dec. 8, 1980):
(subst '(new list) '(a b) '((a b) a b)) produced
((new list) new list) in Maclisp on the PDP-10 ((a b) a b) in Maclisp on Multics ((new list) a b) in Lisp Machine Lisp
As nearly as I could judge from the Interlisp documentation, Interlisp's SUBST produces output looking like Lisp Machine Lisp's, but the (new list) in the result is not eq to the first argument given.
Being conservative and assuming an EQ test is done is usually the best strategy. Substituting symbols for symbols in each of these Lisps is defined equivalently. The peculiar discrepancies come up only with numbers, lists, etc. For those applications, you might just write your own SUBST-like function as something like:
** The definition of real SUBST is actually more complex in its treatment of hunks. A treatment of what it does would be a good idea here.
(subst 'alpha 'a '(a b (c a))) => (ALPHA B (C ALPHA)) (setq foo '(a (b c))) => (A (B C)) (setq copy-of-foo (subst nil nil foo)) => (A (B C)) (progn (rplaca (cadr copy-of-foo) 'beta) (list copy-of-foo foo)) => ((A (BETA C)) (A (B C))) ;; Example showing how SUBST's full copying works. (setq result (subst 'y 'x (setq input '((x y z) (a b) (x m) d e f)))) => ((Y Y Z) (A B) (Y M) D E F) (list (eq (car input) (car result)) (eq (cadr input) (cadr result)) (eq (caddr input) (caddr result)) (eq (cdr input) (cdr result)) (eq (cddr input) (cddr result)) (eq (cdddr input) (cdddr result))) => (NIL NIL NIL NIL NIL NIL)
See also: SUBLIS
CAR/CDR Control Variables
By default, in the interpreter, CAR, CDR, RPLACA, and RPLACD do error checking to make sure you are taking CAR and CDR only of lists, hunks, and NIL. For certain system programming reasons, it may be necessary to over-ride this error checking selectively. This can be done by setting the variables CAR and CDR. The following settings for CAR and CDR are defined:
NIL This operation defined only on lists, hunks, or NIL. LIST This operation defined only on lists or hunks. SYMBOL This operation defined only on lists, symbols, hunks, or NIL. T This operation `defined' on any datatype.
In compiled code, these functions alway behave as if their controlling variable were set to T (no error checking). For safety, debug your code in interpreted form. Unintentionally calling CAR, CDR, RPLACA, or RPLACD on non-lists is a common way to produce an MPV error (Memory Protection Violation).
|The Revised Maclisp Manual (Sunday Morning Edition)|
Published Sunday, December 16, 2007 06:17am EST, and updated Sunday, July 6, 2008.