20 ms·

Common Lisp names all sixteen binary logic gates

158 points by optimalsolver 4y ago

deleted 4y ago
[deleted]
tromp 4y ago
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...
- samatman 4y ago
  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.
- thefifthsetpin 4y ago
  Common lisp is from 1980.
  - deleted 4y ago
    [deleted]
- zetalyrae 4y ago
  Explicit is, as they say, better than implicit.
  - kazinator 4y ago
    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.
    - thaumasiotes 4y ago
      > 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.
      - deleted 4y ago
        [deleted]
      - kazinator 4y ago
        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.
- gavmor 4y ago
  > 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.
  - donio 4y ago
    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.
  - gumby 4y ago
    > 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.
  - abecedarius 4y ago
    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).
- zem 4y ago
  it keeps the naming scheme consistent
- saghm 4y ago
  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.
  - ngcc_hk 4y ago
    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).
  - thayne 4y ago
    > outside of programming contexts, And formal logic, and reletadly generally mathematical proofs.
  - adrian_b 4y ago
    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".
- eyelidlessness 4y ago
  > As if programmers are not familiar with dozens of other programming languages using plain or... Specificity is the soul of narrative.
phoe-krk 4y ago
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
- zachbeane 4y ago
  Also, some context from comp.lang.lisp is available at https://www.xach.com/naggum/articles/3250122499743574%40naggum.no.html https://www.xach.com/naggum/articles/3250122499743574%40nagg...
  - lisper 4y ago
    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).
- 4y ago
math-dev 4y ago
Marvellous language
- deleted 4y ago
  [deleted]
westurner 4y ago
From File:Logical_connectives_Hasse_diagram.svg https://commons.wikimedia.org/wiki/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 https://en.wikipedia.org/wiki/Hasse_diagram
- westurner 4y ago
  > 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 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_classical_logic https://en.wikipedia.org/wiki/Quantum_logic#Differences_with...
  - westurner 4y ago
    Cirq > Gates and operations: https://quantumai.google/cirq/build/gates https://quantumai.google/cirq/build/gates Cirq > Operators and Observables: https://quantumai.google/cirq/build/operators https://quantumai.google/cirq/build/operators qiskit-terra/qiskit/circuit/operation.py Interface: https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/circuit/operation.py https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/circ... tequila/src/tequila/circuit/gates.py: https://github.com/tequilahub/tequila/blob/master/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_information https://en.wikipedia.org/wiki/Pauli_matrices#Quantum_informa... From Quantum_information#Quantum_information_processing https://en.wikipedia.org/wiki/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.
layer8 4y ago
logorc1 could be aliased to logimpl (for material implication).
cratermoon 4y ago
The Law of Leaky Abstractions[1] strikes again! 1 https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-abstractions/ https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-a...
- hayley-patton 4y ago
  How so?
  - cratermoon 4y ago
    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.
    - hayley-patton 4y ago
      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.
    - tsimionescu 4y ago
      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.
ngcc_hk 4y ago
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.
- rep_lodsb 4y ago
  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.
  - _19qg 4y ago
    > Lisp - like many other interpreted languages and the best thing: Lisp isn't an interpreted language and never was.
deleted 4y ago
[deleted]
svat 4y ago
For reference, here is the corresponding table of all 16 functions, from Knuth: https://imgur.com/a/Xb2HysB https://imgur.com/a/Xb2HysB (TAOCP Vol 4A, earlier draft of this part online at https://cs.stanford.edu/~knuth/fasc0b.ps.gz https://cs.stanford.edu/~knuth/fasc0b.ps.gz.)
bmitc 4y ago
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.
- optimalsolver 4y ago
  https://www.reddit.com/r/ProgrammingLanguages/comments/xb1720/other_than_the_7_basic_logic_gates/ https://www.reddit.com/r/ProgrammingLanguages/comments/xb172...
xelxebar 4y ago
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 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 \ | 0 1 - | --- 0 | 0 1 1 | 1 0 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.
- bhaney 4y ago
  That's horrifying
  - geocar 4y ago
    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.
    - rawling 4y ago
      > 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.
      - geocar 4y ago
        > 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?
ttctciyf 4y ago
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.
- karatinversion 4y ago
  Implication isn’t actually complete - you can’t construct negation from it, because (T, …, T) can only ever get mapped to T.
  - ttctciyf 4y ago
    Ah, thanks, seems I misremembered.
