编程语言中的「组合性」是什么意思?

编程语言中的「组合性」是什么意思?

PL的讚歌就是组合的讚歌! PL的偉大就是组合的偉大!

这没啥好想的,组合就是组合的字面意义:给你两个X,怎么产生一个更大的X。

基本上,如果你写过程序,你就用过组合 - 除非你连汇编都不碰,只写机器码。

为什么要发明汇编?

很简单:机器码无法组合。假设你写了一段机器码,里面函数sin在地址0x12345,你要用那个函数可以jmp过去。假设你要写另一段机器码,你不能很简单的手动把以前的那一段机器码抄过去!因为你抄过去会抄在不同地址,以前的所有jmp都作废了。

为了解决这,我们抽象掉绝对地址,引入label来表示未知地址,就可以组合代码了!

为什么要发明Fortran?

计算无法组合。如果我们register a b c d里面有4个int,我们要计算(a * b) + (c * d)怎么办?我们需要找一个没用的register,存放a * b,再找一个没用的,放c * d,再加起来。。。如果register刚好用光,恭喜你,你还要先push几个上stack,等下再pop下来。。。但是这很不对啊,我们要个c * d,为什么要关心这么多无关的,比如说a * b用了那个register?如果你的算式复杂点,那更惨,完全管理不过来。。

所以我们抽象掉register/stack object,引入表达式来表示某个会存在register的结果,就可以组合算术了!

为什么要发明Algol?

早期Fortran里面你的If后面只能跟着三个行号,代表结果是0/正/负的时候jmp到那,这很难用 - 如果我们想根据情况进行某一部分计算,然后统一进行下一部分的计算,我们只能先跳过去,然后在三个分支都表示跳回来。。。

于是我们就在Algol中加入block structure,if后面接着语句,也就是说可以嵌套if,让我们可以组合控制流。

为什么要发明Scheme?

为了组合feature。随着lambda the ultimate系列paper的发布,我们发现了,很多时候,我们需要的各种feature只需要用lambda, macro, continuation三件装就能设计出来。

于是,我们的language就不需要加入成千上万的特性(成本太高),只要有了这三件装,我们就可以想要啥特性,自己实现一下就好了!

而且这些特性还是first class的,也就是说你可以用这些特性来组合出更多特性,也可以任意复用。。。比如说,if在scheme中会返回值,所以你需要value的一切场景,你都可以在里面通过if expression/while造出!(而不像python这样,while不返回值,导致有的情况下需要写多行)

所以说,我们是不是到了发展的极致,剩下的只是修修补补?

远远不是。这不是结束,甚至不是结束的开端,只是前传的谢幕。

我们剩下的问题很明显。

在我们发现计算机以前,没有任何计算机编程的问题。现在我们的计算机散布到世界各地。。。于是计算机编程也成为世界性的问题。(Dijkstra)那现在我们有了无数的程序,如何管理这些程序也就成为了同样重大的问题。也就是说,编程语言的好处,不应该只有’如何表示最终程序‘,而应该侧重’如何帮助写出最终程序‘。而为了做到这一点,我们必须做减法。

所以我们远离goto。因为goto不可组合。如果你的一段代码用了goto,你无法后接一段代码,来表示’然后执行这操作‘ - goto很可能在执行的途中给你跳到其他地方。你也难以通过加入assertion来辅助debug - 你的程序可能在任意时刻,通过goto,破坏掉你的assumption。

同理我们也在远离可变性。这是完全一样的原因:当你组合表达式,写出a = f(g(x), h(y))的时候,如果g, h使用了相同的全局变量,你无法说’g(x)会算出这个结果,h(y)会算出这个结果,所以f(g(x), h(y))会算出这个结果‘ - 当你调用g(x)时,会影响h(y),而用h(y)有可能影响f...这依然是某种不可组合性,所以我们反对全局变量。Haskell由于Call by need semantic,直接禁止Reference,但是这只是量的问题 - 认为全局变量该满天飞的,也就只有完全不需维护性的OIer。

另一方面,去除重复的特性也会提高组合性。最常见的反面教材就是有0或多个返回值/参数d的函数。如果任何语言的函数是这样设计的(比如C++),在这种语言中做函数上的抽象将会更加困难 - 如果你在C++中有过写memorization的经历,你该再也清楚不过了:首先你得对void返回进行special case,假装是返回empty tuple,然后你需要用variadic argument把参数装进tuple,然后检测在不在cache里面,最后如果不在cache里面,需要再unpack。。更简单的作法就是把Pair/Unit当作内建概念,然后一切返回/接受void的地方都用Unit,而多参数多返回用Pair表示就好(再加上语法糖)。这样,memo函数就是一个简单的(a -> b) -> (a -> b)!为什么我们去掉了东西,组合性反而提高了?很简单,过去,有多种方法表示多(variadic expression, multiple argument, tuple),于是在各种‘多’之中转换的需求由此而生。而现在,只有一种多:Tuple。现在,不止没有任何转换,一切跟tuple无关的库(比如memo)都不需要考虑‘如果输入有多个怎么办?’这种问题 - 这是tuple的工作,不是你的工作。一个概念,一个特性。

Racket的Contract也是往可组合性上再进一步 - 通过Contract,我们可以对每个模块,单独的检测是否根据well-behaved according to specification。这看上去能用assertion做到,只不过Racket的再高级一些:assertion只能是一阶的,你不能写:assert对于所有输入,输出满足此条件。而Racket可以(Higher Order Contract)。于是,在一个Racket程序中,出现了问题,Racket可以快速定位出不符合Spec的代码,而不需要自己去推测是那出了问题。

所以说,编程语言的很大一部分研究,就是研究如何提高可组合性。这才是最重要的问题。