秩 (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). 

外部链接

编辑