Common Lisp names all sixteen binary logic gates | Hacker News Reader

Common Lisp names all sixteen binary logic gates

cs.cmu.edu

158 pointsoptimalsolver64 comments

J also has these, though it might be a stretch to say it "names" them. Some might argue it's more direct, however: https://code.jsoftware.com/wiki/Vocabulary/bdot#bitwise

Basically, if you read off the bits of the truth table left-to-right, top-to-bottom, you get a string of 4 bits. This encodes a 4-bit integer, which is J's "name" of the function. E.g. for OR

which has a truth table like

    0 1
    1 0

which flattens to 0 1 1 0, gets the encoding 0b0110 = 6. So J would write the logical XOR as (6 b.). To get the bitwise version, just add 16.

That's horrifying

Scroll the linked article down: the lisp “boole” function works the same way i.e. (boole 6 x y) is xor. Lisp has the same thing. But maybe the organisation isn’t clear?

Or is it the numeric value that you fear? There is a fantastic use for this, that if you don’t know, you may want to think about for more than a few seconds.

> There is a fantastic use for this, that if you don’t know, you may want to think about for more than a few seconds.

Is it one of the things in the table towards the bottom of the J article? I have to admit, I'm struggling to read the syntax.

> Is it one of the things in the table towards the bottom of the J article?

Erm, no. That table suggests using b. as a replacement for other (clearer) algorithms for performance reasons, rather than parameterisation.

What I mean by parameterisation is this: if you have a function that takes some arbitrary bitwise operation, instead of taking a lambda, you can pass the truth-table directly.

This idea is mentioned only briefly in the J article (More Info, ¶2):

2. Operand m may be an array, in which case each result cell will be the array of the results of the logical functions specified by m.

Maybe that is too-obvious to an array programmer and not-enough-obvious to someone who isn't, and so it is hard to properly consider the implications or applications of this.

Here's one: Parsing AND/OR operations from an expression (like an SQL expression). You could use a tree of operators and then walk the tree for every row you want to consider or you could store the compositions as a list and do a single reduction.

Is that enough for you to get the idea of what is going on here?

Ah, ok. I'd got as far as going, you can call "&","|" etc. a number based on its truth table, and then you can extend this to other operators we don't think about so much by completing the number range, but I hadn't got so far as going... what...

   a = (o >> (x + 2y)) % 2

or something.

I'd hoped it might involve adding/multiplying different operators together or something like that.

Wouldn't it be more constructive to name this fantastic use, instead of just mentioning it and snarkily suggesting it's obvious?

Maybe geocar is too young to remember ROT13, and doesn't want to spoil things for those of us who did want to think about it first.

fbzrgvzrf jr jnag gb pbzcbfr bcrengvbaf

> To get the bitwise version, just add 16.

That’s the only horrifying part. It gives up the ability to do this for functions taking more than two inputs. They should have used -6 for the bitwise version.

Otherwise, this technique of implementing functions as table lookups with their names being the table is brilliant. That’s self-documenting code. Imagine not having to learn what max means for IEEE floats, but just being able to read it from its function name.

In fact, you would not have to implement any function; you’re just write its name, and the compiler would implement it for you.

I also think they should infer from context whether (6 b.) takes three arguments and produces none, takes two arguments and produces one, takes one and produces two, or takes none and produces three. /s

