My Profile Photo

wlnirvana


Youth is not a time of life, it is a state of mind.


子程序(函数)考古学

2018年,我开始在科蚪实务学堂——北京的一所打工子弟公益职高——做志愿者,教学生们编程。从最初的Python,到现在的Java,无论哪种语言,我发现“函数”总是学习过程中的一个难点。后来听另一位志愿者说,他曾经做过一门网课,也是讲到有参数的函数时,学生开始大量退课。

仔细想想,对于没有上过高中、文化课基础不好的中职学生,甚至对于一些文科出身的大学生来说,函数这个概念本身可能确实不容易理解。以Java为例,完整的函数,涉及到变量、类型、传参、调用、作用域等许多知识。

作为职业程序员,这些基本的技术已经深入到我们的日常生活之中,所以也许会觉得简单,进而对学生学得慢感到困惑。那么,如果我们转换一下视角,仍然是函数这项技术,问你语句和表达式有什么差别、unit和void类型异同何在、为什么求值多用applicative而非normal顺序、绑定时lexical相比dynamic作用域的优势究竟在哪,你(假如不太了解PLT的话)是不是也突然觉得,小小一个函数原来水这么深?这些流动儿童初次接触函数的时候,也许就是这种感受。

也正是因此,我对函数在编程语言(而非数学)中的历史产生了兴趣:有没有可能营造一种皮亚杰式的学习情景,让学生自发地重走早期编程语言发展之路,自然而然地自己发明出函数?这篇文章就是我对这段历史的一个简单梳理。成果其实比较令人失望,因为结论大致是函数历史对于今天的学习指导意义不大。不过姑且记录下来,聊以慰藉,也算不费自己辛苦一场。

需要指出的是,为了区别数学中的函数,将话题局限在编程领域之内,我特地在题目中用了“子程序”这样的字眼——也许有一定误导性,但只好两害相权取其轻了。为了契合当下的编程语境,下文中,如不特殊说明,函数、子程序、function、subroutine等术语将在一定程度上混合、模糊地使用。


今天的程序员可能难以想象一门编程语言竟然不支持函数,然而,这确确实实就是历史上真实发生过的事情。且不说最早高级语言的SHORT CODE不支持程序员自定义函数,就连第一位图灵奖得主Alan Perlis设计的早期语言Internal Translator、划时代的成熟语言Fortran的第一个版本,也全都不支持自定义函数。一言以蔽之,对函数的支持并不是与生俱来,而是计算机科学先驱们艰辛探索的结果。毫不夸张地说,作为最为强大的编程技术之一,函数的历史就是编程语言的(早期)历史、就是计算机本身的(早期)历史。

下意识的函数

在计算机发轫之初,编程这件事并不像今天一样,有高级、汇编、机器语言这些丰富的层次。在计算机圈子内部,数学家、物理学家、电气工程师之间的界限有些模糊,所有人一起参与计算机的建造和改进,同时也对弹道、核反应等计算进行编程和调试。在这个意义上,大家都既是系统程序员,又是应用程序员,工作主要在机器语言甚至电路连接层面展开。

不难想象,这个时候的程序都具有明显的指令式风格(imperative programming),而且常常操纵地址和指针。由于具体“代码”和体系结构、物理实现还高度相关,我们很难套用今天有PLT加持的各种语义去解释当年的编程范式。但即便在如此原始的阶段,函数的影子也已经若隐若现。

一方面,抽象地看,(尤其是组合)电路本身其实就是一个函数。比如加法器、乘法器,不就是加法函数、乘法函数吗?当然,电路并不会像Haskell里的纯函数一样将某个值“返回”,反而还常常在计算的同时对整个系统(比如输出端的电压)造成改变。不过,早期程序员对这一点也心知肚明,所以并没有冒昧借用数学中现成的概念、把这种功能命名为function,而是喜欢称之为subroutine。

另一方面,即便抛开加减法这种硬件提供的内置功能不谈,程序员们也很早就意识到了过程抽象的重要性。著名传记作家Walter Isaacson认为传说中的第一位程序员Ada Lovelace就已经使用了subroutine,不过似乎不太可信,因为Ada传世的程序的“程序”中其实看不到函数的影子。

明确历史可考的subroutine,大概可以追溯到Grace Hopper等人1944年在Mark I上的程序。从Hopper的描述来看,他们的使用方式还比较初级,最开始全靠手工“复制粘贴”,后来通过改一些(可能是地址之类的?)数字,算是找到了通用一点的办法。不过Hopper自己也说了,他们那个时候压根没有subroutine这样的名词,大家觉得自己只不过写了一些代码、互相借用而已。

调用函数

第一个真正的突破来自1949年的英国。在日后图灵奖得主Wilkes的带领下,剑桥师生新建了一台叫做EDSAC的计算机。这台机器的许多特性都值得大书特书,比如最早的汇编语言最早的编程教材、最早的电子游戏等等。在函数相关的技术上,EDSAC则是首次明确提出了subroutine的概念,允许(主)程序执行过程中进行函数调用,函数执行完之后再通过返回地址继续之前的程序。

需要指出的是,用今天的眼光来看,EDSAC所支持的主要是函数调用,而不是函数定义。

“啥?等一下……定义和调用还能分开?区区函数这么个破玩意,有那么复杂吗?”

是的,对函数调用和函数定义的支持,历史上确实是分开进行的。事实上,许多我们现在看来是理所当然的事情,都是早期开拓者们经历了无数的尝试、失败才换来的。

