崔鹏飞的Octopress Blog

模板方法模式:子类型多态和高阶函数

| Comments

模板方法模式定义了一个算法的步骤,并允许次类别为一个或多个步骤提供其实践方式。让次类别在不改变算法架构的情况下,重新定义算法中的某些步骤。

以上是wiki对模板方法的定义。

比较容易理解,我们有一个算法,其中某些步骤是确定的不太会变的代码。而另外一些步骤则需要变化并且自由组合。

《Head First Design Patterns》里有一个🌰:

假设我们需要制作咖啡因饮品,其实就是咖啡和茶。制作步骤有些类似,分为四步:1烧水,2泡,3装杯,4加调料。

其中第一步和第三步是稳定的代码,变化可能性不大,而第二步和第四步则每种饮品有自己的风味。

这样就有了下面的代码:

Java

首先有一个咖啡因饮品的抽象类,定义一个算法骨架:1烧水,2泡,3装杯,4加调料。 其中的第二步和第四步是有待实现的抽象方法,留给子类决定怎么搞。第一步和第三步是写死的。

接下来是咖啡,它实现了过滤咖啡和添加牛奶、糖的步骤。这样当它的实例的prepareRecipe方法被调用时就会执行父类的烧水、装杯,以及自己的泡和加调料。

还有,就是茶了。它和咖啡不一样,是用浸泡而不是过滤,加的是柠檬而不是牛奶和糖。

最后用一个main函数来执行制作咖啡和茶的代码。

很好,如果再有其他的咖啡因饮品,只需要增加一个子类,并且实现两个方法就好了。只要我们对于四个步骤的定义在该领域中足够稳定,这份代码就是很好很强大,易于扩展的。

有代码如此,夫复何求呢?

不过再想一下

这个模式想要达到的,不过是将一个算法的某些部分做的灵活一些,可以自由替换和组合。

那这个,不就是函数组合吗?如果我们使用的是允许高阶函数的语言的话,那还有什么必要把这些函数包装在类里呢?

functions

接下来是用Scala实现的版本:

首先,定义三个type,分别是泡和加调料这两个步骤,还有饮品本身(这三个type其实是一样的,看起来有点傻)。

然后有一个算法骨架,把第一和第三步锁死,把第二和第四步空出来,分别用一个参数来实现注入不同的实现。

接下来有泡和加调料的四种不同实现,分别是一个函数,符合各自的函数签名。

最后,用一个main函数来执行。可以看到,泡和加调料的函数是作为参数传入的。如果我们需要加牛奶和糖的茶,或者是柠檬味的咖啡的话,也会变得非常容易。

就这样,51行代码变成了28行。四个类变成了一个object。

而如果是要用子类型多态(subtype polymorphism)来做到这样的自由组合,那么我们需要的或许就是策略模式,把泡和加调料分别写成接口并提供不同的实现类来组合。可以想象,这会导致很多的boilerplate。

结语

Java代码中实现多态的方式是通过子类继承父类并且实现抽象方法来实现的。而Scala代码中则是通过把不同的函数传入骨架组合出一个新的函数来实现的。

子类型多态(subtype polymorphism)是个好东西,但是在某些场景下显得有点重。能用高阶函数这种轻量级的方式来实现的时候,就没有必要选择子类型多态这种过重的方式。

访问者模式 in FP:Pattern Matching

| Comments

访问者模式是一种将算法与对象结构分离的软件设计模式。

这个模式的基本想法如下:首先我们拥有一个由许多对象构成的对象结构,这些对象的类都拥有一个accept方法用来接受访问者对象;访问者是一个接口,它拥有一个visit方法,这个方法对访问到的对象结构中不同类型的元素作出不同的反应;在对象结构的一次访问过程中,我们遍历整个对象结构,对每一个元素都实施accept方法,在每一个元素的accept方法中回调访问者的visit方法,从而使访问者得以处理对象结构的每一个元素。我们可以针对对象结构设计不同的实在的访问者类来完成不同的操作。

以上是wiki对访问者模式的定义。

这个定义着实难读。我们来看wiki给出的例子:

假设我们要为汽车建模,汽车有不同的组成部件,轮胎,车身,和引擎。

在开车之前需要先检查车辆每个部件的状况,然后依次启动所有部件以启动汽车。

在这里我们很容易识别出车的组件各自应该是一个实体。而对车辆组件进行检查和启动的代码应该分别处于不同的实体中。

这样就有了访问者的代码(来自wiki):

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
interface ICarElement {
    void accept(ICarElementVisitor visitor);
}

class Wheel implements ICarElement {
    private String name;

    public Wheel(String name) {
        this.name = name;
    }

    public String getName() {
        return this.name;
    }

    public void accept(ICarElementVisitor visitor) {
        visitor.visit(this);
    }
}

class Engine implements ICarElement {
    public void accept(ICarElementVisitor visitor) {
        visitor.visit(this);
    }
}

class Body implements ICarElement {
    public void accept(ICarElementVisitor visitor) {
        visitor.visit(this);
    }
}

class Car implements ICarElement {
    ICarElement[] elements;

    public Car() {
        this.elements = new ICarElement[]{new Wheel("front left"),
                new Wheel("front right"), new Wheel("back left"),
                new Wheel("back right"), new Body(), new Engine()};
    }

    public void accept(ICarElementVisitor visitor) {
        for (ICarElement elem : elements) {
            elem.accept(visitor);
        }
        visitor.visit(this);
    }
}

首先是汽车部件的实体。它们都实现同一个ICarElement的接口。 该接口定义一个accept方法,用来接受访问者然后用访问者来访问所有汽车部件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
interface ICarElementVisitor {
    void visit(Wheel wheel);

    void visit(Engine engine);

    void visit(Body body);

    void visit(Car car);
}

