编程语言的一些基础概念（一）：静态函数式编程

世界上最好的编程语言是什么？

这就好像问 世界上最好的车是什么车？F1 比赛的，日常家用的和跑山路的最好的车显然是不一样的。同理，不同的编程语言也有他们最适合的使用场景，程序员们通常都会个几种语言，因为工作需要可能要学新的语言。不同编程语言之间是不是完全不一样呢？他们之间有没有什么共同点是不同语言间类似的呢？有没有一些最基本的概念？

最近在看了 Coursera 上的 Programming Languages, Part A，对于这个问题做了部分解答，这里做个阶段性的总结。

这是门什么样的课？

Programming Languages 这个课程是华盛顿大学的公开课，评分很高，包括在知乎上，有很多人推荐。

课程在 Coursera 上一共有三部分，分别用不同的编程语言来做基础概念的说明和对比，既有函数式编程，也有面向对象编程，Part A 用的是 Standard ML (SML)，Part B 是 Racket，Part C 是 Ruby，分别代表了不同类型的编程语言，为什么是这三门语言，作者在课程里有详细的解释。

不同类型的编程语言

这个课的重点不是在这几门语言本身，而是一些编程语言的概念，和使得这些语言变得优雅的语言特性。

函数式编程 和 SML 的一些语言特性

整个课程的系列就介绍到这，Part A 的重点是函数式编程以及 SML 的一些语言特性。包括了函数式编程的一些概念 数据不可变 (Immutable Data)，头等函数 (First-Class Function)，高阶函数 (Higher-Order Function) 等，以及 SML 本身的一些特性 类型推论 (Type Inference)，柯里化和偏函数应用 (Currying and Partial Application)，模块 (Module) 等。

类型推论（Type Inference）

SML 是静态类型语言( Statistically Typed)，在编译时进行类型检查，同时它又是隐式类型 (Implicit Typed)，可以省略类型声明，在编译时会自动做类型的推导，来判断类型是不是正确的。

val x = 42
fun f(y,z,w) = if y then z+x else 0

函数 f 的参数省略了声明类型，编译器从 x = 42 和 z+x 可以推导出 x 和 z 的类型是 int，从 if y 可以推导出 y 的类型是 bool。这个特性能让代码简洁不少。

List 的用法和非函数式编程很不一样

在 SML 里，List 的最主要功能有两个 hd 代表 head，取数组的第一个元素，tl 表示 tail，数组的第一个之外的全部元素，因为有这样的特性，使得函数式编程的数组递归变得很顺其自然。

fun sum_list (xs : int list) =
	if null xs
	then 0
	else hd(xs) + sum_list(tl xs)

多态的数据类型（Polymorphic Datatypes）

SML 的数据类型有 int, bool, real, string 等具体的，函数接受的数据类型除了这些之外，也可以是多态的。

fun length xs =
	if null xs
	then 0
	else 1 + length(tl xs)

在这个例子里， xs 是一个 list，可以是一个 int list, string list 或者 bool list 等，所以 SML 表示 xs 的类型是 'a list ‘a 表示数据类型的多态，也是能够通过 Type Inference 推导出来的。

数据不可变（Immutable Data）

在 SML 里，没有赋值的概念，而是由一系列的 绑定（bindings）组成的。比如说

(* 这里不是赋值，而是建立了一个新的 x 的 binding，
   在当前的环境下，x 是不能更改的，永远是等于 1 的 *)
val x = 1

(* 这里并不是对 x 的值进行修改，而是新建了一个 x 的 binding，
	 前面的 x 被这个 shadow 了，所以当前的环境下，x 永远是 3 *)
val x = 3

数据不可变是函数式编程最主要的特性之一，优点在于去除了不同代码之间的依赖性，不需要像 Java 这类语言一样去考虑List 传址，一个地方代码对值的更改，不会导致另外一个部分的代码出错。

fun append (xs : int list, ys : int list) =
    if null xs
    then ys
    else (hd xs) :: append(tl xs, ys)

val xs = [1, 2]
val ys = [3, 4]
val z = append(xs, ys)

上面这个例子的作用是 append 两个 list，:: 这个符号是把一个值插入到一个 list 的第一位。因为数据不可变的性质，上面代码中直接返回的是一个新的 list， ys 的值不会因为是被 append 的那个 list 而改变。

反过来看一个 Java 的数据可变，带来了安全隐患的例子，是以前 Java Library 里真实存在的一个 Bug 的简化版。


