[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
The cube of lisp booleans (#f nil () #t)
From: |
Mark H Weaver |
Subject: |
The cube of lisp booleans (#f nil () #t) |
Date: |
Sun, 30 Aug 2009 13:17:16 -0400 |
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)
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- The cube of lisp booleans (#f nil () #t),
Mark H Weaver <=