Programming Languages Part A Week 3笔记

这次回顾Week3的内容，主要介绍了Standard ML的模式匹配。

课程主页：

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

B站搬运：

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

Week 3

构建新类型的方法

如何构建更大的类型

• 已知：

  • 具有各种基本类型，如int bool unit char
  • 构建（嵌套）复合类型的方法：元组、列表、选项(option)

• 即将推出：

  • 构建复合类型的更多方法

• 首先：任何语言中3个最重要的类型构建块

  1. “每个”(“Each of”)：一个t值包含t1 t2 ... tn中的每个值
  2. “其中一个”(“One of”)：一个t值包含t1 t2 ... tn中的某一个值
  3. “自引用”(“Self reference”)：一个t值可以引用其他t值
  • 值得注意的是，很多数据都可以用这些构建块构件
  • 注意：这些不是这些概念的通用名称

例子

• 元组构建each-of类型
  • int * bool包含int和bool
• 选项(option)构建one-of类型
  • int option包含一个int或不包含数据
• 列表使用所有三个构建块
  • int list包含一个int和另一个int list或不包含数据
• 当然，我们可以嵌套复合类型
  • ((int * int) option * (int list list)) option

即将推出

• 另一种在ML中构建each-of类型的方法
  • 记录(Records)：有命名字段
  • 和元组的关系以及语法糖的概念
• 一种在ML中构建和使用我们自己的one-of类型的方法
  • 例如，包含int或string的类型
  • 将导致模式匹配，ML最酷、对Java程序员来说最奇怪的特性之一
• 本课程后面部分：OOP是如何实现其中one-of类型的
  • 过程式和函数式编程的关键对比

记录(Records)

记录

• 记录值有持有值的字段（任何名称）

  {f1 = v1, …, fn = vn}

• 记录类型有持有类型的字段（和名称）

  {f1 : t1, …, fn : tn}

• 记录值或类型中的字段的顺序并不重要

  • REPL按字母顺序排列字段，只是为了保持一致性

• 建立记录：

  {f1 = e1, …, fn = en}

• 访问片段：

  #myfieldname e

  (评估规则和类型检查符合预期)

例子

{name = “Amelia”, id = 41123 - 12}

评估为

{id = 41111, name = “Amelia”}

并且具有类型

{id : int, name : string}

如果一些表达式，如变量x有这种类型，那么就用如下方式得到字段：

#id x #name x

注意我们没有必要声明任何记录类型

• 同样的程序也可以使用类型为{id:bool,ego:bool}的{id=true,ego=false}

按名称与按位置

• (4,7,9)和{f=4,g=7,h=9}之间没有什么区别。

  • 元组稍短一些
  • 记录更容易记住“什么在哪里”
  • 一般来说，这是一个品味问题，但对于许多字段，记录通常是一个更好的选择

• 结构体语法的一个常见决定是，是通过位置（如元组）还是通过一些（字段）名称（如记录）来指代事物。

  • 一个常见的混合体就像Java方法参数（以及到目前为止使用的ML函数）。
    • 调用者使用位置
    • 被调用者使用变量
    • 可以采用不同的方式；有些语言可以这么做

元组作为句法糖

关于元组的真相

之前，我们给出了元组的语法、类型检查规则和评估规则，但我们可以用如下方式取代：

• 元组语法只是写某些记录的不同方式
• (e1,...,en)是表达{1=e1,...,n=en}的另一种方式
• t1*...*tn是表达{1:t1,...,n:tn}的另一种方式
• 换句话说，字段名为1、2、…的记录。

事实上，ML实际上是这样定义元组的

• 除了程序和打印中的特殊语法外，它们并不存在
• 你可以写{1=4,2=7,3=9}，但这是不好的风格

语法糖

“元组只是字段名为1、2、…n的记录的语法糖”

• 语法：可以完全通过相应的记录语法来描述语义
• 糖：它们使语言更甜

将会看到更多的语法糖的例子

• 简化了对语言的理解
• 简化了语言的实现

为什么？因为即使我们有元组的语法便利性，也很少有语义需要担心。

我们看到的其他例子：

• andalso, orelse vs. if then else

数据类型绑定

数据类型绑定

• “奇怪的”（？）而且非常棒（！）制作以下类型之一的方法：

  • 一个datatype绑定

    datatype mytype = TwoInts of int * int
    			   | Str of string 
    			   | Pizza

