Why is `Box` called `Box`?

A question 110% on the etymology of the name of this type.
Where did the primary heap-pointer-type get the name "Box"?

Many/ most other standard library types sound (to me) like "what I'd expect you to expect" -

  • Essentially all of the container-structures (Vec, HashMap, HashSet, array, etc.)
  • Central traits like Clone, Copy, Display
  • Rc, Arc (essentially de-capitalized acronyms)

But where did "Box" as the name of the primary heap-pointer come from?

1 Like

I believe that comes from this terminology:

9 Likes

"Boxing" and "boxed value" are general terms also used by other languages, e.g. see this:

4 Likes

Based on a quick search the earliest reference to "box" I could find in the rust history is in src/test/run-pass/box-unbox.rs of Calculate size of parametric types in exterior slots in deref_slot so… · graydon/rust-prehistory@733aa31 · GitHub.

3 Likes

I know Haskell speaks about boxed and unboxed types 6.16. Unboxed types and primitive operations — Glasgow Haskell Compiler 9.2.1 User's Guide, and I could – unsurprisingly – find the term in ocaml docs, as well: OCaml - Interfacing C with OCaml.

Given that Rust was first implemented in ocaml, it’d not surprising to me that this termonology of “boxing” values meaning to “put them in an allocation on the heap” was had the change to (and as we know happend to) get adapted for Rust, too.

The ownership considerations about Box<T> are of course new; but given that in existing languages “boxing” also usually implied that the type – mostly – only differed in whether or not it’s put behind an additional indirection onto the heap, compared to any unboxed counterparts, it makes sense that Box<T> in Rust has the same ownership requirements/properties as T does.


One meaning that didn’t get adapted (yet) is the usual implication in OOP languages, but also in Haskell (I don’t know Ocaml well enough) that a “boxed” type can fit into some uniform dynamic representation scheme of values. I.e., as the Wikipedia article linked above points out, in Java, you use “boxed integers” to get ordinary objects that can be used in generic datatypes; similarly in Haskell, while it is (unlike Java) quite strictly statically typed, generic functions still work with dynamic function calls, and are not monomorphized. The fact that when working with Box<T> in Rust, you still always monomorphize your functions over T means that in that aspect Box in Rust is somewhat different from “boxing” in other languages.

I do suppose that if Rust ever gets any support for opting out of monomorphization for certain forms of generic functions, then handling types through an indirection, options including Box<T>, could become necessary for such functions; handling a Box<T> with arbitrary T uniformly – without monomorphization – is actually quite straightforward; and even trait bounds can work through dictionary-passing, which is the approach that Haskell (the original language where Rust’s trait system mostly came from) uses. For comparison, note that Rust’s current support for dynamic function calls is a bit more inflexible: Using trait objects is a combined approach of dictionary-passing and type erasure; e.g. in Haskell you’d achieve this via combining two separate features: dictionary-passing is always present, and type erasure can be achiever via existential types. Dictionary-passing, without type erasure, can be quite useful, as allows for polymorphic recursion, something monomorphization cannot achieve; and also a dedicated existential-types-like feature could offer new capabilities, allowing e.g. handling of multiple values together in one struct of a dynamic / erased type, but all known (in a way that’s understood by the compiler at compile-time) to have the same type.

Sorry, I guess I’ve gone on a bit of a tangent here, quite far away both from the original question and from Rust :sweat_smile:.

5 Likes

The terminology is also used in C#, e.g.

Don't you always put your junk in a box before throwing in on the trash heap?

No, oh well.

I though that in Java and C# boxing was about wrapping things like plain old integers, which are primitives, into actual objects. "integer" becomes "Integer". Now you can put them on the heap rather than just having them as variables on the stack.

Of course we can Box whatever we like.

1 Like

Very interesting tangent, though :slightly_smiling_face:

  • I don't know Haskell well enough to get this dictionary-passing concept, but, based on:

    Would you say that if, in Rust, we unerased the type through some wrapper, we could feature it?

    pub
    struct DebugBox<T : Debug>(
        Box<dyn Debug + 'static>,
        PhantomData<Box<T>>,
    );
    // From<Box<T>>, Into<Box<T>>
    

    ?

    EDIT: It doesn't seem like it (c.f. my attempt; and even this fails)

I guess it’s possible to explain in terms of Rust syntax. Suppose there were no traits, then dictionary passing is a way to simulate certain aspects of what traits allow you to do.

E.g. looking at a simplified Iterator trait,