class CarElementPrintVisitor implements ICarElementVisitor {
    public void visit(Wheel wheel) {
        System.out.println("Visiting " + wheel.getName() + " wheel");
    }

    public void visit(Engine engine) {
        System.out.println("Visiting engine");
    }

    public void visit(Body body) {
        System.out.println("Visiting body");
    }

    public void visit(Car car) {
        System.out.println("Visiting car");
    }
}

class CarElementDoVisitor implements ICarElementVisitor {
    public void visit(Wheel wheel) {
        System.out.println("Kicking my " + wheel.getName() + " wheel");
    }

    public void visit(Engine engine) {
        System.out.println("Starting my engine");
    }

    public void visit(Body body) {
        System.out.println("Moving my body");
    }

    public void visit(Car car) {
        System.out.println("Starting my car");
    }
}

然后就是访问者的实体。它们都实现ICarElementVisitor接口。 这个接口里定义的方法有点多,分别对应每个汽车部件定义了一个visit方法的重载。

在实现的时候自然是做检查的实体实现每个部件的检查,启动的实体实现每个部件的启动。

这里就有一个陷阱,如果代码发展的趋势是汽车部件的种类会增加的话,那这个接口就很不稳定。每增加一种汽车部件就要修改接口并且修改每个实现类。

而如果代码发展的趋势是在自检和启动之外加一些保养啊,洗车啊之类的话就没问题,不需要对已有代码进行修改。

所以使用访问者模式的时候要注意识别被访问者是否是相对稳定而访问者是有扩展趋势的,这样用这个模式才合适。

接下来的代码把以上所有代码串起来执行:

1
2
3
4
5
6
7
public class VisitorDemo {
    public static void main(String[] args) {
        ICarElement car = new Car();
        car.accept(new CarElementPrintVisitor());
        car.accept(new CarElementDoVisitor());
    }
}

从最后的main函数来看,只要能确保汽车部件的数量不会增加,而只有访问者增加,那么客户代码只需要增加一行就能够增加对整车进行清洗或者保养的行为。

车的部件和对部件的操作相互分离,独立发展。很灵活,很巧妙,对吧?

不过再想一下

其实也不需要使劲想了,如果你看过这一系列博文前面的几篇的话,想必已经能够猜到我的用意了。

这些访问者存在的意义就在于承载对汽车部件的某些具体操作,操作是个好听的词儿,说白了就是函数啊。

那既然这些类只是承载函数而已,何不直接就用函数而不费劲去用类包裹一层呢?

functions

那接下来就是用Scala的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
trait CarElement {
  def accept(visitor: Visitor) = visitor(this)
}

case class Body() extends CarElement

case class Engine() extends CarElement

case class Wheel(name: String) extends CarElement

case class Car() extends CarElement {
  val elements: Seq[CarElement] = Seq(
    Wheel("front left"), Wheel("front right"),
    Wheel("back left"), Wheel("back right"),
    Body(), Engine())

  override def accept(visitor: Visitor) = {
    elements.foreach(_.accept(visitor))
    visitor(this)
  }
}

以上是汽车各种部件的定义,和Java代码没有太大区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
object Visitors {
  type Visitor = CarElement => Unit

  val printVisitor: Visitor = {
    case Wheel(name) => println(s"Visiting $name wheel")
    case Body() => println("Visiting Body")
    case Engine() => println("Visiting Engine")
    case Car() => println("Visiting Car")
  }

  val doVisitor: Visitor = {
    case Wheel(name) => println(s"Kicking my $name wheel")
    case Body() => println("Moving my body")
    case Engine() => println("Starting my engine")
    case Car() => println("Starting my car")
  }
}

上面这一段定义了一个叫做Visitor的type,它只是一个函数签名。任何接受一个汽车部件作为参数并且没有返回值的函数都符合它的签名,也就可以被视作Visitor。

接下来是两个符合Visitor签名的函数,都是用pattern match实现的。

pattern match这种神奇的语言特性是如何实现的呢?背后的原因并不神奇,更多详情请参考我之前的另一篇博客:http://cuipengfei.me/blog/2013/12/29/desugar-scala-8/

1
2
3
4
5
6
7
object VisitorDemo {
  def main(args: Array[String]) {
    val car = Car()
    car.accept(printVisitor)
    car.accept(doVisitor)
  }
}

最后定义一个main函数,与Java的main函数做的事情是等价的。

这样,100行变成了45行。Visitor不再作为臃肿的实体存在,而只是函数。

而且如果遵照同样的假设,认为车的部件是稳定的,而访问者是会增多的,那这段Scala代码的增长趋势是每加一个访问者就加一个函数。与Java代码的增长趋势相同。

结语

这次分析的访问者模式和之前的一些模式很类似,当我们需要的实体仅仅是作为承载某种行为的一个载具,那就可以考虑将实体消去,而换用函数这种更简单,更轻量级的抽象方式来实现我们想要的东西。

当年OO模式出现的时候,FP并不盛行,原作者提出的方案无可厚非。不过我们今天有了FP这种更趁手的工具,就可以考虑在合适的时候将其与OO结合使用来达到更好的设计的目的。

观察者模式 in FP:Mutation vs Transformation

| Comments

观察者模式

观察者模式(有时又被称为发布/订阅模式)是软件设计模式的一种。在此种模式中,一个目标对象管理所有相依于它的观察者对象,并且在它本身的状态改变时主动发出通知。这通常透过呼叫各观察者所提供的方法来实现。此种模式通常被用来实作事件处理系统。

以上是wiki对观察者模式的解释。

举一个《Head first design pattern》中的例子:

比如说有一个气象站,每当气象有变化的时候就需要显示当前天气。 需要显示历史平均气温,最高气温和最低气温。 还需要根据气压预测晴雨。

