跳转到内容

编程语言导论/ML 解释器

Add links
来自维基教科书，开放的书籍，开放的世界

为了介绍与操作语义相关的基本概念，我们将定义一个用于 ML 子集的解释器，该子集足够全面，可以包含 lambda 演算。我们从一个非常简单的语言开始，其具体语法如下

    <exp> ::= <exp> + <mulexp>
            | <mulexp>
 <mulexp> ::= <mulexp> * <rootexp>
            | <rootexp>
<rootexp> ::= ( <exp> )
            | <constant>

正如我们之前解释的那样，许多这种语法是样板文件。我们想要解释的语言的基本结构要简单得多

<ast> ::= plus(<ast>, <ast>)
        | times(<ast>, <ast>)
        | const (<const>)

到目前为止，我们有三种类型的元素：表示加法、乘法和数字的节点。为了生成此语言的解释器，我们需要定义访问每个节点时要执行的操作。我们将在 Prolog 中生成这样的解释器。因为我们有三种类型的节点，所以我们需要定义三种类型的操作

val(plus(X,Y),Value) :- val(X, XValue), val(Y, YValue), Value is XValue + YValue.
val(times(X,Y),Value) :- val(X, XValue), val(Y, YValue), Value is XValue * YValue.
val(const(X),X).

我们的语言在此时只能描述算术表达式。因此，程序的含义始终是一个数字。我们的 Prolog 解释器允许我们获得这种含义

| ?- val(const(10000), N).

N = 10000

(1 ms) yes
| ?- val(plus(const(10000), const(20)), N).

N = 10020

请注意，程序的含义通常只是一个值。在 lambda 演算中，每个程序都是一个值。在纯函数式编程语言中，我们也拥有这种语义。例如，正如我们在开发过程中将要继续进行的那样，我们将用更多语法来扩展我们的语言。包含变量和函数的程序的含义只是值，其中值可以是数字或函数。说到变量，这是我们编程语言的下一个补充。在这种情况下，我们需要语法来创建 let 块，就像我们在 ML 中一样。例如

- let val x = 2 in x * x end ;
val it = 4 : int
- let val x = 2 in let val x = 3 in x * x end + x end ;
val it = 11 : int

为了将 let 块添加到我们的编程语言中，我们需要扩展其具体语法。新的语法可以在下面看到

<exp>     ::= <exp> + <mulexp>
            | <mulexp>
<mulexp>  ::= <mulexp> * <rootexp>
            | <rootexp>
<rootexp> ::= let val <variable> = <exp> in <exp> end
            | ( <exp> )
            | <variable>
            | <constant>

在抽象语法方面，let 块迫使我们创建两种新的节点。第一个节点代表 let 结构本身。第二个代表名称，即值的替身。这种扩展的抽象语法可以在下面看到

<ast> ::= plus (<ast>, <ast>)
        | times (<ast>, <ast>)
        | const (<const>)
        | let (<name>, <ast>, <ast>)
        | var (<name>)

我们需要用两个新的子句来增强我们的解释器，以便理解变量和 let 块。现在出现的一个问题是如何跟踪变量的值。为了完成此任务，我们需要一个环境的支持。环境是一个表，它将变量名绑定到这些名称表示的值。请注意，我们不是在谈论可变变量：一旦分配，变量将具有相同的值，直到不再处于作用域内。我们新的解释器版本如下

val(plus(X, Y), Context, Value) :-
  val(X, Context, XValue),
  val(Y, Context, YValue),
  Value is XValue + YValue.
val(times(X, Y), Context, Value) :-
  val(X, Context, XValue),
  val(Y, Context, YValue),
  Value is XValue * YValue.
val(const(X), _, X).
val(var(X), Context, Value) :-
  lookup(X, Context, Value).
val(let(X, Exp1, Exp2), Context, Value2) :-
  val(Exp1, Context, Value1),
  val(Exp2, [(X, Value1)|Context], Value2).

lookup(Variable, [(Variable, Value)|_], Value).
lookup(VarX, [(VarY, _)|Rest], Value) :-
  VarX \= VarY,
  lookup(VarX, Rest, Value).

这个新实现允许我们创建变量，我们通过查找谓词。新的语义很好地模拟了块的行为：let 绑定创建一个新作用域，该作用域仅在此块内有效。例如，下面我们展示了一个 ML 程序及其等效版本，用我们的语言

let val y = 3 in            val(let(y,const(3),
  let val x = y * y in        let(x, times(var(y), var(y)),
    x * x                       times(var(x), var(x)))),
  end                       nil, X).
end

请注意，我们确实具有块语义。例如，下面我们看到程序的解释let val x = 1 in let val x = 2 in x end + x end。该程序产生值 3，正如预期在 ML 中一样

| ?- val(let(x, const(1), plus(let(x, const(2), var(x)), var(x))), nil, V).
V = 3 ? ;

我们现在想要将解释器推进一步，赋予它理解函数的能力，包括高阶函数和闭包。这个新的补充意味着一个值现在可以是一个函数。例如，以下 ML 程序返回一个函数，该函数表示其含义let val f = fn x => x + 1 in f end。将函数添加到我们的语言比添加变量更复杂，因为此添加需要许多步骤。特别是，我们的新具体语法由以下语法给出

<exp>     ::= fn <variable> => <exp>
            | <addexp>
<addexp>  ::= <addexp> + <mulexp>
            | <mulexp>
<mulexp>  ::= <mulexp> * <funexp>
            | <funexp>
<funexp>  ::= <funexp> <rootexp>
            | <rootexp>
<rootexp> ::= let val <variable> = <exp> in <exp> end
            | ( <exp> )
            | <variable>
            | <constant>

