Programming Languages Part A Section1 翻译

这里对Section 1进行翻译。

课程主页：

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

B站搬运：

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

Coursera编程语言课程 第1节总结

标准说明：本总结涵盖的材料与课堂视频以及随视频发布的材料（幻灯片、代码）大致相同。它有助于以叙述的方式阅读材料，并将整个课程部分的材料放在一份文件中，特别是在以后复习材料时。请在讨论区上报告这些笔记中的错误。

目录

• 欢迎使用编程语言
• ML表达式和变量绑定
• 使用use
• 变量是不可改变的(Immutable)
• 函数绑定
• Pairs和其他元组
• 列表
• Let表达式
• Options
• 一些其他表达式和运算符
• 缺乏突变(Mutation)和突变的好处
• 程序设计语言的各个部分

欢迎来到《程序设计语言》

（也可参见课程网页上关于课程结构、作业、评分、软件安装等的介绍性材料。这些材料在此不再重复。）

一门名为”编程语言”的课程可能意味着许多不同的事情。对我们来说，这意味着有机会学习几乎每种编程语言中以某种形式出现的基本概念。我们还将了解这些概念是如何”结合”在一起的，以提供程序员在语言中所需要的东西。我们将使用不同的语言，看看它们如何采取互补的方法来表示这些概念。所有这些都是为了使你成为一个更好的软件开发者，无论使用何种语言。

很多人会说这门课程“教授”了3种语言ML（在A部分）、Racket（在B部分）和Ruby（在C部分），但这是一个糟糕的描述。我们将使用这些语言来学习各种范式和概念，因为它们很适合这样做。如果我们的目标只是让你在这三种语言中尽可能地提高工作效率，那么课程材料将非常不同。也就是说，能够学习新的语言并认识到不同语言之间的差异，是一个重要的目标。

本课程的大部分内容将使用函数式编程（ML和Racket都是函数式语言），它强调不可变的数据（无赋值语句）和函数，特别是接受和返回其他函数的函数。正如我们将在后面的C部分讨论的那样，函数式编程在某些方面与面向对象编程完全相反，但也有许多相似之处。函数式编程不仅是一种非常强大和优雅的方法，而且学习它有助于你更好地理解所有的编程风格。

在课程的最开始，传统的做法是介绍设置课程的动机，在这种情况下，会解释为什么你应该学习函数式编程，以及更普遍的为什么值得学习不同的语言、范式和语言概念。我们基本上会把这个讨论推迟到第三次作业之后。当大多数学生更关心如何理解课程中的工作时，这一点就太重要了，而且更重要的是，在我们建立了共同的术语和经验之后，讨论这个问题要容易得多。动机确实很重要；让我们接受一张“改天支票”，并承诺这将是非常值得的。

ML表达式和变量绑定

所以让我们开始”学习ML”，但要以教授核心编程语言概念的方式，而不仅仅是”写下一些能用的代码”。因此，请特别注意用于描述我们开始时非常简单的代码的词语。我们正在建立一个基础，在本周和下周，我们将迅速扩展这个基础。不要试图将你所看到的东西与你在其他语言中已经知道的东西联系起来，因为这很可能会很挣扎。

一个ML程序是一系列绑定。每个绑定都要进行类型检查，然后（假设它进行了类型检查）进行计算。一个绑定的类型（如果有的话）取决于静态环境（这里的静态一词与它在Java/C/C++中的使用有着微妙的联系，但在这一点上难以解释。），大致是文件中前面的绑定的类型。一个绑定如何被评估取决于动态环境，大致是文件中前面的绑定的值。当我们只说环境(environment)时，我们通常指的是动态环境。有时上下文(cotext)被用作静态环境的同义词。

绑定有好几种，但现在我们只考虑变量绑定，在ML中有这样的语法：

val x = e;

这里，val是一个关键字，x可以是任何变量，e可以是任何表达式。我们将学习许多写表达式的方法。分号在文件中是可选的，但在read-eval-print循环中是必要的，以便让解释器知道你已经完成了输入绑定。

