使用 Object Algebra 改善解释器代码设计

使用 Object Algebra 改善解释器代码设计

前言

很久(很久)没写过文章了,这次就讲讲最近看到的 Object Algebra 相关的内容吧。

什么是 Object Algebra

Object Algebra 是一种类似于抽象工厂的设计模式。不同在于,抽象工厂提供的是具体的类型/接口而 Object Algebra 提供了泛型。通过 Object Algebra, 可以将 Expression Problem 中的定义和实现进行完全的解耦,而仅仅需要非常基础的语言 Feature。

什么是 Expression Problem

在实现语言的时候,经常会遇到这样的问题:我们需要为现有的语言添加新的类型和新的操作。在 oo (面向对象) 语言中我们很容易添加新的类型 (直接实现新的 class) 但添加新的操作会变得相当麻烦。一个常见的途径是通过 Visitor Pattern 来解决后一个问题,但与此同时会使添加新的类型变得困难 (需要改动 Visitor) 。

下面是一个非常典型的例子:

考虑构造途径如下的 Exp
Exp := Lit : Integer -> Exp | Add : Exp -> Exp -> Exp.
常见的 Java 实现大概长这个样子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
interface Exp {
Value eval();
}

class Lit implements Exp {
int x;
public Lit(int x) { this.x = x; }
public Value eval() {
return new VInt(x);
}
}

class Add implements Exp {
Exp l, r;
public Add(Exp l, Exp r) { this.l = l; this.r = r; }
public Value eval() {
return new VInt(l.eval().getInt() + r.eval().getInt());
}
}

其中 Value 用来表示 Exp 中出现的值,下面是给出的一种实现

1
2
3
4
5
6
interface Value {
Integer getInt();
Boolean getBool();
}
class VInt implements Value {...}
class VBool implements Value {...}

这种实现方式在实现新的结构,比如 $\mathrm{mul} : \mathrm{exp} \rightarrow \mathrm{exp} \rightarrow \mathrm{exp}$ 时,可以直接声明新的 class 来解决:

1
2
3
4
5
6
7
class Mul implements Exp {
Exp l, r;
public Add(Exp l, Exp r) { this.l = l; this.r = r; }
public Value eval() {
return new VInt(l.eval().getInt() * r.eval().getInt());
}
}

但是如果要为 Exp 添加新的方法则需要对实现了 Exp 的所有类进行改动。

为了解决这个问题,我们可以使用 Visitor Pattern 来改写之前的程序:

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
interface Exp {
<A> A accept(IntAlg<A> vis);
}

interface IntAlg<A> {
A lit(Integer a);
A add(A a, A b);
}

class Lit implements Exp {
Integer value;
public Lit(Integer a) {this.value = a;}
public <A> A accept(IntAlg<A> vis) {
return vis.lit(this.value);
}
}

class Add implements Exp {
Exp left, right;
public Add(Exp left, Exp right) { this.left = left; this.right = right; }
public <A> A accept(IntAlg<A> vis) {
return vis.add(left.accept(vis), right.accept(vis));
}
}

class IntEvaluator implements IntAlg<Integer> {
public Integer lit(Integer a) { return a; }
public Integer add(Integer a, Integer b) { return a + b; }
}

Exp 提供了一个接受 IntAlg<A> 的方法来访问其内部的结构,IntAlg<A> 则描述了 Exp 应该满足的性质/支持的结构。

Visitor Pattern 在为 Exp 添加新特性时会相当方便,比如我们希望它支持一个 print 操作,可以直接添加一个

1
2
3
4
5
6
7
8
9
10
11
12
interface IPrint {
String print();
}

class Printer implements IntAlg<IPrint> {
public IPrint lit(Integer a) {
return () -> a.toString();
}
public IPrint add(IPrint a, IPrint b) {
return () -> "(" + a.print() + " + " + b.print() + ")";
}
}

在使用时可以添加一个 Factory 来简化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class IntFactory implements IntAlg<Exp> {
public Exp lit(Integer a) {
return new Lit(a);
}

public Exp add(Exp a, Exp b) {
return new Add(a, b);
}
}

