有趣的事实(Fun-Fact)

1
2
3
4
5
6
7
8
printf("hello, world\n");              \\C
(display "hello, world") \\Scheme
NSLog(@"hello, world\n"); \\Objective-C
print("hello, world\n") \\Swift
std::cout << "hello, world\n"; \\C++
System.out.println("hello, world\n"); \\Java
print 'hello, world' \\Python
console.log("hello, world"); \\JavaScript

你有没有奇怪过,为什么每学一门编程语言,第一个要写的程序一定是打印hello, world?这实际上得追溯到The C Programming Language这本书,这本书在1978年发行第一版,作为世界上第一本教授编程语言的书。而书上的第一段程序就是打印hello world。这本书很可能是大部分语言的作者看的第一本编程书,没有这本书,也许就没有计算机语言的大家庭。所以,每个程序员为了祈求程序安稳运行,都要在学习语言的第一段程序写下hello,world这样的咒语。

好了,下面进入今天的主题–编程漫游。先来聊一聊编程语言必须具备的三大要素。


语言和编程的三大要素

语言的三大要素:

  • 基本(primitive)表达式(expression):包括数字和符号等,比如,3、4、+。
  • 复合(compound)表达式:将基本或复合表达式合并后的表达式,比如3+4。
  • 抽象(abstraction) :对某个表达式和复合表达式命名,将表达式和复合表达式与名字捆绑起来,让表达式和复合表达式可以通过捆绑的名字被单独隔离出来当做一个单独的个体使用。计算机中抽象的本意是,在认识集合中,为有关认识命名,将有关认识与其他认识隔离出来。 当然,艺术和数学上的抽象是另一回事了。

接下来通过语言的三大要素,尝试拓展出编程的三大要素。比如将a=3、b=4,将3+4更改为一个sum{return 3+4;}函数,就是将基本表达式与抽象结合起来,延伸出数据(data)比如说a、b,和将复合表达式与抽象结合起来,延伸出过程(process)比如说sum。再将sum过程中的3和4通过第一大要素抽象成a和b并作为参数传入,就延伸出了将过程应用(apply)于数据。通过延伸,就得出了编程的三大要素:

  • 数据
  • 过程
  • 过程应用于数据

这里顺便提一句,既然所有写下的程序都是由这三大要素组成的,那么复杂的程序和简单的程序差别在哪里?就是抽象的层级的不同。更复杂的程序抽象程度比简单程序抽象程度更低,需要处理更加贴近计算机的抽象。并且,抽象层级越高,程序的表达能力越强。

虽然说编程有三大要素,但是,平时在设计程序的时候,实际上就涉及到两件事:过程如何抽象和数据如何抽象。下面就聊一聊这两件事,以及面向对象编程、函数式编程、响应式编程。


过程抽象

这时再深入思考一下,过程是如何抽象的?将特定的表达式推向成更广泛的过程,过程还将数据与如何将数据应用于过程隔离开来。比如,将3+4抽象成,将sum应用于3和4。

尾递归(tail-call)

在很多语言中,迭代和递归之间的区分就是,函数是否调用自身。实际上,迭代也可以用调用自身的方式实现,只要把限制条件当做参数传入再用限制条件判断就可以。这种,用调用自己实现迭代的方式,会表现在最后return语句的地方调用自身,叫做尾递归。很多语言会通过编译器进行尾递归优化,可使函数栈上只会占用恒量的空间。

闭包(closure)

这里会涉及环境(environment)一词,环境这一概念不用深究。理解成语境就可以。比如说,一个函数调用了另一个函数。这两个函数内部有同样的变量名,那么这两个变量名不会冲突。因为,调用函数切换了语境,也就是说切换了环境。

在过程内仍可以定义新的过程,新定义的过程的环境会被拓展(extend)到被定义的环境,而不是被应用的环境。这代表新定义的过程可以读、写到被定义时环境的数据,这种现象叫做词法作用域(lexical scope)。在过程内定义的新过程也叫作闭包。这个闭包的名字是怎么由来的呢?这是因为这个新定义的过程通过读、写和被定义时环境的数据形成了一个闭环,所以叫做闭包。实际上,面向对象编程中的方法(method)与闭包之间没有本质区别,方法的环境也是被拓展到被定义的类(class)中,同闭包一样。

