[GHC] #14196: Replace ArrayArray# with either UnliftedArray# or Array#

[GHC]

#14196: Replace ArrayArray# with either UnliftedArray# or Array#
-------------------------------------+-------------------------------------
           Reporter:  andrewthad     |             Owner:  (none)
               Type:  feature        |            Status:  new
  request                            |
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.2.1
           Keywords:                 |  Operating System:  Unknown/Multiple
  LevityPolymorphism                 |
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 Just to be clear, there currently is nothing named `UnliftedArray#`. I
 would like to propose that such a thing possibly be added, with the long-
 term goal of deprecating and removing `ArrayArray#`. The interface for it
 would look like this:

 {{{#!hs
 data UnliftedArray# (a :: TYPE 'UnliftedRep)
 data MutableUnliftedArray# s (a :: TYPE 'UnliftedRep)

 indexUnliftedArray# :: forall (a :: TYPE 'UnliftedRep). UnliftedArray# a
 -> Int# -> a
 writeUnliftedArray# :: forall (a :: TYPE 'UnliftedRep).
 MutableUnliftedArray# s a -> Int# -> a -> State# s -> State# s
 readUnliftedArray# :: forall (a :: TYPE 'UnliftedRep).
 MutableUnliftedArray# s a -> Int# -> State# s -> (# State# s, a #)
 unsafeFreezeUnliftedArray# :: forall (a :: TYPE 'UnliftedRep).
 MutableUnliftedArray# s a -> State# s -> (#State# s, UnliftedArray# a#)
 newUnliftedArray# :: forall (a :: TYPE 'UnliftedRep). Int# -> a -> State#
 s -> (# State# s, MutableUnliftedArray# s a #)
 }}}

 You would also have a few other things like `sameMutableUnliftedArray#`,
 `sizeofMutableArray#`, `unsafeThawUnliftedArray#`, `copyUnliftedArray#`,
 etc. The main difficulty that I see in doing this is that I'm not sure if
 you can tell a primop that it takes a polymorphic argument whose kind is
 something other than `TYPE LiftedRep`. The bodies of all of the functions
 I listed above could simply be copied from the `ArrayArray#` functions.

 There are a few alternatives I've heard discussed. One is to make `Array#`
 accepted both boxed or unboxed types. There is a brief discussion of this
 in the UnliftedDataTypes proposal [#point0 (0)]. Indeed, it appears that
 some have managed to smuggle unlifted data into `Array#` already, with the
 caveats one would expect [#point1 (1)]. This interface would look like:

 {{{#!hs
 data Array# (a :: TYPE k)
 data MutableArray# s (a :: TYPE k)
 indexArray# :: Array# a -> Int -> a -- same as before
 indexUnliftedArray# :: forall (a :: TYPE UnliftedRep). Array# a -> Int ->
 a
 }}}

 So instead of having `Array#` and `UnliftedArray#` as separate data types,
 we could have `Array#` handle both cases, but we would need to make a
 duplicate of every function that operates on `Array#`. This follows all of
 the appropriate rules for when levity polymorphism is allowed, and it
 should be backwards-compatible with the previous non-levity-polymorphic
 definition of `Array#`. I'm not sure how many things in the GHC runtime
 assume that the values inside an array are lifted, so this might cause a
 bunch of problems. If it is possible, this approach would be kind of neat
 because then `SmallArray#` could be similarly adapted.

 Anyway, I just wanted to get this out there. I would be happy to try
 implementing the first proposal (involving `UnliftedArray#`) at some point
 in the next six months. Any feedback on the idea would be appreciated.
 Also, any comments on how appropriate this is for someone new to
 contributing to GHC would be appreciated as well. Thanks.

 * [=#point0 (0)]
 https://ghc.haskell.org/trac/ghc/wiki/UnliftedDataTypes#Parametricity
 * [=#point0 (1)]
 https://www.reddit.com/r/haskell/comments/6v9rmg/an_unified_array_interface/dlyph4i/

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14196>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler