Programming Languages Part B Section6 翻译

这里对Section 6进行翻译。

课程主页：

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

B站搬运：

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

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

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

目录

• 不使用数据类型的数据类型编程
• 改变我们对算术表达式数据类型的评估方式
• 通过Racket列表的递归数据类型
• 通过Racket的struct实现递归数据类型
• 为什么struct方法更好
• 实现一般的编程语言
• 在另一种语言中实现一种编程语言
• 关于合法AST的假设和非假设
• 有变量的语言的解释器需要环境
• 实现闭包
• 可选：更有效地实现闭包
• 通过元语言中的函数定义”宏”

不使用数据类型的数据类型编程

在ML中，我们使用数据类型绑定来创建我们自己的one-of类型，包括用于树状数据的递归数据类型，例如用于算术表达式的小语言。数据类型绑定在静态环境中引入了一个新的类型，以及用于创建该类型数据的构造器和用于使用该类型数据的模式匹配。Racket作为一种动态类型的语言，没有直接对应于数据类型绑定的东西，但它确实支持同样的数据表示和编程。

首先，我们在ML中需要数据类型的一些情况在Racket中更简单，因为我们可以直接使用动态类型将任何类型的数据放在我们想要的地方。例如，我们知道ML中的列表是多态的，但是任何特定的列表都必须有相同类型的元素。所以我们不能直接建立一个持有“string和ints”的列表。但是，我们可以用一个数据类型来解决这个限制，就像这个例子一样：

datatype int_or_string = I of int | S of string

fun funny_sum xs =
    case xs of
        [] => 0
      | (I i)::xs' => i + funny_sum xs'
      | (S s)::xs' => String.size s + funny_sum xs'

在Racket中，不需要这样的变通方法，因为我们可以直接写出对元素为数字或字符串的列表有效的函数：

(define (funny-sum xs)
  (cond [(null? xs) 0]
        [(number? (car xs)) (+ (car xs) (funny-sum (cdr xs)))]
        [(string? (car xs)) (+ (string-length (car xs)) (funny-sum (cdr xs)))]))

对这种方法至关重要的是，Racket有内置的基元，如null?, number?和string?，用于在运行时测试数据的类型。

但对于像这种用于算术表达式的ML表示法的递归数据类型：

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

将我们的编程习惯适应于Racket将被证明是更有趣的。

我们将首先考虑一个评估exp类型的ML函数，但这个函数的返回类型与我们在课程早期编写的类似函数不同。然后我们将考虑在Racket中为算术表达式定义和使用这种类型的两种不同方法。我们将论证第二种方法更好，但第一种方法对于理解Racket的总体情况和第二种方法特别重要。

改变我们对算术表达式数据类型的评估方式

最明显的函数是对算术表达式进行求值并返回结果的函数，该函数需要接收上述ML数据类型的值。以前，我们这样写一个函数：

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

eval_exp_old的类型是exp->int。特别是，返回类型是int，一个ML整数，然后我们可以使用ML的算术运算符进行加法、乘法等。

在本模块的其余部分，我们将改写这类函数以返回exp，因此ML类型将变成exp->exp。调用的结果（包括递归调用）将具有Const i的形式（对于某个int i），例如Const 17。调用者必须检查返回的exp的种类确实是Const，提取基础数据（在ML中，使用模式匹配），然后自己根据需要使用Const构造函数来返回exp。对于我们的小算术语言，这种方法导致了一个相当复杂的程序：

exception Error of string

fun eval_exp_new e =
    let
	fun get_int e =
	    case e of
		Const i => i
	      | _ => raise (Error "expected Const result")
    in
	case e of
         Const _ => e
	  | Negate e2  => 
	    Const (~ (get_int (eval_exp_new e2)))
	  | Add(e1,e2) => 
	    Const ((get_int (eval_exp_new e1)) + (get_int (eval_exp_new e2)))
	  | Multiply(e1,e2) => 
	    Const ((get_int (eval_exp_new e1)) * (get_int (eval_exp_new e2)))
    end

