面向對象程序設計基礎

四门語言實現的類Python語言的解釋器

本次作業實現的是類Python語言的解釋器，使用swing提供圖形界面。可使用make編譯。

進入build/目錄用java MainFrame運行程序。或者使用make frame運行。

html/index.html 中有源代碼層面的文檔，類之間的繼承關係等。

class_hierachy.png 是程序中用到的所有類的關係圖。

另外還提供了其他三個語言的實現：Haskell、Ruby、C++，放在 misc/ 目錄中。

Haskell實現

Hython 是用 Haskell 實現的一個解釋器，

數據類型

  • None
  • Integer
  • Bool
  • Function

其中 Integer 是任意精度的。

流程控制語句

  • if .. elif .. else
  • while .. else

實現的其他特性

支持函數定義(def)以及單行的 lambda 表達式，函數可以嵌套，支持 closure。

設計

  • Parser/Location.hs：對待解釋程序的代碼進行標註。供詞法、語法分析、解釋階段使用，以提供錯誤信息定位的功能。
  • Parser/Lexer.x：使用 Alex 進行詞法分析。在此過程中能檢測縮進錯誤、括號不匹配情況。
  • Parser/Parser.y：使用 Happy 進行語法分析。
  • Parser/ParserMonad.hs：提供了語法分析階段狀態的表示(state monad)以及一些實用函數。應用 lens 使得記錄類型字段的提取與修改的變得十分便捷。
  • Parser/Utils.hs：語法分析階段一些輔助函數。
  • Parser/ADT.hs：將語法單元表示爲 ADT(和之前提到的不同，algebraic data type)，基本上是 Statement 與 Expr 兩類。每個 ADT 都可附帶一個額外的衛星數據，程序中只是簡單地讓語法分析階段使用了類型爲 Location 的衛星數據以提供錯誤信息定位。但整個接口是可擴展的，需要使可以輕易添加其他數據的支持。
  • Parser/Error.hs：錯誤信息。
  • Core/Prim.hs：實現了 control stack，使用 continuation 與 state monad 來表示語句/表達式執行時產生的作用。變量綁定情況分 local variables、enclosing variables、global variables 三種，從而實現 closure。
  • Core/Interpret.hs：提供 ADT 執行時的語義。
  • Main.hs：命令行選項解析，支持在詞法分析階段、語法分析階段停止，輸出相應信息。

設計模式

程序中使用到了很多設計模式，不過由於 Haskell 是 lazy functional programming language，這些設計模式的實現方式和平常見的有較大差異。

Strategy：Haskell 有 first-class 的 function，函數乃至高階函數都是 first-class object，可以自由地在函數間傳遞，相互組合，實現豐富的功能。比如 Core/Interpret.hs 中的 funOrLambdaProc，使用了 continuation passing style，指定當函數求值完後，根據上下文的不同，來決定捨棄(statement)或返回(lambda)。通過這一方法，我把 function 和 lambda共同部分提取出來，由差異部分(strategy)來提供不同語義。

Factory method, Abstract factory, Builder：同上，傳遞 first-class function 實現對象創建。Haskell 有 type class，能更好地把具有相似接口的函數組織起來。Parser/Utils.hs中的很多函數就實現了這一類設計模式的功能，由於 algebraic data type的輕量、靈活，程序就顯得非常緊湊。

Adapter, Decorator：這類是幾乎隨處可見的，因爲 function間可以自由的組合， . $ 等操作符(函數)就實現了這類功能，無需像 class-based object-oriented 語言那樣定義新類並用繼承來實現。

Interpreter：Parser/Interpret.hs 定義了一套 domain specific language，用於解釋 continue break return =等的語義，整個程序就是由這些簡單語義復合起來的。

Command：Haskell 中把副作用的部分和 pure 部分分離開，用類型 IO表示，程序中大量使用了 IO 複合（但沒有實際執行），最後由 runInterpreter一起執行。

Composite：由於 algebrai data type(和 class-based正交的方法)，程序中大量使用了組合，Token Expr Statement 包含 annot，組合 None Bool Integer 表示 object 等等。

Iterator：Haskell 是 lazy functional programming language，不會使用的部分不會求值，有 foldl map concat zip union lookup等大量用於 list 處理的函數，起到了 internal iterator 的作用。我的程序中 lexer parser 部分就有 external internal 結合的意味。

Prototype：因爲 pure，沒有副作用，我使用了 lens(本質是 store comonad)來方便從記錄類型中提取字段以及修改記錄類型，提供了從一個對象快速生成新對象的功能。

Flyweight：由於 constant applicative forms的存在，大量無參函數都會被編譯器優化成只執行一次。比如我的程序中 Parser/Lexer.hs 中的 keywords 函數，是一個關鍵字標識符到其 constructor的 map。

State Memento Singleton：沒有副作用，這些都沒有必要。purely functional programming 能實現 persistent data structure，而不需要這些設計模式。

Facade：各式各樣函數的複合，實用函數可以方便定義。這個模式也是普遍、無處不在的。

Proxy：程序中使用了 IORef，對一個變量的操作轉爲對該 IORef操作，決定讀取還是寫入。

Mediator：moand transformer。這些 monad transformer 本身就像 C++ 的 template 的參數那樣，可以任意堆砌。其中也有 call-with-current-continuation，用 purely functional 的方式實現了 return continue break 等代碼邏輯。