• 在环境中添加一个新的类型mytype

• 在环境中添加构造函数：TwoInts, Str, 和Pizza

• 构造函数是生成新类型值（或是新类型值）的函数：

  • TwoInts : int * int -> mytype
  • Str : string -> mytype
  • Pizza : mytype

我们创造的值

• 任何mytype类型的值都是由其中一个构造函数构成的
• 该值包含：
  • “哪个构造函数”的“标签”（例如，TwoInts）。
  • 相应的数据（例如(7,9)）。
• 例子：
  • TwoInts(3+4,5+4)被评估为TwoInts(7,9)
  • Str(if true then "hi" else "bye")被评估为Str("hi")
  • Pizza是一个值

使用他们

• 所以我们知道如何建立数据类型的值；下一步是需要访问它们
• 访问一个数据类型的值有两个方面
  • 检查它是什么变体（什么构造函数生成了它）
  • 提取数据（如果该变体有任何数据）
• 注意我们的one-of类型是如何使用函数来实现的
  • null和isSome检查变体
  • hd, tl, valOf提取数据（在错误的变体上引发异常）
• ML对数据类型的绑定也可以这样做
  • 例如，isStr和getStrData等函数。
  • 但是，它做得更好

Case表达式

Case

ML结合了使用case表达式和模式匹配访问one-of值的两个方面

• 模式匹配更加通用/强大（很快！）

例子：

fun f x = 
    case x of 
	    Pizza => 3 
      | Str s => 8
      | TwoInts(i1,i2) => i1 + i2

• 一个多分支的条件表达式，根据变量选择分支
• 提取数据并绑定到该分支的本地变量上
• 类型检查：所有分支必须具有相同的类型
• 评估：在case…和正确分支之间进行评估

模式

一般形式的语法是：

case e0 of 
	 p1 => e1
   | p2 => e2 
     … 
   | pn => en

对于今天来说，每个模式都是一个构造函数的名称，后面跟着正确数量的变量（即C或C x或C(x, y)）。

• 从语法上讲，大多数模式（今天所有的模式）看起来都像表达式
• 但模式不是表达式
  • 我们不对它们进行评估
  • 我们看e0的结果是否与它们匹配

为什么这种方式更好

1. 你可以使用模式匹配来编写你自己的测试和数据提取函数，如果你必须这样做的话
   • 但不要在你的作业上这样做
2. 你不能忘记一个case（不完整的模式匹配警告）
3. 你不能重复一个case（类型检查错误）
4. 你不能忘记正确地测试变体，否则可能得到一个异常（像hd []）
5. 模式匹配可以被泛化并变得更加强大，从而导致优雅和简洁的代码

有用的Datetype

有用的例子

让我们修正一下，到目前为止，我们唯一的例子数据类型是愚蠢的……

• 枚举，包括携带其他数据

  datatype suit = Club | Diamond | Heart | Spade
  datatype rank = Jack | Queen | King
  			 | Ace | Num of int

• 识别现实世界事物/人的另一种方式

  datatype id = StudentNum of int
              | Name of string
                      * (string option)
                      * string

不要这样做

不幸的是，糟糕的培训和使one-of类型不方便的语言导致了常见的不良风格，即在one-of类型是正确的工具的地方使用each-of类型：

(* use the student_num and ignore other fields unless the student_num is ~1 *)
{ student_num : int,
  first 	  : string,
  middle      : string option,
  last        : string }

• 这种方法放弃了语言的所有好处，强制每个值都是一个变体，你不会忘记分支，等等。
• 而且它使你不太清楚你在做什么

这就是说…

但如果相反，如果你代码中的每一个”人”都有名字，也许还有一个学生号，那么应该使用each-of：

{ student_num : int,
  first 	  : string,
  middle      : string option,
  last        : string }

表达式树

一个更令人兴奋的数据类型的例子，使用自引用：

datatype exp = Constant of int
             | Negate   of exp
             | Add      of exp * exp
             | Multiply of exp * exp

ML中的exp类型的表达式：

Add (Constant (10+9), Negate (Constant 4))

如何在你的脑海中描绘出结果值：

递归

这并不奇怪，递归数据类型上的函数通常是递归的：