It would be fun to try and hack the above in a set of C macros. Might lead to a good IOCCC entry (https://www.ioccc.org/)

>In fact, you would not have to implement any function; you’re just write its name, and the compiler would implement it for you.

Isn't this equivalent to placing the function code into its name, in other words, inlining the function? Looks cute for 2-bit programs, but I doubt it scales for 100-bit ones.

These names essentially come from the PDP-10 which has instructions for all 16 boolean operations:

    0000 SETZ
    0001 AND
    0010 ANDCA
    0011 SETM
    0100 ANDCM
    0101 SETA
    0110 XOR
    0111 IOR
    1000 ANDCB
    1001 EQV
    1010 SETCA
    1011 ORCA
    1100 SETCM
    1101 ORCM
    1110 ORCB
    1111 SETO

Where A = accumulator, M = memory, B = both, C = complement of, Z = zero, O = one.

The LISP machine processors (CONS, CADR) also had a 74181 ALU which you could control directly so these names were used again on that platform.

For reference, here is the corresponding table of all 16 functions, from Knuth: https://imgur.com/a/Xb2HysB

(TAOCP Vol 4A, earlier draft of this part online at https://cs.stanford.edu/~knuth/fasc0b.ps.gz.)

What they call "logorc1 [...] or complement of integer1 with integer2" with truth table:

> 1 1 0 1

I think of as (material) implication (the '→' operator, where you can read A → B as "A implies B" or "if A then B".)

This is equivalent to "not (A and (not B))" (because it is only false when A is true and B is false) which in turn reduces to "B or (not A)" by deMorgan (iirc).

This is a pretty standard part of propositional calculus, I seem to remember, and, like nand, implication is complete in the sense that all other operations can be constructed from it.

I guess it may be better from a consistency POV to name it in terms of other operations, but I think the implication name would be more correct.

Implication isn’t actually complete - you can’t construct negation from it, because (T, …, T) can only ever get mapped to T.

Ah, thanks, seems I misremembered.

> This is a pretty standard part of propositional calculus, I seem to remember, and, like nand, implication is complete in the sense that all other operations can be constructed from it.

Implication is not complete; you also need negation.

logorc1 could be aliased to logimpl (for material implication).

The only thing that stood out to me is that bitwise or is called logior, short for logical inclusive or. As if programmers are not familiar with dozens of other programming languages using plain or...

Common lisp is from 1980.

In other words, what C does with absolutely monstrous glyphs, CL does with consistently-named functions. It has logior, lognor, and logxor.

I briefly read that five minutes ago and will probably remember it next week.

Explicit is, as they say, better than implicit.

No it isn't. Even machine language has implicit behaviors which make it suck less like the next instruction implicitly being found at the next address after the previous instruction, without which you'd need an explicit indication of where you want to go.

We can just about define the concept of a higher level language in terms of how it makes numerous chores and concerns implicit.

Good explicit could beat bad implicit in some situations, and vice versa.

> Even machine language has implicit behaviors which make it suck less like the next instruction implicitly being found at the next address after the previous instruction, without which you'd need an explicit indication of where you want to go.

That's not right. There is an explicit indication of where you want to go, the program counter. By default it will increment in an explicit, documented way, but you can also write directly to it. There's nothing implicit about it.

If an instruction changes the program counter, but the program counter doesn't appear as an operand of that instruction, then the effect is implicit.

"Appearing as an operand" means that the instruction could choose a different register to increment other than the program counter, and to increment it by a different value other than exactly to the next instruction.

Indeed, if there is a program counter visible as a register, then it is an explicit representation of where execution is happening.

You don't seem to be sensitive to the IMHO critical difference between "explicit representation" and "explicit operation", though.

An explicit representation can be subject to the implicit effects of operations.

E.g. is is implicit that mkdir("foo", 0755) in Unix will create the directory entries "." and "..". Much of the time you don't worry about them. They are explicitly there, to be sure.

A closure object is an explicit representation of a function; the capture of lexical varaible values by a closure is implicit.

> Work on Common Lisp started in 1981 (wikipedia)

Is it possible that, then, programmers were not familiar with dozens of other languages? I notice this about the R language (1993), a derivation of S (1976): it is like a language from an alternate timeline in which syntax settled on other conventions but, at the time, the question wasn't closed.

And a lot of what ended up in CL has much older roots. I see logior and friends in the MIT Lisp Machine manual but not in the Maclisp one. Maclisp does have a version of boole though.

> Is it possible that, then [1981], programmers were not familiar with dozens of other languages?

In those days people knew more programming languages than is common today. In addition most of the people on the CL committee were academics or from academic instititutions — “industry” back then was more nerd oriented than business oriented as it more commonly is today.

I think you're basically right that conventions were more open, though that's a different question from whether programmers knew a lot of languages.

I started programming in 1981 and read a bunch of older sources in that decade, and saw IOR sometimes (I forget where).

it keeps the naming scheme consistent

To be fair, I've often found that outside of programming contexts, people generally use/interpret "or" to mean xor, and otherwise will use more specific language (e.g. "and/or", "X, Y, or both"). It depends on context of course, but I think a big part of it is that it's somewhat common for the options presented to be literally impossible to both hold true (e.g. "I think either team A or B will win the Superbowl this year") or at least can reasonably assumed to be ("Have you decided what to order?" "I think I'm going to get either the steak or the salmon"). I don't think it's crazy to be willing to experiment with thinking outside the box when it comes to naming things given how hard we always talk about coming up with good names is.

In fact this “or” thinking underlying a lot of problem in our ability to handle issues. You always being asked to choose a or b … catholic or Protestant etc? the question is always should be 4 options - on top of “or” can we have both or none?

For the winning team … if weather or riots etc suddenly prevent further we can declare no win or in some cases both win (each got 1 point instead of re-match).

> outside of programming contexts,

And formal logic, and reletadly generally mathematical proofs.

While I agree that in common language "or" frequently means "exclusive or", I believe that using "xor" to mean "exclusive or" is a bad choice, because "xor" is ambiguous.

In computer programming, "xor" is always used with the meaning "sum modulo 2", never with the meaning "exclusive or", despite its etymology.

The 2 logical functions "exclusive or" and "sum modulo 2" are distinct. They coincide only when applied to two arguments, but they are very different when applied to 3 or more arguments.

"Exclusive or" of N Boolean values is true when one and only one of them is true. "Sum modulo 2" of N Boolean values is true whenever an odd number of them are true.

Both logical functions are very important and I find annoying that the name of "exclusive or" has been misapplied to "sum modulo 2".

I'd rather argue the opposite since XOR gates in hardware with more than 2 inputs also implement sum-modulo-2. Therefore I'd prefer the exactly-1-of-N-inputs-is-true (N > 1) function to be named differently.

These 2 logical functions have been named correctly and used so for centuries, so there is no need to change any name.

The confusion between their names has appeared only some time around 1950, when someone of the designers of the first computers, while implementing in hardware the parity function, a.k.a. modulo-2 sum function, has decided nonetheless to give it the XOR mnemonic from the different "exclusive or" function. and then many others have followed this usage.

It is OK now to use XOR, but one should always be well aware that XOR means parity a.k.a. modulo-2 sum, and not "exclusive or".

I have replied to the parent comment, where the computer mnemonic "xor" was used to mean "exclusive or" in natural language, which is not recommended, as it may be not clear which is the intended meaning, because "xor", in its normal usage, does not mean "exclusive or".

It should be noted that in mathematical notation, the 3 logical quantifiers "for all X ...", "there exists a X ..." and "there exists a unique X ..." correspond to the 3 logical functions "and", "or" and "exclusive or", and not to "and", "or" and "xor" (in the normal meaning of "xor").

Thanks for that clarification :)

Now that I think about it, we could have named it (bitwise) "ODD" and "EVEN" instead of "XOR" and "XNOR".

The usage of "xor" as "sum modulo 2" is correct if you interpret it as composition of two-argument operators like a^b^c == a^(b^c). It's much easier to use infix notation with associative operators, so that is likely why the "sum mod 2" interpretation won.

The "real xor of >2 arguments" is more useful with a notation like exactly_one(a,b,c).

> people generally use/interpret "or" to mean xor, and otherwise will use more specific language (e.g. "and/or", "X, Y, or both").

“To mean xor” isn’t really the best way to put it because “xor” in programming is often generalized to “odd parity”, ie xor(x,y,z) usually means x^y^z instead of x+y+z === 1. Does the second interpretation even have a common name to distinguish it from the odd parity interpretation of xor for multivalued cases?

> As if programmers are not familiar with dozens of other programming languages using plain or...

Specificity is the soul of narrative.

That is the documentation we need for all Common Lisp including the one about its usefulness.

Btw too less tea I have a hard time to say that the function can handle infinity amount … ok with unlimited amount. The whole infinity thing is always a confusing as the definition of infinity is unlimited oriented (integer always have at least one more integer whatever integer you named) and hence can be computed by lazy computing. But you cannot handle infinity in one go.

A positive integer has an infinite number of leading zeroes, and a negative integer in two's complement has an infinite number of leading ones.

On the machine level, you have registers of limited width, and there are usually instructions that sign-extend a shorter integer by setting all the high bits to '1' if it is negative.

By convention, the highest bit indicates the sign, but mathematically it's "arithmetic modulo 2^n", and any value can be interpreted as both positive and negative. For example, a 4 bit register containing '0111' would normally be interpreted as decimal 7, but could also represent -9.

Lisp - like many other interpreted languages - uses arbitrary precision integers, so while not infinite they can be very large.

> Lisp - like many other interpreted languages

and the best thing: Lisp isn't an interpreted language and never was.

This link was a comment in a recent thread. Does anyone have a link to that thread? I can't find it and remember it being interesting.

https://www.reddit.com/r/ProgrammingLanguages/comments/xb172...

The Law of Leaky Abstractions[1] strikes again!

1 https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-a...

How so?

I would have thought it would be intuitively obvious to the most casual observer, but for the sake of those not burdened with the realization that "full stack" really encompasses everything from the quantum behavior of charged particles in a electric field to the world and the people around the software: binary logic gates are a very low-level hardware devices implemented in MOSFETs. They are the tiny building blocks of computational power. To reify these physical devices as abstractions at the level of a language designed to abstract concepts such as the y combinator of lambda calculus, seeing binary logic gates is clearly a leak from lower levels.

Perhaps so, and I've cracked a similar joke (where's the hardware and compiler writers?) but no one brought up a "full stack", so it wasn't obvious what the leaky abstraction was.