我们现在知道了一个变量绑定的语法（如何写），但是我们仍然需要知道它的语义（它如何进行类型检查和评估）。为了对一个变量绑定进行类型检查，我们使用”当前的静态环境”（之前绑定的类型）对e进行类型检查（这将取决于它是什么样的表达式），并产生一个”新的静态环境”，它是当前的静态环境，但x的类型为t，其中t是e的类型。评估是类似的：为了评估一个变量绑定，我们使用”当前的动态环境”（前面的绑定的值）来评估e（这将取决于它是什么类型的表达式），并产生一个”新的动态环境”，它是当前的环境，除了x具有值v，其中v是评估e的结果。

值是一个表达式，它”没有更多的计算要做”，也就是说，没有办法简化它。正如下面所描述的，17是一个值，但8+9不是。所有的值都是表达式，但不是所有的表达式都是值。

这整个关于ML程序含义的描述（绑定、表达式、类型、值、环境）可能看起来非常理论化或深奥，但这正是我们为几种不同类型的表达式给出精确和简洁的定义所需要的基础。下面是几个这样的定义：

• 整数常量：
  • 语法：一串数字
  • 类型检查：在任何静态环境下都是int类型
  • 评估：在任何动态环境下都是其本身（它是一个值）
• 加法：
  • 语法：e1+e2，其中e1和e2是表达式
  • 类型检查：当e1和e2在同一静态环境中且具有int类型时，类型为int，否则不进行类型检查
  • 评估：在同一动态环境中将e1评估为v1，将e2评估为v2，然后产生v1和v2的和
• 变量：
  • 语法：一串字母、下划线，等等
  • 类型检查：在当前静态环境中查找变量并使用该类型
  • 评估：在当前动态环境中查找变量并使用该值
• 条件表达式：
  • 语法是if e1 then e2 else e3，其中e1、e2和e3是表达式
  • 类型检查：使用当前的静态环境，条件的类型检查只有如下条件满足时才进行：
    • (a) e1有bool类型和
    • (b) e2和e3有相同的类型。
    • 整个表达式的类型是e2和e3的类型。
  • 评估：在当前的动态环境下，评估e1。如果结果为true，在当前动态环境下评估e2的结果就是整体结果。如果结果是false，则在当前动态环境下评估e3的结果就是整体结果。
• 布尔常量：
  • 语法：要么是true，要么是false
  • 类型检查：在任何静态环境下都是bool类型
  • 评估：在任何动态环境下就是其本身（它是一个值）
• 小于比较：
  • 语法：e1 < e2，其中e1和e2是表达式
  • 类型检查：当e1和e2在同一静态环境中具有int类型时类型为bool，否则不进行类型检查
  • 评估：在同一动态环境中，将e1评估为v1，将e2评估为v2，然后如果v1小于v2，则产生true，否则产生false

当你学习一种编程语言的新结构时，你应该问这三个问题。语法是什么？类型检查规则是什么？评估规则是什么？

使用use

当使用read-eval-print循环时，从一个文件中添加一连串的绑定是非常方便的。

use "foo.sml"; 

就是这样做的。它的类型是unit，其结果是()（unit类型的唯一值），但它的效果是包括文件”foo.sml”中的所有绑定。

变量是不可改变的

绑定是不可改变的。给定val x=8+9; 我们产生一个动态环境，x映射到17。在这个环境中，x总是映射到17；在ML中没有”赋值语句”来改变x映射到什么。如果你正在使用x，这就非常有用了。你可以在以后有另一个绑定，比如说val x = 19;，但这只是创造了一个不同的环境，在这个环境中，后来的``x的绑定会覆盖(shadow)先前的那个。当我们定义使用变量的函数时，这种区别将是非常重要的。

函数绑定

回顾一下，一个ML程序是一连串的绑定。每个绑定都增加了静态环境（用于类型检查后续绑定）和动态环境（用于评估后续绑定）。我们已经介绍了变量绑定；现在我们介绍函数绑定，即如何定义和使用函数。然后，我们将学习如何使用pair和列表从较小的数据中建立和使用较大的数据块。