fun eval e =
	case e of
	    Constant i 		=> i
	  | Negate e2 		=> ~ (eval e2)
      | Add(e1,e2) 		=> (eval e1) + (eval e2)
      | Multiply(e1,e2)  => (eval e1) * (eval e2)

迄今为止的模式匹配：精确

仔细的定义

当一个语言结构是”新和陌生的”，就有更多的理由来精确地定义评估规则，所以让我们回顾下”到目前为止”的数据类型绑定和case表达式（将会有一些扩展，但依然是”到目前为止”的内容）。

数据类型(Datatype)绑定

datatype t = C1 of t1 | C2 of t2 | … | Cn of tn

添加类型t和类型ti->t的构造函数Ci

• Ci v是一个值，也就是说，结果”包括标签”

省略“of t”，因为构造函数只是标签，没有底层数据

• 这样的Ci是一个类型为t的值

给定一个类型为t的表达式，使用case表达式来：

• 看看它有哪个变体（标签）
• 一旦你知道了哪个变体，就提取底层数据

case e of p1 => e1 | p2 => e2 | … | pn => en

• 像往常一样，可以在表达式的任何地方使用case表达式
  • 不需要是整个函数体，但通常是这样的
• 将e评估为一个值，称之为v
• 如果pi是第一个与v相匹配的模式，那么结果就是在”通过匹配扩展”的环境中对ei进行评估
• 模式Ci(x1,...,xn)与值Ci(v1,...,vn)相匹配，并将环境扩展为x1 to v1 ... xn to vn
  • 对于”无数据”构造函数，模式Ci匹配值Ci

另一个表达式的例子

把它们放在一起

datatype exp = Constant of int 
             | Negate of exp 
             | Add of exp * exp
             | Multiply of exp * exp

我们来定义max_constant : exp -> int。

这是一个很好的例子，我们可以在编程时将几个主题结合起来：

• Case表达式
• 本地辅助函数
• 避免重复递归
• 通过使用库函数实现更简单的解决方案

fun max_constant e =
    let fun max_of_two (e1,e2) =
	    let val m1 = max_constant e1
		val m2 = max_constant e2
	    in 
		if m1 > m2 then m1 else m2 
	    end
    in
	case e of
	    Constant i      => i
	  | Negate e2       => max_constant e2
	  | Add(e1,e2)      => max_of_two(e1,e2)
	  | Multiply(e1,e2) => max_of_two(e1,e2)
    end

val test_exp = Add (Constant 19, Negate (Constant 4))
val nineteen = max_constant test_exp

(* Note: Using Int.max, we don't need a local helper function. 
This second version is fewer lines, but there is a bit more
code copying. *)

fun max_constant2 e =
    case e of
	Constant i      => i
      | Negate e2       => max_constant2 e2
      | Add(e1,e2)      => Int.max(max_constant2 e1, max_constant2 e2)
      | Multiply(e1,e2) => Int.max(max_constant2 e1, max_constant2 e2)

类型同义词(Synonyms)

创造新类型

• 一个数据类型绑定引入了一个新的类型名称

  • 区别于所有现有的类型
  • 创建新类型的值的唯一方法是构造函数

• 一个类型同义词是一种新的绑定方式

  type aname = t

  • 只是为一个类型创建了另一个名字
  • 类型和名称在各方面都是可以互换的
  • 不要担心REPL打印的内容：选择它想要的内容，就像选择记录字段名称的顺序一样

为什么有这个？

• 现在，类型同义词只是为了方便谈论类型：

• 例子（已经定义了suit和rank）：

  type card = suit * rank

• 写一个类型的函数

  card -> bool

• 好的，如果 REPL 说你的函数的类型是

  suit * rank -> bool

• 这很方便，但并没有让我们”做”任何新的事情

• 本课程后面将看到与模块化相关的另一个用法

列表(List)和选项(Option)是数据类型

递归数据类型

数据类型绑定可以描述递归结构

• 见过算术表达式
• 现在是链表

datatype my_int_list = Empty 
                     | Cons of int * my_int_list
					 
val one_two_three = Cons(1,Cons(2,Cons(3,Empty)))

fun append_mylist (xs,ys) = 
    case xs of
        Empty => ys
      | Cons(x,xs') => Cons(x, append_mylist(xs',ys))

选项(Option)是数据类型

选项只是一种预定义的数据类型绑定

• NONE和SOME是构造函数，而不仅仅是函数。
• 所以使用模式匹配而不是isSome和valOf

