[racket] Box: When and why?

There is a variation on what Matthias said, which is when you need a
shared structure whose value changes but whose representation may
contain immutable constants.

Consider a queue to which you may need to store references in multiple
places (including, say, a hash-table).

The queue may itself be a functional value, and the empty queue may
well be represented with `empty'.  However, empty is immutable, so you
can't store the empty in the hash-table, change the content of the
queue, and expect the hash-table to notice the change.

In such cases, you would use the box to represent the queue, with the
box's content representing the queue's content.  The hash table refers
to the box, so updates to the box are reflected in the hash table.

If you work it out, you realize that at some point this involves the
by-reference pattern that Matthias referred to.  However, its point is
not really to implement by-reference, but a different concept (that of
shared references to changing structures that may contain immutable
and transient values).

In the above example, you could instead make the queue itself be a
mutable structure, and store a special kind of value that reflects
emptiness.  This has two downsides:

1. You've made your queue mutable, which may pollute code, weaken
invariants, and reduce performance.

2. Now you have a special kind of queue that says "I am not a queue".

Traditional programming textbooks for languages like Pascal and C++
are full of these kinds of monstrosities and the very tricky problems
of programming correctly with them.  Crack open any "circular queue"
chapter and feel the pain.

The other, cleaner, option is to create a mutable structure just as a
placeholder: a single-field mutable structure whose only purpose is to
say "the queue's content is that value over there, I'm just the
shareable reference to it".

Well, you could define that structure, or use the one that's already
provided for you: the box.  (It's just like you said: when you have a
small number of values to return, you don't bother creating a new
structure, you just use `values'.)

Shriram