华盛顿CSE341编程语言讲义.pdf资源-CSDN文库

需积分: 5 157 浏览量 2024-02-03 12:13:11 上传评论收藏 3.13MB PDF 举报

资源推荐

资源详情

资源评论

CSE341：2016年春季编程语言课程

第1单元总结

标准描述：这个总结大致涵盖了课堂和复习部分的内容。当回顾材料时，以叙述方式阅读材料并将整个单

元的材料放在一个文档中可能会有所帮助。请报告这些笔记中的错误，甚至是打字错误。这个总结不能完

全替代上课、阅读相关代码等。

欢迎来到编程语言课程. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 1

ML表达式和变量绑定. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . 2

使用 us e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 3

变量是不可变的. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 4

函数绑定. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . 4

对和其他元组. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . 5

列表. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 6

Let表达式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 8

选项. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

其他一些表达式和运算符. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

缺乏变异和其优点. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

欢迎来到编程语言课程

课程网页的顶部有四个重要的文件，这里不再重复。它们是教学大纲、学术诚信政策、挑战项目政策以及

关于这门课程与Coursera上的一门课程相关的描述。请仔细阅读这些文件。

一个名为“编程语言”的课程可以有很多不同的含义。对我们来说，它意味着有机会学习几乎在每种编程语

言中都出现的基本概念。

我们还将对这些概念如何“组合在一起”以提供程序员所需的内容有一些了解。我们将使用不同的语言来看

看它们如何以互补的方式表示这些概念。所有这些都旨在使您成为一名更好的软件开发人员，无论使用哪

种语言。

很多人会说这门课程“教授”3种语言ML、Racket和Ruby，但这是相当误导的。我们将使用这些语言来学习

各种范式和概念，因为它们非常适合这样做。如果我们的目标只是让您在这三种语言中尽可能高效地工作

，课程材料将会非常不同。话虽如此，能够学习新的语言并识别不同语言之间的相似之处和差异是一个重

要的目标。

大部分课程将使用函数式编程（ML和Racket都是函数式语言），强调不可变数据（没有赋值语句）和函数

，特别是接受和返回其他函数的函数。正如我们将在课程中讨论的那样，函数式编程与面向对象编程完全

相反，但也有许多相似之处。函数式编程不仅是一种非常强大和优雅的方法，而且学习它可以帮助你更好

地理解所有编程风格。

在课程的最开始，通常要激发学习兴趣，这种情况下，我们将解释为什么你应该学习函数式编程，更一般

地说，为什么值得学习它。

不同的语言、范式和语言概念。我们将在大约两周后再详细讨论这个问题。在大多数学生更关心课程工作

内容的时候，这个问题太重要了，而且更重要的是，在我们建立了几节共享术语和经验的讲座之后，这个

讨论会更容易进行。动机确实很重要；让我们推迟一下，但承诺它一定是值得的。

ML表达式和变量绑定

所以让我们开始“学习ML”，但以一种教授核心编程语言概念的方式，而不仅仅是“编写一些能工作的代码”

。因此，请非常注意用来描述我们开始的非常简单的代码的词语。我们正在建立一个基础，这个基础将在

本周和下周迅速扩展。暂时不要试图将你看到的内容与你已经了解的其他语言联系起来，因为这可能会导

致困难。

一个ML程序是一系列的绑定。每个绑定都会进行类型检查，然后（假设它通过了类型检查）进行求值。

一个绑定的类型（如果有的话）取决于一个静态环境，大致上是文件中前面绑定的类型。一个绑定的求值

方式取决于一个动态环境，大致上是文件中前面绑定的值。当我们只说“环境”时，通常指的是动态环境

。有时候，“上下文”被用作“静态环境”的同义词。

有几种绑定方式，但现在我们只考虑一个变量绑定，在ML中的语法如下：

val x = e;

在这里， val是一个关键字， x可以是任何变量， e可以是任何表达式。我们将学习很多种写表达式的方

法。分号在文件中是可选的，但在读取-求值-打印循环中是必需的，以便让解释器知道你已经完成了绑定的

输入。

我们现在知道了变量绑定的语法（如何编写），但我们仍然需要知道它的语义（如何进行类型检查和求值

）。大多数情况下，这取决于表达式 e。要进行变量绑定的类型检查，我们使用“当前静态环境”（前面绑

定的类型）来检查 e（这将取决于表达式的类型）并生成一个“新的静态环境”，该环境与当前静态环境相同

，只是 x具有类型 t，其中 t是 e的类型。求值类似：要求值一个变量绑定，我们使用“当前动态环境”（

前面绑定的值）来求值 e（这将取决于表达式的类型）并生成一个“新的动态环境”，该环境与当前环境相同

，只是 x具有值 v，其中 v是求值 e的结果。

一个值是一个表达式，即“没有更多的计算”，即没有办法简化它。如下面更一般地描述的那样，17是一个

值，但8+9不是。所有的值都是表达式。并不是所有的表达式都是值。

这整个关于ML程序意义的描述（绑定、表达式、类型、值、环境）可能看起来非常理论化或者晦涩，但这

