J语言初探

先看些例子,感受一下J的魅力:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
+/\ i.6 NB. prefix sum of 0~5
0 1 3 6 10 15
(+/ % #) 2 3 4 5 NB. mean
3.5
*/~ 1+i.9 NB. multiplication table
1 2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18 21 24 27
4 8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81
({.;#)/.~ 'abbccc'
┌─┬─┐
│a│1│
├─┼─┤
│b│2│
├─┼─┤
│c│3│
└─┴─┘

最早了解J是受了DarkRaven的教唆,在Project Euler的论坛里能看到很多晦涩但又简洁的J的实现,个个都是code golf的风格,力图节省每一个字节,风格全然不像常规编程语言,J与C的差异感觉尤胜Haskell与C的差异,但没有学。几年后又了解到curimit也在看,之后就认真研究了一下。

Noun

J中的数据称为noun,比如3'string'等。相邻的一串数如3 4 2 5视为一个整体,表示一个array:

1
2
3
4
4 5 6
4 5 6
'aa'
aa

Copula

赋值操作符=.=:被称为copula。=.为local assignment,有点类似局部变量定义;=:为global assignment。

1
2
a =: 4 5 6
b =: 'aa'

赋值的内容可以是noun、verb、adverb、conjunction等。

1
2
3
a_verb =: verb def '- y' NB. 定义一个monadic verb
an_adverb =: \
a_conjunction =: &

Verb

Verb(用uv表示)是一种以noun为参数,返回noun的函数,分为monadic(单元)和dyadic(二元)两种。Monadic verb在右边取一个参数(y),Dyadic verb在左右两边各取一个参数(xy)。

1
2
3
4
5
6
% 4 NB. monadic % (Reciprocal)
0.25
- 3 NB. monadic - (Negate)
_3
2 - _3 NB. dyadic - (Minus)
5

J中大多数操作符都具有monadic和dyadic两种形式。

多个noun和verb组成的表达式,从右到左计算,没有二元操作符优先级的规定,若要改变运算顺序可以使用括号。若形成noun verb noun的形式,则应用dyadic verb而非monadic:

1
2
3
4
5
6
7
8
3 * 1 + 2
9
(3 * 1) + 2
5
% 2 + 2
0.25
% % 2 + 2
4

Monadic i.为Integers,用于生成整数序列:

1
2
3
4
5
6
7
8
9
10
11
12
13
i. 3 NB. 1维array,shape为1
0 1 2
i. 2 3 NB. 2维array,shape为2 3
0 1 2
3 4 5
i. 2 3 4 NB. 3维array,shape为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

Monadic #为Tally,计算array的第0维长度即shape的首元素:

1
2
3
4
# 0 1 2
3
# i. 2 3 4
2

Dyadic ,为Append,拼接两个array。一串数会被解析为一个array,但变量和数不会被解析为一个array,若要拼接需使用,

1
2
3
x =: 3 4
2 , x
2 3 4

Adverb & conjunction

Adverb是单元修饰符,跟在noun或verb后面形成新的noun、verb、adverb、conjunction。

最简单的用法是修饰verb得到新verb,可以看作是FP中的higher-order function。

1
2
3
4
5
6
+ / 1 2 3 4 NB. / (Insert),类似FP中的fold/reduce,作用为计算 1+(2+(3+4))
10
+ / \ 1 2 3 4 NB. \ (Prefix),类似FP中的scan,多个adverb采用左结合,即`(+/)\`,作用为计算 (+/ 1),(+/ 1 2),(+/ 1 2 3)
1 3 6 10
,~ 1 2 NB. ~ (Reflex),作用为计算 1 2 , 1 2
1 2 1 2

Conjunction为双元修饰符,作用在左右两个noun或verb上形成新的noun、verb、adverb或conjunction。

1
2
3
4
5
6
7
8
(5 & -) 4 NB. & (Bond),规则为`m&v y => m v y`、`u&n y => y u n`,即固定某个dyadic verb一边的参数,类似Haskell中infix operator的section
1
(- & 5) 4
_1
%@:% 4 NB. @: (At),规则为`u@:v y => u (v y)`,类似FP中的函数结合。
4
((10&+)^:3) 1 NB. ^: (Power of Verb)。若`n`为非负整数,表示在`y`上应用`n`次`u`;若`n`为-1(J中用`_1`表示),表示`u`的逆运算。很多primitive都设置了逆运算,参看<http://www.jsoftware.com/jwiki/Vocabulary/Inverses>
31

Conjunction ",根据左右参数的词性有三种语义,最常用的形式为u"n y,左边为verb,右边为整数$n$,用于在参数y的所有$n$-cells上应用u。后文会提到,是array-oriented programming的重要组成部分。

若只给conjunction提供一边的参数,则会得到adverb:

1
2
f =: - @: NB. u f = - @: u
g =: @: - NB. u f = u @: -

Noun为值,verb作用在noun上产生新的noun,这两个词性和常规编程语言中表达式的构成尚无太大区别。但adverb和conjunction的结果可能是多种词性,从而无法静态确定局部表达式运算结果的词性,无法表达为context-free grammar,也无法用abstract syntax tree表示。

Adverb & conjunction可以自定义。uv分别为左右参数:

1
2
3
4
5
6
7
8
f =: 1 : 'u' NB. 1代表adverb。定义了一个原样返回的adverb
+/ f 1 2 3
6
where =: 2 : 'u' NB. 2代表conjunction,返回左侧参数。根据求值顺序,右边参数已经被求值了
3 plus 4 where plus =: + NB. `plus =: +`已经执行过了,返回左侧参数。模拟Haskell的where
7
(z+1)*(z+2) where z =: 3
20

求值方式

J的表达式的计算方式比较奇特(http://www.jsoftware.com/help/dictionary/dicte.htm)。待求值的表达式被划分为word,每个word动态确定词性。解释器会设置一个求值栈,有一系列规约步骤。每一步会进行规约或移入:

  • 检查栈顶四个元素,检查它们的词性是否满足预设的9条规约规则之一,是则规约
  • 否则把最右边的word压入求值栈

9条规则描述了monadic verb、dyadic verb、adverb、conjunction、hook、fork、括号、赋值等的应用场景:

1
2
3
4
5
6
7
8
9
edge V N any 0 Monad
edge AVN V V N 1 Monad
edge AVN N V N 2 Dyad
edge AVN VN A any 3 Adverb
edge AVN VN C VN 4 Conj
edge AVN VN V V 5 Fork
edge CAVN CAVN any 6 Bident
name N =. =: CAVN any 7 Is
( CAVN ) any 8 Paren

其中edge表示=. =: (或表达式左端隐含的哨兵字符,name为标识符,A、C、N、V分别为adverb、conjunction、noun、verb。

从中可以归纳出几个求值相关结论,和之前描述的规则吻合:

  • adverb和conjunction优先于verb
  • dyadic verb比monadic verb优先
  • 连续多个verb后跟一个noun时,从右到左求值
  • conjunction是左结合的,且结合verb的能力强于noun

上面所描述的只是J内置verb、adverb、conjunction的沧海一粟,众多的操作符是J表现力强大的重要原因。操作符大多为1~2个字符使得J简短而晦涩。

控制结构

J也包含if、for、while等控制结构,但很多时候可以被其他操作符代替。

1
2
3
4
5
foo =: verb define NB. 多行定义一个verb,行首输入 ) 标示结束
if. 1 do. 1
else. 3
end.
)

if.后面跟的noun为空或者首元素非0时为真。

1
2
3
4
5
6
7
8
9
10
11
f =: +&0
g =: +&1
h =: +&2
t =: ] NB. monadic ] (Same),返回值为参数,类似FP中的identity函数
foo =: verb define NB. 多行定义一个verb,行首输入 ) 标示结束
select. t y
case. 0 do. f y
case. 1 do. g y
case. 2 do. h y
end.
)

当不需要缺省case时,select往往可以用` @.代替。` 是conjunction,把verb转化为gerund(一种box类型,属于noun),@.则根据t的测试结果在gerund array中选择指定元素,恢复成verb后应用到参数上。

1
2
3
4
5
f`g`h
┌─┬─┬─┐
│f│g│h│
└─┴─┴─┘
foo_alternative =: f`g`h @. t'

Verb可以作为adverb、conjunction的参数,但无法作为verb的参数,gerund使得它在另一个verb面前成为first-class object,从中可以幻化出很多奇妙的用法。

上面提到的^: (Power of Verb)当右边参数为_(正无穷大)时表示重复迭代直到值不再发生变化。右边参数为verb时:(u ^: v) y = u ^: (v y)。两个^:常被连用以表示当条件满足时则反复执行,有时可用于替代while循环:

1
2
3
4
halve =: -: NB. monadic -: (Halve)
even =: 0: = 2&| NB. 偶数返回1,奇数返回0
w =: (halve ^: even) ^: _ NB. while (是偶数) 减半
w_alternative =: verb def 'while. even y do. y =. halve y end. y'

另外还有whilst. for. try. catch.等控制结构。

Array-oriented programming

Wikipedia上J被分类为array-oriented programming language,J的array操控能力确实非常强大。

J的array有一个属性称为shape,是表示各维长度的列表。比如i. 2 3 4的shape是2 3 4;单个数、字符称为scalar,其shape为空列表。因此所有noun都具有shape。Shape列表的长度称为rank。

Verb有个属性,也称为rank,表示期望接受的参数的维数。当实际参数的rank高于verb的rank时,J解释器会把参数的shape切分为两部分,frame和cells。下表显示shape为2 3 4的array的可能划分方案:

1
2
3
4
5
6
frame cells
length value rank shape
0-cells 3 2 3 4 0 empty
1-cells 2 2 3 1 4
2-cells 1 2 2 3 4
3-cells 0 empty 3 2 3 4

设verb的rank为$r$,则shape长为$r$的后缀成为$r$-cells,剩余的前缀部分则作为frame。各个$r$-cells独立地被verb作用,产生结果。所有$r$-cells的结果再组装成shape为frame的array(当frame为空时则为scalar),为verb作用在整个参数上的结果。这个过程就像FP语言中的多层map,或者说像多层隐式的循环。

尝试用conjunction "改变#的rank(并不准确,这里为方便描述暂这样表达,实际上产生了一个新verb,其rank为2,可看作#的代理),作用到i. 2 3 4上:

1
2
3
4
5
6
7
8
9
# i. 2 3 4
2
#"3 i. 2 3 4
2
#"2 i. 2 3 4
3 3
#"1 i. 2 3 4
4 4 4
4 4 4

行首三空格是jconsole的提示符。

#"3的rank为3,i. 2 3 4的shape 2 3 4被拆为空的frame和cells 2 3 4两部分,#作用在唯一的3-cells上得到结果,和# i. 2 3 4相同。
#"2的rank为2,i. 2 3 4的shape 2 3 4被拆为frame 2和cells 3 4两部分,#独立地作用在2个2-cells上得到2个结果,2个结果拼装为一个array(frame即为其shape)。
#"1的rank为1,i. 2 3 4的shape 2 3 4被拆为frame 2 3和cells 4两部分,#独立地作用在2*3个2-cells上得到6个结果,2*3个结果拼装为一个2维array(frame即为其shape)。

善加利用rank可以省却很多for循环。

上文讨论的是monadic verb的rank,对于dyadic verb,两个参数可以有不同的rank。比如dyadic +用于计算两数之和,其左右参数的rank均为0。不难想象它可以用于计算两个array的和、两个矩阵的和、或是两个更高维array的和,只要它们的shape一致。实际上+两个参数可以具有不同shape,比如3 4 5 + (i. 3 2),左边参数shape为3,右边参数shape为3 2。Dyadic +的左右rank均为0,左边参数的frame为3,右边参数的frame为3 2。这个计算是合法的理由是较短的frame是较长的frame的前缀。具体发生的过程比较复杂,3 4 5每个数被重复多份,化作了和较长frame相同的形状(3*2):

1
2
3
3 3
4 4
5 5

参与运算。

Boxing

为了支持异构array,J提供了另一种scalar数据类型:box。数、字符、字串(字符array)、array等都可用monadic <操作符转成box,box也可以嵌套:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
< 1
┌─┐
│1│
└─┘
< 1 2
┌───┐
│1 2│
└───┘
<'abc'
┌───┐
│abc│
└───┘
< < 1
┌───┐
│┌─┐│
││1││
│└─┘│
└───┘

Box是scalar,可以和其他box并置组成array,而各box的内容的类型则允许不同。J通过这一机制实现异构array,可以模拟C的struct:

1
2
3
4
5
6
'abc' ; 1 2 3 ; (<3); (i.2 2)
┌───┬─────┬───┬───┐
│abc│1 2 3│┌─┐│0 1│
│ │ ││3││2 3│
│ │ │└─┘│ │
└───┴─────┴───┴───┘

Monadic >用于取出box中的内容:

1
2
3
4
5
6
7
8
> < 1 2
1 2
> < 'abc'
abc
> < < 1
┌─┐
│1│
└─┘

Box可以用于包装多个不同类型的参数,从而用于形成复杂数据结构、模拟多元verb:

1
2
3
4
5
6
7
8
9
10
<0;1;<<1
┌─────────┐
│┌─┬─┬───┐│
││0│1│┌─┐││
││ │ ││1│││
││ │ │└─┘││
│└─┴─┴───┘│
└─────────┘
(<0;1;<<1) { i. 2 2 3 NB. 获取array中相应元素:第0维取0、第1维取1、第2维取非1(即0,2)
3 5

Conjunction &.名为Dual,u&.v y => v^:_1@u@v y,即把参数按v变形后,应用u,之后再应用v的逆运算。

<>互为逆运算,可以用conjunction b.确认:

1
2
3
4
>b._1
<
<b._1
>

对于box类型有个技巧:&.>,这是conjunction &.固定右边参数(Bident规则)后得到的adverb,效果是解开box后采取特定运算,再box回去,类似Perl的Schwartzian transform,例如:

1
2
3
4
(1&+)&.> 4`
┌─┐
│5│
└─┘

Tacit programming

J中tacit programming有两个基石,其一是adverb、conjunction,另一个是hook和fork。

Hook和fork是J中的一套语法,用于把参数传递给多个verb而不用引用参数的变量名,实现tacit programming,规则如下:

1
2
(V0 V1) Ny => Ny V0 (V1 Ny) monadic hook
(V0 V1 V2) Ny => (V0 Ny) V1 (V2 Ny) monadic fork

先看monadic hook,两个verb并置会形成一个新verb,接受的参数会变成双份,这条规则酷似SKI combinator calculus中的S combinator,S x y z = x z (y z)。Dyadic hook是其二元变体。

Monadic fork的设计非常精巧和简洁,三个verb并置。若参数只被使用一次,则不难用& (Bond)以及一系列函数组合实现。当参数要被使用多次时,通常希望在被处理后有个汇合过程。Fork的设计精确地刻画了这一点。效果类似Haskell Reader monad的liftM2

1
2
% pointfree '\x y r -> x r + y r'
liftM2 (+)

5、7、9……个verb也能形成fork,可以看作右边3个verb形成fork后再跟其余verb形成fork:V0 V1 V2 V3 V4 = V0 V1 (V2 V3 V4)。Fork规则的设计精妙如此,可以轻易扩展。

Fork产生的verb也可以用作dyadic,参与fork的V0可以换成noun,得到一些派生规则:

1
2
3
4
Nx (V0 V1) Ny => Nx V0 (V1 Ny) dyadic hook
Nx (V0 V1 V2) Ny => (Nx V0 Ny) V1 (Nx V2 Ny) dyadic fork
(N0 V1 V2) Ny => N0 V1 (V2 Ny) monadic noun fork
Nx (N0 V1 V2) Ny => N0 V1 (Nx V2 Ny) dyadic noun fork

13 : n可以让解释器帮你找tacit形式:

1
2
3
4
13 : 'x-y'
-
13 : '(4*x)-y'
] -~ 4 * [

Conjunction弥补操作符数目的不足

J把ASCII可见字符中几乎所有标点符号(可能是所有)都用上作为primitive了,另外把.:跟在操作符后又得到大量primitive,即便如此毕竟无法涵盖所有常用的verb。因此又有一系列conjunction应运而生,用不同的左参数来表示不同的函数,比如o.家族:

1
2
3
4
5
6
7
8
9
cop=: 0&o. NB. sqrt (1-(y^2))
sin=: 1&o. NB. sine of y
cos=: 2&o. NB. cosine of y
tan=: 3&o. NB. tangent of y
coh=: 4&o. NB. sqrt (1+(y^2))
sinh=: 5&o. NB. hyperbolic sine of y
cosh=: 6&o. NB. hyperbolic cosine of y
tanh=: 7&o. NB. hyperbolic tangent of y
...

相当晦涩,好在编号还是有一些规律,比如奇数表示奇函数,偶数表示偶函数。大量系统函数也是用这种方式定义的:http://www.jsoftware.com/jwiki/Vocabulary/Foreigns

J中定义了不少常量来缓解难以记忆的问题:

1
2
3
4
5
6
7
plus =: verb define
x+y
)
verb
3
define
:0

Object-oriented programming

J中实现了namespace,和J中的很多其他概念一样,给了它一个术语叫locale。同一时刻可以有多个locale,每个locale存放了一些变量定义,同一时刻一个标识符可能存在于多个locale里,但具有不同的定义。J的REPL环境里的默认locale为base。每个locale可以定义search path,当找不到某标识符定义时到search path的locale里找。另外有一个特殊locale名为z,若search path也找不到某标识符定义时会引用z里的定义。z中定义了大量库函数。

1
2
3
4
5
6
7
8
9
10
11
coname '' NB. 当前locale名称。标识符`coname`来自locale `z`
┌──┐
│bb│
└──┘
nl '' NB. 当前locale定义的标识符列表。`nl`来自locale `z`
foo =: 0
nl ''
┌───┐
│foo│
└───┘

J定义了两个语法引用指定locale的标识符:

  • name_loc_。临时切换到locale z,引用标识符name,之后回到原先的locale。
  • name__varvar为locale名的box,通过变量var间接引用,也会临时切换locale。
1
2
names_z_ '' NB. 临时切换到locale `z`后执行verb调用,因此输出`z`定义的标识符列表
...

Locale语法在很多地方和JavaScript的prototype相似,它被用于实现prototype-based object-oriented programming。Class的方法定义在一个单独的locale里,每个object实例也会分配到一个新的locale,设置search path为其class,优先查找自身定义的标识符,若不存在则会在class的locale里找。通过设置class locale的search path可以实现继承。

下面代码定义了一个class:

1
2
3
4
5
6
7
coclass 'Stack' NB. 切换到locale `Stack`
create =: verb def 'a =: 0 $ 0' NB. constructor,被下文的dyadic conew引用
destroy =: codestroy NB. destructor,手动调用,用于删除实例的locale
push =: verb def '# a =: (<y) , a' NB. 方法
top =: verb def '> {. a'
pop =: verb def '# a =: }. a'
cocurrent 'base' NB. cocurrent与coclass等价。回到locale `base`

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
] S =: 0 conew 'Stack' NB. 创建Stack的实例S,相伴的locale为`0`
┌─┐
│0│
└─┘
copath <'0' NB. search path为Stack与z
┌─────┬─┐
│Stack│z│
└─────┴─┘
push__S 'meow' NB. 调用方法,在locale `0`中执行
push__S 'hello'
(top__S '') (1!:2) 2 NB. 打印栈顶,在locale `0`中执行
pop__S ''
(top__S '') (1!:2) 2
destroy__S '' NB. 在locale `0`中执行,删除locale `0`
erase <'S' NB. 删除locale `base`中的名字S

规则很简单,是个优雅的设计。

APL

J for the APL Programmer可以了解J和前辈APL的差异,http://www.jsoftware.com/jwiki/Essays/Bibliography上能找到大量有关APL和J渊源的文章。

关于APL有段评论:

APL is like a diamond. It has a beautiful crystal structure; all of its parts are related in a uniform and elegant way. But if you try to extend this structure in any way - even by adding another diamond - you get an ugly kludge. LISP, on the other hand, is like a ball of mud. You can add any amount of mud to it and it still looks like a ball of mud.” – Joel Moses

用于描述J也很合适。J语法简单,一致性强,很多细节上精巧的涉及和大量简短的原语造就了强大的表现力,但扩展它的功能很困难。不管怎么样,它是个不错的桌上计算器(不需要导入库,默认即有大量primitive),我在xmonad配置(https://github.com/MaskRay/Config/tree/master/home/.xmonad/xmonad.hs)里也为它单独分配了一个快捷键以运行J的REPL环境。改变你对编程语言的刻板印象,它已经出色地完成了任务,不是吗?

安装与运行

J system下载页面:http://www.jsoftware.com/stable.htm。Arch Linux用户可以安装AUR里的j8-git。

可执行文件jconsole为命令行解释器,jqt为Qt图形界面。j8-git则提供了/usr/bin/j8

学习材料

http://www.jsoftware.com/jwiki/Books/Beginners列出了一些关于J的书。如果不愿花费太大工夫、只想简单了解的话,可以看44页的Easy J,深入学习的话则可以看较全较新的J for C ProgrammersLearning JExploring Math和J Phrases给出了大量例子,可作为习题集阅读。

上面提到的书中很多能在http://www.cs.trinity.edu/About/The_Courses/cs2322/j-books/找到PDF版本。

http://www.jsoftware.com/jwiki/NuVoc是词典,用于查阅各primitive的语义。

http://rosettacode.org/wiki/Category:J也有大量J代码。可以写一段UserScript以自动跳转到J:

1
2
3
4
5
// ==UserScript==
// @name RosettaCode jump to J
// @match http://rosettacode.org/wiki/*
// ==/UserScript==
location.href = '#J'

或者下载别人整理的代码:https://github.com/acmeism/RosettaCodeData/tree/master/Lang/J

运行jqt,打开Tools->Package Manager,安装labs/labs,之后在Help->Studio->Labs里能找到一些教程。