跳轉到內容

程式語言導論/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://wikibook.tw/w/index.php?title=Introduction_to_Programming_Languages/An_Interpreter_for_ML&oldid=4030906”
華夏公益教科書