LUPA开源社区 › 首页 ›业界资讯› 技术文摘 › 查看内容

函数式编程和J编程语言

2014-6-3 14:07| 发布者: joejoe0332| 查看: 8171| 评论: 0|原作者: 白文, LeoXu, zhych, 海王, 中奖啦, 无若|来自: oschina

摘要: 这里是一个使用J编程语言作为例子对函数式编程所做的一个简要介绍. 用几个示例来向您展示函数式语言令人影响深刻的能力，以及它们在数学领域的应用. 讨论了使用J语言作为数学符号替代品. ...

摘要:

　　这里是一个使用J编程语言作为例子对函数式编程所做的一个简要介绍. 用几个示例来向您展示函数式语言令人影响深刻的能力，以及它们在数学领域的应用. 讨论了使用J语言作为数学符号替代品.

　　主要领域：函数式编程，J编程语言.

　　关键词：函数式编程，J编程语言.

1 介绍

　　计算式是一种用来解释语言的机制. 计算机所解释 (执行特定动作的) 的语句，中所周在叫做计算机的机器语言. 因而它跟随关于计算机组织的研究，被关联到有关计算机语言的组织的研究.

　　计算机语言可以用很多种方式分类。而机器语言直接为计算机所解释。更高级别的计算机语言则往往在某种程度上独立于特定的计算机，并且在程序可能被解释（执行）之前需要翻译（编译）成机器语言。语言也依照系统所采用的运算基础模型，而被分成命令解析型和可应用型两类.

　　抽象是计算领域中的一个重要概念. 一般而言，较高级别的语言更具抽象性. 抽象的关键工具是名称的运用. 一些复杂的项目给定了一个名称. 这个名称随后被用来作为一个另外一个项目的构造块，另外这个项目也会被命名，如此等等. 抽象是管理计算机程序的一种重要工具.

2, 函数编程是什么

　　函数式编程不仅仅使用功能的编程语言。函数式编程的方法在实现方式上不同与命令式编程。功能编程范式涉及可靠地派生程序，分析程序、证明程序的正确性。这是因为函数式编程语言都基于从数学思想在，而数学工具可能需要程序推导、分析和证明这样的过程。

　　函数式编程语言（应用语言）至少在以下方式不同于传统的编程语言（命令式语言）：

　　2.1 名称的使用

　　在命令式语言中，名称被关联到其值（状态）在计算过程中会发生变化的内存单元.

　　在应用型语言中，名称被关联到存储在内存中的项目. 一旦在内存中被创建出来，这个项目就再也不会被改变. 名称会被赋值给项目，只在这个项目需要在稍后的某个时间点被引用时，被存储到内存中. 被存储在内存中的项目作为参数用于后续函数式计算过程的函数中.

　　例如，在C（一种命令式语言）中，我们可能会这样写:

   int foo;
...
   foo = 4;

　　此例中我们将名称foo同一个大小足以容纳一个整形的特定内存单元相关联. 它在那一刻的状态是不确定的. 后来foo被赋值为4, 如示例，其状态就变成了4.

　　在J（一种应用型语言），我们可能会这样写:

   foo =: 4

　　一个项目 4 在内存中被创建，而名称foo被赋值到那个项目.

　　请注意在C中我们会说值4被赋值给了foo，而在J中我们会说名称foo被赋值给了4. 这一差别是微妙的. 使用命令式语言的关注点在于内存单元，还有程序执行期间他们的状态如何改变.

　　使用函数式语言的关注点在于内存中的项目. 一个项目一旦创建，它就再也不会被改变. 名称在它们提供对某些被存储在内存中的东西的引用，而不是一个普通的数据，这种意义上，更具抽象性. 函数被应用到项目来产生结果项目，而这一过程将重复直至运算完成.

　　2.2 状态改变

　　在命令式语言中，计算设计到被命令内存单元的状态改变.

　　例如，考虑一下底下的的C (一种命令式语言) 程序:

#include <stdio.h>
#include <stdlib.h>
int main (int argc, char *argv[])
{ int sum, count, n;
  count = 0;
  sum = 0;
  while (1 == scanf("%d\n", &n))
   { sum = sum + n;
     count++;
   }
  printf("%f\n", (float)sum / (float)count);
  exit(0);
}

　　程序会从标准输入流中读入一些整型值，计算这些值的平均值，并将这个平均值写到标准的输出流。在平均值计算的一开始，内存单元count和sum的状态被初始化为0. 内存单元n针对每一个个整形读取做出改变. 另外，sum的状态会累加每一个读取的整形数，而count的状态会递增读取的整形数的个数. 一旦所有的整形数读取完了，它们的sum的累加值和计数也就知晓，那样平均值就可以被计算出来了.

　　为了使用C的平均值计算程序，人们必须编译这个程序.

[jhowland@Ariel jhowland]$ make ave
cc     ave.c   -o ave
[jhowland@Ariel jhowland]$ echo "1 2 3" | ave
2.000000
[jhowland@Ariel jhowland]$

　　使用函数式语言，计算涉及到函数应用程序. 复杂的计算需要一个应用程序的结果作为另外一个应用程序的参数. 这个过程被称作功能性组合. 函数式语言可能会有特殊的组合规则被应用与程序中. 基于数学函数思想的函数式语言，从数学中获得了不少的好处. 数学的技术和工具就可以被用于 (推导，简化，转换，以及证明正确性) 程序的有关方面.

