REF LISTS                                           John Gibson Mar 1994

        COPYRIGHT University of Sussex 1994. All Rights Reserved.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<                             >>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<       LISTS AND PAIRS       >>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<                             >>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

This REF file provides information on the 'list' data structure: how  it
is constructed from pairs, the two  types of lists: normal and  dynamic,
as well as detailing the predicates for use on pairs and lists, pair and
list constructor and access procedures, and other list utilities.

         CONTENTS - (Use <ENTER> g to access required sections)

  1   Introduction

  2   Predicates on Pairs and Lists

  3   Pair Constructor and Access Procedures

  4   List Constructor Procedures

  5   List Access Procedures

  6   Other List Utilities

  7   Generic Data Structure Procedures on Lists

  8   Miscellaneous



---------------
1  Introduction
---------------

A pair  is a  record which  contains two  arbitrary Poplog  data  items,
called the front and the back of the pair: these structures may be  used
in their own right for any purposes.

The most frequent use of pairs, however, is to represent lists of items.
A list is represented in Poplog as a chain of pairs, where the front  of
each pair in the chain is used to hold the next element of the list, and
the back to  hold the  continuation of the  chain, which  may be  either
another pair or the special item [] (the value of nil) at the end of the
list. The two parts of the pair are then known respectively as the  head
and the tail (of  the list represented by  the pair). Thus, whereas  the
head of a list can be any item, the tail must always be another list.

Lists in Poplog can  also be dynamic:  a dynamic list  is one where  the
final element-holding pair in the chain contains in its back not []  but
another (special)  pair,  this pair  having  in its  back  a  procedure.
Whenever an attempt is made to access  the head or tail of this  special
pair, the procedure is called with the expectation that it will  produce
as result the next element of the list (or the item termin if there  are
no more to come).  The result is then  added to the end  of the list  by
placing it in  the front of  the special pair  and constructing  another
special pair to go in  its back (thus the  old special pair becomes  the
last proper pair of the list).

A pair whose  back is  a procedure  is therefore  a valid  list, as  yet
unexpanded, and  which  will be  expanded  by the  application  of  list
procedures like hd, tl, etc. The front of such a pair will contain  true
until the procedure in its back produces termin, at which time the front
becomes false. This indicates that the list is now null (and application
of hd, tl etc will produce an error).

See TEACH * PAIRS, * LISTS for tutorial introductions to pairs and lists
in Pop-11. HELP * LISTS overviews the on-line documentation relating  to
list processing in Pop-11.




--------------------------------
2  Predicates on Pairs and Lists
--------------------------------

atom(item) -> bool                                           [procedure]
        Returns true if item is not a pair, false otherwise.  Equivalent
        to not(ispair(item)).


isdynamic(item) -> p                                         [procedure]
        Returns the generator procedure p underlying a dynamic list,  or
        false if item is not a dynamic list.


ispair(item) -> bool                                         [procedure]
        Returns true if item is a pair, false otherwise.


islist(item) -> bool                                         [procedure]
        Returns true if item is a  list, false otherwise. A list is  one
        of:

          # The value of the constant nil, i.e. [].

          # A pair whose back is [], a procedure, or another pair.

          # A pair  whose  front  is  a boolean,  and  whose  back  is a
            procedure, i.e. a dynamic list.


islink(item) -> bool                                         [procedure]
        Returns true if item is a non-null pair.


null(list) -> bool                                           [procedure]
        Returns true if the list list is empty, false otherwise. list is
        empty if it is either

          # The value of the constant nil, i.e. [].

          # A pair with front false and back a procedure, i.e a  dynamic
            list whose procedure has returned termin.

        Note that  applying  null to  an  unexpanded dynamic  list  pair
        causes it to be expanded.


lmember_=(item, list) -> sublist_or_false                    [procedure]
        If item is  an element of  the list list,  returns the  trailing
        portion of  list starting  with that  element, otherwise  false.
        E.g.

                lmember_=(2, [1 5 4 6 2 3 7 9]) =>
                ** [2 3 7 9]

                lmember_=([3 4 5], [1 2 [3 4 5] 6 7]) =>
                ** [[3 4 5] 6 7]

        Note that equality is  determined with the  operator =, that  is
        the result will be  a list if list  contains an element that  is
        structurally equal to item.


lmember(item, list) -> sublist_or_false                      [procedure]
        If item is  an element of  the list list,  returns the  trailing
        portion of  list starting  with that  element, otherwise  false.
        E.g.

                lmember(2, [1 5 4 6 2 3 7 9]) =>
                ** [2 3 7 9]

        Note that, unlike lmember_=, equality is determined by using the
        operator  ==  (absolute  equality),  which  generally  makes  it
        faster. But

                lmember([3 4 5], [1 2 [3 4 5] 6 7]) =>
                ** <false>

        returns false because although the item argument is structurally
        equal to a member of list, it is not the actual same structure.


