haskelllazy-evaluationevaluationstrictness

What is the relationship between unboxed types and strictness?

Unboxed types, like Int#, and strict functions, like f (!x) = ..., are something different, but I see conceptual similarity - they disallow thunks/laziness in some way. If Haskell was a strict language like Ocaml, every function would be strict and every type unboxed. What is the relationship between unboxed types and enforcing strictness?

Solution

  • Unboxed vs Boxed Data

    To support parametric polymorphism and laziness, by default Haskell data types are represented uniformly as a pointer to a closure on the heap, with a structure like this:

    alt text
    (source: haskell.org)

    These are "boxed" values. An unboxed object is represented by the value itself directly, without any indirection or closure. Int is boxed, but Int# is unboxed.

    Lazy values require a boxed representation. Strict values do not: they can represented either as fully evaluated closures on the heap, or as primitive unboxed structures. Note that pointer tagging is an optimization that we can use on boxed objects, to encode the constructor in the pointer to the closure.

    The Relationship to Strictness

    Normally, unboxed values are generated in an ad hoc fashion by functional language compilers. In Haskell, however, unboxed values are special. They:

    1. they have a different kind, #;
    2. can only be used in special places; and
    3. they're unlifted, so are not represented as a pointer to a heap value.

    Because they are unlifted they are necessarily strict. The representation of laziness is not possible.

    So particular unboxed types, like Int#, Double#, really are represented just as double or int on the machine (in C notation).

    Strictness Analysis

    Separately, GHC does strictness analysis of regular Haskell types. If a value's use is found to be strict – i.e. it can never be 'undefined' – the optimizer might replace all uses of the regular type (e.g. Int) with an unboxed one (Int#), since it knows that the use of Int is always strict, and thus replacement with the more efficient (and always strict) type Int# is safe.

    We can of course have strict types without unboxed types, for example, an element-strict polymorphic list:

    data List a = Empty | Cons !a (List a)

    is strict in its elements, but does not represent them as unboxed values.

    This also points out the mistake you made about strict languages, like OCaml. They still need to support polymorphism, so either they provide a uniform representation, or they specialize data types and functions to every type. GHC by default uses uniform representation, as does OCaml, though GHC can also specialize types and functions now (like C++ templates).