　　我们先看下面这个J（一种应用语言）程序的例子：

+/ % #

　　这个程序计算来自标准输入的一列数字的平均值。结果（因为没有给结果指定参数名）使用标准输出显示。

　　这个J 平均值程序有几个有趣的特点.

程序简洁.
程序存在没有命名的内存单元.
程序不分配任务.
数字不是挨个处理的。
该算法被表示没有参考的数据.

　　使用J 平均值程序时，你应该把程序和数字表放在一个J计算机（解释器）的标准输入流中。

[jhowland@Ariel jhowland]$ echo "(+/ % #) 1 2 3" | jconsole
   (+/ % #) 1 2 3
2
   [jhowland@Ariel jhowland]$

　　这个J 平均值程序包含三个功能。

+/ 加法
% 除法
# 计数

　　当一个三功能的程序被应用到一个单一的参数，y，则下列组成的交叉规则被使用。

(f g h) y = (f y) g (h y)

　　在这个J 平均值程序中， f是功能+ / ，表示相加;g是功能％，表示相除；＃是计数功能，计算元素列表中的元素的个数。

　　J求平均值的程序需要更多解释。/ (insert)是一个函数，它的作用是使两个参数的函数（二价元素）可用，它的返回值是一个重复获取导出函数参数列表中参数的函数，。例如，+/调用一个函数计算它的参数列表中的参数之和。*/导出一个函数计算它的参数列表中的参数。许多函数式语言允许在导出函数中设定返回值为函数类型。然而多数命令式语言却没有这个功能。

　　例如，调用导出函数 +/可以计算它的参数列表之和，*/计算参数列表之积。

2.3 表达式

　　函数式语言专门处理产值表达式。通常情况下，一个表达式产生一个值。

　　命令式语言使用语言结构（如赋值）——在计算过程中，被用来去描述指定内存单元的状态变化，如 C 中的 while 循环。这样的语言中包含很多不产生任何值的语句，以及一些对其他条目产生副作用的语句，如修改其他条目的值。

2.4 副作用

　　命令式语言可能会有产生副作用的语句。如，在C语言写的平均值程序中包含count++;这样一条语句，该语句引用了count的值（这个平均值程序并没有用到这个引用），并将它的值增1。这个C语言版的程序依赖于这个副作用。

　　纯函数式的语言没有副作用。

3 为什么要学习函数式编程

　　函数式编程之所以重要有以下原因：

3.1 可任意赋值

　　函数式语言允许程序不事先分配内存。结构化的命令式语言（没有goto语句）使得程序容易派生，便于理解和追踪。类似的，assignment-free函数语言也有相同的优点。

3.2 抽象层次高

　　函数式语言提倡使用更高层次的抽象。例如，函数可以作为函数调用的返回值。函数可以像数据一样被操纵。现存的函数可以被修改，也可以联合组成新的函数。函数式编程包含大量的工作单元而很少使用个体声明。算法可以被直接实现而不引用任何数据。

3.3 并行计算

　　函数式编程语言允许应用程序处理数据集合而不是强制性迭代处理集合中的每项数据。这些应用程序可以任意赋值并且独立求值，函数式编程语言提供了并行处理结构化数据的理想范式。

3.4 人工智能

　　函数式语言在人工智能领域得到广泛的应用。AI研究者在 LISP程序语言的基础上做了许多早期的开发工作，虽然它不是一个纯粹的函数式语言，但对大多数函数式语言的设计产生了重要的影响。

3.5 原型设计

　　在复杂系统的设计，函数式语言通常会制定设计规范并且开发一个原型实现系统的主要功能。函数式语言简单的语义和严格的数学基础使它成为复杂系统功能设计的理想工具。

3.6 理论

　　函数式语言的数学基础提供了与计算机科学理论的衔接。问题的可判定性可能代表了不同函数框架应用。例如，denotational语义的本质是将命令式程语言序转化为等价的函数式语言程序。

4 J函数式编程语言

　　J编程语言[Burk 2001,Bur 2001,Hui 2001]是一个函数式编程语言。J使用插入记号和特殊符号表示原函数，诸如+或者 %，或者在 .或者 :后面添加特殊符号或者单词。每个函数名称可能作为一元参数（一个变元，通常写在右边）或者二元参数（两个变元，一个在左边，另一个在右边）。

　　J语言内置函数列表在数字1和2里展示。这些数字展示了在*左边的一元函数定义和在右边的二元函数定义。例如，函数标记+:代表一元doubl参数e和二元not-or(nor)参数。

　　Figure 1: J Vocabulary, Part 1

　　J使用简单的规则判定函数表达式的优先级。一元变量或者右边的二元变量是整个表达式右边的值。左边二元变量的值作为优先项赋值给左边的二元变量。括号用于更改表达式的优先级。例如，表达式3*4+5值为27，然而表达式（3*4）+5的值为17。

Figure 2: J Vocabulary, Part 2

　　高优先级函数（返回值为函数的函数）必须在其它函数调用前完成（必须）。有两种类型的高优先级函数同 ; adverbs （高优先级一元函数）和conjunctions （高优先级二元函数）。数字1和 2用粗斜体表示adverbs，用粗体表示conjunctions 。例如，与运算符 (Curry)绑定一个固定参数值的二元函数，返回一个一元函数(4&*导出一个求4的幂级数的一元函数).。

　　J是一种函数式编程语言，它使用函数化组成方式模拟计算处理。J提供一种叫做隐式（tacit）的编程方式。隐式（Tacit）编程无需引用他们的参数，并且常常使用特别的构成规则，这被叫做hooksand forks。显式编程这种传统的控制结构也被支持。内部一个显式的定义，左边的参数是一对的，总是被命名为 x. 同时单参数（与右边的双参数类似）会被命名为 y. 。

　　J提供了一个强有力的简单数据结构集合比如（列表）list和（数组）array。数据（在J语言中撤销是函数的第一类状态），一旦将标识创建为常量或者函数应用，就不可以再修改。数据项具备这样几个属性，例如类型（type）（数字或者字符，确切值或者不确定值等等），图形（shape）（每个轴线上都有长度的列表（list））和排（rank）（轴线上的数字）。名称（Name）是一个抽象的工具（非内存单元），它可以被赋值（或者反向赋值）为数据或者函数。

5 J 语言编程示例

　　函数式编程中计算的基础模型是函数组合. 一个程序包含一系列的函数应用程序，它们互相协作共同计算出程序的最终结果. J编程语言包含丰富的原生函数，使用更高级别的函数和组合规则将它们组合在一起供程序使用. 为了更好的理解理解组合规则和更高级别的函数，我们可以使用标准的数学符号以符号的形式构造出一些语言的特性。我们先从使用字符数据给参数名字赋值开始.

   x =: 'x'
   y =: 'y'

　　我们希望有一些命名为 f. g, h, 以及 i 的函数, 每一个函数的形式如下 :

   f =: 3 : 0
'f(',y.,')'
:
'f(',x.,',',y.,')'
)

