Google
 

Trailing-Edge - PDP-10 Archives - decus_20tap1_198111 - decus/20-0004/06lisp.doc
There are no other files named 06lisp.doc 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
                        nconc instead of nconc1, e.g.,

                        _(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