fun inc_or_zero intoption =
    case intoption of
        NONE => 0
      | SOME i => i+1

列表(List)是数据类型

不需要使用hd, tl, null

• []和::也都是构造函数
• （奇怪的语法，尤其是中缀）

fun sum_list xs =
    case xs of
        [] => 0
      | x::xs' => x + sum_list xs'

fun append (xs,ys) =
    case xs of
        [] => ys
      | x::xs' => x :: append(xs',ys)

为什么要进行模式匹配

• 模式匹配对于选项和列表来说是更好的，原因与所有数据类型相同
  • 没有遗漏的情况，没有错误的变体的例外情况，等等。
• 我们只是为了教学而先学了另一种方法
  • 在作业2中不要使用isSome, valOf, null, hd, tl
• 那么为什么null, tl等是预定义的？
  • 为了作为参数传递给其他函数（下周）
  • 因为有时它们很方便
  • 但不是什么大事：可以自己定义它们

多态数据类型

完成故事

• 内置选项和列表不是必需的/特殊的
  • 除了列表构造函数的特殊语法之外
• 但这些数据类型的绑定是多态类型构造函数
  • int list和string list以及int list list都是类型，都不是list
  • 函数可能是多态的，也可能不是多态的
    • val sum_list : int list -> int
    • val append : 'a list * 'a list -> 'a list
• 好的语言设计：可以定义新的多态数据类型
• 半可选：作业2不需要了解这个

定义多态数据类型

• 语法：将一个或多个类型变量置于数据类型名称之前

  datatype 'a option = NONE | SOME of 'a
  
  datatype 'a mylist = Empty | Cons of 'a * 'a mylist
  
  datatype ('a,'b) tree = 
  			    Node of 'a * ('a,'b) tree * ('a,'b) tree
  		      | Leaf of 'b

• 可以在构造函数定义中使用这些类型变量

• 绑定然后引入一个类型构造器，而不是一个类型

  • 必须是int mylist或string mylist或'a mylist
  • 不能是mylist

其他方面没有变化

照常使用构造函数和case表达式

• 不改变评估规则
• 类型检查将确保类型的使用是一致的
  • 例如：不能混合列表的元素类型
• 函数将根据数据的使用方式而具有多态性或非多态性

each-of类型的模式匹配：函数参数的真相

一个令人兴奋的部分

• 了解一些关于”真正发生了什么”的深刻真相
  • 使用的语法糖比我们意识到的要多得多
• 每个值绑定和函数绑定都使用模式匹配
• ML中的每个函数都只需要一个参数
• 首先需要扩展我们对模式匹配的定义……

Each-of类型

• 到目前为止，我们对其中一个类型使用了模式匹配，因为我们需要一种方法来访问这些值
• 模式匹配也适用于记录和元组：
  • 模式(x1,...,xn)匹配元组值(v1,...,vn)。
  • 模式{f1=x1, ..., fn=xn}匹配记录值{f1=x1, ..., fn=xn}（并且字段可以重新排序）。

例子

这是很差的风格，有效但风格拙劣，只有一个case分支：

fun sum_triple1 (triple : int * int * int) =
    case triple of
      (x,y,z) => z + y + x

fun full_name1 (r : {first:string,middle:string,last:string}) =
    case r of 
        {first=x,middle=y,last=z} => x ^ " " ^ y ^ " " ^z

Val-binding模式

• 新功能：值绑定可以使用一个模式，而不仅仅是一个变量

  • 结果发现变量只是模式的一种，所以我们只是在第1讲中告诉了你一个半真半假的事实

    val p = e

• 对于从每个类型中获取（所有）部分是非常好的

  • 也可以只获取部分内容（这里没有显示）

• 通常情况下，把构造函数模式放在val-binding中的风格很差

  • 测试一个变体，如果有不同的变体，则引发异常（如hd, tl, valOf）

更好的例子

这是好的风格

• 尽管我们接下来会再次改进它
• 语义上与单分支case写表达式相同

fun full_name2 (r : {first:string,middle:string,last:string}) =
    let val {first=x,middle=y,last=z} = r
    in
		x ^ " " ^ y ^ " " ^z
    end

fun sum_triple2 triple =
    let val (x,y,z) = triple 
    in 
        x + y + z 
    end

函数——参数模式

