欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《编程机制探析》第十九章 函数 = 数据 = 类型 ?

程序员文章站 2022-05-17 13:43:48
...
《编程机制探析》第十九章 函数 = 数据 = 类型 ?

本章继续讲解ErLang和Haskell的语言特性。
本书中选择ErLang和Haskell作为研讨语言,是因为我个人觉得这两门语言最具有代表性。
网上有一本脍炙人口的函数式编程教材,叫做《计算机程序的构造和解释》,英文为《Structure and Interpretation of Computer Programs》,简写为SICP。
你在网上搜索SICP,就能够直接搜索到这本书的网址。这本书非常有名,世界上不少有名大学用这本书作为教材。同时,这本书在对函数式编程感兴趣的程序员中也非常有名。
那本书采用的函数式语言是scheme,是LISP语言的一种简化版本,常用作教学语言。我从那本书中学到了很多。我在本书中用到的“树形递归”概念就来自于SICP。
注:LISP也是一门应用相对较多的工业级语言,有很多实际项目。
那本书对于很多函数式编程模型的基本概念,进行了极为透彻的解释和剖析,令我受益匪浅。尤其是其中“数据抽象”关于Pair数据类型的描述。
在SICP中,Pair数据模型就是用闭包来实现的。在scheme语言中,闭包的概念同ErLang和Haskell是一样的,也是匿名函数。而且,scheme语言中的匿名函数干脆就用lambda这个关键字来定义。
Scheme的语法和LISP语言相似,也是一门值得学习的语言。不过,这不是本书的任务了。
我在这里,就用ErLang的匿名函数,模拟SICP中的例子,将Pair结构(即二元组)实现一遍。
读者可能会问,Pair结构还用实现吗?不就是二元组吗?ErLang里面不是已经有Tuple类型吗?这里的假设是,现在,我们只有一个非常基础的语言,还不支持Tuple类型,只支持最基本的函数式语法,我们如何在这样的条件下,从头构造出Pair(即二元组)这个类型。
在这个假设中,我们要考虑到最基本的函数式编程语言中的Pair实现。在这个纯粹的世界里,一穷二白,我们没有任何资源,只有最基本的生产资料——函数。
我们只能借助于函数来实现Pair数据结构。前面提到了,函数实现数据结构,必须借助闭包特性携带数据。前面也举了简单的闭包例子。
下面我们来看如何用闭包实现Pair数据结构。采用的编程语言,主要是ErLang语法,配上文字说明,和一定的类JavaScript代码对照帮助。
首先,我们定义Pair数据结构的一个构造函数construct_pair。ErLang语法如下:
construct_pair( Head, Tail ) ->
  fun( select_head ) -> Head;
     ( select_tail ) -> Tail end.

