Subject: Re: Just curious, why is boole the way it is?
From: Erik Naggum <erik@naggum.no>
Date: 30 Dec 2002 07:28:25 +0000
Newsgroups: comp.lang.lisp
Message-ID: <3250222105960910@naggum.no>

* Peter Seibel
| I'm just not clear why they weren't implemented as sixteen
| different functions.

  When you ask why some choices in the past were not made a certain
  way, the inherent anachronism of the question shows the way to the
  answer.  Standing somewhere on the path not taken and asking "why
  did you not go here?" demonstrates the power of human imagination,
  but the answer lies in researching why the choices that /were/ made
  were made the way they were.  Time and again we find people who
  look at the past and wonder why someone did not do what they think
  would have been the smarter move from their vantage point of the
  future, but it is nothing but an occluded case of hindsight.

  The question that should be asked is what kind of problems were
  solved by that choice at the time it was made.  Assume it was very
  intelligently made at the time and look for the conditions that
  would make it very intelligent.  Just like you approach arguments
  or statements that fly in the face of your beliefs, you have to
  look for the facts that would make it a rational choice.  If it no
  longer looks like the best possible choice, that means the good
  reasons have yielded to other reasons over time, but understand
  that this is /history/ at its best.  It was not some dumbass idiot
  choice at the time, it was a demonstration of intelligence applied
  so as to get incredibly elegant results.  Arguments along the lines
  of "but the PDP-10 died", betrays an inability to deal with time as
  the fourth dimension.  Specifically, something may have been true
  without being true today because something changed, so you need to
  look at what was true at the same time to grasp the meaning of any
  historic truths.  And so, too, with the choices people make.

  But which functions are you missing?  Set to all zeros, set to all
  ones, set to argument 1, set to argument 2, set to complement of
  argument 1, set to complement of argument 2, right?  These are part
  of the `boole´ operator because they are required in the matrix of
  operators and values and so are needed if you build a mini-language
  that does boolean bit-wise operations.  Now, a number of problems
  can be solved with such mini-languages that operate on the bits of
  a large machine word -- but the problems that can be solved with a
  puny 32-bit machine word (or punier 16-bit or puniest 8-bit) are
  uninteresting.  Since Common Lisp supports bignums and because the
  PDP-10 had very decent support for arrays of machine words that
  formed virtual integers (thus enabling the evolution of bignums),
  the functionality makes sense only when you understand how integers
  can be used productively as bit maps.

  Now, you may be surprised to find that the operators of `boole´ are
  also found to have exact parallels for bit vectors:

        PDP-10  bits  boole opcode  integer     bit-vector
        ------  ----  ------------  ----------  ----------
        SETZ    0000  boole-clr       logclr      bit-clr
        AND     0001  boole-and     logand      bit-and
        ANDCA   0010  boole-andc2   logandc2    bit-andc2
        SETM    0011  boole-1         log1        bit-1
        ANDCM   0100  boole-andc1   logandc1    bit-andc1
        SETA    0101  boole-2         log2        bit-2
        XOR     0110  boole-xor     logxor      bit-xor
        IOR     0111  boole-ior     logior      bit-ior
        ANDCB   1000  boole-nor     lognor      bit-nor
        EQV     1001  boole-eqv     logeqv      bit-eqv
        SETCA   1010  boole-c2        logc2       bit-c2
        ORCA    1011  boole-orc2    logorc2     bit-orc2
        SETCM   1100  boole-c1        logc1       bit-c1
        ORCM    1101  boole-orc1    logorc1     bit-orc1
        ORCB    1111  boole-nand    lognand     bit-nand
        SETO    1111  boole-set       logset      bit-set

  The "missing" functions (indented by two spaces above) may be
  defined as follows:

(defun logclr (&rest integers)
  (declare (ignore integers))
  (logior))

(defun log1 (integer-1 integer-2)
  (declare (ignore integer2))
  integer-1)

(defun log2 (integer-1 integer-2)
  (declare (ignore integer1))
  integer-2)

(defun logc2 (integer-1 integer-2)
  (declare (ignore integer-1))
  (lognot integer-2))

(defun logc1 (integer-1 integer-2)
  (declare (ignore integer-2))
  (lognot integer-1))

(defun logset (&rest integers)
  (declare (ignore integers)
  (logand)))

(defun bit-clr (bit-vector-1 bit-vector-2 &optional result)
  (declare (ignore bit-vector-2))
  (bit-andc2 bit-vector-1 bit-vector-1 result))

(defun bit-1 (bit-vector-1 bit-vector-2 &optional result)
  (declare (ignore bit-vector-2))
  (bit-and bit-vector-1 bit-vector-1 result))

(defun bit-2 (bit-vector-1 bit-vector-2 &optional result)
  (bit-and bit-vector-2 bit-vector-2 (if (eq result t) bit-vector-1 result)))

(defun bit-c2 (bit-vector-1 bit-vector-2 &optional result)
  (bit-not bit-vector-2 (if (eq result t) bit-vector-1 result)))

(defun bit-c1 (bit-vector-1 bit-vector-2 &optional result)
  (declare (ignore bit-vector-2))
  (bit-not bit-vector-1 result))

(defun bit-set (bit-vector-1 bit-vector-2 &optional result)
  (declare (ignore bit-vector-2))
  (bit-orc2 bit-vector-1 bit-vector-1 result))

  (Please note that a /full/ implementation of these functions would
  also include compiler macros to turn them into the simpler form, on
  which the compiler would be able to apply its reasoning capability
  about builtin functions.  A /native/ implementation would exploit
  the simpler nature of `bit-clr´ and `bit-set´ to fill or construct
  a bit-vector with the same element, and `bit-1´ and `bit-2´ would
  be implemented with an equally fast copying function, but the above
  definitions require no information about the implementation of the
  standard functions or of the bit-vector type, so may serve as the
  substrate upon which a (future|layered) standard may be built.)
  
  If the above 12 functions are perceived as useful, I would be
  inclined to publish a package with them suitable for inclusion in
  the major Common Lisp environments, with the appropriate level of
  native support.  (Also, I need to learn the mechanics of such
  publication, and something suitably harmless would be a good
  stepping stone.)

-- 
Erik Naggum, Oslo, Norway

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.