Programming Languages, UW, Part C - OOP v.s. FP

Posted on 繁/简： set

在此之前，我们已经接触了三种各具特色的语言：ML，Racket 与 Ruby，这门课程选择它们作为示例语言是十分别具匠心的。ML - statically functional language, Racket - dynamically functional language, Ruby - dynamically OOP language.

在 Part B 中，我们以 ML 与 Racket 为例比较了 static typing 与 dynamic typing；在这一节中，我们将以 ML，Racket 与 Ruby 为例比较 functional programming 与 object-oriented programming。


  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.


OOP Versus Functional Decomposition

The Basic Set-Up

Followed is the canonical example of a common programming pattern. Suppose we have:

  • Expressions for a small "language" such as for arithmetic.
  • Different variants of expression, such as integer values, negation and addition expressions.
  • Different operations over expressions, such as evaluating them, converting them to strings, or determining if they contain the constant zero in them.

对这个范式我们应该已经相当熟悉了；之前我们也分别用 ML 与 Racket 实现过这个算数小语言。该问题能被一个矩阵 (two-dimensional grid) 进行表示：其中的每一个格子代表某个 variant 与 operation 的组合。例：

variant/operation eval toString hasZero
Int
Add
Negate

No matter what programming language we use or how we approach solving this programming problem, we need to indicate what the proper behavior is for each entry in the grid.

Functional v.s. OOP Approach

Functional decomposition breaks programs into functions that performs some operation and object-oriented decomposition breaks programs down into classes that give behavior to some kind of data.

也就是说，对于上文中提到的矩阵，functional programming lays out the program by column — 其定义操纵不同类型数据的函数，按列实现程序。要素有 datatype, constructor 与 function。

而 object-oriented programming lays out the program by row — 其定义不同的类，类中包含与其他类的实例交互的方法，按行实现程序。要素有 class, subclass 与 abstract method。

因此，functional decomposition 又被称为 procedural decomposition (过程分解) - it breaks the problem down into procedures corresponding to each operation。相对的，OOP decomposition 被称为 data-oriented decomposition - it breaks the problem down into classes corresponding to each data variant.

至于哪种分解方式更好完全是一个见仁见智的问题：对于不同的问题模型，有时基于过程的分解更为自然，有时基于数据的分解更为自然。但本质上，这两种分解方式是对立而又统一的 (so exactly opposite that they are the same).


Extending New Operations or Variants

当我们尝试扩展以上矩阵，即增添新的 operations 或 variants 时，functional programming 的 by-column 方法与 OOP 的 by-row 方法之间的区别将更加明显。

首先考虑 functional programming。

  • Adding a new operation is easy. We can implement a new function without editing any existing code. 由于 FP 是按列，也就是按函数实现程序的，新增一个 operation 等价于在矩阵中新增一列。
  • Adding a new data variant is less pleasent. We need to go back and change all our functions to add a new case. 新增一个 variant 等价于在矩阵中新增一行；但 FP 是按列实现程序的，因此在每一列后我们都需要新增一个单元 (case)。

Object-oriented programming 则与其完全相反。

  • Adding a new variant is easy: implement a new subclass without editing any existing code.
  • Adding a new operation is less pleasant. We need to go back and change all classes to add a new method.

Functional decomposition allows new operations and object-oriented decomposition allows new variants without modifying existing code and without explicitly planning for it.

但在设计程序时，如果做好提前的计划，或者使用某些 somewhat awkward programming techniques，那么在 FP 中添加 variants 与在 OOP 中添加 operations 也能较为简单的实现。

代码的设计与结构允许方便的进行删减或添加新功能，而不会引起大规模的重构或破坏原有的功能，这种性质称为代码的 extensibility (可扩展性)。

若我们只需要添加新的 operations，那么一个 FP-style 的程序显然要比 OOP-style 的程序可扩展性更强；反之，一个只需要添加新的 variants 的应用背景下 OOP-style 要比 FP-style 的程序可扩展性更强。

问题在于 (1) the future is often difficult to predict; we may not know what extensions are likely, and (2) both forms of extension may be likely.

实际上，软件的设计 rubostness (鲁棒性) 与 extensibility (可扩展性) 鱼与熊掌难以兼得。由于要为未来做规划，可扩展性高的程序往往 need more work to develop, harder reason about locally and harder to change without breaking extensions.


Binary Methods

Binary methods are operations that take two data variants as arguments. Similarly, we have n-ary methods that take more data variants as arguments.

在此之前，我们研究的 operations 大多都是针对同一种数据类型的：eval, toString 与 hasZero 皆属此类。若我们想对两个 (binary) 或以上 (n-ary) 种类的数据类型进行操作，则需要讨论更多的情况。

FP: Simply Adding Cases

