Web pdp-10.trailing-edge.com

Trailing-Edge - PDP-10 Archives - decuslib20-01 - decus/20-0004/6lisp.tty
There are no other files named 6lisp.tty in the archive.
```

SECTION 6

LIST MANIPULATION AND CONCATENATION

list[x1;x2;...;xn]      lambda-nospread function.   Its value is  a list
of the values of its arguments.

append[x1;x2;...;xn]    Copies the top level of the list x1  and appends
this to a copy of top level list  x2 appended to
... appended to xn, e.g.,
append[(A B) (C D E) (F G)] = (A B C D E F G).
Note that only  the first n-1 lists  are copied.
However   n=1   is   treated   specially;  i.e.,
append[x] can be used to copy the top level of a
1
single list.

The following examples illustrate  the treatment
of non-lists.

append[(A B C);D] = (A B C . D)
append[A;(B C D)] = (B C D)
append[(A B C . D);(E F G)] = (A B C E F G)
append[(A B C . D)] = (A B C . D).

nconc[x1;x2;...;xn]     Returns  same  value  as  append   but  actually
modifies the list structure of x1 ... xn-1.

Note that  nconc cannot change  NIL to  a list. In  other words,  if the
value of foo  is NIL, then  the value of  (NCONC FOO (QUOTE (A B C))) is
(A B C), but  foo will  not have  been changed.   The "problem"  is that
nconc simply  has a collection  of pointers to  work with, and  does not
know where they originally came from, i.e., does not know that  this NIL
is the value of  foo, and while it  is possible to alter  list structure
using rplaca, there is no way to change a non-list to a list.

nconc1[lst;x]           Performs nconc[lst;list[x]].   The cons  will be
on the same page as lst.

------------------------------------------------------------------------
1
To copy a list to all levels, use copy.

6.1
```
```

tconc[ptr;x]            tconc is  useful for building  a list  by adding
elements one  at a  time at  the end,  i.e., its
role  is similar  to that  of  nconc1.  However,
unlike nconc1,-1, tconc does not have  to search
to the end of  the list each time it  is called.
It does this by keeping a pointer to the  end of
the  list  being  assembled,  and  updating this
pointer  after each  call.  The  savings  can be
considerable for  long lists.   The cost  is the
extra word  required for  storing both  the list
being assembled, and  the end of the  list.  ptr
is  that  word:  car[ptr]  is  the   list  being
assembled,  cdr[ptr]  is  last [car[ptr]].   The
value  of  tconc is  ptr,  with  the appropriate
modifications to car and cdr.  Example:

_(RPTQ 5 (SETQ FOO (TCONC FOO RPTN)))
((5 4 3 2 1) 1).

tconc can be initialized in two ways.  If ptr is
NIL, tconc  will make up  a ptr.  In  this case,
the program must set some variable to  the value
of the first call  to tconc.  After that,  it is
unnecessary to reset ptr since  tconc physically
changes it.  Thus:

_(SET FOO (TCONC NIL 1))
((1) 1)
_(RPTQ 4 (TCONC FOO RPTN))
((1 4 3 2 1) 1).

If ptr is initially (NIL), the value of tconc is
the same as for ptr=NIL, but tconc  changes ptr,
e.g.,

_(SETQ FOO (CONS))
(NIL)
_(RPTQ 5 (TCONC FOO RPTN))
((5 4 3 2 1) 1).

The   latter  method   allows  the   program  to
initialize, and  then call tconc  without having
to perform setq on its value.

lconc[ptr;x]            Where tconc is used  to add elements at  the end
of a list, lconc is used for building a  list by
adding lists at the end, i.e., it is  similar to

_(SETQ FOO (CONS))
(NIL)
_(LCONC FOO (LIST 1 2))
((1 2) 2)
_(LCONC FOO (LIST 3 4 5))
((1 2 3 4 5) 5)
_(LCONC FOO NIL)
((1 2 3 4 5) 5)

6.2
```
```

Note that

_(TCONC) FOO NIL)
((1 2 3 4 5 NIL) NIL)
_(TCONC FOO (LIST 3 4 5))
((1 2 3 4 5 NIL (3 4 5)) (3 4 5))

lconc uses the same pointer conventions as tconc
for  eliminating  searching to  the  end  of the
list, so that the  same pointer can be  given to
tconc and lconc interchangeably.

attach[x;y]             Value is equal  to cons[x;y], but attaches  x to
the front  of y by  doing an rplaca  and rplacd,
i.e., the value of  attach is eq to y,  which it
physically  changes.  y  must be  a list,  or an
error is generated, ARG NOT LIST.

remove[x;l]             Removes all occurrences of x from list l, giving
a  copy  of  l  with  all  elements  equal  to x
removed.

Convention: Naming a function  by prefixing an existing function  with d
frequently indicates the  new function is  a destructive version  of the
old one, i.e., it does  not make any new structure but  cannibalizes its
argument(s).

dremove[x;l]            Similar to remove, but uses eq instead of equal,
and actually modifies  the list l  when removing
x, and thus does not use any additional storage.
More efficient than remove.

Note that  dremove cannot  change a list  to NIL.   For example,  if the
value of foo is  (A), then (DREMOVE (QUOTE A) FOO) will return  NIL, and
not perform any conses, but the  value of foo will still be  (A) because
there  is  not way  to  change a  list  to a  non-list.   See discussion
following description of nconc on page 6.2.

copy[x]                 Makes a copy of  the list x.  The value  of copy
is  the  copied  list.   All  levels  of  x  are
2
copied,   down  to  non-lists,  so  that   if  x
contains arrays and strings, the copy of  x will
contain the same arrays and strings, not copies.
Copy is recursive in the car direction  only, so
that very long lists can be copied.

------------------------------------------------------------------------
2
To copy just the top level of x, do append[x].

6.3
```
```

copyall[x]              Like  copy except  copies down  to  atoms, i.e.,
arrays, hash-arrays,  strings, user  data types,
etc., are all copied.

reverse[l]              Reverses (and copies)  the top level of  a list,
e.g., reverse[(A B (C D))] = ((C D) B A).   If x
is not a list, value is x.

dreverse[l]             Value is same  as that of reverse,  but dreverse
destroys the original  list l and thus  does not
use any additional storage.  More efficient than
reverse.

subst[x;y;z]            Value  is  the  result  of  substituting  the S-
expression  x  for  all  occurrences  of  the S-
expression    y   in    the    S-expression   z.
Substitution occurs whenever  y is equal  to car
of some  subexpression of z,  or when y  is both
atomic  and  not  NIL  and  eq  to  cdr  of some
subexpression of z.  For example:

subst[A;B;(C B (X . B))] = (C A (X . A))
subst[A;(B C);((B C) D B C)] = (A D B C),
not (A D . A).

The  value of  subst  is a  copy of  z  with the
appropriate  changes.   Furthermore, if  x  is a
list, it is copied at each substitution.

dsubst[x;y;z]           Similar  to  subst,  but does  not  copy  z, but
changes the list structure z itself. Like subst,
dsubst  substitutes  with  a  copy  of  x.  More
efficient than subst.

lsubst[x;y;z]           Like subst except x is substituted as a segment,
e.g.,      lsubst[(A B);Y;(X Y Z)] is (X A B Z).
Note that if x is NIL, produces a copy of z with
all y's deleted.

esubst[x;y;z;flg]       Similar to dsubst, but first checks to see  if y
actually  appears in  z.  If  not,  calls error!
where flg=T means print a message of the  form x
? This function is actually an implementation of
the editor's R command (see Section 9),  so that
y  can use  &, --,  or alt-modes  as with  the R
command.

6.4
```
```

sublis[alst;expr;flg]   alst      is      a      list      of     pairs:
((u1 . v1) (u2 . v2) ... (un . vn)) with each ui
atomic.

The value of sublis[alst;expr;flg] is the result
of substituting each  v for the  corresponding u
3
in expr,   e.g.,
sublis[((A . X) (C . Y));(A B C D)] = (X B Y D).
New structure is  created only if needed,  or if
flg=T,  e.g.,  if  flg=NIL  and  there   are  no
substitutions, value is eq to expr.

subpair[old;new;expr;flg]
Similar to sublis,  except that elements  of new
are substituted  for corresponding atoms  of old
in expr, e.g.,
subpair[(A C);(X Y);(A B C D)]  = (X B Y D)
As with sublis, new structure is created only if
needed, or if flg=T, e.g., if flg=NIL  and there
are no substitutions, the value is eq to expr.

If old ends in an atom other than NIL,  the rest
of the elements on new are substituted  for that
atom.    For  example,   if   old=(A B . C)  and
new=(U V X Y Z), U is  substituted for A,  V for
B, and (X Y Z) for C.  Similarly, if  old itself
is an atom (other than NIL), the entire list new
is substituted for it.

Note that subst, dsubst, lsubst, and esubst all substitute copies of the
appropriate  expression,  whereas  subpair  and  sublis  substitute  the
identical structure (unless flg=T).

last[x]                 Value is a pointer to the last node in  the list
x,  e.g., if  x=(A B C) then  last[x] = (C).  If
x=(A B . C) last[x] = (B . C).  Value is  NIL if
x is not a list.

flast[x]                Fast version of last  that compiles open as  a 5
instruction loop,  terminating on  a null-check.
Interpreted, generates an error, BAD  ARGUMENT -
FLAST, if x ends in other than NIL.

nleft[l;n;tail]         Tail is a tail of l or NIL.  The value  of nleft
is the tail of  l that contains n  more elements

------------------------------------------------------------------------
3
To remember the order on alst, think of it as old to new, i.e., ui -
> vi.

6.5
```
```

4
than               tail,                e.g., if
x=(A B C D E), nleft[x;2]=(D E),
nleft[x;1;cddr[x]]=(B C D E).  Thus nleft can be
used to work backwards through a list.  Value is
NIL if l does  not contain n more  elements than
tail.

lastn[l;n]              Value  is  cons[x;y],  where  y  is  the  last n
elements  of l,  and x  is the  initial segment,
e.g.,
lastn[(A B C D E);2]=((A B C) D E)
lastn[(A B);2]=(NIL A B).

Value is NIL, if  l is not a list  containing at
least n elements.

nth[x;n]                Value is  the tail of  x beginning with  the nt-
1th-1h element, e.g.,  if n=2, value  is cdr[x],
if n=3,  cddr[x], etc.  If  n=1, value is  x, if
n=0, for consistency, value is  cons[NIL;x].  If
x has fewer than n elements, value is NIL, e.g.,
nth[(A B);3]=NIL, as is nth[(A . B);3] Note that
nth[(A . B);2]=B.

fnth[x;n]               Fast version  of nth that  compiles open as  a 3
instruction loop,  terminating on  a null-check.
Interpreted, generates an error, BAD  ARGUMENT -
FNTH, if x ends in other than NIL.

length[x]               Value is the length  of the list x  where length
is  defined as  the number  of cdrs  required to
reach a non-list, e.g.,
length[(A B C)] = 3
length[(A B C . D)] = 3
length[A] = 0

flength[x]              Fast version of length that compiles open as a 4
instruction loop,  terminating on  a null-check.
Interpreted, generates an error, BAD  ARGUMENT -
FLENGTH, if x ends in other than NIL.

count[x]                Value  is  the  number  of  list  words  in  the
structure x.  Thus, count is like a  length that
goes to all levels.  Count of a non-list is 0.

------------------------------------------------------------------------
4
If tail is not NIL, but not  a tail of l, the result is the  same as
if tail  were NIL, i.e.,  nleft operates by  scanning l  looking for
tail, not by computing the lengths of l and tail.

6.6
```
```

ldiff[x;y;z]            y must be a tail of x, i.e., eq to the result of
applying some number  of cdrs to  x.  ldiff[x;y]
gives a list of all elements in x up to y, i.e.,
the   list  difference   of  x   and   y.   Thus
ldiff[x;member[FOO;x]] gives  all elements  in x
up to the first FOO.

Note that the value of ldiff is always new list structure  unless y=NIL,
in which case the value is x itself.

If  z  is  not  NIL,  the  value  of   ldiff  is
effectively nconc[z;ldiff[x;y]], i.e.,  the list
difference is added at the end of z.

If y  is not  a tail of  x, generates  an error,
LDIFF: NOT A TAIL.   ldiff   terminates   on   a
null-check.

intersection[x;y]       Value is  a list whose  elements are  members of
both lists x and y.  Note that intersection[x;x]
gives a  list of  all members  of x  without any
duplications.

union[x;y]              Value is a (new) list consisting of all elements
included on  either of  the two  original lists.
It is  more efficient to  make x be  the shorter
5
list.

6
sort[data;comparefn]    data  is  a list  of  items to  be  sorted using
comparefn, a predicate function of two arguments
which  can compare  any  two items  on  data and
return  T if  the first  one belongs  before the
second.  If comparefn is NIL, alphorder is used;
thus  sort[data]  will alphabetize  a  list.  If
comparefn  is T,  car's  of items  are  given to
alphorder; thus sort[a-list;T]  will alphabetize
by the  car of  each item.   sort[x;ILESSP] will
sort a list of integers.

------------------------------------------------------------------------
5
The value of union  is y with all elements  of x not in y  consed on
the front  of it. Therefore,  if an element  appears twice in  y, it
will     appear     twice     in     union[x;y].     Also,     since
union[(A);(A A)] = (A A),  while  union[(A A);(A)] = (A),  union  is
non-commutative.

6
Sort, merge, and alphorder were written by J. W. Goodwin.

6.7
```
```

The value of sort is the sorted list.   The sort
is destructive and  uses no extra  storage.  The
value returned is  eq to data but  elements have
been switched around.  Interrupting with control
D, E, or B may cause loss of data, but control H
may be used at any time, and sort will  break at
a clean state from which ^ or control characters
are safe.   The algorithm used  by sort  is such
that the maximum number of compares is n*log2 n,
where n is length[data].

Note: if comparefn[a;b] = comparefn[b;a],  then the ordering of a  and b
may or may not be preserved.

For example, if (FOO .  FIE) appears before (FOO . FUM) in  x, sort[x;T]
may or may not reverse the order of these two elements.  Of  course, the
user can always specify a more precise comparefn.

merge[a;b;comparefn]    a  and b  are lists  which have  previously been
sorted  using sort  and comparefn.   Value  is a
destructive merging of  the two lists.   It does
not matter which list is longer.   After merging
both a  and b  are equal to  the merged  list In
fact,  cdr[a] is  eq  to cdr[b]).  merge  may be
aborted after control-H.

alphorder[a;b]          A  predicate  function  of  two  arguments,  for
alphabetizing.  Returns  T if its  arguments are
in order, i.e., if  b does not belong  before a.
Numbers  come  before  literal  atoms,  and  are
ordered by magnitude (using  greaterp).  Literal
atoms and strings  are ordered by  comparing the
(ASCII) character  codes in their  pnames.  Thus
alphorder[23;123]       is       T,      whereas
alphorder[A23;A123]   is   NIL,    because   the
character code for  the digit 2 is  greater than
the code for 1.

Atoms and strings  are ordered before  all other
data types.   If neither  a nor  b are  atoms or
strings, the value  of alphorder is T,  i.e., in
order.

Note:  alphorder does  no unpacks,  chcons, conses  or nthchars.   It is
several times faster for alphabetizing than anything that can be written
using these other functions.

mergeinsert[new;lst]    lst is NIL or a list of partially  sorted items.
mergeinsert tries  to find  the "best"  place to
(destructively)      insert      new,      e.g.,
mergeinsert[FIE2; (FOO FOO1 FIE FUM)]=
(FOO FOO1 FIE FIE2 FUM).     Value    is    lst.
mergeinsert is undoable.

6.8
```
```

mergeinsert is used  by addtofile (Section 14)  to insert the name  of a
new function into a list of functions.  The algorithm is  essentially to
look for the item with the longest common leading sequence of characters
with respect to new, and then merge new in starting at that point.

cplists[x;y]            compares x and  y and prints  their differences,
i.e., cplists is  essentially a SRCCOM  for list
structures.

6.9
```