[Haskell] Question for the haskell implementors: Arrays, unsafePerformIO, runST

[John Meacham]

So, I finally decided that jhc needs real arrays, but am running into an
issue and was wondering how other compilers solve it, or if there is a
general accepted way to do so.

here is what I have so far

> -- The opaque internal array type
> data Array__ a
>
> -- the array transformer quasi-monad
> newtype AT a = AT (Array__ -> Array__)
>
> seqAT__ :: AT a -> AT a -> AT a
> seqAT__ (AT a1) (AT a2) = AT $ \a -> a2 (a1 a)
>
> doneAT__ :: AT a
> doneAT__ = AT id
>
> newAT__ :: Int -> AT a -> Array__ a
> newAT__ n (AT a1) = a1 (prim_newAT__ n)
>
> writeAT__ :: Int -> a -> AT a
> writeAT__ i x = AT $ \a -> prim_writeAT__ i x a
>
> -- none of these routines have run-time checks
> foreign import primitive "prim_newAT__" :: Int -> Array__
> -- performs *update-in-place*
> foreign import primitive "prim_writeAT__" :: Int -> a -> Array__ -> Array__
> foreign import primitive "unsafeAt__" :: Array__ a -> Int -> a
>
> -- example use
> newArray :: [a] -> Array__ a
> newArray xs = newAT__ (length as) $ foldr assign doneAT (zip [0..] xs) where
>     assign (i,v) rs = writeAT__ i v `seqAT__` rs


now, the problem occurs in newAT__

> newAT__ :: Int -> AT a -> Array__ a
> newAT__ n (AT a1) = a1 (prim_newAT__ n)
                            ^ this gets floated out as a CAF.

it all seems good, but the call to (prim_newAT__ n) is a constant and
hence gets pulled to the top level and all arrays end up being the same
array! this is no good. I always knew in the back of my mind that
'unsafePerformIO' had the same problem, but sort of punted solving it
since unsafePerformIO is not really used in any critical paths. However,
it pretty much fundamentally breaks arrays!

I imagine the same issue would arise with runST.

so, any idea how to solve it? I could brute force it and make the
compiler recognize calles to prim_newAT__ as special, but I really don't
like that idea. it is hard to guarentee such things across all possible
optimizations and I'd like a general solution rather than hardcoding a
bunch of routines as special.




So far, my best idea though I don't know if it will work is adding a
primitive:

> foreign import primitive "prim_newWorld__" :: forall a . a -> World__

which will throw away its argument and produce a World__. but since it
is primtive, the compiler will assume the world it returns might depend
on its argument. then I could do something like:

> foreign import primitive "prim_newAT__" :: World__ -> Int -> Array__

> newAT__ :: Int -> AT a -> Array__ a
> newAT__ n (AT a1) = a1 (prim_newAT__ (prim_newWorld__ a1) n)

so the initial call to newAT__ now depends on the array transformer and
can't be floated out as a CAF.

I have reduced several magic primitives to just one, the world creation
one. but I am still not sure how happy I am about it and wanted to know
what other compilers did.


        John


--
John Meacham - ⑆repetae.net⑆john⑈