lambda表达式

使用lambda表达式可以代替定义辅助过程,lambda表达式相当于匿名过程。在python中,lambda表达式只能包含一个return表达式,不能包含赋值和条件控制。而scheme、java、c++等其他语言中没有这种限制。lambda表达式起源于历史上的lambda演算。lambda表达式与闭包很容易混在一起,傻傻分不清楚。实际上,将lambda表达式理解成是闭包的一种匿名形式就好。

高阶函数(higher-order-function)

接下来再来考虑,可不可以将过程再抽象?将特定的过程抽象成更广泛的过程。这就引出了高阶函数。可将过程应用于过程,过程也可以返回过程,以提高抽象层级,提高表达能力。不用多说,高阶函数是函数式编程独有的,面向对象编程是不存在高阶函数的。


数据抽象

数据抽象与过程抽象相近。过程抽象将特定的表达式隔离出来,使过程更加广泛。而数据将如何使用数据和数据本身如何构造隔离开来,使数据更加广泛。两种抽象都形成了模块化。

构造数据

对数据做抽象,经常需要将多个信息“粘(glue)”起来。面向对象编程(Object-Oriented-Programming)中,数据用对象和类来构造。而函数式编程中,数据用元组(tuple)来构造。在面向对象编程中,构造出数据比较自然,这里就不多讲了。下面重点聊一聊,函数式编程中如何构造数据。

在函数式编程中,由二元组可以构造出一切数据。让每个节点的第一个元素代表节点的值,第二个元素代表与下一节点的连接。这样就使二元组可以代表每个节点。也就构造出了线性数据结构。

1
(value, (value, (value, (value, nil))))

让节点的第一个元素代表节点的值,第二个元素用线性数据结构代表节点的任意子节点。这样就使二元组可以分为代表节点的二元组和代表同层级节点关系的二元组。也就构造出了树状数据结构。

1
2
3
4
5
6
7
8
9
(value, 
(value, nil)
)

(value,
((value, nil),
((value, nil),
(value, nil)))
)

既然可以构造出线性数据结构,二元组自然也可以构造出图状数据结构和集合。

在函数式编程中,元组甚至可以由一系列两种类型的过程组成的,构成(constructor)和选择(selector)。在Scheme中,可以使用cons、car、cdr过程构造出二元组,cons为构成类型过程。car取出二元组的第一个值,cdr取出二元组的第二个值,car、cdr为选择类型过程。之所以说Scheme可以这样构造出二元组,是因为Scheme处于效率考虑,并没有这样构造。但是,确实可以这样做。

1
2
3
4
5
6
7
8
9
10
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1 -- CONS" m))))
dispatch)

(define (car z) (z 0))

(define (cdr z) (z 1))

既然元组可以构造一切数据,而元组又由一系列过程组成。那认为数据就是一系列过程,这样有问题吗?这样认为是不行的,这就相当于认为数据与过程是等价的了。除了一系列的过程,数据还要有这些过程组合起来可以满足的行为。这里可以看出,数据与过程虽然是不等价的,但数据与过程之间真的没有明显的界限。

通用接口(Conventional-Interface)

数据的通用接口包括,map、for-each、filter、fold-right(accumulate)、fold-left(reduce)、append、flatten、flatmap等等,它们是任意数据都可以提供的高阶函数接口(比较常见的是线性数据结构中),这些接口通过高阶函数的方式,可以提供给数据很强的表达能力。并且还可以将这些接口链(chainning)调用形成流水线(pipeline),以分解复杂操作(operator),使每个过程单一化。以下是Scheme中,如何实现这些通用接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
(define (map op sequence)
(if (null? sequence)
nil
(cons (op (car sequence))
(map op (cdr sequence)))))