这段代码的意思是,construct_pair函数内部,定义了一个匿名函数,这个匿名函数的作用是,当匿名函数接受到一个select_head常量作为参数的时候,就返回construct_pair函数的Head参数;当匿名函数接受到一个select_tail常量作为参数的时候,就返回construct_pair函数的Tail参数。最后,construct_pair函数返回这个匿名函数。一定要注意,Pair函数返回的是另一个函数,返回值是一个函数。
请注意其中fun定义匿名函数时有多个模式匹配分支的写法。
可以看到,这是一个典型的闭包应用。匿名函数保存了外部的construct_pair函数的两个参数,将来调用的时候,会返回其中某一个参数。
为了帮助理解,下面给出JavaScript语法的对应代码:
construct_pair(Head, Tail){
  return new Function(Selector) {
if(Selector == “select_head”)
  return Head;
if(Selector == “select_tail”
  return Tail;
  }
}

现在我们定义了construct_pair函数,这是一个构造函数,能够构造并返回一个函数,这个返回的函数就是一个闭包。下面我们给这个闭包函数定义两个getter方法,用来获取闭包携带的Head和Tail数据。ErLang代码如下:
get_head(ClosureFunction ) –>  ClosureFunction (select_head).
get_tail(ClosureFunction) ->  ClosureFunction (select_tail).

对应的JavaScript语法的代码:
get_head(ClosureFunction ) { return ClosureFunction (“select_head”); }
get_tail(ClosureFunction ) { return ClosureFunction (“select_tail”); }

现在我们有了一个构造函数construct_pair,两个getter函数,Pair数据结构定义完毕。使用方法如下:
Pair = contruct_pair(1, 2),
Head = get_head(Pair),
Tail = get_tail(Pair),

变量Head的值是1,变量Tail的值是2。
我们可以看到,这么定义的Pair数据结构,是一个只读的数据结构,一旦构造完毕,数值就不能修改,只有getter,没有setter。正符合二元组的概念。
这个例子主要表现的概念就是,数据和程序之间的关系。在这里程序就是数据,数据就是程序。这完全是由闭包能够携带数据的特性来实现的。
如果用Haskell的curry特性来实现这个结构,写法会更清晰一些。
contruct_pair :: a -> b -> char -> d
contstruct_pair a b ‘H’ = a
contstruct_pair a b ‘T’ = b

get_head:: (char -> a ) -> a
get_head curried = curried ‘H’

get_head:: (char -> b ) -> b
get_head curried = curried ‘T’

用法为:
pair = contruct_pair a b
theHead = get_head pair
theTail = get_tail pair

二元组可以这样构造?那么,三元组,四元组呢?同样的写法。三元组,就写三个匹配分支。四元组就写四个匹配分支。整个Tuple类型呢?应该如何构造?
这个,从理论上讲,Tuple中有多少个元素,就应该构造多少个匹配分支。这才符合数据即程序、程序即数据的理论模型。
真的是这样吗?有人不敢相信地问。
我点头。真的是这样。事情的真相就是这么残酷。
真实的情况下,我们无法用索引来访问Tuple中的元素,我们只能用模式匹配(具体就是位置匹配)的方式获取Tuple中的元素。
这意味着,如果我们想取得Tuple中某个元素,我们必须这样写:(_, _, x) = (1, 2, 3)。或者,我们就得为Tuple中的每一个位置的元素定义一个获取方法。比如,二元组的获取方法,用Haskell写就是这样:
head (x, _) = x
tail (_, y) = y
如果是个三元组,四元组呢?那就得为每一个长度的元组都定义一连串的函数。
三元组的获取方法:
first (x, _, _) = x
second (_, y, _) = y
third (_, _, z) = z

四元组的获取方法:
first (x, _, _,_) = x
second (_, y, _,_) = y
third (_, _, z,_) = z
fourth(_, _, _, w) = w

别无它法吗?
方法是有的。但是,这需要自定义Tuple类型。由于Haskell的类型定义比较复杂,我们先来看ErLang的自定义Tuple类型。
ErLang提供了一种叫做record的宏定义,允许程序员用字段名字来访问Tuple中的每个元素。具体例子如下:
-record (xyz, {x, y, z})  %  record 的定义,xyz 元组中依次含有 x, y, z三个元素
XYZ = #xyz{ x = 1, y = 2, z = 3}  % 创建一个Tuple
X = XYZ#xyz.x  % 访问Tuple中的元素x ——即第一个元素
Updated = XYZ#xyz{y = 1}  % 更新元素y ——即第二个元素,并生成一个新的Tuple。
另外,record还可以嵌套,还可以模式匹配。在搜索引擎中用ErLang Records两个关键字进行搜索,很容易就能找到ErLang文档中关于record的各种用法的详细例子。其中,模式匹配的例子,令人击节叹赏。强烈建议读者去读一读。
record也叫做Tagged Tuple(贴了标签的元组),Haskell也提供了类似的“Tagged Tuple”自定义类型。我们从头看起。
在Haskell中,“Tagged Tuple”是用data这个关键字来构造的。
data用于定义“类型构造器”(Type Constructor),即“类型”的构造函数。data有两种用法,可以带类型参数,也可以不带类型参数。
不带类型参数的时候,定义出来的类型名本身就是一种具体类型。比如:
data Boolean = True | False
其中的竖线 | 表示“或”的意思。
带类型参数的data定义,就是一种参数化类型(抽象类型)。比如:
data Pair a = pair_constructor a a
我们就定义了一个元素类型相同的二元组类型——Pair。
pair_constructor 10 10 的数据类型就是 Pair Integer。
pair_constructor 1.2 3.1 的数据类型就是 Pair Float。
Pair a是参数化类型(抽象类型)。Pair Integer和Pair Float都是Pair a的类型实例(instance)。这两个类型已经成为了具体类型,不再是抽象类型。
我们看到,Pair实际上对应的数据结构就是二元组,只是元素数据类型相同而已。
我们可以把上述类型构造器的定义修改如下:
data Pair a b = pair_constructor a b
这样,我们就定义了一个通常意义上的二元组——Pair。
pair_constructor 10 10 的数据类型就是 Pair Integer Integer。
pair_constructor 1.2 3.1 的数据类型就是 Pair Float Float。
pair_constructor 10 1.1 的数据类型就是 Pair Integer Float。
那么,我们如何取出Pair中的数据呢?同Tuple一样,我们只能使用模式匹配(位置匹配)的方式获取对应位置的数据。
pair_constructor _ y = pair_constructor 10 12
就把12获取到y变量里面。
我们可以写出pair_constructor的元素获取函数。
head (pair_constructor x _) = x
tail (pair_constructor _ y) = y
我们还可以把类型名和类型构造器名写成一样。比如:Pair a = Pair a a
这样,就得到了“类型名即函数名”的效果。从这里,我们可以体会到更多函数式编程中“一切皆函数”的思想。对应的,面相对象语言中也有“一切皆对象”的思想。
类似于ErLang的record宏,Haskell的data也可以定义字段名。
data Pair a = Pair {head, tail :: a}
这就相当于直接定义了head和tail两个获取方法。head (Pair 10 20) 就得到10,tail (Pair 10 20) 就得到20。
同ErLang的record宏定义一样,我们也可以在模式匹配中用到字段名。
add (Pair{head = x, tail = y}) = x + y
类似的,我们也可以更新某个字段,获取一个新的元组。
p = Pair 10 20
updated = p{y = 30}
调用updated(在Haskell里,updated就相当于函数名),得到的结果是Pair 10 30。
解决了“Tagged Tuple”问题之后,我们继续探索函数式语言的旅程。
不知道读者有没有发现一个奇怪的现象。在ErLang中,顺序语句之间用逗号,分开。但是,在Haskell中,却从来没有提过这事儿。在前面出现的Haskell代码中的函数体中,只有一条语句。确切的说,只有一个表达式,尽管这个表达式可能有很多个条件分支。
难道Haskell函数里只允许有一个表达式吗?没错,事实正是如此。Haskell函数定义中,只允许存在一个表达式。当然,这个表达式可以任意复杂,可以包含很多层次的条件分支。但归根结底,它只能是一个表达式的语法树。
关于Haskell,有一种说法:Haskell是没有调用顺序的。
这种说法的原因就在于此。在Haskell中,每个函数只允许有一条语句,根本就不存在顺序执行的语句,当然就没有调用顺序了。
但是,Haskell真的不存在调用顺序吗?当然……不是。
表达式中可能存在条件分支,执行某个条件分支的时候,总得先判断条件,才能执行该条件分支的表达式。
当我们获得一个函数调用的结果,作为参数传给另一个函数的时候,这里面,函数调用之间也存在顺序。
因此,“Haskell是没有调用顺序的”,这句话是有其适用范围的。比如,在函数体内,在树根表达式的级别上,确实是没有调用顺序的,因为只有一个表达式的语法树的树根。
Haskell函数内部只有一个表达式,那岂不是很受限制?确实如此,使用Haskell,我们必须学会更有效地分解问题,构造程序。
不过,为了方便编程,Haskell还是提供了两种辅助编程结构,允许程序员加入一些变量定义之类的赋值语句。这两种辅助编程结构分别是let … in 结构和where 结构。这两种结构是等价的,只是代码位置摆放不同。
在let … in结构中,变量定义部分写在let和in只见,函数体表达式写在in的后面。在where结构中,函数体表达式写在where的前面,而变量定义写在where的后面。
let … in结构更为常见,而且,其他函数式语言(如LISP)中也存在类似的结构,我们就以let…in结构为例。参见下面的代码:
f :: Integer -> Integer
f a =
let
     i = 1
     j = i + 2
   in
     a – j + i
在这段代码中,我们定义了两个变量——i 和 j,并在函数体中用到了这两个变量。
这段代码没什么出奇的,读者看到这里一定会松一口气——“我说嘛,太阳下没有新雪,也不过是这么回事。”,或者会大失所望地叹一口气——“这有什么嘛。一点新意都没有。”
等一等,我把上面的代码换一种写法。
f :: Integer -> Integer
f a =
let
     j = i + 2
     i = 1
   in
     a - j + i
这段代码中,变量 j的定义引用了变量 i ,而 i 的定义在 j 之后。
看到这里,读者可能会陷入了深思。难道,这是因为Haskell没有顺序的缘故?所以,可以乱序执行?
我得说,这种想法是错误的。从概念上就错了。在let和in之间,只是变量的“定义”,而非变量的“赋值”。这个概念一定要弄清楚。赋值需要顺序,但定义不需要顺序。
为了更清楚地认识这个问题,我们可以把变量定义看做是函数定义,即 i 和 j 是两个函数名,i 和 j 的定义相当于定义了两个内部函数。
这么一想,一切就豁然开朗了。既然是函数定义,那么自然是可以没有顺序的。
事实上,我们确实可以把Haskell中出现的名字都看作是函数名。这个想法很有效。在很多情况下,这种想法能够帮助我们理解很多看似稀奇古怪的现象。
我们再来看一个例子。
f :: Integer -> Integer
f a =
let
     j = 2
     i = 1 / 0
   in
     a – j
这个函数中,函数体表达式没有用到 i 这个变量,因此,i = 1 /0 这条语句就不会被执行。
不过,这种说法是错的。
应该说,i = 1/ 0 这个函数就不会被调用。
这才是正确的表达方法。
我们再来看一个有趣一点的例子。
f :: [Integer]
f = (1 : f)
你能看出这个函数的返回值结果吗?
一个元素全部是1的……无限List?有人犹犹豫豫地说。
没错,这就是Haskell中的著名的无限List。
这不会引起死循环吗?有人问。
在一般的语言中,这种代码确实会引起死循环。但是,Haskell不是一般的语言。它是一种支持Lazy特性的语言。
在计算机常用语中,Lazy(懒惰)这个词,是和Eager(积极)这个词相对应的。
大部分语言都是积极分子(Eager),看到一条语句,就急急忙忙冲上去,将其按倒,啊,不,是将其执行完毕。也就说,Eager语言积极性很高,遇到工作就要一下子做完,从不拖拖拉拉。Lazy语言就不一样,他很懒,总是把工作推到最后一刻,直到不能再拖的时候,才开始真正地工作。
下面,我们就以
UnlimtedList = f
head UnlimtedList
这段代码为例,看看ErLang(积极分子)和Haskell(懒家伙)的不同表现。其中,f就是我们上面定义的构造无限List的函数。
ErLang遇到这段代码,好嘛,立马挥起膀子就开始干活。首先,遇到的是UnlimtedList = f这条语句。于是,ErLang开始调用函数f,期望获得整个List。结果,这一去,当当当,恰如荆轲刺秦王,壮士一去兮不复还。他陷在死循环中,再也回不来了。
Haskell遇到这条赋值语句会怎么样呢?
“等等,你说什么?赋值语句?我没听错吧。”Haskell疑惑地看了我一眼,道:“在我的字典里,只有定义,没有赋值。更没有什么语句。这事儿和我没什么关系。你还是找别人去做。”
好嘛,这家伙还真懒,推得一干二净。
好吧,我承认,我的表达错误。我换一种说法,“请问,Haskell先生,您遇到UnlimtedList = f这条定义,该怎么做呢?”
“定义?”Haskell仍是那副看着白痴的表情,看着我,“你是说定义?我没听错吧?”
“没有。你没有听错。”我耐心道。
“你有没有搞错?!”Haskell发火了,“既然是定义,就让它定在那里好了。你还想干什么?”
“我…..”我又一次被打败了,只好指着下一条代码,“对不起,我错了。可是,您看这里,有个head f表达式,是对UnlimtedList的调用。这个表达式是需要被执行的。您看…..”
“好吧。拿过来我看看吧。”这次,Haskell没有推诿,拿过了任务单。
过了一会儿,Haskell把任务交了回来,简单地告诉我,“是1”。
“就这样?”我问。
“那还能怎样?”Haskell反问。
“你不是应该先获得UnlimitedList这个List吗?”我承认,我确实存有坏心。我想让ErLang和Haskell忙个不停。这样才能对比出我的清闲,从而显示出我作为一个资本家的优越性。
“List?”Haskell又是那副看白痴般的怜悯表情,“醒醒吧。我是大名鼎鼎的Haskell。在我的字典里,所有名字都可以看做是函数。UnlimitedList对我来说也只是一个函数。我只要调用它,得到结果就够了。”
好吧,我承认,是我太仁慈了。我又递给Haskell一份任务单,“那么,请看看这份任务吧。”
那份任务单是这么写的。
f :: [Integer]
f = (f : 1)
调用该函数的表达式是 head f。
“Haskell先生,”我尽量用柔和的声音道,“这一次,我还是需要同样的结果。我需要取得f这个List,啊,不,按照您的说法,是f这个函数。我需要取得f这个函数的返回值的头一个元素。您能帮助我吗?”
Haskell低头看了任务单很久,脸色苍白地抬起头,看着我,咬牙切齿道:“你够狠。”
这一次,Haskell终于被打败了。他被成功地拖住了。我得意地笑了。我只要不让你遇到返回一个值的匹配分支,我只让你遇到递归分支,我看你怎么Lazy,你照样得给我卖力干活。我,陶醉在自己的成功中。
血腥资本家,啊,不,成功企业家,就是这样炼成的。
我们来分析这个案例。f = (1:f) 和 f = (f:1) 有什么不同呢?
有人举手了,龇着一口大白牙,跃跃欲试地跳着道:“我知道,我知道。”
“你知道,你就说吧。”
“f = (1:f) 是尾递归。f = (f:1)是非尾递归。”那人胸有成竹道,目光中满是自信。
“瞎说!”我怒了,“简直比我还糊涂!”
这两种写法,都是非尾递归。因为,最后一步操作,都是一个组成二元组(即List)的操作。
区别在于,f = (1:f)这种写法的递归分支在后,费递归分支在前;而f=(f:1)的递归分支在前,非递归分支在后;非递归分支的位置不同,即造成了两种不同的结局。
Haskell的Lazy只能对非递归分支起作用,遇到递归分支,一样得卖命地干下去。
掌握了这个原则,我们就可以制造更多的无限List。只要非递归分支在前就行了。
f = let
     g = 2 : 3 : f
   in
     1 : g
这个函数返回一个[1, 2, 3, 1, 2, 3 …]模样的List。
g n = n : g (n+1)
f = g 1
这个函数就返回一个自然数List,[1, 2, 3 …]
在函数式语言的概念模型中,函数、类型、数据都可以看做是同一种东西——函数。在Haskell中,函数调用是Lazy的,数据结构也是Lazy的,如前面描述的无限List。
出于效率考虑,Haskell不可能将所有的Tuple类型都用闭包(匿名函数)实现一遍。Lazy特性的实现,通常基于一种叫做Thunk的结构。示意代码如下:
Thunk {
  value = null; // 变量初始值为空

  getValue() {
     if value is null  // 如果变量值为空,说明是第一次使用,那么为这个变量创建值
        then value = createValue();
   
     return value;
  }

  createValue() { … }
}
这种Thunk结构是一种很常见的设计模式,叫做Singleton Pattern。特别的,由于该Singleton具有Lazy特性,所以也叫做Lazy Singleton。