Hacker News new | ask | show | jobs
by adrian_b 1739 days ago
One of the innovations brought by the C language was the use of distinct symbols for the McCarthy logical operators (&& || !) and for the bit string operators (& | ~).

The predecessors of C, i.e. B and BCPL also had both kinds of operators but they used the same symbols for them (in B: & | !) and the context determined which was meant.

However the choice made by C for the new symbols was constrained by the ASCII code, which had no other available symbols.

One decade before the C language, there were 6 symbols in use for the 3 logical or bit string operators, for example IBM PL/I used & | and NOT SIGN, while CPL and IBM APL\360 used LOGICAL AND, LOGICAL OR and TILDE OPERATOR.

The names in capitals are the Unicode names of the symbols.

So there are enough traditional symbols for both the McCarthy logical operators and for the bit string operators, without inventing any new symbols, like C did.

In my opinion, the IBM PL/I set of 3 symbols (& | NOT SIGN) is appropriate for the McCarthy logical operators, while the CPL / IBM APL\360 set of 3 symbols is appropriate for the bit string operators.

The reason is that & and | are more visually distinct so they are preferable in IF or WHILE conditions.

On the other hand, the bit string "and" and "or" are nothing else but "min" and "max" applied to vectors of 1-bit numbers. So the symbols LOGICAL AND and LOGICAL OR are also the right choice as symbols for "min" and "max". Because the LOGICAL AND and the LOGICAL OR symbols are just rotated LESS THAN and GREATER THAN, they are graphically suitable for "min" and "max".

1 comments

You know, the reason Bob Bemer put backslash in ASCII was so that you could write logical AND and logical OR in the conventional way: P /\ Q, P \/ Q. With underscores and backspace for overstrike you had XOR, but that went away with the move to CRT terminals in the 01970s†, and of course ¬ isn't in ASCII.

—⁂—

I like the generalization you're implicitly suggesting, to use /\ and \/ for generalized lattice "meet" and "join"; bit strings are more naturally a lattice or a Boolean algebra (in the algebraic sense—a distributive complemented lattice) than they are a vector space. There's no analogue to \/ in a vector space! Other useful lattice algebras include integers as you point out ("min"/"max"), integers ("lcm"/"gcd", which is how recent versions of APL interpret ∧/∨, though this seems a bit 05AB1E-ish to me, since how often do you actually use those operations?), floating-point numbers (again min/max), and sets (intersection/union). All of these happen to be distributive in the sense that A /\ (B \/ C) = (A /\ B) \/ (A /\ C) and A \/ (B /\ C) = (A \/ B) /\ (A \/ C). You can also construct lattices as Cartesian products of other lattices and duals of other lattices; these are distributive iff the underlying atomic lattices are. (It might be worthwhile to think of bit strings as a topological space along the lines of the Sierpinski space, but I'm not sure if that enables anything useful.)

If we want /\ and \/ to represent operations on specifically a distributive complemented lattice (a Boolean algebra in the algebraic sense), we unfortunately rule out the min/max and gcd/lcm lattices, as well as finite subsets of an infinite set, because there's no suitable way to define ¬. This seems like a pretty big loss because integer min and max are such common operations, more common than bitwise AND and OR in my experience; infix and looping notation for them makes a lot of algorithms easier to express.

But when we introduce element complementation, there's another operation that becomes natural and is in fact so widely used in programming that Golang has an infix operator for it: abjunction, &^. And abjunction is also an infix operator in SQL (MINUS), as well as a machine instruction in SSE (ANDNPS), ARM (BIC), and Wirth-the-RISC. Because it's falsehood-preserving, it doesn't suffer from the infinity problems that occur in extending ¬ to finite subsets of an infinite set or gcd/lcm, although I'm not sure about min/max. It permits McCarthy-style short-circuit evaluation.

On the other hand, every lattice, whether unbounded, bounded but uncomplemented, or complemented, has a dual lattice; you just interchange meet and join. It's unfortunate that there's no way in most programming languages to use this to derive an efficient min-heap data structure from an efficient max-heap or vice versa.

—⁂—

One of the great benefits of syntax in ASCII (or other small character sets without homographs) is that it diminishes Don Norman's "gulfs of evaluation and execution". If you see an operator in ASCII, even an ugly weird one like #+#, you can probably figure out how to type it on a US English keyboard. (And ASCII characters are common enough that even nontechnical users can usually tell you how to type @ on their non-US-English keyboards.) And, if you've typed it, you can usually tell if you've typed it correctly. By contrast, operators like ¬, ÷, λ, ɑ, 𝛼, ⍺, 𝛂, ꭤ, 𝞪, 𝝰, and α have some real usability drawbacks. (All of those last eight are distinct Unicode characters, but two of them are only very subtly different in the font I'm using here.)

______

† Inexplicably, although the heyday of terminals with hardware character generation only lasted from about 01975 to 01988, overstriking never made a comeback, instead blessing us with the botched abortion that is Unicode combining characters and the fifteen normalization forms.