函数式编程

什么是函数式编程

到现在我们已经讲了很多了，但还没有真正涉及到函数式编程. 目前所讲的所有特性 - 丰富的数据类型（rich data types）， 模式匹配（pattern matching）， 类型推导（type inference）， 嵌套函数（nested functions） - 可以想象它们都可以在一种”超级C“语言中存在。这些特性当然很酷，它们使得代码简洁易读，减少bug，但是它们实际和函数式编程没什么关系。实际上我的观点是函数式编程语言的妙处不是在于函数式编程，而是因为在我们长年习惯于类C语言编程的时候，编程技术已经提高很多了。因此当我们一次又一次地写struct { int type; union { ... } }的时候，ML和Haskell程序员却有着很多安全的变量和数据类型的模式匹配。当我们小心翼翼地 free所有的malloc时候，很多语言在上世纪八十年代就有了超越手工管理的内存垃圾收集器。

好了，现在是时候告诉你们什么是函数式编程了。

基本的但不是很能说明问题的定义是在函数式语言中,函数（functions）是一等公民。

听上去不是很有用，让我们来看个例子。

# let double x =
    x * 2
  in
  List.map double [ 1; 2; 3 ];;
- : int list = [2; 4; 6]

在这个例子中，我首先定义了一个嵌套函数double，它读入一个参数x后返回x * 2。然后map在给定的列表([1; 2; 3])的每个元素上调用double来生成结果：一个每个数都扩大一倍的新的列表。

map被称为高阶函数（higher-order function） (HOF)。高阶函数是指一个把其他函数作为参数之一的函数。

到现在为止还算简单。如果你对C/C++熟悉的，这就象传递一个函数指针作为参数。Java中有匿名类(anonymous class)就象一个低速的闭包（closure）。如果你知道Perl那么你可以已经知道和使用了Perl中的闭包和Perl的map函数，这和我们现在所说的完全相同。事实上Perl很大程度上也是一个函数式语言。

闭包是那些带着它们被定义时的环境的函数。特别的，一个闭包可以引用它定义时存在的变量。让我们把上面那个函数变得更通用一些，以便我们可以对任何整数列表乘以一个任意值n:

let multiply n list =
  let f x =
    n * x
  in
  List.map f list
  ;;

因此:

# multiply 2 [1; 2; 3];;
- : int list = [2; 4; 6]
# multiply 5 [1; 2; 3];;
- : int list = [5; 10; 15]

关于multiply函数有一点值得注意的是嵌套函数f. 这是一个闭包。我们注意一下f怎样使用变量n的值，我们并没有把n作为显式的参数传递给它。f是从它的环境中找到它的。n是传递给函数multiply的参数，所以在这个函数中都是有效的。

这可能听上去很简单，但让我们更进一步的仔细观察下那个对map的调用List.map f list.

map 的定义在List模块中，离当前的代码很远。也就是说，我们把f 传递到一个”很久很久以前，在一个很遥远很遥远的星系“（译者：星球大战片头）中的一个模块。 代码可以传递f给其他模块，或者把它的引用（reference）在某个地方以便之后 再调用它。不管怎样，这个闭包保证f总是可以获取它定义时的环境，比如n。

这里是一个来自lablgtk的真实的例子。实际上这是一个类方法（我们还没有谈到类和对象，暂时 可以把它看作一个函数定义。）

class html_skel obj = object (self)
  ...
  ...
  method save_to_channel chan =
    let receiver_fn content =
      output_string chan content;
      true
    in
    save obj receiver_fn

首先你要知道的是方法最好调用的save函数的第二个参数是一个函数(receiver_fn)。它带着从widge获取的文字重复调用receiver_fn函数。

现在来看receiver_fn的定义。这个函数是一个闭包，因为它含有一个引用,这个因用指向它的环境中的chan。

部分函数应用（Partial function applications）和 currying

让我们定义一个加法函数用来相加两个整数。

let plus a b =
  a + b
  ;;

这里是给前面上课时睡着的朋友的几个问题。

1. 什么是plus?
2. 什么是plus 2 3?
3. 什么是plus 2?