函数参数也可以是一个模式，针对函数调用中的参数进行匹配：

fun f p = e

例子（很好的风格！）：

fun full_name3 {first=x,middle=y,last=z} =
    x ^ " " ^ y ^ " " ^z

fun sum_triple3 (x,y,z) =
    x + y + z

一种新的方式

• 对于作业2。
  • 不要使用#字符
  • 不需要写下任何明确的类型

其他

一个函数，它接收一个int*int*int类型的，并返回一个int，即它们的总和：

fun sum_triple3 (x,y,z) =
    x + y + z

一个接收三个int参数并返回一个int作为其总和的函数:

fun sum_triple3 (x,y,z) =
    x + y + z

看到区别了吗？(我也没有。)

关于函数的真相

• 在ML中，每个函数都只需要一个参数（*）

  • “零参数”是指单位模式()与单位值()相匹配

• 我们所称的多参数函数只是需要一个元组参数的函数，在函数绑定中用元组模式来实现

• 优雅而灵活的语言设计

• 实现了在Java中无法做到的可爱而有用的事情，例如：

  fun rotate_left (x, y, z) = (y, z, x)
  fun rotate_right t = rotate_left(rotate_left t)

一些类型推理

一种新的方式

• 对于家庭作业2

  • 不要使用#字符
  • 不需要写下任何明确的类型

• 这些都是相关的

  • 类型检查器可以使用模式来计算出类型
  • 只用#foo或#1，它不能确定”其他什么字段”

为什么没有问题

便于类型检查器确定函数类型：

fun sum_triple1 (x, y, z) =
    x + y + z

fun full_name1 {first=x, middle=y, last=z} =
    x ^ " " ^ y ^ " " ^ z

在没有明确类型注释的情况下获得错误信息：

(* these versions will not type-check without type annotations because
   the type-checker cannot figure out if there might be other fields *)
fun sum_triple2 (triple : int*int*int) =
	   #1 triple + #2 triple + #3 triple

fun full_name2 (r : {first:string, middle:string,
                    last:string}) =
      #first r ^ " " ^ #middle r ^ " " ^ #last r

意外的多态性

• 有时类型检查器”比你预期的更聪明”

  • 某些部分的类型可能比你想象的要少

  • 例如：如果你不使用某个东西，那么它可以有任何类型

    (* these functions are polymorphic: type of y can be anything *)
    
    fun partial_sum (x, y, z) = 
        x + z
    
    fun partial_name {first=x, middle=y, last=z} =
        x ^ " " ^ z

• 这没什么问题！

  • 比你需要的更通用的类型总是可以接受的
  • 当然，前提是你的函数是正确的
  • 下一段对”更通用类型”有更精确的定义

多态类型和相等类型

例子

• “写一个函数，将两个字符串列表相加”

  fun append (xs,ys) =
     case xs of
         [] => ys
       | x::xs' => x :: append(xs',ys)

• 你期望string list * string list -> string list

• 实现是'a list * 'a list -> 'a list

• 这没什么问题：为什么？

更一般

类型

'a list * 'a list -> 'a list

比以下类型更一般

string list * string list -> string list

• 它”可以被用作”任何不太通用的类型，例如

  int list * int list -> int list

• 但它并不比以下类型更通用

  int list * string list -> int list

“更一般”的规则

你（和类型检查器）可以不假思索地应用的简单规则：

一个类型t1比类型t2更通用，如果你能把t1，一致地替换其类型变量，并得到t2。

• 例子：用int * int替换每个'a。
• 例子：用bool替换每个'a，用bool替换每个'b。
• 例子：用bool替换每个'a，用int替换每个'b。
• 例子：用'a替换每个'b，用'a替换每个'a。

其他规则

• 可以将”更一般”的规则与等价的规则结合起来
  • 类型同义词的使用并不重要
  • 字段名的顺序并不重要

例子，给定

type foo = int * int

类型

