Progamming Languages 第一部分笔记

发表于 2019-02-06 分类于编程与算法，课程笔记阅读次数：本文字数： 3.1k 阅读时长 ≈ 10 分钟

本篇博客为 coursera programming languages 课程的第一部分学习笔记。

ML 表达式与变量绑定

一个 ML 程序由一系列的绑定（bindings）组成
- 每个绑定会先进行类型检查，再进行分析
  - 类型检查在静态环境中完成
  - 绑定的分析在动态环境中完成
绑定有很多种，这里先介绍最常见的变量绑定，其语法如下：
val x = e;
- val 是一个关键字，x 可以是任意变量，e 可以是任意表达式
  - 分号在文件中可以省略，在交互终端（REPL）中不能省略
- 类型检查：将x 的类型设为 t 其中 t 是表达式 e 的类型
- 分析：将x 的值设为 v 其中 v 是表达式 e 的分析结果
值是一种无法进一步进行计算（简化）的表达式
- 所有的值都是表达式，但并非所有的表达式都是值
ML 中常见的表达式包括：
- 整型常量
  - 语法：一个数字序列
  - 类型检查：在任意静态环境中均为 int
  - 分析：在任意动态环境中均为其自身（是一个值）
- 四则运算（以加法为例）
  - 语法：e1 + e2 其中 e1 和 e2 是表达式
  - 类型检查：当且仅当 e1 和 e2 在同一静态环境中均为 int 时，该表达式类型为 int，否则类型检查不通过（实际上同为 real 类型也可以）
  - 分析：在同一动态环境中将 e1 分析为 v1，将 e2 分析为 v2，则整个表达式的值为 v1+v2
- 变量
  - 语法：一个字母或下划线等组成的序列
  - 类型检查：寻找在当前静态环境中该变量的类型并使用该类型
  - 分析：寻找在当前动态环境中该变量的值并使用该值
- 条件式
  - 语法：if e1 then e2 else e3 其中 e1、e2、e3 均为表达式
  - 类型检查：在当前静态环境下，当且仅当 e1 为 bool 类型且 e2 和 e3 为同一类型时类型检查才通过，此时表达式的类型为 e2 和 e3 的类型
  - 分析：在当前动态环境下，如果 e1 为 true，则表达式的值为 e2 的值，否则为 e3 的值
- 布尔常量
  - 语法：true 或 false
  - 类型检查：在任意静态环境中均为 bool
  - 分析：在任意动态环境中均为其自身（是一个值）
- 比较式（以小于为例）
  - 语法：e1 < e2 其中 e1 和 e2 是表达式
  - 类型检查：当且仅当 e1 和 e2 在同一静态环境中均为 int 时，该表达式类型为 bool，否则类型检查不通过
  - 分析：在同一动态环境中将 e1 分析为 v1，将 e2 分析为 v2，如果 v1 小于 v2，则整个表达式的值为 true，否则为 false

变量的不可变性

在 ML 中，绑定是不可变的
- 对于一个变量，如果你在第一次绑定之后又重新进行绑定，则其只是在第二次绑定后的动态环境中投影（shadows）了原来的值，并不会对第一次绑定时的结果造成影响

使用 use

在使用 REPL 时，我们可以通过 use 语句将文件中的所有绑定一次性导入：
use "foo.sml";
- 该语句的输出类型为 unit，结果为 ()

函数绑定

函数是一种调用参数并通过函数体产生结果的代码块
ML 中的函数没有类（class）的概念，也不存在返回语句

下面给出一个计算幂次的简单函数：

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

语法

函数绑定的语法如下：
fun x0 (x1 : t1, ..., xn : tn) = e
- 函数名为 x0
- 其接收 n 个参数 x1, ..., xn ，其类型对应为 t1, ..., tn
- 其函数体为表达式 e

类型检查

