看来最后还是得玩玩函数式编程

functional programming 说起来总觉得有点玄,最近想来想去还是要把这个东西玩的更清楚一点,这里做点笔记。前面想搞清楚的 scala + scalding,或者 GNU R,又或者 emacs 的 eLisp,还有 haskell、ML 等等等等,这些都是 functional programming language。其实前面对这个概念(相对于 imperative programming)的理解还是有点偏差的,这里用一个简单的例子来说明一下。

其实这个例子在本科的时候师父就举过,他大概是说数学书“表意”上存在某种歧义:

  • 很多时候数学书上的等号表示“相等”,其实也不尽然,比如 e = \lim_{n \to \infty} (1 + \frac{1}{n})^n,从某个意义来说这个等号只是表示 e 是后面一串东西的“别名”,我们将这个复杂的结果用简单的符号进行了替换,将对应的“值” bind 到这个符号上了
  • 但是某些时候却要表示“赋值”,这种情形在将优化算法的时候常见 x = x + \Delta x,师父强调这个等号一般要用另外一个符号,我也一般将这种写法改写成为 x \gets x + \Delta x 以示区别

这个地方等号的歧义其实是说,前者等号描述的其实是一个替换关系,后者是表示对值的更改。这个微妙的区别反应在写程序上,正是 functional programming 与 imperative programming 的区别:

  • functional programming 里很重要的就是表示的替换关系,
  • imperative programming 里面很重要的是表示修改状态

这种微妙的区别导致实现一个简单的问题上策略的差异。这里用经典的阶乘来说明:对于长期习惯了 imperative programming 的我来说,想到的就是 n! = n \cdot (n - 1) \cdot \cdots \cdot 1,写一个循环搞定

template <class Integer> Integer
factorial (Integer n) {
  Integer prod = 1 ;
  for (Integer i = 2 ; i < n + 1 ; ++ i)
    prod *= i ;
  return prod ;
}

我们很自然的引入了某个状态,并且通过修改它得到了需要的结果。而 functional programming 的思路却是将其转换为替换,即 n! = n \cdot (n-1)!,于是如此的实现就会变成 recursion,

template <class Integer> Integer
factorial (Integer n) {
  if (n < 2)
    return 1 ;
  else
    return n * factorial (n - 1) ;
}

这时候的函数就像前面写得极限一样,类似一种替换的效果。既然如此,我们是否有一些关于“binding”和“substitution”方面的理论成果,看看这种风格能走多远?在数学里面,这就是 1930s 由 Alonzo Church 提出的 \lambda calculus 所表述的演算系统。

lambda calculus

我们将以上概念抽象成为数学符号(这其实是某个 BNF 表示的 language):

  • lambda term 可以是一个变量
  • \lambda x.t 表示一个类似函数的东西,它接收一个变量 x,将变量 x 的值代入这个 lambda term t,这称为一个 lambda abstraction
  • 将一个 lambda term 和另一个前后放在一起,表示 application

咋一看这个似乎只能表示一元函数互相的关系,但实际上通过 currying 可以变成多元函数,下面是几个常见的例子:

  • \lambda x.x 相当于是一个 identity function
  • \lambda x.(\lambda y.t) 相当于是一个两元函数,

为了简便起见,我们常如下定义优先级和省略写法:

  • application 是左结合的,即 ABC 表示 ((AB)C)
  • application 比 abstraction 优先级高,即 \lambda X.AB 表示 \lambda X.(A B)
  • 连续的 lambda 可缩写,即 \lambda XYZ.M 表示 (\lambda X. (\lambda Y. (\lambda Z.M)))

相关的概念有 free variable、bound variable,常用的一些操作包括 alpha conversion、beta reduction 和 eta conversion:

  • \lambda X_1.M \rightarrow^\alpha_{\mathbf{n}} \lambda X_2.M[X_1 \leftarrow X_2]
  • (\lambda X.M_1) M_2 \rightarrow^\beta_{\mathbf{n}} M_1 [X \leftarrow M_2]
  • \lambda X.MX \rightarrow^\eta_{\mathbf{n}} M

通过这个 calculus 我们能

  • 定义 bool 和 boolean algebra:通常可以令 true 为 \lambda x.\lambda y.x,false 为 \lambda x.\lambda y.y,令 if 为 \lambda v.\lambda t. \lambda f. v t f,通过这样的定义,我们可以展开 if true M N 或者 if false M N 看看结果,这里我们以前者为例:\text{if true} M N \rightarrow (\lambda v.\lambda t. \lambda f. v t f) (\lambda x.\lambda y.x) M N,这其实很容易看出来,if 是三元函数,表示后面三个东西做 application,true 是两元函数,取第一个参数,于是 reduction 之后就是 M。
  • 定义(类比)自然数,比如 0 = \lambda f.\lambda x.x,而 1 = \lambda f.\lambda x. f x,之后我们只需要增加 fx 前面即可。每一个自然数 n 对应于一个“高阶函数”,即函数的函数,它能将 f 这个函数做 n 次 composition;我们还可以定义加法,首先定义加 1,\text{add1} = \lambda n.\lambda f. \lambda x. f(n f x),这样我们对 0 多用几次就能得到前面定义的自然数
  • 其实我们离一般的程序语言需要的控制结构不远了,比如 for-loop 或者 while-loop 等本质上都可以用 recursion 来实现,为此我们必须扩展 \lambda calculus,避免出现同一个名字在定义两侧均出现的问题,这一般使用如下技巧,将自己多次作用到参数上等价于 \text{mkmk} = \lambda k.\lambda t.t ((k k) t),这样令 \text{mk} = (\text{mkmk}\, \text{mkmk}),我们就能将任意一个基本的操作(第一个参数是占位符,传递的仍然是自己)弄成递归的调用了。这类 mk 常被称为 fixed point operator,更有名的是 Y combinator,一般定义为 \lambda f.(\lambda x. f (x x)) (\lambda x. f (x x))

lisp, scheme, haskell and etc

最早的 functional programming language 莫过于 lisp 了,这是第二老的编程语言(更老的是 fortran)。lisp 的发展导致了两种风格的变体:Common Lisp 算是集大成者,各种特性都加进去,而 Scheme 算是 minimalist 仅仅使用了最核心的一些 lisp 的特点。后者适合教学,比如 Structure and Interpretation of Computer Programs 一书就是讲述 scheme 的。

Linux 里面其实有不少这些语言的实现:

其实也没搞清楚,这些人为啥这么热衷于搞一堆 programming languages…

——————
And the servant ran to meet her, and said, Let me, I pray thee, drink a little water of thy pitcher.

Advertisements
看来最后还是得玩玩函数式编程