这次回顾Week4的内容，主要介绍了Standard ML的头等函数和高阶函数。

课程主页：

https://www.coursera.org/learn/programming-languages/home

B站搬运：

https://www.bilibili.com/video/BV1dL411j7L7

Week 4

头等函数(First-Class)简介

什么是函数式编程？

“函数式编程”可能意味着一些不同的事情：

在大多数/所有情况下（已完成和正在进行）避免突变
将函数用作值（本节）
鼓励递归和递归数据结构的风格
更接近数学定义的风格
使用惰性的编程习语（稍后的主题，简要介绍）
不是OOP或C的东西？（不是一个好的定义）

除了”让函数式编程变得简单/默认/必需”之外，不确定是否存在”函数式语言”的定义。

对某一种语言没有明确的是/否

头等函数

头等函数：可以在我们使用值的地方使用它
- 函数也是值
- 参数、结果、元组的一部分、变量绑定、由数据类型构造器或异常
- 例子：
```
fun double x = 2*x 
fun incr x = x+1 
val a_tuple = (double, incr, double(incr 7))
```
最常见的用途是作为另一个函数的参数/结果
- 另一个函数被称为高阶函数
- 分解常见函数的强大方法

函数闭包

函数闭包：函数可以使用来自函数定义之外的绑定（在函数定义的范围内）。
- 使得头等函数更加强大
- 稍后将在更简单的例子之后讨论这个特性
头等函数和函数闭包之间的区别没有得到普遍的理解
- 即使术语被混淆，也有重要的概念上的区别

小结

本节的大部分内容是：

如何使用头等函数和闭包
精确的语义
多种强大的习语

函数作为参数

我们可以将一个函数作为参数传递给另一个函数
- 不是一个新的功能，只是以前从未想过这样做
剔除普通代码的优雅策略
- 用调用一个函数来代替N个类似的函数，在这个函数中，你传递N个不同的（短）函数作为参数

例子

可以重用n_times而不是定义许多类似的函数

计算f(f(…f(x)))，其中调用次数为n

代码：

fun n_times (f,n,x) = 
    if n=0
    then x
    else f (n_times(f,n-1,x))

fun increment x = x+1

fun double x = x+x

val x1 = n_times(double,4,7)
val x2 = n_times(increment,4,7)
val x3 = n_times(tl,2,[4,8,12,16]) 

(* and we can define functions that use n_times *)
fun addition (n,x) = n_times(increment,n,x) (* assumes n >=0 *)
fun double_n_times (n,x) = n_times(double,n,x)
fun nth_tail (n,x) = n_times(tl,n,x)

多态类型和函数作为参数

关键点

高阶函数通常非常”通用”和”可重用”，以至于它们有多态类型，即有可变类型的类型
但也有非多态的高阶函数
也有多态的非高阶（一阶）函数
了解函数的类型总是一个好主意，特别是高阶函数

类型

fun n_times (f,n,x) = 
    if n=0
    then x
    else f (n_times(f,n-1,x))

val n_times : ('a -> 'a) * int * 'a -> 'a
- 更简单但不太有用的类型：(int -> int) * int * int -> int
我们的两个例子用int实例化了'a
我们的一个例子用int list实例化了'a
这种多态性使n_times更有用
类型是根据参数的使用方式推断的（后面的讲座）
- 描述了哪些类型必须是确切的东西（如int），哪些类型可以是不一样的东西（例如，'a）

多态性和高阶函数

许多高阶函数是多态的，因为它们是如此可重用，以至于某些类型“可以是任何东西”
但有些多态函数不是高阶函数
- 例如：len : 'a list -> int
还有一些高阶函数不是多态的
- 例如：times_until_0 : (int -> int) * int -> int
```
fun times_until_0 (f,x) =
	if x=0 then 0 else 1 + times_until_0(f, f x)
```

匿名函数

匿名函数介绍

在顶层不必要的定义仍然是糟糕的风格。

fun triple x = 3*x
fun triple_n_times1 (f,x) = n_times(triple,n,x)

所以这样更好（但不是最好的）

fun triple_n_times2 (n,x) =
  let fun triple x = 3*x in n_times(triple,n,x) end

而这是更小的范围

它有意义，但看起来很奇怪（风格差）

fun triple_n_times3 (n,x) = 
    n_times((let fun triple y = 3*y in triple end), n, x)

匿名函数

这样做是不行的，一个函数绑定不是一个表达式
```
fun triple_n_times (f,x) =
	n_times((fun trip y = 3*y), n, x)
```
这是我们构建的最佳方式，匿名函数的表达式形式
```
fun triple_n_times (f,x) =
	n_times((fn y => 3*y), n, x)
```
像所有表达式一样，可以出现在任何地方
- 语法：
  - fn而不是fun
  - =>而不是=
  - 没有函数名，只有一个参数模式