(define (for-each op sequence)
(cond ((not (null? sequence))
(op (car sequence))
(for-each op (cdr sequence)))))

(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else filter predicate (cdr sequence)))))

(define (fold-right initial op sequence)
(if (null? squence)
initial
(op (car squence)
(fold-right initial op (cdr sequence)))))

(define (fold-left op initial sequence)
(define (iter result rest)
(if (null? rest)
result
(iter (op result (car rest))
(cdr rest))))
(iter initial sequence))

(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1)
(append (cdr list1) list2))))

(define (flatten sequence)
(fold-right nil append sequence))

(define (flatmap op sequence)
(flatten (map op sequence)))

总结

函数式编程与面向对象编程,它们之间的区别在于数据如何抽象和过程再抽象。函数式编程对过程抽象会更加自然,面向对象编程对现实世界中的模型系统(model system),也可以说是对数据抽象更加自然。现在大部分语言都既含有函数式编程思想又有面向对象编程思想,先用面向对象编程对数据做抽象,再用函数式编程思想对对象做过程抽象,比如像Swift、Python。或者结合出对象-函数式编程语言,比如像Scala。总之,如何将面向对象编程与函数式编程结合起来,才是未来。


响应式编程(Functional-Reactive-Programming)

整篇文章都在提及过程而不是函数这个名词,只是因为过程这个概念比函数更加广义。比如说,现在常见的GUI程序,Web与App基本上就做了两件事:用户交互与处理网络请求。这两件事都是服务器-客户端的系统模型,客户端通过参数和URL向服务端发起请求,服务端相应请求,自然不能说这是函数,但这基本上就是过程的定义。计算机上与人做交互,人向计算机输入参数,计算机相应输入的参数并给以与结果,这也是过程。既然这两件事都可以看做是过程,过程又构成了数据的改变,这不就是函数式编程嘛,那就尝试引入函数式编程来做GUI程序。除了引入函数式编程来处理过程,而这两个过程还有个特征,都是回调。而回调,正好符合惰性求值的特点。

惰性求值(Lazy-Evaluation)

与惰性求值相对的就是随机访问(random-access),将数据先计算好放入存储器,访问数据时,直接访问存储器。而惰性求值,顾名思义,不会将数据计算好放入存储器,访问数据时,再进行计算。惰性求值在Haskell语言中是默认的求值方式,而Scheme语言对惰性求值有很好的支持。惰性求值并不会有明确的求值序列,所以在惰性求值方式的函数式编程中要想有明确的求值序列会比较困难,需要monad结构。而在命令式(Imperative)或者面向对象编程中,一定有明确的求值序列。

那如何结合函数式编程和惰性求值来编程?专门构造出流来抽象数据。

流(Stream)

流是结合高阶函数和惰性求值的线性数据。流的性质是,只构造出了流的一部分,如果使用者需要使用流未构造出的部分,流就自动构造下去,像窗口一样,“流动”下去,这也就是为什么被命名为流。这样,使用流的时候就制造出了整个流都已经构造出来的假象,那么流也可以是无限的了。流保存如何计算值(闭包),而不直接保存值。这样流就由流的值和如何计算下一个流构成。如何计算下一个流要先通过此流的值计算出下一个流的值,再将计算出的值和定义出的如何计算下下一个流构成新的流。以下就是Python简单实现出的Stream。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Stream(object):
def __init__(self, first, compute_rest, empty=False):
self.first = first
self._compute_rest = compute_rest
self.empty = empty
self._rest = None
self._computed = False
@property
def rest(self):
"""Return the rest of the stream, computing it if necessary."""
assert not self.empty, 'Empty streams have no rest.'
if not self._computed:
self._rest = self._compute_rest()
self._computed = True
return self._rest
def __repr__(self):
if self.empty:
return '<empty stream>'
return 'Stream({0}, <compute_rest>)'.format(repr(self.first))

以下是如何创建一个Stream。

1
s = Stream(1, lambda: Stream(2+3, lambda: Stream.empty))

可以看到,每个Stream都由流的值和用匿名过程表示的如何计算下一个流构成。

