From ... Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!newsmi-us.news.garr.it!NewsITBone-GARR!news.mailgate.org!newsfeed.icl.net!newsfeed.fjserv.net!newsfeed.icl.net!newsfeed.fjserv.net!news.tele.dk!news.tele.dk!small.news.tele.dk!newsfeed1.e.nsc.no!nsc.no!nextra.com!uio.no!nntp.uio.no!ifi.uio.no!not-for-mail From: Erik Naggum Newsgroups: comp.lang.lisp Subject: Re: Just curious, why is boole the way it is? Date: 29 Dec 2002 03:48:19 +0000 Organization: Naggum Software, Oslo, Norway Lines: 112 Message-ID: <3250122499743574@naggum.no> References: Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: maud.ifi.uio.no 1041133701 16941 129.240.65.203 (29 Dec 2002 03:48:21 GMT) X-Complaints-To: abuse@ifi.uio.no NNTP-Posting-Date: 29 Dec 2002 03:48:21 GMT Mail-Copies-To: never User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 Xref: archiver1.google.com comp.lang.lisp:49531 * 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 #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.