Programming Languages Part B Week 3笔记

这次回顾Part B Week 3的内容，主要介绍了Struct以及如何在Racket中实现一个简单的编程语言的解释器。

课程主页：

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

B站搬运：

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

Week 3

在Racket中进行无结构的数据类型编程

没有数据类型的生活

• Racket没有支持one-of类型的数据类型绑定
• 在一个动态类型的语言中没有必要。
  • 可以混合不同类型的值，使用number?, string?, pair?,等原语来 “查看你有什么”。
  • 可以使用cons单元来建立任何类型的数据
• 这一节：用我们已经知道的东西编写数据类型的代码
• 下一节：用结构体做同样的事情的更好方法
  • 对比有助于解释结构的优势

混合集合

• 在ML中，不能有一个”ints或strings”的列表，所以要使用数据类型

  datatype int_or_string = I of int | S of string 
  
  fun funny_sum xs = (* int_or_string list -> int *) 
     case xs of 
          [] => 0
        | (I i)::xs’ => i + funny_sum xs’ 
        | (S s)::xs’ => String.size s + funny_sum xs’

• 在Racket中，动态类型使其自然而然地不需要明确的标签

  • 取而代之的是，每个值都有一个带有原语的标签来检查它
  • 所以只需用number?或string?来检查列表的car

递归结构

我们知道更多有趣的数据类型编程：

datatype exp = Const of int | Negate of exp | Add of exp * exp | Multiply of exp * exp

fun eval_exp e = 
   case e of 
        Constant i => i 
      | Negate e2 => ~ (eval_exp e2) 
      | Add(e1,e2) => (eval_exp e1) + (eval_exp e2) 
      | Multiply(e1,e2)=>(eval_exp e1)*(eval_exp e2)

改变我们的做法

• 先前版本的eval_exp的类型为exp->int
• 从现在开始，我们将用exp->exp的类型来写这样的函数
• 为什么？因为我们将解释具有多种结果的语言（ints, pairs, functions, …）
  • 尽管到目前为止的例子要复杂得多
• 如何？请看ML代码文件：
  • 基本情况下返回整个表达式，例如，(Const 17)
  • 递归情况：
    • 检查变体（例如，确保一个Const）
    • 提取数据（例如，Const下的数字）
    • 同时返回一个exp（例如，创建一个新的Const）

Racket中的新方法

• 请看Racket代码文件，为同样的新的”exp->exp“解释器编码
  • 使用列表，其中列表的car编码为”什么样的exp”
• 关键点：
  • 定义我们自己的构造函数、测试变量、提取数据的函数
    • 比起难以阅读的car, cdr的使用，风格更好
  • 同样的递归结构，没有模式匹配
  • 没有类型系统，除了文档中，没有”什么是exp”的概念
    • 但是，如果我们正确地使用辅助函数，那么就可以了
    • 如果需要，可以增加更明确的错误检查

可选的：符号

• 我们不会关注Racket的符号，比如'foo，但简单来说
  • 本质上以引号字符开始
  • 像字符串一样，可以是几乎任何字符序列
  • 与字符串不同的是，用eq?来比较两个符号，这很快

在Racket中使用结构体进行数据类型编程

新功能