函数有点像Java等语言中的方法——它是用参数调用的，并且有一个生成结果的主体。与方法不同，没有类、this等概念。我们也没有像返回语句这样的东西。一个简单的例子是这个假设$y\ge 0$的计算$x^y$的函数：

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$个类型为t1, ..., tn的参数x1, ... xn，并有一个表达式e作为其主体。一如既往，语法只是语法——我们必须为函数绑定定义类型规则和评估规则。但大致上说，在e中，参数被绑定为x1, ... xn，调用x0的结果是e的评估结果。

类型检查：

为了对一个函数绑定进行类型检查，我们在一个静态环境中对主体e进行类型检查，（除了所有先前的绑定之外）映射x1到t1，…，xn到tn，x0到t1 * … * tn -> t。由于x0在环境中，所以我们可以进行递归函数调用，也就是说，一个函数定义可以使用自己。函数类型的语法是”参数类型”->”结果类型”，其中参数类型用*（恰好与表达式中用于乘法的字符相同）分隔。为了使函数绑定进行类型检查，主体e必须具有t类型，即x0的结果类型。考虑到下面的评估规则，这是有道理的，因为函数调用的结果就是评估e的结果。

但是，t到底是什么——我们从来没有把它写下来？它可以是任何类型，由类型检查器（语言实现的一部分）来找出t应该是什么，以便将它用于x0的结果类型，使”一切顺利”。现在，我们将把它看作是神奇的，但类型推理（弄清没有写下来的类型）是ML的一个非常酷的特征，在课程的后面会讨论。事实证明，在ML中你几乎不需要写下类型。很快，参数类型t1, ..., tn也将是可选的，但要等到我们稍后学习模式匹配时才会出现（我们在本讲座和家庭作业1中使用像#1这样的pair-reading结构的方式需要这些明确的类型。）。

在函数绑定后，x0被添加到静态环境中，并带有其类型。参数不被添加到顶层静态环境中——它们只能在函数主体中使用。

评估：

函数绑定的评估规则很简单：一个函数是一个值——我们只需将x0作为一个函数添加到环境中，以便以后可以调用它。正如递归所预期的那样，x0在函数主体和后续绑定的动态环境中（但不像Java中那样，对于前面的绑定，定义函数的顺序非常重要）。

函数调用：

函数绑定只对函数调用有用，这是一种新的表达方式。语法是e0 (e1,...,en)，如果正好有一个参数，圆括号是可选的。类型规则要求e0的类型看起来像t1*...*tn->t，对于$1≤i≤n$，ei的类型是ti。那么整个调用的类型为t。希望这不会太令人惊讶。对于评估规则，我们使用调用点的环境来评估e0为v0，e1为v1，…，en为vn。然后v0必须是一个函数（它将被假设为调用类型检查），我们在一个扩展的环境中评估函数的主体，使函数参数映射到v1, ..., vn。

究竟我们用参数扩展的是哪个环境？是定义函数时的”当前”环境，而不是正在被调用的环境。这个区别现在不会出现，但我们以后会详细讨论。

把所有这些放在一起，我们可以确定这段代码将产生一个Ans为64的环境：

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

Pairs和其他元组

编程语言需要从较简单的数据中建立复合数据的方法。我们将在ML中学习的第一个方法是pairs。建立一个pair的语法是(e1,e2)，它将e1评估为v1，e2评估为v2，形成一对值(v1,v2)，它本身就是一个值。由于v1和/或v2本身可以是pair（可能持有其他pair，等等），因此我们可以用几个“基本”值构建数据，而不仅仅是两个（比如）整数。一个pair的类型是t1*t2，其中t1是第一部分的类型，t2是第二部分的类型。

就像生成函数只有在我们能够调用它们时才有用一样，生成pairs也只有在我们以后能够检索这些片段时才有用。在我们学习模式匹配之前，我们将使用#1和#2来访问第一和第二部分。#1 e或#2 e的类型规则不应令人惊讶：e必须有某种类型，看起来像ta * tb，那么#1 e有类型ta，#2有类型tb。