此时,用流就结合出了响应式编程。响应式编程的世界观:一切都是按照函数式编程中进行数据抽象,然后构造出来的流!这意味着,任何值都可以转换为流,甚至是1和0,这样就将GUI程序转化一个无穷无尽的流。

Everything-is-a-stream

状态

在写程序的时候,经常需要局部变量去表示程序的状态。这实际上是需要让计算机反映时间这一概念,时间的流逝由状态的改变隐式去表示。那么通过状态向计算机反映时间,编程的时候就需要注意表示状态变量的操作顺序,操作顺序会影响程序的正确性。更麻烦的就是多线程下的并发同步问题。函数式编程尽力就想干掉状态,但仍反映时间,这可怎么整?

先将数据分为可变(mutable)数据和不可变(immutable)数据。对于可变数据,存在状态,改变数据后还是同一个数据,数据只是改变了状态。而不可变数据,不存在状态。改变数据后,改变后的数据和未被改变时的数据不是同一个数据。

那不可变数据如何解决了多线程下的并发同步问题?这里涉及到线程安全,实际上肯定只有线程不安全才需要进行线程并发同步嘛。线程安全指的是,多次以多线程执行程序和这段程序以单线程执行最后结果一致。不可变数据每次数据都不是同一个数据,所以是线程安全的,自然也就不需要加锁,解决了线程同步问题。

再使用不可变数据来反映程序随时间流逝而变化,就像上文提到的Stream一样,Stream每次被访问都会创建出一个新的Stream。函数式编程尽量使用不可变数据来编程。

而从这方面看,响应式编程还有个特点,将人与计算机的交互抽象为过程,干掉状态,解决大部分引入时间而带来的问题。举个简单的例子:

1
2
3
4
5
6
7
8
9
10
11
命令式:
int i = 0
++i
++i

响应式:
Observable->onNext(i=0)->onNext(i=1)->onNext(i=2)
subscribe->i

对于命令式中,i是可变数据,存在状态,如果你想在i=1的时候,做一些事,你要自己模拟出计算机如何计算,然后再在正确的位置写代码。
而响应式中,i是不可变数据,不存在状态,你根本不需要关心正确的位置,你只要在一个地方写就可以了。

到这里再用几句话总结一下响应式编程是个啥?

FRP结合了函数式和响应式,函数式体现在哪?函数式体现在用函数抽象数据,用流来实现这一点,响应式体现在哪?响应式体现在干掉状态,用不可变数据来实现这一点。并且FRP与命令式编程的最大区别在于,命令式编程语言就是在告诉如何计算机如何做(how to do),而FRP告诉计算机做什么(what to do),实际上这就是FRP是声明式范式的子范式的一种表现。

为什么上文说解决大部分问题?因为在交互式系统中,状态是没法完全舍弃的。实际上,状态这个问题背后的本质是计算机的计算模型。SICP第三章最后一段如是说:

本章开始时提出了一个目标,那就是构造出一些计算模型,使其结构能够符合我们对于试图去模拟的真实世界的看法。我们可以将这一世界模拟为一集相互分离的、受时间约束的、具有状态的相互交流的对象,或者可以将它模拟为单一的、无时间也无状态的统一体。每种观点都有其强有力的优势,但就其自身而言,又没有一种方式能够让人们完全满意。我们还在等待着一个大一统的出现。

到这里,可以看出编程就是如何用计算机的计算模型模拟真实世界。那么,在回答如何模拟真实世界之前,先要回答我们如何认识世界,而这个问题就是物理和哲学要回答的问题了。计算机在等待的大一统计算模型,很可能就是物理界在等待的万物统一理论。


引用

SICP 习题答案 http://sicp.readthedocs.io/en/latest/

SICP in python https://wizardforcel.gitbooks.io/sicp-in-python/content/index.html

闭包 http://blog.codinglabs.org/articles/closure-perspective-of-abstract-mathematic-and-functional-language.html

FRP http://reactivecocoa.io/philosophy.html