肯尼斯·艾弗森(Kenneth Iverson)1964年的语言APL为他赢得了图灵奖。他的获奖演讲“记法作为一种思维工具”认为,更好的记法将引导人们对数学有更深刻的理解。他提供了许多例子,涉及线性代数、算术、概率和逻辑。
不幸的是,他涵盖的大多数数学与编程无关。但是,他的核心思想仍然适用,改变我们描述程序的方式会改变我们对它们的看法。我想展示一下艾弗森的一些注释是如何让我们更好地理解我们可以用编程语言做什么的。
免责声明:虽然NaaToT是用APL编写的,但我将使用Iverson的后续语言J,因为我对它更熟悉。我列出的符号示例应该很容易翻译成其他基于APL的语言。为了让非APL用户更清楚,我还将使用非惯用的J。
在我们讨论J的符号之前,我需要先介绍一下它的特性,APL遵循与其他编程语言不同的一套标准和设计理念。它使用的术语也略有不同。
APL以非常简洁而臭名昭著。大多数函数(“动词”)不是描述性的名称,而是单字符。APL甚至使用自己的符号,如⌿和↑,这些符号需要特殊的键盘。J则使用有向图形。(*y)是符号函数。(*.。Y)将笛卡尔坐标转换为极坐标。(*:Y)平方y。
进一步简而言之,每个符号既表示一元函数(一元数),又表示二元函数(二元数)。1当*y给出y的符号时,x*y是乘法。同样,(*.)。和(*:)具有与其一元形式关系不大的二元形式。
这些特性使APL代码具有其特有的“行噪声”密度。这是我编写的一些J代码,用于在CSV中获得随机加权行:
如果我们想谈论APL的影响,我们需要谈论数组。
大多数语言将单个数字(标量)视为基元,将数组视为基元集合。2对数组的操作是通过对数组中的标量重复操作来实现的。如果我想要将数组中的每个元素都加倍,我必须这样做:
定义DOUBLE_ARRAY(A):OUT=a[:]for i,n in Enumerate(Out):Out[i]=2*n Return Out。
我们可以使用像map这样的东西来简化这一过程,但是map本身被定义为遍历数组,标量操作是我们用来模拟数组操作的原语。
J不一样。与将数组作为“标量集合”不同,数组是原语。如果我写1,我会得到一个只有一个元素的数组。如果我写13,我会得到一个有3的数组。所有操作在设计时都考虑到了数组。下面是我如何将数组中的每个元素都加倍:
这不是一个重载运算符:*一次只对整个数组起作用。我们稍后将更详细地讨论这个问题。
当我们超过一维时,第一类数组变得特别重要。大多数语言将矩阵表示为嵌套数组,其中每个元素也是一个数组。不能保证所有的数组都具有相同的长度,并且无法在任何维数组上编写通用运算符。如果我有适用于列表的映射,我必须手动扩展它以处理2D矩阵,并再次扩展它以处理3D张量。
]x=:i.。3 3 0 1 2 3 4 5 6 7 8 6*x 0 6 12 18 24 30 36 42 48。
这样做的一个重要结果是,J数组是纯粹的结构化数据集合,而不是概念性的数据集合。在大多数语言中,嵌套数组强制执行数据的结构和概念表示。由于操作必须针对数组的维数进行专门化,因此我们的算法固定了数据的结构。相比之下,在J中,我们可以随心所欲地对轴进行重新排序。
简短的例子。假设我们有三个光传感器,它们每天获取每小时的读数,总共两天。这里有三个维度的信息:一天中的某一天、一天中的某一小时和特定的传感器。
]x=: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。
在这里,我将数据组织为一个矩阵数组。每个矩阵表示一天,其中行是不同的传感器,列是小时。但我与此组织无关。我可能希望每个传感器有一个矩阵,其中行是小时,列是天。我可以使用一行程序重新排列数据:
1 0 2|:x 0 1 2 3 12 13 14 15 4 5 6 7 16 17 18 19 8 9 10 11 20 21 22 23。
因为我们可以一次处理整个数组,所以我们需要一些方法来讨论数组的组件。向矩阵添加向量没有意义,但是我们可以将向量添加到矩阵的每行或每列。
J用等级来支持这种表达,动词的等级代表它自然作用于数组的多少。秩为0的东西作用于单个元素,秩为1的动词作用于行,秩为2的动词作用于矩阵。加法具有秩(0 0):x+y按元素方式将x和y相加,并考虑y的结构。4.。
]x=:i.。3 3 0 1 2 3 4 5 6 7 8 10+x 10 11 12 13 14 15 16 17 18 10 20 30+x 10 11 12 23 24 25 36 37 38。
我们可以用(";)修饰动词的等级。写入(x+#34;1y)将每行x与每行y相加。
RANK使得在与聚合相同的级别上处理数据子集变得很容易。回到传感器示例:我可以在三个基本维度上切割数据。有了排名,我可以选择我想要的维度。
注:首日0{x 0 1 2 3 4 5 6 7 8 9 10 11 NB.。第一小时0{";1 x 0 4 8 12 16 20 NB。第一个传感器0{";2 x 0 1 2 3 12 13 14 15。
除了改进我们操作数组的方式外,RANK还帮助我们将脚本视为执行的集合,而不仅仅是单个执行。假设我们有一组值,我们想看看有多少值低于某个阈值。但是我们不确定我们想要的阈值是多少;相反,我们应该用不同的阈值多次尝试相同的操作,并比较结果。在大多数语言中,我们会将其作为需要聚合的N个单独调用来执行。使用RANK,我们可以将其视为单个操作。
与加法一样,x<;y的秩为(0 0)。我们不给它排名1,而是给它排名(0,0,_):一次将x的每个元素应用于y的所有元素。
3 57<;";(0_)6 2 8 3 1 5 3 0 7 1 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0。
这种特殊用法如此普遍,以至于J提供了一个特殊的副词u/,作为句法上的糖。
3 57<;/6 2 8 3 1 5 3 0 7 1 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0。
因为我们有完整的运行集,所以我们可以分析所有结果是如何关联的。哪些指数恰好通过了两个门槛?哪些指数至少通过了一个阈值,但不是全部?
注:正好2 2=+/x 1 0 0 0 1 0 nb。至少一个(*./~:+./)x 1 0 0 0 1 0 0 1 0 0(*./~:+./)x 1 0 0 0 1 0 0 0。
您可能已经注意到布尔运算符返回数字。J没有特殊的布尔类型:1为TRUE,0为FALSE。J不仅仅是一个黑客,它将这种等价性集成到它的数组范例中。除此之外,它还提供了一种不同于任何其他语言的过滤方法。
假设你想选择列表中5以下的所有元素。你的过滤思维模式是什么?它可能类似于“检查第一个元素,如果为真,则将其追加到一个新列表中,检查下一个元素,依此类推。”即使您从Filter原语的角度考虑,您也很可能会想象它是如何实现的。过滤的J模型完全不同:
这在双关语上很管用。第(#)个二元体是Copy:给定y的元素y_i,我们将其复制x_i次。
1 2 3 1#';abcd';y=:?~10 4 3 6 2 9 8 5 1 7 0(5&>y)1 1 0 1 0 0 0 1 0 1(5&>y;y)#y 4 3 2 1 0。
我们构造了5>;y的结果,筛子,作为与实际过滤分开的步骤。筛子是一个截然不同的值。这打开了各种用途。我们可以使用相同的筛子过滤不同的列表:
筛子=:5;y 1 1 0 1 0 0 0 1 0 1筛子#0 2 4 6 8 1 3 5 7 9 0 2 6 5 9。
我们也可以在筛子上做手术。我们可以将其反转以拒绝匹配的元素,或将其左移以获取匹配之前的元素:
注:拒绝而不是选择(-.。筛子)#y 6 9 8 5 7 lshift=:1&;(|.!0)LShift筛网1 0 1 0 0 0 1 0 1 0(LShift筛网)#y 4 6 57。
我们甚至可以使用筛子以过滤以外的方式修改原始列表。最简单的示例是(f,y)+y:递增每个满足f的元素。j提供了一种融合映射和过滤的通用机制,5但这涉及到介绍J机制,这超出了本文的讨论范围。
最后,我们可以直接研究筛子的性质。我们可以取平均值来获得通过过滤器的原始数组的百分比。我们可以得到过滤元素的索引之间的距离,或者查看过滤元素在原始数组中是如何聚集的。我们过滤的方式本身就是数据。
与过滤和筛子一样,J有一个基于数组的排序结构:等级。数组的等级(/:y)是置换向量,如果用于索引y,将返回已排序的数组。
[y=:1 9 2 8 3 7 1 9 2 8 37]g=:/:y 0 2 4 5 3 1Nb.。挑选索引g{y 1 2 3 7 8 9。
这从根本上抓住了我们所说的“排序”的意思。很容易定义要排序的列表的含义:增加索引对应于增加值。6但是,这不足以定义排序。以下函数可确保对所有输出进行排序:
您需要指定输出数组具有与输入数组具有相同基数的相同元素,这是一个需要检查的相当复杂的属性。但这一性质是通过应用排列向量免费提供给我们的。7“返回排序的排列”是“排序”最简单的数学定义。
与筛子一样,我们可以独立于原始数组使用等级,例如对不同的数组进行排序。我们还可以将等级作为排列向量进行分析。我们可以反转它,计算原始数组的“未排序”程度,或者找到数组的固定点。
注:颠倒排列/:G 0 5 1 4 2 3Nb。每个元素距离排序有多远?|g-i。6 0 1 2 2 1 4 NB。固定点是什么?G=i。6 1 0 0 0。
这是我在其他语言中最怀念的事情之一。在其他方面中,有了等级可以很容易地保存列表排序的“历史”。存储长度为N的置换向量只需要≈4N个字节,而原始数组需要多少个字节。您可以在原始视图中查看一组数据,对其进行排序,然后在完成后“翻转”回原始视图。
]sortedy=:g{y1 2 3 7 8 9NB.。Invert g]ig=:/:g0 5 1 4 2 3NB。返回y y=(ig{sortedy)1 1 1。
当人们想到API时,他们会想到语法。但这不是APL的本质,没有什么能阻止APL变得冗长。APL的本质在于它如何将数组视为基元,以及如何表示数组转换。符号的存在只是为了鼓励探索,帮助核心思想闪耀光芒。它可以帮助我们更好地思考数组和程序。
我可能不会在我的日常编程中使用J,但我很高兴我学会了它,并认为它使我成为一名更好的程序员。如果你对J感兴趣,你可以在这里下载。您也可以在这里在线试用。
我在我的时事通讯上分享了这篇文章的初稿。如果你喜欢我的作品,为什么不订阅呢?
APL是第一个使用“Monad”作为术语的语言。流行的FP意思是30年后才出现的。[返回]。
近几十年来,随着MATLAB和Julia等语言拥有数组优先的原语,以及Numpy等库对现有语言进行扩充,这种情况发生了一些变化。其中大部分都是受到APL的启发。[返回]
好吧,这是个小谎言。作为优化,J会将其视为标量。但在道德上,它表现为一个元素的数组,除非在非常特殊的情况下。[返回]。
X的维度应该与y的“最高有效维度”相匹配。因此,如果x是2x3矩阵,y是2x3x19x7矩阵,那么x+y是可行的。[返回]。
更确切地说,是一种可以用来融合两者的机制。J中的几乎所有东西都具有常见用例的七重职责。[返回]。
我现在只考虑整数列表,但是相同的规范可以扩展到任意排序键。[返回]