函数的类型为“参数类型” -> “结果类型”
- 对于 x0，其类型为 t1 * ... * tn -> t
- 表达式 e 的类型 t 由 ML 自动推理得出
参数并没有添加到顶层的静态环境中，只能在函数体中使用

分析

ML 将函数简单地分析为一个值
- 将该函数添加到动态环境中，方便之后调用

函数调用

函数调用是一种新的表达式
语法： e0 (e1, ..., en)
类型检查：
- e0 的类型为 t1*...*tn->t
- 对于 1 ≤ i ≤ n, ei 的类型为 ti
- 则整个函数调用的类型为 t
分析：
- 使用进行调用时的动态环境将 e0 分析为 v0, e1 分析为 v1，以此类推
  - v0 一定是一个函数
- 然后我们将这些参数代入到函数体中进行计算，得出最终的结果
  - 注意此时的动态环境为函数定义时的环境，而非调用的环境

Pairs 和 Tuples

编程语言需要基于简单数据构造复合数据的方法
- 本节将介绍 pairs 和 tuples 这两种构建方法

Pairs

语法：(e1, e2)
类型检查：pair 的类型为 t1 * t2
- t1 是 e1 的类型
- t2 是 e2 的类型
分析：pair 的取值为 (v1, v2)
- v1 是 e1 的值
- t2 是 e2 的值
使用 #1 和 #2 来获取 pair 的第一部分与第二部分
- 如果 e 的类型 ta * tb
- 则 #1 e 的类型为 ta 且 #2 e 的类型为 tb

应用举例：

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

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

Tuples

tuples 可以理解为 pairs 的扩展，其支持任意数量的部件
- 3-tuple 举例： (7, 9, 11)
  - 其类型为 int * int * int
  - 可以通过 #1 e、 #2 e 和 #3 e 来获取部件
tuples 和 pairs 可以任意嵌套，组成更加复杂的数据结构
- 举例：(7, (true, 9))

Lists

pairs 和 tuples 的长度需要提前确定，下面介绍另一种长度可变的数据类型 lists
- lists 的长度不固定，但其中所有元素需保持同一类型
lists 可以分为两类：空 list 和非空 list

空 list

语法： [ ]
类型检查：’a list
- 这表明其可以为任意类型的 list
分析：空 list 本身是一个值

非空 list

语法： [e1, e2, ..., en]
类型检查：当所有的元素均为类型 t 时，list 的类型为 t list
分析：list 的值为 [v1, v2, ..., vn]
通常我们使用 e1 :: e2 来创建一个 list
- e1 是一个类型为 t 的元素
- e2 是一个元素类型为 t 的 list

内置函数

目前我们将使用 ML 内置的以下三种函数来操作 lists：
- null 函数：空 list 为 true，非空 list 为 false
- hd 返回 lists 的第一个元素，如果为空则抛出异常
- tl 返回 lists 除第一个元素之外的剩余部分（仍然是 list ），如果为空则抛出异常

应用举例

fun append (xs : int list, ys : int list) = 
    if null xs 
    then ys 
    else (hd xs) :: append(tl xs, ys)
        
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)

一般使用 lists 的函数通常都是递归的
写递归函数的两个步骤：
- 先考虑基线情况（base case）
- 然后写递归（recursive case）
我们可以将 pairs 或 tuples 和 lists 随意结合在一起

Let 表达式

let 表达式是 ML 的一个重要特性
- 其能够提供简单灵活的局部绑定
- 可以放置在任何能够放置表达式的地方
let 表达式的形式如下：
let b1 b2 ... bn in e end
- 语法：每个 bi 都是一个绑定，e 是一个表达式
- let 表达式中的一个绑定的作用范围是：
  - 该绑定之后的所有绑定
  - let 表达式的本体（body）
- 类型检查：e 的类型即为整个 let 表达式的类型
- 分析：e 的值即为整个 let 表达式的值

应用举例

let 表达式也可以绑定函数：

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

在这个局部函数中，使用了函数体外的变量 x
这是函数式编程的一个重要特性（函数闭包）