　　我们使用一种函数生成定义，它使用到了一个模式，而不是为每一个函数都输入定义（以及他们的反函数）.

   math_pat =: 3 : 0
'''',y.,'('',y.,'')''',LF,':',LF,'''',y.,'('',x.,'','',y.,'')'''
)

　　应用 math_pat 会产生如下定义:

   math_pat 'f'
'f(',y.,')'
:
'f(',x.,',',y.,')'

　　使用我们所拥有的显示的定义 (:) 以及反向定义 (:.):

   f =: (3 : (math_pat 'f')) :. (3 : (math_pat 'f_inv'))
   g =: (3 : (math_pat 'g')) :. (3 : (math_pat 'g_inv'))
   h =: (3 : (math_pat 'h')) :. (3 : (math_pat 'h_inv'))
   i =: (3 : (math_pat 'i')) :. (3 : (math_pat 'i_inv'))

　　它会为 f. g, h, 和 i 中的每一个函数都生成定义，还有每一个函数的反函数的符号式定义.

　　接下来，我们使用这些定义来探索J的一些组合规则以及更高级别的函数.

   f g y
f(g(y))
   (f g) y
f(y,g(y))
   x f g y
f(x,g(y))
   x (f g) y
f(x,g(y))
   f g h y
f(g(h(y)))
   (f g h) y
g(f(y),h(y))
   x f g h y
f(x,g(h(y)))
   x (f g h) y
g(f(x,y),h(x,y))
   f g h i y
f(g(h(i(y))))
   (f g h i) y
f(y,h(g(y),i(y)))
   x f g h i y
f(x,g(h(i(y))))
   x (f g h i) y
f(x,h(g(y),i(y)))
   f@g y
f(g(y))
   x f@g y
f(g(x,y))
   f&g y
f(g(y))
   x f&g y
f(g(x),g(y))
   f&.g y
g_inv(f(g(y)))
   (h &. (f&g))y
g_inv(f_inv(h(f(g(y)))))
   x f&.g y
g_inv(f(g(x),g(y)))
   f&:g y
f(g(y))
   x f&:g y
f(g(x),g(y))
   (f&g) 'ab'
