日拱一卒，伯克利CS61A，教你用Python寫一個Python直譯器

語言: CN / TW / HK
時間 2022-06-02 01:15:20

大家好，日拱一卒，我是樑唐。本文始發於公眾號Coder樑

我們繼續伯克利CS61A公開課之旅，這一次我們做的是這門課的實驗10。

這節實驗課很有意思，它是Scheme project的基礎實驗課。在這節課上我們將會用Python寫一個簡單的Python直譯器，支援一些簡單的變數定義、函式呼叫和lambda表示式。

整個實驗的難度不高，但質量很不錯，很有意思。算是為我們理解程式的編譯過程打下一個簡單的基礎，之前做Scheme直譯器專案吃力的同學可以先做一下這個，再回過頭做Scheme，會更容易上手很多。原本的課程安排也是這個順序。

課程連結

實驗原始文件

我的Github

首先，我們需要先去實驗課的網站下載實驗檔案：

這一次的實驗有一點點特殊，可能是因為間隔有一些久了，18年的實驗內容當中提供的ok有一些問題，執行的時候會報錯。所以我去找了19年的資料作為代替，19年中的ok可以順利執行。

19年的這節實驗課和18年大部分一樣，只不過多了幾道Scheme語言的練習題。我看了一下，這幾道題很多我們之前都做過類似的，所以本文還是基於18年的實驗內容撰寫的，19年課件中新增的題目大家感興趣可以自己做做看。

Topics

Interpreters

直譯器

直譯器是一個程式，它允許你通過一個固定的程式語言和計算機進行互動。它能理解你輸入的表示式，執行對應的行為得到結果。

在Project 4當中，你將會使用Python編寫一個Scheme的直譯器。我們這節課用的Python直譯器中的絕大部分都是用C語言編寫的。計算機本身使用硬體來解釋機器碼（一系列0和1代表基礎的執行執行比如相加、從記憶體讀取資訊等）

當我們談論直譯器的時候，有兩種語言在起作用：

  1. 被解釋/被實現的語言，在這個實驗當中，你將會使用PyCombinator語言
  2. 底層實現的語言，在這個實驗當中，你將會使用Python來實現PyCombinator語言

注意，底層語言需要和被實現的語言不同。實際上，這節課我們將會使用Python實現一個小版本的Python（PyCombinator）。這種idea被稱為元迴圈評估。

真實世界當中，需要直譯器使用了Read-Eval-Print Loop（REPL）。這個迴圈會等待使用者的輸入，然後分三步執行：

  • Read：直譯器獲取使用者的輸入（一個string），並且將它傳遞給lexer 和 parser

    • lexer將使用者的輸入的字串轉化成atomic片段（tokens），就像已實現語言的“words”

  • parser接收tokens並且將它們重新整理成底層執行的語言能夠識別的資料結構

  • Eval：在eval和apply中交替遞迴evaluate表示式來獲得一個只

    • Eval讀入一個表示式並根據語言的規則evaluate結果。Evaluate一個call表示式會需要呼叫apply來將一個已經evaluate得到的操作應用在它的運算元上

  • Apply接收一個操作（函式），將它應用在call表示式的引數上。Apply也可以呼叫eval來做更多的事情，所以eval和apply相互遞迴得到結果

  • Print：展示使用者輸入evaluate之後的結果

下圖展示這些模組之間是如何協作的：

PyCombinator Interpreter

今天我們來建立PyCombinator，我們自己的Python基礎直譯器。在這次實驗的末尾，你將會能夠使用一系列primite比如add,mul和 sub（你可以在下方expr.py中看到完整的清單）。更令人興奮的是，我們還能夠在你實現的直譯器當中建立和呼叫lambda函式。

你將會實現一些關鍵部分，讓我們能夠evaluate下方的表示式：