在 functional decomposition 中，binary method 的实现比较简单，我们只需要在函数体中讨论对应的 cases 即可。当数据种类较多时，讨论的 cases 也将增加，但也存在许多简化的方法 (使用 wildcard _，定义辅助函数，利用重复的 cases 等等)。

举例来说，add_values 方法原本只能计算两个 Int 类型数之和；若我们想将其扩展为 binary method，支持对 Int 与 String 与 Rational 三种数据类型进行操作 (语义由我们自定义)，我们只需要在其函数体中增加对应的 3 * 3 = 9 种 cases 即可。

1
2
3
4
5
fun add_values(v1, v2) = 
    case (v1, v2) of
        (Int i, Int j)		=> Int (i + j)
      | (Int i, String s)	=> String (Int.toString i ^ s)
      | ... (* 3 data variants, 9 cases in total *)

OOP: Double Dispatch

对于同样的例子，OOP 需要使用一个特殊的 technique - double dispatch 来实现 binary method。

假设我们已经定义了 Int, Negate, MyString, MyRational, Add, Mult 等相关的类，为了扩展 Add 的语义，我们需要对 Add 类中的 eval 方法进行修改。原来的 eval 方法：只能处理两个 Int 类型数之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Add < Exp
    attr_reader :e1, :e2
    def initialize(e1, e2)
        @e1 = e1
        @e2 = e2
    end
    def toString
        "(" + e1.toString + e2.toString + ")"
    end
    def hasZero
        e1.hasZero || e2.hasZero
    end
    def eval                              # eval method that needs to be modified
        Int.new(e1.eval.i + e2.eval.i)    # i is a method in class Int
    end
end

一个很自然的想法是，模仿在 FP 中我们定义的 add_values 函数对来修改 eval：利用 is_a? 等类型判断方法来分类讨论不同的 cases。例如使用 is_a? Int，或 is_a? MyString 来获取 e1 与 e2 的类。

但是请注意，使用类型判断函数是非常不符合 OOP style 的。我们应该调用某个对象的方法，在无需明确的获取另一个对象所属类的情况下执行我们自定义的加法操作。也就是说，An Int, MyRational or MyString should know "how to add itself to another value." 于是我们将类 Add 中的 eval 改写成这样。

1
2
3
def eval
    e1.eval.add_values e2.eval    # one (first) dispatch
end

这样修改要求我们分别在 Int, MyString 与 MyRational 类中实现方法 add_values。通过 dynamic dispatch，我们成功将该自定义的加法运算分为了三种情况，分别交由 Int, MyString 与 MyRational 类进行进一步处理。

为什么这里利用了 dynamic dispatch？因为调用同样的方法 eval， e1.eval 返回的类不同 (Int, MyString 或 MyRational)，所调用的 add_values 方法也不同，从而实现了相同方法的不同表现 (behaviors)。

以 Int 类中的 add_values 方法的实现为例；当前已知的信息是 Self 的类为 Int，未知的是参数对象的信息；我们不如再进行一次 dynamic dispatch，即，在所有类中再定义三个接口方法，分别对应 Int, MyString 与 MyRational 类，并将 Self 的信息传入该未知对象的接口。这样未知对象就间接获取了关于 Self 的信息。

这样的 technique 称为 double dispatch，即利用两次 dynamic dispatch 以实现 binary method。这正符合 OOP 的精神：When we "need to know" the class of v, we call a method on v instead.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Int < Exp
    attr_reader :i
    ...
    def add_values v
        v.addInt self    # double (second) dispatch (based on following interfaces)
    end
    def addInt v
        Int.new(i + v.i)
    end
    def addString v
        MyString.new(v.s + i.to_s)
    end
    def addRational v
        MyRational.new(v.i+v.j*i, v.j)
    end
end

虽然形式上差异很大，Double dispatch 本质上与 FP approach 是相同的；最终我们还是实现了 3 * 3 = 9 种 cases。只不过，通过 add_values 方法的一次分配与 addInt, addString 与 addRational 接口方法的二次分配，dynamic dispatch could pick the correct code among all 9 cases in the end.

在 Java 这样的静态类型 OOP 语言中，我们需要 (1) 声明参数与返回值的类型，并且 (2) 在父类中声明子类所继承的方法与其类型，这使得 double dispatch 的实现更为直观。


Multiple Dispatch & Static Overload

It is NOT true that all OOP languages require the cumbersome double-dispatch pattern to implement binary operatoins in a full OOP style. Languages with multimethods, also known as multiple dispatch, provide more intuitive solutions.

支持 multiple dispatch 的语言允许在类中声明多个同名方法。举例来说，在允许 multiple dispatch 的语言中，在 Int, MyString, 与 MyRational 类中均可定义三个名为 add_values 的方法；也就是说程序中将会有 3 * 3 = 9 个名为 add_values 的方法，分别对应 9 个 cases。