f(g(ab))
   (f&(g"0)) 'ab'
f(g(a))
f(g(b))
   (f&:(g"0)) 'ab'
f(  
g(a)
g(b)
))))
   f^:3 y
f(f(f(y)))
   f^:_2 y
f_inv(f_inv(y))
   f^:0 y
y
   f 'abcd'
f(abcd)
   f/ 2 3$'abcdef'
f(abc,def)
   (f/"0) 2 3$'abcdef'
abc
def
   (f/"1) 2 3$'abcdef'
f(a,f(b,c))
f(d,f(e,f))
   (f/"2) 2 3$'abcdef'
f(abc,def)
   'abc' f/ 'de'
f(abc,de)
   'abc' (f"0)/ 'de'
f(a,d)
f(a,e)

f(b,d)
f(b,e)

f(c,d)
f(c,e)
   'abc' (f"1)/ 'de'
f(abc,de)

5.1 数字

　　浮点数用诸如3e10来表示并且可以通过使用谓词x:转换为精确的定点数。

   x: 3e10
30000000000

　　有理数通常使用r来分割分子和分母。

]a =: 1r2
1r2
      (%a)+a^2
9r4
   %2
0.5
   % x: 2
1r2

　　使用整形谓词（$）我们可以创建一个 $3 \times 3$ 表格并且赋以精确的值。

 ] matrix =: x: 3 3 $ _1 2 5 _8 0 1 _4 3 3
_1 2 5
_8 0 1
_4 3 3

   ]inv_matrix =: %. matrix
  3r77  _9r77  _2r77
_20r77 _17r77  39r77
 24r77   5r77 _16r77

   matrix +/ . * inv_matrix
1 0 0
0 1 0
0 0 1

　　阶乘函数（！）中使用定点数将产生巨大的数字。

   ! x: i. 20
1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800
87178291200 1307674368000 20922789888000 355687428096000 6402373705728000
121645100408832000

   ! 100x
93326215443944152681699238856266700490715968264381621468592963895217
59999322991560894146397615651828625369792082722375825118521091686400
0000000000000000000000

　　统计!n末尾有多少个0，我们可以使用函数q:，这个函数可以统计它整数参数中的有效数字。!n后面的0都有因子（乘法中的因子，比如6=2*3，2和3就是6的因子）2和5。显然 !n因子2的个数远比因子5.我们可以通过如下代码统计!n中0的个数。

   +/ , 5 = q: >: i. 4
0
   !6
720
    +/ , 5 = q: >: i. 6
1
   !20x
2432902008176640000
    +/ , 5 = q: >: i. 20
4

　　J支持复数，使用符号j来区分实部和虚部。

   0j1 * 0j1
_1
   +. 0j1 * 0j1 NB. real and imaginary parts
_1 0
   + 3j4 NB. conjugate
3j_4

　　还支持如下的数字：

   1p1 NB. pi
3.14159
   2p3 NB. 2*pi^3
62.0126
   1x1 NB. e
2.71828
   x: 1x1 NB. e as a rational (inexact)  
6157974361033r2265392166685
   x: 1x_1 NB. reciprocal of e as a rational (inexact)
659546860739r1792834246565
   2b101 NB. base 2 representation
5
   1ad90 NB. polar representation
0j1
   *. 0j1 NB. magnitude and angle
1 1.5708
   180p_1 * 1{ *. 3ad30 * 4ad15 NB. angle (in degrees) of product
45

　　我们可以像下面一样定义一个函数 rotate 和rad2deg：

   rotate =: 1ad1 & *
   rad2deg =: (180p_1 & *) @ (1 & {) @ *.

　　rotate函数在单位圆上逆时针旋转1弧度，而rad2deg绕极轴旋转一个用复数表示的三角度。

 rad2deg (rotate^:3) 0j1 NB. angle of 0j1 after 3 degrees rotation
93
   +. (rotate^:3) 0j1 NB. (x,y) coordinates on the unit circle
_0.052336 0.99863
   +/ *: +. (rotate^:3) 0j1 NB. distance from origin
1
   +. rotate ^: (i. 10) 1j0 NB. points on the unit circle
       1         0
0.999848 0.0174524
0.999391 0.0348995
 0.99863  0.052336
0.997564 0.0697565
0.996195 0.0871557
0.994522  0.104528
0.992546  0.121869
0.990268  0.139173
0.987688  0.156434

　　单位圆的绘制在数字3中展示：

   'x y'=: |:  +. rotate ^: (i. 360) 1j0
   plot x;y

　　Figure 3: 单位圆的绘制

5.2 算法和流程

　　Howland [How 1998]经常使用递归的Fibonacci函数描述递归和迭代过程。在J语言中，递归Fibonacci 定义如下：

fibonacci =. monad define
if. y. < 2
  do. y.
  else. (fibonacci y. - 1) + fibonacci y. - 2 
end.
)

　　使用 fibonacci 计算从0开始计算10个 fibonacci 整数：

 fibonacci "0 i.11
0 1 1 2 3 5 8 13 21 34 55

　　Howland [ How 1998 ]也阐述了接续（即优先次序）的概念；在表达式中，一元表达式表示计算子表达式的结果

Given a compound expression e and a sub-expression f of e, the continuation of f in e is the computation in e, written as a monad, which remains to be done after first evaluating f. When the continuation of f in e is applied to the result of evaluating f, the result is the same as evaluating the expression e. Let c be the continuation of f in e. The expression e may then be written as c f.

Continuations provide a ``factorization'' of expressions into two parts; f which is evaluated first and c which is later applied to the result of f. Continuations are helpful in the analysis of algorithms.

　　用定义分析递归的fibonacci函数，fibonacci 每次递归都包含一个fibonacci函数。因此，至少有一次递归过程不是单个过程，fibonacci 函数的执行是一个递归过程。

　　定义一个一元函数fib_work，统计fibonacci的执行次数并作出评估。fib_work 是一个J语言定义的序列函数。

ib_work =. monad define
if. y. < 2
  do. 1
  else. 1 + (fib_work y. - 1) + fib_work y. - 2
end.
)

　　应用fib_work计算从0到10整数递归的次数：

   fib_work "0 i.11
1 1 3 5 9 15 25 41 67 109 177

5.2.1 实验

　　考虑一个实验，评估工作站上执行fibonacci需要多长时间。先估计fib_work 100，尽管上面已经给出递归过程的定义，但有必要给出一个迭代过程的定义以便于评估。考虑下面的函数定义：

fib_work_iter =: monad def 'fib_iter 1 1 , y.'

fib_iter =: monad define
('a' ; 'b' ; 'count') =. y.
if. count = 0
  do. b
  else. fib_iter (1 + a + b) , a , count - 1
end.
)

　　使用fib_work_iter可以得到与fib_work相同的统计递归次数结果：

  fib_work_iter "0 i. 11
1 1 3 5 9 15 25 41 67 109 177

　　下面使用fib_work_iter 计算fib_work 100（精确的）。

fib_iter 100x
57887932245395525494200

　　最终，在工作站上执行一系列fibonacci 函数递归所使用的时间不超过20s。

使用3500 applications/sec作为估计：

0 3500 #: 57887932245395525494200x
16539409212970150141 700
   0 100 365 24 60 60 #: 16539409212970150141x
5244612256 77 234 16 49 1

　　最大结果是 5244612256 个世纪。

　　解决这一问题的一种可选的实验性方法是对递归的fibonacci定义进行计时，并从成果时间的倍数中寻找模式.

   [ experiment =: (4 10 $'fibonacci ') ,. ": 4 1 $ 20 21 22 23
fibonacci 20
fibonacci 21
fibonacci 22
fibonacci 23
   t =: time "1 experiment
   t
2.75291 4.42869 7.15818 11.5908
   (1 }. t) % _1 }. t
1.60873 1.61632 1.61924

　　请注意赔率大概是一样的，这意味着计算fibonacci的时间应该是指数级的。执行下面的计算，作为对事件的一个估计值:

   [ ratio =: (+/ % #) (1 }. t) % _1 }. t
1.61476
   0 100 365 24 60 60 rep x: ratio^100
205174677357 86 306 9 14 40

　　这一试验性质的方法产生了某种比 205174677357 更大的估计值. 同学们应该警惕任意试验性设计中的某些缺陷.

5.3 统计

假设我们有下面这些测试成绩.

   [ scores =: 85 79 63 91 85 69 77 64 78 93 72 66 48 76 81 79
85 79 63 91 85 69 77 64 78 93 72 66 48 76 81 79
   /:~scores  NB. sort the scores
48 63 64 66 69 72 76 77 78 79 79 81 85 85 91 93

在干叶图上可以看到一条轴上有观察的单元数字值（页），还有其它轴上的更多重要的数字值（干）. 这些可能是从如下这些分数中计算得来的:

   stem =: 10&* @ <. @ %&10
   leaf =: 10&|
   sl_diagram =: ~.@stem ;"0 stem </. leaf
   sl_diagram /:~scores
+--+-----------+
|40|8          |
+--+-----------+
|60|3 4 6 9    |
+--+-----------+
|70|2 6 7 8 9 9|
+--+-----------+
|80|1 5 5      |
+--+-----------+
|90|1 3        |
+--+-----------+

一个更加传统的频率表可以由 fr =: +/"1 @ (=/) 的定义得出. 左边的参数是一个频率的范围，而右边的参数是一个观察值的列表.

   4 5 6 7 8 9 fr <. scores%10
1 0 4 6 3 2

这个频率表可以用一个使用了内置统计库的柱形图来展示(图 4).

图 4: 分数频率的柱形图

   pd 'new'
   pd 'type bar'
   pd 'xlabel "40" "50" "60" "70" "80" "90"'
   pd 4 5 6 7 8 9 fr <. scores%10
   pd 'show'

　　当掷硬币大量的次数，头朝上的数量比上投掷的总数应该会接近0.5. 然而，但是头朝上和底朝上的次数差的绝对值可能会非常巨大. 这可以使用下面的试验来描述, 结果显示在图 5 和 6 中.

   toss =: >: i. n =: 500   NB. 500 coin tosses
   heads =: +/\?n$2
   ratio =: heads % toss
   diff =: |toss - 2*heads

   toss =: >: i. n =:10  NB. a small trial
   toss;ratio
+--------------------+------------------------------------------------------------+
|1 2 3 4 5 6 7 8 9 10|1 0.5 0.666667 0.75 0.6 0.666667 0.714286 0.625 0.555556 0.5|
+--------------------+------------------------------------------------------------+
   toss;diff
+--------------------+-------------------+
|1 2 3 4 5 6 7 8 9 10|1 0 1 2 1 2 3 2 1 0|
+--------------------+-------------------+

图 5: 头朝上的比率

图 6: 头朝上和底朝上的差值

5.4 Groups

我们可以从数论来试验一些基本的想法来证明J的表现力.

   12 +. 5  NB. greatest common divisor
1
   27 +. 3
3
   1 2 3 4 5 6 7 8 9 10 11 12 +. 12
1 2 3 4 1 6 1 4 3 2 1 12
   NB. The numbers <: 12 which are coprime with 12
   (1 = 1 2 3 4 5 6 7 8 9 10 11 12 +. 12) #  1 2 3 4 5 6 7 8 9 10 11 12
1 5 7 11
   NB. The numbers <: 12 which have common factors with 12
   (-. 1 = 1 2 3 4 5 6 7 8 9 10 11 12 +. 12) #  1 2 3 4 5 6 7 8 9 10 11 12
2 3 4 6 8 9 10 12
   NB. 8 9 19 have common factors but do not divide 12
   ((-. 1 = 1 2 3 4 5 6 7 8 9 10 11 12 +. 12) #  1 2 3 4 5 6 7 8 9 10 11 12) | 12
0 0 0 0 4 3 2 0

接下来，我们概括这些表达式作为函数totatives和non_totatives。

   totatives =: 3 : 0
p =. >: i. y.
(1 = p +. y.) # p
)
   non_totatives =: 3 : 0
p =. >: i. y.
(-. 1 = p +. y.) # p
)
   totatives 12
1 5 7 11
   totatives 28
1 3 5 9 11 13 15 17 19 23 25 27
   non_totatives 12
2 3 4 6 8 9 10 12
   non_totatives 15
3 5 6 9 10 12 15
   divisors =: 3 : 0
p =. non_totatives y.
(0 = p | y.) # p
)
   divisors "0 (12 27 100)
2 3  4  6 12  0  0   0
3 9 27  0  0  0  0   0
2 4  5 10 20 25 50 100

totatives 函数中n的数量被称为n的欧拉函数. 我们可以定义totient =: # @ totatives. 另一种隐形的定义是phi =: * -.@%@~.&.q:.

   (totient "0) 100 12
40 4
   phi 100 12
40 4

欧拉定理指出给定一个整数与互质, 然后 $modulo (n,i^{totient (n))}) = 1$ . 这导致了定义:

   euler =: 4 : 'x. (y.&| @ ^) totient y.'
   2 euler 19
1
   2 euler 35
1
   3 euler 28
1
   3 euler 205
1
   3 euler 200005
1

两个 totatives 中的产物 , 是一个 totative 中 n. 我们可以使用J的表 (/) 副词看到这一点.

   totatives 12
1 5 7 11
   12 | 1 5 7 11 */ 1 5 7 11
 1  5  7 11
 5  1 11  7
 7 11  1  5
11  7  5  1

我们注意到，我们有一组（封闭，单位元，逆，和关联性）。有一个表副词可以用来展示上述的结果。

   table
1 : 0
u.table~ y.
:
(' ';,.x.),.({.;}.)":y.,x.u./y.
)
   12&|@* table totatives 12
+--+-----------+
|  | 1  5  7 11|
+--+-----------+
| 1| 1  5  7 11|
| 5| 5  1 11  7|
| 7| 7 11  1  5|
|11|11  7  5  1|
+--+-----------+

请注意，12的totatives的另外残基12不形成一个组。

    12&|@+ table 0 , totatives 12
+--+------------+
|  | 0 1  5 7 11|
+--+------------+
| 0| 0 1  5 7 11|
| 1| 1 2  6 8  0|
| 5| 5 6 10 0  4|
| 7| 7 8  0 2  6|
|11|11 0  4 6 10|
+--+------------+

　　

　　首先要考虑 totatives的值

   p: 6
17
   totatives 17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
   17&|@* table totatives 17
+--+-----------------------------------------------+
|  | 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16|
+--+-----------------------------------------------+
| 1| 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16|
| 2| 2  4  6  8 10 12 14 16  1  3  5  7  9 11 13 15|
| 3| 3  6  9 12 15  1  4  7 10 13 16  2  5  8 11 14|
| 4| 4  8 12 16  3  7 11 15  2  6 10 14  1  5  9 13|
| 5| 5 10 15  3  8 13  1  6 11 16  4  9 14  2  7 12|
| 6| 6 12  1  7 13  2  8 14  3  9 15  4 10 16  5 11|
| 7| 7 14  4 11  1  8 15  5 12  2  9 16  6 13  3 10|
| 8| 8 16  7 15  6 14  5 13  4 12  3 11  2 10  1  9|
| 9| 9  1 10  2 11  3 12  4 13  5 14  6 15  7 16  8|
|10|10  3 13  6 16  9  2 12  5 15  8  1 11  4 14  7|
|11|11  5 16 10  4 15  9  3 14  8  2 13  7  1 12  6|
|12|12  7  2 14  9  4 16 11  6  1 13  8  3 15 10  5|
|13|13  9  5  1 14 10  6  2 15 11  7  3 16 12  8  4|
|14|14 11  8  5  2 16 13 10  7  4  1 15 12  9  6  3|
|15|15 13 11  9  7  5  3  1 16 14 12 10  8  6  4  2|
|16|16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1|
+--+-----------------------------------------------+

和

   17&|@+ table 0 , totatives 17
+--+--------------------------------------------------+
|  | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16|
+--+--------------------------------------------------+
| 0| 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16|
| 1| 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16  0|
| 2| 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16  0  1|
| 3| 3  4  5  6  7  8  9 10 11 12 13 14 15 16  0  1  2|
| 4| 4  5  6  7  8  9 10 11 12 13 14 15 16  0  1  2  3|
| 5| 5  6  7  8  9 10 11 12 13 14 15 16  0  1  2  3  4|
| 6| 6  7  8  9 10 11 12 13 14 15 16  0  1  2  3  4  5|
| 7| 7  8  9 10 11 12 13 14 15 16  0  1  2  3  4  5  6|
| 8| 8  9 10 11 12 13 14 15 16  0  1  2  3  4  5  6  7|
| 9| 9 10 11 12 13 14 15 16  0  1  2  3  4  5  6  7  8|
|10|10 11 12 13 14 15 16  0  1  2  3  4  5  6  7  8  9|
|11|11 12 13 14 15 16  0  1  2  3  4  5  6  7  8  9 10|
|12|12 13 14 15 16  0  1  2  3  4  5  6  7  8  9 10 11|
|13|13 14 15 16  0  1  2  3  4  5  6  7  8  9 10 11 12|
|14|14 15 16  0  1  2  3  4  5  6  7  8  9 10 11 12 13|
|15|15 16  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14|
|16|16  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15|
+--+--------------------------------------------------+

最后, 考虑到定义powers 来提高totatives到欧拉力.

   powers =: 3 : '(totatives y.) (y.&| @ ^) / i. 1 + totient y.'
   powers 12
1  1 1  1 1
1  5 1  5 1
1  7 1  7 1
1 11 1 11 1
   powers 17
1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 1
1  2  4  8 16 15 13  9  1  2  4  8 16 15 13  9 1
1  3  9 10 13  5 15 11 16 14  8  7  4 12  2  6 1
1  4 16 13  1  4 16 13  1  4 16 13  1  4 16 13 1
1  5  8  6 13 14  2 10 16 12  9 11  4  3 15  7 1
1  6  2 12  4  7  8 14 16 11 15  5 13 10  9  3 1
1  7 15  3  4 11  9 12 16 10  2 14 13  6  8  5 1
1  8 13  2 16  9  4 15  1  8 13  2 16  9  4 15 1
1  9 13 15 16  8  4  2  1  9 13 15 16  8  4  2 1
1 10 15 14  4  6  9  5 16  7  2  3 13 11  8 12 1
1 11  2  5  4 10  8  3 16  6 15 12 13  7  9 14 1
1 12  8 11 13  3  2  7 16  5  9  6  4 14 15 10 1
1 13 16  4  1 13 16  4  1 13 16  4  1 13 16  4 1
1 14  9  7 13 12 15  6 16  3  8 10  4  5  2 11 1
1 15  4  9 16  2 13  8  1 15  4  9 16  2 13  8 1
1 16  1 16  1 16  1 16  1 16  1 16  1 16  1 16 1

5.5 多项式

　　在这部分我们将讨论多项式的表示和操作。多项式由它的系数决定，所以我们将多项式表示成一个升序的列表而不是通常的降序。例如，多项式被表示为了5 2 0 1.

多项式求值，我们采用如下表示：

 peval =: (#. |.) ~
   5 2 0 1 peval 3
38

p.用来表示多项式求值。

  5 2 0 1 p. 3
38

多项式的加减转化为针对同类项系数的加减：

 psum =: , @ (+/ @ ,: & ,:)
   pdif =: , @ (-/ @ ,: & ,:)
   1 2 psum 1 3 1
2 5 1
   3 psum 1 3 1
4 3 1
   1 2 pdif 1 3 1
0 _1 _1

下面我们考虑多项式的积和衍生的多项式。如果我们使用乘积表，同类项的系数在表的斜对角线倾斜。倾斜副词/.可以访问这些对角线上的值。

   pprod =: +/ /. @ (*/)
   1 2 pprod 1 3 1
1 5 7 2
   pderiv =: 1: }. ] * i. @ #
   pderiv 1 3 3 1
