Boolean: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
m (3 revisions imported: Migrate from miraheze)
m (Text replacement - "</source>" to "</syntaxhighlight>")
 
(9 intermediate revisions by 2 users not shown)
Line 2: Line 2:
|<code>0</code> <code>1</code>
|<code>0</code> <code>1</code>
|}
|}
In array languages, '''Boolean''' data consists only of the [[number]]s 0 and 1 (outside of APL, [[wikipedia:Boolean_data_type|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 [[wikipedia:Proposition|Proposition]] such as a [[comparison]] of two [[scalar]]s. 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.
In array languages, '''Boolean''' data consists only of the [[number]]s 0 and 1 (outside of APL, [[wikipedia:Boolean_data_type|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 [[wikipedia:Proposition|proposition]] such as a [[comparison]] of two [[scalar]]s. 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 ==
== 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 [[sum]]ming a result [[vector]] to find out how many times the comparison was true:
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 [[sum]]ming a result [[vector]] to find out how many times the comparison was true:
<source lang=apl>
<syntaxhighlight lang=apl>
       3 1 4 1 5 9 2 < 5
       3 1 4 1 5 9 2 < 5
1 1 1 1 0 0 1
1 1 1 1 0 0 1
       +/ 3 1 4 1 5 9 2 < 5
       +/ 3 1 4 1 5 9 2 < 5
5
5
</source>
</syntaxhighlight>
With [[index origin]] 0, Booleans can also be used as [[Index|indices]] into an array.
With [[index origin]] 0, Booleans can also be used as [[Index|indices]] into an array.
<source lang=apl>
<syntaxhighlight lang=apl>
       ⎕IO←0
       ⎕IO←0
       '-+'[3 1 4 1 5 9 2 < 5]
       '-+'[3 1 4 1 5 9 2 < 5]
++++--+
++++--+
</source>
</syntaxhighlight>


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.
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.
<source lang=apl>
<syntaxhighlight lang=apl>
       1 1 1 1 0 0 1 / '3141592'
       1 1 1 1 0 0 1 / '3141592'
31412
31412
       0 4 1 2 0 0 0 / '3141592'
       0 4 1 2 0 0 0 / '3141592'
1111411
1111411
</source>
</syntaxhighlight>


== Boolean functions ==
== Boolean functions ==
Line 35: Line 35:


{|class=wikitable
{|class=wikitable
! <source lang=apl inline>f 0</source> !! <source lang=apl inline>f 1</source> !! Function
! <syntaxhighlight lang=apl inline>f 0</syntaxhighlight> !! <syntaxhighlight lang=apl inline>f 1</syntaxhighlight> !! Function
|-
|-
|  0  ||  0  || Constant 0
|  0  ||  0  || Constant 0
Line 41: Line 41:
|  0  ||  1  || Identity
|  0  ||  1  || Identity
|-
|-
|  1  ||  0  || <source lang=apl inline>~</source> [[Not]]
|  1  ||  0  || <syntaxhighlight lang=apl inline>~</syntaxhighlight> [[Not]]
|-
|-
|  1  ||  1  || Constant 1
|  1  ||  1  || Constant 1
Line 47: Line 47:


{|class=wikitable
{|class=wikitable
! <source lang=apl inline>0 f 0</source> !! <source lang=apl inline>0 f 1</source> !! <source lang=apl inline>1 f 0</source> !! <source lang=apl inline>1 f 1</source> !! Function
! <syntaxhighlight lang=apl inline>0 f 0</syntaxhighlight> !! <syntaxhighlight lang=apl inline>0 f 1</syntaxhighlight> !! <syntaxhighlight lang=apl inline>1 f 0</syntaxhighlight> !! <syntaxhighlight lang=apl inline>1 f 1</syntaxhighlight> !! Function
|-
|-
|  0  ||  0  ||  0  ||  0  || Constant 0
|  0  ||  0  ||  0  ||  0  || Constant 0
|-
|-
|  0  ||  0  ||  0  ||  1  || <source lang=apl inline>∧</source> [[And]], <source lang=apl inline>⌊</source> [[Minimum]] , <source lang=apl inline>×</source> [[Times]]
|  0  ||  0  ||  0  ||  1  || <syntaxhighlight lang=apl inline>∧</syntaxhighlight> [[And]], <syntaxhighlight lang=apl inline>⌊</syntaxhighlight> [[Minimum]] , <syntaxhighlight lang=apl inline>×</syntaxhighlight> [[Times]]
|-
|-
|  0  ||  0  ||  1  ||  0  || <source lang=apl inline>></source> [[Greater Than]]
|  0  ||  0  ||  1  ||  0  || <syntaxhighlight lang=apl inline>></syntaxhighlight> [[Greater Than]]
|-
|-
|  0  ||  0  ||  1  ||  1  || Left argument
|  0  ||  0  ||  1  ||  1  || Left argument
|-
|-
|  0  ||  1  ||  0  ||  0  || <source lang=apl inline><</source> [[Less Than]], <source lang=apl inline>|</source> [[Residue]]
|  0  ||  1  ||  0  ||  0  || <syntaxhighlight lang=apl inline><</syntaxhighlight> [[Less Than]], <syntaxhighlight lang=apl inline>|</syntaxhighlight> [[Residue]]
|-
|-
|  0  ||  1  ||  0  ||  1  || Right argument
|  0  ||  1  ||  0  ||  1  || Right argument
|-
|-
|  0  ||  1  ||  1  ||  0  || <source lang=apl inline>≠</source> [[Not Equal]]
|  0  ||  1  ||  1  ||  0  || <syntaxhighlight lang=apl inline>≠</syntaxhighlight> [[Not Equal]]
|-
|-
|  0  ||  1  ||  1  ||  1  || <source lang=apl inline>∨</source> [[Or]], <source lang=apl inline>⌈</source> [[Maximum]]
|  0  ||  1  ||  1  ||  1  || <syntaxhighlight lang=apl inline>∨</syntaxhighlight> [[Or]], <syntaxhighlight lang=apl inline>⌈</syntaxhighlight> [[Maximum]]
|-
|-
|  1  ||  0  ||  0  ||  0  || <source lang=apl inline>⍱</source> [[Nor]]
|  1  ||  0  ||  0  ||  0  || <syntaxhighlight lang=apl inline>⍱</syntaxhighlight> [[Nor]]
|-
|-
|  1  ||  0  ||  0  ||  1  || <source lang=apl inline>=</source> [[Equal]]
|  1  ||  0  ||  0  ||  1  || <syntaxhighlight lang=apl inline>=</syntaxhighlight> [[Equal]]
|-
|-
|  1  ||  0  ||  1  ||  0  || Right argument negation
|  1  ||  0  ||  1  ||  0  || Right argument negation
|-
|-
|  1  ||  0  ||  1  ||  1  || <source lang=apl inline>≥</source> [[Greater Than or Equal]], <source lang=apl inline>*</source> [[Power]]
|  1  ||  0  ||  1  ||  1  || <syntaxhighlight lang=apl inline>≥</syntaxhighlight> [[Greater Than or Equal]], <syntaxhighlight lang=apl inline>*</syntaxhighlight> [[Power]]
|-
|-
|  1  ||  1  ||  0  ||  0  || Left argument negation
|  1  ||  1  ||  0  ||  0  || Left argument negation
|-
|-
|  1  ||  1  ||  0  ||  1  || <source lang=apl inline>≤</source> [[Less Than or Equal]], <source lang=apl inline>!</source> [[Binomial]]
|  1  ||  1  ||  0  ||  1  || <syntaxhighlight lang=apl inline>≤</syntaxhighlight> [[Less Than or Equal]], <syntaxhighlight lang=apl inline>!</syntaxhighlight> [[Binomial]]
|-
|-
|  1  ||  1  ||  1  ||  0  || <source lang=apl inline>⍲</source> [[Nand]]
|  1  ||  1  ||  1  ||  0  || <syntaxhighlight lang=apl inline>⍲</syntaxhighlight> [[Nand]]
|-
|-
|  1  ||  1  ||  1  ||  1  || Constant 1
|  1  ||  1  ||  1  ||  1  || Constant 1
Line 84: Line 84:
== Boolean optimization ==
== 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.
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. Later APLs implemented with bit Booleans include [[APL\3000]], [[SHARP APL]], [[Dyalog APL]], and [[dzaima/APL]].


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.
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.
Line 91: Line 91:
* [[Dyalog '08]] (05): [[Roger Hui]], [https://dyalog.tv/Dyalog08/?v=k8Wt5sDDzgI "Performance Improvements in Dyalog: A Case Study"]
* [[Dyalog '08]] (05): [[Roger Hui]], [https://dyalog.tv/Dyalog08/?v=k8Wt5sDDzgI "Performance Improvements in Dyalog: A Case Study"]
* [[Dyalog '16]] U08: [[Bob Bernecky]], [https://dyalog.tv/Dyalog16/?v=G2g13YKjWes "A Compendium of SIMD Boolean Array Algorithms in APL"]
* [[Dyalog '16]] U08: [[Bob Bernecky]], [https://dyalog.tv/Dyalog16/?v=G2g13YKjWes "A Compendium of SIMD Boolean Array Algorithms in APL"]
* [[Dyalog '17]] D08: Marshall Lochbaum, [https://dyalog.tv/Dyalog17/?v=2KnrDmZov4U "Moving Bits Faster in Dyalog 16.0"]
* [[Dyalog '17]] D08: [[Marshall Lochbaum]], [https://dyalog.tv/Dyalog17/?v=2KnrDmZov4U "Moving Bits Faster in Dyalog 16.0"]
* Dyalog Blog: Marshall Lochbaum, [https://www.dyalog.com/blog/2018/06/expanding-bits-in-shrinking-time/ "Expanding Bits in Shrinking Time"]
* Dyalog Blog: [[Marshall Lochbaum]], [https://www.dyalog.com/blog/2018/06/expanding-bits-in-shrinking-time/ "Expanding Bits in Shrinking Time"]


Because they are so small relative to CPU registers, Booleans can make [[wikipedia:SIMD|SIMD]] (Single Instruction Multiple Data) techniques viable even in processors with no dedicated SIMD unit. Programming in this way is called [[wikipedia:SWAR|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.
Because they are so small relative to CPU registers, Booleans can make [[wikipedia:SIMD|SIMD]] (Single Instruction Multiple Data) techniques viable even in processors with no dedicated SIMD unit. Programming in this way is called [[wikipedia:SWAR|SWAR]] (SIMD Within a Register), and is considerably easier when working with bit Booleans than when working with integers. While most processors now have SIMD registers and instructions, current SIMD implementations don't provide all the bitwise operations that are available for ordinary registers, such as addition or bitwise shifts on entire registers. Boolean SWAR programming can be useful to more easily develop algorithms which are fast (often beating dedicated SIMD optimizations with each Boolean stored in a byte) while remaining architecture independent.


== External links ==
== External links ==


* [[Bob Smith]], [http://www.sudleyplace.com/APL/boolean.pdf "Boolean Functions"]
* Jonathan Barman, [http://archive.vector.org.uk/trad/v011/barman011_127.pdf APL and Partitioned Data] (a follow-up on Smith's paper)
* [[Eugene McDonnell]], [https://www.jsoftware.com/papers/eem/caret.htm "The Caret and the Stick Functions"] (on classifying Boolean functions).
* [[Eugene McDonnell]], [https://www.jsoftware.com/papers/eem/caret.htm "The Caret and the Stick Functions"] (on classifying Boolean functions).
* [[Phil Last]], [http://archive.vector.org.uk/art10501140 "Boolean Reductions"]
* [[John Scholes]], [https://www.dyalog.com/blog/2014/10/data-driven-conditionals-2/ "Data-driven Conditionals"]


* [[John Scholes]], [https://www.dyalog.com/blog/2014/10/data-driven-conditionals-2/ "Data-driven Conditionals"]
{{APL features}}[[Category:Numbers]]

Latest revision as of 22:10, 10 September 2022

0 1

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. Later APLs implemented with bit Booleans include APL\3000, SHARP APL, Dyalog APL, and dzaima/APL.

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:

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. While most processors now have SIMD registers and instructions, current SIMD implementations don't provide all the bitwise operations that are available for ordinary registers, such as addition or bitwise shifts on entire registers. Boolean SWAR programming can be useful to more easily develop algorithms which are fast (often beating dedicated SIMD optimizations with each Boolean stored in a byte) while remaining architecture independent.

External links


APL features [edit]
Built-ins Primitives (functions, operators) ∙ Quad name
Array model ShapeRankDepthBoundIndex (Indexing) ∙ AxisRavelRavel orderElementScalarVectorMatrixSimple scalarSimple arrayNested arrayCellMajor cellSubarrayEmpty arrayPrototype
Data types Number (Boolean, Complex number) ∙ Character (String) ∙ BoxNamespaceFunction array
Concepts and paradigms Conformability (Scalar extension, Leading axis agreement) ∙ Scalar function (Pervasion) ∙ Identity elementComplex floorArray ordering (Total) ∙ Tacit programming (Function composition, Close composition) ∙ GlyphLeading axis theoryMajor cell search
Errors LIMIT ERRORRANK ERRORSYNTAX ERRORDOMAIN ERRORLENGTH ERRORINDEX ERRORVALUE ERROREVOLUTION ERROR