forked from rebcabin/dpans2texi
-
Notifications
You must be signed in to change notification settings - Fork 0
/
concept-conses.tex
134 lines (104 loc) · 4.81 KB
/
concept-conses.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
% -*- Mode: TeX -*-
A \newterm{cons} is a compound data \term{object}
having two components called the \term{car} and the \term{cdr}.
\displaythree{Some defined names relating to conses.}{
car&cons&rplacd\cr
cdr&rplaca&\cr
}
Depending on context, a group of connected \term{conses} can be viewed
in a variety of different ways. A variety of operations is provided to
support each of these various views.
\beginsubsection{Conses as Trees}
A \newterm{tree} is a binary recursive data structure made up of
\term{conses} and \term{atoms}:
the \term{conses} are themselves also \term{trees}
(sometimes called ``subtrees'' or ``branches''), and the \term{atoms}
are terminal nodes (sometimes called \newterm{leaves}).
Typically, the \term{leaves} represent data while the branches
establish some relationship among that data.
\displayfour{Some defined names relating to trees.}{
caaaar&caddar&cdar&nsubst\cr
caaadr&cadddr&cddaar&nsubst-if\cr
caaar&caddr&cddadr&nsubst-if-not\cr
caadar&cadr&cddar&nthcdr\cr
caaddr&cdaaar&cdddar&sublis\cr
caadr&cdaadr&cddddr&subst\cr
caar&cdaar&cdddr&subst-if\cr
cadaar&cdadar&cddr&subst-if-not\cr
cadadr&cdaddr©-tree&tree-equal\cr
cadar&cdadr&nsublis&\cr
}
\beginsubsubsection{General Restrictions on Parameters that must be Trees}
\issue{DOTTED-LIST-ARGUMENTS:CLARIFY}
Except as explicitly stated otherwise,
for any \term{standardized} \term{function} that takes a \term{parameter}
that is required to be a \term{tree},
the consequences are undefined
if that \term{tree} is circular.
\endissue{DOTTED-LIST-ARGUMENTS:CLARIFY}
\endsubsubsection%{General Restrictions on Parameters that must be Trees}
\endsubsection%{Conses as Trees}
\beginsubsection{Conses as Lists}
A \newterm{list} is a chain of \term{conses} in which the \term{car} of each
\term{cons} is an \term{element} of the \term{list},
and the \term{cdr} of each \term{cons} is either the next
link in the chain or a terminating \term{atom}.
A \newterm{proper list} is a \term{list} terminated by the \term{empty list}.
The \term{empty list} is a \term{proper list}, but is not a \term{cons}.
An \newterm{improper list} is a \term{list} that is not a \term{proper list};
that is, it is a \term{circular list} or a \term{dotted list}.
A \newterm{dotted list} is a \term{list} that has a terminating \term{atom}
that is not the \term{empty list}. A \term{non-nil} \term{atom} by itself
is not considered to be a \term{list} of any kind---not even a \term{dotted list}.
A \newterm{circular list} is a chain of \term{conses} that has no termination
because some \term{cons} in the chain is the \term{cdr} of a later \term{cons}.
\displayfour{Some defined names relating to lists.}{
append&last&nbutlast&rest\cr
butlast&ldiff&nconc&revappend\cr
copy-alist&list&ninth&second\cr
copy-list&list*&nreconc&seventh\cr
eighth&list-length&nth&sixth\cr
endp&make-list&nthcdr&tailp\cr
fifth&member&pop&tenth\cr
first&member-if&push&third\cr
fourth&member-if-not&pushnew&\cr
}
\beginsubsubsection{Lists as Association Lists}
An \newterm{association list} is a \term{list} of \term{conses}
representing an association of \term{keys} with \term{values},
where the \term{car} of each \term{cons} is the \term{key}
and the \term{cdr} is the \term{value} associated with that \term{key}.
\displayfour{Some defined names related to assocation lists.}{
acons&assoc-if&pairlis&rassoc-if\cr
assoc&assoc-if-not&rassoc&rassoc-if-not\cr
}
\endsubsubsection%{Lists as Association Lists}
\beginsubsubsection{Lists as Sets}
\term{Lists} are sometimes viewed as sets by considering their elements
unordered and by assuming there is no duplication of elements.
\displayfour{Some defined names related to sets.}{
adjoin&nset-difference&set-difference&union\cr
intersection&nset-exclusive-or&set-exclusive-or&\cr
nintersection&nunion&subsetp&\cr
}
\endsubsubsection%{Lists as Sets}
\beginsubsubsection{General Restrictions on Parameters that must be Lists}
%Barrett: This forces something like
% \f{(MEMBER X '(X Y . Z))} to detect the \f{( . Z )}
% in safe code even when it would not naturally be reached
% by the search. We should soften this slightly.
%KMP: Fixed.
Except as explicitly specified otherwise,
any \term{standardized} \term{function} that takes a \term{parameter}
that is required to be a \term{list} should be prepared to signal
an error \oftype{type-error} if the \term{value} received is a \term{dotted list}.
% Sandra complained that this was only said a few places,
% and needed to be said more.
% This is a stopgap while we make sure we mean it everywhere.
Except as explicitly specified otherwise,
for any \term{standardized} \term{function} that takes a \term{parameter}
that is required to be a \term{list},
the consequences are undefined
if that \term{list} is \term{circular}.
\endsubsubsection%{General Restrictions on Parameters that must be Lists}
\endsubsection%{Conses as Lists}