这种情况就很适合使用观察者模式,每种需要显示气象的装置作为观察者,气象数据本身作为可以被观察的对象。 每当气象变化的时候,被观察的对象就会通知观察者来根据新的数据作出新的显示。

以下是书中给出的代码:

Java

1
2
3
4
5
6
7
8
9
public interface Observer {
    void update(float temp, float humidity, float pressure);
}

public interface Subject {
    void registerObserver(Observer o);

    void notifyObservers();
}

首先定义两个接口,一个是观察者,接收新的气象数据。一个是被观察者,可以注册观察者以及通知观察者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class WeatherData implements Subject {
    private ArrayList<Observer> observers = new ArrayList<>();
    private float temperature;
    private float humidity;
    private float pressure;

    public void registerObserver(Observer o) {
        observers.add(o);
    }

    public void notifyObservers() {
        for (Observer observer : observers) {
            observer.update(temperature, humidity, pressure);
        }
    }

    public void setMeasurements(float temperature, float humidity, float pressure) {
        this.temperature = temperature;
        this.humidity = humidity;
        this.pressure = pressure;
        notifyObservers();
    }
}

接下来定义气象数据本身。代码很容易理解,把观察者保存在一个list里,每当气象数据变化的时候就通知这些观察者去做出新的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class CurrentConditionsDisplay implements Observer {

    public CurrentConditionsDisplay(Subject weatherData) {
        weatherData.registerObserver(this);
    }

    public void update(float temperature, float humidity, float pressure) {
        System.out.println("Current conditions: " + temperature
                + "F degrees and " + humidity + "% humidity");
    }
}

public class StatisticsDisplay implements Observer {
    private float maxTemp = 0.0f;
    private float minTemp = 200;
    private float tempSum = 0.0f;
    private int numReadings;

    public StatisticsDisplay(WeatherData weatherData) {
        weatherData.registerObserver(this);
    }

    public void update(float temp, float humidity, float pressure) {
        tempSum += temp;
        numReadings++;

        if (temp > maxTemp) {
            maxTemp = temp;
        }

        if (temp < minTemp) {
            minTemp = temp;
        }

        System.out.println("Avg/Max/Min temperature = " + (tempSum / numReadings)
                + "/" + maxTemp + "/" + minTemp);
    }
}

public class ForecastDisplay implements Observer {
    private float currentPressure = 29.92f;
    private float lastPressure;

    public ForecastDisplay(WeatherData weatherData) {
        weatherData.registerObserver(this);
    }

    public void update(float temp, float humidity, float pressure) {
        lastPressure = currentPressure;
        currentPressure = pressure;

        System.out.print("Forecast: ");
        if (currentPressure > lastPressure) {
            System.out.println("Improving weather on the way!");
        } else if (currentPressure == lastPressure) {
            System.out.println("More of the same");
        } else if (currentPressure < lastPressure) {
            System.out.println("Watch out for cooler, rainy weather");
        }
    }
}

然后有三个观察者,分别负责显示当前气象,气象历史分析和晴雨预测。

CurrentConditionsDisplay是最简单的,没有任何状态,它只是负责在每次气象有变化的时候把最新的气象显示出来。

StatisticsDisplay复杂一点点,它需要记录历史气温,以便于计算平均温度,最高和最低气温。这是一个会有状态变化的对象。

ForecastDisplay也有状态变化,它需要记录上次的气压,以便于根据气压变化来预测晴雨。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class WeatherStation {

    public static void main(String[] args) {
        WeatherData weatherData = new WeatherData();
        CurrentConditionsDisplay currentDisplay = new CurrentConditionsDisplay(weatherData);
        StatisticsDisplay statisticsDisplay = new StatisticsDisplay(weatherData);
        ForecastDisplay forecastDisplay = new ForecastDisplay(weatherData);

        weatherData.setMeasurements(80, 65, 30.4f);
        weatherData.setMeasurements(82, 70, 29.2f);
        weatherData.setMeasurements(78, 90, 29.2f);
    }
}

最后,有一个main函数,把以上所有代码串起来。

三个观察者都在观察同一个气象数据,每当气象有变化的时候,三个观察者都会被通知,并作出相应处理。

如果我们需要其他的更复杂的气象显示装置,只需要实现Observer接口,注册到气象数据上去,那么在每次气象有变化的时候就可以收到通知并作出处理。不需要对已有代码做出任何改变。

很灵活,很强大,对吧?

不过再想一下

观察者模式有没有更好地实现方式呢?

答案肯定是有的。

C#的delegate和Event就是一种用来实现观察者模式的很好的语言特性。它在语言级别为添加事件订阅和取消订阅提供了支持。

不过这一篇博客主要是想要讲一个immutable的观察者模式实现,C#就不多讲了。

可以想一下,上面的Java代码里的三个观察者,CurrentConditionsDisplay是没有任何状态变化的,它存在的意义仅在于其update方法。 而这个方法每次都是接受最新的气象数据,并作出输出。

StatisticsDisplay和ForecastDisplay则是截取气象历史数据不同的片段,将其作为可变状态封装在内部,并据其状态的改变决定update方法的行为。

这样看来,如果我们有一种方式,可以提供完整的气象数据历史,那么这三个观察者就都可以各取所需,而不需要拥有自己的可变状态了。

具体该怎么做呢?

functions

以下是Scala的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
case class WeatherData(temperature: Float = 0,
                       humidity: Float = 0,
                       pressure: Float = 0,
                       observers: Seq[Observer] = Nil,
                       history: Seq[WeatherData] = Seq(WeatherData(history = Nil))) {

  def register(observer: Observer) =
    this.copy(temperature, humidity, pressure, observers :+ observer, history)

  def weatherChanged(weatherData: WeatherData) = {
    val newHistory = history :+ weatherData
    observers.foreach(observer => observer(newHistory))
    this.copy(temperature, humidity, pressure, observers, newHistory)
  }
}