pub trait Iterator<Item> {
    fn next(this: &mut Self) -> Option<Item>;
    fn size_hint(this: &Self) -> usize;
}

and let’s use free-standing functions for maximal functional programming experience

fn next<Self_: Iterator<Item>, Item>(this: &mut Self_) -> Option<Item> {
    Iterator::next(this)
}

fn size_hint<Self_: Iterator<Item>, Item>(this: &Self_) -> usize {
    Iterator::size_hint(this)
}

then here’s a generic function that uses it

fn second<T, I: Iterator<T>>(mut i: I) -> Option<T> {
    let _ = next(&mut i)?;
    next(&mut i)
}

Then we could “simulate” traits in the following manner. Define a struct instead of a trait:

pub struct IteratorDict<Self_, Item> {
    pub next: fn(&mut Self_) -> Option<Item>,
    pub size_hint: fn(&Self_) -> usize,
}

fn next<Self_, Item>(dict: &IteratorDict<Self_, Item>, this: &mut Self_) -> Option<Item> {
    (dict.next)(this)
}

fn size_hint<Self_: Iterator<Item>, Item>(dict: &IteratorDict<Self_, Item>, this: &Self_) -> usize {
    (dict.size_hint)(this)
}

Here, the free-standing functions now expect an extra argument of type &IteratorDict<Self_, Item>, which replaces the Self_ Iterator<Item> bound that was previously in place. In the same way, we modify the second function:

fn second<T, I>(dict: &IteratorDict<I, T>, mut i: I) -> Option<T> {
    let _ = next(dict, &mut i)?;
    next(dict, &mut i)
}

This function now passes the dictionary argument explicitly to the calls to next.


In this frameworks, what are trait implementations? They’re basically constants:

Taking

type StaticChars = std::str::Chars<'static>;

impl Iterator<char> for StaticChars {
    fn next(this: &mut Self) -> Option<char> {
        std::iter::Iterator::next(this)
    }
    fn size_hint(this: &Self) -> usize {
        0 // yeah, we don’t really know a good size
    }
}

this translates to

const IMPL_ITERATOR_CHAR_FOR_STATIC_CHARS: IteratorDict<StaticChars, char> = IteratorDict {
    next: std::iter::Iterator::next,
    size_hint: |this| 0,
};

Then a non-generic function that calls next

fn foo(mut x: StaticChars) {
    next(&mut x);
}

uses this dictionary

fn foo(mut x: StaticChars) {
    next(&IMPL_ITERATOR_CHAR_FOR_STATIC_CHARS, &mut x);
}

Finally, a generic implementation is a generic function:

impl<T> Iterator<T> for std::vec::IntoIter<T> {
    fn next(this: &mut Self) -> Option<T> {
        std::iter::Iterator::next(this)
    }
    fn size_hint(this: &Self) -> usize {
        this.len()
    }
}

becomes

fn impl_iterator_for_into_iter<T>() -> IteratorDict<std::vec::IntoIter<T>, T> {
    IteratorDict {
        next: std::iter::Iterator::next,
        size_hint: |this| this.len(),
    }
}

And you can probably imagine how to use this when you need a dictionary.


The role of the trait resolver is to always find the correct way of constructing the necessary dictionary. In a generic function, this dictionary might need to be built using functions like impl_iterator_for_into_iter; a generic trait implementation with a trait bound becomes a function that transforms dictionaries:

struct Wrapper<I>(I);
impl<Item, I: Iterator<Item>> Iterator<Item> for Wrapper<I> {
    fn next(this: &mut Self) -> Option<Item> {
        next(&mut this.0)
    }
    fn size_hint(this: &Self) -> usize {
        size_hint(&this.0)
    }
}

becomes

fn impl_iterator_for_wrapper<I, Item>(dict: &IteratorDict<I, Item>) -> IteratorDict<Wrapper<I>, Item> {
    IteratorDict {
        next: |this| next(dict, &mut this.0),
        size_hint: |this| size_hint(dict, &this.0),
    }
}
// this code doesn’t compile, see below

This is the point where I notice that using fn pointers in Rust was inaccurate. Should’ve probably been something like Arc<dyn Fn(...) -> ...> instead to more properly simulate the function types of Haskell and allow capturing. But I hope you get the point.


