[Haskell-cafe] Mutable arrays

[Don Stewart]

jeff1.61803:
>    On Feb 6, 2008 1:18 AM, Jonathan Cast <[1]jonathanccast at fastmail.fm>
>    wrote:
> 
>      On 5 Feb 2008, at 10:14 PM, Jeff I* wrote:
> 
>        On Feb 5, 2008 4:58 PM, ChaddaA- FouchA(c)
>        <[2]chaddai.fouche at gmail.com> wrote:
> 
>          2008/2/5, Jeff I* <[3]jeff1.61803 at gmail.com>:
>          > This is interesting.  I've been programming in Concurrent Clean
>          for a while.
>          >  Instead of monads, Clean supports unique types for mutable arrays
>          and IO.
>          > In Clean, I can write code that iterates through a mutable array
>          by
>          > converting it to a lazy list.  This is convenient because I can
>          use all the
>          > nice list processing functions that are available.
>          >
> 
>          You could absolutely write something like that in Haskell, but as
>          some
>          have pointed out, this is probably _not a Good Idea_, even though it
>          works in your particular case, the array could be modified between
>          the
>          time you get the lazy list and the time you actually read it... And
>          there's no way to insure it's not happening in Haskell, and I
>          strongly
>          doubt there is in Concurrent Clean, could you confirm ?
> 
>        Concurrent Clean can handle this in a safe way.  Here's a code snippet
>        for normalize_2D_ary from ArrayTest.icl:
>        
>        uToList_2D :: *(a u:(b c)) -> (.[c],*(a u:(b c))) | Array a (b c) &
>        Array b c
>        map_in_place_2d_arr :: (a -> a) *(b *(c a)) -> *(b *(c a)) | Array b
>        (c a) & Array c a
>        normalize_2D_ary :: *(a *(b c)) -> *(a *(b c)) | Array a (b c) & Array
>        b c & / c & Ord c
>        normalize_2D_ary ary =
>            let (lst,ary2) = uToList_2D ary
>                max_elem = foldl1 max lst
>            in  map_in_place_2d_arr (\ x -> x / max_elem) ary2
>        uToList_2D takes a unique array, ary, and returns a tuple containing a
>        list of the array elements and a "new" array, ary2.  uToList_2D does
>        not modify ary, but Clean's type system forces any function that
>        accesses a unique array to thread the array through and return a "new"
>        array.  Under the hood the "new" array actually uses the same memory
>        storage as the original array.  So, it is effecient.  Threading the
>        array serializes access insuring the array won't be modified until
>        the list is complete.
> 
>      I'm confused --- does uToList_2D return the head of the list before or
>      after it finishes reading the array?  If before, then I don't see how
>      the type system prevents me from modifying the array before I finish
>      examining the list, as you claim.  If after, then the list isn't truly
>      lazy.
> 
>    
>    uToList_2D can return the head of the list before it finishes reading the
>    array.  I could modify the code so that it is ambiguous whether the array
>    is modified before the list processing is finished.
>    
>    normalize_2D_ary ary =
>        let (lst,ary2) = uToList_2D ary
>            max_elem = foldl1 max lst
>         in  map_in_place_2d_arr (\ x -> x / max_elem) ary  // I changed ary2
>    to ary
>    
>    However, the type system will generate an error with this code because
>    ary is no longer unique because it is referenced in two expressions. 
>    Clean produces this error message:
>    
>    Uniqueness error [ArrayTest.icl,55,normalize_2D_ary]: "ary" demanded
>    attribute cannot be offered by shared object
>    
>    I should mention that a problem with the code I've shown is that it is
>    very sensitive to the order in which the expression graph is evaluated. 
>    Simple changes can cause lst to become strict and the program to run out
>    of heap.
>    By the way, Clean has it's share of rough edges.  The reason I'm hanging
>    out on Haskell-Cafe is because I'm trying to get away from those rough
>    edges.  But, I am missing Clean's uniqueness types.  I'm starting to
>    see Haskell's unsafe functions as a blunt work around that could be fixed
>    elegantly and safely by implementing uniqueness types.

That's a reasonable critique : its hard to enforce uniqueness, in the
type system in Haskell, -- I'd be interesting to see approaches that
avoid extending the compiler.

-- Don