Just curious, why is boole the way it is?
Peter Seibel
sixteen ops rather than sixteen functions. It seems that you burn the
same number of symbols in the COMMON-LISP package (well, even one more
the way it is than if there were sixteen functions) and as functions
are first-class in Lisp doesn't seem it makes paramaterizing things
significantly easier.And then why are there the LOGAND, et al.
functions covering eleven of the sixteen cases handled by BOOLE? Is it
historical? Is there some deep design insight that is eluding me? Just
curious.
-Peter
--
Peter Seibel
pe...@javamonkey.com
Rainer Joswig
Peter Seibel <pe...@javamonkey.com> wrote:
The Symbolics docs say:
"As a matter of style the explicit logical functions such as logand,
logior, and logxor are usually preferred over the equivalent forms
of boole. boole is useful, however, when you want to generalize a
procedure so that it can use one of several logical operations."
Erik Naggum
| Can someone explain why the BOOLE function is a single function
| with sixteen ops rather than sixteen functions.
I'll try...
| It seems that you burn the same number of symbols in the
| COMMON-LISP package (well, even one more the way it is than if
| there were sixteen functions) and as functions are first-class in
| Lisp doesn't seem it makes paramaterizing things significantly
| easier.
Burning any given number of symbols in the `common-lisp´ package is
not a design goal, though.
| And then why are there the LOGAND, et al. functions covering eleven
| of the sixteen cases handled by BOOLE? Is it historical? Is there
| some deep design insight that is eluding me? Just curious.
You may find the table in the standard at `boole´ instructive, but
it should be a lot more instructive when listed in the proper order:
Results of (BOOLE <op> #b0011 #b0101) ...
---Op-------Decimal-----Binary----Bits---
BOOLE-CLR 0 0 ...0000
BOOLE-AND 1 1 ...0001
BOOLE-ANDC2 2 10 ...0010
BOOLE-1 3 11 ...0011
BOOLE-ANDC1 4 100 ...0100
BOOLE-2 5 101 ...0101
BOOLE-XOR 6 110 ...0110
BOOLE-IOR 7 111 ...0111
BOOLE-NOR -8 -1000 ...1000
BOOLE-EQV -7 -111 ...1001
BOOLE-C2 -6 -110 ...1010
BOOLE-ORC2 -5 -101 ...1011
BOOLE-C1 -4 -100 ...1100
BOOLE-ORC1 -3 -11 ...1101
BOOLE-NAND -2 -10 ...1110
BOOLE-SET -1 -1 ...1111
In a sane implementation of `boole´, the values of the various
`boole-foo´ constants exactly mimic the last four bits of the
result of the operation between #B0011 and #B0101. It is damn
disappointing to find implementations that fail to exploit this
exceedingly elegant property of the logic operator set!
Those with a proper history background in computer science will
know that the sixteen operators of the PDP-10 from Digital
Equipment Corporation (RIP) go as follows, with the 9-bit binary
op-code, which should be compared with the above table:
SETZ 100 000 000 set to zero
AND 100 000 100 and
ANDCA 100 001 000 and complement of accumulator
SETM 100 001 100 set to memory
ANDCM 100 010 000 and complement of memory
SETA 100 010 100 set to accumulator
XOR 100 011 000 exclusive or
IOR 100 011 100 inclusive or
ANDCB 100 100 000 and complement of both (= nor)
EQV 100 100 100 equivalent (complement of xor)
SETCA 100 101 000 set to complement of accumulator
ORCA 100 101 100 inclusive or complement of accumulator
SETCM 100 110 000 set to complement of memory
ORCM 100 110 100 inclusive or complement of memory
ORCB 100 111 000 inclusive or complement of both (= nand)
SETO 100 111 100 set to ones
For completeness, there were four versions of each op-code, using
the last two bits of the op-code: the basic version (00) which
found the source at the effective address and placed the result in
the accumulator, the immediate version (01) which used the
effective address itself as the source, the memory version (10)
which was like the basic version but stored the value back to the
effective address (i.e., memory), and the both version (11) which
was like the memory version except that it also stored the result
in the accumulator. There were lots of elegance in this processor,
properly discussed in alt.sys.pdp10, but suffice to say that its
registers were accessible as the low 16 machine words of memory, so
a register-to-register operation did not differ from a register-to-
memory operation except in execution time. Since this was a word-
machine, its 36-bit machine words contained 27 more bits, 18 of
which were the address, 1 was the indirection bit, 4 were the
indexing accumulator used in computing the effective address, and
the 4 last were the accumulator. (The indirection bit as pretty
cool -- the effective address calculation would /loop/ using the
effective address it had just computed to pick up a new machine
word to compute it from. Multidimensional arrays was a blast!)
Note that a whole slew of instructions were redundant or no-ops but
were included because the instruction set was exceptionally
regular. The oral tradition included information on the fastest
NOP and the use of the JUMP instruction (jumped on no condition!)
to do error handling. Ah, those were the days!
One of the very amusing aspects of this processor was that it was
possible to execute an instruction held in a register as if it had
been found in the normal instruction flow. It was thus common
practice to construct fairly complex algorithms with variations on
a theme by passing in various op-codes and using the deposit byte
instruction to store it into the op-code field of a machine word in
a register. The deposit byte instruction as well as the load byte
instructions have also been carried over into Common Lisp: DPB and
LDB, but the storing op-code into machine word and executing it
stunt could obviously not become part of a higher-level language,
but `boole´ serves precisely that function...
--
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.
Peter Seibel
> * Peter Seibel
> | Can someone explain why the BOOLE function is a single function
> | with sixteen ops rather than sixteen functions.
>
> I'll try...
Thanks.
> | It seems that you burn the same number of symbols in the
> | COMMON-LISP package (well, even one more the way it is than if
> | there were sixteen functions) and as functions are first-class in
> | Lisp doesn't seem it makes paramaterizing things significantly
> | easier.
>
> Burning any given number of symbols in the `common-lisp´ package is
> not a design goal, though.
Okay. That was just a guess.
So I get why there are sixteen variants. I'm just not clear why they
weren't implemented as sixteen different functions. Is the point that
if an implementation used proper values of the boole-* constants then
the compiler could compile a call to the boole function to the same
snippet of (PDP-10) machine code with the value of the appropriate op
stuck in the middle four bits of the above op-codes. I.e. something
down in the bowels of the compiler there might exist a funciton like:
(defun compile-boole (boole-op addr1 addr2)
(emit-boole-preamble addr1 addr2)
(emit (dpb boole-op (byte 4 2) #B100000000))
(emit-boole-postable addr1 addr2))
Whereas if there were sixteen separate functions the compiler would
have to have some special magic to realize that all sixteen can by
compiled into almost the same machine code, modulo four bits. If so,
does it really matter (other than just for elegance) what the values
of the constants are if your compiler isn't targeting the PDP-10?
Frank A. Adrian
> So I get why there are sixteen variants. I'm just not clear why they
> weren't implemented as sixteen different functions.
It's useful for bit-blt operations this way. You can use the same loop
structure while just changing the sources and operation. You might ask,
"Then why not just change the function applied to the source and
destination?". Many of these operations can compile directly into machine
code - just drop a few bits into the instruction (yes, it's self-modifying,
but it's fast, even when you do have to reload the I-cache to do it :-). A
"sufficiently smart" compiler (or coder) can inline many of these
operations, even on today's chips. Not that many Lisp programs take
advantage of these capabilities these days - the days of screen bit-level
rendering by the main CPU seem long gone, all the bit-blt operations are
safely tucked away in graphics cards, and precious few of them seem to have
Lisp engines inside. However, fast bit-level operations can still be quite
useful in manipulation of large, dense sets, matching algorithms, etc.
Whether or dynamic boolean operators are still important enough to keep the
boole operation optimized over its logxxx bretheren might be debateable,
though.
faa
Pascal Bourguignon
> [...]
> So I get why there are sixteen variants. I'm just not clear why they
> weren't implemented as sixteen different functions. Is the point that
> if an implementation used proper values of the boole-* constants then
> the compiler could compile a call to the boole function to the same
> snippet of (PDP-10) machine code with the value of the appropriate op
> stuck in the middle four bits of the above op-codes. I.e. something
> down in the bowels of the compiler there might exist a funciton like:
>
> (defun compile-boole (boole-op addr1 addr2)
> (emit-boole-preamble addr1 addr2)
> (emit (dpb boole-op (byte 4 2) #B100000000))
> (emit-boole-postable addr1 addr2))
>
> Whereas if there were sixteen separate functions the compiler would
> have to have some special magic to realize that all sixteen can by
> compiled into almost the same machine code, modulo four bits. If so,
> does it really matter (other than just for elegance) what the values
> of the constants are if your compiler isn't targeting the PDP-10?
I think that more fundamentaly, this orthogonality allows to implement
boole directly:
ab a b f0 f1 f2 ... f14 f15
----------------------------------------
0 0 0 0 1 0 0 1
1 0 1 0 0 1 1 1
2 1 0 0 0 0 1 1
3 1 1 0 0 0 1 1
There are 16 functions, because the two bits of the arguments can make
four combinations. The value of the function for each combination
correspond to the corresponding bit in the function number!
For example, f2(0,1)=1 because the bit 0*2+1=1 of 2 (=0010) is 1, while
f2(1,0)=0 because the bit 1*2+0=2 of 2 (=0010) is 0.
A logically implemented microprocessor would take the same shortcut,
hence exhibiting that regular op-code table.
(defun boole op in1 in2)
(let ((opbits (integer-to-bitvector op))
(in1bits (integer-to-bit-list in1))
(in2bits (integer-to-bit-list in2))
)
(bit-list-to-integer
(mapcar (lambda (bit1 bit2) (nth (+ (* 2 bit1) bit2) opbits))
in1bits in2bits))))
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
There is a fault in reality. Do not adjust your minds. -- Salman Rushdie
Erik Naggum
| 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.)
Joe Marshall
> So I get why there are sixteen variants. I'm just not clear why they
> weren't implemented as sixteen different functions. Is the point that
> if an implementation used proper values of the boole-* constants then
> the compiler could compile a call to the boole function to the same
> snippet of (PDP-10) machine code with the value of the appropriate op
> stuck in the middle four bits of the above op-codes. I.e. something
> down in the bowels of the compiler there might exist a funciton like:
>
> (defun compile-boole (boole-op addr1 addr2)
> (emit-boole-preamble addr1 addr2)
> (emit (dpb boole-op (byte 4 2) #B100000000))
> (emit-boole-postable addr1 addr2))
You have to understand how the instructions were executed by the
hardware. The instruction register had fields that were connected by
wires to various parts of the hardware. The middle 4 bits of the
instruction register were connected to the hardware that performed the
boolean operation and selected one of the 16 possible results.
Now combine this with the `execute instruction in register' feature.
Now the inner loop of your BITBLT routine can take the boolean
operation you wish to perform as an argument and simply fill in the
appropriate field in a SETZ instruction. Now instead of 16 different
bitblt routines (or a 16-way branch in the middle of your tight loop),
you have one.
Peter Seibel
Absolutely. That is exactly the spirit in which I posted my original
question. Thank you for your detailed replies.
Kent M Pitman
> You have to understand how the instructions were executed by the
> hardware. The instruction register had fields that were connected by
> wires to various parts of the hardware. The middle 4 bits of the
> instruction register were connected to the hardware that performed the
> boolean operation and selected one of the 16 possible results.
But also, I don't know if it came up in this discussion, the nature of
the value is unspecified. It could be that the values are _functions_
and that BOOLE just funcalls them. So we left room for this integer
dispatch style that Erik described in detail, but we also left room
for other mechanisms.