正是我们需要为几种不同类型的表达式给出精确而简洁的定义的基础。下面是几个这样的定义：

• 整数常量：

–语法：一系列数字

–类型检查：在任何静态环境中类型为int

–评估：在任何动态环境中自身（它是一个值）

1这里的单词 static 与其在Java/C/C++ 中的使用有一种脆弱的联系，但在这一点上解释起来太脆弱了。

变量是不可变的

绑定是不可变的。给定val x = 8+9;我们产生一个动态环境，其中 x映射到 17。在这个环境中， x将始终映

射到 17；在ML中没有“赋值语句”来更改x映射到的内容。如果你正在使用 x，这非常有用。你以后可以有

另一个绑定，比如val x = 19;，但这只会创建一个不同的环境，其中后面的绑定对 x进行了屏蔽。当我们定

义使用变量的函数时，这个区别将非常重要。

函数绑定

回想一下，ML程序是一系列绑定的序列。每个绑定都会添加到静态环境（用于类型检查后续绑定）和动态

环境（用于评估后续绑定）。我们已经介绍了变量绑定；现在我们介绍函数绑定，即如何定义和使用函数

。然后，我们将学习如何使用对和列表从较小的数据构建和使用较大的数据块。

函数有点像Java等语言中的方法-它是通过参数调用并产生结果的东西。与方法不同，没有类、this等概念

。我们也没有像return语句这样的东西。一个简单的例子是计算 x

的函数，假设 y ≥ 0：

fun pow (x:int, y:int) = （仅当y >= 0时正确）

如果 y=0

那么 1

否则 x * pow(x,y-1)

语法：

函数绑定的语法如下（我们稍后会对这个定义进行泛化）：

fun x0 (x1 : t1, ..., xn : tn) = e

这是一个名为 x0的函数绑定。它有 n个参数 x1, ... 类型分别为 t1, ..., tn，并且有一个表达式 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也将是可选的，但是在稍后学习模式匹配之前不是。

在函数绑定之后，将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) = （仅当y >= 0时正确）

如果 y=0

那么 1

否则 x * pow(x,y-1)

fun cube (x:int) =

pow(x,3)

val ans = cube(4)

对偶和其他元组

编程语言需要一种将简单数据组合成复合数据的方法。我们将在ML中学习的第一种方法是对偶。构建对

偶的语法是 (e1,e2)，它将 v1评估为 v1，将 v2评估为 v2，并且生成值为 (v1,v2)的对偶，它本身也是一

个值。由于 v1和/或 v2本身可能是对偶（可能包含其他对偶等），我们可以构建具有多个“基本”值的数据

，而不仅仅是两个整数。

对偶的类型是 t1*t2，其中 t1是第一部分的类型， t2是第二部分的类型。

就像制作函数只有在我们可以调用它们时才有用，制作对只有在我们以后可以检索到各个部分时才有用。

在我们学习模式匹配之前，我们将使用 #1和 #2来访问第一个和第二个部分。对于#1 e或#2 e的类型规则应

该不会让人感到意外： e必须具有类似于ta * tb的某种类型，然后#1 e的类型为 ta，#2 e的类型为 tb。

下面是使用对的几个示例函数。 div_mod可能是最有趣的，因为它使用了一个对来返回具有两个部分的答案。

2我们在本单元和作业1中使用对读取构造，需要这些显式类型。

剩余178页未读，继续阅读

评论收藏

内容反馈

绝不原创的飞龙

粉丝: 1w+
资源: 1091

华盛顿 CSE341 编程语言讲义.pdf

最新资源

华盛顿 CSE341 编程语言讲义.pdf

石溪 CSE509 系统安全讲义.pdf

H3CSE GB381答案含解析.pdf

H3CSE路由实验文档手册.pdf

H3CSE GB0-381 .pdf

360cse_13.0.2256.0.exe

360浏览器极速版360cse_11.0.2116.0.exe

360cse_12.0.1476.0.exe

360cse_12.0.1478.0.exe

DS_CSE7761_V1.3.pdf

CSE446 Machine Learning.pdf

360cse_13.0.2250.0.exe

H3Cse路由、交换版.7z

新版H3CSE GB0-371 GB0-381 GB0-391 V2.1题库 100%包通过

360cse_7.5.3.118.exe

cse_5.2.0.804

cse_5.3.0.806

2021年H3CSE考试题库371.381.391包含PDF文件，vce文件.rar

360cse_8.5.0.142.exe

H3CSE（路由）学习笔记.pdf

相关实用应用程序（Windows可用）

免费可用的ChatGPT网页版.zip

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

chromedriver-win64.zip

李飞飞自传 我看见的世界 The World I see

全国计算机二级WPSoffice精选350道选择题题库（含答案）.pdf

哈尔滨工业大学-ChatGPT调研报告-2023.3.6-94页.pdf

农村公交与异构无人机协同配送优化

4个亲测好用的ChatGPT4渠道

学术海报模板+论文科研+研究生

最新资源

李飞飞自传我看见的世界 The World I see