函数式编程 - Scheme 1

第十九课

引入

本课之前,我们已经介绍两种编程范式,面向过程 (procedure-oriented) 和面向对象 (object-oriented)。面向过程范式下的程序通常由几个高级 (high-level) 函数如 init, doTaskA, doTaskB, finish和一些负责更小过程的低级 (low-level) 函数构成;面向对象范式下的程序通常围绕着系统中的对象,通过对象之间的信息传递改变对象内部状态,从而完成具体编程任务。本节将介绍一种新的范式,函数式编程 (Functional Programming)。

函数式编程与面向过程编程有些相似,但最大的区别在于:面向过程编程不在乎每个函数的返回结果,而函数式编程则是围绕着每个函数的返回结果来编程。函数式编程通常把一个大的编程任务看作是一个函数,任务的输入数据就是函数的输入,而任务的结果就是函数的输出结果,而这个任务对应的函数又可以分解 (decompose) 成许多更小的函数,它们之间同样依靠输入和输出结果来沟通,达到完成最终任务的目的,举例如下:

f(x, y) = x^3 + y^2 + 7
g(x) = f(x, x+1) + 8
h(x, y, z) = f(x, z) * g(x+y)

我们的任务是就是输入 x, y, z,输出 h(x, y, z) 的值,而 h(x, y, z) 又可以被分解成 f(x, z) 和 g(x+y) 相乘的结果...

Scheme 举例

> (define celsius->fahrenheit (temp)
(+ 32 (* 1.8 temp)))
> (celsius->fahrenheit 100)
212

为了和面向过程编程区分,我们把 celsius-> fahrenheit 称为 procedure,(celsius->fahrenheit 100) 称为 evaluate procedure,与二者对应的是面向过程编程中的函数 (function) 以及函数调用 (function call)。

Scheme 基础

Scheme 中,除了 primitive types,剩下的都是 list。这里 ' 实际上是 (quote ...) 的简写,它的作用是抑制 (suppress) evaluation,' 中的元素都是 list 数据。car 和 cdr 是 list 的选择器,car 返回 list 中的第一个元素,cdr 返回 list 中除第一个元素之外的 list。

> (car '(1 2 3 4 5))
1
> (cdr '(1 2 3 4 5))
(2 3 4 5)
> (car (cdr (cdr '(1 2 3 4 5))))
3
> (caddr '(1 2 3 4 5))
3
> (cdr '(4))
()
> (cdr '())
; specification 没有定义行为,不要这么做

cons 是 construct 的缩写,它可以理解为 car 的逆操作,将一个元素放到 list 的首位:

> (cons 1 '(2 3 4 5))
(1 2 3 4 5)
> (cons '(1 2 3) '(4 5))
((1 2 3) 4 5)

append 可以把两个 list 合成一个 list

> (append '(1 2 3) '(4 5)
(1 2 3 4 5)
> (append '(1 2) '(3) '(4 5) '(6 7 8))
(1 2 3 4 5 6 7 8)
> (append '(2 3) (list 1) '(4 5))

define 可以把一个名字和一个表达式在环境中联系起来

> (define add (x y)
(+ x y))
ADD
> (add 10 7)
17

Scheme 在 runtime 中才会发现类型不匹配

> (add "hello" "world")
error

Scheme 中对整个 list 的操作通常选择用递归而不是迭代来完成

(define sum-of (numlist)
(if (null? numlist) 0
(+ (car numlist)
(sum-of (cdr numlist))))

小结

Scheme 与 C 相比是一门对程序员来说更加简单的语言,它把程序员与内存直接打交道的工作完成,程序员可以更多地思考程序的逻辑本身。

参考