Array Predicates: Difference between revisions

From NARS2000
Jump to navigationJump to search
(New page: This clever idea of Bob Bernecky's [http://www.snakeisland.com/predicat.pdf] provides a performance improvement for certain expressions by marking certain arrays with special properties. ...)
 
No edit summary
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
This clever idea of Bob Bernecky's [http://www.snakeisland.com/predicat.pdf] provides a performance improvement for certain expressions by marking certain arrays with special properties.  For example, a permutation vector [http://mathworld.wolfram.com/Permutation.html] has the property that it is invariant under various APL primitives such as rotate/reversal (<apll></apll>) and grade up/down (<apll>⍋ ⍒</apll>).
This clever idea of Bob Bernecky's [http://www.snakeisland.com/predicat.pdf] provides a performance improvement for certain expressions by marking certain arrays with special properties.  For example, the property of being a Permutation Vector [http://mathworld.wolfram.com/Permutation.html] is invariant (is still a Permutation Vector, albeit a different one) under various APL primitives such as rotate/reversal (<apll>L⌽PV</apll> and <apll>⌽PV</apll>) and grade up/down (<apll>⍋PV</apll> and <apll>⍒PV</apll>).


Bernecky has defined several array predicate properties, one of which has been implemented in NARS so far:  permutation vectors.
Bernecky has defined several array predicate properties, two of which have been implemented in NARS2000 so far.


In this case, monadic iota (<apll>{iota}</apll>) produces a permutation vector, as does deal (<apll>?</apll>) when the left and right arguments are the same, and are marked internally as suchFurther use of such arrays maintain that property when operated on by rotate/reversal and grade up/down.  Moreover, the grade primitive uses a much faster (linear) algorithm than it would normally use.
== Permutation Vectors ==
 
<p>In this case, index generator (<apll>⍳S</apll>) produces a Permutation Vector, as do the grade primitives (<apll>⍋V</apll> and <apll>⍒V</apll>), as well as deal (<apll>L?R</apll>) when the left and right arguments are the same &mdash; the results of these primitives are marked internally as Permutation VectorsSubsequent use of such arrays maintains that property when operated on by rotate/reversal (<apll>L⌽PV</apll> and <apll>⌽PV</apll>).  Moreover, the two grade (<apll>⍋PV</apll> and <apll>⍒PV</apll>) and the index of (<apll>PV⍳R</apll>) and membership (<apll>L∊PV</apll>) primitives use a much faster (linear) algorithm than they would normally, given that the lookup argument is a Permutation Vector.</p>
 
<p>In summary,</p>
 
<p>Set the bit in the result:  <apll>⍳S</apll>, <apll>⍋V</apll>, <apll>⍒V</apll>, and <apll>R?R</apll>.</p>
 
<p>Pass on the bit:  <apll>L⌽PV</apll> and <apll>⌽PV</apll>.</p>
 
<p>Read and take advantage of the bit:  <apll>⍋PV</apll>, <apll>⍒PV</apll>, <apll>PV⍳R</apll>, and <apll>L∊PV</apll>.</p>
 
== Example ==
 
<p>In the common expression <apll>⍋⍋R</apll>, the right hand grade sets the bit and the left hand grade reads it and uses a linear algorithm to produce the result.</p>
 
== All 2s ==
 
<p>Mostly for the Representation primitive (<apll>L⊤R</apll>), if the left argument is all 2s and the right argument is integer, the result can be represented as Boolean.</p>

Latest revision as of 01:16, 20 February 2011

This clever idea of Bob Bernecky's [1] provides a performance improvement for certain expressions by marking certain arrays with special properties. For example, the property of being a Permutation Vector [2] is invariant (is still a Permutation Vector, albeit a different one) under various APL primitives such as rotate/reversal (L⌽PV and ⌽PV) and grade up/down (⍋PV and ⍒PV).

Bernecky has defined several array predicate properties, two of which have been implemented in NARS2000 so far.

Permutation Vectors

In this case, index generator (⍳S) produces a Permutation Vector, as do the grade primitives (⍋V and ⍒V), as well as deal (L?R) when the left and right arguments are the same — the results of these primitives are marked internally as Permutation Vectors. Subsequent use of such arrays maintains that property when operated on by rotate/reversal (L⌽PV and ⌽PV). Moreover, the two grade (⍋PV and ⍒PV) and the index of (PV⍳R) and membership (L∊PV) primitives use a much faster (linear) algorithm than they would normally, given that the lookup argument is a Permutation Vector.

In summary,

Set the bit in the result: ⍳S, ⍋V, ⍒V, and R?R.

Pass on the bit: L⌽PV and ⌽PV.

Read and take advantage of the bit: ⍋PV, ⍒PV, PV⍳R, and L∊PV.

Example

In the common expression ⍋⍋R, the right hand grade sets the bit and the left hand grade reads it and uses a linear algorithm to produce the result.

All 2s

Mostly for the Representation primitive (L⊤R), if the left argument is all 2s and the right argument is integer, the result can be represented as Boolean.