秩 (J編程語言)

(Rank),是對非面向陣列標量編程語言循環廣泛化[1][2]。它還是Lisp語言中的mapcar[3],及現代函數式編程語言中的map高階函數的廣泛化,以及對APL\360中標量擴展[4]矩陣內積[5]外積[6]的廣泛化[7]。秩的正規實現,是在J語言中,但也可獲得於APL語言實現如Dyalog APL[8]ISO標準ISO/IEC 13751:2001的擴展APL[9]和NARS2000[10]

簡介

編輯

秩有一些不同的含義。一般的說,秩的概念用於依據它們的子陣列來處理正交陣列英語Orthogonal array[11]。例如,二維陣列可以在秩為2之下,按一個完整的矩陣進行處理;或者在秩為1之下,對它所包含的諸個一維列向量或行向量進行處理;或者在秩為0之下,對它所包含的諸個單獨元素進行處理。J語言中有三種秩:

  • 名詞秩,名詞的秩是非負整數
  • 動詞秩,動詞的秩是三個整數的列表。
  • 秩連詞,秩連詞"用來導出具有指定秩的一個動詞。

名詞秩

編輯

在J語言中,名詞是陣列英語array data type。名詞的秩是這個陣列的維數。儘管有時存在爭論[12],人們通常用如下名字稱謂低維陣列[13]

名字
原子 標量 0
列表 向量 1
表格 矩陣 2
立體 張量 3

一個N維整數陣列可以通過i.建立,它接受一個整數向量作為參數。其中整數的數目定義了維數,而每個整數的絕對值定義對應維的長度。可以使用派生動詞#@$來確定一個名詞的秩。

   i. 3
0 1 2
   >:i. 3
1 2 3
   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
   #@$ i. 2 3 4
3

動詞秩

編輯

在J語言中,動詞是接受名詞參數產生名詞結果的函數。動詞的秩,控制着如何將動詞應用到秩大於0的名詞。採用副詞u b. 0來確定動詞u的秩。例如:

   * b. 0
0 0 0
   +/ b. 0
_ _ _

這裡的_「無窮」,指示將參數作為整體處理。動詞的秩被表達為三個數:

  1. 一元情況的秩
  2. 二元情況用於左參數的秩
  3. 二元情況用於右參數的秩

例如,−y使用作為單子(monad),是一元情況;x−y使用作為雙子(dyad),是二元情況。在所有情況下,有一些底層動詞被應用於「單元」(cell),它是有指示秩的子陣列。如果參數沒有動詞指示的那麼多維,在這種退化的情況下,動詞的秩會有效的縮減為參數實際的秩。

在動詞中,負數秩被解釋為,將提供為參數的名詞的秩,減少指示正值,但永不會變得小於零。例如,一個動詞具有一元秩負1,在給它一個秩為3的參數的時候,將參數分解成秩為2的陣列的一個列表。將動詞的主體,應用到這些二維子陣每個之上一次。

在特定動詞和特定名詞的上下文下,將名詞的諸維,劃分成前綴諸維的序列,稱為框架(frame);和後綴諸維的序列,稱為單元(cell)。正數動詞秩,指示單元諸維的數目,負數動詞秩,指示框架諸維的數目。

秩連詞

編輯

秩連詞",接受一個動詞左參數和一個名詞右參數來建立一個新動詞。