问题一很简单。plus是一个函数。它有两个整数型参数并返回一个整数。我们这样来表示这个函数的类型：

plus : int -> int -> int

问题二就更简单了。plus 2 3是一个数，整数5。我们这样来表示它的类型：

5 : int

但是问题三呢？看上去plus 2是一个错误。但是实际上却不是的。如果我们在OCaml的 toplevel中输入上述代码，toplevel会显示：

# plus 2;;
- : int -> int = <fun>

这不是一个错误。它告诉我们plus 2事实上也是一个函数。它以一个整数为参数并返回一个整数。这是一个什么样的函数呢？让我们给这种神秘的函数起名为f,然后尝试把它作用在几个整数上来看它到底做什么。

# let f = plus 2;;
val f : int -> int = <fun>
# f 10;;
- : int = 12
# f 15;;
- : int = 17
# f 99;;
- : int = 101

在工程上这已经足够proof by example让我们声明plus 2是一个给整数加2的函数。

回到原始的定义，让我们把第一个参数(a)换成2:

let plus 2 b =       (* 这不是真正的OCaml代码！ *)
  2 + b
  ;;

这样我希望你或多或少的开始理解为什么plus 2是给整数加2的函数了吧。

现在来看这些表达式的类别，我们可以领悟到在函数类型中用奇怪的箭头符号->的原因了。

    plus : int -> int -> int
  plus 2 : int -> int
plus 2 3 : int

这个过程叫做currying (或者应该叫 uncurrying,我一直搞不清这两个定义).这个名字来源与Haskell Curry的与lambda calculus有关的重要发现。为了避免进入OCaml背后的数学世界而使这个教程变得过于繁琐，我将不会再进一步地说明这个主题。如果感兴趣，你可以从用 Google来获得更多关于currying的信息。

还记得开始时候我们的double和multiply函数吗？ multiply是这样定义的:

let multiply n list =
  let f x =
    n * x
  in
  List.map f list
  ;;

现在我们可以象这样来更简单地定义double,triple函数：

let double = multiply 2;;
let triple = multiply 3;;

它们确实是函数,不信你看:

# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]

你也可以不用中间函数f，而象这样来直接用部分应用（partial application）：

# let multiply n = List.map (( * ) n);;
val multiply : int -> int list -> int list = <fun>
# let double = multiply 2;;
val double : int list -> int list = <fun>
# let triple = multiply 3;;
val triple : int list -> int list = <fun>
# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]

