Some Uses of { and } We believe that the design of APL was also affected in important respects by a number of procedures and circumstances. Firstly, from its inception APL has been developed by using it in a succession of areas. This emphasis on application clearly favors practicality and simplicity. The treatment of many different areas fostered generalization … — Falkoff and Iverson,
The Design of APL 0. Introduction This paper explores uses of the new primitives all,
from, select, and merge
({⍵, ⍺{⍵, v}⍵ and ⍺v}⍵).
Facilities of K.E. Iverson’s
A Dictionary of APL
[1986]
are exploited.
Brief explanations of the less
familiar aspects of the notation
are in Appendix A.
1. A Few Applications Examples here illustrate the meaning of { } . Some readers may wish to skip to Section 2, which defines { } directly, before returning. 1.1 Short Examples
1.2 Text Formatting Carim [1977] and Smith [1979] discussed the text formatting or “paragraphing” problem. Given: a string ⍵ of words separated by blanks, and a positive integer ⍺ of the desired width. Replace appropriate elements of ⍵ by the “new line” character nl , so that lines are no wider than ⍺ , and each line contains all the words that fit within the line. (To focus on essentials, assume words are at most ⍺ in length, and adjacent words are separated by exactly one blank.)Our solution has two constituents, both employing { and both of interest in their own right. classify: (⍴⍵)⍴(⍴⍺)↓(+\i<⍴⍺) i¨{}i←⍋⍺,,⍵ Nondecreasing vector ⍺ partitions the real numbers into contiguous intervals; classify computes the index of the interval which contains ⍵ . That is, if z←⍺ classify ⍵ , then ⍴z ←→ ⍴⍵ , and i{z is the least nonnegative integer such that (i{⍵)<(i{z){⍺ . (i{z is ⍴⍺ if (i{⍵)≥¯1{⍺ .) Examples: ¯1 0 2 4 7.5 classify 2 3 ¯1 0 2 4 7.5 classify ¯99 0 ¯1 0 2 4 7.5 classify ¯99 ¯1 99 2 1.5 2.5 6 7 7.5 0 1 5 3 2 3 4 4 5 The second constituent solves a version of the transitive closure problem. tc: (x⍳n)↑x←0{⍉{⍀(1 1+n)⍴n⌊⍵,n←⍴⍵ Integer vector ⍵ represents a directed acyclic graph, whose nodes art labelled ⍳0{⍴⍵ . i{⍵ is the terminus of the arc originating at node i . (If (i{⍵)≥⍴⍵ , node i has no outgoing arc.) tc⍵ computes the nodes reachable from node 0. For examp1e, x←1 3 4 6 7 8 9 10 12 13 15 15 15 15 15 (⍳0{⍴x),¨<x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 3 4 6 7 8 9 10 12 13 15 15 15 15 15 tc is useful in resolving multiple quotations, overlapping substring occurrences, and others, as well as in text formatting. Having classify and tc in hand, we are ready to solve the text formatting problem. fit: nl (¯1+(tc e classify ⍺+s){s)¨{}⍵ ⊣ e←1↓(s1),⍴⍵ ⊣ s←(l<¯1↓1,l)/⍳0{⍴⍵ ⊣ l←⍵∊' ' ⍺ is the maximum width of a line,
and ⍵ is a string.
First, compute s ,
the index of the starting letter of
each word; and e ,
one plus the index of the ending
letter of each word.
If a line were to start at word i ,
then the next line starts at the first word which
ends beyond i{⍺+s — at
word i{e classify ⍺+s . We
know the first line starts at word 0 ,
so the lines (except the first) start at
words t now is the time for all good men to chew up all the foobars in their country. the quick brown fox jumps over the lazy dog. 20 fit t 25 fit t now is the time for now is the time for all all good men to chew good men to chew up all up all the foobars the foobars in their in their country. country. the quick brown the quick brown fox fox jumps over the lazy jumps over the lazy dog. dog. 1.3 Latin Square Analysis of Variance latin: n×ss(mean,⍵)mean+/(>0 1 2⊃1 0 2⊃1 2 0)⍉x← ⍵(((0{⍺)⍳⍺),¨>{⍳¨>⍴⍺)¨{}(3⍴n)⍴0 ⊣ n←0{⍴⍺ mean: (+/⍵)÷¯1{1,⍴⍵ ss: ⍵+.*2 ⍺ is a Latin square, a matrix of 0{⍴⍺ symbols where each symbol occurs in a row (column) exactly once. Numeric matrix ⍵ are data from an experiment with design ⍺ : (<i,j){⍵ is the datum for row factor i , column factor j , and treatment factor (<i,j){⍺ . From ⍺ and ⍵ , latin computes the treatments, rows, and columns sums of squares. The rank3 array x within latin is an expansion of ⍵ , indicating where the data would fit in a complete block design. Example: (Mendenhall & Scheaffer [1973]) sq data sq latin data 3 1 2 4 44 41 30 40 626 365 226.5 2 3 4 1 41 42 49 49 1 4 3 2 59 41 59 34 4 2 1 3 58 37 53 59 1.4 Databases a is a 4dimensional array implementing a database.
The scalar (<i,j,k,l){a is the number of people who Three scenarios in the use of this database: One, index array i0 has been used to analyze the database +/+/a (city vs. age), and index array j0 has been used to analyze the database +⌿+⌿a (education vs. income). The index array i0∘.(,¨>)j0 can be used to explore in greater detail (in database a) the cases analyzed in the previous two studies. Two, i1 selects all people of age 25 in Toronto or Montreal, and j1 selects high school graduates living in those two cities. i1,j1 selects Torontonians or Montrealers, who are 25 years old or have at least 12 years of education. Three, people in age range y←25+⍳22 are “in their prime”; having less than s years of schooling is “less than welleducated”; and income brackets 0 through b are “lower income”. Then (<(<∘),(<y),(<<⍳s),<<⍳1+b){a selects Yuppies. Exercise: Do the above with [;] indexing. 1.5 Lagrange Interpolation Polynomial lagrange: (×/(⍵∘.c)÷⍤2 z⍤¯1 c)+.×fz ⊣ c←(<¨>¨>⍳0{⍴⍺){z ⊣ z←0{⍉⍺ ⊣ fz←1{⍉z ⍺ is a 2column matrix with distinct rows; each row (z,f z) is a sample from a univariate complex function f . lagrange interpolates ⍺ at ⍵ , using a (¯1+0{⍴⍺)th degree polynomial. Examples: x← 1 2 ¯6.2 y←20 ¯5 5.5 a←x,⍪y y ≡ a lagrange x 1 a lagrange ¯2 ¯1 0 1 2 55.47 50.23 38.41 20 ¯5 b←y⌹x∘.*⍳0{⍴x (¯2 ¯1 0 1 2∘.*⍳0{⍴x)+.×b 55.47 50.23 38.41 20 ¯5 1.6 Triangular Matrix Inversion A square matrix ⍵ is upper triangular if (0=⍵)∨c∘.≤c←⍳0{⍴⍵ . There is a simple computation for inverting such a matrix: invert a 2 2 triangular matrix of numbers, without using the commutativity of × then generalize to a (conceptual) 2 2 triangular matrix of matrices, substituting +.× for × . ri: (ai,ai+.×b+.×di)⍪(c,di) ⊣ ai←⍙(<( <i),<i){⍵ ⊣ b← (<( <i),<<i){⍵ ⊣ c← (<(<<i),<i){⍵ ⊣ di←⍙(<(<<i),<<i){⍵ ⊣ i←⍳⌈n÷2 : 1≥n←0{⍴⍵ : ÷⍵ ri quarters ⍵ : ai , b , c , and di are respectively the inverse of the top left, the top right, the bottom left, and the inverse of the bottom right. The two recursive steps in ri can be performed in parallel; thus ri shows how to compute the inverse of a triangular matrix in (2⍟n)*2 parallel time. Section 3.3 exhibits a computation for the inverse of
a general matrix, also using { .
2. Definitions of { and } { is a verb; } is a monadic adverb. Here, we define the four cases arising therefrom: {⍵ , ⍺{⍵ , v}⍵ , and ⍺v}⍵ . 2.1 All {⍵: (↓⍴¨>⍵)⍴<⍤1⍉(×/k)⍴⍤>⍉¨>((⌽×\⌽1↓k,1),¨>k)⍴¨>⍵ ⊣ k←×/⍤⍴⍤>⍵ {⍵ has rank 1, and computes the Cartesian product of the opened elements of ⍵ . The result satisfies ⍴{⍵ ←→ ↓⍴¨>⍵ and ⍴¨>⍵ ←→ (⍴{⍵) ←→ (⍴{⍵)⍴<⍴⍵ . 2.2 From Dyadic { encompasses all computations expressible by [;] indexing of APL\360, as well as the new negative indexing and complementary indexing. The left rank is 0 , the right rank is infinite; i.e. the definition applies to each scalar of ⍺ and to ⍵ in toto. Note the key role played by monadic { . ⍺{⍵: ((<⍴⍵)⊥⍤>{⍺ fi ⍵){,⍵ fi: (⍴a)⍴(a≡⍤0⊃¨>a)⊖i,¨<(⍳¨>s)~⍤,¨>i←s⍤>¨>a ⊣ a←(⊢¨>>⍺),((⍴⍴⍵)⍴,>⍺)⍴<∘ ⊣ s←⍴⍵ Where ⍵ is a vector and ⍺∊⍳⍴⍵ , is primitive. Otherwise, successive opened elements in >⍺ select
along successive axes of ⍵ . i←>k{,>⍺
is the index for axis k . i
may be an array of integers in the
range It is instructive to consider simpler computations for ⍺{⍵ in two special cases. If each opened element of >⍺ is an integer array, ⍺{⍵ ←→ >(s⊥⍤>s¨>{>⍺){,<⍤(⍴,>⍺)⍵ ⊣ s←<(⍴,>⍺)↑⍴⍵ Furthermore, if ⍺ is an integer, i.e. if ⍺∊(n)+⍳2×n←0{⍴⍵ , then ⍺ selects a major cell of ⍵ ; and ⍺{⍵ ←→ >((0{⍴⍵)⍺){<⍤¯1 ⍵ 2.3 Select v}⍵: (v{⍳¨>⍴⍵){⍵ v} has infinite monadic rank. v is applied to {⍳¨>⍴⍵ , the result is then used to select from ⍵ . v}⍵ is commonly, but not always, equivalent to v⍵ . 2.4 Merge The dyadic case of the derived verb v} produces a merge of its arguments. Both the left and the right rank are infinite. Positions in ⍵ selected by v are replaced by ⍺ . ⍺v}⍵ is a new array; neither ⍺ nor ⍵ nor v are affected by the computation of ⍺v}⍵ . Schueler [1986] proposes the following definition. It combines in one phrase {⍵ , ⍺{⍵ , v}⍵ , and ⍺v}⍵ . ⍺v}⍵: ((⌽i,⍤,j)⍳i){⌽⍵,⍤,(⍴j)⍴⍺ ⊣ j←v}i←{⍳¨>⍴⍵ Variable j in the definition indicates positions in ⍵ selected by v . In this paper, we assume either ⍴⍺ matches ⍴j , or ⍺ is a scalar. v ,
the verbal argument to } ,
is not restricted to any
subclass of verbs. In particular, v need not be a
“selection function”.
3. Some Primitives in Terms of { and } In this section, we define some primitives, both old and new, in terms of { } . The intent is to increase understanding of these primitives and of { } , rather than to present a formal system of definitions. 3.1 Old Selection ⌽⍵: (1+⍳0{⍴⍵){⍵ ⊖⍵: (1+⍳0{⍴⍵){⍵ ⍺⌽⍵: ((0{⍴⍵)⍺+⍳0{⍴⍵){⍵ ⍺⊖⍵: ⍺⌽¨⍉⍵ n⌿⍵: (((0∊1↑n)++\(⍳+/n)∊+\n){(0+.=n)↓⍋×n){⍵ n⍀⍵: (n×+\n){(0{1↑0⍴⍵)⍪>(+/n)⍴<⍤¯1 ⍵ ⍉⍵: (⌽⍳0{⍴⍴⍵)⍉⍵ ⍺⍉⍵: ((>{⍳¨>(⍴⍵)⌊.+¯×~l)+.×(⍴⍵)⊥l){,⍵ ⊣ l←⍺∘.=⍳1+⌈/⍺ 3.2 Cuts Iverson [1983] and [1986] described a family of verbs derived from the phrase n⍤v (adverb ⍤ with nounal left argument n and verbal right argument v . All derived verbs in this family apply v to rectangular pieces cut from ⍵ ; the exact nature of the cut is determined by n . Currently, n∊¯3+⍳7 is permissible. All cuts have infinite monadic rank and infinite right rank, i.e. apply to all of ⍵ . 0⍤v , 3⍤v , and ¯3⍤v have left rank 2; the others have left rank 1. ⍺ 0⍤v ⍵: v (<⍺ ci ⍵){⍵ 0⍤v ⍵: (0 ¯1∘.×⍴⍵) 0⍤v ⍵ ⍺ 1⍤v ⍵: (i⍪⍥,⍤0(1↓i,⍴⍺)i) 0⍤v ⍵ ⊣ i←⍺/⍳0{⍴⍺ 1⍤v ⍵: (⍵≡⍤¯1 ¯⊢0{⍵) 1⍤v ⍵ ¯1⍤v ←→ 1⍤(v⍤(1¨↓)) 2⍤v ←→ 1⍤(v⍤⊖)¨⊖ ¯2⍤v ←→ 2⍤(v⍤(¯1¨↓)) ⍺ 3⍤v ⍵: (⍺ ti ⍵) 0⍤v ⍵ : 1≥⍴⍴⍺ : (⍉1,⍪⍺)⍙⍵ 3⍤v ⍵: ((⍴⍴⍵)⍴⌊/⍴⍵) 3⍤v ⍵ ⍺ ¯3⍤v ⍵: ((⍺≡⍤(1¨{⍤2)i)⌿i←⍺ ti ⍵) 0⍤v ⍵ : 1≥⍴⍴⍺ : (⍉1,⍪⍺)⍙⍵ ¯3⍤v ⍵: ((⍴⍴⍵)⍴⌊/⍴⍵) ¯3⍤v ⍵ ci: ((l×¯1s)+(⍴⍵)0{a)+¨>(¯1*l)×¨>⍳¨>s ⊣ l←0>s ⊣ s←1{a ⊣ a←⍺,0 1∘.×(1{⍴⍺)↓⍴⍵ ti: 1 0 2⍉i,¨<(×1{⍺)×⍤1(1{⍺)⌊⍤1(⍴⍵)⍤1 i ⊣ i←(0{⍺)×⍤1 l\,>{⍳¨>⌈(l/⍴⍵)÷l/0{⍺ ⊣ l←0≠0{⍺ This dense and dry description imparts little sense of the utility of n⍤v . The usefulness end power of cuts are better illustrated through examples. But, given the title of the current text, such examples are more suitable for another paper. (Stay tuned.) 3.3 Two Primitives from Linear Algebra u.v⍵: (0{⍉⍵) u.v ⍙ (<¨>¨>(⍳0{⍴⍵),¨>0){⍵ : 1=¯1{⍴⍵ : u⌿,⍵ Iverson
[1976]
proposed a generalization of the determinant;
Iverson
[1982]
and
[1986]
refined the idea.
The above is an adaptation of a recursive
definition in Hoffman & Kunze
[1971],
and works by
“expansion by minors” along the first column of
matrix ⍵ .
The definition demonstrates the key role
played by .× is the ordinary determinant. ⌹⍵: (adj⍵)÷.×⍵ : ≠/⍴⍵ : (⌹(+⍉⍵)+.×⍵)+.×+⍉⍵ adj: ⍉(¯1*+/>i)×.×(<¨>¨>i){⍵ ⊣ i←{⍳¨>⍴⍵ ⍵ is a complex matrix; ⌹
is as in APL\360, but
extended to the complex domain;
and adj is the
“classical adjoint” of mathematics.
The above is a grossly inefficient
(not to mention numerically unstable)
means of computing ⌹ ,
but is useful for
theoretical investigations.
McDonnell & Shallit
[1980]
employed this definition to assign a meaning
to ⌹⍵ where 0=.×⍵ ;
viz., 4. Further Applications 4.1 Combinations comb: (c/k),(1+⌽↓⍳¨>⌽c){1+(⍺1)⍙⍵1 ⊣ c←(⍺1)!(⍺1)+⌽k ⊣ k←⍳1+⍵⍺ : 0=⍺ : 1 0 ⍴0 All size ⍺ combinations (subsets)
of ⍳⍵ ;
combinations and elements therein are in ascending order.
This is a restatement, in modern terms,
of the algorithm in Hui
[1981].
In words, the rows in ⍺ comb ⍵ whose first
element is k ,
are formed by prefixing k
to The phrase (⍉(⍺=+⌿t)t←(⍵⍴2)⊤⍳2*⍵)∘∇'⍺/⍵'⍤1⍳⍵ is equivalent to ⍺comb⍵ , but requires space (and time) exponential in the size of the desired result. Examples: 2 comb 4 3 comb 5 4 comb 6 0 1 0 1 2 0 1 2 3 0 2 0 1 3 0 1 2 4 0 3 0 1 4 0 1 2 5 1 2 0 2 3 0 1 3 4 1 3 0 2 4 0 1 3 5 2 3 0 3 4 0 1 4 5 1 2 3 0 2 3 4 1 2 4 0 2 3 5 1 3 4 0 2 4 5 2 3 4 0 3 4 5 1 2 3 4 1 2 3 5 1 2 4 5 1 3 4 5 2 3 4 5 4.2 Compositions comp: (c/k),((⍺1)↑⍤0 c/k)+(1+⌽↓⍳¨>⌽c){(⍺1)⍙⍵ ⊣ c←(⍺2)!(⍺2)+⌽k ⊣ k←⍳1+⍵ : 1≥⍺ : ((⍺≥⍤×⍵),⍺)⍴⍵ All size ⍺ compositions of ⍵ , in ascending order: all vectors x of nonnegative integers, such that (⍺=⍴x)^(⍵=+/x) . For example, ⍺comp⍵ are the exponents in the expansion of an ⍺nomial (a+b+…+z , ⍺ terms) raised to the ⍵th power. The current definition of comp is a restatement,
in modern terms, of the algorithm in Hui
[1982].
In words, the rows in ⍺comp⍵
whose first element is k ,
are formed by prefixing k
to The phrase ⍉(⍵=+⌿t)/t←(⍺⍴1+⍵)⊤⍳(1+⍵)*⍺ is equivalent to ⍺comp⍵ , but requires space (and time) exponential in the size of the desired result. Examples: 2 comp 3 3 comp 3 0 3 0 0 3 1 2 0 1 2 2 1 0 2 1 3 0 0 3 0 1 0 2 1 1 1 1 2 0 2 0 1 2 1 0 3 0 0 4.3 Permutations perm: ⍪⌿k,⍤¯1 (⍙⍵1){⍤¯ 1 k~⍤1 0 k←⍳⍵ : 1≥⍵ : (1,⍵)⍴0 All permutations of ⍳⍵ , in ascending order. This is a restatement, in modern terms, of the algorithm in Hui [1981]. In words, the rows in perm⍵ whose first element is k , are formed by prefixing k to the result of permuting (⍳⍵)~k by perm⍵1 ; in other words, (k=0{⍉t)⌿t←perm ⍵ ←→ k,(perm ⍵1){(⍳⍵)~k . The phrase (^/(⍳⍵)∊⍤1 t)⌿t←⍉(⍵⍴⍵)⊤⍳⍵*⍵ is equivalent to perm⍵ , but requires space (and time) exponential in the size of the desired result. Examples: perm 3 perm 4 0 1 2 0 1 2 3 0 2 1 0 1 3 2 1 0 2 0 2 1 3 1 2 0 0 2 3 1 2 0 1 0 3 1 2 2 1 0 0 3 2 1 1 0 2 3 1 0 3 2 1 2 0 3 1 2 3 0 … sup: (0,1+t)⍪⍪k⌿,⍤¯1(k∘.≠k)∘∇'⍺\⍵'⍤¯1(¯1+s↑t){⍤¯ 1 e ⊣ e←k~⍤1 0 k ⊣ k←1↓⍳⍵ ⊣ s←((0{⍉t)⍳1),2⍵ ⊣ t←⍙ ⍵1 : 1≥⍵ : (1,⍵)⍴0 All selfupgrading permutations of ⍳⍵ ,
in ascending order.
The algorithm is due to H.A. Rothe (McDonnell
[1976]).
In words, the rows in sup⍵ whose first
element is 0 ,
are formed by prefixing 0
to 1+sup⍵1 ;
the rows whose first element
is k (0≠k) has 0 in
column k ,
the other columns
are The phrase (∧/t=⍋⍤1 t)⌿t←perm⍵ is equivalent to sup⍵ , but requires space (and time) exponential in the size of the desired result. Examples: sup 3 sup 4 0 1 2 0 1 2 3 0 2 1 0 1 3 2 1 0 2 0 2 1 3 2 1 0 0 3 2 1 1 0 2 3 1 0 3 2 2 1 0 3 2 3 0 1 3 1 2 0 3 2 1 0 sdp: x⍪⊖⌽x←(⌽mt),(r⍴⌊⍵÷2),⍤1 t←⍪⌿k,⍤¯1⊂(k∘.≠k)∘∇'⍺\⍵'⍤¯1 (s↓⍙⍵4+r){⍤¯ 1 e ⊣ e←((⍳⍵)~0,m,r⍴⌊⍵÷2)~⍤1 k,⍪mk ⊣ k←⌽(⌈⍵÷2)+⍳¯1+⌊⍵÷2 ⊣ s←0,⌊(⍵4)÷2 ⊣ m←⍵1 : (1≥⍵)∨2≤r ⊣ r←4⍵ : ((1≥⍵),⍵)⍴0 All selfdowngrading permutations of ⍳⍵ , in ascending order. The algorithm is due to E.E. McDonnell (McDonnell [1976]), and derives by observing that a choice for the first element of a row immediately determines three other elements of that row. We first generate the upper right corner (local variable t in sdp), whence the full result obtains easily. The phrase (∧/t=⍒⍤1 t)⌿t←perm⍵ is equivalent to sdp⍵ , but requires space (and time) exponential in the size of the desired result. Examples: sdp 4 sdp 5 1 3 0 2 1 4 2 0 3 2 0 3 1 3 0 2 4 1 sdp 8 sdp 9 1 7 3 5 2 4 0 6 1 8 3 6 4 2 5 0 7 1 7 4 2 5 3 0 6 1 8 5 2 4 6 3 0 7 2 3 7 6 1 0 4 5 2 3 8 7 4 1 0 5 6 2 4 7 1 6 0 3 5 2 5 8 1 4 7 0 3 6 3 2 6 7 0 1 5 4 3 2 7 8 4 0 1 6 5 3 5 1 7 0 6 2 4 3 6 1 8 4 0 7 2 5 4 2 6 0 7 1 5 3 5 2 7 0 4 8 1 6 3 4 5 1 0 7 6 2 3 5 6 1 0 4 8 7 2 3 5 3 0 6 1 7 U 2 6 3 0 7 4 1 8 5 2 5 4 0 1 6 7 3 2 6 5 0 1 4 7 8 3 2 6 0 3 5 2 4 7 1 7 0 3 6 4 2 5 8 1 6 0 4 2 5 3 7 1 7 0 5 2 4 6 3 8 1 ≤⍵: ↑,(⍋⌈/t){(t⍳⌈/t)⌽t←⍉{⍀(1 1+⌈/⍵)⍴⍵,(⍳⌈/⍵)~⍵ The cycle representation of a mix (a generalized
permutation). For example, ≥⍵: ((⍋c++\c){⍵)⍵¨{}⍳1+⌈/⍵ ⊣ c←⍵=⌈\⍵ ≥⍵: ((c/⍵)(1⌽c)/}1⌽⍵)⍵¨{}⍳1+⌈/⍵ ⊣ c←⍵=⌈\⍵ ≥⍵ is the permutation whose cycle representation is ⍵ The first definition is modified from Iverson [1980]; the second is a lineartime computation. For a permutation ⍵ , ≤≥⍵ ←→ ⍵ ←→ ≥≤⍵ . In general, ⍋⍵ and ⍒⍵ require time of order ×/(⍴⍵),2⍟0{⍴⍵ , but for permutations ⍵ , lineartime computations exist: ⍋⍵: (⍳0{⍴⍵) ⍵ ¨{}⍵ ⍒⍵: (⍳0{⍴⍵)(1+⍵)¨{}⍵ 4.4 Permutation Groups perm n , the set of permutations of ⍳n , forms a group under { :
This is the “symmetric group of degree n”. The group table is p∘.({⍤1)p←perm n . In ordinary arithmetic, the ⍺th power of a number ⍵ is the product ×⌿⍺⍴⍵ . Similarly, the ⍺th power of a permutation ⍵ is {⌿(⍺,⍴⍵)⍴⍵ ; or, more concisely, {⌿⍺⌿⍉⍪⍵ . A subgroup of a group is a subset of group elements
which form a group in their own right (under the same
operation). The smallest subgroup containing a
permutation ⍵ ,
the subgroup generated by ⍵ ,
is the set of all distinct powers
of ⍵ : sg: {⍀(∧⌿1⍤⍴c=⌈\c←≤⍵)⌿⍉⍪⍵ sg 2 5 1 0 3 4 sg 1 4 5 2 0 3 2 5 1 0 3 4 1 4 5 2 0 3 1 4 5 2 0 3 4 0 3 5 1 2 5 3 4 1 2 0 0 1 2 3 4 5 4 0 3 5 1 2 3 2 0 4 5 1 0 1 2 3 4 5 Let ⍵ be a set of permutations — a matrix whose rows are permutations. To compute the members of the subgroup generated by ⍵ , we reason as follows: Since the subgroup must be closed, it contains ⍵∘.({⍤1)⍵ ; or, in standard matrix form, ↑⍪⌿⍵∘.({⍤1)⍵. This process is repeated, until no more new permutations are introduced. Thus we have sgm: '↑⍪⌿⍵∘.({⍤1)⍵'∇∘. ¯(⍉⍪⍳¯1{⍴⍵)⍪⍵ The “process” is the derived verb '↑⍪⌿⍵∘.({⍤1)⍵'∇∘ ; the augmentation of ⍵ by the identity permutation ⍳¯1{⍴⍵ converts a limit computation v. ¯ into the desired closure computation. In general, no one permutation generates the entire group, else { on permutations would be commutative. Herstein [1975] (Exercise 2.10.11) tells us there exists a generator of size two: p←(⌽⍳2⌊n),2↓⍳n and q←1⌽⍳n suffice to generate p1←p and q1←(1⌽⍳n1),n1 , which are like p and q except ¯1{⍵ is invariant under p1{⍵ and q1{⍵ . Therefore, pqgen: ((t)/0<t←(p pqe ⍵),¯1){p,¨<q←1⌽⍳n ⊣ p←(⌽⍳2⌊n),2↓⍳n ⊣ n←0{⍴⍵ pqe: m shrink (,((t)/0<t){¯1 0 0,¨<2 ¯1,m1),k ⊣ t←(¯1↓k⌽⍺) ⍙ ¯1↓⍵ ⊣ k←m1+⍺⍳¯1{⍵ : 2≥m←0{⍴⍵ : (⍺≡⍵)↓¯1 shrink: ⍺ ⍙ (0≠t)/t←((0<l/⍵){¯2,⍺)l 1⍤(+/) ⍵ : ∧/l←s≠¯1↓2,s←×⍵ : ⍵ ⍵≡{⌿y←pqgen⍵ and (y∧.=p)∧.∨(y∧.=q) for permutation ⍵ . That is, sgm p,¨<q is the entire permutation group. What is the significance of permutation groups? Let G be a group table of a finite group of order n . If relabel:(0{t)⍳t←<⍤¯2⍵ , the columns of relabel G are distinct permutations of ⍳n , and relabel G ←→ relabel H∘.({⍤1)H←⍉relabel G In other words, every finite group G of order n is isomorphic to a subgroup H of the permutation group of degree n . This is the finite case of Cayley’s Theorem, named in honor of the English mathematician who first observed the fact (Herstein [1975], Section 2.9). We illustrate Cayley’s Theorem with an example. Let G be a group table of the group of transpositions (reflections and rotations) of the square. G in this instance is a matrix of boxed literal vectors. (More about the unusual element names later.)
⍴G 8 8 relabel G 0 1 2 3 4 5 6 7 1 2 3 0 7 4 5 6 2 3 0 1 6 7 4 5 3 0 1 2 5 6 7 4 4 5 6 7 0 1 2 3 5 6 7 4 3 0 1 2 6 7 4 5 2 3 0 1 7 4 5 6 1 2 3 0 H←⍉relabel G The columns of relabel G ,
the rows of H , are distinct
permutations of ⍳8 ,
and H is a subgroup of the
permutation group of degree 8.
After relabelling, relabel H∘.({⍤1)H 0 1 2 3 4 5 6 7 1 2 3 0 7 4 5 6 2 3 0 1 6 7 4 5 3 0 1 2 5 6 7 4 4 5 6 7 0 1 2 3 5 6 7 4 3 0 1 2 6 7 4 5 2 3 0 1 7 4 5 6 1 2 3 0 (relabel G)≡relabel H∘.({⍤1)H 1 (The names for the elements of G are due to considerations discovered independently by Thomson [1979], Hui [1981], and Benkard & Seebe [1983]: (pm:⍵∘.=⍳0{⍴⍵ and mp:⍵⍳1 are an inverse pair, mapping permutations to boolean matrices and vice versa. Let f be a string of ⊢ ⍒ ⍋ ⌽ , a function on permutations; and t be a transposition of the square. Identify f and t , if f p ←→ t¨pm p (←→ mp t pm p) t m ←→ f¨mp m (←→ pm f mp m) In other words, G may be viewed as a group of transpositions of the square, or isomorphically as a group of functions on permutations. We saw previously that G is also isomorphic to a subgroup of the permutations, by Cayley’s Theorem. (Table G above is a compact presentation of numerous
identities involving the functions ⊢ ⍒ ⍋ ⌽ applied to
permutations: The entry (<i,j){G is equivalent to
the result of
composing (<i,0){G
and (<0,j){G .
For example, the entry at the intersection of row ⍒
column ⍋⍒ is ⍋ ,
whence ⍒⍋⍒ ←→ ⍋ ;
similarly, ⍋⍋ ←→ ⊢ , ⍒⍒⍒ ←→ ⍋⌽ , ⍒⍒⍒⍒ ←→ ⊢ , and so forth.)
5. Conclusion { has more expressive power than [;] , without the anomalous syntax. Because of this, { can be used in verb phrase; and as the paper shows, derived verbs involving { have many uses. } allows verbs other than
indexing to indicate
elements are to be replaced.
Unlike “indexed
assignment”, }
requires no special syntax, and
has no side effects.
Acknowledgments It is a pleasure to thank Fred Appleyard, Bob Bernecky, Paul Berry, Maxine Hersch, Ken Iverson, and Henri Schueler, whose comments, criticisms, and corrections led to numerous improvements in the paper. Ideas herein evolved over many conversations with
K.E. Iverson.
Any remaining errors, strategic or tactical,
stylistic or technical, are of course mine.
References
Appendix A: Notation Brief explanations on less familiar aspects of the notation are given here; full descriptions can be found in A Dictionary of APL (Iverson [1986]). Basically, expressions which would return results in an older APL (such as APL\360) work as before, but some expressions which previously caused errors now return results, The following conventions apply:
A.1 Direct Definition A direct definition consists of 2 or 4 parts, separated by colons. Examples: root: ⍵*÷⍺ oder: 'nein' : ⍺∨⍵ : 'ja' fact: ⍵×⍙⍵1 : 0=⍵ : 1 3 root 4 5 6 computes the
cube roots of 4 5 6 ; A.2 Rank The ranks of a verb are three integers mv,lv,rv , the monadic rank, left rank, and right rank, respectively. A verb need only be defined on arguments of rank bounded by its rank(s); the extension to arguments of higher rank is uniform for all verbs. The intrinsic ranks of a verb u may be augmented by the adverb ⍤ , thus: u⍤n . For positive rank r , ⍵ is split into f←(r)↓⍴⍵ cells, each with shape (r)↑⍴⍵ . We speak of f as the frame or the outer shape of ⍵ relative to rank r (or relative to v , the verb whose rank is r); and the cells as rankr cells or simply rcells. A negative rank indicates the number of leading axes to exclude from the cell shape: the excluded axes become the frame. ¯1cells are also known as “major cells”. Many verbs are defined in terms of major cells. v⍵: ⍵ is split into f←(mv)↓⍴⍵ rankmv cells. The result obtains by applying v to each mvcell of ⍵ , with a necessarily common result cell shape c . The overall result has shape f,c . ⍺v⍵: ⍺ is split into fa←(lv)↓⍴⍺ ranklv cells; ⍵ into fb←(rv)↓⍴⍵ rankrv cells. One of the following must hold: fa matches fb , or both of fa or fb is empty. If the former, v is applied to corresponding cells of ⍺ and ⍵ to obtain the result cells; if the latter, the single cell for the empty frame is applied against every cell of the other argument, to obtain the result cells. The overall result has shape fa,((0=⍴fa)/fb),c . The familiar scalar functions and scalar extension of APL\360, are special cases of this cellular verb application and cellular extension, where all ranks 0 . The preceding is stated more succinctly below. (u⍤>⍵ applies u to the open of each scalar of ⍵ .)
u⍤n⍵: u⍤> (0{r)enc⍵ ⊣ r←⌽3⍴⌽n ⍺u⍤n⍵: (f⍴a) u⍤> (f⍴b) ⊣ f←(⍴a),(0=⍴⍴a)/⍴b ⊣ a←(1{r)enc⍺ ⊣ b←(2{r)enc⍵ ⊣ r←⌽3⍴⌽n enc: (t↓⍴⍵)⍴(t↑⍴⍵)enl,⍵ ⊣ t←((0≤⍺)×⍺⌊⍴⍴⍵)+(0>⍺)×0⌈⍺+⍴⍴⍵ enl: (<⍺⍴⍵),⍺⍙(×/⍺)↓⍵ : ''≡⍵ : ⍵ Intrinsic ranks of primitive verbs:
A.3 Nouns
A.4 Verbs
A.5 Adverb
Appendix B: Annotated Examples ⍺{⍵ , “from”, begins with the primitive notion of selecting an element from a vector — 1=⍴⍴⍵ and ⍺∊⍳⍴⍵ . x←31 41 59 26 53 58 97 93 0{x 7{x 3{x 31 93 26 ⍺{⍵ is defined for scalar ⍺ and array ⍵ . (The extension to ⍺ with higher rank will be explained later.) >⍺ must be a scalar or a vector, and the length of ,>⍺ must be no greater than the rank of ⍵ . >k(,>⍺ is the index for axis k . ⊢m←4 5⍴⍳12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 (<(<1),<2){m 7 (<(<1 2),<4 3 2){m 9 8 7 14 13 12 The left argument to { can be simplified by exploiting the permissiveness of monadic > on open arrays. (An open array is one which is not boxed.) Dyadic ⊃ may also be useful in this regard. The last two examples can be restated thus: (<1 2){m 7 (<1 2⊃4 3 2){m 9 8 7 14 13 12 In (<1 2){m , 1 ←→ >0{,><1 2
is the index for axis 0 (rows); 2 ←→ >0{,><1 2
is the index for axis 1 (columns).
In (<1 2⊃4 3 2){m , 1 2 ←→ Where the left argument of ⍺{⍵ is open, “major cells” of ⍵ are selected. Major cells of ⍵ are the subarrays of rank ¯1+⍴⍴⍵ along the leading axis of ⍵ . 2{m 10 11 12 13 14 0{m 0 1 2 3 4 2{m is row 2 of m , because 2 ←→ >0{,>2 is the index for axis 0; 0{m is row 0 of m because 0 ←→ >0{,>0 . Indices i for an axis of length l may be integers in the range l to ¯1+l ; negative i is equivalent to li . As indices ¯1 ←→ ¯1+l , ¯2 ←→ ¯2+l , and s0 on. (<0 ¯1){m 4 (<¯1⊃0 ¯1 1){m 15 19 16 ¯2{m 10 11 12 13 14 The left rank of ⍺{⍵ is 0 , and the right rank is infinite: each scalar of ⍺ is applied against all of ⍵ , to get an individual result with shape c ; the overall result of ⍺{⍵ has shape (⍴⍺),c . This produces “scattered indexing“, an effect not directly computable with [;] indexing of APL\360. (0 1⊃¯1 ¯1){m 1 19 (<¯1⊃0 ¯1 1){m 15 19 16 (2 2⍴0 1⊃¯1 ¯1⊃¯1 0⊃0 ¯2){m 1 19 15 3 2 0 ¯1{m 10 11 12 13 14 0 1 2 3 4 15 16 17 18 19 (2 2⍴2 0 ¯1 3){m 10 11 12 13 14 0 1 2 3 4 15 16 17 18 19 15 16 17 18 19 ((<1⊃2 3),<2 3⊃1){m 7 8 11 16 x←3 1 4 1 5 9 2 7 ((⌽⍳⌈/x)∘.<x){'.⎕' .....⎕.. .....⎕.. .....⎕.⎕ .....⎕.⎕ ....⎕⎕.⎕ ..⎕.⎕⎕.⎕ ⎕.⎕.⎕⎕.⎕ ⎕.⎕.⎕⎕⎕⎕ ⎕⎕⎕⎕⎕⎕⎕⎕ In all the examples above. >k{,>⍺ are integer arrays. >k{,>⍺ may also be boxed; integers therein indicate positions to be excluded. This is “complementary indexing”. (<(<1),<2){m row 1, column 2 7 (<(<1),<<2){m row 1, excluding column 2 5 6 8 9 (<(<<1),<2){m column 2, excluding row 1 2 12 17 (<(<<1),<<2){m excluding row 1 & column 2 0 1 3 4 10 11 13 14 15 16 18 19 (<(<<¯1),<2){m column 2, excluding row ¯1 2 7 12 (<(<<''),<2){m column 2, excluding nothing 2 7 12 17 (<(<∘),<2){m ∘ ←→ <'' 2 7 12 17 (<∘⊃2){m ∘⊃2 ←→ (<∘),<2 2 7 12 17 i←0 1 j←0 1 2 m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 (<(<i),<j){m (<(<i),<<j){m 0 1 2 3 4 5 6 7 8 9 (<(<<i),<j){m (<(<<i),<<j){m 10 11 12 13 14 15 16 17 18 19 In Section 3.3, we use complementary and scattered indexing in concert, to produce succinct definitions for the generalized determinant and for ⌹⍵ . The following are examples of [;] indexing, and expressions using { which compute the same result. Recall that ∘ ←→ <'' . a[i] i{a a[i;] i{a a[i;;] i{a a[i;j;k] (<i⊃j⊃k){a a[i;j;k;;;] (<i⊃j⊃k){a a[i;j;] (<i⊃j){a a[i;;j] (<i⊃∘⊃j){a a[;;j] (<∘⊃∘⊃j){a {⍵ , “all”, computes the cartesian product of the opened elements of its vector argument ⍵ . {1 2⊃4 5 6 7 ┌───┬───┬───┬───┐ │1 4│1 5│1 6│1 7│ ├───┼───┼───┼───┤ │2 4│2 5│2 6│2 7│ └───┴───┴───┴───┘ {'cr'⊃'ao'⊃'dmntw' ┌───┬───┬───┬───┬───┐ │cad│cam│can│cat│caw│ ├───┼───┼───┼───┼───┤ │cod│com│con│cot│cow│ └───┴───┴───┴───┴───┘ ┌───┬───┬───┬───┬───┐ │rad│ram│ran│rat│raw│ ├───┼───┼───┼───┼───┤ │rod│rom│ron│rot│row│ └───┴───┴───┴───┴───┘ {⍵ is closely related to selecting from rectangular arrays. For example, ⍺{⍵ (Section 2.2) and ⍺⍉⍵ (Section 3.1) are both defined in terms of monadic { . In particular, the phrase {⍳¨>⍴⍵ plays a key role in the definition of ⍺v}⍵ (“merge”). ⍴{⍳¨>⍵ ←→ ⍴⍵ ; each opened element is the “position” of an element of ⍵ , a number represented in base ⍴⍵ . ⊢a←2 3 4⍴⍳24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ⍳¨⍴a ┌───┬─────┬───────┐ │0 1│0 1 2│0 1 2 3│ └───┴─────┴───────┘ {⍳¨>⍴a ┌─────┬─────┬─────┬─────┐ │0 0 0│0 0 1│0 0 2│0 0 3│ ├─────┼─────┼─────┼─────┤ │0 1 0│0 1 1│0 1 2│0 1 3│ ├─────┼─────┼─────┼─────┤ │0 2 0│0 2 1│0 2 2│0 2 3│ └─────┴─────┴─────┴─────┘ ┌─────┬─────┬─────┬─────┐ │1 0 0│1 0 1│1 0 2│1 0 3│ ├─────┼─────┼─────┼─────┤ │1 1 0│1 1 1│1 1 2│1 1 3│ ├─────┼─────┼─────┼─────┤ │1 2 0│1 2 1│1 2 2│1 2 3│ └─────┴─────┴─────┴─────┘ ⍺v}⍵ produces a “merge” of ⍺ and ⍵ ; positions (v i){i←{⍳¨>⍴⍵ in ⍵ are replaced by ⍺ . In words, the verb v is applied to i←{⍳¨>⍴⍵ , the result is then used to select from i , to obtain positions in ⍵ to be replaced by ⍺ . In this paper, we assume ⍺ is either a scalar, or ⍴⍺ ←→ (v i){i . 1 0{3 1 4 1 5 9 1 3 1 0¨{3 1 4 1 5 9 1 3 (¯1 8) 1 0¨{3 1 4 1 5 9 8 ¯1 4 1 5 9 (¯1 ¯2 ¯3) 1 1 1¨{}3 1 4 1 5 9 3 ¯3 4 1 5 9 The phrase n¨v is a monadic verb derived from the dyadic adverb ¨ (“with”), array n , and verb v ; n¨v ⍵ ←→ n v ⍵ . n¨v is a verb, and therefore can be used as argument to adverbs such as } ; n v on the other hand is a sentence fragment, being neither a noun nor a verb nor an adverb nor punctuation. ⍺v}⍵ is a new array; neither ⍺ nor ⍵ nor v are affected by the computation of ⍺v}⍵ . We could of course assign the result to any name. m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ¯1 (<1 2)¨{}m a single element 0 1 2 3 4 5 6 ¯1 8 9 10 11 12 13 14 15 16 17 18 19 (¯1 ¯2 ¯3 ¯4 ¯5) 1¨{}m row 1 0 1 2 3 4 ¯1 ¯2 ¯3 ¯4 ¯5 10 11 12 13 14 15 16 17 18 19 ¯1 (<∘⊃2)¨{}m column 2 0 1 ¯1 3 4 5 6 ¯1 8 9 10 11 ¯1 13 14 15 16 ¯1 18 19 ¯1 ¯2 ¯3 ¯4 ¯5 (0 1⊃¯1 ¯1⊃¯1 0⊃0 ¯2}¨{}m 0 ¯1 2 ¯4 4 5 6 7 8 9 10 11 12 13 14 ¯3 16 17 18 ¯2 The last example, “scattered replacement”, is not directly computable with [;] indexing. ¯1 (<(<1),<2)¨{}m 0 1 2 3 4 5 6 ¯1 8 9 10 11 12 13 14 15 16 17 18 19 ¯1 (<(<1),<<2)¨{}m 0 1 2 3 4 ¯1 ¯1 7 ¯1 ¯1 10 11 12 13 14 15 16 17 18 19 ¯1 (<(<<1),<2)¨{}m 0 1 ¯1 3 4 5 6 7 8 9 10 11 ¯1 13 14 15 16 ¯1 18 19 ¯1 (<(<<1),<<2)¨{}m ¯1 ¯1 2 ¯1 ¯1 5 6 7 8 9 ¯1 ¯1 12 ¯1 ¯1 ¯1 ¯1 17 ¯1 ¯1 v, the verbal argument to } , need not involve { . In fact, v need not be a “selection function” at all. (¯1) ¯2 ¯3¨↑}4 5⍴99 99 99 99 99 99 99 99 99 99 99 99 99 ¯1 ¯1 ¯1 99 99 ¯1 ¯1 ¯1 (¯1 ¯2 ¯3 ¯4) 0 0¨⍉}m ¯1 1 2 3 4 5 ¯2 7 8 9 10 11 ¯3 13 14 15 16 17 ¯4 19 (¯1 ¯2 ¯3 ¯4) 0 0¨⍉⍤⊖}m 0 1 2 ¯4 4 5 6 ¯3 8 9 10 ¯2 12 13 14 ¯1 16 17 18 19 '*' 0 0¨⍉} '⍟' 0 0¨⍉⍤⊖}5 5⍴'.' *...⍟ .*.⍟. ..*.. .⍟.*. ⍟...* '⍟' (' '=x)/}x←'cogito, ergo sum' cogito,⍟ergo⍟sum In the last example, / is an adverb; hence (' '=x)/ is a verb, and is the argument to } . Errata
Originally appeared in the APL 87 Proceedings, APL Quote Quad, Volume 17, Number 4, 198705.
