这次回顾Week2的内容，主要是Standard ML的语法介绍。

课程主页：

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

B站搬运：

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

Week 2

ML表达式和变量绑定

一个非常简单的ML程序

(* Programming Languages, Dan Grossman *)
(* Section 1: Our first ML program *)

(* val is a keyword
   x is a variable name
   = is used as a keyword here (has different meaning in expressions)
   34 is a very simple expression (and value)
   ; is used as a keyword here (has different meaning in expressions)
 *)
val x = 34;
(* static environment: x-->int *)
(* dynamic environment: x-->34 *)

val y = 17;
(* static environment: y-->int, x-->int *)
(* dynamic environment: y-->17, x-->34 *)

(* to evaluate an addition, evaluate the subexpressions and add *)
(* to evaluate a variable, lookup its value in the environment  *)

val z = (x + y) + (y + 2);
(* static environment: z-->int, y-->int, x-->int *)
(* dynamic environment: z-->70, y-->17, x-->34 *)

val q = z+1;
(* static environment: q-->int, z-->int, y-->int, x-->int *)
(* dynamic environment: q-->71, z-->70, y-->17, x-->34 *)
 
val abs_of_z = if z < 0 then 0 - z else  z;
(* static environment: abs_of_z-->int, q-->int, z-->int, y-->int, x-->int *)
(* dynamic environment: abs_of_z-->70, q-->71, z-->70, y-->17, x-->34 *)
 
val abs_of_z_simpler = abs z;

变量绑定

变量绑定的一般形式为：

val x = e;

语法：
- 关键字val和符号=
- 变量x
- 表达式e
  - 这些表达式的有许多形式，大多数包含子表达式

语义

语法是你写东西的方式
语义就是它的含义
- 类型检查（在程序运行之前）
- 评估（在程序运行时）
对于变量绑定：
- 类型检查表达式和扩展静态环境
- 评估表达式和扩展动态环境

那么精确的语法是什么，各种表达式的类型检查规则和评估规则？好问题！

ML表达式的规则（到目前为止已看到）

表达式

我们已经看到了很多种表达式：

34 true false x e1+e2 e1<e2
if e1 then e2 else e3

表达式可以任意大，因为任何子表达式都可以包含子子表达式，等等。
每种表达式都有
1. 语法
2. 类型检查规则
  - 生成类型或失败（带有错误消息)
  - 目前为止的类型：int, bool, unit
3. 评估规则（仅用于类型检查）
  - 生成值（或异常或无限循环）

变量

语法：
- 字母，数字，下划线构成的序列，不以数字开头
类型检查：
- 在当前静态环境中查找类型，如果不存在，则失败
评估：
- 在当前动态环境中查找值

加法

语法：
- e1+e2，其中e1和e2是表达式
类型检查：
- 如果e1和e2具有int类型，则e1+e2具有int类型
评估：
- 如果e1评估为v1，e2评估为v2，则e1+e2评估为v1和v2之和

值

所有值都是表达式
并非所有表达式都是值
每个值都在”零步”内”对自己进行评估”（指的是值就是其本身）
示例：
- 34, 17, 42具有类型int
- true、false具有类型bool
- ()具有类型unit

REPL和错误信息

实践学

前两部分已经建立了关键的概念基础
但你还需要一些实践学：
- 我们如何使用REPL运行程序？
- 当我们犯错时，会发生什么？
努力培养对错误的适应力
- 放慢速度
- 不要惊慌
- 仔细阅读你写的东西

use

use “foo.sml”是一个不寻常的表达式
它从文件foo.sml输入绑定信息
结果()绑定到变量it
- 可忽略

REPL

Read-Eval-Print-Loop的名称很好
可以将其视为运行程序的一种奇怪/方便的方式
- 但更方便的是快速试用
- 然后将其移到测试文件中以便于重用
在不重新启动REPL会话的情况下不要使用use，原因将在下一节中讨论
- （但在会话开始时将其用于多个文件是可以的）

错误

你的错误可能是：

