What is the relationship between unboxed types and strictness?

Question

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?

Busyness

I don't have much experience with unboxed types, so even basic remarks are welcome. – Busyness

Not every type would be unboxed, because of polymorphism. Polymorphic functions in OCaml and Haskell use a uniform representation of values as closures. Haskell allows specialization, generating custom functions that use unboxed arguments (OCaml probably does this too). – Markle

Answer 1

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:

_{(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).

Markle

So is there any use of a strict boxed type, like your List example? Doesn't it have the same representation as its lazy counterpart? – Suez

It has the same representation, but different semantics. Such structures are often useful. – Markle

But I thought, for example, data Pair = P Int Int will contain more indirections than data Pair = P !Int !Int. In the former, is each argument a pointer to a pointer (a thunk), and in the latter it is a pointer to a value? – Suez

Answer 2

Unboxed types are necessarily strict, but not all strict values are necessarily unboxed.

data Foo a = Foo !a !a

has two strict fields

data Bar a = Bar {-# UNPACK #-} !Int !a

has two strict fields, but the first one is unboxed.

Ultimately, the reason unboxed types are (necessarily) strict is there is no place to store the thunk as they are just flat, dumb data at that point.

Halfmoon

Answer 3

Arguments of any types can be made "strict", but the only unboxed types that have corresponding boxed types are Char#, Int#, Word#, Double# and Float#.

If you know low-level languages like C, it's easier to explain. Unboxed types are like int, double, etc., and the boxed types are like int*, double*, etc. When you've got an int, you already know the whole value as it's represented in the bit pattern, therefore, it is not lazy. It must be strict too, as all values of int are valid and not ⊥.

However, given an int* you may choose to dereference the pointer later to get the actual value (thus lazy), and it is possible to have invalid pointers (it contains ⊥, i.e. non-strict).

Epistemology