Re: What does "tag space" mean?

[Thien-Thi Nguyen <ttn@gnuvola.org>]

[-- Attachment #1: Type: text/plain, Size: 1916 bytes --]

() Xue Fuqiao <xfq.free@gmail.com>
() Fri, 1 Mar 2013 20:39:52 +0800

   What does "tag space" mean here?

Personally, i think of "space" as the contents of an empty container,
which is similar to the "set of possible elements of a container" (more
classical meaning), which is similar to "sets with some added structure"
(<https://en.wikipedia.org/wiki/Space>).  Leave it to the mathematicians
to drive straight into the fog.  :-D
                                          
Here, the container is a bit field, and a "tag" is a particular pattern
in that bit field.  If all bits are orthogonal, the space for an N-bit
field numbers 2^N.  So that's where the "structure" comes in; In some
tag systems, all bits are "equal" (either 1 or 0), but some bits are
"more equal than others".  This usually manifests as "if bit A is 1,
then the value of bit B doesn't matter (don't care)".  Such a structure
reduces the space:

- orthogonal -- count: 4
  A B
  0 0
  0 1
  1 0
  1 1

- non-orthogonal -- count: 3
  A B
  0 0
  0 1
  1 X

The tags stand for "types" and so when there is no more "space" in the
primary "space", one has to resort to "sub-types", represented by way of
a secondary (additional) bit field, w/ its own structure (perhaps).

Now, if the primary and secondary bit fields abut, you might think of
them to be simply THE bit field (w/o distinction, but definitely WITH
structure).  That's a matter of taste.  (If they do not abut, well then,
there is no choice, unless you squint a little and elide the invervening
bits.  Personally, i imagine it like a diamond-back snake slithering
past, each diamond on its back adjacent to another, even when looped...)

Oops, sorry about that.  It's very easy for me to "space out" on this
topic.  See src/lisp.h, starting w/ comment "Select the tagging scheme",
for details.

-- 
Thien-Thi Nguyen
GPG key: 4C807502

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]