let 表达式可以避免重复的运算

下面的例子用于获得一个 int list 中的最大值

fun bad_max (xs : int list) =
    if null xs 
    then 0 (* note: bad style; see below *) 
    else if null (tl xs) 
    then hd xs 
    else if hd xs > bad_max(tl xs) 
    then hd xs 
    else bad_max(tl xs)

bad_max 函数在一次递归中被调用了两次，导致计算复杂度指数增加

如果采用了 let 表达式，计算复杂度会大大下降

fun good_max (xs : int list) =
    if null xs 
    then 0 (* note: bad style; see below *) 
    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

Options

上面的例子在 list 为空时返回了 0，这并不优雅
- 我们希望返回一个值，表明该 list 为空因此没有最大值
- ML 提供了 options 来做到这一点
一个 option 有两种可能的取值：NONE 或 SOME e
- NONE 表示该 option 没有携带任何值
  - NONE 的类型为 ’a option
- SOME e 表示该 option 携带了一个表达式 e，该表达式的值 v 即为 option 的值
  - SOME e 的类型为 t option，其中 t 为 e 的类型
我们使用 isSome 和 valOf 来处理 options
- 如果 option 为 NONE，则 isSome 为 false
- valOf 获取 SOME e 的值（NONE 则抛出异常）

基于 options，我们可以对之前的例子进行进一步改写：

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 must 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

其他表达式与操作符

e1 andalso e2 是逻辑与
- e1 和 e2 的类型为 bool（下同）
e1 orelse e2 是逻辑或
not e 是逻辑非
e1 = e2 判断两个表达式是否相等
e1 <> e2 判断两个表达式是否不同
其他比较运算符包括：>, <, >=, <=
- real 和 int 类型不能混合比较
~e 表示负数

不可变性的好处

在 ML 中，我们没有方法去改变任何绑定、tuple 或 list 等的内容
- 例如一个变量 x 绑定为 [(3,4),(7,9)]
  - 我们可以为 x 绑定一个新的值，但这仅仅是投影，不会对任何引用了原来 x 的代码产生影响
  - 我们无法去改变 list 或 tuple 中的任何部分，只能进行构建与查询
数据的不可变性是函数式编程的主要贡献

共享与别名

具体来说，不可变性的一大好处就是让共享（sharing）与别名（aliasing）互不相关
下面以一个例子来说明：
fun append (xs : int list, ys : int list) =
if null xs
then ys
else (hd xs) :: append(tl xs, ys)
- 在上面的例子中，返回的 list 是否共享了参数中的元素？
  - 在 ML 中，这是无法得知的（实际上发生了），也是无关紧要的，因为所有的数据都是不可变的
  - 而对于可变数据的语言来说，如果发生了共享，即发生了别名现象，那么对于某个变量的改动可能会引起别的变量的改变，这会导致难以查明的 bug

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

在上面的例子中，getAllowedUsers 会返回一个 allowedUsers 的别名，我们可以随意修改允许用户的名单
- 数组变量是引用类型变量，即使本身是 private，但其中元素可以修改
在 Java 中，我们需要经常对数据进行拷贝，防止别名的出现

编程语言的部件

一般来说，任何编程语言的定义与学习都应该包含如下组成部分：
- 语法（Syntax）：如何正确地编写代码
- 语义（Semantics）：如何理解代码（例如表达式的值如何分析）
- 习语（Idioms）：可以理解为代码模式(惯用代码，例如 let 表达式)
- 库（Libraries）：可以直接复用的代码
- 工具（Tools）：操作程序的工具（编译器、调试器等）

ML 表达式与变量绑定

变量的不可变性

使用 use

函数绑定

语法

类型检查

分析

函数调用

Pairs 和 Tuples

Pairs

Tuples

Lists

空 list

非空 list

内置函数

应用举例

Let 表达式

应用举例

Options

其他表达式与操作符

不可变性的好处

共享与别名

编程语言的部件

思维导图