Boolean

In array languages, Boolean data consists only of the numbers 0 and 1 (outside of APL, Boolean data may use any two values). Boolean values are used in APL whenever a "true" or "false" value is required, that is, the truth value of a logical Proposition such as a comparison of two scalars. The identification of "true" with 1 and "false" with 0 is a simplification of the Iverson bracket, a notation which allowed a truth value to be converted into a number. A notable feature of APL implementations in relation to other language families is their tendency to use bit Booleans (eight in each byte) rather than byte Booleans, a feature which is difficult to implement but increases storage density and can also greatly speed up computation on Boolean arrays.

Examples

The result of a comparison such as Less Than is always composed of Booleans. Because Booleans are numbers, arithmetic functions can be used on them directly, for example by summing a result vector to find out how many times the comparison was true:

      3 1 4 1 5 9 2 < 5
1 1 1 1 0 0 1
      +/ 3 1 4 1 5 9 2 < 5
5

With index origin 0, Booleans can also be used as indices into an array.

      ⎕IO←0
      '-+'[3 1 4 1 5 9 2 < 5]
++++--+

The use of numbers for Booleans also allows functions to be extended from a Boolean domain to a more general domain. The function Compress was originally defined to take a Boolean left argument and use it as a filter for the right argument (removing right argument values corresponding to 0), but has generally now been replaced by an extension called Replicate which can copy right argument values multiple times.

      1 1 1 1 0 0 1 / '3141592'
31412
      0 4 1 2 0 0 0 / '3141592'
1111411

Boolean functions

A monadic or dyadic function (sometimes scalar function) which has a Boolean result when passed Boolean arguments is called a Boolean function. Two Boolean functions are considered the same if they have the same result for every Boolean input. Since there are a finite number of possible inputs (two for monadic functions and four for dyadic functions), and only two results, there are only a finite number of Boolean functions: four monadic and sixteen dyadic.

Every Boolean function which depends on all of its arguments and is not the monadic identity function is represented by a scalar function in APL.

f 0	f 1	Function
0	0	Constant 0
0	1	Identity
1	0	~ Not
1	1	Constant 1

0 f 0	0 f 1	1 f 0	1 f 1	Function
0	0	0	0	Constant 0
0	0	0	1	∧ And, ⌊ Minimum , × Times
0	0	1	0	> Greater Than
0	0	1	1	Left argument
0	1	0	0	< Less Than, | Residue
0	1	0	1	Right argument
0	1	1	0	≠ Not Equal
0	1	1	1	∨ Or, ⌈ Maximum
1	0	0	0	⍱ Nor
1	0	0	1	= Equal
1	0	1	0	Right argument negation
1	0	1	1	≥ Greater Than or Equal, * Power
1	1	0	0	Left argument negation
1	1	0	1	≤ Less Than or Equal, ! Binomial
1	1	1	0	⍲ Nand
1	1	1	1	Constant 1

Boolean optimization

Optimizing for Boolean arrays is one special case of using a small internal type in order to reduce memory usage and improve speed in an APL interpreter. For Booleans this optimization is particularly valuable because each Boolean is representable with a single bit—the smallest discrete quantity available on a CPU. The decision to use packed arrays with eight Booleans for each byte was made by Larry Breed in APL\360, even though the IBM System/360 did not have the capability to address individual bits.

Packed Booleans are especially valuable in array languages because only arrays of Booleans are subject to this optimization: a single Boolean in a processor will use an entire register just like an integer or floating-point value. Using a packed representation for arrays of Booleans both decreases memory usage by a factor of eight and makes faster algorithms possible, as eight times more one-bit values may be fit in a single CPU register (and thus manipulated at once) than one-byte values. However, packed Boolean arrays have a drawback: while optimized algorithms on bit Booleans are usually faster than those on byte Booleans, packed Boolean algorithms are often considerably harder to implement, and unoptimized algorithms using bit Booleans tend to be slower. This is because bits in memory cannot be addressed directly on a modern computing architecture. To read or write a single bit at an arbitrary offset, the byte containing it must be read and then the appropriate bit picked out.

Boolean algorithms are a frequent topic of discussion for APL implementors at the Dyalog user meeting. The following talks all focus primarily on Boolean algorithms:

• Dyalog '08 (05): Roger Hui, "Performance Improvements in Dyalog: A Case Study"
• Dyalog '16 U08: Bob Bernecky, "A Compendium of SIMD Boolean Array Algorithms in APL"
• Dyalog '17 D08: Marshall Lochbaum, "Moving Bits Faster in Dyalog 16.0"
• Dyalog Blog: Marshall Lochbaum, "Expanding Bits in Shrinking Time"

Because they are so small relative to CPU registers, Booleans can make SIMD (Single Instruction Multiple Data) techniques viable even in processors with no dedicated SIMD unit. Programming in this way is called SWAR (SIMD Within a Register), and is considerably easier when working with bit Booleans than when working with integers. Most processors now have SIMD registers and instructions, and the highest levels of Boolean optimization usually require using these instructions. However, Boolean SWAR programming can still be useful to develop algorithms which are fast (often beating dedicated SIMD optimizations on byte-sized data) while remaining architecture independent.

External links

• Eugene McDonnell, "The Caret and the Stick Functions" (on classifying Boolean functions).
• Phil Last, "Boolean Reductions"
• John Scholes, "Data-driven Conditionals"