正如你所见,入演算名字中的“入”是lambda的象形文字。入演算本质上是一个无类型lambda演算,所以熟悉函数式编程的用户应该能很快通过速查手册来理解它的功能。不过无论如何,我们都从头开始。
和其他所有的tutorial一样, 我们将会以打印“你好,入语言!”作为我们的终极目标。但是作为一个函数式语言,想要达到这一目的并没有那么简单。
头等函数(First Class Function),或者第一类函数,是指函数是入语言的一等公民。和其他函数式语言类似,一切都是函数。常数是函数,入表达式是函数,application也是函数。
最简单的入语言程序是一个入(即lambda,下同)表达式。它表示一个匿名函数。例如:
入甲得甲
它相当于:
lambda x. x
也就是一个“将参数映射到其自身”的函数(俗称id函数)。比较凑巧的是,入字不仅仅和lambda长得很像,而且恰有“输入参数”的意思。
运行你会得到:
(lambda "甲" . "甲")
它被解析为了类似于lambda表达式的格式,但是变量名会保留。
为函数提供参数可以apply。例如:
1之入甲得甲
对应的lambda是:
(lambda x. x) 1
你会得到输出:
(ValInt 1)
这里ValInt表示它是一个整数。
那么我们尝试另一种写法:
入甲得甲,取甲为1者
你可能会期待得到和上一个案例同样的输出,但是实际上你会得到:
(lambda "甲" . (apply "甲" (ValInt 1)))
可以看到,入语言将后续的整个部分当做了lambda表达式的函数部分。这是因为入语言会进行贪心匹配尽可能长的源代码,而后半部分“甲取甲为1者”也是一个合法的表达式。
遗憾的是,为了贴合文言文中并没有标点符号的习惯,入语言并没有括号,所以一元函数和二元函数之间会有二义性。但是我们也有其他的解决方法。
接下来我们使用let来规避上面的问题。
以自为入甲得甲
则自取1者
这样我们就为id函数取了一个中文名:“自”。然后再对1使用“自”函数,得到的当然就是它自己。在手册中提到了“以..为”语法是自带y组合子的。对于不熟悉y组合子的用户,可以先不了解它,只需要知道它可以让函数的名字对函数内部可见,从而可以实现递归。
很多常见的运算都是二元运算。在入语言当中,它们当然也是函数。
入甲入乙得甲与乙之和
得到的结果是
(lambda "甲" . (lambda "乙" . (apply (apply <和: (? -> (? -> ?))> "甲") "乙")))
简单来说,就是先输入两个参数,然后将“和函数”应用到它们上面。
接下来的这个程序将会同时展示以“之”格式和“取”格式求值的方法。它们唯一的区别在于函数一个在前、一个在后。
以【加法】为:入甲入乙得甲与乙之和
则【加法】取甲为1者取乙为2者
方括号【】是用来支持多余一个汉字的标识符的,因为中文没有空格,我们只能通过这样的方式来进行分词。我们基于自带函数“和”定义了一个两个整数相加的函数“【加法】”。事实上,“【加法】”与“和”是等价的。
之后,我们对【加法】分别进行了两次“取”,输入了两个参数。于是【加法】函数计算了二者之和。
(ValInt 3)
顺带一提,虽然程序里面有换行、空格、冒号等符号,但是对于入语言而言它们没有意义,都是可以省略的。加上仅仅是为了美观。
我们可以看看对于一个二元函数如果只给定一个参数会发生什么。
以【加法】为:入甲入乙得甲与乙之和
则【加法】取甲为1者
输出为
(lambda "乙" . (apply (apply <和: (? -> (? -> ?))> (ValInt 1)) "乙"))
可以看到,我们得到的是一个一元函数,接受一个“乙”参数,然后将和函数应用于1与乙之上。这个1替代了原本“甲”的位置,是因为“取甲为1者”将1作为参数送给了函数的第一个“形参”(这里借用一下过程式语言的概念)。这样“每次只给一个参数”的演算方法被称为“科里化”。
但是我们现在离打印一个字符串还很远。因为我们的基础数据类型只有ValInt(整数)和ValNum(实数),并没有ValString。虽然我们可以用ValInt存储unicode编码,但也只解决了单个字符Char的问题。我们需要列表来把Char串成String。
一个有序对就是两个值甲、乙,并且提供一个机制来选择是甲还是乙。当然,它也是函数。实现有序对可以参考之前科里化的思路:先输入两个值,然后再输入一个“【首次】”函数,来选择到底是首还是次。
以对为:入甲入乙入【首次】得甲与乙之【首次】
则1与2之对
结果为:
(lambda "【首次】" . (apply (apply "【首次】" (ValInt 1)) (ValInt 2)))
可以看到,1和2的值已经被科里化“写入”了这个函数,只需要再来一个“首次”来选择它们。而首次的实现就更简单了:
以前为:入甲入乙得甲
以后为:入甲入乙得乙
很明显,前就是两个数取前面那个,后就是两个数取后面那个。完整代码:
以对为:入甲入乙入【首次】得甲与乙之【首次】
以前为:入甲入乙得甲
以后为:入甲入乙得乙
以【一二】为:1与2之对
则 【一二】取前者
打印出了“前者”,也就是:
(ValInt 1)
函数可以调用自己,来实现更为复杂的功能。我们以最经典的递归案例:求阶乘,作为例子。
一个正整数的阶乘等于从它到1的所有整数之积。0的阶乘是1。据此,我们可以大致得到思路:
- 如果参数甲和0相同,值为1
- 否则,值为甲和“甲减一的阶乘”之积
写成入就是:
以【阶乘】为:
入甲
令甲等于0时取1
否则取甲与【阶乘】取甲与1之差者之积
则10之【阶乘】
结果为:
(ValInt 3628800)
可以看到入语言还是相当通顺的。
有数据结构基础的用户应该知道,列表可以用链表实现,而链表的节点包含一个数据项和一个next项、且最后一项的next为0。这和刚刚定义的“序对”是一致的。因此我们可以用链表来实现列表。
对于每一个元素,我们令“前者”为数据项,“后者”为列表剩下的部分,然后,我们用一个叫做“元”的东西表示空。即:
引【./libru/列.入】
以列为
1与2与3与元之对之对之对
如果用(first, second)来表示一个序对,那么这个列就是:
(1, (2, (3, null)))
执行上述代码,得到的结果是相似的:
(lambda "【首次】" . (apply (apply "【首次】" (ValInt 1)) (lambda "【首次】" . (apply (apply "【首次】" (ValInt 2)) (lambda "【首次】" . (apply (apply "【首次】" (ValInt 3)) (ValUnit)))))))
接下来我们要打印列表。打印列表和构造列表正好相反:每次只需要打印列表的第一个元素,然后递归调用列印打印剩下的部分。由于我们用“元”作为列表的结束,所以如果当前列表是“元”,递归就停下来。
引【./libru/序对.入】
以【列印】为:
入列
令列与元相同时取元
否则
以_为列之首之书,
以_为【列印】取列为列之次者
则得元
以列为:
1与2与3与元之对之对之对
则列之【列印】
这里我们使用了引来避免重复定义“序对”。另外,我们使用了_这个名字,来忽略掉用不到的求值结果;但是_仅仅是一个标识符而已。同样,这个函数的返回值也是无用的,所以我们返回了“元”。
打印的结果为:
(ValInt 1)(ValInt 2)(ValInt 3)
实际上,【./libru/列.入】里面自带了一个美化了打印结果的【列印】函数,不需要自己再定义了。
为了思路的连贯性,我们刚刚跳过了对“令……时取”的解释,即便它是自明的。这里还是补充解释一下。
令语法本身也是一个语法糖,是为了实现if-then-else的效果,根据条件从两个或更多取值中选择一个。还记得如何从序对中选择元素吗?
以真为入甲入乙得甲
以伪为入甲入乙得乙
这样,如果条件为真,那么就会得到一个“取前者”的真函数,这样就会选择紧跟着“取”后面的第一个选项。否则,就会得到“取后者”的伪函数,从而选择第二个选项。在第二个选项中,我们也可以递归地选择第一个或者第二个,直到某一个条件满足为止。
这一实现被称为丘奇布尔。
现在终于有了列表,我们可以定义字符串了。正如前文所说,字符串可以用整数列表实现。入语言内置了语法糖来实现字符串到列表的转化,我们可以直接使用:
引【./libru/列.入】
以串为“123”
则串
结果为:
(lambda "【首次】" . (apply (apply "【首次】" (ValInt 49)) (lambda "【首次】" . (apply (apply "【首次】" (ValInt 50)) (lambda "【首次】" . (apply (apply "【首次】" (ValInt 51)) (ValUnit)))))))
我们可以注意到这个结果的形式和刚刚用“对”手动构造的列表非常相似,只不过数值是49,50和51。熟悉ascii码的用户应该能注意到它们正是'1'、'2'和'3'的ascii码。
最后我们来打印字符串。有一个问题在于,我们存的是ValInt,该如何转化为对应的字符呢?
所幸入语言提供了【活字印刷】术,可以直接调用并打印单个整数对应的汉字。仿造刚才列印的思路,我们有:
以【串印】为:
入列
令列与元相同时取元
否则
以甲为列之首之【活字印刷】,
以乙为列之次之【串印】,
则得元
最后我们来享受我们的成果。上面这些函数都由【./libru/列.入】提供,我们只需要“引”用一下:
引【./libru/列.入】
以串为“你好,入语言!”
则串之【串印】
终于,屏幕上出现了
你好,入语言!
万事开头难,虽然还有很多问题没有解释,但是这意味着我们终于走出了第一步。
下一篇教程(正在编写中)将会介绍入语言的一些特性和陷阱。