member(item, list) -> bool                          [procedure variable]
        The default procedure in this variable is the same as lmember_=,
        but returns true instead of a sublist, i.e. member is defined as

                lmember_=(item, list) and true

        For example:

                member(2, [1 5 4 6 2 3 7 9]) =>
                ** <true>

                member([3 4 5], [1 2 [3 4 5] 6 7]) =>
                ** <true>




-----------------------------------------
3  Pair Constructor and Access Procedures
-----------------------------------------

conspair(item1, item2) -> pair                               [procedure]
        Constructs and returns  a pair  whose front is  item1 and  whose
        back is item2.


front(pair) -> item                                          [procedure]
item -> front(pair)
        Returns or updates the front of the pair pair.


back(pair) -> item                                           [procedure]
item -> back(pair)
        Returns or updates the back of the pair pair.


destpair(pair) -> (item1, item2)                             [procedure]
        Returns two results, the front item1  and the back item2 of  the
        pair pair.


recursive_front(item1) -> item2                              [procedure]
        Repeatedly applies front to item1 while a pair, and then returns
        whatever (non-pair) value results.

        (This procedure is used by  syspr to extract a procedure's  name
        from its pdprops  when printing the  procedure. The pdprops  can
        thus contain (e.g) a pair whose front is the name and whose back
        is some other data.)


lastpair(pair) -> item                                       [procedure]
item -> lastpair(pair)
        Where pair is the first in a chain of pairs (usually a non-empty
        list), returns  or  updates the  last  pair in  the  chain.  For
        example:

            vars l = [a b c d e];
            lastpair(l) =>
            ** [e]
            "f" -> lastpair(l);
            l =>
            ** [a b c d|f]

        (Note that in  this example, the  update operation has  replaced
        the last pair in the list with a word -- hence it is no longer a
        valid list.)

        Since it operates at the pair level, lastpair will not  expand a
        dynamic list, or even recognise one as such. (The last pair of a
        dynamic list has the generator procedure in its back.)




------------------------------
4  List Constructor Procedures
------------------------------

nil -> list                                                   [constant]
        Constant containing the unique item [], the empty list. Thus

                nil -> x;

        is equivalent to

                [] -> x;


conslist(item1, item2, ..., itemN, N) -> list                [procedure]
        Returns a list  list constructed  from the  top N  items on  the
        stack.


cons(item, list1) -> list2                                   [procedure]
        Constructs and returns a list whose head is item and whose  tail
        is the list list1 (exactly like ::).


item :: list1 -> list2                                      [operator 4]
        This operator constructs and returns  a list whose head is  item
        and whose tail is the list list1.


initl(len) -> list                                           [procedure]
        Constructs a list of length  len. Initially each element is  the
        empty list nil.


pdtolist(p) -> list                                          [procedure]
        Constructs and returns a dynamic list from the procedure p, i.e.
        a pair whose front is true and whose back is the procedure  p. p
        should produce  exactly one  item each  time it  is called,  and
        <termin> (the value of the constant termin) as the last item.


expandlist(list) -> list                                     [procedure]
        Returns  list  unchanged.  If  list  is  a  dynamic  list   then
        expandlist will  expand  all  its elements  and  make  the  list
        static. This  procedure will  loop  forever if  the list  is  of
        infinite length.


sysconslist_onto(list1) -> list2                             [procedure]
        The result list2 of this procedure  is a list consisting of  all
        the  elements  on  the  user   stack  up  to  the  unique   item
        <popstackmark>  (the  value   of  the  constant   popstackmark),
        followed by the argument list list1.

        Pop-11 list constructors use this with a trailing ^^ followed by
        a variable, e.g,

                [% 5, 6, 7, 8 %] -> list;
                [% 1, 2, 3, 4 % ^^list ]

        is equivalent to

                popstackmark, 1, 2, 3, 4;
                sysconslist_onto(list);

        and produces the list [1 2 3 4 5 6 7 8].


sysconslist() -> list                                        [procedure]
        Same as sysconslist_onto([]). Pop-11 list constructors use this,
        i.e,

                [% 1, 2, 3, 4 %]

        is equivalent to

                popstackmark, 1, 2, 3, 4;
                sysconslist();




-------------------------
5  List Access Procedures
-------------------------

dest(list) -> tail_list -> head_item                         [procedure]
        Returns two results,  the tail and  the head of  the list  list,
        which must not be null.


hd(list) -> head_item                                        [procedure]
head_item -> hd(list)
        Returns or updates the head of the list list, which must not  be
        null.


tl(list) -> tail_list                                        [procedure]
tail_list -> tl(list)
        Returns or updates the tail of the list list, which must not  be
        null.