{quux : 'b, bar : int * 'a, baz : 'b}

比如下更加普遍

{quux : string, bar : foo, baz : string}

这等价于

{bar : int*int, baz : string, quux : string}

相等类型

• 你也可能看到带有第二个”引号”的类型变量
  • 例如：''a list * ''a -> bool
• 这些是使用 = 运算符产生的”相等类型”。
  • = 运算符适用于很多类型：int、string、tuples包含所有相等类型，…
  • 但不是所有的类型：函数类型、real，…
• 更一般的规则是完全一样的，除了你必须用可与=一起使用的类型来替换相等类型变量
  • ML的一个”奇怪”的特征，因为=是特殊的

例子

(* has type ''a * ''a -> string *)
fun same_thing(x,y) = if x=y then "yes" else "no" 

(* has type int -> string *)
fun is_three x = if x=3 then "yes" else "no" 

嵌套模式

嵌套模式

• 我们可以随心所欲地嵌套模式
  • 就像我们可以随心所欲地嵌套表达式一样
  • 通常可以避免难于阅读、字数繁多的嵌套case表达式
• 所以模式匹配的全部含义是将模式与”相同形状”的值进行比较，并将变量绑定到”正确的部分”
  • 更加精确的递归定义将在例子之后出现

有用的例子：zip/unzip 3 lists

(* do this *)
fun zip3 list_triple =
    case list_triple of 
	([],[],[]) => []
      | (hd1::tl1,hd2::tl2,hd3::tl3) => (hd1,hd2,hd3)::zip3(tl1,tl2,tl3)
      | _ => raise ListLengthMismatch

(* and the inverse *)
fun unzip3 lst =
    case lst of
	[] => ([],[],[])
      | (a,b,c)::tl => let val (l1,l2,l3) = unzip3 tl
		       in
			   	(a::l1,b::l2,c::l3)
		       end

更多嵌套模式

风格

• 嵌套模式可以带来非常优雅、简洁的代码
  • 如果嵌套模式更简单，则避免嵌套的case表达式，并避免不必要的分支或let表达式
    • 例如：unzip3和nondecrease
  • 一个常见的习惯是针对一个数据类型的元组进行匹配，以比较它们
    • 例子：zip3和multsign
• 通配符是很好的风格：当你不需要数据时，用它们代替变量。
  • 例子：len和multsign

精确嵌套模式

(大部分的）完整定义

模式匹配的语义需要一个模式p和一个值v，并决定

• (1)它是否匹配，
• (2)如果匹配，将引入什么变量绑定。

由于模式可以嵌套，该定义是优雅的递归，每一种模式都有单独的规则。其中一些规则是：

• 如果p是变量x，则匹配成功，x被绑定到v
• 如果p是_，则匹配成功，不引入绑定
• 如果p是(p1,...,pn)，v是(v1,...,vn)，当且仅当p1匹配v1，…，pn匹配vn时，匹配成功。绑定是来自子匹配的所有绑定的结合体
• 如果p是C p1，如果v是C v1（即同一个构造函数）并且p1匹配v1，则匹配成功。
• （还有其他几种类似的模式形式）

例子

• 模式a::b::c::d匹配所有>=3个元素的列表
• 模式a::b::c:[]匹配所有有3个元素的列表
• 模式((a,b),(c,d))::e匹配所有非空的成对pair的列表

可选：函数模式

更多的模式匹配

datatype exp = Constant of int 
             | Negate of exp 
             | Add of exp * exp
             | Multiply of exp * exp

fun old_eval e =
    case e of
        Constant i => i
      | Negate e2  => ~ (old_eval e2)
      | Add(e1,e2) => (old_eval e1) + (old_eval e2)
      | Multiply(e1,e2) => (old_eval e1) * (old_eval e2)

可以改写为

fun eval (Constant i) = i
  | eval (Negate e2) = ~ (eval e2)
  | eval (Add(e1,e2)) = (eval e1) + (eval e2)
  | eval (Multiply(e1,e2)) = (eval e1) * (eval e2)

fun append ([],ys) = ys
  | append (x::xs',ys) = x :: append(xs',ys)

没有比这更强大的了

一般的

fun f e =
	case x of
	  p1 => e1
	| p2 => e2
	...

可以写成

fun f p1 = e1
  | f p2 = e2
 ...
  | f pn = en

如果您愿意（假设x未在任何分支中使用）。

异常

异常

异常绑定引入了一种新的异常类型

exception MyFirstException
exception MySecondException of int * int

raise原语会引发（又称抛出）一个异常。

raise MyFirstException
raise (MySecondException(7,9))

一个handle表达式可以处理（又称捕获）一个异常

• 如果不匹配，异常继续传播

e1 handle MyFirstException => e2
e1 handle MySecondException(x,y) => e2

实际上

异常很像数据类型的构造函数…

• 声明一个异常会增加一个exn类型的构造函数
• 可以在任何地方传递exn的值（例如，函数参数）。
  • 这样做并不常见，但可能很有用
• handle可以有多个分支，并有exn类型的模式

尾递归

递归

现在应该能适应递归了。

• 不比使用循环更难
• 通常比循环容易得多
  • 当处理树时（例如，评估一个算术表达式）
  • 像追加列表的例子
  • 即使对局部变量也避免了突变
• 现在：
  • 如何推理递归的效率
  • 尾递归的重要性
  • 使用累加器来实现尾递归
  • [这里没有新的语言特征]

调用堆栈

当一个程序运行时，有一个已经开始但尚未返回的函数调用堆栈

• 调用函数f会将f的实例push到栈上
• 当对f的调用结束时，它(f的实例)从栈中弹出

这些堆栈框架存储了一些信息，如局部变量的值和函数中的”剩余工作”。

由于递归的原因，多个栈帧可能是对同一个函数的调用。

例子

fun fact n = if n=0 then 1 else n*fact(n-1)
val x = fact 3

修订后的例子

仍然是递归，更复杂，但递归调用的结果是调用者的结果（没有剩余的乘法）。

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

调用栈

一个优化

没有必要为了得到一个被调用者的结果而保留一个栈帧，并在没有任何进一步评估的情况下返回它。ML在编译器中识别了这些尾部调用，并对它们进行了不同的处理。

• 在调用前弹出调用者，允许被调用者重新使用相同的堆栈空间
• （与其他优化一起，）与循环一样高效

有理由认为所有函数式语言的实现都会进行尾部调用优化

实际发生的

累加器(Accumulators)

尾递归的寓意

• 在合理优雅、可行和重要的情况下，将函数重写为尾递归会更有效率
  • 尾递归：递归调用是尾部调用
• 有一种方法可以经常指导这种转换
  • 创建一个接收累加器的辅助函数
  • 旧的基本情况为初始累加器
  • 新的基本情况为最终累加器

例1

fun sum1 xs =
    case xs of
        [] => 0
      | i::xs' => i + sum1 xs'

fun sum2 xs =
    let fun f (xs,acc) =
            case xs of
                [] => acc
              | i::xs' => f(xs',i+acc)
    in
        f(xs,0)
    end

例2

fun rev1 xs =
   case xs of
       [] => []
     | x::xs' => (rev1 xs') @ [x]

