编程语言学习在编程教育中所扮演的角色

Daniel P.Friedman关于程序语言学习的一篇文章《A Role of the Study of Programming Languages int the Education of a Programmer:编程语言学习在编程教育中所扮演的角色》。这篇文章提出的观点对我个人感触颇深,因此决定将它翻译出来。另外,虽然文中的程序例子很少,但是具备对scheme的初步了解,会有助于理解这篇文章。另外,如果对比原文,你会发现很多地方感觉少了“句子”,这是因为更多的时候我进行了意译,做了很多省略。译文中的所有程序均可以在DrRacket(需要设置语言为R5RS)下运行。


对于程序员教育,编程语言学习扮演着两种角色。首先,学习编程语言应该要教会你怎么避免一些错误的想法。接下来我会通过动态作用域的历史类型系统的讨论以及在正确实现尾递归过程中的可能错误几方面来说明这点。再次,学习编程语言应该教会你如何汲取一些好的想法从而形成独立认识。我会通过解决尾递归的一些问题来说明这点。这些问题需要一些形式体系,但大部分都是直观的,只需要学习者具备开放性思维即可。当然,也许编程语言学习对于程序员教育还有其他角色意义,但是,上面的两点在我所教的毕业生中体现的最为明显和清晰。

John Rossie描述了编程专家在一个不知编程语言专家为何物的世界中的工作情形:

在一个软件项目中,当需要数据库时,数据库专家被召集;当需要网络解决方案时,网络专家被召集;当需要基于操作系统的特殊需求时,操作系统专家被召集。但是在每个软件项目中,程序语言都是具有某些特殊需求的。我所见过的每个成功的软件项目中,都会召集一个程序语言专家用于解决一些特殊需求。

大多数的程序员、架构师和管理者都不需要对编程语言有创造性思维。对于他们而言,只需要选择,而不需要构建编程语言。在非语言专业人士可能无法解决的一些代价高昂的问题,语言专家却可能会发现简单的解决之道。在非专业人士眼中的“策略”和“标准”,语言专家却看到检测性和强制性。对于语言专家而言,那些会威胁到整个项目的问题才是我们的专有领域。xxxx。通过将需要的一些假定构建到编程语言及其工具中,我们可以将精力聚焦于软件架构,进而减少软件系统的熵值和错误。

我曾经作为软件分析师与其他两名语言专家一起共事。我们团队的专业性意见不止一次地突显了其价值所在。 我们的系统分析经常会揭示出一些本可以通过程序的形式化操作完美解决的问题。由于工程管理者对这种解决方式非常陌生,因此很多时候我们不得不避免这种做法。几个有经验的自作聪明的项目管理者会声称了解决停机问题,以此来指责我们。他们是不可理喻的,并没有受到良好的教育。在他们长久以来的编程经历中并不将程序看做数据,而我们则正好相反。当我们向他们解释我们的方法本质上就是编译器前端技术的变种时,他们表现了些许兴趣,但很明显,他们充满了怀疑。之后通过原型实现,我们证明了我们的想法,而且我们花费了很少的时间,因为对于一个受到良好程序语言教育的人来说,这些问题仅仅是编程语言课程涉及问题中的一些问题的小变种。

“程序即是数据”是非常简单明了的观念。这点在软件移植项目中再明显不过了,但是我们却见到一些项目的管理者对这点视而不见。幸运的是,我们看到了这点并有能力提供足够专业的意见,但他们却从没主动寻求我们的帮助。

我希望每个程序员和架构师都可以如我们一样,看到此类解决方案,但是现实并非如此。这就好比希望全世界的色盲者可以如正常人一样分辨颜色。但是我深信我们可以期望每个程序员至少可以知晓“色彩的存在”,少数人也许甚至可以看清“色彩”。良好的编程语言教育课程是非常必要的。让他们知道各种可能性以及学会一定的创造性思维就够了。那么,当他们发现某个影响整个系统的问题,仅仅适合语言方式去解决时,他们也许会意识到寻求一位语言专家的帮助。这种想法已经保全了很多软件工程项目。

Jon说程序皆是数据,我同意这点,但我同时认为,所有的数据也是程序。我们编写的每个程序都是某种形式的解释器。这一论断很简洁,硬件就是一个解释器。但它的真实意义是什么呢?每个程序都处理数据;数据处理器就是个解释器。甚至一个编译器也是个解释器。它处理的输入数据是一个程序,输出是另外一个程序。类型检查器同样是一种解释器。它解释程序并创建类型。一段以Monadic或者CPS形式生成代码的程序也是一个解释器。如果我写了一个输入为“5”的程序,如果我期望输入值是数值,那么它就应该被解释为数值5。但是,如果输入是“V”呢?它可以被理解为字符,也可以被理解为罗马数字5。我们无法确定它的真实意义。而如果我们写的函数输入“XIV”,输出“XV”,你会认为这是一个后继函数么?若干你并不了解罗马数字,由于输出时更加短了,难道你不会猜测该函数是个前驱函数?因此,数据必须被解释才能有实际的意义。大多数的程序员都会几种编程语言,部分人会纠结于所钟爱的语言很难处理一些场景。编程语言的学习研究在某种程度上会缓解这一问题。现如今,持续地学习新语言是每个程序员都应该具备的能力。有一些特定的语言设计问题,这会一定程度上降低学习一门新编程语言的难度,比如:语言中如何实现各类变量的识别。我们的一个目标就是尽量多的学习到这类特定的语言设计问题,这样,当需要使用新的编程语言时,我们可以容易的区分出该语言的各种本质特性,并可以合理将语言特性拼凑使用在程序中。