你可以閱讀repl.py中 Read-Eval-Print 迴圈的程式碼，下面是REPL元件的一個概述：

  • Read：reader.py中read函式呼叫了接下來的兩個函式來對使用者的輸入做語法分析（parse）。

  • reader.py中tokenize函式用來做lexer（詞法分析），將使用者輸入的字串拆分成token

  • reader.py中read_expr函式對tokens做parse，轉換成expr.py中Expr子類的例項

  • Eval：表示式（表示為Expr物件）被evaluate成合適的值（表示為Value物件，也在expr.py檔案中）

  • Eval：每一個表示式型別都用它專屬的eval方法，用來做evaluate

  • Apply：call表示式evaluate時會呼叫操作符（operator）的apply方法，並將它應用在傳入的引數上。對於lambda表示式來說，apply會呼叫eval來先evaluate函式的主體

  • Print：呼叫value的__str__方法，將得到的內容打印出來

在這次實驗當中，你只需要實現expr.py中Eval和Apply步驟。

你可以通過以下命令啟動PyCombinator直譯器：

bash python3 repl.py

試著輸入數字或者lambda 表示式（比如lambda x, y: x + y）來觀察evaluate之後的結果。

現在任何名稱（比如add）以及call表示式比如（add(2, 3)）都會輸出None。你需要實現Name.eval以及CallExpr.eval來讓我們能在直譯器中夠觀察names和call表示式。

如果你想要更好地理解我們的輸入是如何被讀入以及轉化成Python程式碼的，你可以在執行直譯器的時候使用--read flag：

使用Ctrl-C或Ctrl-D退出直譯器。

Required Questions

Q1: Prologue

序言

在我們編寫程式碼之前，讓我們來理解直譯器當中已經寫好的部分。

下面是我們實現的簡介：

  • repl.py包含了REPL迴圈邏輯，它會重複從使用者輸入當中讀取表示式，evaluate它們，將它們的結果打印出來（你不需要完全理解這個檔案中的程式碼）
  • reader.py包含了我們直譯器的reader部分。函式read呼叫函式tokenize和read_expr來講表示式字串轉化成Expr物件（你不需要完全理解這些程式碼）
  • expr.py包含了我們直譯器對錶達式和值的表示。Expr和Value的子類囊括了PyCombinator語言當中所有表示式和值的型別。global環境是一個包含了所有pritimite函式繫結的字典。同樣可以在檔案的底部找到程式碼

使用ok命令來測試你對reader的理解，你可以一邊參考reader.py一邊回答問題。

bash python3 ok -q prologue_reader -u

使用ok命令來測試你對Expr和Value的理解，你可以一邊參考expr.py一邊回答問題。

bash python3 ok -q prologue_expr -u

Q2: Evaluating Names

我們想要在PyCombinator中實現的第一個表示式型別是name。在我們的程式當中，name是一個Name類的例項。每一個例項擁有一個string屬性，它代表變數的名稱。比如x。

之前我們說過，變數名對應的值依賴於當前環境。在我們的實現當中，環境被表示成一個字典，它儲存name（string）和它們值（Value類的例項）的對映。

Name.eval方法將當前環境作為引數env，返回環境中繫結在Name上的值。依次實現以下邏輯：

  • 如果name存在在環境中，找到它的值並返回
  • 如果name不存在，丟擲NameError異常，並提供合適的資訊：

python raise NameError('your error message here (a string)')

python def eval(self, env): """ >>> env = { ... 'a': Number(1), ... 'b': LambdaFunction([], Literal(0), {}) ... } >>> Name('a').eval(env) Number(1) >>> Name('b').eval(env) LambdaFunction([], Literal(0), {}) >>> try: ... print(Name('c').eval(env)) ... except NameError: ... print('Exception raised!') Exception raised! """ "*** YOUR CODE HERE ***"

使用ok命令進行測試：

bash python3 ok -q Name.eval

現在你實現了name的evaluate邏輯，你可以像是檢視一些primitive函式一樣檢視變量了。你也可以試著檢視一些沒有定義的變數，看看NameError是如何展示的。

但很遺憾，這些函式現在還只能看，不能用，接下來我們會實現它們。

答案

