SML学习笔记03-函数

参考：CMU 15-150 Lecture02

1 函数的应用

1.1 函数的类型检查

一个 lambda 表达式 (fn (x:int) => body) : t1 -> t2 其类型是 \(t1\rightarrow t2\) 当 body : t2 且 x : t1

注意：

  参数 \(x\) 的类型很重要，不能被省略

  举个例子：若函数体 body 为 x + 9 ，则仅当 \(x\) 的类型确定时：x : int，函数体 body 才能具有一个合规的类型，从而整个 lambda 表达式才能有类型 int -> int

例：

• (fn (x:int) => x) : int -> int
• (fn (x:real) => x) : real -> real

如果e2 e1 : t2 仅当 e2 : t1 -> t2 且 e1 : t1

此处 e2 可看作一函数，e1 可看作函数 e2 的一个参数

现已知一计算面积的函数 area，如：area(2.1 + 1.9)，则 area : real -> real

为何有area : real -> real？

因为 area 是一个 lambda 表达式 fn (r:real) => pi*r*r 且 pi*r*r : real

  为何 pi*r*r : real？

  因为：pi:real 且 r:real

1.2 求值规则

e2 e1的求值规则，分为以下四步：

1. 将 e2 化简为一个（函数）值
2. 将 e1 化简为一个值 v
3. 将第二步中新产生的绑定 [v/x] 添加到环境 env 中
4. 利用现存环境 env 中的一系列绑定去带值求解函数体 body

回忆学习笔记02：

  一个闭包（closure）包含了一个 lambda 表达式 (fn (x:t) => body) 以及一个环境 env

  而一个环境 env 由该函数在定义时其自由变量的绑定所组成

注意：

  第二步会出现仅当第一步能产生一个值

  第三步和第四步会出现仅当第一第二步能产生值

  第四步或许会产生一个值，但也可能不会产生一个值

具体来说，例：

 求 area (2.1 + 1.9)

  \(\Rightarrow\) [3.14159/pi](fn (r:real) => pi*r*r) (2.1 + 1.9)

  \(\Rightarrow\) [3.14159/pi](fn (r:real) => pi*r*r) 4.0

  \(\Rightarrow\) [3.14159/pi][4.0/r]pi*r*r

  \(\Rightarrow\) 50.26544

一个问题：

  val pi : real = 3.14159

  fun area (r:real) : real = pi*r*r

  area (2.1 + 1.9) \(\hookrightarrow\) 50.26544

  val pi : real = 0.0

  area (2.1 + 1.9) \(\hookrightarrow\) ????????

答案仍然是 50.26544

为什么？

  因为当函数 area 被定义时，pi 就已经和值 3.14159 绑定了（上述 “回忆学习笔记02” 已阐述过函数定义及其绑定间的关系），后续不会再被更改

2 递归

让我们从一个简单的阶乘函数来入手递归：

在数学中，阶乘函数定义为：

  \(fact(0)=1\)

  \(fact(n)=n*(fact(n-1)),\ for\ all\ n>0\)

我们也可以用 \(n!\) 这一缩写记号来代表 \(fact(n)\)

而数学中的这一阶乘函数在 SML 语言中将被写作：

fun fact(0:int):int = 1
  |	fact(n:int):int = n * (fact(n-1))

则 fact 6 = 720

 fact 0 = 1

3 模式

3.1 函数子句与模式匹配

fun fact(0:int):int = 1
  |	fact(n:int):int = n * (fact(n-1))

上述代码中有两个函数子句：

• 第一个子句以 fun 为开头
• 第二个子句以逻辑符号 “或” | 为开头

在这之后，每条子句都遵循此格式：fact pattern = expression

当 SML 语言对形如 fact(value) 的表达式进行求值时，SML 会尝试将 value 按顺序与每一个 pattern 进行匹配

• 如果匹配成功，只要 pattern 中包含变量，SML 就会创建一个变量绑定，并且对相应表达式进行求值

例：

• 对于 fact(0) 来说，0 会与第一个 pattern 相匹配，于是 SML 求值为 1
• 对于 fact(3) 来说，3 会与第二个 pattern 相匹配，并且 SML 会创建一个值绑定：[3/n] ，然后再接着去对表达式 n*fact(n-1) 求值

3.2 更一般的形式

fun f p1 = e1
  | f p2 = e2
  ...........
  | f pk = ek

每一个 pj 都是一个 pattern，且每一个 ej 都是一个表达式

注意：

  如果 f : t -> t' ，则每一个 pattern pj 都必须属于类型 t，且每一个表达式 ej 都必须属于类型 t'

当对 f(v) 进行求值时，SML 会尝试将 v 与 p1 , p2 , ... ... , pk 进行匹配，直到遇到与 v 相匹配的 pj ，此时便停止匹配。同时对 pj 相应的表达式 ej 进行求值

如果没有 pattern 与 v 匹配，则会引发出一个 至关重要的“运行时错误”，处于这个原因，pattern 的集合 {pj} 应当覆盖所有可能的情况。

• 如果你给出的 pattern 集合 {pj} 没有覆盖完所有的情况，SML 会给出一个 Warning: match nonexhaustive

• 但当你给出的 pattern 集合 {pj} 中出现了重复或者多余的元素，则 SML 会给出一个 Error: match redundant

3.2 什么是 pattern ？

目前（以后我们会看到更多的情况），一个 pattern 可以是以下几种情况之一：