fun rev2 xs =
    let fun aux(xs,acc) =
            case xs of
                [] => acc
              | x::xs' => aux(xs', x::acc)
    in
        aux(xs,[])
    end

分析

• 对于fact和sum，尾递归更快，但两种方式都是线性时间
• 非尾递归rev是二次时间复杂度，因为每次递归调用都使用append，它必须遍历第一个列表
  • 而1+2+…+(length-1)几乎是length*length/2。
  • 道理：小心列表追加，特别是在外部递归中。
• 尾递归优点是恒定时间（和快速），所以累加器版本更好。

尾递归：视角和定义

总是尾递归？

• 当然，在某些情况下，递归函数不能在恒定的空间内进行计算
• 最明显的例子是处理树的函数
• 在这些情况下，自然递归的方法才是正确的选择
  • 你可以让一个递归调用成为一个尾部调用，但很少值得这样复杂化
• 要小心过早优化
  • 喜欢清晰、简明的代码
  • 但如果输入可能很大，则要减少空间的使用

什么是尾部调用

• 通常”没有什么留给调用者做”的直觉就足够了
  • 如果f x的结果是包围函数体的”直接结果”，那么f x就是一个尾部调用
• 但我们可以递归地定义”尾部位置”
  • 那么”尾部调用”就是”尾部位置”的函数调用

精确的定义

尾部调用是指在尾部位置的函数调用：

• 如果一个表达式不在尾部位置，那么就没有子表达式在尾部位置
• 在fun f p = e中，主体e在尾部位置
• 如果if e1 then e2 else e3在尾部位置，那么e2和e3都在尾部位置（但e1不在）
  • (对于case表达式也类似）
• 如果let b1 ... bn in e end在尾部位置，那么e就在尾部位置（但没有绑定表达式在尾部位置）
• 函数调用参数e1 e2不在尾部位置