Array Predicates: Difference between revisions

From NARS2000
Jump to navigationJump to search
No edit summary
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>L⌽R</apll> and <apll>⌽R</apll>) and grade up/down (<apll>⍋R</apll> and <apll>⍒R</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.
Bernecky has defined several array predicate properties, one of which has been implemented in NARS so far.
Line 5: Line 5:
== Permutation Vectors ==
== Permutation Vectors ==


In this case, index generator (<apll>⍳R</apll>) produces a Permutation Vector, as does 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 Vectors.  Subsequent use of such arrays maintains that property when operated on by rotate/reversal and grade up/down.  Moreover, the two grade (<apll>⍋PV</apll> and <apll>⍒PV</apll>) and the index of (<apll>PV⍳R</apll>) primitives use a much faster (linear) algorithm than they would normally use when the appropriate argument is a Permutation Vector.
In this case, index generator (<apll>⍳R</apll>) produces a Permutation Vector, as does 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 Vectors.  Subsequent use of such arrays maintains that property when operated on by rotate/reversal and grade up/down.  Moreover, the two grade (<apll>⍋PV</apll> and <apll>⍒PV</apll>) and the index of (<apll>PV⍳R</apll>) primitives use a much faster (linear) algorithm than they would normally, given that the appropriate argument is a Permutation Vector.

Revision as of 19:51, 18 August 2008

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, one of which has been implemented in NARS so far.

Permutation Vectors

In this case, index generator (⍳R) produces a Permutation Vector, as does 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 and grade up/down. Moreover, the two grade (⍋PV and ⍒PV) and the index of (PV⍳R) primitives use a much faster (linear) algorithm than they would normally, given that the appropriate argument is a Permutation Vector.