object Observers {
  type Observer = Seq[WeatherData] => Unit

  val currentConditionsDisplay: Observer = history =>
    println(s"Current conditions: " +
      s"${history.last.temperature} F degrees and " +
      s"${history.last.humidity} % humidity")

  val statisticsDisplay: Observer = history =>
    println(s"Avg/Max/Min temperature = " +
      s"${history.map(_.temperature).sum / history.size}" +
      s"/${history.map(_.temperature).max}" +
      s"/${history.map(_.temperature).max}")

  val forecastDisplay: Observer = history => {
    val currentPressure = history.last.pressure
    val lastPressure = history.dropRight(1).last.pressure

    print("Forecast: ")
    if (currentPressure > lastPressure) println("Improving weather on the way!")
    else if (currentPressure == lastPressure) println("More of the same")
    else if (currentPressure < lastPressure) println("Watch out for cooler, rainy weather")
  }
}

object WeatherStation {
  def main(args: Array[String]) {
    val weatherData = WeatherData()
      .register(currentConditionsDisplay)
      .register(statisticsDisplay)
      .register(forecastDisplay)

    weatherData
      .weatherChanged(WeatherData(80, 65, 30.4f))
      .weatherChanged(WeatherData(82, 70, 29.2f))
      .weatherChanged(WeatherData(78, 90, 29.2f))
  }
}

以上就是Scala实现的全部代码了。

开始分析之前,先做一个极其复杂的数学运算: 106行的Java代码,等价于54行Scala代码。 7个类,变成了3个。

下面开始正经的分析。

首先有一个叫做WeatherData的case class,它是完全不可变的。

其register方法,接受一个新的Observer作为参数,并产生一个新的包含比原来多一个Observer的WeatherData实例。

其weatherChanged方法接受一个新的气象数据,生成一个新的历史数据Seq,并把目前为止包含所有历史气象数据的Seq传递给每一个Observer去做处理。最后返回一个包含最新历史数据的新的WeatherData实例。

那么这些Observer具体是怎么定义的呢?

首先Observer只是一个type,不是一个class,它是没有状态的,用来定义函数签名。

三个具体的display仅仅是三个符合Observer签名的函数,它们都接受气象历史数据作为参数,在历史数据中各取所需,作出处理。都是没有任何副作用的。 这很合理,毕竟只是display,仅需要对数据进行分析和显示,只读不写,没有什么要改变已有数据的必要性。

最后一个main函数把所有代码串起来,就得到了一份没有任何可变性的代码。

Mutation vs Transformation

在Java版的代码中,不同的显示设备不断地根据最新的气象数据改变自己的状态,并根据改变之后的状态来决定其update的行为。

而在Scala代码中,不同的显示设备没有状态,它们都仅仅是函数而已。它们在每次气象变化时根据全部气象历史数据决定自己的行为。

全部代码中没有重新赋值语句,所有的赋值操作都是对局部变量的赋值,程序员可以感知到的变化就只在于observers列表和history列表的增长。而即便是这两个数据结构的增长都是通过不断生成新的不可变的Seq来实现的。

总结来说,Java版代码通过改变已有数据来达成行为的改变。而Scala代码则通过利用不可变的函数和不断生成不可变的数据来实现行为的改变。

这种不可变的代码于什么优势呢?

其好处在于需要程序员操心的事情更少。变化的点越少,麻烦事越少。

如果以上的Java代码有问题,程序员除了需要检查计算平均气温,最高最低气温,气压变化的算法之外,还需要检查重新赋值语句所造成的效果。气温的sum是否算对了?测温次数是否算错了?气压变化是否记录对了?这些都是变化的点,这些都是导致错误的可能性之所在。

而在Scala代码中,如果代码有问题,同样需要检查算法的正确性,也就是检查不可变的函数的正确性。除此之外,只需要检查history列表的增长就可以了。而一个列表的增长是很难出错的。

Java中所有对象状态的改变分散在代码中不同的地方,到了Scala代码中它们都集中到了一个列表的增长上,仅仅通过对这个列表的transformation就驱动了其余全部代码的行为改变。减少了变化的点,就减少了出错的可能情况的数量,减少了程序员的负担。

解释器模式:OOP Versus Functional Decomposition

| Comments

解释器模式

In computer programming, the interpreter pattern is a design pattern that specifies how to evaluate sentences in a language. The basic idea is to have a class for each symbol (terminal or nonterminal) in a specialized computer language. The syntax tree of a sentence in the language is an instance of the composite pattern and is used to evaluate (interpret) the sentence for a client.

以上是wiki对解释器模式的描述。

这是一个学术性稍强的模式,不太好找到生活化的比喻。

就直接上代码吧。

Java

1
2
3
interface Expression {
    int interpret(Map<String, Expression> variables);
}

首先有一个表达式的接口,定义一个求值的方法,该方法接收一个String -> Expression的map。

可以猜到,这个map就是该表达式求值的时候需要用到的context。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Plus implements Expression {
    Expression leftOperand;
    Expression rightOperand;

    public Plus(Expression left, Expression right) {
        leftOperand = left;
        rightOperand = right;
    }

    public int interpret(Map<String, Expression> variables) {
        return leftOperand.interpret(variables) + rightOperand.interpret(variables);
    }
}

class Minus implements Expression {
    Expression leftOperand;
    Expression rightOperand;

    public Minus(Expression left, Expression right) {
        leftOperand = left;
        rightOperand = right;
    }

    public int interpret(Map<String, Expression> variables) {
        return leftOperand.interpret(variables) - rightOperand.interpret(variables);
    }
}

class Number implements Expression {
    private int number;