3 6 3
   p.. 1 3 3 1  NB. There is a primitive for derivative
3 6 3

　　为易于表示高抽象级函数，可以考虑使用元素是多项式的矩阵。我们称这个为 boxed table。例如，

[ m =: 2 2 $ 1 2 ; 1 2 1 ; 1 3 3 1 ; 1 4 6 4 1
+-------+---------+
|1 2    |1 2 1    |
+-------+---------+
|1 3 3 1|1 4 6 4 1|
+-------+---------+
   [ n =: 2 3 $ 1 2 3 ; 3 2 1 ; 1 0 1 ; 3 3 3 3 ; _1 _2 3; 3 4 5
+-------+-------+-----+
|1 2 3  |3 2 1  |1 0 1|
+-------+-------+-----+
|3 3 3 3|_1 _2 3|3 4 5|
+-------+-------+-----+

下一步，我们将定义一个新版本的psum, pdif和pprod，假设它们的参数是boxed polynomials。

   psumb =: psum &. >
   pdifb =: pdif &. >
   pprodb =: pprod &. >

之后我们可以为了这些元素是多项式的矩阵定义一个矩阵乘积：

pmp =:  psumb / . pprodb
      m pmp n
+---------------------+---------------+------------------+
|4 13 19 18 9 3       |2 4 3 6 3      |4 12 17 16 5      |
+---------------------+---------------+------------------+
|4 20 45 61 56 36 15 3|2 5 5 8 14 11 3|4 19 43 60 52 25 5|
+---------------------+---------------+------------------+
   m pmp m
+--------------------+-----------------------+
|2 9 14 10 5 1       |2 10 20 22 15 6 1      |
+--------------------+-----------------------+
|2 12 30 42 37 21 7 1|2 13 38 66 75 57 28 8 1|
+--------------------+-----------------------+
   m pmp^:0 m
+-------+---------+
|1 2    |1 2 1    |
+-------+---------+
|1 3 3 1|1 4 6 4 1|
+-------+---------+
   m pmp^:1 m
+--------------------+-----------------------+
|2 9 14 10 5 1       |2 10 20 22 15 6 1      |
+--------------------+-----------------------+
|2 12 30 42 37 21 7 1|2 13 38 66 75 57 28 8 1|
+--------------------+-----------------------+
   m pmp^:2 m
+----------------------------------------+----------------------------------------------+
|4 29 88 152 176 148 88 36 9 1           |4 31 106 217 304 309 230 123 45 10 1          |
+----------------------------------------+----------------------------------------------+
|4 35 137 323 521 613 539 353 168 55 11 1|4 37 158 418 772 1055 1094 864 513 222 66 12 1|
+----------------------------------------+----------------------------------------------+
   m pmp^:10  x: &. > m
+-------------------------------------------------...
|1024 29952 424704 3899184 26124316 136500501 5803...
+-------------------------------------------------...
|1024 31488 471040 4577232 32551980 180983051 8205...
+-------------------------------------------------...

5.6 证明

Iverson和其它的作者已经使用J语言写了数本关于数学计算的书。其中一个[Ive 1995]在[Gra 1989]使用J语言描述算法和证明。下面的例子是从[Ive 1995]摘录的。

在定理声明中，一个表达式I和另外一个r相等。我们可以在J语言中使用如下方式表示两者关系：

t=: l -: r

这是我必须匹配r,t必须是常函数1所有输入。t有时叫做同义反复。例如，

l =: +/ @ i.     NB. Sum of integers
r =: (] * ] - 1:) % 2:

