J语言初探

8th Sept 2015
16 min read
Tags:
j

Noun
Copula
Verb
Adverb & conjunction
求值方式
控制结构
Array-oriented programming
Boxing
Tacit programming
Conjunction弥补操作符数目的不足
Object-oriented programming
APL
安装与运行
学习材料

先看些例子，感受一下J的魅力：

   +/\ 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：

   4 5 6
4 5 6
   'aa'
aa

Copula

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

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

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

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

Verb

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

   % 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：

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

Monadic i.为Integers，用于生成整数序列：

   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的首元素：

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

   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     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。

   (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：

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

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

Adverb & conjunction可以自定义。u、v分别为左右参数：

   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、括号、赋值等的应用场景：

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等控制结构，但很多时候可以被其他操作符代替。

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

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

   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后应用到参数上。

   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循环：

   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的可能划分方案：

           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上：

   # 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)：

3 3
4 4
5 5

参与运算。

Boxing

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

   < 1
┌─┐
│1│
└─┘
   < 1 2
┌───┐
│1 2│
└───┘
   <'abc'
┌───┐
│abc│
└───┘
   < < 1
┌───┐
│┌─┐│
││1││
│└─┘│
└───┘

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

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

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

   > < 1 2
1 2
   > < 'abc'
abc
   > < < 1
┌─┐
│1│
└─┘

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

   <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.确认：

   >b._1
<
   <b._1
>

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

   (1&+)&.> 4;5;6
┌─┬─┬─┐
│5│6│7│
└─┴─┴─┘

Tacit programming

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

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

(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：

% 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，得到一些派生规则：

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形式：

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

Conjunction弥补操作符数目的不足

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

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中定义了不少常量来缓解难以记忆的问题：

   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中定义了大量库函数。

   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__var。var为locale名的box，通过变量var间接引用，也会临时切换locale。

   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：

   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`

   ] 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 Programmers或Learning J。Exploring 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：

// ==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里能找到一些教程。