    public Number(int number) {
        this.number = number;
    }

    public int interpret(Map<String, Expression> variables) {
        return number;
    }
}

class Variable implements Expression {
    private String name;

    public Variable(String name) {
        this.name = name;
    }

    public int interpret(Map<String, Expression> variables) {
        if (null == variables.get(name)) return 0;
        return variables.get(name).interpret(variables);
    }
}

然后有表达式的四个实现类:加法表达式,减法表达式,数字表达式,还有变量。

数字表达式在求值的时候就直接返回它被创建时拿到的数字就好了,这是最简单的。

加法和减法的interpret方法在求值的时候仅仅是把行为委托给了两个子表达式,再对子表达式的求值结果做加减法。

变量在求值的时候则是去context里面寻找其name对应的表达式(也就是它所指向的表达式),然后对其求值。

下面是对它们的结合使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class InterpreterExample {
    public static void main(String[] args) {
        Map<String, Expression> context = new HashMap<>();
        context.put("w", new Number(5));
        context.put("x", new Number(10));
        context.put("z", new Number(42));

        Plus expr = new Plus(new Variable("w"),
                new Minus(new Variable("x"),
                        new Variable("z")));

        System.out.println(expr.interpret(context));
    }
}

首先构造一个context,里面有w,x,z三个数字。然后计算w+(x-z)的值(看着像不像Lisp?)。

不过再想一下

这些代码实际做的是什么事呢?

实际就是把一个以遇到Number为退出条件的递归算法拆碎了。

如果我们不把它拆碎,就写成递归函数会如何呢?

functions

用Scala试着实现一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
trait Expr

case class Plus(left: Expr, right: Expr) extends Expr

case class Minus(left: Expr, right: Expr) extends Expr

case class Number(n: Int) extends Expr

case class Var(name: String) extends Expr

object ExprEval {
  def eval(expr: Expr, context: Map[String, Expr]): Int = {
    expr match {
      case Plus(l, r) => eval(l, context) + eval(r, context)
      case Minus(l, r) => eval(l, context) - eval(r, context)
      case Var(name) => eval(context(name), context)
      case Number(n) => n
    }
  }

  def main(args: Array[String]) {
    val context = Map("w" -> Number(5), "x" -> Number(10), "z" -> Number(42))
    val expr = Plus(Var("w"), Minus(Var("x"), Var("z")))
    println(eval(expr, context))
  }
}

以上就是全部代码,与Java版等价。 递归函数很容易看懂,其退出条件也很容易看出来。

69行代码变成了26行。

四个case class代表四种表达式,其中并没有什么方法,只是用来作为数据的承载者。

一个eval函数,用pattern match来对四种表达式进行不同的处理。

不过这次我倒不是要宣扬说解释器模式属于是用不合适的工具解决问题。

而是要介绍两种组织代码的方式:按行组织还是按列组织。

按行组织代码与按列组织代码

昨天我在看解释器模式,准备写一个Java实现,再写一个Scala实现,并以此来达到我黑Java的阴暗目的。

但是看了wiki上的示例代码后,马上就想起了去年上过的一门MOOC:《Programming languages》。 (这门课是由华盛顿大学的Dan Grossman教授讲授的,内容极好,强烈推荐。)

这门课里有一节就提到了上面说的两种组织代码的方式:按行组织还是按列组织。 这节课的视频在这里:https://www.youtube.com/watch?v=uEHnI3pq_FM)

比如我们上面的两版代码,Java代码把对表达式的求值分散在每个不同的表达式类里。

而Scala代码把求值代码集中写在一个函数里,pattern match每种表达式类型并求值。

如果要做成一个表格的话,就是这样的:

table

其中的问号代表具体的求值实现。

Java代码横向组织,有一个Plus类,里面有interpret方法,有一个Minus类,里面有interpret方法,等等。这是按照行组织。

而Scala代码则纵向组织,有一个eval函数,纵向把四种表达式的求值都包揽了。这是按列组织。

上面的表格太小,看着不明显,现在假设我们需要打印表达式的功能。那么表格就会变成这样:

table2

可以想象,Java代码里会在每个表达式类里加一个toString函数的实现。横向扩展,一个类把数据和算法组织在一起。

而在Scala代码里则会写一个toString的递归函数,包揽所有字符串打印的工作。纵向扩展,一个函数去分辨数据类型,并据此选择计算策略。

OOP versus Functional Decomposition

那到底哪种组织方式更好呢?

并没有确定的答案,Dan Grossman教授在课程中给出的解释是这样的:

FP and OOP often doing the same thing in exact opposite way: organize the program “by rows” or “by columns”. Which is “most natural” may depend on what you are doing (e.g., an interpreter vs. a GUI) or personal taste.

到底如何组织取决于你想要解决什么样的问题,比如你要做一个GUI库,那么数据与算法放在一起,互相接近是最自然的组织方式。这时选择OOP是最好的设计决策。

而如果你要实现的东西类似于本文中的解释器,那么一个递归的算法来统一处理所有表达式类型则是最自然的。这时选择Functional Decomposition是最好的设计决策。

结语

OOP与Functional Decomposition,这二者并不是完全对立的。

熟练掌握多种抽象与代码组织方式,正确识别应用场景,据此选择合适的范式,或者是选择多种范式结合使用,才是这一系列博文的真实用意。

只不过由于传统的OO设计模式过于盛行,FP范式接受度不够,才会有这一系列博文黑Java,捧Scala的表象。

命令模式的不爽就像用指甲刀刮胡子

| Comments

命令模式

在面向对象程式设计的范畴中,命令模式是一种设计模式,它尝试以物件来代表实际行动。命令物件可以把行动(action) 及其参数封装起来,于是这些行动可以被:

  • 重复多次
  • 取消(如果该物件有实作的话)
  • 取消后又再重做