回到70年前的剑桥,EDSAC程序中调用的,其实都是今天所谓的(标准)库函数。尽管标准库有时会要求程序员提供额外的辅助函数——例如库函数F1是用inverse interpolation法求解方程f(x)=0的根,然后把求解结果放在hD位置,那你肯定要提供一个函数f(x)EDSAC才能帮你求解嘛——但作为语言和机器的设计者,Wilkes等人对程序员的预期,其实就是老老实实使用标准库。哪怕程序员自己提供的辅助函数,也是服务于标准库的,一般不需要程序员编程时在主程序中显式调用。

简而言之,EDSAC辅助函数的目的并不是用结构化的思维方式来简化编程、管理复杂性。也正是从这个角度出发,EDSAC的在函数方面的贡献主要是调用。但即便如此,它的划时代意义也不容否认。如果说加法器是硬件实现的函数,那么EDSAC则第一次旗帜鲜明地提出了由软件实现的(库)函数。自EDSAC以后,基本上所有的语言都提供了对标准库和函数调用的支持。

自定义函数

函数调用捋个差不多了,那么问题来了,函数定义又是什么时候进入编程语言的呢?

从时间上来说,最早的似乎是Böhm在1950年设计的一门语言。事实上,彼时博士还没毕业的这位Böhm老兄不仅设计了(在当时唯一自称是universal的)这门高级语言,而且干脆是从理论化的机器模型到语言的编译器,全都设计了。可惜,貌似他也只是停留在了设计而已,并没有真的建造这样一台机器。1976年,Knuth老爹用Böhm构想的这门语言实现了一个TPK算法,从中可以清晰地看到,程序员已经可以调用自己定义的函数来计算平方根了。

Böhm终究还是纸上谈兵,在真正被实现了的语言当中,对自定义子程序的最早支持可能来自一位被历史忽视了的英国计算机科学家Alick E. Glennie。1952年,Glennie为Manchester Mark I计算机设计了一个叫做Autocode的系统。Autocode大概只能勉强能算是一门高级语言,因为Glennie的编译器虽然可以把Autocode代码转成Manchester Mark I机器指令,但Autocode语言本身其实相当晦涩,以至于Backus认为压根不能把这门语言称为“代数的”。不过,这并不妨碍它对函数的支持。Glennie在剑桥的讲义当中给出了一个简单的例子,明确地调用了自己定义的子程序。

Fortran——新的时代

应该说,前面介绍的所有语言,尽管都或多或少地从某个侧面支持了函数,但受限于当时的物理、数学、计算机科学发展阶段的限制,依然非常初级,除了EDSAC之外影响力也不太大。参数、返回值、类型、过程与函数的差别等等,更是没怎么进入讨论范围。然而,1956年Fortran I横空出世,(几乎)将这一切都改变了。

Fortran可能是第一个比较接近现代编程语言的高级语言,而且时至今日依然广泛应用于数值计算领域。由于采用了直观的英语、数学表达式来编程,即便不是数学家、电子工程师,一样可以阅读手册进行学习。不过,Fortran对后世最大的贡献,也许是揭开了上层语言和底层机器相分离的大幕。从此以后,编程语言设计者们越来越多地采用BNF或类似的方式来记录语法,语义学也蓬勃地发展了起来,单独研究一门编程语言慢慢成为了可能。

在函数方面,Fortran I实现了1954 年的Fortran 0中的构想,允许用户(即程序员)以非常简单优雅地方式定义函数。函数可以有多个参数,返回值则会替换掉原来的函数调用,在表达式中参与运算。Fortran II中开始区分了function和subroutine,究竟本身是不是一个好的设计暂且不说,对今天的函数教学反倒有一些启发。在Fortran之后,ALGOL 60正式引入了现代意义的类型概念,LISP中函数更是与生俱来的一等公民,各种新的编程语言如雨后春笋一般迅速地发展起来了……

尾声

函数的历史回顾到这里,其实已经差不多可以结束了。无论是调用还是定义,不管理论模型还是物理实现,函数这一最强大的抽象工具,到Fortran都已初现端倪。不过可惜的是,由于史料的缺乏,我们很难了解Wheeler、Böhm、Glennie这些人是如何萌生出子程序的想法的,因而对建构主义的函数教学帮助并不是特别大。更何况,现代程序员接触的都是高级语言,几乎不需要关心体系结构的细节,连指针都很少直接操作了。非要让学生从底层电路到高级语言完整地重走一遍,收获自然会非常大,但对于职业教育的学习来说并不实际。所以,我的这番梳理并没有实现最初的目标,多少有些遗憾。

不过,阅读计算机、早期编程语言的发展史使我意识到,几乎所有我们今天觉得稀松平常的技术,都凝结了前人艰苦卓绝的努力。事实上,甚至都不是前人,像Knuth这样计算机科学家今天依然健在。克罗齐说,“一切历史都是当代史”,但对于沧海桑田的计算机科学,这句话也许可以稍微改改、反过来说:一切当代立刻就会变成历史。今天,函数式编程者自视甚高、深度学习似乎风头正劲,但50年后的人看待这些技术,可能就跟我们现在看待函数一样,不过雕虫小技而已。意识到自己正身处历史的洪流之中时,我才愈发感受到自己的渺小,愈发认同Dijkstra的那番话

当我们能够真诚地认识到编程工作之复杂,坚守谦逊优雅的程序设计语言,发自内心地承认人类思维的局限性,成为一名谦卑的程序员的时候,我们才能真正做好编程这件事。

comments powered by Disqus