public class Test {
public static void main(String[] args) {
IntFactory factory = new IntFactory();
System.out.println(factory.add(factory.lit(1), factory.lit(5)).accept(new Printer()).print());
System.out.println(factory.add(factory.lit(1), factory.lit(5)).accept(new IntEvaluator()));
}
}

会分别打印出 (1 + 5)6

但是 Visitor Pattern 对于 Exp 结构的扩展却非常不便,如果要添加一个 E mul(E, E) 则需要对所有的类型实例,比如 LitAdd 等 进行修改。

如何用 Object Algebra 对结构与行为进行解耦

注意到 Visitor Pattern 中的 accept 方法会使访问的途径限制在 interface 定义时的状态 。那么该如何解决这个问题呢?

那就是利用泛型。

我们不再使用 Exp 这个 interface 和每个结构对应的类型,而提供 Generic 的构造器。还是刚才的那个问题,这次我们再换一种方法实现:

1
2
3
4
interface ExpAlg<E> {
E lit(Integer x);
E add(E e1, E e2);
}

Object Algebra 能使两个方向的扩展都变得容易:

添加新的方法

我们同时添加求值和打印两种方法

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
interface Eval {
Integer eval();
}

class EvalExpAlg implements ExpAlg<Eval> {
public Eval lit(final Integer x) {
return () -> x;
}

public Eval add(final Eval e1, final Eval e2) {
return () -> e1.eval() + e2.eval();
}
}

interface IPrint {
String print();
}

class PrintExpAlg implements ExpAlg<IPrint> {
public IPrint lit(final Integer x) {
return () -> x.toString();
}

public PPrint add(final IPrint e1, final IPrint e2) {
return () -> "(" + e1.print() + " + " + e2.print() + ")";
}
}
添加新的类型

我们可以直接在当前的 ExpAlg 上进行扩展,或者利用 Java 的 interface 支持的多继承来进行特性的组合

1
2
3
interface SubExpAlg<E> extends ExpAlg<E> {
E sub(E e1, E e2);
}

虽然刚才实现的 EvalExpAlgPrintExpAlg 是无法应用到 SubExpAlg 上的,但这时我们可以直接使用 面向对象 中的继承来直接对其进行扩展:

1
2
3
4
5
6
7
8
9
10
11
class EvalSubExpAlg extends EvalExpAlg implements SubExpAlg<Eval> {
public Eval sub(final Eval e1, final Eval e2) {
return () -> e1.eval() - e2.eval();
}
}

class PrintSubExpAlg extends PrintExpAlg implements SubExpAlg<IPrint> {
public IPrint sub(final IPrint a, final IPrint b) {
return () -> "(" + e1.print() + " - " + e2.print() + ")";
}
}

注意到整个过程中都没有冗余代码出现,Object Algebra 成功地解决了它们之间的耦合问题!

一个更为具体的例子

在 Object Algebra 的基础上,我们可以将语言的各种结构分散到不同的 Algebra 中,并在相应的功能对应的 Algebra 中分开实现,比如对于一个提供了变量定义和赋值的 Exp ,我们如下分开定义多个 Algebra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// IntAlgebra.java
public interface IntAlgebra<E> {
E intLiteral(int value);
E add(E a, E b);
E sub(E a, E b);
E mul(E a, E b);
E div(E a, E b);
}

// BindingAlgebra.java
public interface BindingAlgebra<E> {
E ident(String name);
E set(String name, E value);
E define(String name, E value);
}

定义 IEval 和相应的 Algebra 实现 (Environment 用来保存变量的绑定)

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
/// IEval.java
public interface IEval {
int eval(Environment<Integer> env);
}

// EvalBindingAlgebra.java
public interface EvalBindingAlgebra extends BindingAlgebra<IEval> {
@Override
default IEval ident(String name) {
return (env) -> env.find(name);
}

@Override
default IEval set(String name, IEval value) {
return env -> {
env.set(name, value.eval(env));
return 0;
};
}

@Override
default IEval define(String name, IEval value) {
return env -> {
env.define(name, value.eval(env));
return 0;
};
}
}

