3.5.包含抽象的语言的解释器

发表于 更新于 分类于 ， 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 6 分钟

\(3.5\)包含抽象的语言的解释器(\(Interpreters\;for\;Languages\;with\;Abstraction\))

  先前Calcualtor的实现并未给出定义新操作、给变量命名、表达计算的一般方法等的实现。下面给出描述性的实现方法：

1.结构

  一个\(scheme\)解释器和先前的计算器解释器有很多相似的结构：

  • 分析器通过计算器解释(\(evaluator\;interpretation\))来产生一个表达式。
  • 计算函数侦测表达式的形式；对于调用表达式，它会调用一个函数用于处理某些参数。

  两者的计算器(\(evaluator\))的区别存在于特殊的形式(\(special\;form\))，用户定义函数(\(user-defined\;function\))和实现计算所需的环境模型(\(the\;environment\;model\;of\;computation\))。

  \(a.\)解析(\(Parsing\))

1
2
>>> read_line("(car '(1 . 2))")
Pair('car', Pair(Pair('quote', Pair(Pair(1, 2), nil)), nil))

  \(b.\)计算(\(evaluation\))

  \(Scheme\)每次计算一个表达式。每个通过scheme_read返回的表达式都传递给scheme_eval函数，它会在当前环境env中计算表达式expr。

  scheme_eval函数会计算\(Scheme\)中的不同表达式类型：初始型(\(primitive\))，特殊型(\(special\;form\))和调用表达式(\(call\;expression\))。每种形式都有它们对应的计算法则： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def scheme_eval(expr, env):
        """Evaluate Scheme expression expr in environment env."""
        if scheme_symbolp(expr):
            return env[expr]
        elif scheme_atomp(expr):
            return expr
        first, rest = expr.first, expr.second
        if first == "lambda":
            return do_lambda_form(rest, env)
        elif first == "define":
            do_define_form(rest, env)
            return None
        else:
            procedure = scheme_eval(first, env)
            args = rest.map(lambda operand: scheme_eval(operand, env))
            return scheme_apply(procedure, args, env)

  \(c.\)过程调用(\(Procedure\;application\))

  过程调用通过scheme_apply实现。它比起先前的calc_apply更具普遍性。它接受两类参数：PrimitiveProcedure或LambdaProcedure。

  PrimitiveProcedure是在\(python\)中实现的，它有一个fn的实例属性(\(instance\;attribute\))，每当过程被调用，这个函数就被调用。

  LambdaProcedure是在\(scheme\)中实现的。它有一个body属性，这是一个\(scheme\)表达式，每当过程被调用它就被调用。为了将该过程用于一系列参数，body表达式会在一个新环境里被调用。为了搭建环境，一个新的框架被加入进环境中，在这个框架中，过程的形式参数(\(formal\;parameters\))与变量(\(argument\))绑定。body通过scheme_eval计算。

  \(d.\)递归调用与计算(\(Eval/apply\;recursion\))

  实现计算过程的scheme_eval和scheme_apply是相互递归的(\(mutually\;recursive\))。每当一个调用表达式被计算，计算函数都需要被调用。而应用函数使用计算函数将操作元表达式作为参数，并计算用户定义的过程这一部分(\(user-defined\;procedures\))。这一相互递归的过程是由下面这个过程决定的：计算函数是通过(\(in\;terms\;of\))应用函数定义的，而应用函数又是通过计算函数定义的。

  递归的循环以语言原语(\(language\;primitive\))结束。计算函数有一个用于计算基本表达式的基本情况。一些特殊形式(\(special\;form\))也是不需要递归调用的基本情况。

  这种处理表达式形式(\(expression\;form\)) 的\(eval\)函数与处理函数及其参数的\(apply\)函数相互递归调用的结构组成了计算过程的核心。

2.环境

  \(a.\)基本结构

  我们希望实现一个Frame类来构建环境。每个Frame的实例都代表一个环境，在这个实例中，标记(\(symbol\))与值(\(value\))相绑定。

  Frame实例由一个binding字典和parant框架构成。对于\(Global\)框架，parent=None。

  \(b.\)binding和define

  binding并不是直接访问的，它通过两个Frame方法访问：lookup和define。lookup过程会在我们的环境模型中执行\(lookup\)过程。然后符号与当前frame的binding相匹配。如果它找到了，它相关联的值就被返回；否则，lookup过程会在parent frame继续该过程。而define方法在当前frame中将标记与值相绑定。

  考虑下面的程序： 

1
2
(define (factorial n)
  (if (= n 0) 1 (* n (factorial (- n 1)))))
1
2
(factorial 5)
120

  定义这样一个函数有以下步骤：

  1. 检查表达式的格式(\(format\))，确保它是一个完备的\(Scheme\)列表，至少有两个元素与关键字\(define\)。
  2. 分析第一个元素。在本例中，寻找函数名称\(factorial\)和形式参数\(list(n)\)。
  3. 用提供的形式参数创造一个LambdaProcedure，body和parent环境。
  4. 在当前环境的第一个frame中，将\(factorial\)标志与这个函数绑定。

  第二个输入是一个调用表达式。传给scheme_apply的过程是与\(factorial\)相绑定的LambdaProcedure。为了应用这一过程，一个新的框架创建了，扩展了原来的父框架。在这个框架中，标志\(n\)与值\(5\)绑定。然后，\(factorial\)的body部分在这个环境中被计算，它的值也被返回。

3.作为程序的数据

  我们可以从模拟(\(analogy\))的角度来看待程序。对程序含义的操作观点(\(optional\;view\))认为：程序是对一个抽象机器的描述。以先前的函数为例： 

1
2
(define (factorial n)
  (if (= n 0) 1 (* n (factorial (- n 1)))))

  我们可以将这个程序看作对一个机器的描述，这个机器包括减法、乘法、相等性测试、双向开关和另一个\(factorial\)机器(由于一个机器内部可以嵌套另一个机器，这个机器是无限的)：

  相似地，我们可以将\(Scheme\)解释器视为一个特别的机器，它将一个对机器的描述作为输入。对于这个输入，解释器配置好自己来模拟这个描述的机器。

  从这个角度，我们的\(Scheme\)解释器是一种具有普遍性的机器。当其它机器在\(Scheme\)程序中被描述时，解释器会模拟这些机器。它扮演着被编程语言操纵的数据对象和编程语言本身之间的桥梁。对于用户的输入，解释器将其视为一个简单的句子，并通过一系列完备规则操作它们。

  计算作为执行过程一部分的表达式是一个有活力的编程语言所具的特点。在程序的执行过程中创建并计算表达式的能力是一个有力的工具。