Each add_values method would indicate the class it expects for its argument. Then e1.eval.addvalues e2.eval would pick the right one of the 9 by, at run-time, considering the class of the result of e1.eval and the class of the result of e2.eval.

Ruby, Java, C#, C++ 等语言采用的均是 dynamic single dispatch: the method-lookup rules involve the run-time class of the receiver (the object whose method we are calling, or self), not the run-time class of the argument(s).

而 dynamic multiple dispatch 不仅仅考虑 receiver 的类，它将根据多个对象 (当然包括传入的参数) 的类来选择需要被调用的方法。因此可以说 multiple dispatch is "even more dynamic dispatch".

Java 与 C++ 这样的 statically typed languages 不支持 multiple dispatch，但它们允许在类中定义同名方法，并通过我们所声明的实参类型 (types) 来选择调用的方法。这一 semantic 被称为 static overloading。

Static Overloading Multiple Dispatch
languages statically typed OOP dynamically typed OOP
argument dependence types of arguments at compile-time run-time class of the result of evaluating the arguments
receiver dependence run-time class of receiver (odd hybrid?) run-time class of receiver
double dispatch does not avoid double dispatch simplify cumbersome double dispatch

在 (dynamic) single dispatch 根据 receiver 的 run-time class 选择调用的方法这一基础上，multiple dispatch 根据参数的 run-time class 进一步选择，static overloading 根据参数的 types 进一步选择。

但 multiple dispatch 能够在某种程度上简化笨重的 double dispatch technique；static overloading 则无法做到这一点，当需要使用 double dispatch 时还是无法避免。


Beyond Single Inheritance

继承是 OOP 的灵魂之一：But so far all our examples have been classes with 1 (immediate) superclass. If inheritance is so powerful, why not allow ways to use more code defined in other places?

下面我们将介绍三个有紧密联系，但不同的 ideas；它们均能在一定程度上实现比单继承更加强大的代码复用。由强到弱分别是：multiple inheritance (多继承)，mixins (混入) 与 interfaces (接口)。

C++: Multiple Inheritance

Languages with multiple inheritance let one class extend multiple other classes.

当某个类同时具有多个父类的特征时，多继承是一个很自然的想法。举例来说，考虑类 Person 的两个子类 Cowboy 与 Artist，当我们想实现一个艺术家牛仔时，我们仅需要定义同时继承自 Cowboy 类与 Artist 类的 CowboyArtist 类即可。

Intuitively，我们将多继承定义为子类继承多个父类中的所有方法与成员变量，但我们能够很容易发现这个定义的不妥之处：若多个父类中的方法或成员变量存在重复，或者冲突，又如何处理？

一个典型的例子是同名方法问题。若 Cowboy 类中定义了方法 draw (draw a gun, 指拔枪)，且 Artist 类中也定义了方法 draw (draw a picture, 指画画)，那么 CowboyArtist 类该如何继承这两个行为完全不同的同名方法？若两个方法都继承，又应该如何进行区分？

在支持多继承的语言中，多继承带来的语义问题需要通过定义相当复杂的 rules for how subclassing, method lookup, and field access work 来解决。 举例来说，C++ 有至少两种创建子类的方式。

  • 子类继承所有来自父类的方法与成员变量。
  • 对于继承自共同祖先的成员变量，仅仅拷贝一份。

在单继承中，所有的类与继承关系形成的 hierarchy 是一颗树，而多继承形成的则是一个 DAG。在设计多继承的相关规则时，继承自共同祖先 (common ancester) 的方法与成员变量常常需要被特殊考虑，因为它们很可能会导致重复或冲突 (若在两个子类中分别被重写)。

Ruby: Mixins

Ruby has mixins, which are somewhere between multiple inheritance (above) and interfaces (below).

They provide actual code to classes that include them, but they are not classes themselves, so we cannot create instances of them.

我们使用 module 关键字来定义 mixins，在类的定义中使用 include 关键字来“继承” mixins。

1
2
3
4
5
module Doubler
    def double
        self + self # use self's + message, not defined in Doubler
    end
end

一般来说，我们尽量避免在 mixins 中定义实例变量。mixins 比较优雅的用法应是：They define methods that call other methods on self that are not defined by mixins.

如上例，mixin Doubler 可以被任意实现了 + 方法的类 include：可以是某个自定义的类 (AnotherPt)，也可以是标准库中的一些符合要求的类 (如 String)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class AnotherPt
    attr_accessor :x, :y
    include Doubler
    def + other        # add two points
        ans = AnotherPt.new
        ans.x = self.x + other.x
        ans.y = self.y + other.y
        ans
    end
end

class String
    include Doubler
end

现在类 AnotherPt 与类 String 的实例都能够直接调用 Doubler 方法了。

