let語言來自eopl 《Essentials of Programming Languages》，本段只實現(xiàn)第一個簡單的let proc的語言。

eopl的書中的代碼使用scheme編寫，可以在github中取得。https://github.com/mwand/eopl3 ?就是作者之一寫的，本文將第三章的一個例子轉(zhuǎn)為python語言來實現(xiàn)。

本文的2個py代碼在： https://github.com/wangdxh/eopl3-in-python ? let文件夾下面

python 安裝pyparsing ?: pip install pyparsing

let語言的定義如下：

let xx = 0, bb = 24 in

if zero? ( xx ) ?then -(bb,3) ?else - (xx , 5 )

使用pyparsing解析得到：

[['let', [['xx', '=', [0]], ['bb', '=', [24]]], 'in', ['if', ['zero?', ['xx']], 'then', ['-', ['bb'], [3]], 'else', ['-', ['xx'], [5]?]]]]

let語言的pyparsing語法定義如下：

identifier = Word(alphas, alphanums+'_-?') ?字符開頭，包含字符，數(shù)字，下劃線，減號，問號

number = Combine( Optional('-') + Word(nums)).setParseAction(lambda t:int(t[0])) ?數(shù)字：整數(shù)

var_exp = Group( identifier )變量表達(dá)式,

const_exp = Group( number) 整數(shù)表達(dá)式

使用pyparsing的Group將變量和整數(shù)都封裝在一個list里面，這樣變量，整數(shù)，和其他的語法一樣，解析出來的結(jié)果都是list，便于解釋時整體處理。

expression = Forward() ?表達(dá)式，先定義為Forword類型，用于遞歸的類型定義，先給出一個類型聲明，后面給出具體的定義。

LPAREN, RPAREN, COMMA = map(Suppress, '(),') ?左括號，右括號，逗號定義為Superss，這樣在引用到LPAREN等變量的時候，這些符號并不出現(xiàn)在解析結(jié)果中，但是如果是‘（’去構(gòu)建表達(dá)式的時候，還是會出現(xiàn)在結(jié)果中，Supress(‘，’) 則不會。

diff_exp = Group( '-' + LPAREN + expression + COMMA + expression + RPAREN)

減號語法 - （xx， 3），解析為： ['-', ['xx'], [3]] 這里的3是整數(shù)，并不是字符串，因為在number的定義中，設(shè)置了解析操作 setParseAction(lambda t:int(t[0])) 講解析結(jié)果轉(zhuǎn)換成了int。

這里注意express， 減法的定義里面包含了experssion，expression的定義里面會包含減法，let語法，if語法等多個語法，會造成遞歸引用，所以要用Forword

zero_exp = Group( Keyword('zero?') + LPAREN + expression + RPAREN)

判斷是否為bool類型，zero？（xx） 解析為：['zero?', ['xx']]

if_exp = Group( Keyword('if') + expression + Keyword('then') + expression + Keyword('else') + expression)

if zero? ( xx )? then -(bb,3)else - (xx , 5 ) ?if語句定義 解析為：

['if', ['zero?', ['xx']], 'then', ['-', ['bb'], [3]], 'else', ['-', ['xx'], [5]]] ?每一個expression 都解析為一個列表，除了整數(shù)外第一個字段都是表達(dá)式的名稱。

let_exp = Group(Keyword('let') + Group( delimitedList( Group( identifier + '=' + expression ))) + "in" +? expression)

let 語法，后面跟著一個變量定義的列表，‘in’關(guān)鍵字，最后的expression是執(zhí)行的body，里面可以引用let后面定義的變量。 delimitedList 表示為 a + ','+ a + ',' + a 至少有一個a，后面跟則多個以逗號間隔的a，用于多個變量聲明的列表。

proc_exp = Group(Keyword('proc') + LPAREN + identifier + RPAREN + expression)

定義函數(shù)的方式，let f = proc (x) -(x,1) in (f 30)， 以proc開頭，括號里面是定義的函數(shù)參數(shù)，目前只支持一個參數(shù)的定義，參數(shù)后面跟著一個expression，是函數(shù)體。在定義的let 和proc里面執(zhí)行體的表達(dá)式暫時都只有一個，方便解析

call_exp = Group('(' + expression + expression + ')' )

調(diào)用表達(dá)式，以（）開始和結(jié)尾，這里的解析結(jié)果中（）是存在的，并且list的第一個字段就是 '(', ?因為它沒有用Supress封裝。第一個expression是函數(shù)定義或者函數(shù)變量，第二個expression是函數(shù)執(zhí)行的參數(shù)

let f = proc (x) -(x,1) in (f 30) 解析為：

[ ?['let', [['f', '=', ['proc', 'x', ['-', ['x'], [1]]]]], 'in', ['(', ['f'], [30], ')']] ?]

接下來定義

expression << (diff_exp | zero_exp | if_exp | call_exp | proc_exp | let_exp | const_exp | var_exp) ?<< 是pyparsing的語法，表示真正地定義expression。 expression定義為前面定義的表達(dá)式中的任何一個。所以各個表達(dá)式和expression是遞歸地引用的。

現(xiàn)在一個完整的語法分析的定義就完成了，調(diào)用 expression.parseString(program)對字符串進(jìn)行解析，expression的分析結(jié)果是ParseResults，這個類可以當(dāng)作list來進(jìn)行操作，而且所以的分析結(jié)果都是放在一個大的list里面的，我們的每條expression定義的時候都用Group封裝了，所以每個expression又會獨立地在有個list內(nèi)。

解釋執(zhí)行：

let f = proc (x) -(x,1) in (f 30) 解析為：