subscrl(N, list) -> item                                     [procedure]
item -> subscrl(N, list)
        Returns or updates the N-th element of the list list (where  the
        first element has  subscript 1). Because  this procedure is  the
        class_apply procedure of  pairs, this  can also be  used in  the
        form

                list(N) -> item
                item -> list(N)


destlist(list) -> (item1, item2, ..., itemN, N)              [procedure]
        Puts the N elements of the list list on the stack, together with
        the number N.


dl(list) -> (item1, item2, ..., itemN)                      [procedure]
(item1, item2, ..., itemN) -> dl(list)
        Puts the N elements of the list list on the stack, e.g.

                dl([1 2 3 4])

        is equivalent to 1, 2, 3, 4. The updater fills list with the top
        N items from the stack, e.g.

                vars list = [a b c d];
                1, 2, 3, 4 -> dl(list);
                list =>
                ** [1 2 3 4]


oneof(list) -> item                                          [procedure]
        Returns a  randomly chosen  element of  list (using  the  random
        number generator * random). For example:

            vars list = [cat dog goat];
            oneof(list) =>
            ** cat
            oneof(list) =>
            ** goat

        (list must not be empty.)




-----------------------
6  Other List Utilities
-----------------------

applist(list, p)                                             [procedure]
-> applist(list, p)
        Applies the procedure p  to each element of  the list list.  The
        updater applies  the  updater  of  p to  each  element  of  list
        backwards, i.e.

                -> applist(list, p)

        is functionally the same as

                applist(rev(list), updater(p))

        Compare with maplist.


copylist(list1) -> list2                                     [procedure]
        Returns a copy of the list, list1, i.e. list2 is a list in which
        all the pairs are  copies of those in  list1. copylist does  not
        copy elements of list1 which are themselves lists, see  copytree
        for a recursive copier.


copytree(list1) -> list2                                     [procedure]
        This makes a list, list2, which is a copy of list1. Any elements
        of list1 which are themselves lists are recursively copied.


delete(item, list1)          -> list2                        [procedure]
delete(item, list1, eq_p)    -> list2
delete(item, list1, N)       -> list2
delete(item, list1, eq_p, N) -> list2
        Deletes occurrences of  item from  list1, producing  a new  list
        list2 (which shares the largest possible trailing sublist of the
        original).

        eq_p  is  an  optional  argument;  if  supplied,  it  must  be a
        procedure of the form

                eq_p(list_element, item) -> bool

        eq_p is  used to  compare each  list element  against item,  and
        those for which  it returns  true are deleted.  If not  supplied
        eq_p defaults to nonop = (i.e. structure equality).

        N is a second optional argument:  if supplied, it is an  integer
        >= 0  which  specifies  how many  matching  elements  should  be
        deleted (e.g,  if  1 then  only  the first  occurrence  will  be
        removed). If not supplied, all occurrences are deleted.

        For example,

            delete(1, [1 2 3 4 5 6 1 9 8]) =>
            ** [2 3 4 5 6 9 8]

        (In this example, the  trailing sublist [9  8] is unaffected  by
        the delete and will be shared with the original list.)


ncdelete(item, list1)          -> list2                      [procedure]
ncdelete(item, list1, eq_p)    -> list2
ncdelete(item, list1, N)       -> list2
ncdelete(item, list1, eq_p, N) -> list2
        Same as delete (see  above), but does not  copy list pairs  that
        need to  be changed,  and thus  (may) destructively  change  the
        original list. The result list2 will be == to list1 unless there
        are one or more  leading matching occurrences  of item that  are
        deleted.


flatten(item) -> list                                        [procedure]
        Returns a  list  of  all  the  items  produced  by  'recursively
        list-destructing' item, where this means:

          # if   item   is   a   list,   the   result   of   recursively
            list-destructing each element;

          # item otherwise.

        In other words, 'flattens' every tree of lists or sub-lists that
        can be traced from item.


listlength(list) -> N                                        [procedure]
        Returns the number of elements n in the list list.


maplist(list1, p) -> list2                                   [procedure]
list2 -> maplist(list1, p)
        Applies the procedure p to each element of the list list1,  and
        returns a list  of all  results produced  in so  doing. This  is
        equivalent to

                [% applist(list1, p) %] -> list2

        The action of the updater is

                dl(list2) -> applist(list1, p)


ncmaplist(list, p) -> list                                   [procedure]
        Applies procedure  p to  every element  of its  first  argument,
        replacing that element with the  result of calling p.  ncmaplist
        is destructive  in  that  it  re-uses the  pairs  of  its  first
        argument. For example:

            vars l = [0.6 2.2 2.9 4.0];
            ncmaplist(l, round) =>
            ** [1 2 3 4]
            l =>
            ** [1 2 3 4]

        Compare with maplist.