1. 一个常量：如：3 , true , "abc"
2. 一个变量
3. 子 pattern 的一个元组
4. 一个通配符 _（意为可以匹配任何东西）

patterns 必须是 线性的，这意味着任何变量在任何一个 pattern 中最多只能出现一次

4 元组

4.1 类型patterns可以出现在声明中

例：

val (k,r) : (int * real) = (2 , 3.14)

  此处的 pattern 是一个元组：(k,r)，由一对变量组成（子patterns是两个变量）

  这一行声明在环境 env 中创造了两个绑定：[2/k, 3.14/r]

例：

val 49 : int = square(7)

  此处的 pattern 是一个常量：49

  这里的声明没有包含任何一个变量。它会成功仅当 square 返回一个值 49

  所以，此处的声明更多的意义是在于对函数 square 的测试

例：（元组 pattern 在函数中的应用）

fun fibb (0:int) : int * int = (1 , 0)
  | fibb n =
      let
         val (a:int, b:int) = fibb(n-1)
      in
         (a+b, a)
      end;
val (21, 13) = fibb 7;

5 case表达式

5.1 类型pattern出现在case表达式中

(case e of
     p1 => e1
   | p2 => e2
   ..........
   | pk => ek)

• case表达式的语义样式和函数非常相像（e 可看作作函数中的参数）

• 类型检查：

    设表达式 e 类型为 t'，则所有的 pj 必须能够与类型 t' 相匹配

    所有表达式 ej 的类型必须一致，我们姑且称其类型为 t

    则类型 t 就是 case 表达式整体的类型

    图例：

• SML 会对 e 求值，如果 e 能化简成值 v，则 SML 会将值 v 与 p1 , p2 , ... ... , pk相匹配。如果第一个匹配到的 pattern 是 pj，则 SML 就对 pj 后对应的表达式 ej 求值

5.2 case 表达式是一种避免 if-then-else 结构的一种很好的代替方案

fun select (x:int) =
      (case (square x, x > 0) of
         (1, true)  => 0
       | (_, false) => x
       | (sqr, _)   => sqr);

注意：

  (square x, x > 0) 中的 x > 0 并不是在强调 square x 中 x 的范围。而是二元组 (square x, x > 0) 中的第二个元素（square x 为二元组中的第一个元素）

  最后一行的 sqr 是一个普通的变量名，指代 case 后所跟二元组 (square x, x > 0) 的第一个元素：square x

  最后两行中出现的 _ 意为通配符，任何参数都能与之成功匹配

所以，我们可以得到：

 0 = select  1
~1 = select ~1
25 = select  5

6 函数是一类成员（值）

6.1 函数可以作为参数被使用

函数能否被当作参数使用是函数式编程语言的一个重要特征

例：

fun sqrf (f : int -> int, x : int) : int = square(f(x))

注意：

  sqrf 的参数是一个由函数和 int 类型值组成的二元组，即 ((int -> int) * int)

那么该如何调用 sqrf 函数呢？

  这就需要用到内联 lambda 表达式来构造匿名函数的方式去充当参数：

  sqrf (fn (n:int) => n+2, 4);

一道例题：

fun dotwice (f : int -> int, x : int) : int = 
	sqrf (fn (n:int) => sqrf(f,n), x);
求：dotwice (fn (k:int) => k, 3) = ??????

解：

  dotwice (fn (k:int) => k, 3)

  = sqrf (fn(n:int) => sqrf(k->k,n), 3)

  sqrf(k->k, n)

  = n*n

所以：

  dotwice (fn (k:int) => k, 3)

  = sqrf (fn(n:int) => sqrf(k->k,n), 3)

  = sqrf (fn(n:int) => n*n, 3)

  = square(9)

  = 81

所以：

  81 = dotwice (fn (k:int) => k, 3)

7 一些补充

7.1 关于扩展等价的一些补充

• 如果 \(e_1\hookrightarrow v\) 且 \(e_2\hookrightarrow v\) （ \(v\) 是一个值），则\(e_1\cong e_2\)
• 如果 \(e_1\Rightarrow e_2\) ，则 \(e_1\cong e_2\)
• 如果 \(e_1\Rightarrow e\) 且 \(e_2\Rightarrow e\) ，则 \(e_1\cong e_2\)
• 注意：\(e_1\cong e_2\) 并不意味着 \(e_1\Rightarrow e_2\) 或者 \(e_2\Rightarrow e_1\)

例：

  \(1+1+1+7\) \(vs\) \(2\times 5\)

  纵使 \((1+1+1+7)\cong (2\times 5)\) 但是这并不意味着 \((1+1+1+7)\Rightarrow (2\times 5)\) 或者 \((2\times 5)\Rightarrow (1+1+1+7)\)

  因为 \(\Rightarrow\) 意味着 “化简” 。而虽然上述二者都相等，但是它们却无法化简到对方的形态

• [3/y, 5/z] (fn(x:int)=>x+y+z) \(\cong\) (fn(x:int)=>x+8)

两函数虽然扩展等价，但是两函数并不相同，不能画等号

因为：在第一个函数中，\(y+z\) 的计算只有在函数被调用时才会被执行（其余的时刻 \(y+z\) 并不会被计算），所以严格来讲，\(y+z\neq 8\)，意即两个函数不能严格画等号

7.2 关于完全性的一些补充

假设 f: int -> int

• 如果 f 是完全的，则 f(1)+f(2) \(\cong\) f(2)+f(1)
• 如果 f 不一定是完全的，则 f(1)+f(2) \(\ncong\) f(2)+f(1)