```python def eval(self, env): if self.string in env: return env[self.string]

raise NameError("The name: {} is not defined".format(self.string))

```

Q3: Evaluating Call Expressions

現在，讓我們為call表示式新增evaluate邏輯，比如add(2, 3)。記住，call表示式擁有一個操作符和0或多個運算元。

在我們的實現當中，一個call表示式被表示成了CallExpr例項。每一個CallExpr例項都用operator和operands屬性。operator是Expr的例項，因為每個call表示式可以擁有多個運算元，所以operands是一個Expr例項的list。

比如在add(3, 4)對應的CallExpr中：

  • self.operator是Name('add')
  • self.operands是[Literal(3), Literal(4)]

在CallExpr.eval中，通過三個步驟實現對call表示式的evaluate：

  1. 在當前環境中evaluate operator
  2. 在當前環境中evaluate operands
  3. 將operator得到的結果（是一個函式）應用在operands evaluate之後的結果上

提示：operator和operands都是Expr的例項，你可以呼叫它們的eval方法來evaluate它們。並且你可以通過呼叫函式的apply方法來應用一個函式（PrimitiveFunction或LambdaFunction的例項），它們接收一個引數的list（Value例項）

python def eval(self, env): """ >>> from reader import read >>> new_env = global_env.copy() >>> new_env.update({'a': Number(1), 'b': Number(2)}) >>> add = CallExpr(Name('add'), [Literal(3), Name('a')]) >>> add.eval(new_env) Number(4) >>> new_env['a'] = Number(5) >>> add.eval(new_env) Number(8) >>> read('max(b, a, 4, -1)').eval(new_env) Number(5) >>> read('add(mul(3, 4), b)').eval(new_env) Number(14) """ "*** YOUR CODE HERE ***"

使用ok命令來進行測試：

bash python3 ok -q CallExpr.eval

現在，你已經實現了evaluate call表示式的方法，我們可以使用我們的直譯器來計算一些簡單的表示式了，比如sub(3, 4)或者add(mul(4, 5), 4)。開啟你的直譯器來做一些cool的運算。

答案

python def eval(self, env): operator = self.operator.eval(env) operands = [op.eval(env) for op in self.operands] return operator.apply(operands)

Optional Questions

Q4: Applying Lambda Functions

我們可以做一些基礎的數學運算了，但如果我們可以實現一些我們自定義的函式這會更加有趣。

一個lambda函式被表示成LambdaFunction類的例項。如果你看一下LambdaFunction.__init__，你將會看到每一個lambda函式擁有三個例項屬性：parameters, body和parent。比如我們看一個例子lambda f, x: f(x)。對於對應的LambdaFunction例項，我們將會擁有以下屬性：

  • parameters——一個string的list，比如['f', 'x']
  • body——一個Expr，比如CallExpr(Name('f'), [Name('x')])
  • parent——一個我們用來查詢變數的parent環境，注意，這是lambda函式被定義時候的環境。LambdaFunction被建立在LambdaExpr.eval方法中，所以建立時的環境就是LambdaFunction的parent環境

如果你嘗試輸入lambda表示式，你將會看到它返回一個lambda函式。然而如果你想要呼叫一個lambda函式，比如(lambda x: x)(3)它會輸出None。

你將要實現LambdaFunction.apply方法，這樣我們就可以呼叫我們的lambda函數了。這個方法接收一個arguments list，包含傳遞給函式的引數值。在evaluate lambda函式時，你需要確保lambda函式的formal parameter（形式引數）和實際入參能夠對應。為了做到這一點，你需要修改你evaluate 函式body的環境。

應用LambdaFunction有三個步驟：

  1. 製作parent環境的拷貝，對於字典d，你可以通過d.copy()獲取拷貝
  2. 在拷貝當中更新上LambdaFunction的引數以及傳入方法的引數
  3. 使用新建立的環境evaluate body

