ISSUE: Collection allocation

REVISION HISTORY: Rob MacLachlan, 18 February 94

STATUS:  open

RELATED ISSUES:

CATEGORY: change and clarification


PROBLEM DESCRIPTION:

The Dylan book is very unclear about when results can share structure and when
arguments can be destroyed.  The book says nothing about what it means to
share structure or destructively modify.

Definitions:
 -- The contents of a collection are the key-value pairs stored in the
    collection.  The contents are said to be altered when:
      - The ordering of the pairs changes (if the collection defines
      	ordering),
      - Keys are added or removed (according to the collection's key test.)
      - The value of a key (according to the key test) changes (as tested by
        ID?)

 -- A collection is fresh if modification of any pre-existing collection's
    contents can never modify the contents of the fresh collection, and
    symmetrically, modifying a fresh collection will never modify the contents
    of any pre-existing collection.  Immutable collections can't be modified,
    so a fresh immutable result can share structure with other immutable
    collections.  For example (given that <pair> is mutable) if we say that
    the result of list is fresh, then we guarantee that:
        id?(list(1), list(1))  =>  #f

 -- A function destructively modifies its argument if calling the function
    could affect the contents of the argument collection.

Status quo:
    map, map-as, copy-sequence, list, vector, shallow-copy
        Creates a new collection
        Sharing illogical, but not explicitly disallowed
        Destruction unspecified (presumably illegal)

    add, add-new, remove, remove-duplicates
        Returns a new sequence
        "May share no structure" [must not share structure]
        Argument explicitly unmodified

    add!, add-new!, remove!, remove-duplicates!, reverse!, sort!
        Result may or may not be ID?
        Result may share structure.
        Argument is destructively modified

    choose, choose-by, concatenate-as, concatenate, reverse, sort, as
        Returns a new sequence
        Sharing unspecified
        Destruction unspecified (presumably illegal)

    intersection, union
        Returns a new sequence
        Sharing explicitly allowed
        Destruction unspecified (presumably illegal)

    ...-setter, pop, pop-last
        Don't return the altered collection
        Destruction required

    push, push-last
        Result must be ID?
        Sharing required
        Destruction required

    pair
        Creates a new pair
        Sharing allowed
        Destruction unspecified (presumably illegal)


PROBLEM 1: Many functions don't say they aren't destructive.
PROPOSAL 1:
    Clarify that unless explicitly documented to do so, functions don't
    destructively modify their arguments.


PROBLEM 2: 
    Sharing is unspecified for some functions which should have a fresh
    result.

PROPOSAL 2:
    Clarify that MAP, MAP-AS, COPY-SEQUENCE, LIST and VECTOR allocate a fresh
    result sequence.  Clarify that PAIR creates a fresh pair with a shared
    tail.


PROBLEM 3: 
    There is no consistent usage of the ! convention.

PROPOSAL 3:
    Document that the ! convention is used when function returns a
    destructively modified version of the argument (and thus might possibly be
    confused with a non-destructive function.)  Destructive functions that
    return other values (like -setter functions and pop) don't need to use the
    ! convention.  ! isn't a universal warning that an operation is
    destructive --- it is a naming convention that is primarily used when
    destructive and non-destructive functions both exist or when a destructive
    function needs to return a potentially non-EQ result value.

    Change push and push-last to return the pushed value (not the
    destructively modified collection.)


PROBLEM 4:
    There is gratuitous variation in the permission to share.

PROPOSAL 4:
    -- Change add, add-new, remove and remove-duplicates to say that the
       result might not be fresh.
    -- Clarify that the result of choose, choose-by, concatenate-as,
       concatenate, reverse, sort and "as" might not be fresh. 


RATIONALE:

These proposals clarify what sharing relationships exist and reduce the number
of different sharing/destruction policies.

    map, map-as, copy-sequence, list, vector, pair, shallow-copy
        Result is fresh to a specified degree:
          -- For pair, the pair is fresh.
          -- For shallow-copy, the fresh portion is defined by the actual
             method.  The collection method returns a fresh collection.
          -- The other listed functions return a fresh collection.
        Destruction forbidden

    add, add-new, remove, remove-duplicates, choose, choose-by, concatenate-as,
    concatenate, reverse, sort, intersection, union, as
        Possible non-fresh result
        Destruction forbidden

    add!, add-new!, remove!, remove-duplicates!, reverse!, sort!
        Possible non-fresh result
        Result may or may not be ID?
        Destruction allowed

    ...-setter, pop, pop-last, push, push-last
        Don't return the altered collection
        Destruction required


EXAMPLES:

COST TO IMPLEMENTORS:
    Existing collection implementations would need several small changes.

COST TO USERS:
    Allowing non-fresh results for add, add-new and remove could possibly
    result in more frequent bad interactions with destructive operations.

PERFORMANCE IMPACT:
    Consistently allowing non-fresh results allows important optimizations for
    lists.  Clarifying that immutable results are always fresh eliminates any
    need to spuriously copy immutable collections.

BENEFITS:
    Simpler and more consistent approach to allocation and destruction.
    Improved efficiency.

AESTHETICS:
    Allowing non-fresh results allows non-destructive programming to be more
    efficient.

FUTURE FEATURES: Allows for standard immutable collections