如果我们定义n= : ],右边是一个恒等函数，我们可以转化最后一个等式：

r =: (n * n - 1:) % 2:

下一步，

t =: l -: r

注意实验上呈现的，不管输入参数为何，t总是1.

  t 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1

定理证明是从l到r的一系列恒等表达式有序组合。

l
+/ @ i.                            Definition of l
+/ @ |. i.                         Sum is associative and commutative
                                   (|. is reverse)
((+/ @ i.) + (+/ @ |. @ i.)) % 2:  Half sum of equal values
+/ @ (i. + |. @ i.) % 2:           Summation distributes over addition
+/ @ (n # n - 1:) % 2:             Each term is n -1; there are n terms
(n * n - 1:) % 2:                  Definition of multiplication
r                                  Definition of r

当然，上述证明每个表达式是都是一个简单的程序，而证明是一系列有序验证可以将一个表达式转化成另一个。

5.7 J可以作为一种数学符号

Iverson讨论了数学符号在数学计算中的作用。在这篇文章他引用了

A. N. Whitehead

通过减轻大脑不必要的工作负担，一种好的数学符号可以把精力集中在更高级的问题上，事实上增加了脑力劳动的强度。

F. Cajori

一些诸如 , $\sqrt{n}$ , 的数学符号仅适用于正整数，如果应用于浮点数、负数和复数，则可能导致致命错误。

A. de Morgan

数学符号，就像语言一样，并没有严格的限制而得到广泛使用，它的便利性和规定得到了大多数人的认同。

其它著名的引用是与J语言的特性有关：

Friedrich Engels

在科学中，每一种新的术语都会引发革命性的改变

Bertrand Russell

好的符号有一种一种微妙和暗示性的作用，就像一位活生生的老师一般

A. N. Whitehead, 数学的序言作者

这里有一个众所周知的错误，重复已出版的书籍和那些名人的演讲，我们应该富有创新精神并且思考我们可以做什么。事实的情况可能与我们想象的不同，文明的进步提升了数学运算的重要性，但我们却没有深入的思考他们

当然，J语言符号正变得流行，让大脑从繁琐的计算中解放出来，集中精力思考运算背后的事情。它也移除了数学计算的多义性，不要被_3(十减三)和应用程序中的-3混淆。

一种好的数学符号扩展的例子可以在Cajori的外部乘积的引用中(spelled .）找到。+/ . *（矩阵乘积）被表达成一种外部的乘积推导出其它有用的外部乘积诸如+./ . *。

很遗憾，J语言并没有被计算机科学广泛接受，在数学上接受就更少了。

参考文献：

Burk 2001
Burke, Chris, J User Manual, J Software, Toronto, Canada, May 2001.
Bur 2001
Burke, Chris, Hui, Roger K. W., Iverson, Kenneth E., McDonnell, Eugene, E., McIntyre, Donald B.,J Phrases, J Software, Toronto, Canada, March 2001.
Gra 1989
Graham, Knuth and Patashnik, Concrete Mathematics, Addison-Wesley Publishing Company, Reading, MA, 1989.
How 1997
Howland, John E., ``It's All in The Language (Yet Another Look at the Choice of Programming Language for Teaching Computer Science)'', Journal for Computing in Small Colleges, Volume 12, Number 4, April, 1997.
How 1998
Howland, John E.,``Recursion, Iteration and Functional Languages'', Journal for Computing in Small Colleges, Volume 13, Number 4, April, 1998.
How 2002
Howland, John E., ``Building Models: A Direct but Neglected Approach to Teaching Computer Science'', Journal for Computing in Small Colleges, Volume 17, Number 5, April, 2002.
Hui 2001
Hui, Roger K. W., Iverson, Kenneth E.,J Dictionary, J Software, Toronto, Canada, May 2001.
Ive 1995
Iverson, Kenneth, Concrete Math Companion, Iverson Software, Toronto, Canada, 1995.
Ive 2000
Iverson, Kenneth E., ``Computers and Mathematical Notation'',http://www.jsoftware.com/pubs/camndoc.zip, 2000.