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⑈
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
