Changes between Version 24 and Version 25 of ArrayTasklist

Show
Ignore:
Timestamp:
02/05/10 00:13:12 (12 years ago)
Author:
kurahaupo
Comment:

Add "invariant array" section. Remove deprecation of "Array" as it's been done

Legend:

Unmodified
Added
Removed
Modified

  • ArrayTasklist

    v24 v25  
    2424     * ''(No, it's "random". ResizableBooleanArray does accept negative indeces, while ResizableIntegerArray does not.)'' 
    2525 
    26 == Fixed Arrays == 
    27  
    28  * Should fixed-sized arrays support push, pop, shift and unshift? 
    29    * ''(probably not)'' 
    30  
    31  * Should there be special cases for very small arrays, such that no separate memory block is needed? These could be useful to implement vectors in mathematical operations, and tuples generally. 
    32  
    33  * Should fixed-sized arrays automatically become resizable arrays when resizing operations are attempted? 
    34    * ''(maybe)'' 
    35  
    3626== Resizable Arrays == 
    3727 
    … …  
    5242 
    5343 * My dictionaries can't agree whether the spelling is "resizable" or "resizeable"; if the latter, should we fix the spelling now, later, or never? 
     44 
     45== Fixed-sized Arrays == #FixedArrays 
     46 
     47 * Should fixed-sized arrays support push, pop, shift, unshift, splice and resize? 
     48   * ''(probably not)'' 
     49 * If so, should they automatically be mutated into the corresponding resizable type when these operations are attempted? 
     50   * ''(probably)'' 
     51 * Should there be special cases for very small arrays, such that no separate memory block is needed? These could be useful to implement vectors in mathematical operations, and tuples generally. 
     52 
     53== Invariant Arrays == 
     54 
     55Invariant arrays are one way to implement the notion of "an array as a (composite) value" rather than "an array as a container". Optimizing for this case brings huge benefits to single-assignment languages. 
     56 
     57Invariant arrays are effectively a special case of fixed-sized arrays, only more stringent: not only is the array structure fixed, but the values of the elements within it are also fixed. Operations such as shift, unshift, push, pop, splice, resize and replace-element would work, if at all, by generating a new array, rather than altering the old one. This is easy to support for native types (Integer, Float & String) but would require additional support for invariance within PMCs. 
     58 
     59An good implementation would probably need: 
     60 * A "write only" flag, for arrays that are under construction 
     61 * A wrapper "container" PMC that simply references its corresponding "value" PMC 
     62 * A "radix tree" approach to storage, to avoid excessively heavy copying when generating new arrays as a result of the usual mutator methods 
     63 
     64''(What else? Any other thoughts?)'' 
    5465 
    5566== Universal Ancestral "Array" == #ArrayAncestor 
    … …  
    8798 * Array types should grow by powers of two (or multiples of system page size for large arrays) for improved allocation performance 
    8899   * (they already do -- kurahaupo) 
    89  * Deprecate and remove Array PMC type. 
    90  
    91100 * The current implementations of resizable array PMC's are derived from fixed-sized array PMC's. However the (current) use of the "size" field -- provided by the base PMC -- is arguably incorrect, in that it does not track the allocated size as it would for the fixed-sized version. Instead of changing the meaning of "size" in the base PMC, we should call it "allocated_size", and then in the derived PMC have "logical_size". This means that the memory-safety of the "allocated_size" bound is then implemented only once, within the base PMC. 
    92101