[Haskell-cafe] Byte Histogram

[wren ng thornton]

On 2/8/11 6:00 AM, Ketil Malde wrote:
>> This does seem a bit excessive. As a start, I don't remember anyone
>> asking for control over (un)boxedness, so hopefully we could jettison
>> that part of it?
>
> Uh, you mean like in IOUArrays, the UNPACK pragma, or
> -funbox-strict-fields?  Unboxing is an important optimization, but
> perhaps the current feature set suffices.

As another issue to bear in mind, there is a big difference between 
strict types and unpointed types (either as types themselves, or as 
function spaces).

Semantically we have lots of reasons for wanting unpointed types--- that 
is, types which do not have bottom as an inhabitant. And it is clear 
that pointed and unpointed versions are different types[1]. One of the 
major issues looming here is the fact that unpointed types may not form 
domains, wreaks havoc for the domain theory semantics people often use 
for laziness. But at the same time, removing bottom can make it much 
easier to reason about things.

Strict types are, semantically, the same as unpointed types. And since 
Haskell is non-total, strict types are the only possible exact 
implementation of unpointed types (though decent type-checkable 
approximations may exist). However, operationally, strict types and 
unpointed types are quite different. In strict types we know that the 
value has been evaluated to WHNF (or some other normal form) and 
therefore we can avoid the computational cost of checking to ensure that 
it's been evaluated. Whereas unpointed types may not have been evaluated 
already, we simply know that when we do evaluate them we won't get 
bottom. Thus, unpointed types can allow us to have our laziness and... 
er, eat it too.

The arguments for having unpointed types (as opposed to strict types) 
are the same as the arguments for having laziness in the first place. 
Conversely, the arguments for having strict types (as opposed to 
unpointed types) are the same as the arguments for having strictness 
annotations of any kind. Both have their place, but we should be clear 
about what our goals are before choosing one or the other. Personally 
I'd like to have both, because they fill different needs, and because 
it's easy to automate the conversion between them[2].


[1] Though conversion between them is easy. From unpointed to pointed is 
just a forgetful functor; from pointed to unpointed is the monad of 
evaluation.

[2] Functions of strict arguments can be lifted to functions of 
unpointed arguments by simple wrappers to force argument evaluation. 
With strictness analysis, it can be possible to optimize the wrapper 
away and to call the strict-typed version directly. This is sort of like 
the SPECIALIZE pragmas.

We can also lift functions of unpointed arguments into functions of 
pointed arguments by changing the return type of the function to allow 
for bottom to be returned. Note that this requires that we distinguish 
pointed and unpointed types, not just pointed and unpointed function 
spaces. This is a natural consequence of the fact that evaluation is a 
monad, but it makes things get really hairy really quickly. Then again, 
that complexity may be unavoidable since we'd like to be able to have 
functions return strict and unpointed values just like they can return 
unboxed values.

-- 
Live well,
~wren