[Haskell-cafe] What is a Boxed Array?

Tomasz Zielonka tomasz.zielonka at gmail.com
Fri Dec 9 17:04:56 EST 2005


On Fri, Dec 09, 2005 at 02:29:33PM -0500, Cale Gibbard wrote:
> A "box" is a cell representing some value in a program. It generally
> contains a pointer to code (a thunk), or to a proper value. When
> evaluation of that box is forced for the first time, the code
> executes, and when it is done, it updates the pointer with a pointer
> to the result value. There are a number of slight variations on this
> scheme, but essentially the idea is that there is a layer of
> indirection which keeps track of whether the value has been evaluated
> yet or not. This sort of thing forms a major role in the
> implementation of a lazy language like Haskell.
> 
> Ordinary Arrays in Haskell, say, Array i e for some index type i, and
> element type e, are arrays of boxed values. That is, each element of
> the array is a pointer to either code, or a value, and each may be
> evaluated separately and lazily.

I just want to add that many strict languages also have a distinction
between boxed and unboxed arrays (or offer only boxed arrays), because
there are other reasons to box values besides implementing laziness,
like for simplifying the memory model (which can simplify GC
implementation), allowing to intermix values of different types
(different kinds of polymorphism) or allow variable sized values (think
strings, arrays and arbitrary size integers).

Some concrete examples: Arrays in many scripting languages, like Python,
are often boxed. There are some languages, like R, where there are many
types of unboxed arrays, for efficiency reasons.

The situation in OCaml is a bit more complicated - standard arrays are
boxed in general, the tagged 31bit int hack makes them unboxed for ints,
and arrays of doubles are unboxed as an exception - IIUC in some cases
this requires a runtime check, for example in non-inlined functions
which are polymorphic on the type of array elements.

Best regards
Tomasz

-- 
I am searching for a programmer who is good at least in some of
[Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland


More information about the Haskell-Cafe mailing list