以上是wiki对命令模式的定义(术语像是台湾的)。

下面是来自《Head first design patterns》的一个例子:

假设你有很多家用电器:电灯泡,电视,音响,还有一个水疗浴缸。(就是没有手电筒)

每个家用电器都有自己的开关装置,处于不同的位置。如果你想把它们都开启,需要一个一个地去按按钮。

现在你想要有一个遥控器,一键开启所有电器,一键关闭所有电器。

或者是一键完成任意的电器操作组合。

每个电器的接口都是不同的,但是又需要和同一个遥控器集成,于是呢,肯定要有一个统一的接口了。

于是就有了下面命令模式的实现代码。

Java

首先是有四大件家用电器。各自之间没有什么关系。

这里面的代码都有点傻,不过没关系,我们就想象这都是些很复杂的硬件通信之类的代码就好了。

然后,定义一个Command接口,其中只有一个execute()方法。

之后我们会用它的实现类来操作各种电器。

这一大坨,就是Command的实现了。

四大件电器,于是便有八个Command,分别负责每个电器的开启和关闭。

有些电器的开启和关闭比别的要复杂一些,不过这没有关系,因为它们的细节都被封装在Command的实现类里面了,我们接下来的代码只要和Command这个接口打交道就好了。

还有一个宏命令,用来组合其他命令。

可以实现遥控器了。

http://elisabethrobson.com/wp-content/uploads/2014/07/Command.jpg

这个遥控器上的按钮都是空白的,我们可以给它置入任意我们想要的命令。

终于可以写一个main函数了:

  • 把家用电器和其对应的Command联系起来
  • 把各种Command组合成开启和关闭两个宏命令
  • 把宏命令置入遥控器

然后,只要按一个按钮,就可以开启所有电器,享受资产阶级奢靡的生活了。

享受够了之后只要再按一个按钮就可以把所有电器关闭掉。

如果再有别的电器,只需要实现几个新的Command,把新的Command组合入宏命令,继续使用遥控器就好了。

换句话说,因为遥控器和电器之间通过Command解耦了,增加新的电器和新的Command对于遥控器没有影响,遥控器的代码是稳定的。这也就是所谓的对扩展开放,对修改关闭。

很好,很符合良好的设计原则,看着就舒服对吧?

不过再想一下

电灯的开启和关闭这两个命令仅仅是对电灯的两个方法的简单代理。

音响的开启和关闭这两个命令仅仅是对音响的两个方法的简单代理。

电视机的关闭也是简单的代理。

这些命令类是否看起来太单薄了呢?它们的方法异常瘦弱,营养不良。

它们除了持有一个需要操作的电器的实例之外,基本没有什么实例级状态。

(电视开机还好,由于需要选择频道,好歹调用了两个方法。 水疗浴缸操作比较复杂,需要调节温度,所以也还稍微好一些。)

每次看到这种贫血的类,我就怀疑它们存在的必要性。

如果我们只是想要给家用电器内的方法构造一个统一个的对外接口,是不是可以用函数式来实现呢?

functions

来试试用Scala实现:

首先是有四大件家用电器,这部分和Java的代码等价。

这一段用来定义各种命令的代码就不同了。

我们对家用电器的各种方法的调用都是只期待其副作用,不期待任何返回值的。所以可以定义一个函数签名Command来涵盖所有这类操作。

和上面的Java代码类似,这里也有一个宏命令,只不过实现简单一些。

电视的开启,水疗浴缸的开和关都有对应的方法来把家用电器的实例封入闭包中。

咦?电灯的开关,音响的开关,以及电视的关闭都跑哪儿去了呢?

由于这几个操作都只涉及到一个方法的调用,它们直接就符合Command的函数签名,所以不用再封入任何闭包了。这一点看下面的代码就明白了。

我们可以定义一个遥控器。其中有开启,和关闭两排按钮。

最后,可以写一个main函数,其中所做的事情和之前Java代码main函数所做的事情是一样的。

只不过,不需要创建各种Command的实例。

而且light.on,stereo.on,light.off,stereo.off,tv.off这几个方法由于符合Command的签名,是可以直接拿来当Command用的。(注意方法名后面没有(),不是调用,而是函数传递)

前后两版代码是等价的。只不过:

  • 247行代码变成了93行代码
  • 16个实体变成了7个

作为一个多按几个按钮都嫌麻烦的好逸恶劳的资产阶级,这个结果是我所乐于见到的。

更少,更紧凑的代码。更少的实体。我终于可以用更小的成本来享受我昂贵的家用电器了。

指甲刀刮胡子

最后回到标题上去:指甲刀刮胡子,意即用不合适的工具解决问题。

命令模式想要做到的事情其实就是给各种不同的操作寻找一个统一的接口,从而实现调用者(遥控器)和被调用者(家用电器)之间的解耦。

给不同的操作寻找一个统一的接口这件事可以通过接口来做,但是我们同时要承担写一堆贫血类的代价。

而如果直接用函数来做的话,则可以得到更紧凑简洁的代码(就像object Commands这个实体内的代码一样)。

该模式提出的时候FP并不如今日盛行,其作者选用了可能会导致贫血类泛滥的解决方案,这无可厚非。传播了解耦和开闭等良好设计的原则也实为功德。

不过今天我们有了剃须刀,就无需一定要用指甲刀来刮胡子了。

职责链模式的别扭就像用门框夹核桃

| Comments

职责链模式

责任链模式在面向对象程式设计里是一种软件设计模式,它包含了一些命令对象和一系列的处理对象。每一个处理对象决定它能处理哪些命令对象,它也知道如何将它不能处理的命令对象传递给该链中的下一个处理对象。该模式还描述了往该处理链的末尾添加新的处理对象的方法。