// EvalIntAlgebra.java
public interface EvalIntAlgebra extends IntAlgebra<IEval> {
@Override
default IEval intLiteral(int value) {
return (env) -> value;
}

@Override
default IEval add(IEval a, IEval b) {
return (env) -> a.eval(env) + b.eval(env);
}

@Override
default IEval sub(IEval a, IEval b) {
return (env) -> a.eval(env) - b.eval(env);
}

@Override
default IEval mul(IEval a, IEval b) {
return (env) -> a.eval(env) * b.eval(env);
}

@Override
default IEval div(IEval a, IEval b) {
return (env) -> a.eval(env) / b.eval(env);
}
}

由于 Java 的 class 不支持多继承,这里我们使用 interface + default method implementation 。

那么最后再将它们包装在一个 interface 中

1
2
3
4
5
6
7
8
9
10
11
// AllAlgebra.java
public interface AllAlgebra<T> extends
BindingAlgebra<T>,
IntAlgebra<T> {
}

// AllEvalAlgebra.java
public interface AllEvalAlgebra extends
BindingFactory,
IntFactory {
}

此时的 AllEvalAlgebra 仍然是 interface, 我们可以给出一个默认实现

1
2
3
class AllEvalAlgebraInstance implements AllFactory, AllAlgebra<IEval> {
// nothing here
}

使用 Antlr 生成一个 Parser , 我们使用它的 Visitor 模式来构造一个 Algebra : (示例代码)

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
62
63
64
class ExpAstVisitor<T> extends TestBaseVisitor<T> {
@NotNull
private final AllAlgebra<T> algebra;

TestAstVisitor(@NotNull AllAlgebra<T> algebra) {
this.algebra = algebra;
}

@Override
public T visitAssignExpr(TestParser.AssignExprContext ctx) {
return algebra.set(ctx.id.getText(), visit(ctx.assignBody));
}

@Override
public T visitNumExpr(TestParser.NumExprContext ctx) {
return visit(ctx.cmpExpr());
}

@Override
public T visitDeclStmt(TestParser.DeclStmtContext ctx) {
return algebra.define(ctx.name.getText(), algebra.intLiteral(0));
}

@Override
public T visitInfixExpr(TestParser.InfixExprContext ctx) {
final var left = visit(ctx.left);
final var right = visit(ctx.right);
switch (ctx.op.getText()) {
case "+": return algebra.add(left, right);
case "-": return algebra.sub(left, right);
case "*": return algebra.mul(left, right);
case "/": return algebra.div(left, right);
default:
throw new RuntimeException("Unrecognized op at <infixExpr> " + ctx.op.getText());
}
}

@Override
public T visitUnaryExpr(TestParser.UnaryExprContext ctx) {
if (ctx.op.getText().equals("+")) {
return visit(ctx.num());
}
return algebra.sub(algebra.intLiteral(0), visit(ctx.num()));
}

@Override
public T visitPrimitiveExpr(TestParser.PrimitiveExprContext ctx) {
return visit(ctx.primitive());
}

@Override
public T visitExprStmt(TestParser.ExprStmtContext ctx) {
return visit(ctx.expr());
}

@Override
public T visitPrimitive(TestParser.PrimitiveContext ctx) {
if (ctx.NUM() != null)
return algebra.intLiteral(Integer.parseInt(ctx.NUM().getText()));
if (ctx.ID()!= null)
return algebra.ident(ctx.ID().getText());
return visit(ctx.expr());
}
}

最后在 Main 中试着调用一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Main {

private final static String code = "var a; a = 1; a = a + 1; a = a * 3; a;";

public static void main(String[] args) {
CharStream streams = CharStreams.fromString(code);
TestLexer lexer = new TestLexer(streams);
CommonTokenStream tokens = new CommonTokenStream(lexer);
TestParser parser = new TestParser(tokens);
ParseTree tree = parser.program();
var algebra = new AllEvalAlgebraInstance();
IEval result = tree.accept(new ExpAstVisitor<>(algebra));
var env = Environment.<Integer>topEnvironment();
System.out.println(result.eval(env));
}
}