• Ali Cehreli (73/73) Nov 06 2009 D's slices have "discretionary sharing semantics"

Ali Cehreli <acehreli yahoo.com> writes:

D's slices have "discretionary sharing semantics"

This is a request for comment in defining the *existing* semantics of D's
arrays. I might have gotten a number of things wrong and appreciate your
comments.

Being a C++ programmer, and a relative D newbie, I've found it difficult to
wrap my head around D's arrays. The following is the way of describing their
semantics that makes me finally understand them.

There are two types of arrays in D:

1) Fixed-sized arrays: These have value semantics; they own their data and are
copied when assigned (even as function parameters as of dmd 2.036). They are
quite different and powerful from C's arrays and are very easy to understand.

2) "The other type of arrays": They do not own any elements; the elements that
they provide access to are owned by something else: the elements might be owned
by e.g. a fixed array or the garbage collector.

This type has "discretionary sharing" semantics (I like the term "ad-lib
sharing" as well, but the word that begins with a 'D' has more potential ;) )

The problem so far has been with the second type. The names "dynamic array" and
"slice" have been used but neither term helped me. I found none of those names
nor their definitions to be adequate to describe what they are.

First, they are not really "arrays" because they don't own their elements; they
actually "share consecutive elements" that are owned by something else.

Second, they are not "slices" in the way slices are commonly described. For
example, Wikipedia's definition contains "array slicing is an operation that
extracts certain elements from an array and packages them as another array."
D's dynamic arrays or slices don't fit this definition.

The distinction between "dynamic array" and "slice" has been very confusing
too. Aren't they the same thing? I will use "slice" from now on...

D's slices have "discretionary sharing semantics." When copied, they start
sharing elements but they never own the elements themselves. The sharing is
discretionary, because any slice

- may start sharing additional elements without breaking its existing sharing
contracts, or

- may drop their sharing contracts, and start sharing new elements

Assignment (including copying to functions) of slices do not "assign," but
start a discretionary sharing contract, which may be broken by either of the
parties.

I will try to express these semantics by modifying Table 4.3 of Andrei's
chapter on arrays. (I've also removed some text for brevity.)

(I've formatted the table to fit a 70 character wide window.)

Legend:
* - Modification to Andrei's table
X - Operations that may break the sharing contract

Name             Type   X * Description
-----------------------------------------
new T[n]         T[]      * Creates n consecutive elements and
                            returns a slice that shares those elements

[t1, . . ., tk]  T[]      * Creates k consecutive elements and
                            returns a slice that shares those
                            elements

a=b              T[]      * Copies slice to slice (a starts sharing
                            the same elements as b has been sharing)

a[‹e ›]          ref T      Accesses element by index

a[‹e1›..‹e2›]    T[]      * Returns a slice that shares some of a's
                            elements

a[]              T[]        Participate in array-wise expressions
                            otherwise just the identity operation
                            a[0 .. $]

a.dup            T[]      * Creates copies of elements that 'a' shares
                            and returns a slice that shares the new
                            elements

a.length         size_t     Reads slice's length

a.length = n     size_t X * Changes the number of elements that 'a'
                            shares; may share less of what is already
                            being shared, or may share newly created
                            elements that are the concatenation of
                            the existing elements that 'a' has been
                            sharing and new ones with the value T.init

a is b           bool     * Compares whether the slices share the same
                            elements

a !is b          bool       Same as !(a is b)

a == b           bool       Compares slices for element-for-element
                            equality

a != b           bool       Same as !(a == b)

a~t              T[]    X * Creates new elements by concatenating the
                            elements that the slice has been sharing
                            and the new element; returns a slice that
                            shares all of the new elements

t~a              T[]    X * Creates new consecutive elements by
                            concatenating the new element and the
                            elements that the slice has been sharing;
                            returns a slice that shares all of the
                            new elements

a~b              T[]    X * Creates new consecutive elements by
                            concatenating the elements that each
                            slice has been sharing; returns a new
                            slice that shares all of the new elements

a ~= t           T[]    X * Appends a new element to the elements
                            that the slice has been sharing

a ~= b           T[]    X * Appends the elements that 'b' has been
                            sharing to the elements that 'a' has been
                            sharing; 'a' starts sharing all of those
                            elements

a.ptr            T*         The address of a's first element (unsafe)


Does this make sense?

Ali