(struct foo (bar baz quux) #:transparent)

• 定义了一种新的事物并引入了几个新的函数。
  • (foo e1 e2 e3)返回”a foo“，其中bar, baz, quux字段存放e1, e2和e3的评估结果
  • (foo? e)对e进行评估，当且仅当结果是用foo函数生成的东西时，返回#t
  • (foo-bar e)对e进行求值，如果结果是由foo函数生成的，则返回bar字段的内容，否则为错误
  • (foo-baz e)对e进行求值，如果结果是由foo函数生成的，则返回baz字段的内容，否则错误
  • (foo-quux e)对e进行求值，如果结果是由foo函数产生的，则返回quux字段的内容，否则错误

习语

(struct const (int) #:transparent) 
(struct negate (e) #:transparent) 
(struct add (e1 e2) #:transparent) 
(struct multiply (e1 e2) #:transparent)

• 对于像exp这样的”数据类型”，为每个”exp的种类”创建一个结构
  • 结构就像ML构造函数
  • 但提供构造器、测试器和提取器函数
    • 代替pattern
    • 例如，const, const?, const-int
  • 动态类型意味着”这些是exp的种类”是”在注释中”，而不是一个类型系统
  • 动态类型意味着字段的”类型”也是”在注释中”

我们需要的一切

之前介绍的结构是我们需要的全部内容。

• 构建代表表达式的树，例如：

  (multiply (negate (add (const 2) (const 2)))
            (const 7))

• 构建我们的eval-exp函数（见代码）：

  (define (eval-exp e)
    (cond [(const? e) e] ; note returning an exp, not a number
          [(negate? e) (const (- (const-int (eval-exp (negate-e e)))))]
          [(add? e) (let ([v1 (const-int (eval-exp (add-e1 e)))]
                          [v2 (const-int (eval-exp (add-e2 e)))])
                      (const (+ v1 v2)))]
          [(multiply? e) (let ([v1 (const-int (eval-exp (multiply-e1 e)))]
                               [v2 (const-int (eval-exp (multiply-e2 e)))])
                           (const (* v1 v2)))]
          [#t (error "eval-exp expected an exp")]))

属性

• #: transparent是结构定义上的一个可选属性

  • 对我们来说，在REPL中打印结构值，而不是隐藏它们，这对调试作业很方便。

• #: mutable是结构定义的另一个可选的属性

  • 提供了更多的功能，例如：

    (struct card (suit rank) #:transparent #:mutable)
    ; also defines set-card-suit!, set-card-rank!

  • 可以决定每个结构是否支持突变，有通常的优点和缺点

    • 正如预期的那样，我们将避免使用这个属性

  • mcons只是一个预定义的可变结构

结构的优势

方法对比

(struct add (e1 e2) #:transparent)

对比

(define (add e1 e2) (list 'add e1 e2))
(define (add? e) (eq? (car e) 'add))
(define (add-e1 e) (car (cdr e)))
(define (add-e2 e) (car (cdr (cdr e))))

这不是语法糖的案例。

关键的区别是

(struct add (e1 e2) #:transparent)

• 调用(add x y)的结果不是一个列表
  • 而且不存在列表，使得add?返回#t
• struct产生了一种新的东西：用一种新的数据来扩展Racket
• 所以在”add”上调用car、cdr或mult-e1是一个运行时错误。

列表方法容易出错

(define (add e1 e2) (list 'add e1 e2)) 
(define (add? e) (eq? (car e) 'add)) 
(define (add-e1 e) (car (cdr e))) 
(define (add-e2 e) (car (cdr (cdr e))))

• 使用car, cdr会破坏抽象性，list-库函数直接在“add表达式”上操作

  • 可能的错误：

    (define xs (list (add (const 1) (const 4)) …))
    (car (car xs))

• 可能产生add?回答错误的函数，例如如下表达式不应该返回#t

  (cons 'add "I am not an add")

优势总结

结构方法：

• 对于定义数据类型来说，风格更好，更简洁
• 在使用数据类型时同样方便
• 但在误用数据类型时能更好地及时发现错误
  • 不会在错误的数据类型上使用访问器函数
  • 不会混淆测试函数

更多关于抽象的内容

Struct方法与Racket的其他特点结合起来甚至更好，这里没有讨论：

• 模块系统可以让我们隐藏构造函数来执行不变性
  • List-approach不会从客户端隐藏cons
  • 动态类型的语言可以通过让模块定义新的类型来拥有抽象的类型
• contract系统让我们检查不变性，即使构造函数是暴露的
  • 例如，”add”的字段也必须是”表达式”

结构是特殊的

• 通常我们最终会了解到一些方便的功能可以与其他功能一起编码
• 而结构定义则不是这样
  • 一个函数不能引入多个绑定
  • 无论是函数还是宏都不能创建新的数据类型
    • 构造函数的结果对其他所有测试函数都返回#f：number?，pair?，其他结构的测试函数等。

实现编程语言

典型工作流

1. 字符串
2. 解析
3. 类型检查

解释器或编译器

• 因此，”实现的其余部分”采用抽象语法树（AST）并”运行程序”以产生一个结果
• 从根本上说，有两种方法可以实现PL B：
• 用另一种语言A写一个解释器
  • 更好的名称：评估器、执行器
  • 用B语言编写一个程序，并产生一个答案（用B语言）。
• 用另一种语言A编写一个编译器，将其翻译成第三种语言C
  • 更好的名字：翻译器
  • 翻译必须保持含义（等价）。
• 我们把A称为元语言
  • 保持A和B的一致性至关重要

现实更复杂

• 评估（解释器）和翻译（编译器）是你的选择
  • 但在现实中，两者都有，而且是多层的
• 一个合理的例子
  • Java编译器到字节码的中间语言
  • 有一个字节码的解释器（本身是二进制的），但在运行时将频繁的函数编译为二进制
  • 芯片本身就是二进制的解释器
    • 好吧，除了现在的x86在硬件上有一个翻译器来翻译更原始的微操作，然后执行
• Racket使用了类似的组合

Sermon

• 解释器vs编译器vs组合是关于特定语言实现的，而不是语言定义
• 所以不存在”编译型语言”或”解释型语言”这样的东西
  • 程序无法”看到”实现的工作方式
• 不幸的是，你经常听到这样的句子
  • “C语言更快，因为它是编译的，而LISP是解释的”
  • 这是无稽之谈；礼貌地纠正人们
  • （诚然，带有”eval”的语言必须在每个程序中”附带一些语言的实现”）

跳过解析

• 如果在PL A中实现PL B，我们可以跳过解析
  • 让B程序员直接在PL A中编写AST。
  • 使用ML构造器或Racket结构，情况并不那么糟糕
  • 将B程序作为树植入A中

; define B’s abstract syntax
(struct call …))
(struct function …)
(struct var …)
…

; example B program
(call (function (list “x”)
                (add (var “x”)
                     (var “x”)))
      (const 4))

已经完成了一个例子!

• 元语言A = Racket
• B = “算术语言”
• 用调用Racket构造函数的方式编写算术程序
• 解释器是eval-exp

(struct const (int) #:transparent)
(struct negate (e) #:transparent)
(struct add (e1 e2) #:transparent)
(struct multiply (e1 e2) #:transparent)

(define (eval-exp e)
  (cond [(const? e) e]
        [(negate? e)
         (const (- (const-int
                     (eval-exp (negate-e e)))))]
        [(add? e) …]
        [(multiply? e) …]…

你的解释器可以和不可以假设什么？

我们所知道的

• 用Racket结构定义B语言的（抽象）语法
  • 在家庭作业中把B语言称为MUPL
• 通过构造函数在Racket中直接编写B语言程序
• 将B语言的解释器作为一个（递归的）Racket函数来实现
• 现在，一个微妙但重要的区别：
  • 解释器可以假定输入是一个”B的合法AST”。
    • 否则，可以给出错误的答案或难以捉摸的错误
  • 解释器必须检查递归结果是否是正确的值
    • 否则给出一个错误信息

合法的ASTs

• “解释器必须处理的树”是Racket作为一种动态类型语言所允许的所有树的一个子集

  (struct const (int) #:transparent)
  (struct negate (e) #:transparent)
  (struct add (e1 e2) #:transparent)
  (struct multiply (e1 e2) #:transparent)

• 可以为结构字段假定”正确的类型”

  • const持有一个数字
  • negate持有一个合法的AST
  • add和multiply持有两个合法AST

• 不合法的AST会使解释器”崩溃”，这很好

  (multiply (add (const 3) "uh-oh") (const 4))
  (negate -7)

解释器的结果

• 我们的解释器返回表达式，但不是任何表达式
  • 结果应该总是一个值，一种对自身求值的表达式
  • 如果不是，解释器就有一个错误
• 到目前为止，只有值来自const，例如，(const 17)
• 但是一个更大的语言有更多的值，而不仅仅是数字
  • 布尔值，字符串，等等。
  • 值的pair（值的定义递归）
  • 闭包
  • …

例子

请看增加了布尔运算、数字比较和条件语句的语言的代码：

(struct bool (b) #:transparent) 
(struct eq-num (e1 e2) #:transparent)
(struct if-then-else (e1 e2 e3) #:transparent)

如果程序是一个合法的AST，但对它的评估试图使用错误的数值种类，怎么办？

• 例如，”add布尔值”
• 你应该检测到这一点，并给出一个错误信息，而不是在解释器的实现方面
• 意味着每当需要一个特定种类的值时，都要检查一个递归的结果
  • 不需要检查任何种类的值是否合适

实现变量和环境

处理变量

• 到目前为止，解释器都是针对没有变量的语言的
  • 没有let-expressions、带参数的函数，等等。
  • 家庭作业中的语言有所有这些东西
• 这段话用英语描述了要做什么
  • 由你来把它翻译成代码
• 幸运的是，你要实现的是我们从课程一开始就一直强调的东西
• 环境是变量（Racket字符串）与值（由语言定义）之间的映射。
  • 只在环境中放入成对的字符串和值
• 评估是在环境中进行的
  • 环境作为参数传递给解释器辅助函数
  • 一个变量表达式在环境中查找变量
  • 大多数子表达式使用与外层表达式相同的环境
  • 一个let-expression在一个更大的环境中评估其主体

设置

• 所以现在一个递归辅助函数拥有所有有趣的东西：

  (define (eval-under-env e env)
      (cond … ; case for each kind of
       )) ; expression

  • 递归调用必须”向下传递 “正确的环境

• 然后eval-exp只是用相同的表达式和空环境调用eval-under-env

• 在家庭作业中，环境本身只是Racket列表，包含一个字符串（MUPL变量名称，例如，”x“）和一个MUPL值（例如，(int 17)）的Racket对。

一个评分的细节

• 风格上，eval-under-env是一个辅助函数，可以在eval-exp中本地定义
• 但不要在你的作业中这样做
  • 我们有直接调用eval-under-env的评分测试，所以我们需要它在顶层

实现闭包

最精彩的部分

• 作业中最有趣和最令人费解的部分是，正在实现的语言具有头等的闭包性
  • 当然是有词法范围的
• 幸运的是，你要实现的是我们第一次学习闭包时就一直强调的…

高阶函数

• “魔法”：当函数可能返回其他函数、将其存储在数据结构中等，我们如何使用词法范围的”正确环境”？

• 没有魔法：解释器使用一个封闭的数据结构（有两个部分）来保持它以后需要使用的环境

  (struct closure (env fun) #:transparent)

• 评估一个函数表达式：

  • 一个函数不是一个值，一个闭包是一个值
  • 评估一个函数会返回一个闭包
  • 从（a）函数和（b）函数被评估时的当前环境中创建一个闭包

• 评估一个函数调用

  • 见后续

函数调用

(call e1 e2)

• 利用当前环境将e1评估为一个闭包
  • 如果结果是一个不属于闭包的值，则出现错误
• 使用当前环境将e2评估为一个值
• 在闭包的环境中评估闭包的函数体，扩展为：
  • 将函数的参数名映射到参数值上
  • 对于递归，将函数的名称映射到整个闭包
• 这就是我们几周前学过的”编码”的相同语义
• 给定一个闭包，代码部分永远只使用环境部分（扩展）进行评估，而不是在调用地的环境

可选：闭包的效率高吗？

这开销很大吗？

• 建立一个闭包的时间开销很小：一个有两个字段的结构
• 如果环境很大，存储闭包的空间可能会很大
  • 但环境是不可改变的，所以有大量的共享是自然而然的，例如，列表的尾部（参考第3讲）
  • 尽管如此，最终还是要保留一些不需要的绑定
• 在实践中使用的替代方法：当创建一个闭包时，存储一个可能更小的环境，只保存函数体中的自由变量。
  • 自由变量：出现但没有被shadowed的变量
  • 一个函数体将永远不需要环境中的其他东西

自由变量例子

(lambda () (+ x y z)) ; {x, y, z}
(lambda (x) (+ x y z)) ; {y, z}
(lambda (x) (if x y z)) ; {y, z}
(lambda (x) (let ([y 0]) (+ x y z))) ; {z}
(lambda (x y z) (+ x y z)) ; {}
(lambda (x) (+ y (let ([y z]) (+ y y)))) ; {y, z}

计算自由变量

• 那么，解释器每次创建闭包时都要分析代码体吗？
• 不：在评估开始之前，计算程序中每个函数的自由变量，并将这些信息与函数一起存储。
• 与朴素地存储整个环境的方法相比，现在建立一个闭包需要更多的时间，但空间更小。
  • 而且时间与自由变量的数量成正比
  • 而且可以进行各种优化
• [同时使用比列表更好的数据结构来查找变量]

编译高阶函数

• 如果我们要编译到一种没有闭包的语言（如汇编），就不能依赖”当前环境”。
• 所以在编译函数时，让翻译产生”常规”函数，这些函数都需要一个额外的明确参数”环境”。
• 编译器用使用环境参数查找变量的代码来取代所有自由变量的使用。
  • 可以通过一些技巧使这些操作快速化
• 运行中的程序仍然会创建闭包，每个函数调用都会将闭包的环境传递给闭包的代码

Racket函数作为解释语言的“宏”

回顾

• 我们实现语言的方法：
  • 在A语言中实现B语言
  • 直接用A语言的构造函数来编写B语言的程序，从而跳过解析。
  • 用A语言编写的解释器递归地进行评估。
• 我们对宏的了解：
  • 扩展了语言的语法
  • 在程序运行之前，即在调用解释器主函数之前，使用宏会扩展语言的语法。

小结

• 通过我们的设置，我们可以使用产生B语言抽象语法的A语言（即Racket）函数作为B语言”宏”：
  • 语言B的程序可以使用这些”宏”，就像它们是语言B的一部分一样
  • 不改变解释器或结构定义
  • 只是通过我们的设置启用了一个编程习语
    • 有助于教授什么是宏
  • 参见代码，了解”宏”的定义和”宏”的用途
    • “宏扩展”发生在调用eval-exp之前

可选：hygiene问题

• 早些时候，我们有关于宏的hygiene问题的（可选）材料
  • （除其他外），在使用局部变量以避免多次评估表达式时的shadowing变量问题
• 这里描述的”宏”方法并不能很好地解决这个问题。