Common Lisp isn't strictly a high-level language, it has always been meant as a practical, multi-paradigm language. After all `car' and `cdr' are the names of two registers of a particular LISP machine. Also, bitwise operations are not exclusively an implementation detail - they may well be the point of your computation (as in many programs written to control devices in an embedded system).

Not to mention, the Y combinator is itself a low-level detail of how certain high-level functions (recursive functions) can be expressed in the formalism of the lambda calculus.

Given that on a Lisp Machine (or in a Lisp OS like Mezzano https://github.com/froggey/Mezzano ), the language talks natively to low-level devices (Graphics, SCSI, Bus, Ethernet, ... and other peripherals), it is expected that it has to deal with bits, too.

From File:Logical_connectives_Hasse_diagram.svg https://commons.wikimedia.org/wiki/File:Logical_connectives_...:

> Description: The sixteen logical connectives ordered in a Hasse diagram. They are represented by:

> - logical formulas

> - the 16 elements of V4 = P^4({})

> - Venn diagrams

> The nodes are connected like the vertices of a 4 dimensional cube. The light blue edges form a rhombic dodecahedron - the convex hull of the tesseract's vertex-first shadow in 3 dimensions.

Hasse diagram: https://en.wikipedia.org/wiki/Hasse_diagram

> A research question for a new school year: (2021, still TODO)

> The classical logical operators form a neat topology. Should we expect there to be such symmetry and structure amongst the quantum operators as well?

From Quantum Logic https://en.wikipedia.org/wiki/Quantum_logic :

> Quantum logic can be formulated either as a modified version of propositional logic or as a noncommutative and non-associative many-valued (MV) logic.[2][3][4][5][6]

> Quantum logic has been proposed as the correct logic for propositional inference generally, [...] group representations and symmetry.

> The more common view regarding quantum logic, however, is that it provides a formalism for relating observables, system preparation filters and states.[citation needed] In this view, the quantum logic approach resembles more closely the C*-algebraic approach to quantum mechanics. The similarities of the quantum logic formalism to a system of deductive logic may then be regarded more as a curiosity than as a fact of fundamental philosophical importance. A more modern approach to the structure of quantum logic is to assume that it is a diagram—in the sense of category theory—of classical logics

Quantum_logic#Differences_with_classical_logic: https://en.wikipedia.org/wiki/Quantum_logic#Differences_with...

Cirq > Gates and operations: https://quantumai.google/cirq/build/gates

Cirq > Operators and Observables: https://quantumai.google/cirq/build/operators

qiskit-terra/qiskit/circuit/operation.py Interface: https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/circ...

tequila/src/tequila/circuit/gates.py: https://github.com/tequilahub/tequila/blob/master/src/tequil...

Pauli matrices > Quantum information: https://en.wikipedia.org/wiki/Pauli_matrices#Quantum_informa...

From Quantum_information#Quantum_information_processing https://en.wikipedia.org/wiki/Quantum_information#Quantum_in... :

> The state of a qubit contains all of its information. This state is frequently expressed as a vector on the Bloch sphere. This state can be changed by applying linear transformations or quantum gates to them. These unitary transformations are described as rotations on the Bloch Sphere. While classical gates correspond to the familiar operations of Boolean logic, quantum gates are physical unitary operators.

Are there a finite number of unitary transformations on a Bloch sphere? (If not, is topology relevant to a structured continuum?)

Unitary transformations satisfy local conservation of thermodynamic entropy. (Is Gauss's law similar?)

To save everyone a click:

    integer1        0       0       1       1 
    integer2        0       1       0       1       Operation Performed 
    ----------------------------------------------------------------
    boole-clr       0       0       0       0       always 0 
    boole-set       1       1       1       1       always 1 
    boole-1         0       0       1       1       integer1 
    boole-2         0       1       0       1       integer2 
    boole-c1        1       1       0       0       complement of integer1 
    boole-c2        1       0       1       0       complement of integer2 
    boole-and       0       0       0       1       and 
    boole-ior       0       1       1       1       inclusive or 
    boole-xor       0       1       1       0       exclusive or 
    boole-eqv       1       0       0       1       equivalence (exclusive nor) 
    boole-nand      1       1       1       0       not-and 
    boole-nor       1       0       0       0       not-or 
    boole-andc1     0       1       0       0       and complement of integer1 with integer2 
    boole-andc2     0       0       1       0       and integer1 with complement of integer2 
    boole-orc1      1       1       0       1       or complement of integer1 with integer2 
    boole-orc2      1       0       1       1       or integer1 with complement of integer2

Also, some context from comp.lang.lisp is available at https://www.xach.com/naggum/articles/3250122499743574%40nagg...

And to save everyone from having to read that:

| Can someone explain why the BOOLE function is a single function with sixteen ops rather than sixteen functions.

It's because there are only four possible inputs to a two-input boolean gate, and so there are only 2^4=16 possible boolean gates. Furthermore there is a straightforward representation of those gates as an ordered sequence of four bits that specify the output of the gate for each of the four possible combinations of inputs (though the CL standard does not actually require implementations to use this representation, and not all do).

MACLISP also had a BOOLE function, which had an extra argument with 16 possible values., e.g.

    (BOOLE 1 x y) was equivalent to x & y (1 = 0001 => AND)
    (BOOLE 6 x y) was equivalent to x ^ y (6 = 0110 => XOR)
    (BOOLE 7 x y) was equivalent to x | y (7 = 0111 => OR)
    (BOOLE 14 x y) was equivalent to ~(x & y) (14 = 1110 => NAND)

i.e. the first argument always corresponds to the values in the binary operation table (as shown in your table).

But in Common Lisp, the values are in an arbitrary order with, e.g. boole-and = 6 instead of 1 (0001), boole-xor = 8 instead of 6 (0110), and boole-nand = 10 instead of 14 (1110). As well as being arbitrary, this unnecessarily breaks backward compatibility with MACLISP.

    boole-and       0       0       0       1       and 
    boole-nand      1       1       1       0       not-and

While boole-and appears in the 6th (counting from 0) position, it still has a binary representation here of 1, and boole-nand is (reasonably) its complement with 14. It seems the table has been reordered for some reason for this presentation. It seems to present 0-ary, 1-ary, 2-ary operations in that order, which doesn't correspond to the order of the binary representation.

If I remember correctly these are the PDP-10 Boolean operator codes.

Yep, zachbeane's near-simultaneous comment to mine has a link with details on that.

The order is implementation-specific. For the values I cared to sample below, CLISP seems to have sane values that reflect the truth tables:

  [1]> boole-clr
  0
  [2]> boole-set
  15
  [3]> boole-and
  8
  [4]> boole-ior 
  14
  [5]> boole-nand
  7

Obviously, values with this property are not unique; they depend on the bit combination order. boole-and and boole-ior could plausibly be 1 and 7.

IMHO, the latitude in the spec should be interpreted as accommodating this truth table ordering variation, and not as an invitation for arbitrarily enumerating the functions so that the values don't make sense as truth tables.

That is to say, it should be possible to perform logical operations on the values whose interpretation is that the truth tables are combined accordingly, such that these two are equivalent:

   (boole (logior boole-xxx boole-yyy) a b)

   <-->

   (logior (boole boole-xxx a b) (boole boole-yyy a b))

No matter how boole-and is defined, (logior boole-and boole-nand) should produce 15, which should be the value of boole-set.

The vector indexing trick recommended in the boole function's example should only be necessary for a program which needs the operators to have concrete values corresponding to a particular choice of truth table bit order. It should not be necessary for obtaining indexing which has the above good behavior with respect to being able to use logical operators on the truth tables in order to combine them.

Indeed, the implementation from which you are reporting seems to have a broken numbering. For the boole-xor function, we need to see a value that has two zeros and two ones. If it's not one of the values 2, 5, 9, 6, 10, 12, then the numbering is broken. It is inescapable that boole-clr and boole-set must be 0 and 15.

Marvellous language

Reply on news.ycombinator.com