名詞右參數構成自三個數,分別指定一元秩、二元左秩和二元右秩[14]。如果右參數只有兩個數,第一個數是二元左秩,而第二個數是一元秩和二元右秩。如果右參數只有一個數,它被接受為所有三種情況下的秩。如果右參數是個動詞,就複製使用它的秩。例如:

   (*"1 1 1) b. 0
1 1 1
   (*"0 _) b. 0
_ 0 _
   (*"1) b. 0
1 1 1
   (*"<) b. 0
_ 0 0

如果給秩連詞的左參數是個名詞,建立一個常量動詞。這個動詞的主體忽略任何參數的值,並總是生成這個名詞的結果。

框架一致

編輯

在二元運算的情況下,左右兩個參數,都有自己的框架,二者必須達成一致(agreement)。左右兩框架經常是共同的。如果左右兩框架不是同一的,有三種可以運算的情況:

兩參數中一個的形狀序列,是另一個的形狀序列的前綴,例如:

   (i. 2 3) * i. 2 3 4
  0   0   0   0
  4   5   6   7
 16  18  20  22

 36  39  42  45
 64  68  72  76
100 105 110 115

這裡左側參數的短框架2 3,是右側參數的長框架2 3 4的前綴。求值這個動詞的結果,跟隨着前綴諸維序列2 3,是二元動詞應用到兩個有關單元的結果,即將左參數的每個0維標量,乘以右參數的每個1維陣列。

兩參數中一個的形狀序列,是另一個的形狀序列的後綴,可以通過秩連詞,指定動詞秩為維數少參數的秩,從而對它按整體處理,例如:

   (i. 3 4) *"2 i. 2 3 4
  0   1   4   9
 16  25  36  49
 64  81 100 121

  0  13  28  45
 64  85 108 133
160 189 220 253

這裡左側參數的短框架3 4,是右側參數的長框架2 3 4的後綴。求值這個動詞的結果,跟隨着前綴諸維序列2,是二元動詞應用到兩個有關單元的結果,即將左參數的作為整體的1個2維陣列,乘以右參數相同形狀的每個2維陣列。

指定動詞左右秩中的一個為_,即按整體處理,例如:

   $ (i.2 3) (*"0 _) i.3 4
2 3 3 4
   $ (i.2 3) (*"_ 0) i.3 4
3 4 2 3
   $ (i.2 3) (*"1 _) i.3 4
2 3 4
   $ (i.2 3) (*"_) i.2 3 4
2 3 4

這裡第一個運算的左秩為0,而右秩為按整體處理;求值的結果中跟隨着左參數的諸維序列2 3的,是將左參數的每個0維標量,乘以右參數的作為整體的2維陣列的結果。第二個運算的左右秩與第一個運算相反,其結果中來自二者的諸軸的前後次序也與之相反。第三個運算的左秩為1,而右秩為按整體處理;跟隨着左參數的諸維序列2的,是將左參數的每個1維向量,乘以右參數的作為整體的2維陣列的結果。第四個運算的左右秩都按整體處理,則同於前綴情況。

秩作為循環的泛化

編輯

理解秩要求知道一些非常基礎的面向陣列編程概念。在大多數基於陣列的語言中,歸約(reduction)用前向斜槓/來指示。在J語言中,斜槓接受一個函數左參數,和要被這個函數歸約的陣列作為右參數。將加法歸約應用到一個1維陣列:

   +/ 1 2 3
6

預期的結果是1 + 2 + 3。 將加法歸約應用到一個2維陣列:

   +/ i. 2 3
3 5 7

預期結果是0 1 2 + 3 4 5+/的秩為_「無窮」,即將參數作為整體來運算,+算符被映射到這個陣列的最高秩之上。對2個向量進行歸約,參數名詞的形狀從2 3變為1 33,結果是合計了每行元素的長度為3的1維陣列。這個代碼對應如下APL2及其派生者的代碼:

      + 2 3⍴⍳6
3 5 7

還對應於如下C語言代碼片段[15]

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];
    }
}

假定需要合計每列元素,而得到長度為2的1維陣列,在C語言代碼中如下這樣寫:

for(i = 0; i < 2; ++i) {
    sum[i] = 0;
    for(j = 0; j < 3; ++j) {
        sum[i] += array[i][j];
    }
}

APL中不需要用到循環構造,這個代碼寫為:

      +/ 2 3⍴⍳6
3 12

在J語言中使用秩連詞可以寫為:

   +/"1 i. 2 3
3 12
   +/"_1 i. 2 3
3 12

為了進一步展示在J語言中秩是如何工作的,以3維陣列上的加法歸約為例子:

   a=: i. 2 3 4
   +/ a
12 14 16 18
20 22 24 26
28 30 32 34
   +/"_1 a
12 15 18 21
48 51 54 57
   (+/"_1 a) -: +/"2 a
1
   +/"1 a
 6 22 38
54 70 86
   (+/"1 a) -: +/"_2 a
1

引用

編輯
  1. ^ Slepak, Justin; Shivers, Olin; Manolios, Panagiotis. An array-oriented language with static rank polymorphism (PDF). [2020-05-19]. (原始內容存檔 (PDF)於2020-01-10). 
  2. ^ Loopless Code I: Verbs Have Rank. Jsoftware. [2020-05-19]. (原始內容存檔於2019-01-03). 
  3. ^ The mapcar Function. Free Software Foundation. [2020-05-19]. (原始內容存檔於2020-01-09). 
  4. ^ Scalar extension. [2022-06-14]. (原始內容存檔於2022-06-14). 
  5. ^ Inner Product. [2022-06-14]. (原始內容存檔於2022-06-15). 
  6. ^ Outer Product. [2022-06-14]. (原始內容存檔於2022-06-14). 
  7. ^ Leading axis theory. [2020-05-22]. (原始內容存檔於2022-06-14). 
  8. ^ Dyalog APL. [2022-06-14]. (原始內容存檔於2022-06-28). 
  9. ^ ISO/IEC 13751:2001. [2022-06-17]. (原始內容存檔於2022-01-21). 
  10. ^ NARS2000. [2022-06-17]. (原始內容存檔於2013-09-12). 
  11. ^ Bernecky, R. An Introduction to Function Rank. APL88 Conference Proceedings, APL Quote Quad 18 (2). December 1987. 
  12. ^ kgwgk; nabla9; azag0; tome; radarsat1. HPTT: A High-Performance Tensor Transposition C++. Hacker News. Y Combinator. 2017-04-24 [2019-12-10]. (原始內容存檔於2018-09-07). 
  13. ^ Rabanser, Stephan; Shchur, Oleksandr; Günnemann, Stephan. Introduction to Tensor Decompositions and their Applications in Machine Learning. 2017-11-29. arXiv:1711.10781  [stat.ML]. 
  14. ^ Burke, Chris. Essays: Rank. Jsoftware. 2014-09-12 [2020-05-19]. (原始內容存檔於2018-09-06). 
  15. ^ Controlling Verb Execution By Specifying a Rank. Jsoftware. [2020-05-19]. (原始內容存檔於2019-01-03). 

延伸閱讀

編輯
  • Abrams, P.S. §II.E. An APL Machine (PDF). Stanford University (學位論文). February 1970 [2020-05-19]. (原始內容存檔 (PDF)於2016-03-05). 
  • Bernecky, R.; Iverson, K.E. Operators and Enclosed Arrays. Proceedings. 1980 APL Users Meeting. Jsoftware. 6–8 October 1980 [2020-05-19]. (原始內容存檔於2016-03-16). 

外部連結

編輯