使用匿名函数

最常见的用途：高阶函数的参数
- 不需要名字，只需传递一个函数即可
但是：不能为递归函数使用匿名函数
- 因为没有名字来进行递归调用
- 如果不是为了递归，fun绑定将是val绑定和匿名函数的语法糖：
```
fun triple x = 3*x
val triple = fn y => 3*y
```

不必要的函数包装

一种风格点

比较：

if x then true else false

与：

(fn x => f x)

所以不要这样做：

n_times((fn y => tl y),3,xs)

当你可以这样做的时候：

n_times(tl,3,xs)

Map和Filter

Map

代码：

fun map (f,xs) =
    case xs of
	[] => []
      | x::xs' => (f x)::(map(f,xs'))

类型：

val map : ('a -> 'b) * 'a list -> 'b list

毫无疑问，Map是”高阶函数名人堂”中的一员

这个名字是标准的（对于任何数据结构）
一旦你知道了它，你就会一直使用它：节省了一点空间，但更重要的是，传达了你正在做什么
类似的预定义函数：List.map
- 但它使用了currying（后续介绍）

Filter

代码：

fun filter (f,xs) =
    case xs of
	[] => []
      | x::xs' => if f x
		  then x::(filter (f,xs'))
		  else filter (f,xs')

类型：

val filter : ('a -> bool) * 'a list -> 'a list

filter是名人堂的一员：

所以，只要你的计算是一个过滤，就使用它。
类似的预定义函数：List.filter
- 但它使用了currying（后续介绍）

归纳总结先前的主题

归纳总结

到目前为止，我们的头等函数的例子都是：

把一个函数作为另一个函数的参数
处理一个数字或一个列表

但头等函数在任何地方对任何类型的数据都是有用的

可以传递几个函数作为参数
可以把函数放在数据结构中（元组、列表等）
可以返回函数作为结果
可以编写高阶函数来遍历你自己的数据结构

只要你想抽象出”用什么来计算”，就很有用

但没有新语言特性

返回函数

记住：函数是头等值
- 例如，可以从函数中返回它们
愚蠢的例子，代码：
```
fun double_or_triple f =
    if f 7
    then fn x => 2*x
    else fn x => 3*x
```
有类型(int -> bool) -> (int -> int)，但REPL打印(int -> bool)-> int -> int，因为它从不打印不必要的括号，并且t1 -> t2 -> t3 -> t4意味着t1->(t2->(t3->t4))

其他数据结构

高阶函数不仅适用于数字和列表
它们对你自己的数据结构（数据类型绑定）的普通递归遍历也很有效
高阶谓词的例子：
- 一个算术表达式中的所有常数都是偶数吗？
- 使用一个更通用的(int -> bool)* exp -> bool类型的函数
- 用(fn x => x mod 2 = 0)调用它

词法作用域的定义

非常重要的概念

我们知道函数体可以使用范围内的任何绑定物
但现在，函数可以被传来传去：在什么范围内？
在函数被定义的地方（而不是它被调用的地方）
这种语义被称为词法范围
这种语义有很多很好的理由（为什么）
- 在解释了语义是什么之后讨论（什么）
- 在课程的后面：实现它（如何）
必须为家庭作业、考试和合格的编程”掌握这个”

例子

展示了即使没有高阶函数的词法范围：

(* 1 *) val x = 1
(* 2 *) fun f y = x + y
(* 3 *) val x = 2
(* 4 *) val y = 3
(* 5 *) val z = f (x + y)

第2行定义了一个函数，当被调用时，在环境中评估主体x+y，x映射为1，y映射为参数
在第5行的调用：
- 查找f，得到第2行定义的函数
- 在当前环境中评估x+y，得到5
- 用5调用该函数，在旧环境中评估主体，产生6

闭包

如何在已经不存在的旧环境中评估函数？

语言的实现会根据需要保留它们

可以把函数的语义定义如下：

一个函数值有两个部分
- 代码（很明显）
- 定义函数时的环境
这是一个”pair”，但与ML pair不同，你不能访问这些部分
你能做的就是调用这个”pair”
这个pair被称为函数闭包
一个调用在环境部分（用函数参数扩展）评估代码部分

例子

(* 1 *) val x = 1
(* 2 *) fun f y = x + y
(* 3 *) val x = 2
(* 4 *) val y = 3
(* 5 *) val z = f (x + y)

第2行创建了一个闭包，并将f绑定到它。
- 代码：”取y并有函数体x+y“
- 环境：”x映射到1”
  - (加上范围内的其他东西，包括用于递归的f)
第5行用5调用第2行定义的闭包
- 所以在环境”x映射到1”中评估的主体扩展为”y映射到5”

后续

现在你知道了这个规则：词性范围。接下来的步骤（本节的其余部分）：

（愚蠢的）例子来证明这个规则是如何与高阶函数一起工作的
为什么另一个自然规则，动态范围，是一个坏主意
使用这个规则的高阶函数的强大习语
- 函数传递给迭代器，如filter
- 还有几个习语

词法作用域和高阶函数

该规则保持不变

一个函数主体在定义（创建）该函数的环境中被评估

用函数参数进行扩展

当我们获取和返回函数时，这个规则没有变化

但”环境”可能涉及嵌套的let表达式，而不仅仅是顶层的绑定序列

使头等的函数更加强大
即使一开始可能看起来违反直觉

例子：返回一个函数

(* 1 *) val x = 1 
(* 2 *) fun f y = 
(* 2a *) 	let val x = y+1 
(* 2b *) 	in fn z => x+y+z end 
(* 3 *) val x = 3 
(* 4 *) val g = f 4 
(* 5 *) val y = 5 
(* 6 *) val z = g 6

相信这个规则：评估第4行，将g绑定到一个闭包：
- 代码：输入z，输出x+y+z
- 环境：y映射到4，x映射到5（shadowing）
- 所以这个闭包将永远在其参数上增加9
所以第6行将15绑定到z上

例子：传递函数

(* 1 *) fun f g = (* call arg with 2 *) 
(* 1a *) 	let val x = 3 
(* 1b *) 	in g 2 end 
(* 2 *) val x = 4 
(* 3 *) fun h y = x + y 
(* 4 *) val z = f h

相信这个规则：评估第3行，将h绑定到一个闭包：
- 代码：输入y，输出x+y
- 环境：x映射到4，f映射到一个闭包
- 所以这个闭包会一直把4加到它的参数上
所以第4行将6绑定到z上
- 第1a行不相关

为什么要使用词法作用域

词法作用域：使用定义函数的环境
动态作用域：使用调用函数的环境

几十年前，两者都可能被认为是合理的，但现在我们知道词法作用域更有意义，以下是三个精确的技术原因。

为什么是词法作用域？

函数含义不依赖于使用的变量名称
- 示例：可以改变f的主体，在所有地方使用q而不是x
```
fun f y =
    let val x = y+1
    in fn z => x+y+z end
```
  - 词法作用域：无关紧要
  - 动态作用域：取决于结果的使用方式
- 示例：可以删除未使用的变量
```
fun f g = 
	let val x = 3
    in g 2 end
```
  - 动态作用域：也许有些g使用它
可以对函数进行类型检查并推断定义的位置
- 示例：动态作用域尝试添加字符串
```
val x = 1
fun f y =
    let val x = y+1
    in fn z => x+y+z end
val x = "hi"
val g = f 7
val z = g 4
```

闭包可以很容易地存储他们需要的数据

更多的例子和习语将陆续出现

fun filter (f,xs) =
    case xs of
	[] => []
      | x::xs' => if f x then x::(filter(f,xs')) else filter(f,xs')

fun greaterThanX x = fn y => y > x

fun noNegatives xs = filter(greaterThanX ~1, xs)

fun allGreater (xs,n) = filter (fn x => x > n, xs)

动态作用域存在吗？

变量的普通作用域肯定是正确的默认值
- 在各种语言中非常普遍
在某些情况下，动态作用域偶尔会很方便
- 所以有些语言（如Racket）有特殊的方法来做
- 但大多数语言并不麻烦
粗略的看，异常处理就更像动态作用域：
- raise e将控制权转移到当前最内层的处理程序上
- 在语法上不必在句柄表达式内（通常也不是）

闭包和重新计算

评估时发生的事

我们知道的事情：

在函数被调用之前，函数体不会被评估
每次函数被调用时，函数主体都会被评估
变量绑定会在绑定被评估时评估其表达式，而不是在每次使用变量时评估

有了闭包，这意味着我们可以避免重复那些不依赖于函数参数的计算

不用担心性能，这是强调函数语义的好例子

重复计算

如下两种方法都能工作，并依赖于使用环境中的变量：

fun allShorterThan1 (xs,s) = 
	filter(fn x => String.size x < String.size s, xs) 
	
fun allShorterThan2 (xs,s) = 
	let val i = String.size s 
	in filter(fn x => String.size x < i, xs) end

第一种方法对xs的每个元素计算一次String.size，第二个方法是对每个列表计算一次String.size s

这里没有什么新东西：当遇到let绑定时会进行评估，当函数体被调用时会进行评估。

Fold和更多闭包

另一个著名的函数：Fold

fold（以及同义词/近亲reduce，inject等）是递归结构上另一个非常著名的迭代器。

通过重复应用f到目前为止的答案，积累一个答案：

fold(f,acc,[x1,x2,x3,x4])计算f(f(f(f(acc,x1),x2),x3),x4)

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

这个版本“folds left”；另一个版本“folds right”
方向是否重要取决于f（通常不是）

类型：

val fold = fn : ('a * 'b -> 'a) * 'a * 'b list -> 'a

为什么又是迭代器？

这些”类似迭代器”的函数并没有内置于语言中
- 只是一种编程模式
- 尽管许多语言有内置的支持，这通常允许提前停止而不使用异常
这种模式将递归遍历与数据处理分开
- 可以为不同的数据处理重复使用相同的遍历
- 可以为不同的数据结构重复使用相同的数据处理
- 在这两种情况下，使用通用方法简洁地传达了意图

fold示例

这些都是有用的，并没有使用”私人数据”：

fun f1 xs = fold ((fn (x,y) => x+y), 0, xs)

fun f2 xs = fold ((fn (x,y) => x andalso y >= 0), true, xs)

这些都是有用的，并且使用了”私人数据”：

fun f3 (xs,lo,hi) = 
    fold ((fn (x,y) => 
	      x + (if y >= lo andalso y <= hi then 1 else 0)),
          0, xs)

fun f4 (g,xs) = fold((fn(x,y) => x andalso g y), true, xs)

迭代器让事实变得更好

由于闭包和词法范围的存在，map、filter和fold等函数变得更加强大
传入的函数可以使用其环境中的任何”私有”数据
迭代器”甚至不知道数据在那里”或它有什么类型

另一个闭包习语：复合函数

复合函数

典型的例子是函数复合：

fun compose (f,g) = fn x => f (g x)

创建一个“记住”f和g绑定到什么的闭包
类型为('b -> 'c) * ('a -> 'b) -> ('a -> ' c)
ML 标准库将其作为中缀运算符o

例子：

fun sqrt_of_abs i = Math.sqrt(Real.fromInt(abs i)) 
fun sqrt_of_abs i = (Math.sqrt o Real.fromInt o abs) i 
val sqrt_of_abs = Math.sqrt o Real.fromInt o abs

从左到右还是从右到左

val sqrt_of_abs = Math.sqrt o Real.fromInt o abs

如同在数学中，函数复合是”从右到左”

“取绝对值，转换为实数，然后取平方根”

函数的”管道”在函数式编程中很常见，许多程序员喜欢从左到右

可以定义我们自己的infix运算符

这个在F#中非常流行（而且是预定义的）

infix |>
fun x |> f = f x

fun sqrt_of_abs i = i |> abs |> Real.fromInt |> Math.sqrt

另一个例子

“备份函数”

fun backup1 (f,g) = fn x => case f x of NONE => g x | SOME y => y

正如高阶函数通常的情况一样，类型暗示了该函数的作用
```
('a -> 'b option) * ('a -> 'b) -> 'a -> 'b
```

另一个闭包习语：Currying

Currying

回顾每一个ML函数都正好需要一个参数
以前通过一个n元组来编码n个参数
另一种方式：取一个参数并返回一个函数，该函数取另一个参数并…
- 以著名逻辑学家Haskell Curry的名字命名的“curry”

例子

val sorted3 = fn x => fn y => fn z => z >= y andalso y >= x 
val t1 = ((sorted3 7) 9) 11

调用(sorted3 7)会返回一个闭包，其中
- 代码为fn y => fn z => z >= y andalso y >= x
- 环境将x映射到7
用9调用该闭包返回一个闭包：
- 代码fn z => z >= y andalso y >= x
- 环境将x映射到7，y映射到9
用11调用该闭包返回true

语法糖，第一部分

一般来说，e1 e2 e3 e4 ...，意味着(...((e1 e2) e3) e4)
因此，可以用sorted3 7 9 11代替((sorted3 7) 9) 11
调用者可以只考虑“用空格代替元组表达式的多参数函数”
- 不同于元组；调用者和被调用者必须使用相同的技术

语法糖，第二部分

一般来说，fun f p1 p2 p3 ... = e，意思是fun f p1 = fn p2 => fn p3 => ... => e
可以只写fun sorted3 x y z = x >=y andalso y >= x来代替val sorted3 = fn x => fn y => fn z => …或fun sorted3 x = fn y => fn z => …
被调用者可以认为“带空格而不是元组模式的多参数函数”
- 不同于元组；调用者和被调用者必须使用相同的技术

最终版本

可以用

fun sorted3 x y z = z >= y andalso y >= x
val t1 = sorted3 7 9 11

作为之前代码优雅的语法糖（比元组更少的字符）：

val sorted3 = fn x => fn y => fn z => z >= y andalso y >= x 
val t1 = ((sorted3 7) 9) 11

Curried fold

一个更有用的例子和对它的调用

接下来会改进调用

fun fold f acc xs = (* means fun fold f = fn acc => fn xs => *)
  case xs of
    []     => acc
  | x::xs' => fold f (f(acc,x)) xs'
(* Note: foldl in the ML standard library is very similar, but 
   the two arguments for the function f are in the opposite order. 
   The order is, naturally, a matter of taste.
*)

(* a call to curried fold: will improve this call next *)
fun sum xs = fold (fn (x,y) => x+y) 0 xs

注意： ML标准库中的foldl的f以相反的顺序接受参数。

部分应用

“参数太少”

以前使用currying来模拟多个参数
但是如果调用者提供“太少”的参数，我们会返回一个“等待剩余参数”的闭包
- 称为部分应用
- 方便且有用
- 可以使用任何curry函数
这里没有新的语义：一个令人愉快的习语

例子

fun fold f acc xs = (* means fun fold f = fn acc => fn xs => *)
  case xs of
    []     => acc
  | x::xs' => fold f (f(acc,x)) xs'
  
fun sum_inferior xs = fold (fn (x,y) => x+y) 0 xs

val sum = fold (fn (x,y) => x+y) 0

我们已经知道，fold (fn (x,y) => x+y) 0评估为一个闭包：给定xs，评估case表达式，f绑定到fold (fn (x,y) => x+y) ，acc绑定到0。

不必要的函数包装

fun sum_inferior xs = fold (fn (x,y) => x+y) 0 xs
val sum = fold (fn (x,y) => x+y) 0

以前学过，当我们可以写val f = g x时，不要写fun f x = g x
这是同样的事情，用fold (fn (x,y) => x+y) 0代替g

迭代器

部分应用对于类似迭代器的函数特别好

例子：

fun exists predicate xs =
    case xs of
      [] => false
    | x::xs' => predicate x orelse exists predicate xs'

val no = exists (fn x => x=7) [4,11,23]

val hasZero = exists (fn x => x=0)

由于这个原因，这种形式的ML库函数通常都是curried
例子：List.map, List.filter, List.foldl

值限制出现了

如果你使用部分应用来创建一个多态函数，由于值限制，它可能无法工作

警告说”类型变量未被泛化”
并且不让你调用该函数
这应该让你吃惊，你没有做错什么，但你仍然必须改变你的代码
请看代码中的变通方法
在讨论类型推理的时候可以多讨论一点

Currying总结

效率

那么哪个更快：tupling和currying多参数？

它们都是恒定时间的操作，所以在你的大部分代码中并不重要，即都”足够快”
对于少部分效率重要的情形：
- 事实证明，SML/NJ编译元组的效率更高
- 但许多其他函数式语言的实现在currying方面做得更好（OCaml、F#、Haskell）
  - 所以currying是”正常的事情”，程序员将t1 -> t2 -> t3 -> t4理解为一个3参数函数，也允许部分应用

可变的引用

ML 有（单独的）突变

可变数据结构在某些情况下是可以的
- 当“更新到世界状态”是合适的模型时
- 但希望大多数语言结构真正不可变
ML使用单独的结构来做到这一点：引用
现在介绍，因为下一个闭包习语中将用到
不要在作业中使用引用——你需要练习无突变编程——它们会导致不太优雅的解决方案

引用

新类型： t ref其中t是一个类型
新表达式：
- ref e创建具有初始内容e的引用
- e1 := e2更新内容
- !e检索内容（不是否定）

引用示例

val x = ref 42
val y = ref 42
val z = x
val _ = x := 43
val w = (!y) + (!z) (* 85 *)
(* x + 1 does not type-check *)

绑定到引用（例如 x）的变量仍然是不可变的：它将始终引用同一个引用
但是引用的内容可能会通过:=更改
并且可能存在引用的别名，这很重要
引用是头等值
就像一个单字段可变对象，所以:=和!不指定字段

另一个闭包习语：回调

回调

一个常见的习语：当事件发生时，库将函数稍后应用，例子：

当按键被按下、鼠标移动、数据到达时
当程序进入某种状态时（如游戏中的回合）

一个库可以接受多个回调

不同的回调可能需要不同类型的私有数据
幸运的是，一个函数的类型不包括其环境中的绑定类型
（在OOP中，对象和私有字段的使用类似，如Java Swing的事件监听器）

可变的状态

虽然这不是绝对必要的，但可变的状态在这里是合理的

我们确实希望”注的册回调”在调用注册回调的函数时发生变化

回调库实例

库维护着”有哪些回调”的可变状态，并提供了一个接受新回调的函数

一个真正的库都会支持删除它们，等等
在例子中，回调的类型是int->unit

所以整个公共库的接口将是注册新回调的函数：

val onKeyEvent : (int -> unit) -> unit

(因为回调的执行是有副作用的，它们可能也需要可变的状态)

实现库

(* these two bindings would be internal (private) to the library *)
val cbs : (int -> unit) list ref = ref []
fun onEvent i =
   let fun loop fs =
        case fs of 
          [] => ()
        | f::fs' => (f i; loop fs')
    in loop (!cbs) end

(* clients call only this function (public interface to the library) *)
fun onKeyEvent f = cbs := f::(!cbs)

客户端

只能注册一个int->unit，所以如果需要任何其他数据，必须在闭包的环境中。

如果需要”记住”一些东西，就需要可变的状态。

例子：

val timesPressed = ref 0
val _ = onKeyEvent (fn _ => timesPressed := (!timesPressed) + 1)

fun printIfPressed i =
    onKeyEvent (fn j => if i=j
                        then print ("you pressed " ^ Int.toString i ^ "\n")
                        else ())

标准库文件

最后一件事

这个话题与本节其他部分没有特别大的关系，但我们把它作为作业3的一个小部分，ML和许多语言一样，有一个标准库:

用于你自己无法实现的东西
- 例子：打开一个文件，设置一个定时器
对于如此常见的东西，一个标准的定义是合适的
- 例子：List.map, 字符串拼接

你应该习惯于寻找文档，并获得关于在哪里寻找的直觉

而不是总是被告知函数的确切作用

应该查看哪里

https://smlfamily.github.io/Basis/manpages.html

组织成结构，这些结构有签名

家庭作业3：寻找并使用或阅读并使用STRING、Char、List和ListPair下的几个函数。

要使用一个绑定：StructureName.functionName

例子：List.map, String.isSubstring

REPL技巧

我经常忘记函数参数的顺序
虽然不能代替完整的文档，但你可以使用REPL来进行快速提醒
- 只需输入函数名称的类型
- 也可以猜测函数名称或打印整个结构
一些 REPL（用于其他语言）对打印文档有特殊支持

可选：带闭包的抽象数据类型

实现一个ADT

作为我们最后一个习语，闭包可以实现抽象的数据类型

可以把多个函数放在一个记录中
这些函数可以共享相同的私有数据
私有数据可以是可变的或不可变的
像对象，强调了OOP和函数式编程有一些很深的相似之处

请看具有插入、成员和大小操作的不可变的整数集的实现代码，实际的代码是先进的/聪明的/棘手的，但没有新的特性

结合了词法范围、数据类型、记录、闭包等

可选：没有闭包的习语

高阶编程

高阶编程，例如，使用map和filter，是非常好的。
语言对闭包的支持使得它非常令人愉快
如果没有闭包，我们仍然可以更手动地/笨拙地进行编程
- 在OOP（如Java）中，使用单一方法的接口
- 在程序性（如C）中，有明确的环境参数
通过这个工作：
- 显示了语言和功能之间的联系
- 可以帮助你理解闭包和对象

概要

这个部分：

只是我们将”移植”到Java和/或C的代码
不使用标准库以提供更全面的比较

接下来的部分：

Java和/或C语言中的代码
哪些地方运行良好，哪些地方令人痛苦

可选：在没有闭包的C语言中使用闭包

C

闭包和OOP对象可以有不在其类型中显示的”部分”。
在C语言中，一个函数指针只是一个代码指针
- 因此，如果没有额外的考虑，接受函数指针参数的函数将不会像接受闭包的函数那样有用
一个常见的技巧
- 总是定义函数指针和高阶函数来接受一个额外的、明确的环境参数
- 但是如果没有泛型，就不能很好地选择列表元素或环境的类型
- 使用void*和各种类型的转换

C技巧

不要这样做：

list_t* map(void* (*f)(void*), list_t xs){
	… f(xs->head) …
}

这样做是为了支持需要私有数据的客户：

list_t* map(void* (*f)(void*,void*) void* env, list_t xs) { 
	… f(env,xs->head) … 
}

像这样的列表库在C语言中并不常见，但回调却很常见！

总是定义回调接口来传递一个额外的void*
缺乏泛型意味着在客户端有大量的类型转换

可选：课程-动机介绍

课程动机

为什么要学习所有（大多数）语言中出现的基本概念？
为什么要使用与C, C++, Java, Python完全不同的语言？
为什么要专注于函数式编程？
为什么要特别使用ML、Racket和Ruby？

注意事项

就本课程而言，我将给出一些理由

我的理由：比普通讲座更多的个人意见
- 其他人也可能有同样有效的理由
部分清单：肯定还有其他好的理由
就课程而言：保持讨论的非正式性
- 不能严格证明所有的理由都是正确的
不会说一种语言比另一种语言”好”。
- 可以毫无恶意地省略”你最喜欢的语言”。

摘要

没有所谓的”最好的”PL
基本概念在某些（多种）PL中更容易教授
好的PL是一个相关的、优雅的编写软件的接口
- 对PL语义的精确理解是无可替代的
函数式语言几十年来一直处于领先地位
- 这些想法已经被主流所吸收。头等函数和避免突变越来越重要
- 同时，利用这些思想成为一个更好的C/Java/PHP黑客
有许多ML、Racket和Ruby的伟大替代品，但每一种都是有原因的，并且它们是如何相互补充的

可选：为什么要研究PL的一般概念

问题

什么是最好的汽车？什么是最好的鞋子？

回答

汽车被用来做相当不同的事情。

赢取一级方程式赛车
带孩子去踢足球
越野
搬运床垫
让风吹动你的头发
在雨中保持干燥

鞋子：

打篮球
去参加正式场合
去海滩

关于汽车的更多信息

一个好的机械师可能有自己的专长，但也了解“汽车”（不是特定的品牌/型号）是如何工作的
内饰的颜色并不重要（语法）
一个好的机械工程师真的知道汽车是如何工作的，如何让它们发挥最大的作用，以及如何设计更好的汽车
- 我没有喜欢的汽车种类，也没有喜欢的PL
要学习汽车部件如何相互作用，从经典设计而不是最新型号开始，可能更有意义的
- 一辆受欢迎的汽车可能不是最好的
- 尤其是对于学习汽车的工作原理来说，可能不是最好的

为什么是语义学和习语

本课程尽可能多地关注语义和习语

对程序、接口和编译器的正确推理需要精确的语义知识
- 不是”我觉得条件表达式可能会这样工作”
- 不是”我喜欢大括号而不是小括号”
- 软件开发的大部分工作是设计精确的接口；PL的含义就是一个非常好的例子
习语使你成为更好的程序员
- 最好在多种场合下看到，包括它们的闪光点
- 即使我从未给你看Java，也能更清楚地看到Java

哈姆雷特

戏剧《哈姆雷特》：

是一部美丽的艺术作品
传授了深刻、永恒的真理
是一些著名谚语的来源
让你成为更好的人

在几个世纪后继续被研究，尽管：

语法对很多人来说非常烦人（但有节奏感）
有更多相同主题的流行电影
阅读《哈姆雷特》不会让你获得暑期实习机会

可选：所有的PL都是一样的吗

所有的汽车都是一样的

为了方便租车，它们都有方向盘、刹车、窗户、大灯等，这很好。
- 然而，学习一辆新车还是很不舒服的。
- 如果你只开过一辆车，你能成为一个伟大的司机吗？
也许PL更像汽车、卡车、船和自行车
那么所有PL真的都一样吗？

所有的语言都是一样的吗？

是的：

任何可以在语言X中实现的输入输出行为都可以在语言Y中实现[Church-Turing论文]
Java、ML和一种有一个循环和三个无限大的整数的语言是”相同的”

是的：

相同的基本原理重复出现：变量、抽象、一元类型、递归定义……

不：

人类条件与不同的文化
一种语言中的原始/默认在另一种中是尴尬的
小心”图灵的陷阱”

可选：为什么选择函数式语言

函数式编程

为什么课程的60-80%时间要使用函数式语言：

不鼓励突变
高阶函数非常方便
通过数据类型等构造实现one-of类型

因为：

这些特性对于正确、优雅、高效的软件来说是非常宝贵的（思考计算的好方法）
函数式语言一直领先于他们的时代
函数式语言非常适合计算的发展方向

大部分课程是关于（1）的，所以在（2）和（3）上花了几分钟时间 …

超前于他们的时代

所有这些都被认为是 “美丽的、毫无价值的、缓慢的PL教授让你学习的东西”

垃圾收集（1995年Java还不存在，PL课程存在）
泛型（Java、C#中的List<T>），比C++更像SML
通用数据表示的XML（像Racket/Scheme/LISP/…）
高阶函数（Ruby, Javascript, C#, …）
类型推理（C#, Scala, …）
递归（1960年关于这个问题的大争论）
其他

介绍

其他流行的函数式PL（按字母顺序排列，请原谅遗漏）

一些”工业用户用户 “列表（肯定存在更多）。

http://www.haskell.org/haskellwiki/Haskell_in_industry
http://ocaml.org/companies.html
一般情形，见http://cufp.org

流行采用的概念。

C#，LINQ（闭包，类型推理，…）。
Java 8 (闭包)
MapReduce / Hadoop
- 避免副作用对这里的容错性至关重要

为什么会出现激增？

我的猜测：

简洁、优雅、高效的编程
JavaScript、Python、Ruby有助于打破Java/C/C++的霸权地位
避免突变是使并发和并行编程更容易的最简单方法
- 一般来说，要处理复杂系统中的共享问题
当然，函数式编程仍然是一个小众市场，但当今世界上有如此多的软件，即使是小众市场也有空间

可选：为什么选择ML, Racket, Ruby

全部语言

SML、Racket和Ruby对我们来说是一个有用的复合：

	动态类型	静态类型
函数式	Racket	SML
面向对象	Ruby	Java/C#/Scala

ML：多态类型，模式匹配，抽象类型和模块
Racket：动态类型，”好的”宏，最小化的语法，评估
Ruby：类，但不是类型，非常OOP，混合器

真希望我们有更多的时间：

Haskell：懒惰、纯洁、类型类、单体
Prolog：统一和回溯

为什么不

SML

SML之外，可以使用类似的语言学习概念：

OCaml：确实是的，但要移植我所有的材料
- 还有一些小东西（例如，二等构造函数）
F#：是的，而且非常酷，但需要一个.Net平台
- 还有一些小东西（二等构造函数，不太优雅的签名匹配）
Haskell：更流行，更酷的类型，但从第一天起就有惰性语义和类型类

无可否认，SML和它的实现已经显示出它们的年龄（例如，andalso和更少的工具支持），但它仍然是静态类型化、eager函数式编程的良好基础。

Racket

Racket之外，可以使用类似的语言学习概念：

Scheme, Lisp, Clojure, …

Racket具有以下特点：

现代感和积极的进化
“更好的”宏、模块、结构、契约……
庞大的用户群和社区（不仅仅是教育）
为教育量身定做的IDE

可以很容易地在Racket系统中定义我们自己的语言。

Ruby

Ruby之外，可以使用类似的语言学习概念：

Python、Perl、JavaScript也是动态类型的，但没有那么”完全”的OOP，而这正是我想关注的
- Python没有（完全的）闭包
- JavaScript也没有类，但却是OOP
Smalltalk满足我的OOP需求
- 但实现方式会合并语言/环境
- 缺乏现代语法和用户基础，等等

这是真正的编程吗？

我们使用ML/Racket/Ruby的方式会让它们看起来很”傻”，正是因为讲座和作业都集中在有趣的语言结构上
“真正的”编程需要文件I/O、字符串操作、浮点、图形、项目经理、测试框架、线程、构建系统等
- 许多优雅的语言拥有所有这些以及更多
  - 包括Racket和Ruby
- 如果我们以同样的方式使用Java，Java也会看起来很”傻”

关于现实的说明

在决定使用/学习一种语言时的合理问题：

有哪些库可供重用？
有哪些工具可用？
什么能让我找到工作？
我的老板让我做什么？
什么是事实上的工业标准？
我已经知道什么？

我们的课程在设计上并不涉及这些问题

你有你的余生来处理这些问题
而技术领导者会影响答案

Week 4

头等函数(First-Class)简介

什么是函数式编程？

头等函数

函数闭包

小结

函数作为参数

函数作为参数

例子

多态类型和函数作为参数

关键点

类型

多态性和高阶函数

匿名函数

匿名函数介绍

匿名函数

使用匿名函数

不必要的函数包装

一种风格点

Map和Filter

Map

Filter

归纳总结先前的主题

归纳总结

返回函数

其他数据结构

词法作用域的定义

非常重要的概念

例子

闭包

例子

后续

词法作用域和高阶函数

该规则保持不变

例子：返回一个函数

例子：传递函数

为什么要使用词法作用域

为什么要使用词法作用域

为什么是词法作用域？

动态作用域存在吗？

闭包和重新计算

评估时发生的事

重复计算

Fold和更多闭包

另一个著名的函数：Fold

为什么又是迭代器？

fold示例

迭代器让事实变得更好

另一个闭包习语：复合函数

更多的习语

复合函数

从左到右还是从右到左

另一个例子

另一个闭包习语：Currying

Currying

例子

语法糖，第一部分

语法糖，第二部分

最终版本

Curried fold

部分应用

“参数太少”

例子

不必要的函数包装

迭代器

值限制出现了

Currying总结

更多复合函数

效率

可变的引用

ML 有（单独的）突变

引用

引用示例

另一个闭包习语：回调

回调

可变的状态

回调库实例

实现库

客户端

标准库文件