python def apply(self, arguments): """ >>> from reader import read >>> add_lambda = read('lambda x, y: add(x, y)').eval(global_env) >>> add_lambda.apply([Number(1), Number(2)]) Number(3) >>> add_lambda.apply([Number(3), Number(4)]) Number(7) >>> sub_lambda = read('lambda add: sub(10, add)').eval(global_env) >>> sub_lambda.apply([Number(8)]) Number(2) >>> add_lambda.apply([Number(8), Number(10)]) # Make sure you made a copy of env Number(18) >>> read('(lambda x: lambda y: add(x, y))(3)(4)').eval(global_env) Number(7) >>> read('(lambda x: x(x))(lambda y: 4)').eval(global_env) Number(4) """ if len(self.parameters) != len(arguments): raise TypeError("Cannot match parameters {} to arguments {}".format( comma_separated(self.parameters), comma_separated(arguments))) "*** YOUR CODE HERE ***"

使用ok進行測試：

bash python3 ok -q LambdaFunction.apply

當你完成之後，你可以嘗試這個新特徵。開啟你的直譯器，嘗試著建立和呼叫你自己的lambda函式。因為函式我們直譯器當中的value，所以我們可以嘗試玩一下高階函式：

```python $ python3 repl.py

(lambda x: add(x, 3))(1) 4 (lambda f, x: f(f(x)))(lambda y: mul(y, 2), 3) 12 ```

答案

題目的描述很長，但其實只要理解了其中的原理，實現本身並不複雜。

其中關於函式形式引數和實際引數之間數量判斷的部分老師已經替我們做好了，我們只需要將它們一一對應上，然後更新在環境的拷貝中，再呼叫body.eval得到結果即可。

```python def apply(self, arguments): if len(self.parameters) != len(arguments): raise TypeError("Cannot match parameters {} to arguments {}".format( comma_separated(self.parameters), comma_separated(arguments))) " YOUR CODE HERE " env = self.parent.copy() for k, v in zip(self.parameters, arguments): env[k] = v

    return self.body.eval(env)

```

Q5: Handling Exceptions

直譯器看起來非常酷，看起來能用了對嗎？但實際上還有一種情況我們沒有處理。你能想到一個簡單的沒有定義的計算嗎？（比如說和除法相關）嘗試著看看會發生什麼，這很坑爹不是嗎？我們得到了一大串報錯，並且退出瞭解釋器。所以我們希望能夠優雅地handle這種情況。

試著再次開啟直譯器，看看進行一些錯誤定義會發生什麼，比如add(3, x)。我們得到了一個簡短的報錯，告訴我們x沒有被定義，但我們仍然可以繼續使用直譯器。這是因為我們的程式碼handle了NameError異常，防止它讓我們的程式崩潰。讓我們看看怎樣handle異常：

在課上，你已經學過了如何丟擲異常。但捕獲異常同樣重要。我們需要使用try/except語句塊來捕獲異常，而不是讓它直接拋給使用者並且導致程式崩潰。

python try: <try suite> except <ExceptionType 0> as e: <except suite 0> except <ExceptionType 1> as e: <except suite 1> ...

我們在可能會丟擲異常的語句<try suite>外面加上這個程式碼塊。如果有異常被丟擲，程式將會檢視<except suite>找到丟擲異常對應的型別。你可以擁有許多except語句。

python try: 1 + 'hello' except NameError as e: print('hi') # NameError except suite except TypeError as e: print('bye') # TypeError except suite

在上面的例子中，將1和hello做加法會丟擲TypeError。Python將會尋找能夠handleTypeError的程式碼塊，並找到了第二個except語句。通常，我們想要執行我們想要handle的異常的型別，比如OverflowError或者ZeroDivisionError（或兩者都要），而不是handle所有的異常。

注意，我們可以使用as e定義異常，這會將異常物件賦值給變數名e。這在我們想要使用異常相關資訊的時候會很有用。

```python

try: ... x = int("cs61a rocks!") ... except ValueError as e: ... print('Oops! That was no valid number.') ... print('Error message:', e) ```

你可以看看repl.py中我們handle異常的部分，這也是我們處理計算中錯誤define異常的好地方。試試看吧！

「」
「」