Some History of Functional Programming Languages

Some History of Functional Programming Languages

这是某个讲座的一份note整理,直接搜标题就能找到原文(20页,不过实质内容没多少)。如果对标题有兴趣可以去找一下,对标题以外的问题有兴趣就不用抱太大的希望去读了,文章主要还是围绕函数式编程语言设计的几个重要节点叙述的,中间穿插着不少八卦和作者自己参与设计的心路历程,可以说是文风比较随意,个人气质浓郁的作品了。读完有点知其然而不知其所以然的意味,相关的历史细节还是得去看满满2页的ref,不过读完差不多也摸清了我之前的一个疑惑:从LISP到SML再到Haskell,函数式编程语言的语法设计到底经历了哪些模式和准则的转变?这篇reading里面我也只挑自己感兴趣觉得有意思的部分讲了。先看下原文的目录:

众所周知,lambda calculus作为最早的函数式编程语言雏形,在现代计算机问世前就有了这样简单而优雅的“编程语言”,借助Church编码,所有的类型(包括现代编程语言中的数值/bool)都被用函数来表示。在sequential machine上实现的lambda calculus使用的是正则序化简(normal order reduction),这种lazy的计算方式可能在今天不太多见(大多数指令式编程语言在传参的时候就会对参数进行化简求值,也就是我们所说的应用序),很容易想到这是计算效率的问题,不过效率问题可以通过normal graph reduction,一种把term转换成DAG的方法去克服。normal graph reduction的具体做法可以自己去看论文,总之它对SK组合子的抽象实现贡献巨大,让递归的表达更加紧凑,以及被应用于后面要讲到的SASL和Miranda

最早的LISP用S表达式(原文用的是S语言,经评论指正和我查阅应该确实是S表达式,而不是我们统计学科的老朋友R语言的哥哥S语言)来表示数据,S表达式由.和括号组成,大概就是这样

((X.Y).Z)         
(ONE.(TWO.(THREE.NIL))) 

后来的LISP系语言也一直沿用着类似这样的形式。M表达式是LISP的理论原型,定义了在S语言的计算,在原来S表达式的基础上增加了函数应用,条件表达式和递归定义函数的能力,使之成为了计算完备(computationally complete)语言,然而,M表达式仍然是一阶的,函数不能像现在很多语言那样作为一等公民来传递使用。另外,LISP也是最早搭载了垃圾回收(garbege collect)的语言。

(M表达式只是作为幽灵短暂的在理论上存在过,McCathy移除了部分限制让它成为了一阶语言,而M语言又可以通过eval/quote再编码成S表达式,实践中LISP程序员都直接以S表达式的形式去写代码了,没人care它……)

最初的LISP并不是基于lambda calculus,而是基于Kleene的一阶递归函数理论,虽然它用lambda表达式来表示函数。LISP也从未成为过纯函数式编程语言,保留了赋值和goto语句这样不优雅的东西,以及非常糟糕的动态作用域(dynamic scope),这来自于非常基础的问题,元编程和高阶编程不同。不过到了今天这些问题也都不复存在了,现在所有版本的LISP都是基于lambda calculus并默认使用词法作用域。

Algol 60虽然不是函数式编程语言,但规则和变量约束与lambda calculus有很大的关系。默认的传参方法是call by name而不是call by value,这就回到刚才那个normal order reduction的问题上了,不过这里用的是另一种巧妙的方en.wikipedia.org/wiki/J,除此之外,Algol 60的函数嵌套,函数作为参数传递,词法作用域的实现需求,环境的stack frame模型,都给了现在的函数式编程语言设计很多启发和借鉴,不详细展开,有空自己去看原文和ref吧。

ISWIM(If you See What I Mean)是一个语言族概念,它们的一些基本元素(如primitives)各不相同,但设计理念和层次一致,被用于不同领域,应用核心是Church without lambda,也就是最早正式提出用

f(x)=expr

来代替

f =  λx. expr

并引入where,let,rec这些语句。offside rule引入了缩进代替begin/end语句。

总之

ISWIM = sugared lambda + assignment + control

这里的assignment和control都是核心之上的imperative layer包裹,control指的是今天的continuation的概念,允许程序自由的跳跃。

