Compact Normal Form and ST

[Edward Z. Yang]

There are two senses of referential transparency here which should be
considered.  First is whether or not you will get the same value results
if you use the compact functionality in ST.  Here, the answer is yes.
Compact normal form has very trivial semantics in this domain, and
it would have been OK even to make compact normal forms be pure
functions.

Second is whether or not the performance characteristics are preserved.
Here, the situation is different.  Most notably, pure expressions and
invocations of the same runST block may be commoned up (via an
optimization pass like CSE.)  In that case, what was previously two
separate compact blocks may be commoned up into a single one.  This
could be disaster if you were planning to use these blocks as separate
allocation buffers for subsequent modifications.

This motivated specializing compact to IO.  It won't segfault if you
put it in ST, but the performance characteristics might change.

Edward

Excerpts from Andrew Martin's message of 2017-06-18 10:24:09 -0400:
> In the primops file where the compact normal form functions are
> documented (https://github.com/ghc/ghc/blob/adcd1c62b6d372f100ccf1d5d7cd94f79aaac194/compiler/prelude/primops.txt.pp#L2487),
> I noticed that all of the functions have type signatures that constrain
> them to only being used in IO. For example:
> 
>     compactAdd# :: Compact# -> a -> State# RealWorld -> (# State# RealWorld, a #)
> 
> I would like to know if generalizing these to allow them to work in ST would
> be sound. That is, changing the type signature to:
> 
>     compactAdd# :: Compact# -> a -> State# s -> (# State# s, a #)
> 
> I'm not requesting that this change actually be made. I only want to
> know if using unsafeCoerce to create the second function for my own
> project would actually be sound.
> 
> For those interested in knowing why I want this, it's because there are
> situation where I'm interested in building up a giant structure in a
> compact region, but in a way that doesn't actually require IO. I think
> it's a pity to have to use a type signature with IO and then call
> unsafePerformIO at the end instead of using the more constrained ST,
> and runST, which makes it clear that I'm not doing anything observable
> form the outside.
> 
> As a minor bonus, the ST version of the Compact data type shouldn't need
> the lock that the IO version does, since concurrent calls to compactAdd
> are not possible.
> 
> -Andrew Martin
>