From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.devel Subject: The cube of lisp booleans (#f nil () #t) Date: Sun, 30 Aug 2009 13:17:16 -0400 Message-ID: <87ab1hql0j.fsf@netris.org> NNTP-Posting-Host: lo.gmane.org X-Trace: ger.gmane.org 1251652664 7815 80.91.229.12 (30 Aug 2009 17:17:44 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 30 Aug 2009 17:17:44 +0000 (UTC) To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Aug 30 19:17:37 2009 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1Mho24-0005L7-Gq for guile-devel@m.gmane.org; Sun, 30 Aug 2009 19:17:36 +0200 Original-Received: from localhost ([127.0.0.1]:59824 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Mho23-0007ky-Oe for guile-devel@m.gmane.org; Sun, 30 Aug 2009 13:17:35 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1Mho1x-0007ki-4S for guile-devel@gnu.org; Sun, 30 Aug 2009 13:17:29 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1Mho1r-0007kW-HU for guile-devel@gnu.org; Sun, 30 Aug 2009 13:17:27 -0400 Original-Received: from [199.232.76.173] (port=34582 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Mho1r-0007kT-Co for guile-devel@gnu.org; Sun, 30 Aug 2009 13:17:23 -0400 Original-Received: from world.peace.net ([204.107.200.8]:59865) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1Mho1r-00052f-0O for guile-devel@gnu.org; Sun, 30 Aug 2009 13:17:23 -0400 Original-Received: from localhost ([127.0.0.1] helo=debxo ident=hope7) by world.peace.net with esmtp (Exim 4.69) (envelope-from ) id 1Mho1l-00017Y-J2; Sun, 30 Aug 2009 13:17:17 -0400 X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 3) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:9214 Archived-At: 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)