这里有几个使用pair的函数例子。 div_mod也许是最有趣的，因为它使用pair来返回一个有两部分的答案。这在ML中是相当令人愉快的，而在Java中（例如）从一个函数中返回两个整数需要定义一个类，写一个构造函数，创建一个新对象，初始化它的字段，并编写返回语句。

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)
    
fun div_mod (x : int, y : int) =  (* note: returning a pair is a real pain in Java *)
    (x div y, x mod y)
    
fun sort_pair (pr : int*int) =
    if (#1 pr) < (#2 pr)
    then pr
    else ((#2 pr),(#1 pr))

事实上，ML通过允许任意数量的部分来支持元组。例如，一个整数的3元组的类型是int*int*int。一个例子是(7,9,11)，你用#1 e, #2 e, #3 e来检索这些部分，其中e是一个表达式，可以评估为一个三元组。

pair和元组可以随你的意愿进行嵌套。例如，(7,(true,9))是一个int * (bool * int)类型的值，这与((7,true),9)不同，后者的类型是(int * bool) * int，又例如(7,true,9)的类型是int * bool * int。

列表

虽然我们可以随心所欲地嵌套pair（或元组），但对于任何有pair的变量、任何返回pair的函数等，都必须有一个pair的类型，而这个类型将决定”真实数据”的数量。即使是元组，类型也指定了它有多少部分。这往往是过于严格的；我们可能需要一个数据列表（例如整数），而当我们进行类型检查时，列表的长度还不知道（它可能取决于一个函数参数）。ML有列表，它在长度方面比pair更灵活，因为它们可以有任何长度，但在类型方面更不灵活，因为任何特定列表的所有元素必须有相同的类型。

空列表，其语法为[]，有0个元素。它是一个值，所以像所有的值一样，它立即对自己进行评估。对于任意类型t，有类型t list，ML将其写成'a list（读作”quote a list”或”alpha list”）。一般来说，类型t list的描述的是列表中的所有元素都具有t类型的列表，这对[]来说是成立的，不管t是什么。

一个有$n$个值的非空列表被写成[v1,v2,...,vn]。你可以用[e1,...,en]创建一个列表，其中每个表达式都被评估为一个值。更常见的是用 e1 :: e2 来创建一个列表，读作”e1 consed onto e2”。这里e1被评估为一个 “t类型的项”，e2被评估为一个 “t值的列表”，结果是一个新的列表，以e1的结果开始，然后是e2中的所有元素。

与函数和pair一样，只有当我们能用它们做一些事情时，创建列表才是有用的。就像pair一样，在我们学习了模式匹配之后，我们将改变我们使用列表的方式，但现在我们将使用ML提供的三个函数。每个函数都需要一个列表作为参数。

• null 对空的列表评估为真，对非空的列表评估为假。
• hd 返回一个列表的第一个元素，如果列表是空的，则引发一个异常。
• tl 返回一个列表的尾部（一个类似其参数但没有第一个元素的列表），如果该列表为空，则引发异常。

下面是一些接受或返回列表的函数的简单例子：

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

创建和使用列表的函数几乎都是递归的，因为列表有一个未知的长度。要编写递归函数，思考过程包括考虑基本情况——例如，空列表的答案应该是什么——以及递归情况——如何用列表其余部分的答案来表示答案。

当你这样思考时，许多问题就变得简单多了，这让那些习惯于思考while循环和赋值语句的人感到惊讶。一个很好的例子是上面的append函数，它接收两个列表并产生一个列表，即一个列表附加到另一个列表上。这段代码实现了一个优雅的递归算法。如果第一个列表是空的，那么我们可以通过对第二个列表进行评估来进行追加。否则，我们可以将第一个列表的尾部追加到第二个列表中。这几乎是正确的答案，但是我们需要对第一个列表的第一个元素进行”运算”（使用 :: 已经有几十年的历史了）。这里没有什么神奇的地方——我们用越来越短的第一个列表不断地进行递归调用，然后随着递归调用的完成，我们再把递归调用所删除的列表元素添加回去。

最后，我们可以随心所欲地组合pair和列表，而不必在语言中添加任何新特性。例如，这里有几个函数，它们接收一个整数对的列表。请注意最后一个函数是如何重用先前的函数以实现一个非常简短的解决方案的。这在函数式编程中是非常常见的。事实上，应该困扰我们的是，firsts和seconds如此相似，但我们却没有让它们共享任何代码。我们将在后面学习如何解决这个问题。

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表达式

Let表达式是一个绝对重要的特性，它允许以一种非常简单、通用和灵活的方式使用局部变量。Let表达式对于风格和效率都是至关重要的。Let表达式让我们拥有局部变量。事实上，它允许我们拥有任何类型的局部绑定，包括函数绑定。因为它是表达式的一种，所以它可以出现在表达式可以出现的任何地方。

从语法上讲，let-expression是：

let b1 b2 ... bn in e end

其中每个bi是一个绑定，e是一个表达式。

let-表达式的类型检查和语义很像我们ML程序中顶级绑定的语义。我们依次评估每个绑定，为后续的绑定创造一个更大的环境。我们把一个绑定的范围称为 “它可以被使用的地方”，所以一个let表达式中的绑定的范围是该let表达式中后来的绑定和该let表达式的 “主体”（e）。e的评估值是整个let表达式的值，而且，不出所料，e的类型是整个let表达式的类型。

例如，这个表达式评估为7；注意x的一个内部绑定是如何影射一个外部绑定的。

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

还注意到let表达式是表达式，所以它们可以作为加法中的子表达式出现（尽管这个例子很傻，风格不好，因为它很难读）。

Let表达式也可以绑定函数，因为函数只是另一种绑定方式。如果一个辅助函数只被一个其他函数所需要，并且不太可能在其他地方发挥作用，那么将其绑定在本地是一种很好的风格。例如，这里我们使用一个本地辅助函数来帮助产生列表[1,2,...,x]:

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

不过，我们可以做得更好。当我们评估对count的调用时，我们在一个动态环境中评估count的主体，该环境是定义count的环境，并为count的参数扩展了绑定。上面的代码并没有真正利用这一点：count的主体只使用from、to和count（用于递归）。它也可以使用x，因为当count被定义时，它就在环境中。那么我们就完全不需要to了，因为在上面的代码中，它的值总是和x一样的。 所以这是更好的风格：

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-expressions的代码。

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)

如果你用countup_from 1 30调用bad_max，它将对自己进行大约$2^{30}$次（超过10亿）递归调用。原因是 “指数爆炸”——代码调用bad_max(tl xs)两次，每一次调用都会再调用bad_max两次（所以总共有4次），以此类推。这种编程”错误”可能很难发现，因为它可能取决于你的测试数据（如果列表递减，算法只进行30次递归调用而不是$2^{30}$次）。

我们可以使用let表达式来避免重复计算。这个版本计算了一次列表尾部的最大值，并将结果值存储在tl_ans中。

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

前面的例子没有正确处理空列表——它返回0。这是不好的风格，因为0确实不是0个数字的最大值。尽管没有好的答案，但我们应该合理地处理这种情况。一种可能性是引发一个异常；如果你有兴趣，你可以在我们以后的课程中讨论它们之前，自己学习一下ML异常。相反，让我们改变返回类型，要么返回最大数，要么表明输入列表是空的，所以没有最大数。根据我们已有的结构，我们可以通过返回一个int list来 “编码”，如果输入的是空列表，则使用[]，如果输入的列表不是空的，则使用一个带有整数（最大值）的列表。

虽然这个方法可行，但是列表是”多余”的——我们将总是返回一个有0或1个元素的列表。所以一个列表并不是对我们要返回的东西的精确描述。ML库有”options”，这是一个精确的描述：一个选option值有0或1个值：NONE是一个”不携带任何东西”的option值，而SOME e将e评估为一个值v，成为携带值v的option。NONE的类型是’a option，如果e的类型是t，SOME e的类型是t option。

给定一个值，你如何使用它？就像我们有null来判断一个列表是否为空一样，我们有isSome，如果它的参数是NONE，它的评估结果为false。就像我们hd和tl来获取列表的一部分（对空列表引发异常），我们有valOf来获取SOME所带的值（对NONE引发异常）。

使用option，这里有一个更好版本的max，带有返回类型int option：

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

上面的版本工作得很好，是一个合理的递归函数，因为它没有重复任何潜在的昂贵计算。但是让每个递归调用（除了最后一个）都创建一个带有SOME的选项，以便让其调用者访问下面的值，这既笨拙又有点低效。这里有一个替代方法，我们使用一个本地辅助函数来处理非空列表，然后只让外层函数返回一个option。注意，如果用[]调用，辅助函数会引发一个异常，但由于它是本地定义的，我们可以确定这不会发生。

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

一些其他的表达式和运算符

ML有你需要的所有算术和逻辑运算符，但其语法有时与大多数语言不同。下面是一些我们会发现有用的额外形式的表达式的简要列表:

• e1 andalso e2是逻辑与：只有当e1的评估为真时，它才会评估e2。如果e1和e2评估为真，结果就是真。当然，e1和e2必须都有bool类型，整个表达式也有bool类型。在许多语言中，这样的表达式被写成e1 && e2，但这不是ML的语法，e1 and e2也不是（但and是我们以后会遇到的一个关键词，有不同的用途）。使用e1 andalso e2通常比等价的if e1 then e2 else false的风格更好。

• e1 orelse e2是逻辑或：只有当e1评估为false时，它才会评估e2。如果e1或e2评估为true，则结果为true。当然，e1和e2必须都有bool类型，整个表达式也有bool类型。在许多语言中，这样的表达式被写成e1 || e2，但这不是ML的语法，e1 or e2也不是。使用e1 orelse e2通常比等价的if e1 then true else e2的风格更好。

• not e是逻辑否定：not只是一个提供的bool->bool类型的函数，我们可以自己定义为fun not x = if x then false else true。在许多语言中，这样的表达式被写成!e，但在ML中，!操作符意味着其他的东西（与可变变量有关，我们将不使用）。
• 你可以用e1 = e2来比较许多数值，包括整数，以确定是否相等。
• 不要用not (e1 = e2)来查看两个数字是否不同，更好的样式是e1<>e2。在许多语言中，语法是e1!= e2，而ML的<>可以被记为，”小于或大于”。
• 其他算术比较的语法与大多数语言中相同：>, <, >=, <=。
• 减法写成e1 - e2，但它必须有两个操作数，所以不能通过-e求相反数。对于求相反数，正确的语法是~e，特别是负数要写成~7，而不是-7。使用~e比使用0-e更好，但对于整数是等效的。

缺少突变及其好处

在ML中，没有办法改变一个绑定、一个元组或一个列表的内容。如果x在某个环境中映射到某个值，如pair列表[(3,4),(7,9)]，那么x将永远在那个环境中映射到该列表。没有任何赋值语句可以将x改为映射到不同的列表。(你可以引入一个新的绑定来shadow x，但这不会影响任何在环境中查找”原始”x的代码。) 没有赋值语句可以让你改变列表的头或尾。也没有赋值语句可以让你改变一个元组的内容。所以我们有构建复合数据和访问片段的结构，但没有结构来改变我们所构建的数据。

这是一个非常强大的功能！这可能会让你感到惊讶：一种语言没有某种东西怎么会是一种特性呢？因为如果没有这样的特性，那么当你写代码的时候，你就不能假设其他的代码不会做一些让你的代码出错、不完整或难以使用的事情。拥有不可变的数据可能是一种语言所能拥有的最重要的”非特性”，它也是函数式编程的主要贡献之一。

虽然不可变的数据有各种优点，但在这里我们将重点讨论一个重要的优点：它使共享和别名变得不重要。在选择Java之前，让我们再考虑上面的两个例子（以及其他语言，在这些语言中，可变数据是常态，赋值语句非常流行）。

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

在sort_pair中，我们显然在else-branch中建立并返回一个新的pair，但在then-branch中，我们是返回pr所指的pair的副本，还是返回一个别名是一个问题，其中调用如下：

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

现在，x和y会是同一pair的别名吗？答案是你无法判断——在ML中没有任何结构可以弄清x和y是否是别名，也没有理由担心它们可能是别名。如果我们有突变，情况就会不同。假设我们可以说，”改变x被绑定的第二部分，使其持有5而不是4”。那么我们就不得不想，y的第2个元素会是4还是5。

如果你感到好奇，我们希望上面的代码会产生别名：通过返回pr，sort_pair函数会返回其参数的一个别名。这比这个版本更有效，因为它将创建另一个内容完全相同的pair：

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

生成新的对(#1 pr, #2 pr)是不好的风格，因为pr更简单，效果也一样。然而在有突变的语言中，程序员一直在做这样的拷贝，正是为了防止别名，即使用一个变量（如x）进行赋值会导致使用另一个变量（如y）的意外变化。 在ML中，sort_pair的用户永远不会知道我们是否返回一个新pair。

我们的第二个例子是我们用于list append的优雅函数：

fun append (xs : int list, ys : int list) =
    if null xs
    then ys
    else (hd xs) :: append(tl xs, ys)

我们可以问一个类似的问题。返回的列表是否与参数共享任何元素？同样，答案并不重要，因为没有调用者可以知道。同样，答案也是肯定的：我们建立一个新的列表，”重用”ys的所有元素。这节省了空间，但如果有人后来对ys进行改变，就会非常混乱。节省空间是不可变数据的一个很好的优点，但在编写优雅的算法时，不必担心是否存在别名。

事实上，tl本身就引入了别名（虽然你看不出来）：它返回（别名）列表的尾部，这比复制一个列表的尾部代价更低，因为复制操作对长列表来说代价很高。

append的例子与sort_pair的例子非常相似，但它更有说服力，因为如果你有许多潜在的长度较大的列表，就很难跟踪潜在的别名。如果我把[1,2]追加到[3,4,5]，我将得到列表[1,2,3,4,5]，但是如果后来有人可以把[3,4,5]列表改为[3,7,5]，那么追加的列表还是[1,2,3,4,5]，还是现在的[1,2,3,7,5]？

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

你能找到问题所在吗？在这里：getAllowedUsers返回allowedUsers数组的别名，所以任何用户都可以通过执行getAllowedUsers()[0] = currentUser()获得访问权。如果Java中有某种不允许更新其内容的数组，那么这是不可能发生的。相反，在Java中，我们经常要记住生成一个副本。下面的修正显示了一个显式循环，以详细说明必须做什么，但更好的风格是使用System.arraycopy这样的库方法或Arrays类中的类似方法——这些库方法的存在是因为数组复制必然很常见，部分原因是突变的。

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

编程语言的各个部分

现在我们已经学了足够的ML，可以用它来编写一些简单的函数和程序，我们可以列出定义和学习任何编程语言所必需的基本”组成部分”。

• 语法：你如何编写语言的各个部分？
• 语义：各种语言特征是什么意思？例如，表达式是如何被评估的？
• 习语：使用语言特征来表达计算的常见方法是什么？
• 库：哪些东西已经为你写好了？你如何做没有库支持就不能做的事情（比如访问文件）？
• 工具：可用于操作语言程序的工具（编译器、读取-评估打印循环、调试器等）

虽然库和工具对于成为一个有效的程序员来说是必不可少的（避免重新发明可用的解决方案或不必要的手动操作），但本课程并没有过多关注它们。这可能会给人留下错误的印象，认为我们使用的是”愚蠢的”或”不实用的”语言，但在一门关于编程语言概念上的相似性和差异的课程中，库和工具就不那么重要了。