class ProtectedResource {
   private Resource theResource = ...;
   private String[] allowedUsers = ...;
   public String[] getAllowedUsers() {
      return allowedUsers;
   }
   public String currentUser() { ... }
   public void useTheResource() {
      for(int i=0; i < allowedUsers.length; i++) {
         if(currentUser().equals(allowedUsers[i])) {
             ... // access allowed: use it
             return;
         }
	 		}
   		throw new IllegalAccessException();
   }
}

虽然 allowedUsers 是 private 的，但是 getAllowedUsers 是 public 并且返回的是 allowedUsers，导致了使用这个库的人可以直接修改 allowedUsers 给自己增加权限。当然修复这个问题也很简单，在 getAllowedUsers 里返回 allowedUsers 的一个 copy 就行了。这里想要说明的是在数据不可变的编程语言里，不用去担心数据可变带来的一些负面影响，当然 Java 的传址也有它的好处。

头等函数和高阶函数（First-Class Function and High-Order Function）

头等函数是能作为一个参数传递到另一个函数的函数。高阶函数 是可以接受函数作为参数也可以返回函数作为结果的函数。直接来看个例子

fun f g =
    let val x = 3
    in
        g 2
    end
val x = 4
fun h y = x + y
val z = f h

这里 h是个头等函数，被当成一个参数传入高阶函数 f 中使用。头等函数和高阶函数也是函数式编程中很重要的概念。除了函数式编程之外，在现在热门的一些编程语言里，有一些是支持这个特性的，比如 Python 和 Javascript。

匿名函数（Anonymous Functions）

在要把一个函数作为参数传递到另一个函数时，又不想在环境中去绑定这个函数，可以使用匿名函数。

fun f (g, x) =
  g x

(* 1. 可以定义函数 *)
fun increment x = x + 1
f (increment, 11)

(* 2. 匿名函数 *)
f (fn x => x + 1, 11)

这个功能在 Javascript 和 Golang 里也是支持的。

// Javascript 例子
(function(x, y){
    alert(x + y);
})(2, 3);

词法域（Lexical Scope）

跟头等函数息息相关的是词法域，函数里变量的值是创建函数时的值，而不是调用函数时的值，创建环境和调用环境时隔绝的，可以说一个函数构成了 function closure。还是用上面那个例子

(* 例子1 *)
fun f g =
    let val x = 3
    in
        g 2
    end
val x = 4
fun h y = x + y
val z = f h

在 val z = f h ，函数 f 被调用，f 里 x 的值应该是 4 还是 3 呢？按照上面的定义，函数 h 被创建时，x 的值是4，所以 g 2 调用 h 时，应该是 4 + 2 而不是用重新定义的 val x = 3。再看另一个例子

(* 例子2 *)
val x = 1
fun f y =
    let val x = y + 1
    in
    	fn z => x + y + z (* 这是一个匿名函数 *)
    end
val g = f 4
val x = 3
val y = 5
val z = g 6

val g = f 4 得到 g 是一个函数 fn z => x + y + z，运行 val z = g 6 时，x + y + z 的 x 应该是什么值呢？x 的值在运行 val g = f 4 时就已经绑定了，val x = y + 1 所以 x 的值是 5，后面定义的 val x = 3 不会更改函数 g 里 x 的值。

根据这两个例子，词法域和*动态作用域 *(Dynamic Scope) 比有什么优点呢？

  1. 可以随时修改变量的值，不会影响到函数的调用。
  2. 在例子1中，val x = 3 没任何作用，直接删除没什么问题。但是如果是在动态作用域里，可能别的代码用到了这个值，删除了会影响到别的程序正常运行 ，可以说词法域使减少了代码之间的依赖。
  3. 在例子2中，将 val x = 3 改成 val x = "hi"，因为有词法域，代码不会有任何问题，但是如果是动态作用域的话，即使编译能过，但是会将 string 和 int 相加，产生额外的一些问题。

尾递归（Tail Recursion）

简单理解，在递归的过程中，每一步不需要再做别的运算，直接将结果传递给下一层递归。

fun fact1 n = if n=0 then 1 else n*fact(n-1)

(* 尾递归 *)
fun fact2 n =
 let fun aux(n,acc) =
	 if n=0
	 then acc
	 else aux(n-1,acc*n)
 in
 	 aux(n,1)
 end

上面这两个函数都是计算 n 的阶乘。fact1 在每次递归返回时，都要进行一次乘法运算，而 fact2 则是通过一个 Accumulator 将值向下一层传递。对于第一种普遍的递归方式，每一层递归都缓存在栈里，所以有一个栈的堆叠，但是对于尾递归来说，SML 进行了优化，不会有多个栈的堆叠，返回的时候直接返回最后的值。不单单 SML 对尾递归有优化，像 Scala 这些函数式编程语言应该都有。

fact1

fact2

