求值器完整實作代碼我已經上傳到了GitHub倉庫：TinySCM，感興趣的童鞋可以前往查看，這里順便強烈推薦UC Berkeley的同名課程CS 61A，
在這個層次結構的最底層是物件語言，物件語言只涉及特定的域，而不涉及物件語言本身（比如它們的文法規則，或其中的其體句子），如要涉及它們，則要有一種元語言，對于語言的兩個層次這一經驗，所有學習外國語的人都是很熟悉的，然后，就要有一種元元語言來討論元語言，以此類推，
——侯世達《哥德爾、埃舍爾、巴赫：集異璧之大成》
緒論
到目前為止，我們探討的都是通過程序抽象、資料抽象以及模塊化等手段來控制系統的復雜性，為了闡釋這些技術，我們一直使用的是同一種編程語言，然而，隨著我們所面對的問題更復雜，我們必須經常轉向新的語言，以便能夠有效地表述自己的想法，實際上，建立新語言是工程設計中控制復雜性的一種威力強大的作業策略，我們常常能通過采用一種新語言而處理復雜問題的能力，
元語言抽象就是建立新的語言，它在工程設計的所有分支中都扮演著重要的角色，在計算機程式設計領域更是特別重要，因為這個領域中，我們不僅可以設計新的語言，還可以通過構造求值器的方式實作這些語言，對某個程式設計語言的求值器（或者解釋器）也是一個程序，在應用于這個語言的一個運算式時，它能夠執行求值這個運算式所要求的動作，
把這一點看做是程式設計語言中最基本的思想一點也不過分：
求值器決定了一個程式設計語言中各種運算式的意義，而它本身也不過就是另一個程式，
事實上，我們幾乎可以把任何程式看做是某個語言的求值器，比如在符號代數中，一個多項式系統包含著多項式的算數規則以及底層的實作，一個符號求導系統亦包含著函式求導的規則以及底層的實作（參見我之前的博客《SICP：符號求導、集合表示和Huffman樹（Python實作）》），從這樣一種觀點看，處理大規模計算機系統的技術，與構造新的程式設計語言的技術有緊密的聯系，而計算機科學中一個重要的思想就是如何去構造適當的描述語言，
接下來我們將要討論如何關于在一些語言的基礎上構造新的語言，在這篇博客里，我們將用Python語言去構造一個Scheme語言的求值器，事實上求值器的實作語言無關緊要，我們也可以用Scheme語言去構造Scheme語言的求值器，用于被求值語言同樣的語言寫出來的求值器被稱為元回圈（metacircular），
從根本上說，元回圈求值器也就是我們在博客《SICP：賦值和區域狀態（Python實作）》中所描述求值的環境模型的一個實作形式，回憶一下，該模型包括兩個部分：
- 在求值一個組合式（combinations）（非特殊形式的復合運算式）時，首先求值其中的子運算式（包括運算子和運算物件），然后將運算子的值（即一個程序物件）應用于運算物件的值，
- 在將一個復合程序物件應用于一集實參時，我們將在一個新環境里求值這個程序的體，構造這一新環境的方式是用一個幀來擴充該程序物件原來的環境，幀中包含的是這個程序的形參與所應用的實參之間的系結，
這兩條規則描述了求值程序的核心部分，也就是它的基本回圈，在這一回圈中，運算式在環境中的求值被規約到程序對實參的應用，而這種應用又被規約到新的運算式在新的環境中的求值，如此下去，直至我們下降到符號（其值可以在環境中找到）或基本程序（它們可以直接應用）， 如下圖所示：
這一求值回圈實際體現為求值器里的兩個關鍵函式scheme_eval()和scheme_apply()的相互作用，我們在4.1.1節將描述他們，
求值器的實作依賴于一些定義了被求值運算式的 語法（syntax） （也即被求值運算式是以何種資料結構來表示的）的程序，我們仍將采用自頂向下的資料抽象技術，設法使求值器獨立于語言的具體表示，例如，對于賦值運算式(set! <var> <val>)，我們用抽象的選取函式assignment_variable()和assignment_value()去訪問賦值中相應的部分（不過這里需要注意，為了方便后面的型別分派操作，我們仍然假設可以用first_expr()和rest_exprs()分別去訪問運算式的首元素和其余元素，算是對抽象性的一個小小的擊穿吧），運算式的具體表示將在4.1.2節里描述，在4.1.3里還會描述一些程序和環境的表示形式，如Environment類、LambdaProcedure類的定義及其對應的一些方法，
4.1.1 求值器的內核
求值程序可以描述為兩個函式scheme_eval()和scheme_apply()之間的相互作用（interplay），
eval
scheme_eval()的引數是一個運算式和一個環境，scheme_eval()對運算式進行分類以此展開后續的求值作業，正如我們上面所說，我們采用選取函式first_expr()和rest_exprs()分別去訪問運算式的首元素和其余元素，并根據運算式的首元素（也即其標簽）來完成運算式型別的判定，運算式的型別可做如下分類：
基本運算式：
- 對于自求值運算式，例如數和字串等（其實也就是我們常說的字面值，literals），
scheme_eval()直接回傳這個運算式本身， - 對于變數，
scheme_eval()必須在環境中查找變數的值，
特殊形式（special forms）：
- 這里的特殊形式包括
if運算式、變數的賦值/定義、引號（'）運算式、lambda運算式等、我們的處理方式是將其分派給不同的名為eval_×××()的求值函式處理，如if運算式就分派給eval_if()函式來處理，
組合式（combinations）：
- 這里的組合式也即程序的應用（application），對于一個程序應用，
scheme_eval()必須先遞回地求值組合式的運算子部分和運算物件部分，而后將這樣得到的程序物件和引數送給scheme_apply()，由它去處理實際的程序應用，注意，如果運算子部分是宏（Macro），則不需要事先對其進行求值就直接將其應用，待應用完畢之后再進行求值，
下面是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，這里的特殊形式的型別分派采用了資料導向的方式（這種做法可以使用戶更容易增加scheme_eval()能分辨的運算式型別，而又不必修改scheme_eval()的定義本身），所有的SPECIAL_FORMS及其所分派的求值函式如下所示：
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特殊形式定義的是采用動態作用域的程序，是原Scheme標準中沒有的，
apply
scheme_apply()有兩個引數，一個是程序，一個是該程序去應用的實參表，scheme_apply()將程序分為兩類：基本程序（求值器內置）和復合程序（通過define或lambda/dlambda特殊形式來定義），對于基本程序，直接呼叫該程序物件的apply()方法去應用實參，對于復合程序，則在新建環境后（該環境包含了形參系結到實參的新幀），順序地求值組成該程序體的那些運算式，下面是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()先在給定的環境中求值if運算式的謂詞（predicate）部分，如果得到的結果為真，eval_if()就去求值這個if的推論（consequent）部分，否則就求值其替代（alternative）部分，其中需要注意，對于if陳述句是肯定有推論部分的，但是我們后面會將cond陳述句的求值規約到對if陳述句的求值，因cond陳述句推論可能為空，故此處需要做出判斷——若推論為空，則回傳謂詞的求值結果，否則照常對推論求值，此外，如果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()對is_scheme_true()的使用中，我們可以看到被實作語言（Scheme）和實作所用的語言（Python）之間的聯系，if_predicate()在被實作的語言里求值，產出這一語言里的一個值，而解釋器的謂詞is_scheme_true()實際上會將該值翻譯為可由實作所用語言的if檢測的值，這里因為在Scheme中，除了False之外的物件都應被判斷為真，故我們實際上需要用Python將is_scheme_true()實作如下：
def is_scheme_true(val):
return val is not False
注意這里如果物件為真則回傳該物件本身，而不是直接回傳True，
至于cond運算式，可以做為派生運算式（derived expressions）由if運算式實作出來，而不必直接去實作，
def eval_cond(expr, env, tail=True):
return scheme_eval(cond_to_if(expr), env, tail)
最后，我們還需要實作and和or這兩個布爾運算式：
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 = https://www.cnblogs.com/orion-orion/archive/2023/05/15/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運算式都是短路（short-circuited）的，對于and運算式，如果其子運算式有求值為False的，則直接回傳False；對于or運算式，如果其子運算式有求值為True的，直接回傳True，
序列
eval_sequence()用在scheme_apply()里，用于求值程序體里的運算式序列，它也用在scheme_eval()里，用于求值begin和let運算式內的運算式序列，這個程序以一個運算式序列和一個環境為引數，按照序列里運算式出現的順序對它們進行求值，并回傳最后一個運算式的值，
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()亦依據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)
賦值和定義
下面程序處理變數賦值，它先呼叫scheme_eval()求出需要賦的值，將變數和得到的值傳給env.set_variable_value()方法，將有關的值安置到環境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運算式
對lambda運算式進行求值時（注意此時只是對lambda運算式的”定義“進行求值），我們會先分別獲取lambda運算式的形參和程序體，并結合lambda運算式定義時的環境來初始化LambdaProcedure物件（也即默認采用的基于詞法作用域規則），
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)
而對于我們額外添加的采用動態作用域的dlambda運算式，在初始化時則不會用到其定義時的環境，
def eval_dlambda_form(expr, env):
validate_form(expr, min=2)
parameters = expr.first
validate_parameters(parameters)
return DLambdaProcedure(parameters, expr.rest)
引號運算式
對quote運算式（即'）進行求值時，直接回傳其所參考的運算式本身即可（無需環境），
def eval_quote(expr, env):
validate_form(expr, min=1, max=1)
return text_of_quotation(expr)
對quasiquote運算式（即 ` ）進行求值則是一個遞回的程序，在獲得了 ` 所參考的運算式后，我們需要掃描該運算式查看是否有被unquote（即以,開頭）的子運算式，如果遇到了則對該子運算式求值，而其余運算式則保持不求值狀態，比如(1 2 ,(+ 3 4)) 的求值結果為'(1 2 7)，注意這里quasiquote內部可以嵌套多個quasiquote和unquote，故需要在遞回時維護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運算式之外進行的，如果在quasiquote之外對unquote進行求值，則會報對應的錯誤：
def eval_unquote(expr, env):
raise SchemeError("Unquote outside of quasiquote")
宏
對宏的定義，也即define-macro運算式進行求值時，我們選擇將運算式的形參、運算式體及環境都保存到MacroProcedure物件中，而不立即進行求值操作求值，此外，我們還在環境中添加宏的名稱與MacroProcedure物件的系結，
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 運算式的表示
這個求值器很像我們在博客《SICP：符號求導、集合表示和Huffman樹（Python實作） 》中所討論的符號微分程式，這兩個程式完成的都是一些對符號運算式的操作，在這兩個程式中，對一個復合運算式的求值結果，也是由對運算式片段的遞回操作來確定的，且對該結果的組合方式也是由運算式的型別來確定，在這兩個程式中，我們都采用了資料抽象技術，將一般性的操作規則與運算式的表示方式進行了解耦（decouple），在符號微分程式中，這意味著同一個微分程式可以處理前綴（prefix）形式、中綴（infix）形式或其他形式的代數運算式，對于求值器，這意味著被求值語言的語法（syntax）僅僅由對運算式進行分類和片段提取的程序來決定，
這里需要提一下，我們求值器的輸入是以序對
Pair組成的表，也即經過詞法分析（lexical analysis）+語法分析（syntactic analysis）后所構建的抽象語法樹（abstract syntax tree, AST），比如對于 Scheme運算式(+ (* 3 5) (- 10 6))其對應的表為：
Pair('+', Pair(Pair('*', Pair(3, Pair(5, nil))), Pair(Pair('-', Pair(10, Pair(6, nil))), nil)))事實上由于Scheme程式本身就可視作一棵AST，因此為Scheme程式寫用于語法分析的Parser例外簡單，我們可以通過
Pair物件的.first屬性訪問其的第一個元素，.rest屬性訪問其的后續元素，
下面是我們所要實作的Scheme語言的語法規范：
- 這里的自求值運算式包括數、字串、
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
- 變數用符號表示：
def is_scheme_variable(x):
return is_scheme_symbol(x)
- 引號運算式的形式是
(quote <text-of-quotation>)（求值器看到的運算式是以quote開頭的表，即使這種運算式在輸入時用的是一個引號）：
def text_of_quotation(expr):
return expr.first
def is_unquote(expr):
return is_tagged_list(expr, "unquote")
注意這里對text_of_quotation()函式而言傳入的expr是不含標簽quote的，故直接使用expr.first來訪問<text-of-quotation>即可，
is_unquote()函式借助函式is_tagged_list()來定義，它可用于確定一個表的開始是不是某個給定符號：
def is_tagged_list(expr, tag):
if is_scheme_pair(expr):
return expr.first == tag
else:
return False
注意我們這里沒有is_quote()函式，這是因為對quote的型別判斷和其它特殊形式一樣，直接在scheme_eval()的分派程序中解決了，
- 賦值的形式是
(set! <var> <value>)：
def assignment_variable(expr):
return expr.first
def assignment_value(expr):
return expr.rest.first
同樣，注意此處的expr不含標簽，
- 定義的形式是：
(define <var> <value>)
或者
(define (<var> <parameter 1>... <parameter n>)
<body>)
后一形式（標準的程序定義）只是下面形式的一種語法包裝：
(define <var>
(lambda (<parameter 1> ... <parameter n>)
<body>))
相應的語法函式是
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不含標簽，
- lambda運算式是由符號
lambda開始的表：
def lambda_parameters(expr):
return expr.first
def lambda_body(expr):
return expr.rest
同樣，注意此處的expr不含標簽，
我們還為lambda運算式提供了一個建構式，它用在上面的definition_value()里，
def make_lambda(parameters, body):
return scheme_cons("lambda", scheme_cons(parameters, body))
- 條件表達式由
if開始，有一個謂詞部分，一個推論部分和一個（可缺的）替代部分，如果這一運算式沒有替代部分，我們就用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運算式提供了一個建構式，它在cond_to_if中使用，用于將cond運算式變換為if運算式，
def make_if(predicate, consequent, alternative):
return scheme_list("if", predicate, consequent, alternative)
begin包裝起一個運算式序列，這里我們設計選擇函式回傳序列中的第一個運算式和其余運算式，
def first_expr(seq):
return seq.first
def rest_exprs(seq):
return seq.rest
我們還設計了一個建構式sequence_to_expr()（用在cond_to_if里），它把一個序列變換為一個運算式，如果需要的話就加上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運算式在規約到用eval_sequence()對運算式序列進行求值之前，需要新建環境，該新環境的建構式下：
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)
派生運算式
在一些語言中，一些特殊形式可以基于其他特殊形式的運算式定義出來，而不必直接去實作，比如cond運算式和let運算式，這樣采用語法變換的方式實作的運算式稱為派生運算式（derived expressions），
cond運算式可以實作為一些嵌套的if運算式，例如，我們可以將對于下列運算式的求值問題：
(cond ((> x 0) x)
((= x 0) (display 'zero) 0)
(else (- x)))
規約為對下面涉及if和begin的運算式的求值問題：
(if (> x 0)
x
(if (= x 0)
(begin (display 'zero)
0)
(- x)))
采用這種方式實作對cond的求值能簡化求值器，
下面展示了提取cond運算式中各個部分的語法程序，以及函式cond_to_if()，它能將cond運算式變換為if運算式，一個分情況分析以cond開始，并包含一個謂詞-動作子句的表，如果一個子句的符號是else，那么就是一個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 求值器資料結構
除了需要定義運算式的外部語法之外，求值器的實作還必須定義好在其內部實際操作的資料結構，做為程式執行的一部分，例如序列資料結構，程序和環境的表示形式，真和假的表示方式等等，
序列資料結構
如我們在博客《SICP: 層次性資料和閉包性質（Python實作）》中所言，序列資料結構由序對來進行層次化定義，序對的定義如下：
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)")
此外，我們還需要一個空表類及其實體：
class nil:
def __len__(self):
return 0
def map(self, fn):
return self
def flatmap(self, fn):
return self
nil = nil()
注意，nil實體將與其相同的類名進行了覆寫，且該空表類自始至終只有一個實體，所以我們可以直接使用is nil語法來測驗某個物件是否為空表，
謂詞檢測
為了實作條件運算式，我們把除了False物件之外的所有東西都接受為真：
def is_scheme_true(val):
return val is not False
def is_scheme_false(val):
return val is False
除了謂詞檢測之外，還有許多諸如is_scheme_pair()、is_scheme_list()之類的Scheme內置資料結構檢測函式，就不在此處進行一一列舉了，大家可直接參考我專案目錄下的primitive_procs.py檔案，
程序的表示
程序分為基本程序（primitive procedures）和復合程序（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)
下列函式可檢查程序是否為基本程序：
def is_primitive_procedure(procedure):
return isinstance(procedure, PrimitiveProcedure)
復合程序則包括形參parameters、程序體body和環境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)
復合程序的make_call_frame()方法用于將復合程序物件應用于實參時，向程序定義時的環境self.env中添加一個新幀（注意不是呼叫時環境env，呼叫時環境env并未使用），從而擴展得到一個新的環境，具體的env.extend_environment()方法我們會在環境的表示部分再講述如何實作，
下列函式可檢查程序是否為復合程序：
def is_compound_procedure(procedure):
return isinstance(procedure, Procedure)
使用動態作用域的dlambda程序物件定義如下：
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)
該程序也是復合程序，唯一的區別是在程序應用時，建立的新環境是基于呼叫時環境env來擴展的，而不是定義時環境，
環境的表示
求值器還需要定義對環境的表示，正如我們在博客《SICP：求值和環境模型（Python實作）》中所說，一個環境就是一個幀的序列，每個幀都是一個包含系結的表格，其中系結關聯起一些變數和與之對應的值，
我們首先定義好幀：
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)
然后在幀的基礎之上定義好環境：
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):
...
和環境有關的方法lookup_variable_value()、extend_environment()、define_variable()、set_variable_value()我們在下面進行分別闡述，
lookup_variable_value()方法回傳符號var在環境里的系結值，如果這一變數沒有系結就發出一個錯誤信號：
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()方法回傳一個新環境，這個環境里包含了一個新幀，其中所有位于表vars里的符號系結到表vals里對應的元素，而該幀的外圍環境是當前這個物件所對應的環境，
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()方法在當前物件所對應環境的第一個幀里加入一個新系結，它關聯起變數var和val，
def define_variable(self, var, val):
frame = self.frames.first
frame.add_binding(var, val)
set_variable_value()方法修改變數var在當前物件所對應環境里的系結，使得該變數現在系結到值val，如果這一變數沒有系結就發出一個錯誤信號，
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)
不過需要注意的是，這里所描述的方法，只不過是表示環境的許多方法之一，由于前面采用了資料抽象的技術，而這已經將求值器的其它部分與這些表示細節隔離開，因此如果需要的話我們也完全可以修改環境的表示，在產品質量的Lisp系統里，求值器中環境操作的速度——特別是查找變數的速度——對系統的性能有著重要的影響，這里所描述的表示方式雖然在概念上非常簡單，但其作業效率卻很低，通常不會用在產品系統里，其低效的原因來自求值器為了找到一個給定變數的系結，需要搜索許多個幀，這樣一種方式稱為深約束，避免這一低效性的方法是采用一種稱為語法作用域的策略，可參考原書5.5.6節，
4.1.4 作為程式運行這個求值器
有了一個求值器，我們手頭上就有了一個有關Lisp運算式如何求值的程式描述（這是用Python描述的），接下來我們來看如何運行這個程式，
我們的求值器程式最終把運算式規約到基本程序的應用（基本程序的定義在專案代碼中的primitive_procs.py檔案中），而每個基本程序名都必須有一個系結，以便當scheme_eval()求值一個應用基本程序的運算子時，可以找到相應的物件，并呼叫這個物件的apply方法，為此我們必須創建起一個初始環境，在其中建立起基本程序的名字與一個唯一物件的關聯，在求值運算式時的程序中可能遇到這些名字，
def setup_environment():
initial_env = Environment()
initial_env.define_variable("undefined", None)
add_primitives(initial_env, PRIMITIVE_PROCS)
return initial_env
這里的PRIMITIVE_PROCS是一個Python全域變數，具體而言是一個存盤了基本程序函式及其名稱的表，基本程序物件的具體表示方式我們已經在上文中提到，也就是PrimitiveProcedure，因此我們可以用下列函式將基本程序名稱及其物件的系結添加到全域環境中：
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))
為了能夠很方便地運行這個元回圈求值器，我們使用函式read_eval_print_loop()來模擬Lisp中的讀入-求值-列印回圈，這個回圈列印出一個提示符（prompt），讀入輸入運算式，進行詞法分析和語法分析轉換為AST后，再在全域環境里求值這個運算式，而后列印出得到的結果，
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)
為了運行這個求值器，現在我們需要著的全部事情就是初始化這個全域環境，并啟動上述的讀入-求值-列印回圈，
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)
下面是一個互動程序實體：
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 將資料作為程式
在思考求值Lisp運算式的Python程式時，有一個類比可能很有幫助，關于程式意義的一種操作式觀點（operational view），就是將程式看做是一種抽象的（可能無窮大的）機器的一個描述，比如考慮下面的Lisp求階乘程式：
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
我們可以將這一程式看成一部機器的描述，這部機器包含的部分有遞減（decrement）、乘法（multiply）以及相等測驗（tests for equality），還有一個兩位開關（即if分支）和另一部階乘機器（這樣，階乘機器就是無窮的，因為其中包含著另一部階乘機器），下圖是這部階乘機器的流程圖，說明了有關的部分如何連接在一起，
按照類似的方式，我們也可以把求值器看做是一部非常特殊的機器，它要求以一部機器的描述作為輸入，給定了這個輸入之后，求值器就能夠規劃自己的行為（configures itself）來模擬被描述的機器，舉例來說，如果我們將factorial程序的定義送入求值器，求值器能夠計算階乘，如下圖所示：
按照這一觀點，我們的求值器可以被看做是是一種通用機器（universal machine），它能夠模擬其它的任何機器，只要它們已經被描述為Lisp程式，這是非常驚人的，比如我們為電子電路設想一種類似的求值器，這將會是一種電路，它以另一個電路（例如某個濾波器）的信號編碼方案做為輸入，在給了它這種輸入之后，這一電路求值器能具有與這一描述所對應的濾波器同樣的行為，這樣的一個通用電子線路將會難以想象的復雜，而程式的求值器卻是一個相當簡單的程式，
事實上，任一求值器都能模擬其他的求值器，這樣，有關“原則上說什么可以計算”（忽略掉有關所需時間和空間的實踐性問題）的概念就與語言或計算機無關了，它反映的是一個有關可計算性（computability） 的基本概念，這一思想第一次是由圖靈以清晰的方式闡述，他在1936年的論文《論可計算數及其在判定性問題上的應用》[2]為理論計算機科學奠定了基礎，在這篇論文里，圖靈給出了一種簡單的計算模型——現在被稱為圖靈機——并聲稱，任何“有效程序”都可以描述為這種機器的一個程式（這一論斷就是著名的邱奇—圖靈論題），圖靈而后實作了一臺通用機器，即一臺圖靈機，其行為就像是所有圖靈機程式的求值器，
求值器的另一驚人方面，在于它就像是在我們的程式設計語言所操作的資料物件和這個程式設計語言本身之間的一座橋梁，現在設想這個用Python實作的求值程式正在運行，一個用戶正在輸入運算式并觀察所得到的結果，從用戶的觀點看，他所輸入的形如(* x x)的運算式是程式設計語言里的一個運算式，是求值器將要執行的東西，而從求值器的觀點看，這一運算式不過是一個表（這里就是三個符號*、x和x的表），它所要做的也就是按照一套定義良好的規則去操作這個表，
這種用戶程式即求值器的資料的情況，未必會成為混亂之源，事實上，有時簡單地忽略這種差異，為用戶提供顯式地將資料物件當做Lisp運算式求值的能力，允許他們在程式里直接使用eval，甚至可能帶來許多方便，在我們實作的這個求值器里，就可以直接使用eval程序：
scm> (eval '(* 5 5))
25
scm> (eval (cons '* (list 5 5)))
25
事實上，Python語言中也內置了eval()函式：
>>> 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.
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/552490.html
標籤：其他
上一篇：【深入淺出 Yarn 架構與實作】6-4 Container 生命周期原始碼分析
下一篇：返回列表