我想谈点关于我个人的一些背景和经历。在1964年的春天,我开始接触到计算机科学,作为一个在校生,我当时的目标就是每学期学习一门新的编程语言。以今天的标准看来,那似乎有点乏味,但是你得明白,当时只有很少几种语言,并且仅有语言手册可看。没有多余的说明文字,因此,如果不能探究到该门语言最初的设计目的的话,是很难读懂语言的说明手册的。我常常都必须阅读一些发表的论文,并努力的理解论文中的抽闲的名词概念,然后去努力地联系说明手册。我必须说这非常不容易,部分原因是当时那些语言并没有良好的设计。(后面我们会看到,当今的语言仍然有待改进)当我进入研究生学院后,我略微提高了个人目标。我将个人目标重新设定为每个学期实现一门语言。之后我进一步提高为每周实现一门语言。

这意味着相比以前我拥有了更多更好的工具。当前指称语义(Denotational Semantics)正变得流行,随后我们会看到指称语义简单地通过忽略非本质的繁杂细节,从而帮助我们在更高的层次理解编程语言的本质。

指称语义用以研究编程语言,而非实现编程语言。当时我们并没有意识到如何去弥补语义指称和LISP语言之间的差距,而那时LISP是语义指称的最好替代者。两者均有λ算子。但是LISP中的λ算子设计的并不完备,因为它并没有完全避免自由变量。1975年的十二月,Mitchell Wand从他的母校MIT带回了一包论文,拿出其中的一张对我说“Dan,我觉得以会喜欢这个的”。

我很少听闻过如此不充分的描述。那篇论文就是Scheme的最初的版本,仅仅一晚上,这篇论文就彻底改变了我的研究生涯,Scheme完备的实现了λ算子。那种构建奇怪变量(动态作用域的直接结果)的古怪做法被完全避免了。这种保证正确性变换的能力在语义指称中出现过,并在Scheme(LISP的变种)中使用它可以解决我的大多数问题。我正需要这种工具,它就出现了!太幸运了!

我谈得有点脱离主题了。就在那时我发现了编程语言迷人之处,因此从1964年直到现在,我都一直在研究这一领域;但也许你们还没有足够的理由和兴趣去做同样的事情。

Anurag Mendhekar表达了他在我的编程语言课程(311)所学的东西是如何帮助他的初创公司成功的。(这封信挺长的): > 我喜欢所有的计算机科学家,并坚信抽象在软件开发中的重要性。但讽刺的是,很多时候,我用来编程的工具,比如编程语言,提供的功能太简陋了,以至于并不能有效的构建抽象,因而导致抽象的强大能力并不能被达成。为了优化程序ended up breaking your abstractions因此你没有必要复杂化程序。311课程式的编程训练让我认识到了一种完全不同的新的编程方式—根据你的需要构建抽象,我至今仍在使用这一编程方式。这一风格和将软件架构硬生生的构建到一些并不适合的固化抽象集合中是相反的,最终这一编程风格可以很好的构建复杂的软件系统,而这一点正是我希望以我的专业经验去论证的。 > > 基于这一软件开发的关键观点,我为Online Anywhere(现在是Yahoo!的一部分)构建了软件平台,这一服务可以实现通过一些非PC设备,如手机、PDA、电视上,发布网络内容。 > > 很快我就构建了一些必需的抽象。然后我使用Java及其元语言编程工具实现了这些抽象。这些工作成果帮助我很快的构建了将HTML内容转换到非PC设备的转换器。这些抽象在技术上对Java进行了扩展,我们称之为Blue。 > > 当我们构建这种转换器积累更多的经验后,我们意识到,一些被频繁使用的转换器中的抽象更好使用。这引导我们开发了Teal语言,在Yahoo!公司中,该语言直到今天仍然被用于支持大量的非PC网络通信。 > > 在构建这一软件平台的过程中,另一个关键的挑战是将大量的转换器组合起来以处理各种不同设备。你猜我们使用了什么方案!我们使用另外一种称为Green的语言解决了该问题。 > > 通过上面的方案,最终我们构建了一个高维护性、搞效率和高扩展性的系统,该系统承担了整个Yahoo!集团的非PC网络通信。我把这一优秀架构归功于当初我在311课程中所学到的编程语言的构建和实现原理。