在引入 mixins 后，之前我们介绍的 method lookup rules 也应作出一些改变；在沿着 class hierarchy 向上寻找 method 的过程中也要考虑类中 include 的 mixin。If obj is an instance of class C and we send message m to obj:

  • First look in the class C for a definition of m.
  • Next look in mixins included in C, Later includes shadow earlier ones.
  • Recur with the superclass of C and its included mixins to see if they defines m.

Java/C#: Interfaces

在 Java 或 C# 中，一个类只能有一个直接父类，但却可以实现 (implement) 任意数量的 interfaces。

一个 interface 声明了若干方法，且规定了这些方法的参数与返回值的类型 (type)。注意，interface 中声明的方法是待实现的，其函数体部分都是空置的。

正是因为 interface 并不真正“定义”方法，而仅仅对方法命名并规定其类型，在 multiple inheritance 中出现的语义问题将得以避免。If two interfaces have a method-name conflict, a class can still implement them both. If two interfaces disagree on a method's type, no class can implement them both since type-checker will catch that.

A class type-checks only if it actually provides (directly or via inheritance) all the methods of all the interfaces it claims to implement.

关于 interface 还有一个很重要的概念：An interface is a type。所以如果类 C 实现了 interface I，我们就能将类 C 的实例传入某个形参类型为 I 的方法，这也是另一种意义上的 duck typing。

与 multiple inheritance 和 mixins 不同，interfaces 并不继承任何代码；它的存在使得某些 statically typed languages 的 type system 更加灵活，允许了某种程度上的 duck typing。

对于不存在 type system 限制的 dynamically typed languages，we can already pass any object to any method and call any method on any object (这也是 dynamic typing 的 essence 所在)，自然 interfaces 的存在就失去了意义。

笔记联动：Algorithm, Princeton - Java Language，这里介绍了 Iterator, Comparator 等等 Java 中常用的 interfaces。


Abstract Methods

The entire point of the abstract class is to be subclassed and have different subclasses define the missing methods, relying on dynamic dispatch for the code in the superclass to call the code in the subclass. (abstract method)

抽象类是纯粹用于继承的类。我们常常能见到其定义了一些方法，这些方法中又调用了类中未定义的方法。如果我们尝试实例化抽象类并调用相应的方法，method missing 错误将会发生。

1
2
3
4
5
class Doubler
    def double
        self + self		# the method '+' is abstract
    end
end

仔细想想，抽象类起到的作用实际上与 mixins 是一致的。它们定义的方法常常会调用其他未定义的方法，而这些 “missing methods” 留待其子类 (或 include 该 mixin 的类) 进行实现。我们把这些在子类中实现的方法称为 abstract methods。

如上例，Doubler 类是一个 abstract class，而 + 方法是 abstract method。注意，double 方法是有“意义”的方法；在被子类继承后，若子类提供了 abstract method (即 + 方法) 的实现，那么通过 dynamic dispatch，double 方法的代码将能够调用子类实现的 abstract method。

在 statically typed languages 中，这一问题更加有趣。由于 type checker 将会在 compile-time 探测并阻止 method missing 错误的产生，我们需要以某种方式提前声明相应的方法为 abstract method，使其能够通过 type checker 的检测。

在 C++ 中，声明 abstract method 的方式是在抽象类中定义缺少实现的空函数，并添加 virtual 关键字；因此 abstract method 又被称为 pure virtual method (纯虚函数)。引入抽象类与抽象方法的概念后，静态类型语言能够更好的支持抽象类与其相关的 features。

  • Thanks to subtyping in these languages, we can have expressions with the type of the superclass and know that at run-time the object will actually be one of the subclasses.
  • Type-checking ensures the object' class has implemented all the abstract methods, so it is safe to call such methods.

OOP 中的 abstract methods 与 FP 中的 higher-order functions 之间存在微妙的联系：They both support a programming pattern where some code is passed other code in a flexible and reusable way.

  • 在 OOP 中，不同的子类以不同的方式实现抽象方法；父类中的代码可以通过 dynamic dispatch 调用子类中的不同实现。即子类中的抽象方法实现传入父类的代码中。
  • 在 FP 中，higher-order functions 能够以函数作为参数，不同的 callers 能够提供不同的函数实现。即 callers 的实参函数实现传入 higher-order function 的函数体代码中。

另外，支持 abstract method 与 multiple inheritance 的语言 (例如 C++) 并不需要 interface。一个只定义 abstract method (i.e., pure virtual method) 的抽象类起到的作用与 interface 一致。


Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Supplementry notes:

My notes in CnBlogs.

Course info:

Programming Languages, Part C, University of Washington, Lecturer: Professor Dan Grossman.

-----------------------------------そして、次の曲が始まるのです。-----------------------------------