面向对象程序设计基础

四门语言实现的类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