这次回顾Part B Week 4的内容，主要介绍了静态类型和动态类型的区别。

课程主页：

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

B站搬运：

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

Week 4

ML vs Racket

主要区别

Racket和ML有很多共同点
主要区别
- 语法
- 模式匹配与结构测试和访问函数
- 各种let表达式的语义
最大的不同：ML的类型系统和Racket缺失类型系统
- 有Typed Racket，与Racket交互得很好，所以你可以有类型化和非类型化模块，但我们不会研究它，它与ML 有一些有趣的不同

即将到来的主题

即将介绍：
- 什么是类型检查？静态类型？动态类型？等等。
- 为什么类型检查是近似的？
- 类型检查的优点和缺点是什么？
但首先要更好地了解ML和Racket：
- Racket 程序员如何描述ML？
- ML程序员如何描述Racket？

从Racket的角度来看ML

除了语法等，ML就像是Racket的一个明确定义的子集
它不允许的如下有错误的程序：
```
(define (g x) (+ x x)) ; ok
(define (f y) (+ y (car y)))
(define (h z) (g (cons z 2)))
```
- 事实上，在ML允许的范围内，我从不需要像number?这样的原语；

同样不允许如下程序：

(define (f x) (if (> x 0) #t (list 1 2)))
(define xs (list 1 #t "hi"))
(define y (f (car xs)))

从ML的角度来看Racket

描述Racket的一种方式是它具有“一种大数据类型”

所有值都有这种类型

datatype theType = Int of int | String of string
                 | Pair of theType * theType
                 | Fun of theType -> theType
                 | …

构造函数被隐式应用（值被标记）
- 42真的很像Int 42
- 原语隐式检查标签并提取数据，对于错误的构造函数报告错误
```
fun car v = case v of Pair(a,b) => a | _ => raise …
fun pair? v = case v of Pair _ => true | _ => false
```

什么是静态检查？

静态检查

静态检查是在程序（成功）解析之后但在程序运行之前拒绝程序所做的任何事情
PL 定义的一部分：执行什么静态检查
- 一个“有用的工具”可以做更多的检查
定义PL的静态检查的常用方法是通过类型系统
- 方法是给每个变量、表达式等一个类型
- 目的包括防止滥用原语（例如，4/“hi”）、强制抽象和避免动态检查
  - 运行时动态
动态类型语言（几乎）不做静态检查
- 但不是绝对的

示例：ML，什么类型可以阻止

在ML中，类型检查确保程序（在运行时）永远不会：

对错误类型的值使用的原语
- 对不是数字的部分使用算术运算
- e1 e2，其中e1不计算为函数
- if和then之间的非布尔值
未在环境中定义的变量
具有冗余模式的模式匹配
模块外的代码调用不在模块签名中的函数

（前两个是类型系统的“标准”，但不同语言的类型系统确保不同的东西）

示例：ML，允许哪些类型

在ML中，类型检查并不能防止任何这些错误；相反，在运行时检测到
- 调用导致异常发生的函数，例如hd []
- 数组边界错误
- 被零除
一般来说，没有类型系统可以防止逻辑/算法错误，（没有程序规范，类型检查器无法“读心”）：
- 反转条件分支
- 调用f而不是g

目的是为了防止某些事情

讨论了有关ML类型系统阻止和不阻止什么的事实
- 尽管之前研究过许多ML的类型规则，但与如何（例如，每个变量使用一种类型）不同
语言设计包括决定检查什么以及如何检查
困难的部分是确保类型系统“实现其目的”
- “如何”完成“什么”
- 后续是更精确的定义

一个关于eager的问题

“在产生影响之前发现错误”与“不要报告可能无关紧要的错误”具有矛盾性
静态检查/动态检查是连续体上的两个点
愚蠢的例子：假设我们只想阻止评估3/0
- 关键时间：在编辑器中禁止它
- 编译时间：如果在代码中看到，则禁止它
- 链接时间：如果在可能被main调用的代码中看到，则不允许它
- 运行时间：当我们到达分区时禁止它
- 更晚：不做除法，而是返回+inf.0
  - 就像每个PL中的3.0 / 0.0一样（它很有用！）

健全性和完备性

正确性

假设一个类型系统应该阻止执行X
- 一个类型系统是健全的，如果它从不接受一个执行X的程序
  - 没有false negatives
- 如果一个类型系统从不拒绝一个不会执行X的程序，则该类型系统是完备的
  - 没有false positives
目标通常是使PL类型系统健全（因此你可以依赖它）但不完备
注意健全性/完备性是关于X

不完备性

ML拒绝了如下几个函数，即使它们不除以字符串：

fun f1 x = 4 div "hi" (* but f1 never called *)

fun f2 x = if true then 0 else 4 div "hi"

fun f3 x = if x then 0 else 4 div "hi"
val x = f3 true

fun f4 x = if x <= abs x then 0 else 4 div "hi"

fun f5 x = 4 div x
val y = f5 (if true then 1 else "hi")

为什么使用不完备性

几乎所有你可能想要静态检查的东西都是不可判定的。
- 任何静态检查器都不能做到以下几点：
  - (1)总是终止
  - (2)健全
  - (3)完备
- 这是一个数学定理！

例子：
- 这个函数会在某些输入上终止吗？
- 这个函数是否会使用一个不在环境中的变量？
- 这个函数会把一个字符串当作一个函数吗？
- 这个函数是否会除以0？
不可知性是计算核心的一个基本概念
- 静态检查的内在近似性可能是其最重要的衍生物

不健全性

假设一个类型系统是不健全的。PL可以做什么？

用一个更新的语言定义来修复它？
根据需要插入动态检查以防止X的发生？
即使”试图阻止它”，也允许X的发生？
更糟的是：如果”程序员出错”，不仅允许X，而且允许任何事情发生
- 接下来将讨论C和C++…

弱类型

为什么采用弱类型（C/C++）？

弱类型：存在这样的程序，根据定义，它们可以通过静态检查，但在运行时却能”让计算机着火”？
- 动态检查是可有可无的，而且在实践中不做
- 为什么可能发生任何事情？
语言实现的便利性：由程序员来进行检查
性能：动态检查需要时间
低级别的：编译器不插入像数组大小这样的信息，所以它不能进行检查。
弱类型是一个糟糕的名字：实际上是既不做静态检查也不做动态检查
- 一个大问题是数组的边界，大多数PL都是动态检查的

弱类型造成了什么

现在已经很少有人说：”strong types for weak minds”
想法是人类总是比类型系统更聪明（参照不可判别性），所以需要让他们”相信我”
现实：人类在避免错误方面真的很糟糕
- 我们需要所有我们能得到的帮助!
- 而类型系统已经变得更有表现力（更少的false positive）
- 在一个用C语言编写的3000万行的操作系统中，一个bug就可能使整个计算机变得脆弱。
- 像这样一个重要的bug可能在本周公布（因为几乎每周都有）。

例子：Racket

Racket不是弱类型
- 它只是动态地检查大多数东西
  - 静态检查模块中的宏使用和未定义变量
- 动态检查的定义是
  - 如果实现可以分析代码以确保不需要某些检查，那么它就可以将其优化。
没有ML或Java的规则会很方便
- cons单元可以构建任何东西
- 除了#f以外的任何东西都是真的
- 这与弱类型的”catch-fire语义”完全不同

另一个误解

原语是在什么操作上定义的，什么时候出错？
- 例子："foo" + "bar"允许吗？
- 例子："foo"+3是否允许？
- 例子：如果arr只有5个元素，是否允许arr[10]?
- 例子：你可以用太少或太多的参数来调用一个函数吗？
这不是静态检查vs动态检查（有时与之相混淆）
- 它是”原语的运行时语义是什么”
- 它是相关的，因为它也涉及到在更快地捕获bug和更方便地捕获bug之间的权衡。
Racket在这些方面通常没有Ruby那么宽松。

静态类型vs动态类型，第一部分

现在可以讨论

在仔细陈述了关于静态检查的事实后，现在可以考虑关于哪个更好的争论：静态检查或动态检查
请记住大多数语言都会做其中的一部分
- 例如，也许原语的类型是静态检查的，但数组的边界不是。

声明 1a: 动态类型更方便

动态类型可以让你建立一个异质列表或返回一个”数字或字符串”而不需要大的类型。

Racket:

(define (f y)
  (if (> y 0) (+ y y) "hi"))
  
(let ([ans (f x)])
  (if (number? ans) (number->string ans) ans))

ML:

datatype t = Int of int | String of string 
fun f y = if y > 0 then Int(y+y) else String "hi" 

case f x of
   Int i => Int.toString i 
 | String s => s

声明 1b: 静态类型更方便

可以假设数据具有预期的类型，而不需要用动态检查使代码杂乱无章，或在逻辑错误以外的地方出现错误。

Racket:

(define (cube x) 
  (if (not (number? x)) 
      (error "bad arguments") 
      (* x x x))) 
      
(cube 7)

ML:

fun cube x = x * x * x

cube 7

声明 2a: 静态类型阻止了有用的程序

任何健全的静态类型系统迫使程序员围绕限制进行编码。

Racket:

(define (f g)
  (cons (g 7) (g #t)))
  
(define pair_of_pairs
  (f (lambda (x) (cons x x))))

ML:

fun f g = (g 7, g true) (* does not type-check *)

val pair_of_pairs = f (fn x => (x,x))

声明 2b：静态类型允许你根据需要进行标记

静态类型语言允许程序员“根据需要进行标记”（例如，使用数据类型），而不是承受标记所有内容的时间、空间和后期错误成本。
在极端情况下，可以在 ML 中使用“TheOneRacketType”
- 在实际中极少需要

datatype tort = Int of int
              | String of string
              | Cons of tort * tort
              | Fun of tort -> tort
              | …
if e1
then Fun (fn x => case x of Int i => Int (i*i*i))
else Cons (Int 7, String "hi")

声明3a：静态类型更早地捕获错误

静态类型一“编译”就捕获了许多简单的错误
- 由于此类错误总是被捕获，因此无需对其进行测试
- 事实上，可以不那么仔细地编码并“依靠”类型检查器

Racket:

(define (pow x) ; curried 
  (lambda (y) 
    (if (= y 0) 
        1 
        (* x (pow x (- y 1)))))) ; oops

ML:

fun pow x y = (* does not type-check *)
  if y = 0
  then 1
  else x * pow (x,y-1)

声明3b：静态只捕获简单的错误

但是静态通常只捕获“简单”的错误，所以你仍然需要测试你的函数，它也应该找到“简单”的错误。

例子同上。

静态类型vs动态类型，第二部分

申明 4a：静态类型更快

语言实现：
- 不需要存储标签（空间、时间）
- 不需要检查标签（时间）
你的代码：
- 不需要检查参数和结果

申明 4b：动态类型更快

语言实现：
- 可以使用优化去除一些不必要的标签和测试
  - 示例：(let ([x (+ y y)]) (* x 4))
- 虽然这通常很难（不可能），但对于程序的性能关键部分来说通常更容易
你的代码：
- 不需要使用额外的标签、函数等“绕过”类型系统限制

申明5a：动态类型更容易重用代码

没有限制性的类型系统，更多的代码可以被不同类型的数据重用
- 如果你对所有内容都使用cons单元，则适用于cons的库很有用
- 集合库非常有用，但通常具有非常复杂的静态类型

申明5b：静态类型更容易重用代码

现代类型系统应该支持合理的代码重用，以及泛型和子类型等特性
如果你对所有内容都使用cons单元，你将混淆什么代表什么并得到难以调试的错误
- 使用单独的静态类型将想法分开
- 静态类型有助于避免库误用

到目前为止

考虑5件编写代码时的重要事：

便利性
不阻止有用的程序
及早发现错误
性能
代码复用

或许会天真地认为，软件是通过采用现有规范、对其进行编码、测试并宣布胜利来开发的。

现实：

在规范稳定之前，通常会进行大量原型设计
1.0版本后经常进行大量的维护/更新

申明6a：动态类型更适用于原型设计

早期，你可能不知道在数据类型和函数中需要什么情况

但是静态类型不允许没有包含全部情况的代码；动态类型运行不完整的程序运行
所以你可以对数据结构做出过早的承诺
并最终编写代码来安抚你后来丢弃的类型检查器
- 在制作原型时特别令人沮丧

申明6b：静态类型更适用于原型设计

有什么比使用类型系统更好的方法来记录你对数据结构和代码案例的不断发展的决策？

新的、不断发展的代码最有可能做出不一致的假设

必要时易于放入临时存根，例如

| _ => raise Unimplemented

申明7a：动态类型更利于改进

可以在不影响旧调用者的情况下将代码更改为更宽松

示例：采用int或string而不是int
所有ML调用者现在必须在参数上使用构造函数并在结果上使用模式匹配
现有的Racket调用者可能没有注意到

申明 7b：静态更利于改进

当我们更改数据或代码的类型时，类型检查器会为我们提供必须更改的所有内容的“待办事项”列表
- 避免引入错误
- 类型中的规范越多，类型检查器列出的规范更改时要更改的内容就越多
示例：更改函数的返回类型
示例：向数据类型添加新的构造函数
- 不使用通配符模式的充分理由
反驳意见：待办事项清单是强制性的，这使得分段改进很痛苦：无法进行中途测试

结尾

静态与动态类型的问题太粗略了
- 更好的问题：我们应该静态执行什么？
你应该知道的合理权衡
- 以事实为依据的理性讨论！
理想情形（？）：允许两全其美的灵活语言？
- 程序员会很好地利用这种灵活性吗？谁决定？

可选：`eval`和`quote`

评估

Racket，Scheme，LISP，Javascript，Ruby，……有eval

在运行时创建一些数据（在Racket中是一个嵌套列表，在Javascript中是一个字符串）
然后把数据当成程序来运行
由于我们不提前知道将创建什么数据，因此我们需要在运行时实现语言实现以支持eval
- 可以是解释器、编译器、组合
- 但是确实需要在任何包含eval的程序中“提供语言实现”

Racket中的`eval`

eval的适当习语是一个争论话题
- 通常但并非总是有更好的方法
- 带有eval的程序更难分析
我们不会使用eval，但没有必要让它变得神秘
- 它适用于符号和其他值的嵌套列表
- 从具体/抽象语法相似性中获益

(define (make-some-code y) ; just returns a list 
  (if y 
     (list 'begin (list 'print "hi") (list '+ 4 2)) 
     (list '+ 5 3))) 

(eval (make-some-code #t)) ; prints "hi", result 6

quote

引用(quote ...)或'(...)是一种特殊形式，它使“下面的一切”是原子和列表，而不是变量和调用
- 但随后调用eval将符号查找为代码
- 所以quote和eval是相反的
- 如下两段代码等价：
```
(list 'begin (list 'print "hi") (list '+ 4 2))

(quote (begin (print "hi") (+ 4 2)))
```
还有准引用
- 下面的所有内容都是原子和列表，除非没有引用
- Ruby、Python、Perl eval字符串等语言并支持将表达式放入字符串中，即准引用
如果好奇，请参阅Racket指南

B部分总结和C部分预览

到目前为止的课程概述

A部分：

基础知识、函数、递归、作用域、变量、元组、列表……
数据类型、模式匹配、尾递归
头等函数、闭包[和课程动机！]
类型推断、模块、等价

B部分：

动态类型、括号、延迟评估、流、宏
结构、解释器、闭包、静态检查、静态类型与动态类型

C部分：

动态类型的面向对象编程Ruby基础知识、数组、块、类、方法等等……
OOP与函数式分解，高级OOP主题（例如 mixins、双重分派），泛型与子类型

完成故事

即使你“已经了解 OOP”，也强烈建议你继续

（整个）重点是以类似的方式研究OOP主题并与FP进行比较/对比
一些具有OOP背景的人发现7 “不太有趣”，但请继续关注8，它建立在7之上
- Homework 6 也适用于不同的经验水平
有些人认为C部分是“反对OOP”，这不正确
将在C部分了解更多关于FP的信息……
将OOP的动态调度实现为Racket中的习语
FP与OOP分解是一个重要的“aha”时刻
作业7涉及在更改分解的同时将ML移植到Ruby
- 它也是另一种“解释器”，用于没有闭包的“几何语言”
ML的类型变量与（Java）泛型和子类型的关系

Week 4

ML vs Racket

主要区别

即将到来的主题

从Racket的角度来看ML

从ML的角度来看Racket

更多关于一种大类型

什么是静态检查？

静态检查

示例：ML，什么类型可以阻止

示例：ML，允许哪些类型

目的是为了防止某些事情

一个关于eager的问题

健全性和完备性

正确性

不完备性

为什么使用不完备性

不健全性

弱类型

为什么采用弱类型（C/C++）？

弱类型造成了什么

例子：Racket

另一个误解

静态类型vs动态类型，第一部分

现在可以讨论

声明 1a: 动态类型更方便

声明 1b: 静态类型更方便

声明 2a: 静态类型阻止了有用的程序

声明 2b：静态类型允许你根据需要进行标记

声明3a：静态类型更早地捕获错误

声明3b：静态只捕获简单的错误

静态类型vs动态类型，第二部分

申明 4a：静态类型更快

申明 4b：动态类型更快

申明5a：动态类型更容易重用代码

申明5b：静态类型更容易重用代码

到目前为止

申明6a：动态类型更适用于原型设计

申明6b：静态类型更适用于原型设计

申明7a：动态类型更利于改进

申明 7b：静态更利于改进

结尾

可选：eval和quote

评估

Racket中的eval

quote

B部分总结和C部分预览

到目前为止的课程概述

完成故事

可选：`eval`和`quote`

Racket中的`eval`