From: Mark H Weaver <mhw@netris.org>
To: guile-devel <guile-devel@gnu.org>
Subject: The cube of lisp booleans (#f nil () #t)
Date: Sun, 30 Aug 2009 13:17:16 -0400 [thread overview]
Message-ID: <87ab1hql0j.fsf@netris.org> (raw)
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)
next reply other threads:[~2009-08-30 17:17 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-08-30 17:17 Mark H Weaver [this message]
2009-09-17 22:17 ` The cube of lisp booleans (#f nil () #t) Neil Jerram
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87ab1hql0j.fsf@netris.org \
--to=mhw@netris.org \
--cc=guile-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).