Subject: Re: Just curious, why is boole the way it is?
From: Erik Naggum <erik@naggum.no>
Date: 29 Dec 2002 03:48:19 +0000
Newsgroups: comp.lang.lisp
Message-ID: <3250122499743574@naggum.no>

* Peter Seibel
| 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.