SICP：元循環(huán)求值器（Python實(shí)現(xiàn)）
元語言抽象就是建立新的語言。它在工程設(shè)計(jì)的所有分支中都扮演著重要的角色，在計(jì)算機(jī)程序設(shè)計(jì)領(lǐng)域更是特別重要。因?yàn)檫@個(gè)領(lǐng)域中，我們不僅可以設(shè)計(jì)新的語言，還可以通過構(gòu)造求值器的方式實(shí)現(xiàn)這些語言。對(duì)某個(gè)程序設(shè)計(jì)語言的求值器（或者解釋器）也是一個(gè)過程，在應(yīng)用于這個(gè)語言的一個(gè)表達(dá)式時(shí)，它能夠執(zhí)行求值這個(gè)表達(dá)式所要求的動(dòng)作。接下來我們將要討論如何關(guān)于在一些語言的基礎(chǔ)上構(gòu)造新的語言。在這篇博客里，我們將用Python語言去構(gòu)造一個(gè)Scheme語言的求值器。事實(shí)上求值器的實(shí)現(xiàn)語言無關(guān)緊要，我們也可以用Scheme語言去構(gòu)造Scheme語言的求值器。用于被求值語言同樣的語言寫出來的求值器被稱為元循環(huán)（metacircular）。
求值器完整實(shí)現(xiàn)代碼我已經(jīng)上傳到了GitHub倉(cāng)庫(kù)：TinySCM，感興趣的童鞋可以前往查看。這里順便強(qiáng)烈推薦UC Berkeley的同名課程CS 61A。
在這個(gè)層次結(jié)構(gòu)的最底層是對(duì)象語言。對(duì)象語言只涉及特定的域，而不涉及對(duì)象語言本身（比如它們的文法規(guī)則，或其中的其體句子）。如要涉及它們，則要有一種元語言。對(duì)于語言的兩個(gè)層次這一經(jīng)驗(yàn)，所有學(xué)習(xí)外國(guó)語的人都是很熟悉的。然后，就要有一種元元語言來討論元語言，以此類推。
——侯世達(dá)《哥德爾、埃舍爾、巴赫：集異璧之大成》
緒論
到目前為止，我們探討的都是通過過程抽象、數(shù)據(jù)抽象以及模塊化等手段來控制系統(tǒng)的復(fù)雜性。為了闡釋這些技術(shù)，我們一直使用的是同一種編程語言。然而，隨著我們所面對(duì)的問題更復(fù)雜，我們必須經(jīng)常轉(zhuǎn)向新的語言，以便能夠有效地表述自己的想法。實(shí)際上，建立新語言是工程設(shè)計(jì)中控制復(fù)雜性的一種威力強(qiáng)大的工作策略，我們常常能通過采用一種新語言而處理復(fù)雜問題的能力。
元語言抽象就是建立新的語言。它在工程設(shè)計(jì)的所有分支中都扮演著重要的角色，在計(jì)算機(jī)程序設(shè)計(jì)領(lǐng)域更是特別重要。因?yàn)檫@個(gè)領(lǐng)域中，我們不僅可以設(shè)計(jì)新的語言，還可以通過構(gòu)造求值器的方式實(shí)現(xiàn)這些語言。對(duì)某個(gè)程序設(shè)計(jì)語言的求值器（或者解釋器）也是一個(gè)過程，在應(yīng)用于這個(gè)語言的一個(gè)表達(dá)式時(shí)，它能夠執(zhí)行求值這個(gè)表達(dá)式所要求的動(dòng)作。
把這一點(diǎn)看做是程序設(shè)計(jì)語言中最基本的思想一點(diǎn)也不過分：
求值器決定了一個(gè)程序設(shè)計(jì)語言中各種表達(dá)式的意義，而它本身也不過就是另一個(gè)程序。
事實(shí)上，我們幾乎可以把任何程序看做是某個(gè)語言的求值器。比如在符號(hào)代數(shù)中，一個(gè)多項(xiàng)式系統(tǒng)包含著多項(xiàng)式的算數(shù)規(guī)則以及底層的實(shí)現(xiàn)，一個(gè)符號(hào)求導(dǎo)系統(tǒng)亦包含著函數(shù)求導(dǎo)的規(guī)則以及底層的實(shí)現(xiàn)（參見我之前的博客《SICP：符號(hào)求導(dǎo)、集合表示和Huffman樹（Python實(shí)現(xiàn)）》）。從這樣一種觀點(diǎn)看，處理大規(guī)模計(jì)算機(jī)系統(tǒng)的技術(shù)，與構(gòu)造新的程序設(shè)計(jì)語言的技術(shù)有緊密的聯(lián)系，而計(jì)算機(jī)科學(xué)中一個(gè)重要的思想就是如何去構(gòu)造適當(dāng)?shù)拿枋稣Z言。
接下來我們將要討論如何關(guān)于在一些語言的基礎(chǔ)上構(gòu)造新的語言。在這篇博客里，我們將用Python語言去構(gòu)造一個(gè)Scheme語言的求值器。事實(shí)上求值器的實(shí)現(xiàn)語言無關(guān)緊要，我們也可以用Scheme語言去構(gòu)造Scheme語言的求值器。用于被求值語言同樣的語言寫出來的求值器被稱為元循環(huán)（metacircular）。
從根本上說，元循環(huán)求值器也就是我們?cè)诓┛?a href="http://www.rzrgm.cn/orion-orion/p/17185719.html" target="_blank">《SICP：賦值和局部狀態(tài)（Python實(shí)現(xiàn)）》中所描述求值的環(huán)境模型的一個(gè)實(shí)現(xiàn)形式。回憶一下，該模型包括兩個(gè)部分：
- 在求值一個(gè)組合式（combinations）（非特殊形式的復(fù)合表達(dá)式）時(shí)，首先求值其中的子表達(dá)式（包括運(yùn)算符和運(yùn)算對(duì)象），然后將運(yùn)算符的值（即一個(gè)過程對(duì)象）應(yīng)用于運(yùn)算對(duì)象的值。
- 在將一個(gè)復(fù)合過程對(duì)象應(yīng)用于一集實(shí)參時(shí)，我們將在一個(gè)新環(huán)境里求值這個(gè)過程的體。構(gòu)造這一新環(huán)境的方式是用一個(gè)幀來擴(kuò)充該過程對(duì)象原來的環(huán)境，幀中包含的是這個(gè)過程的形參與所應(yīng)用的實(shí)參之間的綁定。
這兩條規(guī)則描述了求值過程的核心部分，也就是它的基本循環(huán)。在這一循環(huán)中，表達(dá)式在環(huán)境中的求值被規(guī)約到過程對(duì)實(shí)參的應(yīng)用，而這種應(yīng)用又被規(guī)約到新的表達(dá)式在新的環(huán)境中的求值。如此下去，直至我們下降到符號(hào)（其值可以在環(huán)境中找到）或基本過程（它們可以直接應(yīng)用）。 如下圖所示：
這一求值循環(huán)實(shí)際體現(xiàn)為求值器里的兩個(gè)關(guān)鍵函數(shù)scheme_eval()和scheme_apply()的相互作用，我們?cè)?.1.1節(jié)將描述他們。
求值器的實(shí)現(xiàn)依賴于一些定義了被求值表達(dá)式的 語法（syntax） （也即被求值表達(dá)式是以何種數(shù)據(jù)結(jié)構(gòu)來表示的）的過程。我們?nèi)詫⒉捎米皂斚蛳碌臄?shù)據(jù)抽象技術(shù)，設(shè)法使求值器獨(dú)立于語言的具體表示。例如，對(duì)于賦值表達(dá)式(set! <var> <val>)，我們用抽象的選取函數(shù)assignment_variable()和assignment_value()去訪問賦值中相應(yīng)的部分（不過這里需要注意，為了方便后面的類型分派操作，我們?nèi)匀患僭O(shè)可以用first_expr()和rest_exprs()分別去訪問表達(dá)式的首元素和其余元素，算是對(duì)抽象性的一個(gè)小小的擊穿吧）。表達(dá)式的具體表示將在4.1.2節(jié)里描述。在4.1.3里還會(huì)描述一些過程和環(huán)境的表示形式，如Environment類、LambdaProcedure類的定義及其對(duì)應(yīng)的一些方法。
4.1.1 求值器的內(nèi)核
求值過程可以描述為兩個(gè)函數(shù)scheme_eval()和scheme_apply()之間的相互作用（interplay）。
eval
scheme_eval()的參數(shù)是一個(gè)表達(dá)式和一個(gè)環(huán)境。scheme_eval()對(duì)表達(dá)式進(jìn)行分類以此展開后續(xù)的求值工作。正如我們上面所說，我們采用選取函數(shù)first_expr()和rest_exprs()分別去訪問表達(dá)式的首元素和其余元素，并根據(jù)表達(dá)式的首元素（也即其標(biāo)簽）來完成表達(dá)式類型的判定。表達(dá)式的類型可做如下分類：
基本表達(dá)式：
- 對(duì)于自求值表達(dá)式，例如數(shù)和字符串等（其實(shí)也就是我們常說的字面值，literals），
scheme_eval()直接返回這個(gè)表達(dá)式本身。 - 對(duì)于變量，
scheme_eval()必須在環(huán)境中查找變量的值。
特殊形式（special forms）：
- 這里的特殊形式包括
if表達(dá)式、變量的賦值/定義、引號(hào)（'）表達(dá)式、lambda表達(dá)式等、我們的處理方式是將其分派給不同的名為eval_×××()的求值函數(shù)處理。如if表達(dá)式就分派給eval_if()函數(shù)來處理。
組合式（combinations）：
- 這里的組合式也即過程的應(yīng)用（application）。對(duì)于一個(gè)過程應(yīng)用，
scheme_eval()必須先遞歸地求值組合式的運(yùn)算符部分和運(yùn)算對(duì)象部分。而后將這樣得到的過程對(duì)象和參數(shù)送給scheme_apply()，由它去處理實(shí)際的過程應(yīng)用。注意，如果運(yùn)算符部分是宏（Macro），則不需要事先對(duì)其進(jìn)行求值就直接將其應(yīng)用，待應(yīng)用完畢之后再進(jìn)行求值。
下面是scheme_eval()的定義：
@primitive("eval", use_env=True)
def scheme_eval(expr, env, _=None):
# Evaluate self-evaluating expressions
if is_self_evaluating(expr):
return expr
# Evaluate variables
elif is_scheme_variable(expr):
return env.lookup_variable_value(expr)
# All valid non-atomic expressions are lists (combinations)
if not is_scheme_pair(expr):
raise SchemeError(
"Unknown expression type: {0}".format(repl_str(expr)))
first, rest = first_expr(expr), rest_exprs(expr)
# Evaluate special forms
if is_scheme_symbol(first) and first in SPECIAL_FORMS:
return SPECIAL_FORMS[first](rest, env)
# Evaluate an application
else:
operator = scheme_eval(first, env)
# Check if the operator is a macro
if isinstance(operator, MacroProcedure):
return scheme_eval(complete_apply(operator, rest, env), env)
operands = rest.map(lambda x: scheme_eval(x, env))
return scheme_apply(operator, operands, env)
@primitive("eval", use_env=True)表示將其加入Scheme的基本過程中，過程名為eval（注意，Python語言中的裝飾器會(huì)在被裝飾的函數(shù)定義之后立即運(yùn)行，故上述操作是在scheme_eval()函數(shù)定義之后立即完成的）。這里的特殊形式的類型分派采用了數(shù)據(jù)導(dǎo)向的方式（這種做法可以使用戶更容易增加scheme_eval()能分辨的表達(dá)式類型，而又不必修改scheme_eval()的定義本身）。所有的SPECIAL_FORMS及其所分派的求值函數(shù)如下所示：
SPECIAL_FORMS = {
# Conditionals
"if": eval_if,
"cond": eval_cond,
"and": eval_and,
"or": eval_or,
# Sequencing
"begin": eval_begin,
"let": eval_let,
# Assignments
"set!": eval_assignment,
# Definitions
"define": eval_definition,
# Lambda expressions
"lambda": eval_lambda,
# Quoting
"quote": eval_quote,
"unquote": eval_unquote,
"quasiquote": eval_quasiquote,
# Dynamic scoping
"dlambda": eval_dlambda_form,
# Macro
"define-macro": eval_macro_definition,
# Stream
"delay": eval_delay,
"cons-stream": eval_cons_stream
}
注意這里的dlambda特殊形式定義的是采用動(dòng)態(tài)作用域的過程，是原Scheme標(biāo)準(zhǔn)中沒有的。
apply
scheme_apply()有兩個(gè)參數(shù)，一個(gè)是過程，一個(gè)是該過程去應(yīng)用的實(shí)參表。scheme_apply()將過程分為兩類：基本過程（求值器內(nèi)置）和復(fù)合過程（通過define或lambda/dlambda特殊形式來定義）。對(duì)于基本過程，直接調(diào)用該過程對(duì)象的apply()方法去應(yīng)用實(shí)參，對(duì)于復(fù)合過程，則在新建環(huán)境后（該環(huán)境包含了形參綁定到實(shí)參的新幀），順序地求值組成該過程體的那些表達(dá)式。下面是scheme_apply()的定義：
@primitive("apply", use_env=True)
def scheme_apply(procedure, arguments, env):
validate_procedure(procedure)
if is_primitive_procedure(procedure):
return procedure.apply(arguments, env)
elif is_compound_procedure(procedure):
new_env = procedure.make_call_frame(arguments, env)
# Note that `tail` is set to True when `eval_sequence()` is called here
return eval_sequence(procedure.body, new_env, tail=True)
else:
raise SchemeError(
"Unknown procedure type: {0}".format(repl_str(procedure)))
條件
eval_if()先在給定的環(huán)境中求值if表達(dá)式的謂詞（predicate）部分，如果得到的結(jié)果為真，eval_if()就去求值這個(gè)if的推論（consequent）部分，否則就求值其替代（alternative）部分。其中需要注意，對(duì)于if語句是肯定有推論部分的，但是我們后面會(huì)將cond語句的求值規(guī)約到對(duì)if語句的求值，因cond語句推論可能為空，故此處需要做出判斷——若推論為空，則返回謂詞的求值結(jié)果，否則照常對(duì)推論求值。此外，如果if語句沒有替代部分，則返回False。
def eval_if(expr, env, tail=True):
validate_form(expr, min=2, max=3)
if_pred = if_predicate(expr)
if_predicate_val = scheme_eval(if_pred, env)
# All values in Scheme are true except `false` object,
# that is why we need `is_scheme_true()`
if is_scheme_true(if_predicate_val):
# Note that for `if` caluse , it muse have consequnet,
# so `if_consequent` can not be None (although it can be `nil`).
# But for `cond` clause, `if_consequent` can be None.
if_conseq = if_consequent(expr)
if if_conseq is None:
return if_predicate_val
else:
return scheme_eval(if_conseq, env, tail=tail)
# Turn to alternative
elif len(expr) == 3:
return scheme_eval(if_alternative(expr), env, tail=tail)
# If there is no alternative, return False
else:
return False
從eval_if()對(duì)is_scheme_true()的使用中，我們可以看到被實(shí)現(xiàn)語言（Scheme）和實(shí)現(xiàn)所用的語言（Python）之間的聯(lián)系。if_predicate()在被實(shí)現(xiàn)的語言里求值，產(chǎn)出這一語言里的一個(gè)值，而解釋器的謂詞is_scheme_true()實(shí)際上會(huì)將該值翻譯為可由實(shí)現(xiàn)所用語言的if檢測(cè)的值。這里因?yàn)樵赟cheme中，除了False之外的對(duì)象都應(yīng)被判斷為真，故我們實(shí)際上需要用Python將is_scheme_true()實(shí)現(xiàn)如下：
def is_scheme_true(val):
return val is not False
注意這里如果對(duì)象為真則返回該對(duì)象本身，而不是直接返回True。
至于cond表達(dá)式，可以做為派生表達(dá)式（derived expressions）由if表達(dá)式實(shí)現(xiàn)出來，而不必直接去實(shí)現(xiàn)。
def eval_cond(expr, env, tail=True):
return scheme_eval(cond_to_if(expr), env, tail)
最后，我們還需要實(shí)現(xiàn)and和or這兩個(gè)布爾表達(dá)式：
def eval_and(exprs, env, tail=True):
# If there is no expression to be evaluated, return True
if exprs is nil:
return True
# If the last expression is reached (indicating that the values of the
# previous expressions are all true), then the evaluation result is
# returned directly
elif rest_exprs(exprs) is nil:
return scheme_eval(first_expr(exprs), env, tail=tail)
value = scheme_eval(first_expr(exprs), env)
# If an expression evaluates to False, return False,
# and the remaining expressions are not evaluated
if is_scheme_false(value):
return False
else:
# If an expression evaluates to True, go on,
return eval_and(rest_exprs(exprs), env)
def eval_or(exprs, env, tail=True):
# If there is no expression to be evaluated, return True
if exprs is nil:
return False
# If the last expression is reached (indicating that the values of the
# previous expressions are all False), then the evaluation result is
# returned directly
elif rest_exprs(exprs) is nil:
return scheme_eval(first_expr(exprs), env, tail=tail)
value = scheme_eval(first_expr(exprs), env)
# If an expression evaluates to True, return value, and the remaining
# expressions are not evaluated
if is_scheme_true(value):
return value
else:
return eval_or(rest_exprs(exprs), env)
如上所示，and和or表達(dá)式都是短路（short-circuited）的。對(duì)于and表達(dá)式，如果其子表達(dá)式有求值為False的，則直接返回False；對(duì)于or表達(dá)式，如果其子表達(dá)式有求值為True的，直接返回True。
序列
eval_sequence()用在scheme_apply()里，用于求值過程體里的表達(dá)式序列。它也用在scheme_eval()里，用于求值begin和let表達(dá)式內(nèi)的表達(dá)式序列。這個(gè)過程以一個(gè)表達(dá)式序列和一個(gè)環(huán)境為參數(shù)，按照序列里表達(dá)式出現(xiàn)的順序?qū)λ鼈冞M(jìn)行求值，并返回最后一個(gè)表達(dá)式的值。
def eval_sequence(exprs, env, tail=False):
if not is_scheme_pair(exprs):
return
# If `exprs` is the last expression
if rest_exprs(exprs) is nil:
# The value of the last expression is returned as the value of the
# entire `begin` special form(or the body of a procedure)
return scheme_eval(first_expr(exprs), env, tail)
else:
# Evaluate the expressions <expr 1>, <expr 2>, ..., <expr k> in order
scheme_eval(first_expr(exprs), env)
return eval_sequence(rest_exprs(exprs), env, tail)
eval_begin()和eval_let()亦依據(jù)eval_sequence()來定義：
def eval_begin(exprs, env, tail=True):
validate_form(exprs, min=1)
return eval_sequence(exprs, env, tail)
def eval_let(exprs, env, tail=True):
validate_form(exprs, min=2)
let_env = make_let_env(first_expr(exprs), env)
return eval_sequence(rest_exprs(exprs), let_env, tail=tail)
賦值和定義
下面過程處理變量賦值，它先調(diào)用scheme_eval()求出需要賦的值，將變量和得到的值傳給env.set_variable_value()方法，將有關(guān)的值安置到環(huán)境env里。
def eval_assignment(expr, env):
env.set_variable_value(assignment_variable(
expr), scheme_eval(assignment_value(expr), env))
變量定義也用類似方式處理：
def eval_definition(expr, env):
# Check that expressions is a list of length at least 2
validate_form(expr, min=2)
var = definition_varaible(expr)
val = definition_value(expr)
env.define_variable(var,
scheme_eval(val, env))
return var
Lambda表達(dá)式
對(duì)lambda表達(dá)式進(jìn)行求值時(shí)（注意此時(shí)只是對(duì)lambda表達(dá)式的”定義“進(jìn)行求值），我們會(huì)先分別獲取lambda表達(dá)式的形參和過程體，并結(jié)合lambda表達(dá)式定義時(shí)的環(huán)境來初始化LambdaProcedure對(duì)象（也即默認(rèn)采用的基于詞法作用域規(guī)則）。
def eval_lambda(expr, env):
validate_form(expr, min=2)
parameters = lambda_parameters(expr)
validate_parameters(parameters)
body = lambda_body(expr)
return LambdaProcedure(parameters, body, env)
而對(duì)于我們額外添加的采用動(dòng)態(tài)作用域的dlambda表達(dá)式，在初始化時(shí)則不會(huì)用到其定義時(shí)的環(huán)境。
def eval_dlambda_form(expr, env):
validate_form(expr, min=2)
parameters = expr.first
validate_parameters(parameters)
return DLambdaProcedure(parameters, expr.rest)
引號(hào)表達(dá)式
對(duì)quote表達(dá)式（即'）進(jìn)行求值時(shí)，直接返回其所引用的表達(dá)式本身即可（無需環(huán)境）。
def eval_quote(expr, env):
validate_form(expr, min=1, max=1)
return text_of_quotation(expr)
對(duì)quasiquote表達(dá)式（即 ` ）進(jìn)行求值則是一個(gè)遞歸的過程，在獲得了 ` 所引用的表達(dá)式后，我們需要掃描該表達(dá)式查看是否有被unquote（即以,開頭）的子表達(dá)式，如果遇到了則對(duì)該子表達(dá)式求值，而其余表達(dá)式則保持不求值狀態(tài)。比如(1 2 ,(+ 3 4)) 的求值結(jié)果為'(1 2 7)。注意這里quasiquote內(nèi)部可以嵌套多個(gè)quasiquote和unquote，故需要在遞歸時(shí)維護(hù)depth變量來表示被unquote操作“抵消”后剩余的quasiquote深度。
def eval_quasiquote(expr, env):
def quasiquote_item(val, env, depth):
"""Evaluate Scheme expression `val` that is nested at depth `level` in
a quasiquote form in frame `env`."""
if not is_scheme_pair(val):
return val
# When encountering `unquote`, we decrease the depth by 1.
# If the depth is 0, we evaluate the rest expressions.
if is_tagged_list(val, "unquote"):
depth -= 1
if depth == 0:
expr = rest_exprs(val)
validate_form(expr, 1, 1)
return scheme_eval(first_expr(expr), env)
elif val.first == "quasiquote":
# Leave the item unevaluated
depth += 1
# Recursively quasiquote the items of the list
return val.map(lambda elem: quasiquote_item(elem, env, depth))
validate_form(expr, min=1, max=1)
# Note that when call `quasiquote_item`, we have encountered
# the first quasiquote, so depth=1
return quasiquote_item(text_of_quotation(expr), env, depth=1)
注意unquote操作是不能夠在quasiquote表達(dá)式之外進(jìn)行的，如果在quasiquote之外對(duì)unquote進(jìn)行求值，則會(huì)報(bào)對(duì)應(yīng)的錯(cuò)誤：
def eval_unquote(expr, env):
raise SchemeError("Unquote outside of quasiquote")
宏
對(duì)宏的定義，也即define-macro表達(dá)式進(jìn)行求值時(shí)，我們選擇將表達(dá)式的形參、表達(dá)式體及環(huán)境都保存到MacroProcedure對(duì)象中，而不立即進(jìn)行求值操作求值。此外，我們還在環(huán)境中添加宏的名稱與MacroProcedure對(duì)象的綁定。
def eval_macro_definition(expr, env):
validate_form(expr, min=2)
target = expr.first
if is_scheme_pair(target) and is_scheme_symbol(target.first):
func_name = target.first
# `target.rest` is parameters，not `target.rest.first`
parameters = target.rest
body = expr.rest
# Just store the expression, rather than evaluate it
env.define_variable(func_name, MacroProcedure(parameters, body, env))
return func_name
else:
raise SchemeError("Invalid use of macro")
4.1.2 表達(dá)式的表示
這個(gè)求值器很像我們?cè)诓┛?a href="http://www.rzrgm.cn/orion-orion/p/17026000.html" target="_blank">《SICP：符號(hào)求導(dǎo)、集合表示和Huffman樹（Python實(shí)現(xiàn)） 》中所討論的符號(hào)微分程序。這兩個(gè)程序完成的都是一些對(duì)符號(hào)表達(dá)式的操作。在這兩個(gè)程序中，對(duì)一個(gè)復(fù)合表達(dá)式的求值結(jié)果，也是由對(duì)表達(dá)式片段的遞歸操作來確定的，且對(duì)該結(jié)果的組合方式也是由表達(dá)式的類型來確定。在這兩個(gè)程序中，我們都采用了數(shù)據(jù)抽象技術(shù)，將一般性的操作規(guī)則與表達(dá)式的表示方式進(jìn)行了解耦（decouple）。在符號(hào)微分程序中，這意味著同一個(gè)微分程序可以處理前綴（prefix）形式、中綴（infix）形式或其他形式的代數(shù)表達(dá)式。對(duì)于求值器，這意味著被求值語言的語法（syntax）僅僅由對(duì)表達(dá)式進(jìn)行分類和片段提取的過程來決定。
這里需要提一下，我們求值器的輸入是以序?qū)?code>Pair組成的表，也即經(jīng)過詞法分析（lexical analysis）+語法分析（syntactic analysis）后所構(gòu)建的抽象語法樹（abstract syntax tree, AST）。比如對(duì)于 Scheme表達(dá)式
(+ (* 3 5) (- 10 6))其對(duì)應(yīng)的表為：
Pair('+', Pair(Pair('*', Pair(3, Pair(5, nil))), Pair(Pair('-', Pair(10, Pair(6, nil))), nil)))事實(shí)上由于Scheme程序本身就可視作一棵AST，因此為Scheme程序?qū)懹糜谡Z法分析的Parser異常簡(jiǎn)單。我們可以通過
Pair對(duì)象的.first屬性訪問其的第一個(gè)元素，.rest屬性訪問其的后續(xù)元素。
下面是我們所要實(shí)現(xiàn)的Scheme語言的語法規(guī)范：
- 這里的自求值表達(dá)式包括數(shù)、字符串、
nil（也即空表'()）、布爾值和undefined（在Python中表示為None）：
def is_self_evaluating(expr):
return is_scheme_boolean(expr) or is_scheme_number(expr) or \
is_scheme_null(expr) or is_scheme_string(expr) or expr is None
- 變量用符號(hào)表示：
def is_scheme_variable(x):
return is_scheme_symbol(x)
- 引號(hào)表達(dá)式的形式是
(quote <text-of-quotation>)（求值器看到的表達(dá)式是以quote開頭的表，即使這種表達(dá)式在輸入時(shí)用的是一個(gè)引號(hào)）：
def text_of_quotation(expr):
return expr.first
def is_unquote(expr):
return is_tagged_list(expr, "unquote")
注意這里對(duì)text_of_quotation()函數(shù)而言傳入的expr是不含標(biāo)簽quote的，故直接使用expr.first來訪問<text-of-quotation>即可。
is_unquote()函數(shù)借助函數(shù)is_tagged_list()來定義，它可用于確定一個(gè)表的開始是不是某個(gè)給定符號(hào)：
def is_tagged_list(expr, tag):
if is_scheme_pair(expr):
return expr.first == tag
else:
return False
注意我們這里沒有is_quote()函數(shù)，這是因?yàn)閷?duì)quote的類型判斷和其它特殊形式一樣，直接在scheme_eval()的分派過程中解決了。
- 賦值的形式是
(set! <var> <value>)：
def assignment_variable(expr):
return expr.first
def assignment_value(expr):
return expr.rest.first
同樣，注意此處的expr不含標(biāo)簽。
- 定義的形式是：
(define <var> <value>)
或者
(define (<var> <parameter 1>... <parameter n>)
<body>)
后一形式（標(biāo)準(zhǔn)的過程定義）只是下面形式的一種語法包裝：
(define <var>
(lambda (<parameter 1> ... <parameter n>)
<body>))
相應(yīng)的語法函數(shù)是
def definition_varaible(expr):
target = expr.first
# For the case of (define <var> <value>)
if is_scheme_symbol(target):
# `(define x)` or `(define x 2 y 4)` is invalid
validate_form(expr, min=2, max=2)
return target
# For the case of (define (<var> <param 1>, ..., <param n>) <body>)
elif is_scheme_pair(target) and is_scheme_symbol(target.first):
return target.first
else:
bad_target = target.first if is_scheme_pair(target) else target
raise SchemeError("Non-symbol: {0}".format(bad_target))
def definition_value(expr):
target = expr.first
# For the case of (define <var> <value>)
if is_scheme_symbol(target):
return expr.rest.first
# For the case of (define (<var> <param 1>, ..., <param n>) <body>)
elif is_scheme_pair(target) and is_scheme_symbol(target.first):
# Note: The validation of the lambda special form is turned over
# to `scheme_eval()`
return make_lambda(target.rest, expr.rest)
else:
bad_target = target.first if is_scheme_pair(target) else target
raise SchemeError("Non-symbol: {0}".format(bad_target))
同樣，注意此處的expr不含標(biāo)簽。
- lambda表達(dá)式是由符號(hào)
lambda開始的表：
def lambda_parameters(expr):
return expr.first
def lambda_body(expr):
return expr.rest
同樣，注意此處的expr不含標(biāo)簽。
我們還為lambda表達(dá)式提供了一個(gè)構(gòu)造函數(shù)，它用在上面的definition_value()里。
def make_lambda(parameters, body):
return scheme_cons("lambda", scheme_cons(parameters, body))
- 條件表達(dá)式由
if開始，有一個(gè)謂詞部分，一個(gè)推論部分和一個(gè)（可缺的）替代部分。如果這一表達(dá)式?jīng)]有替代部分，我們就用False做為其替代。
def if_predicate(expr):
return expr.first
def if_consequent(expr):
return expr.rest.first
def if_alternative(expr):
return expr.rest.rest.first
我們也為if表達(dá)式提供了一個(gè)構(gòu)造函數(shù)，它在cond_to_if中使用，用于將cond表達(dá)式變換為if表達(dá)式。
def make_if(predicate, consequent, alternative):
return scheme_list("if", predicate, consequent, alternative)
begin包裝起一個(gè)表達(dá)式序列。這里我們?cè)O(shè)計(jì)選擇函數(shù)返回序列中的第一個(gè)表達(dá)式和其余表達(dá)式。
def first_expr(seq):
return seq.first
def rest_exprs(seq):
return seq.rest
我們還設(shè)計(jì)了一個(gè)構(gòu)造函數(shù)sequence_to_expr()（用在cond_to_if里），它把一個(gè)序列變換為一個(gè)表達(dá)式，如果需要的話就加上begin作為開頭：
def sequence_to_expr(seq):
if seq is nil:
return seq
elif rest_exprs(seq) is nil:
return first_expr(seq)
else:
return make_begin(seq)
def make_begin(seq):
return scheme_cons("begin", seq)
let表達(dá)式在規(guī)約到用eval_sequence()對(duì)表達(dá)式序列進(jìn)行求值之前，需要新建環(huán)境。該新環(huán)境的構(gòu)造函數(shù)下：
def make_let_env(bindings, env):
def bindings_items(bindings, env):
if bindings is nil:
return nil, nil
binding = bindings.first
validate_form(binding, min=2, max=2)
var = binding.first
val = scheme_eval(binding.rest.first, env)
vars, vals = bindings_items(bindings.rest, env)
return scheme_cons(var, vars), scheme_cons(val, vals)
if not is_scheme_list(bindings):
raise SchemeError("Bad bindings list in let form")
vars, vals = bindings_items(bindings, env)
validate_parameters(vars)
return env.extend_environment(vars, vals)
派生表達(dá)式
在一些語言中，一些特殊形式可以基于其他特殊形式的表達(dá)式定義出來，而不必直接去實(shí)現(xiàn)，比如cond表達(dá)式和let表達(dá)式。這樣采用語法變換的方式實(shí)現(xiàn)的表達(dá)式稱為派生表達(dá)式（derived expressions）。
cond表達(dá)式可以實(shí)現(xiàn)為一些嵌套的if表達(dá)式。例如，我們可以將對(duì)于下列表達(dá)式的求值問題：
(cond ((> x 0) x)
((= x 0) (display 'zero) 0)
(else (- x)))
規(guī)約為對(duì)下面涉及if和begin的表達(dá)式的求值問題：
(if (> x 0)
x
(if (= x 0)
(begin (display 'zero)
0)
(- x)))
采用這種方式實(shí)現(xiàn)對(duì)cond的求值能簡(jiǎn)化求值器。
下面展示了提取cond表達(dá)式中各個(gè)部分的語法過程，以及函數(shù)cond_to_if()，它能將cond表達(dá)式變換為if表達(dá)式。一個(gè)分情況分析以cond開始，并包含一個(gè)謂詞-動(dòng)作子句的表。如果一個(gè)子句的符號(hào)是else，那么就是一個(gè)else子句。
def cond_predicate(clause):
return clause.first
def cond_actions(clause):
return clause.rest
def cond_to_if(exprs):
return expand_clauses(exprs)
def expand_clauses(clauses):
# return None means that interpreter does not print anything
if clauses is nil:
return None
first = clauses.first
rest = clauses.rest
validate_form(first, min=1)
if cond_predicate(first) == "else":
if rest is nil:
return sequence_to_expr(first.rest)
else:
raise SchemeError(
"ELSE clause is not last: {0}".format(
repl_str(clauses)))
else:
if cond_actions(first) is nil: # for example, (cond ((= 1 1)))
# there is no consequent, we denote it as None
# o distinguish it from nil
if_consequent = None
else: # for example, (cond ((= 1 1) 2)) or (cond ((= 1 1) nil))
# there is a consequent, including nil
if_consequent = sequence_to_expr(first.rest)
return make_if(cond_predicate(first), if_consequent, cond_to_if(
rest))
4.1.3 求值器數(shù)據(jù)結(jié)構(gòu)
除了需要定義表達(dá)式的外部語法之外，求值器的實(shí)現(xiàn)還必須定義好在其內(nèi)部實(shí)際操作的數(shù)據(jù)結(jié)構(gòu)，做為程序執(zhí)行的一部分。例如序列數(shù)據(jù)結(jié)構(gòu)，過程和環(huán)境的表示形式，真和假的表示方式等等。
序列數(shù)據(jù)結(jié)構(gòu)
如我們?cè)诓┛?a href="http://www.rzrgm.cn/orion-orion/p/16234680.html" target="_blank">《SICP: 層次性數(shù)據(jù)和閉包性質(zhì)（Python實(shí)現(xiàn)）》中所言，序列數(shù)據(jù)結(jié)構(gòu)由序?qū)磉M(jìn)行層次化定義，序?qū)Φ亩x如下：
class Pair:
def __init__(self, first, rest):
self.first = first
self.rest = rest
def __len__(self):
n, rest = 1, self.rest
while isinstance(rest, Pair):
n += 1
rest = rest.rest
# The tail of the list must be nil
if rest is not nil:
raise TypeError("length attempted on improper list")
return n
def __eq__(self, p):
if not isinstance(p, Pair):
return False
return self.first == p.first and self.rest == p.rest
def map(self, fn):
mapped = fn(self.first)
if self.rest is nil or isinstance(self.rest, Pair):
return Pair(mapped, self.rest.map(fn))
else:
raise TypeError("ill-formed list (cdr is a promise)")
def flatmap(self, fn):
from primitive_procs import scheme_append
mapped = fn(self.first)
if self.rest is nil or isinstance(self.rest, Pair):
return scheme_append(mapped, self.rest.flatmap(fn))
else:
raise TypeError("ill-formed list (cdr is a promise)")
此外，我們還需要一個(gè)空表類及其實(shí)例：
class nil:
def __len__(self):
return 0
def map(self, fn):
return self
def flatmap(self, fn):
return self
nil = nil()
注意，nil實(shí)例將與其相同的類名進(jìn)行了覆蓋，且該空表類自始至終只有一個(gè)實(shí)例，所以我們可以直接使用is nil語法來測(cè)試某個(gè)對(duì)象是否為空表。
謂詞檢測(cè)
為了實(shí)現(xiàn)條件表達(dá)式，我們把除了False對(duì)象之外的所有東西都接受為真：
def is_scheme_true(val):
return val is not False
def is_scheme_false(val):
return val is False
除了謂詞檢測(cè)之外，還有許多諸如is_scheme_pair()、is_scheme_list()之類的Scheme內(nèi)置數(shù)據(jù)結(jié)構(gòu)檢測(cè)函數(shù)，就不在此處進(jìn)行一一列舉了，大家可直接參考我項(xiàng)目目錄下的primitive_procs.py文件。
過程的表示
過程分為基本過程（primitive procedures）和復(fù)合過程（compound procedures，也即由define語句或lambda/dlambda語句定義的過程）。我們先定義基本過程如下：
class Procedure:
class PrimitiveProcedure(Procedure):
import primitive_procs as pprocs
def __init__(self, fn, name="primitive", use_env=False):
self.name = name
self.fn = fn
self.use_env = use_env
def apply(self, arguments, env):
if not self.pprocs.is_scheme_list(arguments):
raise self.pprocs.SchemeError(
"Arguments are not in a list: {0}".format(arguments))
# Convert a Scheme list to a Python list
arguments_list = self.flatten(arguments)
try:
if self.use_env:
return self.fn(*arguments_list, env)
return self.fn(*arguments_list)
except TypeError:
raise self.pprocs.SchemeError(
"Incorrect number of arguments: {0}".format(self))
def flatten(self, arguments):
if arguments is nil:
return []
else:
return [arguments.first] + self.flatten(arguments.rest)
下列函數(shù)可檢查過程是否為基本過程：
def is_primitive_procedure(procedure):
return isinstance(procedure, PrimitiveProcedure)
復(fù)合過程則包括形參parameters、過程體body和環(huán)境body：
class LambdaProcedure(Procedure):
import primitive_procs as pprocs
def __init__(self, parameters, body, env):
assert isinstance(env, Environment), "env must be of type Environment"
self.pprocs.validate_type(parameters, self.pprocs.is_scheme_list,
0, "LambdaProcedure")
self.pprocs.validate_type(
body, self.pprocs.is_scheme_list, 1, "LambdaProcedure")
self.parameters = parameters
self.body = body
self.env = env
def make_call_frame(self, arguments, env):
return self.env.extend_environment(self.parameters, arguments)
復(fù)合過程的make_call_frame()方法用于將復(fù)合過程對(duì)象應(yīng)用于實(shí)參時(shí)，向過程定義時(shí)的環(huán)境self.env中添加一個(gè)新幀（注意不是調(diào)用時(shí)環(huán)境env，調(diào)用時(shí)環(huán)境env并未使用），從而擴(kuò)展得到一個(gè)新的環(huán)境。具體的env.extend_environment()方法我們會(huì)在環(huán)境的表示部分再講述如何實(shí)現(xiàn)。
下列函數(shù)可檢查過程是否為復(fù)合過程：
def is_compound_procedure(procedure):
return isinstance(procedure, Procedure)
使用動(dòng)態(tài)作用域的dlambda過程對(duì)象定義如下：
class DLambdaProcedure(Procedure):
def __init__(self, parameters, body):
self.parameters = parameters
self.body = body
def make_call_frame(self, arguments, env):
return env.extend_environment(self.parameters, arguments)
該過程也是復(fù)合過程，唯一的區(qū)別是在過程應(yīng)用時(shí)，建立的新環(huán)境是基于調(diào)用時(shí)環(huán)境env來擴(kuò)展的，而不是定義時(shí)環(huán)境。
環(huán)境的表示
求值器還需要定義對(duì)環(huán)境的表示。正如我們?cè)诓┛?a href="http://www.rzrgm.cn/orion-orion/p/17247251.html" target="_blank">《SICP：求值和環(huán)境模型（Python實(shí)現(xiàn)）》中所說，一個(gè)環(huán)境就是一個(gè)幀的序列，每個(gè)幀都是一個(gè)包含綁定的表格，其中綁定關(guān)聯(lián)起一些變量和與之對(duì)應(yīng)的值。
我們首先定義好幀：
class Frame:
def __init__(self):
self.bindings = {}
def add_binding(self, var, val):
self.bindings[var] = val
def set_var(self, var, val):
self.add_binding(var, val)
然后在幀的基礎(chǔ)之上定義好環(huán)境：
class Environment:
import primitive_procs as pprocs
def __init__(self):
self.frames = self.pprocs.scheme_list(Frame())
def lookup_variable_value(self, var):
...
def extend_environment(self, vars, vals):
...
def define_variable(self, var, val):
...
def set_variable_value(self, var, val):
...
和環(huán)境有關(guān)的方法lookup_variable_value()、extend_environment()、define_variable()、set_variable_value()我們?cè)谙旅孢M(jìn)行分別闡述。
lookup_variable_value()方法返回符號(hào)var在環(huán)境里的綁定值，如果這一變量沒有綁定就發(fā)出一個(gè)錯(cuò)誤信號(hào)：
def lookup_variable_value(self, var):
def env_loop(frames):
# If cannot find the variable in the current environment
if self.pprocs.is_scheme_null(frames):
raise self.pprocs.SchemeError(
"Unbound variable: {0}".format(var))
frame = frames.first
if var in frame.bindings.keys():
return frame.bindings[var]
else:
return env_loop(frames.rest)
return env_loop(self.frames)
extend_environment()方法返回一個(gè)新環(huán)境，這個(gè)環(huán)境里包含了一個(gè)新幀，其中所有位于表vars里的符號(hào)綁定到表vals里對(duì)應(yīng)的元素，而該幀的外圍環(huán)境是當(dāng)前這個(gè)對(duì)象所對(duì)應(yīng)的環(huán)境。
def extend_environment(self, vars, vals):
new_env = Environment()
if len(vars) == len(vals):
new_env.frames = self.pprocs.scheme_cons(
self.make_frame(vars, vals),
self.frames)
elif len(vars) < len(vals):
raise self.pprocs.SchemeError(
"Too many arguemtns supplied")
else:
raise self.pprocs.SchemeError(
"Too few arguemtns supplied")
return new_env
@ staticmethod
def make_frame(vars, vals):
frame = Frame()
while isinstance(vars, Pair):
var = vars.first
val = vals.first
frame.add_binding(var, val)
vars = vars.rest
vals = vals.rest
return frame
define_variable()方法在當(dāng)前對(duì)象所對(duì)應(yīng)環(huán)境的第一個(gè)幀里加入一個(gè)新綁定，它關(guān)聯(lián)起變量var和val。
def define_variable(self, var, val):
frame = self.frames.first
frame.add_binding(var, val)
set_variable_value()方法修改變量var在當(dāng)前對(duì)象所對(duì)應(yīng)環(huán)境里的綁定，使得該變量現(xiàn)在綁定到值val。如果這一變量沒有綁定就發(fā)出一個(gè)錯(cuò)誤信號(hào)。
def set_variable_value(self, var, val):
def env_loop(frames):
# 空表
if self.pprocs.is_scheme_null(frames):
raise self.pprocs.SchemeError(
"Unbound variable: {0}".format(var))
frame = frames.first
if var in frame.bindings.keys():
frame.set_var(var, val)
return
else:
env_loop(frames.rest)
env_loop(self.frames)
不過需要注意的是，這里所描述的方法，只不過是表示環(huán)境的許多方法之一。由于前面采用了數(shù)據(jù)抽象的技術(shù)，而這已經(jīng)將求值器的其它部分與這些表示細(xì)節(jié)隔離開，因此如果需要的話我們也完全可以修改環(huán)境的表示。在產(chǎn)品質(zhì)量的Lisp系統(tǒng)里，求值器中環(huán)境操作的速度——特別是查找變量的速度——對(duì)系統(tǒng)的性能有著重要的影響。這里所描述的表示方式雖然在概念上非常簡(jiǎn)單，但其工作效率卻很低，通常不會(huì)用在產(chǎn)品系統(tǒng)里。其低效的原因來自求值器為了找到一個(gè)給定變量的綁定，需要搜索許多個(gè)幀。這樣一種方式稱為深約束。避免這一低效性的方法是采用一種稱為語法作用域的策略，可參考原書5.5.6節(jié)。
4.1.4 作為程序運(yùn)行這個(gè)求值器
有了一個(gè)求值器，我們手頭上就有了一個(gè)有關(guān)Lisp表達(dá)式如何求值的程序描述（這是用Python描述的）。接下來我們來看如何運(yùn)行這個(gè)程序。
我們的求值器程序最終把表達(dá)式規(guī)約到基本過程的應(yīng)用（基本過程的定義在項(xiàng)目代碼中的primitive_procs.py文件中）。而每個(gè)基本過程名都必須有一個(gè)綁定，以便當(dāng)scheme_eval()求值一個(gè)應(yīng)用基本過程的運(yùn)算符時(shí)，可以找到相應(yīng)的對(duì)象，并調(diào)用這個(gè)對(duì)象的apply方法。為此我們必須創(chuàng)建起一個(gè)初始環(huán)境，在其中建立起基本過程的名字與一個(gè)唯一對(duì)象的關(guān)聯(lián)，在求值表達(dá)式時(shí)的過程中可能遇到這些名字。
def setup_environment():
initial_env = Environment()
initial_env.define_variable("undefined", None)
add_primitives(initial_env, PRIMITIVE_PROCS)
return initial_env
這里的PRIMITIVE_PROCS是一個(gè)Python全局變量，具體而言是一個(gè)存儲(chǔ)了基本過程函數(shù)及其名稱的表。基本過程對(duì)象的具體表示方式我們已經(jīng)在上文中提到，也就是PrimitiveProcedure，因此我們可以用下列函數(shù)將基本過程名稱及其對(duì)象的綁定添加到全局環(huán)境中：
def add_primitives(env, funcs_and_names):
for fn, name, use_env in funcs_and_names:
env.define_variable(name, PrimitiveProcedure(
fn, name=name, use_env=use_env))
為了能夠很方便地運(yùn)行這個(gè)元循環(huán)求值器，我們使用函數(shù)read_eval_print_loop()來模擬Lisp中的讀入-求值-打印循環(huán)。這個(gè)循環(huán)打印出一個(gè)提示符（prompt），讀入輸入表達(dá)式，進(jìn)行詞法分析和語法分析轉(zhuǎn)換為AST后，再在全局環(huán)境里求值這個(gè)表達(dá)式，而后打印出得到的結(jié)果。
def read_eval_print_loop(env, infile_lines=None, interactive=False,
quiet=False, startup=False, load_files=(),
report_errors=False, print_ast=False):
if startup:
for filename in load_files:
scheme_load(filename, True, env)
# Initialize a tokenizer instance
tokenizer = Tokenizer()
# Initialize a parser instance
parser = Parser()
while True:
try:
lines_stream = read_input(infile_lines, input_prompt="scm> ")
# Tokenize the input lines
lines_stream = (tokenizer.tokenize(line) for line in lines_stream)
# Parse a single expression / multiple expressions util all the
# tokens are consumed
while True:
# Parse a complete expression (single-line or multi-line) at a
# time
ast = parser.parse(lines_stream)
result = scheme_eval(ast, env)
if not quiet:
print(repl_str(result))
# If all the tokens read are consumed, then break
if parser.is_empty():
break
except (SchemeError, SyntaxError, ValueError, RuntimeError) as err:
...
def read_input(infile_lines, input_prompt):
if infile_lines: # If use a file stream as input
while infile_lines:
line = infile_lines.pop(0).strip("\n")
yield line
raise EOFError
else: # if use a keyboard stream as input
while True:
yield input(input_prompt)
# If a multi-line expression input is not
# terminated, use whitespace as the
# the input prompt to read more lines.
input_prompt = " " * len(input_prompt)
為了運(yùn)行這個(gè)求值器，現(xiàn)在我們需要著的全部事情就是初始化這個(gè)全局環(huán)境，并啟動(dòng)上述的讀入-求值-打印循環(huán)。
def main():
args = parse_args()
sys.path.insert(0, "")
interactive = True
load_files = []
if args.load:
for filename in args.filenames:
load_files.append(filename)
the_global_env = setup_environment()
read_eval_print_loop(env=the_global_env, startup=True,
interactive=interactive, load_files=load_files,
print_ast=args.ast)
下面是一個(gè)交互過程實(shí)例：
scm> (define (make-withdraw balance)
(lambda (amount)
(If (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds")))
make-withdraw
scm> (define W1 (make-withdraw 100))
w1
scm> (define W2 (make-withdraw 100))
w2
scm> (W1 50)
50
scm> (W2 70)
30
scm> (W2 40)
"Insufficient funds"
scm> (W1 40)
10
4.1.5 將數(shù)據(jù)作為程序
在思考求值Lisp表達(dá)式的Python程序時(shí)，有一個(gè)類比可能很有幫助。關(guān)于程序意義的一種操作式觀點(diǎn)（operational view），就是將程序看做是一種抽象的（可能無窮大的）機(jī)器的一個(gè)描述。比如考慮下面的Lisp求階乘程序：
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
我們可以將這一程序看成一部機(jī)器的描述。這部機(jī)器包含的部分有遞減（decrement）、乘法（multiply）以及相等測(cè)試（tests for equality），還有一個(gè)兩位開關(guān)（即if分支）和另一部階乘機(jī)器（這樣，階乘機(jī)器就是無窮的，因?yàn)槠渲邪硪徊侩A乘機(jī)器）。下圖是這部階乘機(jī)器的流程圖，說明了有關(guān)的部分如何連接在一起。
，看做抽象機(jī)器.png)
按照類似的方式，我們也可以把求值器看做是一部非常特殊的機(jī)器，它要求以一部機(jī)器的描述作為輸入。給定了這個(gè)輸入之后，求值器就能夠規(guī)劃自己的行為（configures itself）來模擬被描述的機(jī)器。舉例來說，如果我們將factorial過程的定義送入求值器，求值器能夠計(jì)算階乘，如下圖所示：
器的求值器.png)
按照這一觀點(diǎn)，我們的求值器可以被看做是是一種通用機(jī)器（universal machine）。它能夠模擬其它的任何機(jī)器，只要它們已經(jīng)被描述為L(zhǎng)isp程序。這是非常驚人的。比如我們?yōu)殡娮与娐吩O(shè)想一種類似的求值器，這將會(huì)是一種電路，它以另一個(gè)電路（例如某個(gè)濾波器）的信號(hào)編碼方案做為輸入。在給了它這種輸入之后，這一電路求值器能具有與這一描述所對(duì)應(yīng)的濾波器同樣的行為。這樣的一個(gè)通用電子線路將會(huì)難以想象的復(fù)雜，而程序的求值器卻是一個(gè)相當(dāng)簡(jiǎn)單的程序。
事實(shí)上，任一求值器都能模擬其他的求值器。這樣，有關(guān)“原則上說什么可以計(jì)算”（忽略掉有關(guān)所需時(shí)間和空間的實(shí)踐性問題）的概念就與語言或計(jì)算機(jī)無關(guān)了，它反映的是一個(gè)有關(guān)可計(jì)算性（computability） 的基本概念。這一思想第一次是由圖靈以清晰的方式闡述，他在1936年的論文《論可計(jì)算數(shù)及其在判定性問題上的應(yīng)用》[2]為理論計(jì)算機(jī)科學(xué)奠定了基礎(chǔ)。在這篇論文里，圖靈給出了一種簡(jiǎn)單的計(jì)算模型——現(xiàn)在被稱為圖靈機(jī)——并聲稱，任何“有效過程”都可以描述為這種機(jī)器的一個(gè)程序（這一論斷就是著名的邱奇—圖靈論題）。圖靈而后實(shí)現(xiàn)了一臺(tái)通用機(jī)器，即一臺(tái)圖靈機(jī)，其行為就像是所有圖靈機(jī)程序的求值器。
求值器的另一驚人方面，在于它就像是在我們的程序設(shè)計(jì)語言所操作的數(shù)據(jù)對(duì)象和這個(gè)程序設(shè)計(jì)語言本身之間的一座橋梁。現(xiàn)在設(shè)想這個(gè)用Python實(shí)現(xiàn)的求值程序正在運(yùn)行，一個(gè)用戶正在輸入表達(dá)式并觀察所得到的結(jié)果。從用戶的觀點(diǎn)看，他所輸入的形如(* x x)的表達(dá)式是程序設(shè)計(jì)語言里的一個(gè)表達(dá)式，是求值器將要執(zhí)行的東西。而從求值器的觀點(diǎn)看，這一表達(dá)式不過是一個(gè)表（這里就是三個(gè)符號(hào)*、x和x的表），它所要做的也就是按照一套定義良好的規(guī)則去操作這個(gè)表。
這種用戶程序即求值器的數(shù)據(jù)的情況，未必會(huì)成為混亂之源。事實(shí)上，有時(shí)簡(jiǎn)單地忽略這種差異，為用戶提供顯式地將數(shù)據(jù)對(duì)象當(dāng)做Lisp表達(dá)式求值的能力，允許他們?cè)诔绦蚶镏苯邮褂?code>eval，甚至可能帶來許多方便。在我們實(shí)現(xiàn)的這個(gè)求值器里，就可以直接使用eval過程：
scm> (eval '(* 5 5))
25
scm> (eval (cons '* (list 5 5)))
25
事實(shí)上，Python語言中也內(nèi)置了eval()函數(shù)：
>>> eval("5 * 5")
25
參考
- [1] Abelson H, Sussman G J. Structure and interpretation of computer programs[M]. The MIT Press, 1996.
- [2] Turing A M. On computable numbers, with an application to the Entscheidungsproblem[J]. J. of Math, 1936, 58(345-363): 5.
浙公網(wǎng)安備 33010602011771號(hào)