Content deleted Content added
mNo edit summary Tags: Reverted Visual edit |
Restored revision 1029343138 by Jason Quinn (talk): Not English |
||
Line 1:
{{Programming paradigms}}
In [[computer science]], '''array programming''' refers to solutions which allow the application of operations to an entire set of values at once. Such solutions are commonly used in [[computational science|scientific]] and [[engineering]] settings.
==Concepts of array==
The fundamental idea behind array programming is that operations apply at once to an entire set of values. This makes it a [[high-level programming language|high-level programming]] model as it allows the programmer to think and operate on whole aggregates of data, without having to resort to explicit loops of individual scalar operations.
[[Kenneth E. Iverson]] described the rationale behind array programming (actually referring to APL) as follows:<ref
{{quote|most programming languages are decidedly inferior to mathematical notation and are little used as tools of thought in ways that would be considered significant by, say, an applied mathematician.
The thesis is that the advantages of executability and universality found in programming languages can be effectively combined, in a single coherent language, with the advantages offered by mathematical notation. it is important to distinguish the difficulty of describing and of learning a piece of notation from the difficulty of mastering its implications. For example, learning the rules for computing a matrix product is easy, but a mastery of its implications (such as its associativity, its distributivity over addition, and its ability to represent linear functions and geometric operations) is a different and much more difficult matter.
Indeed, the very suggestiveness of a notation may make it seem harder to learn because of the many properties it suggests for explorations.
[...]
Users of computers and programming languages are often concerned primarily with the efficiency of execution of algorithms, and might, therefore, summarily dismiss many of the algorithms presented here. Such dismissal would be short-sighted since a clear statement of an algorithm can usually be used as a basis from which one may easily derive a more efficient algorithm.}}
The basis behind array programming and thinking is to find and exploit the properties of data where individual elements are similar or adjacent. Unlike object orientation which implicitly breaks down data to its constituent parts (or [[scalar (computing)|scalar]] quantities), array orientation looks to group data and apply a uniform handling.
[[Function rank]] is an important concept to array programming languages in general, by analogy to [[tensor]] rank in mathematics: functions that operate on data may be classified by the number of dimensions they act on. Ordinary multiplication, for example, is a scalar ranked function because it operates on zero-dimensional data (individual numbers). The [[cross product]] operation is an example of a vector rank function because it operates on vectors, not scalars. [[Matrix multiplication]] is an example of a 2-rank function, because it operates on 2-dimensional objects (matrices). [[Reduce (higher-order function)|Collapse operators]] reduce the dimensionality of an input data array by one or more dimensions. For example, summing over elements collapses the input array by 1 dimension.
==Uses==
Array programming is very well suited to [[implicit parallelization]]; a topic of much research nowadays. Further, [[Intel]] and compatible CPUs developed and produced after 1997 contained various instruction set extensions, starting from [[MMX (instruction set)|MMX]] and continuing through [[SSSE3]] and [[3DNow!]], which include rudimentary [[SIMD]] array capabilities. Array processing is distinct from [[parallel computing|parallel processing]] in that one physical processor performs operations on a group of items simultaneously while parallel processing aims to split a larger problem into smaller ones ([[MIMD]]) to be solved piecemeal by numerous processors. Processors with two or more cores are increasingly common today.
==Languages==
==
In scalar languages such as [[C (programming language)|C]] and [[Pascal (programming language)|Pascal]], operations apply only to single values, so ''a''+''b'' expresses the addition of two numbers. In such languages, adding one array to another requires indexing and looping, the coding of which is tedious.
▲مثالهای متعارف زبانهای برنامه نویسی آرایه عبارتند از: Fortran ، APL و J. سایر موارد شامل: [[A+ (programming language)|A +]]، [[Analytica (software)|Analytica]]، [[Chapel (programming language)|Chapel]]، [[IDL (programming language)|IDL]]، Julia، [[K (programming language)|K]]، Klong، [[Q (programming language from Kx Systems)|Q]]، Mata، [[MATLAB]]، MOLSF، NumPy، [[Perl Data Language|PDL]]، R، [[S-Lang|S -Lang]] ، [[SAC programming language|SAC]] ، [[Nial programming language|Nial]] ، [[ZPL (programming language)|ZPL]] ، [[TI-BASIC]], [[GNU Octave]]
<syntaxhighlight lang="c">
for (i = 0; i < n; i++)
Line 37 ⟶ 34:
</syntaxhighlight>
In array-based languages, for example in Fortran, the nested for-loop above can be written in array-format in one line,
<syntaxhighlight lang="fortran">
a = a + b
</syntaxhighlight>
or alternatively, to emphasize the array nature of the objects,
<syntaxhighlight lang="fortran">
a(:,:) = a(:,:) + b(:,:)
</syntaxhighlight>
While scalar languages like C do not have native array programming elements as part of the language proper, this does not mean programs written in these languages never take advantage of the underlying techniques of vectorization (i.e., utilizing a CPU's [[SIMD|vector-based instructions]] if it has them or by using multiple CPU cores). Some C compilers like [[GNU Compiler Collection|GCC]] at some optimization levels detect and vectorize sections of code that its heuristics determine would benefit from it. Another approach is given by the [[OpenMP]] API, which allows one to parallelize applicable sections of code by taking advantage of multiple CPU cores.
===Array languages===
In array languages, operations are generalized to apply to both scalars and arrays. Thus, ''a''+''b'' expresses the sum of two scalars if ''a'' and ''b'' are scalars, or the sum of two arrays if they are arrays.
====Ada
<syntaxhighlight lang="ada">
A := A + B;
</syntaxhighlight>
====APL
APL uses single character Unicode symbols with no syntactic sugar.
<syntaxhighlight lang="apl">
A ← A + B
</syntaxhighlight>
This operation works on arrays of any rank (including rank 0), and on a scalar and an array. Dyalog APL extends the original language with [[augmented assignment]]s:
<syntaxhighlight lang="apl">
A +← B
</syntaxhighlight>
====Analytica
Analytica
<pre>
A := A + B;
</pre>
====BASIC
[[Dartmouth BASIC]] had MAT statements for matrix and array manipulation in its third edition (1966).
<syntaxhighlight lang="basic">
DIM A(4),B(4),C(4)
Line 88 ⟶ 82:
</syntaxhighlight>
====Mata
[[Stata]]'s matrix programming language Mata supports array programming. Below, we illustrate addition, multiplication, addition of a matrix and a scalar, element by element multiplication, subscripting, and one of Mata's many inverse matrix functions.
<syntaxhighlight lang="stata">
. mata:
Line 111 ⟶ 105:
+-------------+
: C = J(3,2,1) //
: C
Line 157 ⟶ 151:
+-----------+
: H = F[(2\1), (1, 2)] //
: //
: H
1 2
Line 167 ⟶ 161:
+-----------+
: I = invsym(F'*F) //
: //
: I
[symmetric]
Line 182 ⟶ 176:
</syntaxhighlight>
====MATLAB
<syntaxhighlight lang="matlab">
A = A + B;
</syntaxhighlight>
A variant of the MATLAB language is the [[GNU Octave]] language, which extends the original language with augmented assignments:
<syntaxhighlight lang="octave">
A += B;
</syntaxhighlight>
Both MATLAB and GNU Octave natively support linear algebra operations such as matrix multiplication, [[matrix inversion]], and the numerical solution of [[system of linear equations]], even using the [[Moore–Penrose pseudoinverse]].<ref>{{cite web |title= GNU Octave Manual. Arithmetic Operators. |url= https://www.gnu.org/software/octave/doc/interpreter/Arithmetic-Ops.html |access-date= 2011-03-19}}</ref><ref>{{cite web |title= MATLAB documentation. Arithmetic Operators. |url= http://www.mathworks.com/help/techdoc/ref/arithmeticoperators.html |access-date= 2011-03-19}}</ref>
The [[Nial]] example of the inner product of two arrays can be implemented using the native matrix multiplication operator. If <code>a</code> is a row vector of size [1 n] and <code>b</code> is a corresponding column vector of size [n 1].
a * b;
The inner product between two matrices having the same number of elements can be implemented with the auxiliary operator <code>(:)</code>, which reshapes a given matrix into a column vector, and the [[transpose]] operator <code>'</code>:
A(:)' * B(:);
====rasql====
The [[Rasdaman#Raster Query Language|rasdaman query language]] is a database-oriented array-programming language. For example, two arrays could be added with the following query:
<syntaxhighlight lang="sql">
SELECT A + B
Line 211 ⟶ 205:
====R====
The R language supports [[array paradigm]] by default. The following example illustrates a process of multiplication of two matrices followed by an addition of a scalar (which is, in fact, a one-element vector) and a vector:
<syntaxhighlight lang="r">
> A <- matrix(1:6, nrow=2) !!
> A
[,1] [,2] [,3]
[1,] 1 3 5
[2,] 2 4 6
> B <- t( matrix(6:1, nrow=2) ) # t()
> B
[,1] [,2]
Line 234 ⟶ 228:
[1,] 29 20
[2,] 41 29
> D + c(1, 1) # c()
[,1] [,2]
[1,] 30 21
Line 240 ⟶ 234:
</syntaxhighlight>
==Mathematical reasoning and language notation==
The matrix left-division operator concisely expresses some semantic properties of matrices. As in the scalar equivalent, if the ([[determinant]] of the) coefficient (matrix) <code>A</code> is not null then it is possible to solve the (vectorial) equation <code>A * x = b</code> by left-multiplying both sides by the [[matrix inversion|inverse]] of <code>A</code>: <code>A<sup>−1</sup></code> (in both MATLAB and GNU Octave languages: <code>A^-1</code>). The following mathematical statements hold when <code>A</code> is a [[matrix rank#Properties|full rank]] [[square matrix#Square matrices|square matrix]]:
:<code>A^-1 *(A * x)==A^-1 * (b)</code>
:<code>(A^-1 * A)* x ==A^-1 * b </code> (matrix-multiplication [[
:<code>x = A^-1 * b</code>
where <code>==</code> is the equivalence [[relational operator]].
The previous statements are also valid MATLAB expressions if the third one is executed before the others (numerical comparisons may be false because of round-off errors).
If the system is overdetermined - so that <code>A</code> has more rows than columns - the pseudoinverse <code>A<sup>+</sup></code> (in MATLAB and GNU Octave languages: <code>pinv(A)</code>) can replace the inverse <code>A<sup>−1</sup></code>, as follows:
:<code>pinv(A) *(A * x)==pinv(A) * (b)</code>
:<code>(pinv(A) * A)* x ==pinv(A) * b</code> (
:<code>x = pinv(A) * b</code>
However, these solutions are neither the most concise ones (e.g. still remains the need to notationally differentiate overdetermined systems) nor the most computationally efficient. The latter point is easy to understand when considering again the scalar equivalent <code>a * x = b</code>, for which the solution <code>x = a^-1 * b</code> would require two operations instead of the more efficient <code>x = b / a</code>.
The problem is that generally matrix multiplications are not [[commutativity|commutative]] as the extension of the scalar solution to the matrix case would require:
:<code>(a * x)/ a ==b / a</code>
:<code>(x * a)/ a ==b / a</code> (
:<code>x * (a / a)==b / a</code> (
:<code>x = b / a</code>
The MATLAB language introduces the left-division operator <code>\</code> to maintain the essential part of the analogy with the scalar case, therefore simplifying the mathematical reasoning and preserving the conciseness:
:<code>A \ (A * x)==A \ b</code>
:<code>(A \ A)* x ==A \ b</code> (
:<code>x = A \ b</code>
Returning to the previous quotation of Iverson, the rationale behind it should now be evident: {{quote|it is important to distinguish the difficulty of describing and of learning a piece of notation from the difficulty of mastering its implications. For example, learning the rules for computing a matrix product is easy, but a mastery of its implications (such as its associativity, its distributivity over addition, and its ability to represent linear functions and geometric operations) is a different and much more difficult matter.
Indeed, the very suggestiveness of a notation may make it seem harder to learn because of the many properties it suggests for explorations.}}
The use of specialized and efficient libraries to provide more terse abstractions is also common in other programming languages. In [[C++]] several linear algebra libraries exploit the language's ability to [[operator overloading|overload operators]]. In some cases a very terse abstraction in those languages is explicitly influenced by the array programming paradigm, as the [[Armadillo (C++ library)|Armadillo]] and [[Blitz++]] libraries do.<ref name=":1">{{cite web |title= Reference for Armadillo 1.1.8. Examples of Matlab/Octave syntax and conceptually corresponding Armadillo syntax. |url= http://arma.sourceforge.net/docs.html#syntax |access-date= 2011-03-19}}</ref><ref name=":2">{{cite web |title= Blitz++ User's Guide. 3. Array Expressions. |url= http://www.oonumerics.org/blitz/docs/blitz_3.html#SEC80 |access-date= 2011-03-19 |archive-url= https://web.archive.org/web/20110323013142/http://www.oonumerics.org/blitz/docs/blitz_3.html#SEC80 |archive-date= 2011-03-23 |url-status= dead }}</ref>▼
==Third-party libraries==
▲The use of specialized and efficient libraries to provide more terse abstractions is also common in other programming languages. In [[C++]] several linear algebra libraries exploit the language's ability to [[operator overloading|overload operators]]. In some cases a very terse abstraction in those languages is explicitly influenced by the array programming paradigm, as the [[Armadillo (C++ library)|Armadillo]] and [[Blitz++]] libraries do.<ref
==See also==
* [[Array slicing
* [[List of programming languages by type#Array languages|
==References==
| |||