Java

模塊

  • Prim.java，定義了類Python語言的各個語法單元(即語法分析後所有可能產生的符號)，語義。
  • Lexer.java，詞法分析，將類Python語言源文件處理產生詞法符號，如代表整數的 INT，代表變量的 IDENT，表示縮進層數增加的 INDENT 和表示縮進層數減少的 DEDENT 等。使用棧來生成 INDENT DEDENT。
  • Parser.y，語法分析，使用了 Yacc-compatible 的 Bison 產生 Java 源文件 Parser.java，用 LALR 語法分析算法將詞法單元構建成語法單元，一個源文件對應了一棵表達式樹。
  • CLI.java，一個簡單的 CLI 程序。
  • MainFrame.java，GUI 程序。

語法單元設計

考慮到 Python中語句和表達式的區分，實現中將語法單元分爲兩大類：Stmt(statement) 與 Expr(expression)。

Stmt

Stmt 實現爲一個 interface，定義了 eval(執行該 statement)，eval需要兩個參數，Binding 即變量綁定情況，以及 Writer 用於接收 print語句輸出的字符串。

Suite

Suite 表示多行 statement，使用了 composite 的設計模式，implements 了 Stmt，其 eval 實現爲對每個子 statement 執行 eval。

If

由一個 Expr 條件和代表 then 的 Stmt 及代表 else 的 Stmt 組成。其 eval實現爲：執行條件，若爲真則執行 then 的 eval，否則執行 else 的 eval。

While

由一個 Expr 條件和代表循環體的 Stmt 組成。其 eval實現爲：執行條件，若爲真則執行循環體 的 eval。同時捕捉 ContinueException和 BreakException 以提供 flow control。

Print

有一個 Expr，執行時將該 Expr 求值爲 Obj 並輸出。

ExprStmt

代表一個表達式組成的 statement。

擴展

需要擴展時只需使用新類 implements Stmt。

Expr

代表表達式。類似 Stmt，也定義了 eval，由 Bool、Int、BinOP等繼承，這些子類都代表了一類表達式可能的組成形式，比如原子類型 bool，比如雙元操作符結合的兩個表達式(BinOP)。

IntObj

代表整數對象，實現了對另一個 IntObj進行算數運算及比較操作(IntObj.send)。

BinOP

代表雙元運算符作用產生的表達式。執行時分別 eval左右操作數，再把操作轉發給左操作數的 send 方法。

擴展

需要擴展時只需使用新類 implements Stmt。

其他

Binding 類用於表示變量的綁定情況，eval 函數接受一個 Binding 參數和一個 Writer 參數。對於 Continue，執行 eval 時會拋出 ContinueException異常，其上層的 While 用 try..catch 捕獲 ContinueException異常，捕獲到時則重新執行循環。Break 實現方式類似。

思考

本質上 continue 與 break 是 outgoing-only 的 delimited continuation，或者說是帶標籤的 goto。由於 Java語言集成了異常機制，所以用該機制實現較爲便捷。異常也能輕易擴展成處理函數 return。break 與 continue 另一種實現方式則是顯式模擬一個 control stack，寫一個 unwind 函數，接受一個謂詞，來判斷需要彈出 control stack多少元素。正如我的 Haskell 版本中所實現的那樣。

Ruby實現

由於Ruby動態類型檢查，有反射機制，可以減少Java實現中很多類。

四個實現的對比

用兩種不同paradigm的語言C++、Java、Ruby(object-oriented) Haskell(functional)實現該解釋器後，我對class-based object-oriented programming的不足有了更加深切的認識。Java和C++類似，都是相當靜態的語言。由於Java支持interface，變量默認是引用，所有類繼承自Object從而能方便地進行類型轉換，在語法分析階段能少很多boilerplate代碼。而C++則不得不用指針、引用，還要自己管理內存，非常繁瑣。

Ruby由於其是動態語言，爲了表示int bool str等對象就根本不需要定義一個基類，直接用語言內置的 Numeric String Bool等類型，相比 Java 和 C++ 少了非常多的 boilerplate。(Java、C++需要用共同的基類來表示 int bool str 對象同屬於 object的事實，支持一類共同的操作的事實)。對於 print continue的語義，只要讓其能夠 lazy evaluation 即可。而對於這類 call-by-value的語言，使用一個匿名函數(lambda)，讓 eval 表示爲 env -> object的函數即可。由於 proc(類似於函數) 在 Ruby 中是 first-class object，我就把 continue break print 等實現成 proc。

對於 object-oriented programming，我之前瞭解過 Perl Lua Javascript 的 prototype-based object-oriented programming，Smalltalk Ruby 的 dynamic type checking、message passing、reflective、open classes，OCaml 的 subclass 機制，Common Lisp Object System 的 generic function。種種實現讓我體會到 C++ object-oritendted 的缺點，也想到了 OOP先驅 Alan Kay 說過的一段話："I invented the term Object-Oriented, and I can tell you I did not have C++ in mind."。該解釋器的 ADT部分可以看作是一個 Expression problem [1]_。

Java和C++是nominative type system，用名字來判斷類型等價性。Ruby的duck typing則靈活很多，與另一種類型安全形式的 structural typing有一定相似性，比如 OCaml 的。

Haskell版實現

在GitHub上，Hython