很明显,并不是所有的编程语言都适合这种编程风格的。311课程中我学习了Scheme,之后是Common Lisp,这两种语言都非常适合这种编程风格。大量的编程语言(如C和Java)都有一些特性支持这种编程风格,但是相比Schem和Common Lisp,需要做更多的工作。

基于编程语言抽象扩展语言本身的优点在于,可以避免为了效率而违背抽象设计,这样你做的一切都是在更加聪明的实现抽象。在某些方面而言,这中编程风格可能是很困难的,尤其当你没有学习过311课程时,但是,该风格会形成更加统一的方式以优化性能和提高代码的可维护性。(因为这时,优化是模块化的)

Anurag关于分离做什么和怎么做的视图理论是很重要的。当人们抽象性思考如何解决一个问题,为什么要因为细节而徒增负担呢?这里的细节可以是语言设计的实现或者语言本身的实现。细节再想法圆形成型之后才应该被考虑。后面我们会反复看到Jonathan Sobel关于Anurag视图的变种。

现在让我们回归主题。首先,我们有必要自问“研究课题对于我们到底指什么?”。“研究”意味着我们使用自身的智力去获取某个领域的知识。那么,如何获取这种知识呢?人们不应该去通过死记硬背一些事实和案例,而应该通过建立一些基础概念来吸收知识。同时,在我看来,应该通过将正在学习的实际的事物模型化以获取知识。这也就是为什么长期以来我一直教授编程语言(课程)的原因。

举例来说,“一门语言的参数为值传递”可以简单的描述伟“call-by-value”。因为我很容易联想到λ算子中的call-by-value,而λ算子中的call-by-value就是我可以理解的模型,我并不需要多余的解释,我仅仅需要知道这门语言中都有哪些部件是值。一旦语言中值的集合发生变化,我对语言的认识也会相应变化。ML和C语言均是call-by-value型语言,但是他们的值是非常不一样的。

另一方面,我们也有必要自问“研究编程语言对我们到底指什么?”。那是指对语言中保留了十年以上的概念进行半形式化分析。这其中不仅仅是语言中的概念,也包含这些概念背后的法则。

我并不是指用大量的篇幅教授各种语言的特性并要求学生使用这些语言练习写程序来理解语言的语法和特性。我想要学生去实现每一种学习到的语言,即使这种实现很简陋;同时,我刻意避免他们过于关注语法。我并不是说语法不重要,而是就我个人的观点来看,语法对于语言研究并不是一个障碍。

举例来说,语义作用域的概念自从Algol60以来一直出现在各类编程语言中,但事实上,逻辑学家们早就使用这一概念了。逻辑学量词∀和∃依赖于语义作用域。事实上,逻辑学家很难使λ数学置换正确,因为他们并没有用到语义作用域的微妙的地方。

下面是一些原生关系数据库系统的操作,这些关系就是一组元组。

(∀ x E Tuple*) == (andmap (λ (x) E) Tuple*)   注:将E(x)结果输入到每个
和
(∃ x E Tuple*)) == (ormap λ (x) E) Tuple*)

这里我们无意去理解数据库系统实现的聪明之处,而是完全理解这一抽象。可以看看λ算子的强大之处;它可以简单的捕捉到∀和∃量词的绑定项。 现在让我们考虑另外一种语义作用域机制:动态作用域。当你最初学习作用域时,你必须保证掌握动态作用域。这是为什么呢?因为两点:第一,你很可能会和许多语言设计者一样发现动态作用域,同时会后悔使用它。第二,你需要搞明白为什么动态作用域是个错误。尽管如此,在你学习它之前,需要明白变量的命名是由你决定的。在λ算子的术语中, 是支持α置换的。例如:

(λ (x) x) = (λ (y) y) 译注:此处是指变量名称是可以置换的。
当然,这不代表在任何情况下都可以这样做,但你可以使用任何没有在表达式中出现过的命名。例如:
(λ (y) (λ (x) (y x)))
=
(λ (z) (λ (x) (z x)))
我们有理由去相信,编程语言学习必须在一定程度上包含其命名符号。任何编程人员潜意识中都知晓α置换规则,但是至关重要的是规则本身的解释。观察下面的α规则在map是如何作用的。
(define map-t   ;由于原文的map与scheme原生的map函数冲突,因此,此处改为map-t
  (lamba (f ls) ;原文此处使用的是λ,我将其替换为了scheme的lambda定义
     (if (null? ls) 
         '()
         (cons (f (car ls)) (map f (cdr ls))))))

很明显,这是一段正确的程序。我们假定函数f具备形式f:α -> β,代表α的ls具备ls = list,这样,我们容易看出上述程序的输出结果是β类型序列。下面是函数map-t的具体应用:

(let ((ls '(1 2 3 4))) (map-t (lambda (x) (cons x ls)) ls))

输出:((1 1 2 3 4) (2 1 2 3 4) (3 1 2 3 4) (4 1 2 3 4))

这与我们的预计是一样的,因为scheme语言均有词法作用域。那么如果此处let和lambda是动态作用域,会是什么输出结果呢?很明显,输出的表的第一个元素仍然是相同的:((1 1 2 3 4)...。但是,在第二次递归的时候,ls发生了变化(译注:具体来说,(1 2 3 4) -> (2 3 4)),因此,动态作用域影响了map-t函数定义内部的ls的值。非常震惊吧!语言设计者们应该让语言使用者承受这种痛苦的想法么?

动态作用域的map-t输出:((1 1 2 3 4) (2 2 3 4) (3 3 4) (4 4))

译注:

在词法作用域下,调用map-t时,其中的(lambda (x) (cons x ls))中的ls永远是指向初始的输入值(1 2 3 4)

在动态作用域下,调用map-t时,其中的(lambda (x) (cons x ls))中的ls是每次递归调用中变化的。 看看下面的等价定义。第一个是动态作用域绑定,第二个是静态作用域(即词法作用域,lexical scope)绑定。

E[(λ (x) M)]env = (λ (arg) (λ (env) E[M]env[x <- arg]))
                = (λ (arg) (λ (enw) E[M]env[x <- arg]))

我们明显会有一些疑惑。两种定义只是差了一个字符而已,即envenw。之前我已经说过,静态作用域时优于动态作用域的。思考下面的问题。这段Scheme程序有什么问题么?

(if (= n 0) 
  (+ n 5)
  (not (= (length ls) 4)))

没有。我们应该满足这种状况么?那么下面的代码有问题么?

((if (= n 0) 
  5 
  (lambda (x) (+ x 7))) 
6)

没有。我们应该满足这种壮况么?

两种情况我们都不满意。为什么呢?第一个例子中,条件语句的返回值可能是数值或者布尔值;第二个例子中,添加语句的返回值可能是数值或者函数。xxxx。在没有类型的语言中,比如Scheme,这点绝对有可能。但在其他语言,如ML,这是不可能的。但是,ML中有更多的灵活性。你可以设计一种数据类型可以同时表示数值、函数不同类型的值(或对象),虽然这样的代码可能被重写(如解释器),但不管怎样,ML提供这种返回不同类型值的可能性。因此,为了更好的理解编程语言,我们应该在一定程度上学习类型。ML和Haskell语言允许指定类型和推断类型。但是Java却只能支持指定类型。这点是两种语言的本质区别。

译注:

C#中也是同时支持指定类型和推断类型。Javascript和Scheme只支持推断类型。而C/C++和Java一样只支持指定类型。

我们并不想为那些好心的语言设计者(或实现者)引入到语言中的缺陷费心。相应(译注:此处指存在语言设计缺陷)的例子有如下几个:TEX动态作用域宏指令;LISP动态作用域和影子绑定;Java缺少对尾递归优化的支持。虽然这些缺陷很可能有着善意的初衷,但是错了就是错了。我们已经讨论了动态作用域,而关于宏指令的问题我甚至可以写本书说明,因此接下来我们着重讨论下Java的缺陷(译注:指上文提到的不支持尾递归优化)。也许有人会觉得这不是一个缺陷,但我建议这些人应该注意到,微软已经向语言研究社区明确表明,其基于.NET平台的IL中间语言会很好的处理尾递归。

Java中有很多优良的特性,我不想你们误认为我只知批评Java。Java在全世界范围内被广泛使用,因此,这至少表明它是受欢迎的。EOPL第二版全部8章节中的2章在讲述面向对象的概念,因此,我们觉得有必要深入理解下面向对象。但是Java中有些地方是与面向对象相违背的。Guy Steele是1975年发表的”Java语言标准”的两位作者之一,我曾经向他和另外一位至今仍在Sun公司工作的联合作者提出过这一缺陷(即不支持尾递归),他后来也联系过我,并承诺在1997年解决这一缺陷。但是现在已经是2001年了,仍然不见这一问题在未来的Java版本中会被解决。

但是,如果你研究过编程语言,那么你会发现,通过一些小的xxx变换,这一问题仍有可能被避免。意识到这点,可以让你更好的使用Java的优点,但规避其该问题。

绝大多数的Java(和C)实现都没有正确处理尾递归。这不仅仅是一个递归调用的问题,也涉及到方法调用,而方法调用时OOP语言中最主要的操作。在Java中,并不鼓励递归程序,因为这会使方法表过于膨胀。当你细想程序(如操作系统)被设计为不支持中断时,你会发现这不再是个效率问题,而是个正确性问题了。但是,借助我今天所展示的工具,你可以在Java中自由地写递归程序了。

现在我们暂且假定,我写的Scheme程序代码可以很容易地转换为类似Java的程序代码。事实上,这确实可以做到的。我们已经在EOPL第五章和“A Little Java, A Few Patterns”一书中证明论述过实现方式了。

For much of the talk, 你会看到这些保留正确性的变换,我会尽量努力去说清楚其机制,而且我也已经将它们公开,因此,你可以在业余时间去阅读。我想让你在这次讨论中获取的最重要的东西是,这些变换是非常简单和富有逻辑性的,因此,你可以在恰当的时机下使用他们,同时使用它们也可以解决目前绝大多数Java和C实现中都存在的尾递归问题。

考虑下面的sum程序。

(define sum0 
  (lambda (n) 
    (if (= n 0) 
        0 
        (+ n (sum (- n 1))))))
        
(sum 1000000)

该函数是很简单的,表达的数学形式是:n + (n-1) + ··· + 1。它不是基于尾递归调用。

当然,我们可以使用一个累加器变量实现更实用的尾递归版本。

(define sum1 
  (lambda (n acc) 
    (if (= n 0) 
        acc 
        (sum1 (- n 1) (+ n acc)))))
        
(sum 1000000)

上面的程序非常简单,甚至都没有费心写的意义,因为其计算过程就是一个等差数列,结果可以通过公式n(n+1)/2计算。

如果在Java中编写上面列举的两个例子,我几乎确定不会得到计算结果。为什么?因为上面的例子中,每一次过程(函数)调用都依赖于控制栈,而(译注:由于内存有限)控制栈的深度是有限的。因为Java语言设计者和实现者假定是,(在这种场景下)应该使用循环,而非递归。但是,有些递归程序是没法自然的转换为循环的。上面的两个例子在Java环境,都会抛出异常。

我说“几乎确定”是因为有些Java实现中,上述两个例子可能正常输出结果。可能性很多,不再过多的赘述了,我们继续上面的问题。我们回顾下刚刚的例子,我们写出了不能正常工作的Java程序,现在我们的目标是通过必要的变换,可以让它们正常运行。

我会向你们逐步地展示如何在Java解决该问题。第一个例子不是尾递归的,而第二个例子是。我们可以将例子二中的尾递归形式重写为寄存器(全局变量)形式(译注:作者这里是指,将例子中通过函数参数传递的中间变量acc,通过全局变量进行共享)。如下(原文中包含了伪代码,不可直接运行,下面进行了必要的修正):

(define n 1000000)
(define acc 0)
(define sum2 
  (lambda () 
    (if (= n 0) 
        acc
        ())))

(sum2)

如果我们在Java中按上面的形式编写运行,仍然会抛出异常。但是,我们离我们的目标更近了一步。上面我们通过全局变量(寄存器变量)消除了函数调用中的参数,并在调用前,设置全局变量,接下来,我们将要使用goto代替函数调用。

现在,我们对上面的sum3做些许改变,将其变换为suspended-goto形式(译注:该形式为中间形式,并不能实际运行出结果)。如下:

(define n 1000000)
(define acc 0)
(define sum3 
  (lambda () 
    (if (= n 0) 
        acc
        (begin (set! acc (+ n acc)) (set! n (- n 1)) (lambda () (sum3))))))

(lambda () (sum3))

此处没有直接使用goto,而是返回函数本身。我们发现(λ () (f)) = f,这是λ算子的η法则的变种。进而我们可以讲上面的例子转换为η-suspended-goto形式:

(define n 1000000)
(define acc 0)
(define sum3 
  (lambda () 
    (if (= n 0) 
        acc
        (begin (set! acc (+ n acc)) (set! n (- n 1)) sum3))))  ;注意,这里的sum3是没有()的,与sum2是有区别的

(sum3)

那么,现在我们需要在返回函数(即sum3)之后访问该函数了,我们使用循环实现这点,循环也并不会导致Java出现控制栈溢出。在循环中,使用false代替之前的acc来强制退出循环。累加器在计算过程的结束时被间接引用。

(define n 1000000)
(define acc 0)
(define sum4
  (lambda () 
    (if (= n 0) 
        #f
        (begin (set! acc (+ n acc)) (set! n (- n 1)) sum4))))
        
(define run-sum4 
  (lambda () 
    (do () ((not (procedure? (sum4))) acc))))
    
(run-sum4)

这里我们引入了称其为”Action”的寄存器,它可以避免对return语句的依赖。我们可以简单的在每个函数返回点设置action。通过将计算的结果值设置在action寄存器中,既避免了通过函数参数传递改值(参看sum1函数),也避免了通过return语言返回该值(参看sum2函数),进而得到了trampoline form(译注:可直译为蹦床形式),其通用的形式(<-可以理解set!{}可以理解为begin)为如下:

(define action)
(define sum 
  (lambda () 
    (if (= n 0) 
      (<- action false)
      {(<- acc (+ n acc))
       (<- n (- n 1))
       (<- action sum)
      })))
      
(define run 
  (lambda () 
    {(while action (action)) acc}))

基于如上形式,在Java中,我们可以通过创建类(包含sum方法)实例来模型化action实现。通过一些简单的方法也可以讲action赋值为fasle的过程进行转换。

现在我们的程序就基本上不再依赖于底层的运行时架构了。我们可以确保程序不会抛出异常。

现在我们正确实现(在Java)了尾递归,同时我们也不必再忍受上面提到的问题了。但是,我们不应该只生活在语言设计者的世界中(译注:指不应该被语言所限制)。我们可以使用那些已经完美解决此类问题的编程语言。我们不该去承受设计者的设计失误。对于大多数程序而言,将其重写为尾递归形式(tail form)并不是很明显的,但是,这也关系不大,下面我会想你展示如何以通用的方式实现这点。

上面的两种版本的sum(译注:指conventional form和tail form)会产生相同的结果。区别是,在传统形式中被累加的前两个数是0和1;在尾递归形式中被累加的前两个数是n和0。很明显两种形式并不相同,那么为什么我们可以使用尾递归形式呢?事实上我们利用了加法的加数序列的可交换性。并不是每一个问题都符合这种分析。事实上,绝大部分都不符合这个分析。

因此,我们需要一种通用的方式(实现尾递归形式变换)。更进一步地讲,我们需要一种并不依赖编程语言特性的(尾递归变换)方法,我们的例子中是指Java和C。

EOPL第七章中,通过努力思考和遵循一些必要的指导,我们展示如何将第三章中的解释器变换为尾递归形式。同时,我们也展示了将解释器变换为register form。这样,任何的尾递归形式的程序都可以被该解释器变换为迭代形式。但是,如果成为一个有用的程序员工具,那么我们希望它(解释器)可以将任意程序转换为另一种编程语言。事实上,这种算法早在1975年就出现了,它被Gordon Plotkin在论文《Call-by-value, call-by-name, and the lambda calculus》发表。

该论文中的算法存在一个问题:使用其算法会产生非常糟糕的代码。这也导致了一些新的论文发表了,这些论文论述了如何移除被称为“administrative redexes”的问题。在EOPL的早期版本中,我提出了另外一种方式,这种方式更多的考虑了变换过程的本质,而较少涉及其数学含义,由此也转换除了可读性更好的代码。但是,我们发现,该算法太复杂了,以至于绝大多数的读者都略过了该章节。这种情况必须在(EOPL的)下一版中修正。理解如何处理尾递归形式的程序是非常基础的。

但是,我的学生Matthias Felleisen与现在已经是我同事的他的学生Amr Sabry共同发现了一种更好的方式来描述我们的算法。当前在EOPL后期版本中,已经使用了Amr和Matthias的CPS算法。

现在,我们不借助加法的可交换性来实现preregister-tail form。基于preregister-tail form,我们可以简单地转换为trampoline form

基于新算法的tail form代码是CPS形式的。这种算法形式很容易理解学习,但是你也可以使用EOPL中给出的算法。

我们回顾下之前的代码:

(define sum 
  (lambda (n) 
    (if (= n 0) 
        0
        (+ n (sum (- n 1))))))

我们要做的第一件事,就是给每一个λ表达式中增加一个额外的参数,该参数的意义是下一步要做的事。在我们的例子中,只有一个λ表达式,所以,我们给sum函数增加一个cont参数。我们再外部定义一个id函数,并在sum内部使用它。

(define id (lambda (acc) acc)) ;注意此处后一个acc不需要使用(),否则会溢出
(define cps-sum-0 
  (lambda (n cont) 
    (cont
       (if (= n 0) 
           0
           (+ n (cps-sum-0 (- n 1) id))))))
(cps-sum-0 1000000 id)

原程序中的所有lambda表达式都通过CPS处理了。但是同时,我们引入了一个新的λ表达式id。我们也需要id么?不需要,因为它仅仅是一个continuations的表述。

更进一步地,我们可以讲cps-sum-0变换为如下形式:

(define id (lambda (acc) acc)) ;注意此处后一个acc不需要使用(),否则会溢出
(define cps-sum-1 
  (lambda (n cont) 
    (if (= n 0) 
       (cont 0)
       (cont (+ n (cps-sum-0 (- n 1) id))))))
(cps-sum-1 1000000 id)

接下来我们处理cps-sum-0 (- n 1)

(define id (lambda (acc) acc)) ;注意此处后一个acc不需要使用(),否则会溢出
(define cps-sum-2 
  (lambda (n cont) 
    (if (= n 0) 
       (cont 0)
       (cps-sum-2 (- n 1) 
                  (lambda (acc) 
                    (cont (+ n acc)))))))
(cps-sum-2 1000000 id)

我们做的这些变换都是遵循一定的步骤的。通过创建一个continuation来表示接下来要做的事,我们将程序转换为了尾递归形式。在我们例子中,接下来要做的事是指将n累加到累加器(acc)上并调用continuation

为了将程序转换为register form,我们必须将continuation中使用的自由变量都外部化。这个变换有点巧妙。在我们的例子中,带有自由变量的continuation是:

(lambda (acc) 
  (cont (+ n acc)))

其中的ncont是自由变量,所以,我们将整个表达式替换为:

(let ((n n) (cont cont)) 
  (lambda (acc) 
    (cont (+ n acc))))

如此,我们就得到了pre-register form形式:

(define id (lambda (acc) acc)) ;注意此处后一个acc不需要使用(),否则会溢出
(define cps-sum-3 
  (lambda (n cont) 
    (if (= n 0) 
       (cont 0)
       (cps-sum-3 (- n 1) 
                  (let ((n n) (cont cont)) 
                    (lambda (acc) 
                      (cont (+ n acc))))))))
(cps-sum-3 1000000 id)

基于上面的形式,我们就比较容易得出trampoline form了。

某些语言中也许并不支持如下形式的高阶函数:

(lambda (acc) acc)
(lambda (acc) (cont (+ n acc)))

这种情况下,我们仍然可以使用CPS进行变换,但是需要对continuation进行些许变化。当你使用CPS时,那么你就知道其中的continuations应该在何处调用。我们用(apply-cont cont s)替换掉所有的(cont s)

(define id (lambda (acc) acc)) ;注意此处后一个acc不需要使用(),否则会溢出
(define apply-cont-0 (lambda (cont acc) (cont acc))) 
(define cps-sum-4 
  (lambda (n cont) 
    (if (= n 0) 
       (apply-cont cont 0)
       (cps-sum-4 (- n 1) 
                  (let ((n n) (cont cont)) 
                    (lambda (acc) (apply-cont-0 cont (+ n acc))))))))
(cps-sum-4 1000000 id)

我们接着用数据类型结构替代所有的λ-continuations。这些数据类型中包含了λ表达式中的自由变量。在EOPL中,我们推荐使用ML构造这些数据类型,但在这次演讲中,我们使用空表和“cons”,因为例子中只有两个continuations,一个不包含自由变量,另一个包含两个自由变量。第一个是个空continuation,第二个continuation表示“将n和参数相加,并应用到之前的continuation上”,如下是reperesentation-independent-preregister-tail form:

(define id '()) ;注意此处后一个acc不需要使用(),否则会溢出
(define apply-cont-1 
  (lambda (cont acc) 
    (if (null? cont)
        acc
        (apply-cont-1 (cdr cont) (+ (car cont) acc))))) 
(define cps-sum-5 
  (lambda (n cont) 
    (if (= n 0) 
       (apply-cont-1 cont 0)
       (cps-sum-5 (- n 1) (cons n cont)))))
(cps-sum-5 1000000 id)

(define id ’()) (define sum (lambda () (if (= n 0) {(<- cont cont) (<- acc 0) (<- action apply-cont)} {(<- cont (cons n cont)) (<- n (- n 1)) (<- action sum)})) (define apply-cont (lambda () (if (null? cont) (<- action false) {(<- acc (+ (car cont) acc)) ;car和cdr是Scheme中表操作符 (<- cont (cdr cont)) (<- action apply-cont)})))

{(<- cont id) (<- n 1000000) (<- action sum) (run)}

我们可以通过使用一个抽象的方法apply-cont来模型化apply-cont派发,该方法可以继承自continuation type关联的抽象类(在[A Little Java, A Few Java][]第一章中有表述)。在这里的例子中,会有两个子类,一个用于代替空continuation(此处指id),另一个用于代替cons表示的continuation。

或者,我们可以回顾下之前用过程(函数)表示continuation的版本。如果这样子做,我们同样可以讲过程(函数)当做action:

(define id 
  (lambda ()
    (<- action false)))
(define sum 
  (lambda () 
    (if (= n 0)
      {(<- acc 0)
       (<- action cont)}
      {(<- cont (let ((n n) (cont cont)) 
                  (lambda () 
                    {(<- acc (+ n acc))
                     (<- action cont)})))
       (<- n (- n 1))
       (<- action sum)}))

综上,我们看到,那些由于语言的设计缺陷而导致的问题,是有可能通过良好的正确性变换解决的。我们解决方式非常依赖于这种变换。可能你们并不能有效的使用上面的方式解决每种语言的问题,但是,你完全可以发挥自己的聪明才智,找到属于自己的解决视角和方案。当(上文中的)实现不能满足需求时,你需要承受其缺点。

下面是1994年Jonathan Sobel的评论,今天看来是非常中肯的。有趣的是,当前仍为学生的Steve在1999年才发现了trampoline form。(下面的引用比之前的两段更长):

在印第安纳研究生院的第一个学期,我就有幸同时学习了算法分析和编程语言课程。算法课程的学期大作业是实现并优化快速乘法算法。快乘算法是递归的分而治之地计算两数相乘的算法,尤其是成百上千位的大数字的相乘。(该算法同样被用于硬件领域,此时数据单位是从数字变为二进制位)

这项作业成绩的高低部分地决定于算法的速度。每个人都毫不迟疑地选择了使用C语言,更有甚者使用汇编。当然,为了使他们高度优化的程序能够运行起来,他们花费了大量时间进行调试。修改,重新编译,测试,如此反复。

当我决定使用Scheme的时候,每个人都及其震惊和不解。在此之前,我才在编程语言课程中接触Scheme两个月,但是我已经被它的简洁性所吸引。更为重要的是,当时我发现了增量式编译的乐趣:修改后并不需要重新编译所有代码。我想节省那些调试编译时间。另一方面,虽然我们使用的Chez Scheme编译器已经非常高效了,但是,在多数情况下仍然比不上C语言的速度,而程序速度却是这门课程中很重要的衡量指标,那么,我为什么选择Scheme呢?

每个*快乘**调用都会产生三个递归调用(当数字足够小时,只是个简单的乘法)。我注意到那三个后续的递归调用的上下文是一样的。在C语言实现的简单版本中,那个上下文需要被保存和恢复三次,并且在每次调用返回之后会被销毁。我思考到:如果我刻意显示得控制程序流程,那么我就可以只创建上下文一次,并保证在第三次递归调用返回之后才销毁它,从而大大提升程序的效率。函数调用的开销非常大!但是我不可能通过C语言实现这一想法。

我在编程语言课程中学习到,是可以控制程序流程的。更进一步地讲,我可以先完成一个比较简单的,更加本地化的程序版本,然后通过一些列的正确性变换,推导出更加复杂和实用的版本。这就是Scheme的优势所在。因为Scheme天然地具有数学属性,因此,它可以很容易地以代数风格被编写。我们几乎可以按部就班地按照一些重写规则,将程序转换为附带其他属性的形式。这点正是我所需要的。

我先是按照算法分析课本中的步骤,非常直接地实现了快排算法。(在这个过程中,我基本上没在调试上花太多的时间。) 然后,我将程序转换为了CPS风格。接着,我将其中的continuations转换为了记录结构而不是Scheme的过程(即函数)。最后,我将所有的过程都变换为了通过注册器(register)传递,而不是通过参数式地调用。眼下,过程调用基本上是简单的goto,调用开销很小。我花了几个小时完成了这些工作。

将最终的Scheme程序转换为C程序是件简单的事。由于C语言中无论如何都需要用到函数调用,因此,我必须使用goto语句(完成Scheme程序到c程序的转换)。在此之前,因为goto语句的副作用,我从未在C中使用过goto。现在,我可以完全安全地使用它了,而这也挺有趣的。令人惊奇地地方在于:我最终生成了一个我从来没有想过可以写出的程序。

当然,你可能会像当时的我一样存有疑问“它的运行速度够快么?”。比较运行速度使我的主要目标。结果是非常肯定的。班上15名同学中,只有一位同学使用汇编写的程序在速度方面比我的更快。而速度第三快的程序足足比我的程序慢了两倍。

现在我知道了更多的变换方式可以被用于当时的Scheme程序,这样我的程序的速度就可以排在第一名了。对我的程序进行的性能调优表明,主要的时间开销在转换为C语言后的mallocfree。通过显示的栈管理,可以把我的程序中的所有的数据分配和控制管理完全转换为基于栈的方式。我可以把那些必需的控制信息完全放入栈中。还有几处(优化的地方是),我可以重复利用已经存在的栈记录,而不是删除一个记录,再重新创建一条并压入栈。上面这些变换同样在我的编程语言课程中有讲到。可惜的是,当时我并没有更好地利用这些变换。

从这次经历中我理解到了结构化、系统化编程方法的重用性。我发现,编程时可以先采用简单而直接的方式解决问题,之后再应用一些结构性变换;同时,我可以依赖那些变换保证程序的语义不变。我还认识到,我应该优先聚焦于问题本身,而非解决方案的效率。效率来自于优秀的解决方案,而不是程序优化。优化仅仅只是一些正确性变换

Jonathan的看法是非常准确的。编程语言的学习研究,可以催生出一些通用工具,这些工具可以帮助你去解决一些非常棘手的问题。他的表述中的“我最终生成了一个我从来没有想过可以写出的程序。”非常中肯。通过学习研究编程语言的通用特性(如上问提到的一些通用变换等),这些之前对比不可能完成的类似的事,你也可以做到。

我想引用Christopher Strachey的一段话,来结束今天的演讲:

我之所以不遗余力地研究学习编程语言,是因为我认为,只有深刻地理解编程语言本身,我们才能真正理解计算机。理解并不指单纯地使用这些语言。很多人只是使用语言,却从未理解语言本身。

那些希望在Scheme中运行之前的代码的人,下面是一段while的定义:

(define-syntax while 
  (syntax-rules ()
    ((while exp stmts ...)
     (let loop ()
        (if exp (begin stmts ... (loop))))))