语法：您编写的内容没有任何意义或不是您想要的构造
类型检查：您编写的内容没有通过类型检查
评估：程序可以运行但生成错误答案、异常或无限循环

在调试时，即使有时一种错误看起来是另一种错误，也要把错误类型搞清楚。

Shadowing

同一变量的多重绑定

同一个变量的多个变量绑定往往是糟糕的风格
- 往往令人困惑
但这是一个有启发性的练习
- 有助于解释环境如何”工作”
- 有助于解释变量绑定如何 “工作”

（现在强调这一点，为first-class function打下基础）

例子

(* Programming Languages, Dan Grossman *)
(* Section 1: Examples to Demonstrate Shadowing *)

val a = 10

val b = a * 2

val a = 5

val c = b

val d = a

val a = a + 1

(* next line does not type-check, f not in environment *)
(* val g = f - 3  *)

val f = a * 2

两个原因

变量绑定中的表达式被”急切地”评估
- 在变量绑定”完成”之前
- 之后，产生值的表达式是不相关的
在ML中没有办法”赋值给”一个变量
- 只能在以后的环境中shadow它

use

这就是为什么我如此坚持在不重启REPL的情况下不在一个文件上重复使用use的原因
否则，你就会再次引入一些相同的绑定方式
- 可能会让人觉得错误的代码是正确的
- 可能会让人觉得正确的代码是错误的
- （这一切都定义得很好，但我们会感到困惑）

函数（非正式的）

函数定义

函数：整个课程中最重要的构建块

像Java方法一样，有参数和结果
但没有类、this、return等

函数绑定示例：

(* Note: correct only if y>=0 *)
fun pow (x : int, y : int) =
	if y=0
	then 1
	else x * pow(x,y-1)

注意：正文包括一个（递归）函数调用：pow(x,y-1)

一些陷阱

有三个常见的“陷阱”•

如果弄乱了函数参数语法，则会出现错误消息
在类型语法中使用*不是乘法
- 例如：int * int->int
- 在表达式中，*是乘法：x * pow(x,y-1)
不能引用后面的函数绑定
- 这只是ML的规则
- 辅助函数必须在使用之前出现
- 需要特殊构造以实现相互递归（后续课程）

递归

如果你还不习惯递归，你很快就会习惯的
- 将用于大多数函数获取或返回列表
“有意义”，因为对同一函数的调用可以解决“更简单”的问题
递归比循环更强大
- 我们不会在ML中使用循环
- 循环往往（并非总是）掩盖了简单、优雅的解决方案

函数（正式的）

函数绑定：3个问题

语法：fun x0 (x1 : t1, … , xn : tn) = e
- (将在以后的讲座中进行概括)
评估：函数就是一个值!(但还没有评估)
- 将x0添加到环境中，以便以后的表达式可以调用它
- (函数调用语义也允许递归)
类型检查：
- 添加绑定x0 : (t1 * … * tn) -> t如果：
- 可以对主体e进行类型检查，使其在包含的静态环境中具有类型t。
  - “包围”静态环境（早期绑定）
  - x1 : t1, …, xn : tn (参数及其类型)
  - x0 : (t1 * … * tn) -> t (用于递归)

函数调用

一种新的表达方式：3个问题。

语法：e0 (e1,…,en)

（稍后将进行概括）
如果只有一个参数，则括号是可选的

类型检查：

如果
- e0有某种类型(t1 * … * tn) -> t
- e1有类型t1,...,en有类型tn
那么
- e0 (e1,...,en)的类型为t
例子：前面例子中的pow(x,y-1)的类型为int

评估：

(在当前动态环境下，)将e0评估为一个函数fun x0 (x1 : t1, ..., xn : tn) = e
- 由于调用类型检查，结果将是一个函数
(在当前动态环境下，)将参数评估为值 v1, ..., vn
结果是在一个扩展环境中评估e，将x1映射到v1, …, xn映射到vn
- (“环境”实际上是定义函数的环境，并包括x0，以便递归)

Pairs和其他元组

元组和列表

到目前为止：数字、布尔运算、条件式、变量、函数