在上面的例子中，((*) n)是一个(*) (乘)函数的部分应用。 注意这里额外的空格，它使得OCaml不会认为(*是注释的开始。

你可以把中序操作符放在括号中而形成一个函数。这里是一个和以前plus函数等价的一个定义：

# let plus = (+);;
val plus : int -> int -> int = <fun>
# plus 2 3;;
- : int = 5

这里是更多的一些有趣的curring：

# List.map (plus 2) [1; 2; 3];;
- : int list = [3; 4; 5]
# let list_of_functions = List.map plus [1; 2; 3];;
val list_of_functions : (int -> int) list = [<fun>; <fun>; <fun>]

函数式编程的优点

函数式编程，像其他任何优秀的编程技术一样，是你的工具箱中解决某些问题的利器。它使得callback函数变得非常方便，可以用于从GUI编程到场景驱动循环等多种场合。 Functional programming,like any good programming technique,is a useful tool in your armoury for solving some classes of problems. It's very good for callbacks,which have multiple uses from GUIs through to event-driven loops. It's great for expressing generic algorithms. List.map is really a generic algorithm for applying functions over any type of list. Similarly you can define generic functions over trees. Certain types of numerical problems can be solved more quickly with functional programming (for example,numerically calculating the derivative of a mathematical function).

Pure and impure functional programming

A pure function is one without any side-effects. A side-effect really means that the function keeps some sort of hidden state inside it. strlen is a good example of a pure function in C. If you call strlen with the same string,it always returns the same length. The output of strlen (the length) only depends on the inputs (the string) and nothing else. Many functions in C are,unfortunately,impure. For example,malloc - if you call it with the same number,it certainly won't return the same pointer to you. malloc,of course,relies on a huge amount of hidden internal state (objects allocated on the heap,the allocation method in use,grabbing pages from the operating system,etc.).

ML-derived languages like OCaml are "mostly pure". They allow side-effects through things like references and arrays,but by and large most of the code you'll write will be pure functional because they encourage this thinking. Haskell,another functional language,is pure functional. OCaml is therefore more practical because writing impure functions is sometimes useful.

There are various theoretical advantages of having pure functions. One advantage is that if a function is pure,then if it is called several times with the same arguments,the compiler only needs to actually call the function once. A good example in C is:

for (i = 0; i < strlen (s); ++i)
  {
    // Do something which doesn't affect s.
  }

If naively compiled,this loop is O(n²) because strlen (s) is called each time and strlen needs to iterate over the whole of s. If the compiler is smart enough to work out that strlen is pure functional and that s is not updated in the loop,then it can remove the redundant extra calls to strlen and make the loop O(n). Do compilers really do this? In the case of strlen yes,in other cases,probably not.

Concentrating on writing small pure functions allows you to construct reusable code using a bottom-up approach,testing each small function as you go along. The current fashion is for carefully planning your programs using a top-down approach,but in the author's opinion this often results in projects failing.

Strictness vs laziness

C-derived and ML-derived languages are strict. Haskell and Miranda are non-strict,or lazy,languages. OCaml is strict by default but allows a lazy style of programming where it is needed.

In a strict language,arguments to functions are always evaluated first,and the results are then passed to the function. For example in a strict language,this call is always going to result in a divide-by-zero error:

give_me_a_three (1/0);;

If you've programmed in any conventional language,this is just how things work,and you'd be surprised that things could work any other way.

In a lazy language,something stranger happens. Arguments to functions are only evaluated if the function actually uses them. Remember that the give_me_a_three function throws away its argument and always returns a 3? Well in a lazy language,the above call would not fail because give_me_a_three never looks at its first argument,so the first argument is never evaluated,so the division by zero doesn't happen.

Lazy languages also let you do really odd things like defining an infinitely long list. Provided you don't actually try to iterate over the whole list this works (say,instead,that you just try to fetch the first 10 elements).

OCaml is a strict language,but has a Lazy module that lets you write lazy expressions. Here's an example. First we create a lazy expression for 1/0:

# let lazy_expr = lazy (1/0);;
val lazy_expr : int lazy_t = <lazy>

Notice the type of this lazy expression is int lazy_t.

Because give_me_a_three takes 'a (any type) we can pass this lazy expression into the function:

# give_me_a_three lazy_expr;;
- : int = 3

To evaluate a lazy expression,you must use the Lazy.force function:

# Lazy.force lazy_expr;;
Exception: Division_by_zero.

Boxed vs. unboxed types

One term which you'll hear a lot when discussing functional languages is "boxed". I was very confused when I first heard this term,but in fact the distinction between boxed and unboxed types is quite simple if you've used C,C++ or Java before (in Perl,everything is boxed).

The way to think of a boxed object is to think of an object which has been allocated on the heap using malloc in C (or equivalently new in C++),and/or is referred to through a pointer. Take a look at this example C program:

#include <stdio.h>

void
printit (int *ptr)
{
  printf ("the number is %d/n",*ptr);
}

void
main ()
{
  int a = 3;
  int *p = &a;

  printit (p);
}

The variable a is allocated on the stack,and is quite definitely unboxed.

The function printit takes a boxed integer and prints it.

The diagram below shows an array of unboxed (top) vs. boxed (below) integers:

boxedarray.png

No prizes for guessing that the array of unboxed integers is much faster than the array of boxed integers. In addition,because there are fewer separate allocations,garbage collection is much faster and simpler on the array of unboxed objects.

In C or C++ you should have no problems constructing either of the two types of arrays above. In Java,you have two types,int which is unboxed and Integer which is boxed,and hence considerably less efficient. In OCaml,the basic types are all unboxed.