以上是wiki对职责链模式的定义。

举个例子来说,我们的系统中需要记录日志的功能。日志需要根据优先级被发送到不同的地方。

低优先级的日志输出到命令行就好了。而高优先级的错误信息则需要通过邮件通知相关人员并且输出到命令行。

这个例子也是来自wiki的。

以下是wiki提供的Java实现:

Java

首先定义一个Logger抽象类。从其setNext和message这两个方法可以看出,我们后面会把多个具有不同writeMessage实现的Logger链到一起,并且依次让它们处理某件需要被记录的事件。

然后有三个Logger的实现,分别为向命令行输出消息,发送邮件(当然是假的),向命令行输出错误。

最后,有一个main函数,创建三个Logger的实例,把它们通过setNext链在一起。 只需要调用一次message就可以让三个Logger依次工作。

如果以后再有更多的Logger呢,还是可以通过同样的方式把它们链接起来协同工作。

很好,很强大,很易于扩展,对吧?

不过再想一下

这三个Logger的实现类看起来都非常的单薄,弱不禁风。

一个接收mask的构造函数,其唯一职责就是把接收到的mask传递给父类的构造函数。

然后父类根据mask和所发生事件优先级的大小关系决定到底要不要调用子类实现的writeMessage方法。

也就是说,子类完全没有定义自己的实例级状态,其实例级方法的行为也就谈不上随着其状态的变化而变化了。

换句话说,这几个子类存在的价值就在于为父类提供writeMessage这个函数。

啊。。。。。。!

一说到提供函数,我就想到了。。。。。。

functions

我想到的自然是FP了,既然需要的是函数,那我们就使用函数好了。

何必用更重的抽象手段:类,去包裹函数呢?

下面就是比较偏函数式的Scala实现:

这个代码已经简短到我不想解释的程度了。不过还是解释一下吧。

三个log的的等级ERR,NOTICE和DEBUG和之前Java的实现是一样的。

一个case class Event,用来包裹需要被log的事件。

type Logger则是声明了一个函数签名,凡是符合这个签名的函数都可以作为logger被使用。

然后便是三个函数实现,它们将mask通过闭包封进函数内。这三个函数共同依赖一个私有handleEvent函数,其作用和Java代码中的message类似,判断mask和正在发生的事件之间优先级大小关系,并以此决定当前logger是否需要处理该事件。

哎?等一下,这个是职责链模式啊,那个啥,链在哪儿呢?就在main函数里。其中的andThen就可以把三个logger链在一起。

这个andThen是个什么东西?何以如此神奇?

欲知详情,请参考我之前的另一篇博客: http://cuipengfei.me/blog/2013/12/30/desugar-scala-9/

而链接之后的结果本身也是一个函数,于是我们就可以调用chain并传入Event了。

这份代码和前面Java版的行为是等价的,输出是一致的。

门框夹核桃

最后回到标题上去:门框夹核桃,意即用不合适的工具解决问题。

职责链模式想要做到的事情其实就是把多个函数链起来调用。

该模式提出的时候FP并不如今日盛行,其作者选用类来包装需要被链接的多个函数,这无可厚非。

无论是class,还是function,都是为程序员提供抽象的手段。当我们想要链接的东西就是多个function,选择直接用function而非class就会显得更加自然,也更加轻量且合适。

当年design pattern的作者广为传播各种patterns,实为功德。

不过今天我们有了核桃夹,就无需一定要用门框了。

最后,依照惯例,羞辱Java一小下下。 以上wiki提供的实现有77行,偏FP风的实现只有38行,只有一个实体Event。

策略模式的尴尬就像用菜刀开啤酒

| Comments

策略模式

策略模式作为一种软件设计模式,指对象有某个行为,但是在不同的场景中,该行为有不同的实现算法。

以上是中文wiki中对策略模式的定义。

In computer programming, the strategy pattern (also known as the policy pattern) is a software design pattern that enables an algorithm’s behavior to be selected at runtime. The strategy pattern: - defines a family of algorithms, - encapsulates each algorithm, and - makes the algorithms interchangeable within that family.

Strategy lets the algorithm vary independently from clients that use it.

以上是英文版的。

鸭子

这种偏学术性的描述实在太绕嘴,来思考一个实例:

我们需要创建一些鸭子,鸭子有什么行为呢?

  • 鸭子会飞
  • 会叫
  • 会游泳

不过,是否所有的鸭子都是这样呢?万一是玩具鸭子呢?万一是猎人放在水里的用来勾引公鸭子的木质母鸭子呢?万一是外星来客太空鸭呢?

你已经知道什么意思了。

鸭子的各个子类的飞和叫的行为不尽相同。所以我们想把飞和叫这两种行为独立开来,让它们可以自由组合在鸭子的不同子类中。

以上例子来自著名的《Head first design patterns》。

Java

以下是《Head first design patterns》附带的代码:

飞行的接口,以及两个实现:一个真会飞,一个不会飞。

叫的接口,两个实现,一个真会叫,一个不会叫。

最后,终于到了鸭子。鸭子的顶层抽象类声明两个字段,一个用来飞,一个用来叫。

这样在子类里就可以把这两个字段锁定到某个特定的实现,以实现任意的组合。

可以看到,绿头鸭(mallard)组合了真会飞和真会叫。而诱饵鸭(decoy,猎人用来勾引鸭子上钩的那个)则组合了不会飞和不会叫。

可以想象随着飞和叫这两个家族的扩大,我们可以组合出更多种类的鸭子来。

很好,很灵活,很强大,对吧?

不过再想一下

我们想要的不过是把两个家族的不同行为塞到鸭子的子类里去。是否有更容易的办法来做到呢?

trait

一说到把行为塞到某个类里,就会想到mix in,很自然就想到了Scala的trait。