The final step, to get the full picture, is in realizing that if all types had the same representation at run-time, e.g. every type here would implicitly be Box<T>, then all of the functions here monomorphize to the same code, i.e. monomorphization is no longer necessary. Everything does - under the hood - just work with pointers and dynamic function calls. In Haskell, generic type arguments are completely removed/stripped at some stage of compilation, just the way that lifetimes are removed in Rust.


Funnily enough, after having gone through this, I’m seeing more problems with ever getting support for powerful opt-in support for dictionary-passing in Rust, because I forgot about the fact that building up the necessary dictionaries can involve heap allocations, too. Well, actually, maybe building up dictionaries on the stack is feasible and allows most use-cases anyways…



For the record, polymorphic recursion means support for e.g. types like this

struct CompleteBinaryTree<T>(Box<CompleteBinaryTreeEnum<T>>);
enum CompleteBinaryTreeEnum<T> {
    Simply(T),
    DoubleUp(CompleteBinaryTree<Box<(T, T)>>),
} 

The idea behind such a type is that it either has either a T or a Box<(T, T)> or a Box<(Box<(T, T)>, Box<(T, T)>)>, etc... the type system can dictate that it’s going to be balanced, the number of DoubleUp wrappers at the start encodes the size.

Not only can you define such types, you can work with them. If you implement a trait Foo generically such that T: Foo implies Box<(T, T)>: Foo, then next thing you can do is implement CompleteBinaryTree<T>: Foo based on T: Foo, and it just works. This cannot work with monomorphization, because the implementation for CompleteBinaryTree effectively uses arbitrarily complicated trait implementations for all kinds of types T, Box<(T, T)>, Box<(Box<(T, T)>, Box<(T, T)>)>, and so on. Look at this Haskell code for example:

Compiler Explorer

Where

class SumIntegers self where
    sum :: self -> Integer

is basically a trait

trait SumIntegers {
    fn sum(&self) -> BigInt
}

and you write instance SumIntegers SOME_TYPE where ... instead of impl SOME_TYPE: SumIntegers { ... } (the where and indentation is like the block in Rust)

3 Likes

It's only different in the debug version. If you are enabling optimizations then ICF would usually merge everything (it merges all functions which have the same arguments and the same body, not just Box-related functions, of course).

Have you actually hit the case where ICF was failing you badly?

It's unclear how often would you really need that. And it would complicate language significantly.

1 Like

Besides polymorphic recursion, it also has the application of allowing dynamic linking of generic functions. (Well at least of those kinds of functions that can support it.) It could also make more kinds of traits object-safe.

Note that it’s only a personal idea/feeling of mine though; I don’t have any concrete ideas or proposals how exactly this kind of feature could look like. Also, interaction with specialization might be a fairly huge problem; I’m not sure how this could work well with Any/TypeId either.

1 Like

This thing that Rust apparently doesn't support sounds a lot like Box<dyn Trait> (or even &dyn Trait) to me. Is that it, or are you talking about something different?

For those languages, object types are always on the heap. It doesn't make sense to talk about boxing or unboxing them, because you don't have a choice -- they're never on the stack.

It appears it isn't even a particularly new term,
https://cpsc.yale.edu/sites/default/files/files/tr362.pdf (1985)
that:

The Xerox machine, however, needs to use a reserved address, called an unboxed value, to represent an immediate value [Moore 76]

1 Like

I think that is what I meant. I'm no Java or C# guy but as far as I can tell int is a primitive type and will exist as variables on the stack. Where as Integer is an object. On the heap.

The term boxed was used in a similar but more limited sense at least as far back as 1966 in an early design of The BBN 940 Lisp System. I was aware of this usage in the 70s when I started working with early Lisp Machines, which, perhaps not coincidentally, were created by the same people that designed 940 Lisp.

4 Likes

The difference is that Box<dyn Trait> does type erasure as well; (without dynamic downcasting) there's no way to get back the static type of the boxed values. If you just do dictionary/vtable passing, you don't have to erase the type to do so. Since you're calling a function that's using an opaque type, it takes a bit of functional brain to see it, but if you have something like

fn process<T: Foo>(it: Box<T>, f: fn(&T)) {
    it.foo();
    f(&it)
}

This can then be polymorphized using dictionary passing, where the implementation is basically

// Using `?` for an unknown polymorphic type
fn process(vtable: &VTableFor<dyn Trait>, it: Box<?>, f: fn(&?)) {
    vtable.foo((&*it): &?);
    f((&*it): &?);
}

The key difference is that you still have the concrete type to apply at type level, and at runtime it's equivalent to dyn Trait erasure.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.