柯里化和偏函数应用 (Currying and Partial Application)

把接受多个参数的函数，变换成接受一个单一参数的函数，并且返回接受剩下参数的新函数，这个方法叫做 柯里化。看下面的例子：

(* 1. 接受多个参数 Tuple *)
fun sort (x,y,z) = z >= y andalso y >= x
sort (1, 3, 2)

(* 2. 柯里化 *)
val sort = fn x => fn y => fn z => z >= y andalso y >= x
((sort 1) 3) 2)

(* 3. SML 柯里化的简洁写法 *)
val sort x y z = z >= y andalso y >= x
sort 1 3 2

不论是函数的定义，还是调用时，都会比较简洁，除了这个优点外，柯里化使得函数的调用更加灵活。

fun fold f = fn acc => fn xs =>
  case xs of
    []     => acc
  | x::xs’ => fold f (f(acc,x)) xs’

val xs = [1, 2, 3]
val sum1 = fold (fn (x,y) => x+y) 0 xs
val sum2 = fold (fn (x,y) => x+y) 0

在上面这个例子中，我们先绑定了一个函数 fold，作用个 map reduce 的 reduce 一样，把一个 list，按照参数函数 f 的方式，从 acc 开始计算。sum1 直接用 fold 这个函数计算 xs 的总和。因为 fold 是柯里化的，所以可以像 sum2 那样只提供了两个参数，返回一个输入是第三个参数的函数，这就是 partial application 。sum2 是一个函数，参数是一个 list，结果是计算它的总和。

组合函数 (Combining Functions)

一个函数要用到另一个函数的返回结果作为参数时，组合函数可以让代码更简洁，其实也是一个管道的概念。

(* 常规写法 *)
fun sqrt_of_abs i = Math.sqrt(Real.fromInt(abs(i)))

(* 组合函数写法 *)
fun sqrt_of_abs i = (Math.sqrt o Real.fromInt o abs) i

(* 去除 Unnecessary Function Wrapping *)
val sqrt_of_abs = Math.sqrt o Real.fromInt o abs

互递归（Mutual Recursion）

这是一个之前没有注意到的概念。两个函数互相调用，函数 f 里调用 g，函数 g 里调用 f，在运行到函数 f 时，g 还未被绑定，在 SML 里，通过 and 来实现这种互递归。

fun odd(x) =
	if x=0 then false	else even (x-1)
and even(x) =
	if x=0 then true else odd (x-1)

Python 和 Java 也是支持这种互递归的，具体怎么实现的还不了解。

def even(x):
    if x == 0:
        return True
    else:
        return odd(x-1)

def odd(x):
    if x == 0:
        return False
    else:
        return even(x-1)

模块化（Modules）

模块化是要进行大规模开发必不可少的，不同的语言在模块化上的实现方式都不太一样，SML 是通过 structure 来定义模块，用 signature 来定义模块的类型，相当于是模块的接口。代码比较复杂，不具体展开了。

编程语言的组成

Part A 除了介绍函数式编程和 SML 的语言特性外，还穿插了些编程语言的基本概念。

每个变成语言由下面这些组成：

  • 语法（Syntax）: 语言是怎么写的？怎么定义变量，函数等？
  • 语意（Semantics）: 语言特性是什么样的？比如说表达式是怎么被执行的？
  • 风格（Idioms）: 语言的编程风格，怎么写是这个语言的最佳实践？
  • 库（Libraries）: 语言有哪些已经可以用的库，可以大大提高效率？
  • 工具（Tools）: 语言相关的开发工具，比如说编译器，debuggers 等

在学习一门新语言的时候，最基本的是要了解他们的语法，但是最重要的是要知道语意和代码风格。根据不同使用场景选择不同的语言，也可以按照这些部分去考虑。语法简单还是复杂，库和工具是否齐全会影响开发效率，语意和风格是什么样的？有一些会影响运行效率。

没有最好的编程语言，只有更好的程序员

虽然车有很多中不同的类型，车的架构，组成部分等都是差不多的，对于机械工程师来说，最主要是知道车的原理，而不是不同型号的车具体是什么样的。对于程序员来说也是一样的，我们日常熟悉一门或者几门编程语言，但了解编程语言的基本原理，对于用好现在的语言，还有以后学习一门新的语言都是很有帮助的。

总的来说，这个课对于有编程基础的朋友来说难度不大，课程难度也循序渐进，作业设计的也挺不错的。虽然学完这个课没有办法马上应用到什么地方，短时间内可能不会对你现在的工作有什么影响，但是可以帮你打好基础。想学习函数式编程，想要增加对编程语言理解的朋友们，还是很推荐的。

技术编程语言