更多关于Scala的trait的详情请参考我的另一篇博客: http://cuipengfei.me/blog/2013/10/13/scala-trait/

飞行家族。

叫的行为的家族。

最后,鸭子的各种实现。

貌似和Java版的实现差距不大,飞和叫的interface和class变成了trait。

Duck原来是持有Fly和Quack的实例,现在则是变成了混入Fly和Quack这两个trait。

这个代码比Java短一些,紧凑一些,构造函数中的赋值变成了类型声明时的混入。

不过再想一下

我们不过是想要把某种行为塞入到某个类里面去,真的有必要用interface,class,trait来把这些行为包裹起来吗?

行为通常是以哪种形式承载的呢?

functions

行为通常是以函数承载的。

也就是说我们想要做的不过是把符合某个签名的函数塞到鸭子的子类里去而已,而却用interface,class,trait来把这些行为包裹起来了。有些臃肿不是吗?

下面是直接把函数塞入鸭子子类的做法:

Fly和Quack不再是interface或者是trait。而是type aliase。

Scala的type aliase就类似于C#的delegate,用来声明function signature。

更多关于type aliase的更多详情请参考我的另一篇博客: http://cuipengfei.me/blog/2013/12/23/desugar-scala-4/

这样,会飞不会飞,会叫不会叫就无需被class或者trait包裹着了,直接就是一个个的函数。

鸭子的子类通过构造函数接收飞和叫的两个函数作为参数,就能够组合不同的行为了。

如果说之前triat的实现方式与Java实现版相比偏重了inheritance而不是composition,这一版的实现则又回到了纯composition的路上了。

紧凑程度,实体数量都比以上两版有改进。这一点从行数上可以窥见:Java版63行,trait版29行,最后一版21行。

菜刀开啤酒

最后回到标题上去:菜刀开啤酒,意即用不合适的工具解决问题。

strategy patten要解决的问题其实就是如何把一族行为的不同实现注入到某个类里去。

这一点,最开头的wiki定义已经说的很明白了: > Strategy lets the algorithm vary independently from clients that use it.

无论是class,还是function,都是为程序员提供抽象的手段。当我们想要抽象的东西就是一段algorithm(正如wiki所说)的时候,用function来做抽象就是更加轻量且合适的选择。

该模式提出的时候FP并不如今日盛行,其作者选用纯OO的方式解决了问题,并广为传播,实为功德。

不过今天我们有了开瓶器,就无需一定要用菜刀了。

最后是一个Java 8的实现:

看起来比最开始的那一版好一些,但是我还是看它不顺眼。

为什么呢?

一定是由于我强烈的偏见而没有其他任何原因,一定是这样的。

Principles of Reactive Programming Week Two作业导学

| Comments

声明

这系列博文的目标读者仅限于报名参加了这门课并且看完了视频,看完了作业的instruction之后仍有困难的同学。

这系列博文不会公布作业的答案,那是违反Coursera的code of honor的。

我只会试着解释作业中已有的代码,以及应该如何入手。

其实,写这个系列博文对我的帮助比对读者的帮助要大。

这周的作业不太难,主要就是一个观察者模式。

Signal是怎么work的?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
scala> val a = Var(1)
a: calculator.Var[Int] = calculator.Var@7ca6f5b9

scala> val b = Var(2)
b: calculator.Var[Int] = calculator.Var@2286d26

scala> val c = Signal(a() + b())
c: calculator.Signal[Int] = calculator.Signal@5c60548d

scala> c()
res8: Int = 3

scala> a()=10

scala> c()
res10: Int = 12

scala> b()=20

scala> c()
res12: Int = 30

如果能搞懂上面的代码是如何work的,作业题中需要用到Signal的地方就不会有太大问题了。

a=1,b=2,c=a+b,所以c就是3。

a变成10之后c就变成了12(10+2)。

b再变成20之后,c就变成了30(10+29)。

这个级联的变化是如何发生的呢?

有两个关键点:

  • Signal的constructor
  • Signal的update方法

先看Signal的constructor。

1
2
3
class Signal[T](expr: => T) {
  //......
}

以上是它的签名,关键在于expr的类型签名,expr的类型不是T,而是=>T。

这就意味着expr可以是任何类型为T的表达式,可以是一个字面量,也可以是任意复杂的代码块。

比如Signal(123)是可以的,Signal(complicatedMethodCall())也可以。

最上面那块代码中的val c = Signal(a() + b())就属于后一种。

a() + b()不会被立即求值成3然后传入Signal的constructor,而是整体作为一个可以被反复求值的表达式被记录在Signal的实例中。

constructor的入口参数可以被反复求值是级联变化的基础,那是什么触发了真正的变化呢?

那就是关键点之二:update方法。

update方法的妙处在于,如果一个类A有update方法,那么:

1
2
val x = new A()
x(y)=z

在编译之后会变成这样:

1
2
val x = new A()
x.update(y,z)

详情请见我之前的一篇博客:http://cuipengfei.me/blog/2014/06/12/scala-update-method/

Signal的update方法是protected的,不可访问,所以它只可以从变,不可自变。

而Var把update方法public出来了,这样,在下面这样的代码执行时:

1
2
a()=10
//a.update(10)

a就会通知它的observers去重新求值。 这样就实现了a或者b这样的Var变化的时候,c这样的Signal跟着变化的效果。

搞懂了上面的内容就足以去做作业了。

怎么和html页面结合起来的?

执行instruction里提到的webUI/fastOptJS这个task就会把Scala作业代码编译成js。

这个task是scalajs这个dependency带进来的(在webui.sbt里)。

webui这个项目里有一个CalculatorUI.scala文件,也会被编译成js。其中的代码就把作业代码和html的UI结合起来了。

就是这样了,这周的作业不难懂也不太难做。