现在介绍用多个部分建立数据的方法
这一点至关重要
Java的例子：有字段的类、数组

现在：

元组：固定的”数量”，可能有不同的类型

即将介绍：

列表：具有相同类型的任何”数量”

以后：
创建复合数据的其他更普遍的方法

pairs（两个元素的元组）

需要一种方法来建立pair，并需要一种方法来获取元素：

建立：

语法：(e1, e2)
评估：将e1评估为v1，e2评估为v2；结果为(v1,v2)
- 一对值就是一个值
类型检查：如果e1有类型ta，e2有类型tb，那么这pair表达式有类型ta * tb
- 一种新的类型

获取：

语法：#1 e和#2 e
评估：将e评估为一对值，并返回第一块或第二块
- 示例：如果e是变量x，那么在环境中查找x。
类型检查：如果e的类型为ta * tb，那么#1 e的类型为ta，#2 e的类型为tb

例子

(* Programming Languages, Dan Grossman *)
(* Section 1: Pairs and Tuples *)

(* pairs *)

fun swap (pr : int*bool) =
    (#2 pr, #1 pr)

fun sum_two_pairs (pr1 : int*int, pr2 : int*int) =
    (#1 pr1) + (#2 pr1) + (#1 pr2) + (#2 pr2)

    (* returning a pair a real pain in Java *)
fun div_mod (x : int, y : int) = 
    (x div y, x mod y)

fun sort_pair (pr : int*int) =
    if (#1 pr) < (#2 pr)
    then pr
    else (#2 pr, #1 pr)

元组

实际上，你可以有超过两部分的元组

一个新的特征：pair的泛化

示例：

(e1,e2,…,en)
ta * tb * … * tn
#1 e, #2 e, #3 e, …

作业1经常使用int*int*int类型的三元组。

嵌套

对pair和元组可以随意嵌套

不是一个新的特征：由语法和语义所暗示

(* nested pairs *)

val x1 = (7,(true,9)) (* int * (bool*int) *)

val x2 = #1 (#2 x1)  (* bool *)

val x3 = (#2 x1)      (* bool*int *)

val x4 = ((3,5),((4,8),(0,0))) (* (int * int) * ((int * int) * (int * int)) *)

列表介绍

列表

尽管有元组可以嵌套，但变量的类型仍然”承诺”一个特定的”数量”的数据
与此相反，一个列表：
- 可以有任何数量的元素
- 但所有的列表元素都有相同的类型
需要有方法来建立列表并访问这些部分…

建立列表

空列表是一个值：
```
[]
```
一般来说，值构成的列表是一个值；元素由逗号分隔：
```
[v1,v2,…,vn]
```
如果e1评估为v，e2评估为一个列表[v1,...,vn]，那么e1::e2评估为[v,...,vn]：
```
e1::e2 (* pronounced “cons” *)
```

获得列表元组

在我们学习模式匹配之前，我们将使用三个标准库函数：

当且仅当e的值为[]时，null e的值为真。
如果e的值为[v1,v2,...,vn]，那么hd e的值为v1。
- （如果e评估为[]，则引发异常）。
如果e评估为[v1,v2,...,vn]，那么tl e评估为[v2,...,vn]。
- （如果e评估为[]，则引发异常）。
- 注意到结果是一个列表。

列表操作的类型检查

大量的新类型：对于任何类型的t，类型t list描述了所有元素都具有类型t的列表
- 例子：
```
int list bool list int list list (int * int) list (int list * int) list
```
因此，[]可以有任何类型的t list
- SML使用类型'a list来表示（”quote a”或 “alpha”）。
对于e1::e2的类型检查，我们需要t，使e1具有t类型，e2具有t list类型。那么结果的类型就是t list。
null : 'a list -> bool
hd : 'a list -> 'a
tl : 'a list -> 'a list

列表函数

列表函数示例

(* Functions taking or producing lists *)

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

fun countdown (x : int) =
    if x=0
    then []
    else x :: countdown(x-1)

fun append (xs : int list, ys : int list) = (* part of the course logo :) *)
    if null xs
    then ys
    else hd(xs) :: append(tl(xs), ys)

又是递归

列表上的函数通常是递归的
- 唯一”获得所有的元素”的方法是
- 对于空列表，答案应该是什么？
- 对于非空列表，答案应该是什么？
  - 通常是以列表尾部的答案为标准!
同样地，产生可能是任何大小的列表的函数将是递归的
- 你从更小的列表中创建一个列表

pair构成的列表

(* More functions over lists, here lists of pairs of ints *)

fun sum_pair_list (xs : (int * int) list) =
    if null xs
    then 0
    else #1 (hd(xs)) + #2 (hd(xs)) + sum_pair_list(tl(xs))

fun firsts (xs : (int * int) list) =
    if null xs
    then []
    else (#1 (hd xs))::(firsts(tl xs))

fun seconds (xs : (int * int) list) =
    if null xs
    then []
    else (#2 (hd xs))::(seconds(tl xs))

fun sum_pair_list2 (xs : (int * int) list) =
    (sum_list (firsts xs)) + (sum_list (seconds xs))

Let表达式

复习

我们在ML的核心部分已经取得了巨大的进展：

类型：int bool unit t1*...*tn t list t1*...*tn->t
- 类型的”嵌套”（上面的每个t本身可以是一个复合类型）
变量、环境和基本表达式
函数
- 构建：fun x0 (x1:t1, ..., xn:tn) = e
- 使用：e0 (e1, ..., en)
元组
- 构建：(e1, ..., en)
- 使用：#1 e, #2 e, ...
列表
- 构建：[] e1::e2
- 使用：null e hd e tl e

现在

我们需要的重要工具是：局部绑定
- 为了风格和方便
这一段：
- 基本的let-expressions
接下来的一段：
- 一个很自然的想法：嵌套函数绑定
- 为了效率（不是”只是快一点”）
引入局部绑定的结构只是一个表达式，所以我们可以在表达式可以使用的任何地方使用它。

Let-表达式

3个问题：

语法：let b1 b2 … bn in e end
- 每个bi都是任何绑定，e是任何表达式
类型检查：在包含先前绑定的静态环境中对每个bi和e进行类型检查。
- 整个let表达式的类型类型e。
评估：在包含先前绑定的动态环境中评估每个bi和e。
- 整个let表达式的结果是计算e的结果。

例子

fun silly1 (z : int) =
    let val x = if z > 0 then z else 34
	    val y = x+z+9
    in
		if x > y then x*2 else y*y
    end

fun silly2 () =
    let val x = 1 
    in 
		(let val x = 2 in x+1 end) + 
		(let val y = x+2 in y+1 end)
    end

silly2的风格很差，但表明let-表达式是表达式

也可以在函数调用参数、if 分支等中使用它们。
还要注意shadowing

新的内容

新的内容是范围：绑定在环境中的位置
- 在后面的绑定和let-表达式的主体中
  - （除非后面的或嵌套的绑定shadow它）
- 只在后面的绑定和let表达式的主体中
没有其他新的内容：
- 可以放任何我们想要的绑定，甚至函数绑定
- 类型检查和评估就像在”顶层”一样

嵌套函数

任何绑定

根据我们对let-表达式的规则，我们可以在任何let-表达式内定义函数

let b1 b2 … bn in e end

这是一个很自然的想法，通常也是很好的风格。

例子

fun countup_from1 (x : int) =
    let fun count (from:int, to:int) =
	    if from=to
	    then to::[] (* note: can also write [to] *)
	    else from :: count(from+1,to)
    in
	count(1,x)
    end

这显示了如何使用本地函数绑定，但是
- 更好的版本在下一张幻灯片上
- count可能在其他地方有用

更好的例子

fun countup_from1_better (x : int) =
    let fun count (from:int) =
	    if from=x
	    then x::[]
	    else from :: count(from+1)
    in
	count 1
    end

函数可以在其定义的环境中使用绑定：
- 来自”外部”环境的绑定
  - 例如外部函数的参数
- let-表达式中的早期绑定
不必要的参数通常是不好的风格
- 就像前面的例子一样

嵌套函数：风格

在它们（指辅助函数）所帮助的函数内定义辅助函数是良好的风格，如果它们：
- 不太可能在其他地方有用
- 很可能在其他地方被误用
- 很可能在以后被修改或删除
代码设计中的一个基本权衡：重复使用代码可以节省精力和避免错误，但使重复使用的代码以后更难修改

使用Let表达式避免重复计算

避免重复递归

考虑这段代码和它的递归调用

不要担心对null、hd和tl的调用，因为它们的工作量很小。

fun bad_max (xs : int list) =
    if null xs
    then 0
    else if null (tl xs)
    then hd xs
    else if hd xs > bad_max(tl xs)
    then hd xs
    else bad_max(tl xs)
    
let x = bad_max [50,49,…,1]
let y = bad_max [1,2,…,50]

Fast vs unusable

考虑代码的如下部分以及对x, y调用的结果：

if hd xs > bad_max(tl xs)
    then hd xs
    else bad_max(tl xs)

数学从不说谎

假设一个bad_max调用的if-then-else逻辑和对hd, null, tl的调用需要$10^{-7}$秒
- 那么bad_max [50,49,...,1]需要$50 \times 10^{-7}$秒
- 而bad_max [1,2,...,50]需要$1.12 \times 10^8$秒
  - 超过3.5年
  - bad_max [1,2,...,55]需要1个多世纪。
  - 买一台更快的电脑并没有什么帮助
关键是不要做重复的工作
- 将递归结果保存在本地绑定中是至关重要的

高效的max

fun good_max (xs : int list) =
    if null xs
    then 0
    else if null (tl xs)
    then hd xs
    else
        (* for style, could also use a let-binding for (hd xs) *)
        let val tl_ans = good_max(tl xs)
        in
            if hd xs > tl_ans
            then hd xs
            else tl_ans
        end

Fast vs fast

Options

Options的动机

让max对空列表返回0真的很糟糕

可以引发一个异常（未来的主题）。
可以返回一个零元素或单元素的列表
- 这个方法可行，但是风格很差，因为对option的内置支持直接表达了这种情况

Options

对任何类型t，t option是一种类型
- (很像t list，但是是不同的类型，不是一个列表)
构建：
- NONE有类型'a option（很像[]有类型'a list）。
- SOME e有t option的选项，如果e有类型t（很像e::[]）。
访问：
- isSome有类型'a option -> bool
- valOf有类型'a option -> 'a (除了给定NONE)

例子

fun better_max (xs : int list) = 
	if null xs 
	then NONE 
	else 
		let val tl_ans = better_max(tl xs) 
		in 
			if isSome tl_ans 
				andalso valOf tl_ans > hd xs 
			then tl_ans 
			else SOME (hd xs) 
		end

val better_max = fn : int list -> int option

这样做没有什么问题，但作为一个风格问题，可能希望不要在递归中做这么多无用的”valOf“。

修改后的例子

fun better_max2 (xs : int list) =
    if null xs
    then NONE
    else let (* fine to assume argument nonempty because it is local *)
        fun max_nonempty (xs : int list) =
            if null (tl xs) (* xs better not be [] *)
            then hd xs
            else let val tl_ans = max_nonempty(tl xs)
                 in
                 if hd xs > tl_ans
                 then hd xs
                 else tl_ans
                 end
        in
            SOME (max_nonempty xs)
        end

无法告诉你是否复制了

fun sort_pair (pr : int * int) = 
	if #1 pr < #2 pr
	then pr
	else (#2 pr, #1 pr)

fun sort_pair (pr : int * int) = 
	if #1 pr < #2 pr 
	then (#1 pr, #2 pr)
	else (#2 pr, #1 pr)

在ML中，sort_pair的这两种实现是无法区分的
- 但只是因为元组是不可变的
- 第一个是更好的风格：更简单，避免了在当时的分支中制造一个新的pair
- 在具有可变复合数据的语言中，这些是不同的!

假设我们有突变(mutation)

val x = (3,4)
val y = sort_pair x

somehow mutate #1 x to hold 5

val z = #1 y

z是什么？
- 这将取决于我们如何实现sort_pair。
  - 必须仔细决定并记录sort_pair。
- 但如果没有突变，我们可以实现”两种方式”
  - 没有任何代码可以区分别名和相同的副本
  - 不需要考虑别名问题：专注于其他事情
  - 可以使用别名，这样可以节省空间，而没有危险

更好的例子

fun append (xs : int list, ys : int list) =
    if null xs
    then ys
    else hd (xs) :: append (tl(xs), ys)
val x = [2,4]
val y = [5,3,0]
val z = append(x,y)

ML中是第一种情形。

ML与命令式语言

在ML中，我们一直在创建别名而不去考虑它，因为不可能知道哪里有别名。
- 例如：tl是常数时间；不复制列表的其他部分
- 所以不要担心，专注于你的算法
在具有可变数据的语言中（如Java），程序员沉迷于别名和对象标识
- 它们必须区别开，这样后续的赋值才会影响到程序的正确部分
- 在正确的地方进行复制往往是至关重要的
  - 下一节中的可选Java示例

Java突变错误

Java安全的恶梦（不好的代码）

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();
	}
}

必须进行复制

问题：

p.getAllowedUsers()[0] = p.currentUser();
p.useTheResource();

修复：

public String[] getAllowedUsers() {
   String[] copy = new String[allowedUsers.length];
   for(int i=0; i < allowedUsers.length; i++)
      copy[i] = allowedUsers[i];
   return copy;
}

如果代码是不可变的，引用（别名）与复制并不重要。

学习一门语言的片段

五种不同的东西

语法：你如何写语言结构？
语义：程序是什么意思？(评估规则)
习语(idioms) ：使用语言特性来表达你的计算的典型模式是什么？
库：该语言（或知名项目）提供了哪些 “标准 “的设施？(例如，文件访问，数据结构)
工具：语言的实现提供什么来使你的工作更容易？(例如，REPL，调试器，代码格式化，……)
- 实际上并不是语言的一部分

这些是5个独立的问题

在实践中，所有这些问题对于优秀的程序员来说都是必不可少的
许多人把它们混为一谈，但不应该如此

我们的重点

本课程的重点是语义学和习语
- 语法法通常是无趣的
  - 一个需要学习的事实，如”美国内战在1865年结束”
  - 人们纠结于主观的偏好
- 库和工具至关重要，但经常”在工作中”学习新的工具
  - 我们正在学习语义学，以及如何使用这些知识来理解所有的软件并采用适当的习语
  - 通过避免使用大多数库/工具，我们的语言可能看起来很”傻”，但任何以这种方式使用的语言也会如此

Week 2

ML表达式和变量绑定

一个非常简单的ML程序

变量绑定

语义

ML表达式的规则（到目前为止已看到）

表达式

变量

加法

值

REPL和错误信息

实践学

use

REPL

错误

Shadowing

同一变量的多重绑定

例子

两个原因

use

函数（非正式的）

函数定义

一些陷阱

递归

函数（正式的）

函数绑定：3个问题

更多类型检查

函数调用

Pairs和其他元组

元组和列表

pairs（两个元素的元组）

例子

元组

嵌套

列表介绍

列表

建立列表

获得列表元组

列表操作的类型检查

列表函数

列表函数示例

又是递归

pair构成的列表

Let表达式

复习

现在

Let-表达式

例子

新的内容

嵌套函数

任何绑定

例子

更好的例子

嵌套函数：风格

使用Let表达式避免重复计算

避免重复递归

Fast vs unusable

数学从不说谎

高效的max

Fast vs fast

Options

Options的动机

Options

例子

修改后的例子

更多布尔表达式和比较表达式

更多的表达式

布尔操作

布尔运算的风格

比较运算符

不可变数据的一个关键好处

一个有价值的非特性：没有突变

无法告诉你是否复制了

假设我们有突变(mutation)

更好的例子

ML与命令式语言

Java突变错误

Java安全的恶梦（不好的代码）

必须进行复制

学习一门语言的片段