首先，我们需要能够区分两种类型的值：函数和数字。因为我们的编程语言不包含类型系统，所以我们将使用“标记”将函数与数字分开。因此，我们将附加原子fval到每个作为函数的值。这样的值由一对组成：函数的参数和主体。也就是说，我们编程语言中的每个函数都只使用一个参数。这类似于我们在 ML 中找到的，例如，匿名函数正好具有这两个组件：一个形式参数加一个主体。匿名函数的示例包括fn x => x * x, fn x => (fn y => x + y)和fn x => 1。我们的抽象语法可以在下面看到

<ast> ::= plus (<ast>, <ast>)
        | times (<ast>, <ast>)
        | const (<const>)
        | let (<name>, <ast>, <ast>)
        | var (<name>)
        | fn (<name>, <ast>)
        | apply (<ast>, <ast>)

我们有一个节点应用，它表示函数应用。请注意，此节点接收整个 AST 节点，而不是表示函数的简单名称。这是预期的，因为函数可以是表达式的结果。例如，这是一个有效的程序(let val f = fn x => x + 1 in f end) 2。在这种情况下，应用的左侧是表达式let val f = fn x => x + 1 in f end，一旦计算，它将产生函数fn x => x + 1。我们的解释器的扩展版本如下

val(plus(X, Y), Context, Value) :-
  val(X, Context, XValue),
  val(Y, Context, YValue),
  Value is XValue + YValue.

val(times(X, Y), Context, Value) :-
  val(X, Context, XValue),
  val(Y, Context, YValue),
  Value is XValue * YValue.

val(const(X), _, X).

val(var(X), Context, Value) :-
  lookup(X, Context, Value).

val(let(X, Exp1, Exp2), Context, Value2) :-
  val(Exp1, Context, Value1),
  val(Exp2, [bind(X, Value1) | Context], Value2).

val(fn(Formal, Body), _, fval(Formal, Body)).

val(apply(Function, Actual), Context, Value) :-
  val(Function, Context, fval(Formal, Body)),
  val(Actual, Context, ParamValue),
  val(Body, [bind(Formal, ParamValue)|Context], Value).

lookup(Variable, [bind(Variable, Value)|_], Value).
lookup(VarX, [bind(VarY, _)|Rest], Value) :-
  VarX \= VarY, lookup(VarX, Rest, Value).

这个新的解释器功能强大，足以处理像下面代码一样复杂的程序，该代码是用 SML 实现的

let val x = 1 in
  let val f = fn n => n + x in
    let val x = 2 in
      f 0
    end
  end
end

这个程序一旦计算，就会给我们一个相当意外的结果

| ?- val(let(x, const(1), let(f, fn(n, plus(var(n), var(x))), let(x, const(2), apply(var(f), const(0))))), nil, X).

X = 2

我们期望在 ML 中获得 1。但是，我们的解释器返回了值 2。这种差异的答案很简单：我们的解释器使用 动态作用域，而 ML 使用 静态作用域。这是自然的：通常更易于实现动态作用域。这也是早期一些编程语言（如 Lisp）使用动态作用域的原因之一。但是，正如我们之前讨论的那样，静态作用域具有其动态对应物的许多优点。其中一个优点是我们可以将函数用作黑盒。换句话说，在函数体之外发生的定义不会改变该函数的行为。在我们的例子中，实现静态作用域并不困难：我们需要保存创建函数时存在的上下文。我们的解释器的这个新版本实现了静态作用域

val(plus(X, Y), Context, Value) :-
  val(X, Context, XValue),
  val(Y, Context, YValue),
  Value is XValue + YValue.

val(times(X, Y), Context, Value) :-
  val(X, Context, XValue),
  val(Y, Context, YValue),
  Value is XValue * YValue.

val(const(X), _, X).

val(var(X), Context, Value) :-
  lookup(X, Context, Value).

val(let(X, Exp1, Exp2), Context, Value2) :-
  val(Exp1, Context, Value1),
  val(Exp2, [bind(X, Value1) | Context], Value2).

val(fn(Formal, Body), Context, fval(Formal, Body, Context)).

val(apply(Function, Actual), Context, Value) :-
  val(Function, Context, fval(Formal, Body, Nesting)),
  val(Actual, Context, ParamValue),
  val(Body, [bind(Formal, ParamValue)|Nesting], Value).

lookup(Variable, [bind(Variable, Value)|_], Value).
lookup(VarX, [bind(VarY, _)|Rest], Value) :-
  VarX \= VarY, lookup(VarX, Rest, Value).

在这个新的解释器版本中，函数现在表示为三元组fval(Formal, Body, Context))。这个三元组中的两个元素，正式的和身体，与以前一样：函数的参数及其主体。第三个元素，上下文，是在创建函数时存在的绑定。的实现应用也已更改。我们不是在调用函数的上下文中评估函数，而是在创建函数的上下文中对其进行评估。有了这个新的解释器，我们获得了与 SML 相同的行为

| ?- val(let(x, const(1), let(f, fn(n, plus(var(n), var(x))), let(x, const(2), apply(var(f), const(0))))), nil, X).

X = 1

请注意，这两个最后的解释器版本功能强大，足以处理闭包，就像 SML 一样。例如，我们可以在我们的解释器中编写下面的程序，并运行它

let
  val f = fn x => let val g = fn y => y+x in g end
in
  f 1 2
end

如果我们将它翻译成我们的新语言，那么我们有以下程序

?- val(let(f,fn(x,let(g,fn(y,plus(var(y),var(x))), var(g))), apply(apply(var(f),const(1)),const(2))),nil, X).

X = 3

← 追求意义

取自“https://wikibooks.cn/w/index.php?title=Introduction_to_Programming_Languages/An_Interpreter_for_ML&oldid=4030906”
华夏公益教科书