Subject: Re: Just curious, why is boole the way it is? From: Erik Naggum <email@example.com> Date: 30 Dec 2002 07:28:25 +0000 Newsgroups: comp.lang.lisp Message-ID: <firstname.lastname@example.org> * 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.