- thaumasiotes 4y ago
  > 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.
aap_ 4y ago
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.

158 points by optimalsolver 4y ago

deleted 4y ago

[deleted]

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...

samatman 4y ago
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.
thefifthsetpin 4y ago
Common lisp is from 1980.
- deleted 4y ago
  [deleted]
zetalyrae 4y ago
Explicit is, as they say, better than implicit.
- kazinator 4y ago
  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.
  - thaumasiotes 4y ago
    > 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.
    - deleted 4y ago
      [deleted]
    - kazinator 4y ago
      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.
gavmor 4y ago
> 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.
- donio 4y ago
  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.
- gumby 4y ago
  > 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.
- abecedarius 4y ago
  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).
zem 4y ago
it keeps the naming scheme consistent
saghm 4y ago
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.
- ngcc_hk 4y ago
  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).
- thayne 4y ago
  > outside of programming contexts, And formal logic, and reletadly generally mathematical proofs.
- adrian_b 4y ago
  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".
eyelidlessness 4y ago
> As if programmers are not familiar with dozens of other programming languages using plain or... Specificity is the soul of narrative.

phoe-krk 4y ago

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

zachbeane 4y ago
Also, some context from comp.lang.lisp is available at https://www.xach.com/naggum/articles/3250122499743574%40naggum.no.html https://www.xach.com/naggum/articles/3250122499743574%40nagg...
- lisper 4y ago
  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).
4y ago

math-dev 4y ago

Marvellous language

deleted 4y ago
[deleted]

westurner 4y ago

From File:Logical_connectives_Hasse_diagram.svg https://commons.wikimedia.org/wiki/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 https://en.wikipedia.org/wiki/Hasse_diagram

westurner 4y ago
> 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 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_classical_logic https://en.wikipedia.org/wiki/Quantum_logic#Differences_with...
- westurner 4y ago
  Cirq > Gates and operations: https://quantumai.google/cirq/build/gates https://quantumai.google/cirq/build/gates Cirq > Operators and Observables: https://quantumai.google/cirq/build/operators https://quantumai.google/cirq/build/operators qiskit-terra/qiskit/circuit/operation.py Interface: https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/circuit/operation.py https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/circ... tequila/src/tequila/circuit/gates.py: https://github.com/tequilahub/tequila/blob/master/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_information https://en.wikipedia.org/wiki/Pauli_matrices#Quantum_informa... From Quantum_information#Quantum_information_processing https://en.wikipedia.org/wiki/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.

layer8 4y ago

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

cratermoon 4y ago

The Law of Leaky Abstractions[1] strikes again! 1 https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-abstractions/ https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-a...

hayley-patton 4y ago
How so?
- cratermoon 4y ago
  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.
  - hayley-patton 4y ago
    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.
  - tsimionescu 4y ago
    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.

ngcc_hk 4y ago

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.

rep_lodsb 4y ago
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.
- _19qg 4y ago
  > Lisp - like many other interpreted languages and the best thing: Lisp isn't an interpreted language and never was.

deleted 4y ago

[deleted]

svat 4y ago

For reference, here is the corresponding table of all 16 functions, from Knuth: https://imgur.com/a/Xb2HysB https://imgur.com/a/Xb2HysB (TAOCP Vol 4A, earlier draft of this part online at https://cs.stanford.edu/~knuth/fasc0b.ps.gz https://cs.stanford.edu/~knuth/fasc0b.ps.gz.)

bmitc 4y ago

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.

optimalsolver 4y ago
https://www.reddit.com/r/ProgrammingLanguages/comments/xb1720/other_than_the_7_basic_logic_gates/ https://www.reddit.com/r/ProgrammingLanguages/comments/xb172...

xelxebar 4y ago

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 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 \ | 0 1 - | --- 0 | 0 1 1 | 1 0 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.

bhaney 4y ago
That's horrifying
- geocar 4y ago
  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.
  - rawling 4y ago
    > 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.
    - geocar 4y ago
      > 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?

ttctciyf 4y ago

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.

karatinversion 4y ago
Implication isn’t actually complete - you can’t construct negation from it, because (T, …, T) can only ever get mapped to T.
- ttctciyf 4y ago
  Ah, thanks, seems I misremembered.
thaumasiotes 4y ago
> 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.

aap_ 4y ago

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.