rev(list1) -> list2                                          [procedure]
        Returns a new list which is the list list1 reversed.


ncrev(list) -> list                                          [procedure]
        Destructively reverses the order of  the elements of list,  i.e.
        it re-uses the links of its argument.


setfrontlist(item, list1) -> list2                           [procedure]
        Returns list2 formed by moving the  item to the front of  list1,
        or adding the item if not already present.


shuffle(list1) -> list2                                      [procedure]
        Returns list2,  a  copy of  the  list list1  with  the  elements
        randomly re-ordered.


nc_listsort(list, p) -> list                                 [procedure]
        Sorts the argument list according  to the ordering procedure  p,
        using a merge sort  algorithm. nc_listsort is Non-Copying  (i.e.
        it re-uses the  list pairs  in list  in building  up the  sorted
        result, and Non-Checking  (no checks  are made  to confirm  that
        list is indeed a list, and dynamic lists are not expanded).

        The ordering procedure p should be of the form

                p(item1, item2) -> bool

        i.e. a procedure which  takes two items  and returns true  (non-
        false actually) if item1 should come before item2 in the  sorted
        list. <= (for  numbers) and alphabefore  (for words or  strings)
        are examples of this kind of procedure.


syssort(list, p) -> list                                     [procedure]
syssort(list, copy, p) -> list
        Uses * nc_listsort to produce a sorted copy of list, unless  the
        optional boolean argument copy is false, in which case the  sort
        is non-copying. Dynamic  lists are expanded  before the  sorting
        takes place.


sort(list1) -> list2                                         [procedure]
        Returns a list of sorted items, using

                syssort(list1, p) -> list2

        If list1 begins with  a number, the operation  <= (less than  or
        equal) is used for the ordering procedure p; otherwise, list1 is
        assumed  to  contains  words  or  strings,  and  the   procedure
        alphabefore is  used.  (If  the list  contains  both  words  and
        numbers then a mishap will occur).


insertsort(list, p) -> list                                  [procedure]
        Sorts list according  to the  comparison procedure  p, using  an
        insert sort algorithm. insert_sort is non-copying.


flatlistify(list1) -> list2                                  [procedure]
        Given a  list list1,  whose  elements include  sub-lists  and/or
        vectors embedded  arbitrarily, flatlistify  will return  another
        list list2 in which every sub-list or vector is replaced by  the
        sequence of words  required to  compile it as  Pop-11 code  with
        pop11_compile. For example:

            vars x = [a [ b c { d e [ f ] g }] h];
            vars y = flatlistify(x);
            x =>
            ** [a [b c {d e [f] g}] h]
            y =>
            ** [a [ b c { d e [ f ] g } ] h]
            length(x) =>
            ** 3
            length(y) =>
            ** 14




---------------------------------------------
7  Generic Data Structure Procedures on Lists
---------------------------------------------

The  following   generic  data   structure  procedures   (described   in
REF * DATA) are applicable to a list list:

    length(list) -> N
        Same as listlength(list).

    explode(list) -> (item1, ..., itemN)
    (item1, item2, ..., itemN) -> explode(list)
        Applied to a list, explode is the same as dl.

    last(list) -> item
    item -> last(list)
        Returns or updates the last element  of list (which must not  be
        null).

    allbutfirst(N, list) -> sub_list
    allbutlast(N, list) -> sub_list
        Return the sublist consisting of all the elements of list except
        the first N (allbutfirst) or last N (allbutlast). In the case of
        allbutfirst  this  will  be  an  actual  sublist  of  list;  for
        allbutlast it will be a newly-constructed list.

datalength, appdata and fill treat lists as their first pair, i.e.  as a
data structure having two elements.




----------------
8  Miscellaneous
----------------

pair_key -> key                                               [constant]
nil_key -> key                                                [constant]
        Constants holding key structures for  pairs and the unique  item
        [] (see REF * KEYS).


assoc(list) -> assoc_p                                       [procedure]
        Creates a procedure assoc_p  encoding an association table.  The
        argument list  supplies initial  associations in  the form  of a
        list of  two element  lists.  assoc_p when  given an  item  will
        return its associated value, or false if there isn't one, i.e.

                assoc_p(item) -> value

        For anything but  very tiny association  tables, you should  use
        properties rather than this procedure - see REF * PROPS.


appassoc(assoc_p, p)                                         [procedure]
        Applies the  procedure  p  to  each  entry  in  the  association
        structure assoc_p (which must have  been created by assoc).  The
        procedure p is applied as:

            p(item, value)

        for each item/value association in assoc_p.

        For convenience, appassoc  can also  be used  on properties.  In
        this case, it is equivalent to calling appproperty.



--- C.all/ref/lists
--- Copyright University of Sussex 1994. All rights reserved.
