The cube of lisp booleans (#f nil () #t)

The cube of lisp booleans (#f nil () #t)

[Mark H Weaver]

I wrote up a little summary about the new representation of lisp
booleans.  Maybe something like it will end up in the documentation of
guile internals.

It assumes two more "never use" values that weren't in my v1 patch:
IFLAGS 6 and 7.  This helps make scm_is_lisp_bool a fast operation
without further complicating the implementation or documentation.  The
first 8 IFLAGs are lisp booleans, the first 4 of which are lisp-false.

The pictures below are based on representing a value of N bits as an
N-dimensional hypercube.  In this scheme, the entire space of IFLAGS
is currently a 4-dimensional hypercube, of which the lisp booleans are
a 3-dimensional "slice".  Fortunately, we need only think in
3-dimensions as long as we only consider the lisp booleans.

Note the following nice properties of this representation which I
don't think I've mentioned before:

* Most of the tests compare with a small constant (0x04) after ANDing.
  On the x86 at least, this shortens the instruction sequence by one
  byte.  Of the many possible representations which make use of the
  ANDing trick, I chose this one to maximize the number of tests which
  compare to a small constant.

* Within the set of lisp booleans, it is the most-significant bit
  which determines the truth value.  This allows for a fast conversion
  of a known-lisp-boolean SCM to a C boolean using a simple bit-shift,
  and a compact conversion from a C boolean to SCM, by a bit-shift
  followed by an OR with a small constant (0x04).

I've also added a couple of fast operations: canonicalize_boolean,
fast_boolean_not, and the C-boolean <==> SCM conversions.

The bit masks below are written in binary and split into 4-bit nibbles
for clarity.

     Mark


===============================
== The cube of lisp booleans ==
===============================

scm_is_lisp_bool              for everything in the cube
scm_is_lisp_false             for everything in the front layer
scm_is_bool_or_lisp_nil       for everything in the bottom layer
scm_is_bool_and_not_lisp_nil  for the bottom-left  stack
scm_is_false_or_lisp_nil      for the bottom-front row
scm_is_null_or_lisp_nil       for the  right-front column
     ________       ________       ________
    /| 2 | 3 |     /|   |'()|     /|010|011|
   /||___|___|    /||___|___|    /||___|___|
   6/| 0 | 1 |    |/|#f |nil|    |/|000|001|
   /||___|___|    /||___|___|    /||___|___|
   4/_0_/_1_/     |/#f_/nil/     |/000/001/
   /_4_/_5_/      /#t_/___/      /100/101/

           0100  (0) == #f    SCM_BOOL_F
 0001_0000_0100  (1) == nil   SCM_LISP_NIL
 0010_0000_0100  (2) ==                    (don't use)
 0011_0000_0100  (3) == '()   SCM_EOL
 0100_0000_0100  (4) == #t    SCM_BOOL_T
 0101_0000_0100  (5) ==                    (don't use)
 0110_0000_0100  (6) ==                    (don't use)
 0111_0000_0100  (7) ==                    (don't use)

(1000_1111_1111 & x) ==           0100  scm_is_lisp_bool
(1100_1111_1111 & x) ==           0100  scm_is_lisp_false
(1010_1111_1111 & x) ==           0100  scm_is_bool_or_lisp_nil
(1011_1111_1111 & x) ==           0100  scm_is_bool_and_not_lisp_nil
(1110_1111_1111 & x) ==           0100  scm_is_false_or_lisp_nil
(1101_1111_1111 & x) == 0001_0000_0100  scm_is_null_or_lisp_nil

(1100_1111_1111 & x)                    canonicalize_boolean
						(assumes scm_is_lisp_bool(x))
(1100_1111_1111 & x)  ^ 0100_0000_0000  fast_boolean_not
						(assumes scm_is_lisp_bool(x))

                  (x >> 10)             SCM --> C boolean
						(assumes scm_is_lisp_bool(x))
           0100 | (y << 10)             C boolean --> SCM
						(assumes y is 0 or 1)

Re: The cube of lisp booleans (#f nil () #t)

[Neil Jerram]

Mark H Weaver <mhw@netris.org> writes:

> I wrote up a little summary about the new representation of lisp
> booleans.  Maybe something like it will end up in the documentation of
> guile internals.

Really nice!  Do you have ideas/preference for where this should go, or
would you like me to suggest?

> The pictures below are based on representing a value of N bits as an
> N-dimensional hypercube.  In this scheme, the entire space of IFLAGS
> is currently a 4-dimensional hypercube, of which the lisp booleans are
> a 3-dimensional "slice".  Fortunately, we need only think in
> 3-dimensions as long as we only consider the lisp booleans.

This description gives me confidence that your arrangement is the best
possible one.  (As opposed to just being better than what we had
before.)

Regards,
       Neil