ISWIM这个概念相关的paper也最早提出在结构定义中加入代数类型(algebraic type),虽然只有文字叙述,不过类似于今天的either/tuple的想法已经跃然纸上了。以及那篇文章里有关于一个有趣的想法DL的讨论,有兴趣可以找来看一下。

PAL也算是ISWIM思想孕育的产物,是一个用于编程语言学教学的工具,所以专注于数据的完整性和定义语义的准确性,具体的实现层次去看原文,不再赘述,现实意义比较有限。

SASL是在PAL基础上设计的DL,也就是那个作者自己一拍大腿从黑板上的概念开始写的实现,用于编程语言的教学,原文有非常详尽的动机和心路历程,我没兴趣转述,还是自己去看吧。总之它对后来的语言设计影响很大,let...in...和rec...in...语句给了递归和非递归函数定义很大的便利,把所有数据类型都视为一等公民,call by value的传参方式,词法作用域,字符串作为char list处理,提供了多级模式匹配……作者信心满满的说我这个语言比那时候的LISP不知道高到哪里去了。

后来SASL发展出了上文f(x)形式的lambda表达式实现,仅用let定义递归,用:表示cons,用++表示append,引入了缩进where语句,允许多等式模式匹配的函数定义……也就是我们今天的Haskell语法的一部分特性。

同年发展出了其他两种影响力还行的惰性函数式语言,这种模式的优越之处看原文吧,我认为也是硬件所限,到今天未必有那么必要了

Advantages of Laziness

顺便一提,早期函数式语言会考虑用动态类型实现,是因为这是当时主要的推迟类型检查实现类型“多态”的办法,虽然说包括后来出现的Erlang确实证明这种做法还有市场,不过动态类型的优势并没有想象的那么巨大。

NPL用借助了代数类型(ISWIM时期的概念)多等式函数定义的方法取代了case表达式,在NPL基础上发展出的HOPE是高阶,显式强类型,支持多态类型的纯函数式语言,后来与ML合流形成了我们今天熟知的Standard ML

早期ML语言特性

因此SML同时具备了模式匹配和类型推断,然而也吸收了ML的references和exceptions所以不是纯函数语言。

Miranda在SASL的基础上加上了代数类型和多态类型,沿用早期版本ML中*代替类型变量的传统来做出类型签名,如:

tree * ::= Leaf * | Node (tree *) (tree *) 

开始引入变量和constructor在名字上的区别:首字母大写的用于定义constructor,首字母小写的用于定义变量。延续了SASL的惰性,纯函数性质,并加入list comprehesion,类型推断/选择指定的多态类型。另外一个相比SASL的重要改变是加入了守卫(guard)表达式取代原来的条件表达式

当然这样做也强迫where语句的作用域从传统ISWIM的单个表达式扩展到了整个rhs(right-hand side整个等式右边),Haskell如今还保留着这个改变。

Miranda无疑是同时期唯一一个结合了Milner多态类型系统的惰性纯函数语言,很快就风靡起来的了……

后起之秀Haskell与Miranda有很多相似之处:惰性求值,高阶,带有代数类型的多态类型系统……不过它们在类型定义上有很大的语法差别,比如把类型变量中的*演变成了小写字母

细节不再一一回顾,有兴趣请见原文。Haskell在语法的选择上更为丰富,大部分Miranda的东西都在Haskell留存下来了。比较新颖的是Haskell加入了type class,而这个东西又到处是坑

比如只是Haskell强制要求instance type必须generic,这个样子是不行的:

class Taut a where
   taut :: a->Bool
instance Taut Bool where
  taut b = b
instance Taut a => Taut (Bool->a) where -- !(Bool->a) illegal
  taut f = taut (f True) && taut (f False)

只能在用GHC时首行添加

{-# LANGUAGE FlexibleInstances #-}

或者老实用

class Boolean b where
  fromBool :: Bool->b
instance Boolean Bool where
  fromBool t = t
class Taut a where
  taut :: a->Bool
instance Taut Bool where
  taut b = b
instance (Boolean a, Taut b) => Taut (a->b) where
  taut f = taut (f (fromBool True))
          && taut (f (fromBool False))

这就不如SASL语法那么透明了……


好了,我走马观花的带着看了一遍这个lecture note,有兴趣的同学还是去看论文细节吧,没兴趣的话就当外行(我也是)看个热闹了解一些语言早期八卦,方便下次聚会的时候吹牛……不也挺好吗?

编辑于 2019-06-11 12:12