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. By contrast, unboxed arrays, like those of type UArray i e, are arrays of unboxed values. The layer of indirection which normally allows for separate lazy evaluation of the elements is missing. Consequently, such arrays consume much less space in overhead, however, there is a penalty to be paid in ease of use. The array's box now has code which determines the value of every element of the array as soon as it is forced. Thus, even a single lookup in the array will cause the entire array to be computed. If you were going to compute it anyway, you don't lose much. What you do lose however, is the ability to define the array elements recursively in terms of one another. The following definition works for boxed array types, but not unboxed ones: a = array (0,20000) $ (0,0):(1,1):[(i, a ! (i-1) + a ! (i-2)) | i <- [2..20000]] Further, you restrict yourself to only a small collection of possible element types which have a compact unboxed representation. A list of these in the case of UArray is available in the documentation for Data.Array.Unboxed. One paper which might be of interest is the one located at http://citeseer.ist.psu.edu/peytonjones92implementing.html which describes the Spineless Tagless G-machine, a low-level mechanism used to implement Haskell code by GHC. Hope this helps, - Cale On 09/12/05, John Velman <velman@cox.net> wrote:
I've tried google and google scholar, wikipedia, and planetMath. Can't find a description. Can someone point me to a freely available reference?
Thanks,
John Velman
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe