More on Constructors/Selectors:

     - Atoms, empty, and cons form a constructor system.  First, rest,
       and empty? form it companion selector system.  empty? checks an
       empty bit that is actually part of a list, and thus empty? is a
       method of accessing it, like first and rest.

     - Other operations exist, but they are conveniences and aren't part
       of the basic functionality.  The operations listed above are the
       fundamental constructor/selector system.


Abstract Data Types:

     - An abstract data type is a definition of structural qualities of
       a data representation, but does not deal with specific
       implemation details, such as bit layout.  It a programming
       strategy for implementation, and does not define specific tactics
       for implementation.

     - An abstraction barrier is the limit of tactical options resulting
       from working within an abstract data type.


       e.g. integer list:

       The integer list abstract data type will contain the following
       functions: 

       empty_intlist 
           the empty list

       (singleton_intlist int) 
	   returns a list containing the single integer int

       (concatenate_intlists intlist1 intlist2) 
           returns a list consisting of the elements of intlist1 in
           order followed by the elements of intlist2 in order 

       (reverse_intlist intlist) 
	   returns a list consisting of the elements of intlist in the
	   reverse order. 

       (empty_intlist? intlist) 
           returns #t if intlist is empty, #f otherwise

       (head_intlist intlist) 
           returns the first element of intlist, if there is one (if
           not, it can do anything) 

       (tail_intlist intlist) 
           returns an intlist containing everything but the first
           element of intlist, if there is a first element (if not, it
           can do anything)   


       See the DEMO for the definitions for these functions using a
       structure based around the list system.


       Now, the concatenate_intlists and reverse_intlist functions
       defined in the way specified in the DEMO may be too inefficient
       for a particular implementation.  So implementing a different
       approach may be appropriate. Such an approach is described below:


       Consider the binary tree representation of a integer list


                   /\
                  /  \
                 /    \
                /      \           where list elements are read off
               /\      /\          from left to right
              /  \    /  \
             /    \  /    \
             1    2 /      5
                   /\
                  /  \
                 /    \
                3      4

       This tree structure is not capable of representing lists of
       lists, but is sufficient for representing a list of integers.

       The revised functions that use this binary tree representation
       are defined in the second DEMO file.  Some of the changes include:

       singleton_intlist:  now just returns the input integer (i.e. not
                           a list)

       concatenate_intlist:  simply does a cons of the two intlists, not
                             a recursive construction


       Note that concatenate_intlist used in the binary tree DEMO is
       slightly more complicated than the one used in class.  This one
       simplifies some of the other functions, and makes the program
       look nicer.  Still, conditionals are quite costly on modern
       computers, and it probably isn't a good step is speed is
       important.


       Also follow the link to last year's assignment #4.  The intlist
       ADT is discussed in more detail there.