View source for Rank (J programming language)

'''Rank''' is a generalization of [[Control flow#Loops|looping]] as used in scalar (non-[[Array data structure|array]]-oriented) [[Programming language|programming language]]s.<ref>{{Cite web |url=http://www.ccs.neu.edu/home/jrslepak/typed-j.pdf |title=An array-oriented language with static rank polymorphism |last=Slepak |first=Justin |last2=Shivers |first2=Olin |last3=Manolios |first3=Panagiotis}}</ref><ref>{{Cite web |url=http://www.jsoftware.com/help/jforc/loopless_code_i_verbs_have_r.htm#_Toc191734331 |title=Loopless Code I: Verbs Have Rank |author=<!-- Unstated --> |website=Jsoftware}}</ref> It is also a generalization of ''[[Map (higher-order function)|mapcar]]'' in the language ''[[Lisp (programming language)|Lisp]]''<ref>{{Cite web |url=https://www.gnu.org/software/emacs/manual/html_node/eintr/mapcar.html |title=The mapcar Function |website=Free Software Foundation}}</ref> and ''map'' in modern [[Functional programming|functional programming]] languages, and a generalization of scalar extension, inner ([[Matrix (mathematics)|matrix]]) product, and outer product in APL\360. The canonical implementation of rank may be the language ''[[J (programming language)|J]]'', but it is also available in Dyalog APL, the [[Organization:International Organization for Standardization|International Organization for Standardization]] (ISO) [[Technical standard|technical standard]] on Extended APL, and NARS2000.

Rank has several different meanings. In general, the concept of ''rank'' is used to treat an orthogonal array in terms of its subarrays.<ref>{{Cite conference |url=https://dl.acm.org/citation.cfm?id=55632 |last=Bernecky |first=R. |title=An Introduction to Function Rank |book-title=APL88 Conference Proceedings, APL Quote Quad |volume=18 |number=2 |date=December 1987}}</ref> For example, a two-dimensional array may be dealt with at rank 2 as the entire matrix, or at rank 1 to work with its implicit one-dimensional columns or rows, or at rank 0 to work at the level of its individual atoms.

*''Noun rank'' – The rank of a noun is a nonnegative [[Integer|integer]].
*''Verb rank'' – The rank of a verb is a list of three integers.  
*''The rank conjunction'' – The rank conjunction (<code>"</code>) is used to derive a verb with a specific rank.

== Rank as a generalization of looping ==

Understanding rank requires knowing some very basic array-oriented programming concepts. In most array-based languages, reduction is denoted with a forward slash <code>/</code>. In J, the slash takes a left argument of the function and a right argument of the array to be reduced by that function.
<source lang="text">
   +/ 1 2 3
6
</source>

The result is <code>1 + 2 + 3</code>, as expected.

An N-dimensional integer array can also be created with <code>i.</code> which takes a vector of integers as its arguments.  The number of integers defines the dimension and the absolute value of each integer defines the length of the corresponding dimension.
<source lang="j">
   i. 3
0 1 2

   i. 2 3
0 1 2
3 4 5

   i. 2 3 4
 0  1  2  3
 4  5  6  7
 8  9 10 11

12 13 14 15
16 17 18 19
20 21 22 23
</source>

Now let's reduce a two-dimensional array by addition.
<source lang="j">
   +/ i. 2 3
3 5 7
</source>

The result is <code>0 1 2 + 3 4 5</code>, as expected. Reduction runs down each column, adding together all the numbers in that column.

This application of <code>+/</code> to a two-dimensional array corresponds to the C code fragment:<ref>{{Cite web |url=http://www.jsoftware.com/help/jforc/loopless_code_i_verbs_have_r.htm#_Toc191734335 |title=Controlling Verb Execution By Specifying a Rank |author=<!-- Unstated --> |website=Jsoftware}}</ref>
<source lang="c">
for(j = 0; j < 3; ++j) {
    sum[j] = 0;
}
for(i = 0; i < 2; ++i) {
    for(j = 0; j < 3; ++j) {
        sum[j] += array[i][j];
    }
}
</source>

Suppose we wanted to add up the items of each row, as in the C code fragment:
<source lang="c">
for(i = 0; i < 2; ++i) {
    sum[i] = 0;
    for(j = 0; j < 3; ++j) {
        sum[i] += array[i][j];
    }
}
</source>

To produce the result <code>3 12</code>.  We can do this in J without looping simply by using rank.
<source lang="j">
   +/"1 i. 2 3
3 12
</source>

To illustrate further how rank works in J, we can see the original expression is rank 2. The operator is mapped at the highest rank to the array.
<source lang="j">
   +/"2 i. 2 3
3 5 7
</source>

It is common to refer to the lower-dimensional arrays by these names,<ref>{{cite arXiv |title=Introduction to Tensor Decompositions and their Applications in Machine Learning |last=Rabanser |first=Stephan |last2=Shchur |first2=Oleksandr |last3=Günnemann |first3=Stephan |date=2017-11-29 |class=stat.ML |eprint=1711.10781 }}</ref> though they are disputed sometimes.<ref>{{cite web |url=https://news.ycombinator.com/item?id=14183484 |title=HPTT: A High-Performance Tensor Transposition C++ |author=kgwgk |author2=nabla9 |author3=azag0 |author4=tome |author5=radarsat1 |date=2017-04-24 |website=Hacker News |publisher=Y Combinator |access-date=2019-12-10}}</ref>

:{| class="wikitable"
|-
!style="text-align:center;" |Name
!style="text-align:center;" |Rank
|-
|style="text-align:center;" |Atom or scalar
|style="text-align:center;" |0
|-
|style="text-align:center;" |Vector or list
|style="text-align:center;" |1
|-
|style="text-align:center;" |Table or matrix
|style="text-align:center;" |2
|-
|style="text-align:center;" |Tensor or cube
|style="text-align:center;" |3
|}

== Noun rank ==
Nouns, in J, are [[Array data type|arrays]].  The rank of a noun is the number of dimensions of that array.  The derived verb <code>#@$</code> determines the rank of a noun.

== Verb rank ==

Verbs, in J, are functions which take noun arguments and produce noun results.  The rank of a verb controls how the verb is applied to nouns with ranks greater than 0.  This verb rank is expressed as three numbers:

# Rank for the monad case; for example, <code>&minus;y</code> uses <code>&minus;</code> as a [[Monad (functional programming)#History|monad]]
# Rank for the left argument for the dyad case; for example, <code>x&minus;y</code> uses <code>&minus;</code> as a [[Monad (functional programming)#History|dyad]]
# Rank for the right argument for the dyad case

In all cases, there is some underlying verb definition which applies to ''cells'', which are subarrays of the indicated rank.  Or, if the argument does not have that many dimensions, the entire argument.

In verbs, negative rank is interpreted as the rank of the noun supplied for that argument less the indicated value.  (But never less than zero.)

: For example, a verb with monadic rank of negative one when given an argument of rank 3, breaks the argument down into a list of rank 2 arrays.  The verb's body is applied once to each of these two-dimensional subarrays.

In the context of a specific verb and a specific noun, the dimensions of that noun are divided into the sequence of prefix dimensions, called the ''frame'', and the sequence of suffix dimensions, called the ''cells''.  Positive verb ranks indicate the number of cell dimensions, negative verb ranks indicate the number of frame dimensions.

In the dyadic case, there are two frames: one for the left argument, and one for the right argument.  These frames must agree.  If the frames are not identical, one must be a prefix of the other; e.g. {{code|(i. 2 3) *"0 1 i. 2 3 4|j}} multiplies each scalar (zero-dimensional item) on the left by each vector (one-dimensional item) on the right.  The result of evaluating this verb will have the dimensions of the longest frame as the prefix dimensions of its result.  Trailing result dimensions, if any, would be the result of the verb applied to the relevant cell(s).  In degenerate cases, where the arguments do not have sufficient dimensions, the rank of the verb is effectively reduced (which would influence its result).

For example,
<source lang="apl">
   10 + 4 5 6
 14 15 16</source>

Here, the verb <code>+</code> has a rank of 0 0 0, the left argument has a rank of 0, and the right argument has a rank of 1 (with a dimension of 3).  Thus, the left argument has a rank 0 frame and the right argument has a rank 1 frame (with a dimension 3).  The left argument's (empty) frame is a valid suffix for the right argument's frame, so this is a valid operation.  The result has a rank of 1 and a dimension of 3.

== The rank conjunction ==

The rank conjunction takes a verb left argument and a noun right argument to create a new verb. The noun right argument consists of up to three numbers specifying the monadic rank, the dyadic left rank, and the dyadic right rank, respectively.<ref>{{Cite web |url=https://code.jsoftware.com/wiki/Essays/Rank#Verb_Rank |title=Essays: Rank |last=Burke |first=Chris |date=2014-09-12 |website=Jsoftware}}</ref>

If the right argument is only two numbers, they are taken as the ranks for the dyadic case: the first number is the rank of the left argument and the second number is the rank of the right argument.  So, if we want to add a vector to each vector in a matrix:
<source lang="j">
   1 2 3 +"1 1 i. 3 3
1 3  5
4 6  8
7 9 11
</source>
If we want instead to add each scalar on the left to each vector on the right, we would do it this way:
<source lang="j">
   1 2 3 +"0 1 i. 3 3
1  2  3
5  6  7
9 10 11
</source>
If the right argument is only one number, it is taken as the rank for all three cases.

If the right argument is a verb, its rank is used.  For example, these all derive the same verb:

* <source lang="j" inline>+"0 0 0</source>
* <source lang="j" inline>+"0 0</source>
* <source lang="j" inline>+"0</source>
* <source lang="j" inline>+"+</source>

If the left argument to the rank conjunction is a noun, a constant verb is created.  The body of this verb ignores the values of any arguments and always produces a result which is that noun.

== References ==
{{Reflist}}
{{ulist|
{{Cite thesis |type=PhD |last=Abrams |first=P.S. |date=February 1970 |url=http://www.slac.stanford.edu/pubs/slacreports/reports07/slac-r-114.pdf |title=An APL Machine |website=Stanford University |section=§II.E}}
|
Backus, J.W., Can Programming be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs (https://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf), Communications of the ACM, Volume 21, Number 8, 1978-08.; §11.3.3.
|
Bernecky, R., An Introduction to Function Rank (https://dl.acm.org/citation.cfm?id=55632), APL88 Conference Proceedings, APL Quote Quad, Volume 18, Number 2, 1987-12.
|
{{Cite conference |url=http://www.jsoftware.com/papers/opea.htm |title=Operators and Enclosed Arrays |last=Bernecky |first=R. |last2=Iverson |first2=K.E. |date=6–8 October 1980 |website=Jsoftware |conference=1980 APL Users Meeting |book-title=Proceedings}}
|
{{Cite web |url=http://www.jsoftware.com/papers/satn45.htm |title=SATN 45: Language Extensions of May 1983 |last=Bernecky |first=R. |last2=Iverson |first2=K.E. |last3=McDonnell |first3=E.E. |last4=Metzger |first4=R.C. |last5=Schueler |first5=J.H. |date=1983-05-02 |website=Jsoftware |publisher=I.P. Sharp Associates Limited}}
|
Brown, J.A., The Principles of APL2 (http://www.softwarepreservation.org/projects/apl/Papers/PRINCIPLESOFAPL2), TR 03.247, IBM Santa Teresa Laboratory, San Jose, California, 1984-03; §20.0.
|
Dyalog, Dyalog APL Version 14.0 Release Notes (http://www.dyalog.com/dyalog-version-140.htm), Dyalog Limited, 2015.
|
Hui, R.K.W., Rank and Uniformity (http://www.jsoftware.com/papers/rank.htm), APL95 Conference Proceedings, APL Quote Quad, Volume 25, Number 4, 1995-06.
|
Hui, R.K.W., Remembering Ken Iverson (https://keiapl.org/rhui/remember.htm), 2004-11.
|
Hui, R.K.W., Inner Product—An Old/New Problem (http://www.jsoftware.com/papers/innerproduct/ip.htm), British APL Association Conference 2009, 2009-06-08.
|
Iverson, K.E., Operators and Functions (http://www.jsoftware.com/papers/opfns.htm), Research Report #RC7091, IBM, 1978-04-26.
|
Iverson, K.E., A Dictionary of APL (http://www.jsoftware.com/papers/APLDictionary.htm), APL Quote Quad, Volume 18, Number 1, 1987-09.
|
Iverson, K.E., A Personal View of APL (http://www.jsoftware.com/papers/APLPersonalView1.htm), IBM Systems Journal, Volume 30, Number 4, 1991-12.
|
Slepak,Justin; Shivers, Olin; Manolios, Panagiotis, An array-oriented language with static rank polymorphism (http://www.ccs.neu.edu/home/jrslepak/typed-j.pdf).}}

== External links ==
*[http://jsoftware.com/help/dictionary/intro20.htm J Dictionary entry for "rank"]
*[http://jsoftware.com/help/learning/07.htm Rank in "Learning J"]

{{APL programming language}}

[[Category:APL programming language family]]

{{Sourceattribution|Rank (J programming language)}}