这种额外的复杂化对我们简单的类型exp没有什么好处，但我们这样做有一个非常好的理由。不久之后，我们就会开始设计有多种结果的小语言。假设一个计算的结果不一定是一个数字，因为它也可以是一个布尔值、一个字符串、一个pair、一个函数闭包等等。那么我们的eval_exp函数需要返回某种one-of类型，而使用exp类型所表示的可能性的一个子集将很好地满足我们的需要。然后，像加法这样的eval_exp案例将需要检查递归的结果是否是正确的数值类型。如果这个检查不成功，那么上面那行引发异常的get_int就会被评估（而对于我们到目前为止的简单例子，异常永远不会被引发）。

通过Racket列表的递归数据类型

在我们写一个类似于上述ML eval_exp_new函数的Racket函数之前，我们需要确定算术表达式本身。我们需要一种方法来构造常量、相反数、加法和乘法，需要一种方法来测试我们有什么样的表达式（例如：这是否是加法），以及一种方法来访问这些表达式（例如：获取加法的第一个子表达式）。在ML中，数据类型绑定给了我们这一切。

在Racket中，动态类型让我们可以使用列表来表示任何类型的数据，包括算术表达式。 一个古老的习惯是用第一个列表元素来表示”这是什么东西”，然后用后续的列表元素来保存基础数据。用这种方法，我们可以用自己的Racket函数来构造、测试和访问：