[ ['let', [['f', '=', ['proc', 'x', ['-', ['x'], [1]]]]], 'in', ['(', ['f'], [30], ')']]? ]

def value_of_program(program):

return value_of(expression.parseString(program)[0], init_env()) parseString解析結(jié)果的第一個list字段，就是我們的expression的解析結(jié)果，這個結(jié)果也是一個list，第一個字段，就是各個表達(dá)式的第一個字段，整數(shù)的第一個字段，就解析為整數(shù)，變量的第一個字段就是變量的字符串，整數(shù)和變量所在的list也只有一個字段。

我們引入了一個環(huán)境變量的概念，用戶擴展 let語法中定義的 變量聲明，當(dāng)有l(wèi)et xx = 0， bb=1 的時候，會向環(huán)境中擴展一個xx 和 bb的定義，然后去執(zhí)行l(wèi)et中body的定義，body中如果有引用到xx或者bb，就去環(huán)境中查找它的值，或者為整數(shù)，或者為一個函數(shù)。 環(huán)境的擴展時完成閉包的一個重要的環(huán)節(jié)，這里環(huán)境是按照變量的定義動態(tài)擴展的。當(dāng)用let將函數(shù)定義為變量的時候，解釋執(zhí)行時會生成一個閉包的python函數(shù)，這個函數(shù)會和 變量綁定，擴展到環(huán)境中。

因為有些let語法中的函數(shù)的字符在python中是不支持的，比如？，-，所以我們使用一個dict去對應(yīng) let語法中的 某個要執(zhí)行的expression的名稱和 python中的某個實際函數(shù)。使用修飾符定義，在文件enviroments.py中定義：函數(shù)dict，這個symboletofun修飾符將修飾符后面帶著的字符串參數(shù)和要修飾的函數(shù)體，在funcdict中進(jìn)行dict對應(yīng)。

在pylet.py中調(diào)用valueof 執(zhí)行expression表達(dá)式的時候：根據(jù)expression的表達(dá)式的解析結(jié)果list的第一個字段，判斷如果字段類型是int，說明他是一個number常量，它的valueof值就是 int自身；字段的其他類型就是字符串了，‘let’，‘if’，‘（’，‘zero?’ , 'xx',等等，根據(jù)它的字符串去函數(shù)列表中去查找對應(yīng)的處理函數(shù)，每一個expression我們都有一個對應(yīng)的函數(shù)處理，如果找不到，說明這個字符串是一個變量定義，那么變量定義的valueof 就是去環(huán)境中查找變量名稱對應(yīng)的值，或者為int值，或者為python的函數(shù)值。查找環(huán)境中的符號對應(yīng)的值，是apply_env,擴展環(huán)境中的符號對應(yīng)值是extend_env函數(shù)。

首先來看 let的valueof

將 let的解析結(jié)果list，賦值給4個變量，name就是‘let’，然后遍歷變量聲明list，將變量對應(yīng)的表達(dá)式的值計算之后，和 變量的符號串如，‘xx’ ?增加到環(huán)境中，extend_env會在原來環(huán)境的基礎(chǔ)上創(chuàng)建一個新的環(huán)境，并不影響原來的環(huán)境值，只有在執(zhí)行本次let的body時，使用新定義的變量環(huán)境，退出本次let的環(huán)境之后，原來的環(huán)境中并不包含本次let中的變量聲明。而且環(huán)境也使用list實現(xiàn)，當(dāng)出現(xiàn)變量名稱重復(fù)之后，會使用最后插入的變量值。 let語法的執(zhí)行結(jié)果就是它的body的執(zhí)行結(jié)果，body執(zhí)行時，環(huán)境中增加了let語法中聲明的變量的信息。

減號，zero？，if的執(zhí)行都比較類似，如下，

接下來是非常重要的函數(shù)定義和調(diào)用了

函數(shù)定義如下 ：當(dāng)碰到proc時，對這條expression的解釋，會生成一個python的函數(shù)體的值，這樣對于函數(shù)調(diào)用的（），或者 變量的環(huán)境擴展都很方便。proc過程會通過proceduer的函數(shù)，將其body和env閉包地保存，返回一個只帶函數(shù)參數(shù)的新的python函數(shù)體，這個函數(shù)體里面用到時創(chuàng)建proc 時的body 和 環(huán)境的值。例如 let f = proc (x) -(x,1) in (f 30) 執(zhí)行時，proc_func 會為proc生成一個 函數(shù)體，就是procedure返回的python函數(shù)，然后let的變量聲明表達(dá)式執(zhí)行時，會將這個 python函數(shù)和 ‘f’，對應(yīng) 擴展到環(huán)境中，在in后面的 （f，30），‘f’的valueof 執(zhí)行時，會查找到當(dāng)時保留的python函數(shù)體。

函數(shù)的調(diào)用，（f，30）或者（( proc(x) -(x,1)? 30)），第一個expression的valueof 必然是一個python函數(shù)體，然后將第二個expression的值計算出來，作為參數(shù)，執(zhí)行。

測試執(zhí)行：

執(zhí)行這些字符串查看結(jié)果：

'''?let xx = 0, bb = 24 in?if zero? ( xx )?then -(bb,3)?else - (xx , 5 )?'''

let f = proc (x) -(x,1) in (f 30)

(proc(f)(f 30)? proc(x)-(x,1))

((proc (x) proc (y) -(x,y)? 5) 6)

let f = proc(x) proc (y) -(x,y) in ((f -(10,5)) 6)

最后來一個eopl代碼中的例子執(zhí)行：

zero? 的解釋執(zhí)行竟然計算反了，沒有加not，已更新。

作者：小王