; just helper functions that make lists where first element is a symbol
; Note: More robust could check at run-time the type of thing being put in
(define (Const i) (list 'Const i))
(define (Negate e) (list 'Negate e))
(define (Add e1 e2) (list 'Add e1 e2))
(define (Multiply e1 e2) (list 'Multiply e1 e2))

; just helper functions that test what "kind of exp"
; Note: More robust could raise better errors for non-exp values
(define (Const? x) (eq? (car x) 'Const))
(define (Negate? x) (eq? (car x) 'Negate))
(define (Add? x) (eq? (car x) 'Add))
(define (Multiply? x) (eq? (car x) 'Multiply))

; just helper functions that get the pieces for "one kind of exp"
; Note: More robust could check "what kind of exp"
(define (Const-int e) (car (cdr e)))
(define (Negate-e e) (car (cdr e)))
(define (Add-e1 e) (car (cdr e)))
(define (Add-e2 e) (car (cdr (cdr e))))
(define (Multiply-e1 e) (car (cdr e)))
(define (Multiply-e2 e) (car (cdr (cdr e))))

(作为说明，我们以前没有见过'foo这个语法。这是一个Racket符号。就我们的目的而言，符号'foo很像字符串"foo"，你可以使用任何字符序列，但符号和字符串是不同的东西。比较两个符号是否相等是一个快速的操作，比字符串相等要快。你可以用eq?来比较符号，而你不应该将eq?用于字符串。我们可以用字符串来做这个例子，用equal?而不是eq?)。

现在我们可以写一个Racket函数来”评估”一个算术表达式。它类似于eval_exp_new中的ML版本，只是用我们的辅助函数代替了数据类型构造器和模式匹配：

(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")]))

同样地，我们可以使用我们的辅助函数来定义算术表达式：

(define test-exp (Multiply (Negate (Add (Const 2) (Const 2))) (Const 7))) 
(define test-ans (eval-exp test-exp))

注意，test-ans是'(Const -28)，而不是-28。

还注意到，在动态类型下，程序中没有任何东西表示什么是算术表达式。只有我们的文档和注释会指出算术表达式是如何在常量、相反数、加法和乘法方面构建的。

通过Racket的struct定义递归数据类型

上面定义算术表达式的方法不如我们现在介绍的使用Racket中特殊结构体的第二种方法。一个struct表示法看起来像：

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

这就定义了一个名为foo的新结构，就像一个ML构造器。它为环境添加了构建foo的函数，测试某物是否为foo，以及从foo中提取字段bar, baz, quux。这些绑定的名称是由构造函数名称foo系统地形成的，如下所示：

• foo是一个接收三个参数并返回一个值的函数，该值是一个具有容纳第一个参数的bar字段、容纳第二个参数的baz字段和容纳第三个参数的quux字段的foo。
• foo?是一个接受一个参数的函数，对于通过调用foo创建的值返回#t，对于其他的值返回#f。
• foo-bar是一个函数，它接收foo，并返回bar字段的内容，如果传递的不是foo，则引发错误。
• foo-baz是一个函数，它接收foo并返回baz字段的内容，如果传递的不是foo，则引发错误。
• foo-quux是一个函数，它接收foo并返回quux字段的内容，如果传递的不是foo，则引发错误。

我们可以在结构定义中加入一些有用的属性来修改它们的行为，我们在这里讨论其中的两个。

首先，#:transparent属性使字段和访问函数在定义结构的模块之外也能看到。从模块化的角度来看，这种风格值得商榷，但在使用DrRacket时，它有一个很大的优势。它允许REPL打印结构值及其内容，而不仅仅是抽象值。例如，根据我们对结构foo的定义，(foo "hi" (+ 3 7) #f)的结果会打印为(foo "hi" 10 #f)。如果没有#:transparent属性，它将打印为#<foo>，而调用foo函数产生的每个值都将以同样的方式打印。这个特性对于检查从结构的递归使用中建立的值来说变得更加有用。

其次，#:mutable属性使所有的字段都是可变的，它还提供了set-foo-bar!, set-foo-baz!, set-foo-quux!等变体函数。简而言之，程序员在设计结构时决定拥有可改变的字段是否利大于弊。我们也可以让某些字段可变，而某些字段不可变。

我们可以使用结构来定义一种新的方式来表示算术表达式，以及一个评估这种算术表达式的函数：

(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] ; 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")]))

就像我们之前的方法一样，语言中没有任何东西表明算术表达式是如何用常数、取反、加法和乘法来表示的。这个版本的eval-exp的结构与之前的版本几乎相同，只是使用了结构定义提供的函数而不是我们自己的列表处理函数。使用构造函数来定义表达式也是类似的：

(define test-exp (multiply (negate (add (const 2) (const 2))) (const 7)))
(define test-ans (eval-exp test-exp))

为什么struct方法更好

命名结构并不是我们一开始使用的列表方法的语法糖。关键的区别在于，结构定义创造了一种新的值类型。给定

(struct add (e1 e2) #: transparent)

函数add返回的内容会导致add?返回#t，而其他所有类型测试函数如number?, pair?, null?, negate?, multiply?返回#f。同样，访问一个add值的e1和e2字段的方法是使用add-e1和add-e2——使用car, cdr, multiply-e1等是一个运行时错误。(反之，add-e1和add-e2对任何不是add的内容都会产生错误）。

请注意，我们之前使用的列表的方法并不具备这些特性。从我们所说的Add函数构建的内容是一个列表，所以pair?对它返回#t，并且我们可以（尽管它的风格很差），直接用car和cdr访问这些片段。

除了更简洁之外，我们基于结构的方法也更有优势，因为它能更快地发现错误。在我们的算术语言中对一个加法表达式使用cdr或Multiply-e2几乎肯定是个错误，但我们基于列表的方法认为这只不过是使用Racket原语访问一个列表。同样，没有什么能阻止我们的代码的一个不明智的客户写(list 'Add "hello")，然而我们的基于列表的Add?函数会在给出结果列表’(Add "hello")时返回#t。

也就是说，我们在这里使用的结构名称并没有真正执行不变性。特别是，我们希望确保任何add表达式的e1和e2字段只包含其他算术表达式。Racket有很好的方法来做到这一点，但我们在这里不研究它们。首先，Racket有一个模块系统，我们可以用它来向客户端公开结构定义的部分内容，所以我们可以隐藏构造函数，并公开一个不同的函数来保证不变性（就像我们对ML的模块系统所做的那样）。（许多人错误地认为动态类型语言不能像这样强制执行模块化。Racket的结构以及其他语言中的类似功能对此进行了说明。 你不需要抽象类型和静态类型来强制执行 ADT。 有一种方法可以创建新类型，然后不直接公开这些类型的构造函数。）其次，Racket有一个contract系统，允许程序员定义任意的函数，用来检查结构字段的属性，比如只允许字段中出现某些类型的值。

最后，我们注意到Racket的struct是一个强大的原语，不能用其他东西来描述或表示，比如函数表示或宏表示。它确实创造了一种新的数据类型。使add的结果导致add?返回#t，而其他类型的测试则返回#f，这种特性是任何列表、函数、宏等方法都无法做到的。除非语言给了你一个制造这样的新类型的原语，否则任何其他的算术表达式的代码都必须制造一些导致其他类型测试的值，例如使得如pair?或procedure?返回#t。

实现一般的编程语言

虽然这门课程主要是关于编程语言特征的含义，而不是如何实现它们，但实现一种小型编程语言仍然是一种宝贵的经验。首先，理解一些特性的语义的一个好方法是必须实现这些特性，这迫使你思考所有可能的情况。第二，它打消了像高阶函数或对象这样的东西是”魔法”的想法，因为我们可以用更简单的特性来实现它们。第三，许多编程任务类似于实现一种编程语言的解释器。例如，处理像pdf文件这样的结构化文件，并将其转化为用于显示的矩形像素，类似于将一个输入程序转化为一个答案。

我们可以把一个语言实现的典型工作流描述如下。首先，我们取一个字符串，包含该语言中程序的具体语法。一般来说，这个字符串是一个或多个文件的内容。如果这个字符串在语法上不符合要求，解析器就会出错，这意味着这个字符串不可能包含某个语言的程序，因为它存在着诸如误用关键词、错位的括号等问题。如果没有这样的错误，解析器就会产生一棵树，代表这个程序。这就是所谓的抽象语法树，简称AST。对于语言实现的下一步，它是一个更方便的表示。如果我们的语言包括类型检查规则或其他原因，AST可能仍然不是一个合法的程序，类型检查器将使用这个AST来产生错误信息或不产生错误信息。然后，AST被传递给实现的其他部分。

对于实现某个编程语言B的其余实现，基本上有两种方法。第一种，我们可以用另一种语言A写一个解释器，接收B的程序并产生答案。把这样的程序称为B的评估器（evaluator）或B的执行器（executor）可能更有意义，但B的解释器（interpreter）几十年来一直是标准术语。第二种，我们可以在另一种语言A中编写一个编译器，该编译器接收B中的程序，并在其他语言C（不一定是C语言）中产生等效的程序，然后使用一些预先存在的C的实现。一个比 “编译器”更好的术语是”翻译器”，但”编译器”这个术语又是无处不在的。无论是解释器方法还是编译器方法，我们都把A，即我们编写B的实现的语言，称为元语言。

虽然有很多纯正的解释器和编译器，但现代系统往往结合了每种解释器和编译器的各个方面，并使用多层次的解释和翻译。例如，一个典型的Java系统将Java源代码编译成一种可移植的中间格式。然后，Java虚拟机可以开始解释这种格式的代码，但通过进一步将代码编译成可以直接在硬件上执行的代码，可以获得更好的性能。我们可以把硬件本身看作是用晶体管编写的解释器，然而许多现代处理器实际上在硬件中都有翻译器，在执行前就把二进制指令转换成更小的简单指令。即使是这个运行程序的多层故事也有许多变化和增强，但从根本上说，每一步都是解释或翻译的某种组合。

一句说教的话：解释器与编译器是特定编程语言实现的一个特征，而不是编程语言的一个特征。在计算机科学中，有一个更恼人、更普遍的误解，那就是有诸如C等编译语言和诸如Racket等解释语言。这是无稽之谈：我可以为C写一个解释器，也可以为Racket写一个编译器。(事实上，DrRacket采取的是一种混合方法，与Java并无不同。）C语言用编译器实现，而函数式语言用解释器实现的历史很长，但函数式语言的编译器已经存在了几十年。例如，SML/NJ就将每个模块/绑定编译为二进制代码。

在另一种语言中实现一种编程语言

我们上面用于算术表达式的eval-exp函数是一个小型编程语言的解释器的完美例子。这里的语言正是由常量、取反、加法和乘法表达式的构造函数正确构建的表达式。适当的指称取决于语言；在这里，我们的意思是常数用数字表示，相反数/加法/乘法持有其他适当的子表达式。我们还需要为我们的小语言提供一个值（即结果）的表示，这也是语言表示的一部分。这里我们指的是常数，即由常数构造器构建的表达式子集。那么eval-exp就是一个解释器，因为它是一个函数，可以接收我们语言中的表达式，并根据我们语言的语义规则产生我们语言中的值。Racket只是一种元语言，是我们编写解释器的”另一种”语言。

解析和类型检查怎么了？简而言之，我们跳过了它们。通过使用Racket的构造器，我们基本上是直接用抽象语法树来写程序，依靠方便的语法来写树，而不是编造一个语法和写一个解析器。也就是说，我们用这样的表达式编写程序：

(negate (add (const 2) (const 2))) 

而不是像”-(2+2)“这样的字符串。

虽然将算术表达式这样的语言嵌入到Racket这样的另一种语言中，与拥有特殊的语法相比，似乎很不方便，但它的优势甚至超过了不需要写解析器。例如，下面我们将看到我们如何使用元语言（本例中是Racket）来编写类似于我们语言的宏的东西。

关于合法AST的假设和非假设

在像我们的算术表达式语言这样的语言中，两种”错误的”AST之间存在着微妙的区别。为了使这种区别更加清晰，让我们用另外三种表达式来扩展我们的语言：

(struct const (int) #:transparent) ; int should hold a number
(struct negate (e1) #:transparent) ; e1 should hold an expression
(struct add (e1 e2) #:transparent) ; e1, e2 should hold expressions
(struct multiply (e1 e2) #:transparent) ; e1, e2 should hold expressions
(struct bool (b) #:transparent) ; b should hold #t or #f
(struct if-then-else (e1 e2 e3) #:transparent) ; e1, e2, e3 should hold expressions
(struct eq-num (e1 e2) #:transparent) ; e1, e2 should hold expressions

新的功能包括布尔值（真或假）、条件表达式，以及用于比较两个数字并返回布尔值的结构（当且仅当数字相同时为真）。最重要的是，现在用这种语言评估一个表达式的结果可以是：

• 一个整数，如(const 17)
• 一个布尔值，如(bool true)
• 不存在，因为当我们试图评估程序时，我们会得到一个”运行时类型错误”，试图把布尔值当作数字，反之亦然

换句话说，在我们的语言中现在有两种类型的值（数字和布尔值），如果一个子表达式被评估为错误的值，有些操作应该失败。

最后一种可能性是解释器应该检查的，并给出适当的错误信息。如果评估某种表达式（例如加法）需要评估子表达式的结果具有某种类型（例如像(const 4)这样的数字，而不是像(bool #t)这样的布尔值），那么解释器应该检查这种结果（例如使用const?）而不是假设递归结果具有正确的类型。这样一来，错误信息就合适了（例如：”加法的参数不是一个数字”），而不是解释器实现方面的东西。

与这些笔记相对应的课程材料中发布的代码有两个完整的解释器，用于这种语言。第一个解释器不包括任何这种检查，而第二个更好的解释器则包括。称第一个解释器为eval-exp-wrong，第二个解释器为eval-exp，这里只是两者的加法情况：

; eval-exp-wrong
[(add? e)
 (let ([i1 (const-int (eval-exp-wrong (add-e1 e)))]
       [i2 (const-int (eval-exp-wrong (add-e2 e)))])
 (const (+ i1 i2)))]
; eval-exp
[(add? e)
(let ([v1 (eval-exp (add-e1 e))]
      [v2 (eval-exp (add-e2 e))])
  (if (and (const? v1) (const? v2))
      (const (+ (const-int v1) (const-int v2)))
      (error "add applied to non-number")))]

然而，eval-exp是假设它正在评估的表达式是该语言的合法AST。它可以处理(add (const 2) (const 2))，它的评估结果是(const 4)，但是没有优雅地处理(add #t #f)或者(add 3 4)。根据我们在注释中的规则，这些都是不合法的AST，即：

• const的int字段应该保存一个Racket数字。
• bool的b字段应该保存一个Racket布尔值。
• 所有其他表达式的字段应该持有其他合法的AST。(是的，这个定义是递归的）。

解释器假设它被赋予了一个合法的AST是合理的，所以如果被赋予了一个非法的AST，它可以用一个奇怪的、与实现相关的错误信息来实现”崩溃”。

有变量的语言的解释器需要环境

我们的算术表达式语言中缺少的最大东西就是变量。这就是为什么我们可以只有一个递归函数，它接受一个表达式并返回一个值。正如我们从课程一开始就知道的那样，由于表达式可以包含变量，评估它们需要一个将变量映射为值的环境。因此，有变量的语言的解释器需要一个递归的辅助函数，它接收一个表达式和一个环境，并产生一个值。（事实上，对于具有突变或异常等特征的语言，辅助函数甚至需要更多的参数。）

环境的表示是解释器在元语言中实现的一部分，而不是语言的抽象语法的一部分。许多表示方法都是合适的，为常用变量提供快速访问的花式数据结构也是合适的。但是对于我们的目的来说，忽略效率是可以的。因此，使用 Racket作为我们的元语言，一个包含字符串（变量名）和值（变量绑定到的对象）pair的简单关联列表就可以满足要求。

给定一个环境，解释器在不同的情况下以不同的方式使用它：

• 为了评估一个变量表达式，它在环境中查找该变量的名称（即字符串）。
• 为了评估大多数子表达式，例如加法运算的子表达式，解释器向递归调用传递评估外部表达式所传递的相同环境。
• 为了评估像let-expression的主体这样的东西，解释器会向递归调用传递一个稍微不同的环境，比如传递给它的环境中多了一个绑定（即字符串和值的pair）。

为了评估整个程序，我们只需调用我们的递归辅助函数，该函数接收一个带有程序的环境和一个合适的初始环境，例如空环境，其中没有任何绑定。

实现闭包

为了实现带有函数闭包和词法范围的语言，我们的解释器需要记住函数被定义时的环境，以便在函数被调用时使用这个环境而不是调用者的环境。这样做的诀窍很直接：我们可以创建一个叫做闭包的小数据结构，其中包括环境和函数本身。正是这一对（闭包）是解释一个函数的结果。换句话说，一个函数不是一个值，一个闭包才是，所以对一个函数的评估会产生一个闭包，这个闭包记住了我们评估该函数时的环境。

我们还需要实现函数调用。一个调用有两个表达式e1和e2，在ML中是e1 e2，在Racket中是(e1 e2)。(我们在这里考虑的是单参数函数，尽管实现上自然会支持模拟多参数函数的currying)。我们对一个调用的评估如下：

• 我们使用当前的环境来评估e1。结果应该是一个闭包（否则就是一个运行时错误）。
• 我们使用当前的环境来评估e2。其结果将是闭包的参数。
• 我们使用闭包的环境部分来评估闭包的代码部分的主体，并将代码部分的参数扩展到调用地的参数。

在与这些教材相关的作业中，有一个额外的变量环境扩展，它允许闭包以递归方式调用自己。但关键的想法是一样的：我们扩展了与闭包一起存储的环境来评估闭包的函数体。

这确实是解释器实现闭包的方式。这就是我们第一次学习闭包时学到的语义，只是在解释器中被实现了。

可选：更高效地实现闭包

我们在每个闭包中存储整个当前环境，这似乎很昂贵，但事实并不是。首先，当环境是关联列表时，它并不昂贵，因为不同的环境只是彼此的扩展，而且当我们用cons生成更长的列表时，我们并没有复制列表。（记得这种共享是不改变列表的一大好处，我们也不改变环境）。其次，在实际中，我们可以通过只存储函数主体可能使用的环境部分来节省空间。我们可以看一下函数体，看看它有哪些自由变量（在函数体中使用的变量，其名称在函数体之外），我们存储在闭包中的环境只需要这些变量。毕竟，如果函数体没有使用某个变量，闭包的执行就不可能需要从环境中查找该变量。语言实现在开始评估之前，会预先计算每个函数的自由变量。它们可以将结果与每个函数一起存储，这样在构建闭包时就可以迅速获得这组变量。

最后，你可能会问，如果目标语言本身没有闭包，编译器如何实现闭包。作为翻译的一部分，函数定义仍然评估为闭包，它有两个部分，代码和环境。然而，我们并没有一个解释器，每当我们到达一个需要查询的变量时，它都有一个”当前环境”。因此，我们改变了程序中的所有函数，使其接受一个额外的参数（环境），并改变所有的函数调用，使其明确地传入这个额外的参数。现在，当我们有一个闭包时，代码部分将有一个额外的参数，调用者将为这个参数传入环境部分。然后，编译器只需要将所有自由变量的使用翻译成代码，使用额外的参数来寻找正确的值。在实际中，为环境使用良好的数据结构（如数组）可以使这些变量的查找变得非常快（和从数组中读出一个值一样快）。

通过元语言中的函数来实现”宏”

在实现一个解释器或编译器时，必须把被实现的语言和用于实现的语言（元语言）中的内容分开。例如，eval-exp是一个Racket函数，它接收一个算术表达式语言的表达式（或我们正在实现的任何语言），并产生一个算术表达式语言的值。因此，举例来说，一个算术表达式语言表达式永远不会包括eval-exp的使用或Racket加法表达式。

但由于我们是在Racket中编写待评估程序，我们可以使用Racket辅助函数来帮助我们创建这些程序。这样做基本上就是用Racket函数作为宏语言，为我们的语言设计宏。下面是一个例子。

(define (double e) ; takes language-implemented syntax and produces language-implemented syntax
   (multiply e (const 2)))

这里double是一个Racket函数，它接收一个算术表达式的语法并产生一个算术表达式的语法。调用double在我们的语言中产生抽象的语法，很像宏扩展。例如，(negate (double (negate (const 4)))) produces (negate (multiply (negate (const 4)) (const 2))。请注意，这个”宏”double并没有以任何方式评估程序：我们产生了抽象的语法，然后可以被评估，放在一个更大的程序里面，等等。

能够这样做是我们的小语言嵌入Racket元语言的一个优势。 无论选择哪种元语言，同样的技术都能发挥作用。然而，这种方法并不能像真正的宏系统那样处理与变量shadow有关的问题，因为它有hygienic宏。

这里有一个不同的”宏”，在两个方面很有意思。首先，参数是一个Racket列表，其中有语言实现的表达式（语法）。其次，这个”宏”是递归的，对参数列表中的每个元素都调用一次自己：

(define (list-product es)
  (if (null? es)
      (const 1)
      (multiply (car es) (list-product (cdr es)))))