Java

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

什么是 Object Algebra

我也不谈 F-Algebra, Church-encoding, initial/free algebra 的那一套理论了,我也不会。这里就扯一些具体的东西吧。
这里要讲的 Object Algebra 是一种类似于抽象工厂的东西。不同在于,抽象工厂提供的是具体的类型/接口而 Object Algebra 提供了更强大的抽象能力。通过 Object Algebra, 可以将 Expression Problem 中的定义和实现进行完全的解耦,而仅仅需要面向对象语言中常见的部分语言特性。

什么是 Expression Problem

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

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

考虑构造途径如下的 Exp

Exp := Lit : Integer -> Exp
| Add : Exp -> Exp -> Exp.

常见的 Java 实现大概长这个样子

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 中出现的值,下面是给出的一种实现

interface Value {
    Integer getInt();
    Boolean getBool();
}
class VInt implements Value {...}
class VBool implements Value {...}

这种实现方式在实现新的结构,比如 Mul:Exp->Exp->Exp 时,可以直接声明新的 class 来解决:

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 来改写之前的程序:

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 操作,可以直接添加一个 interface 和相应的实例

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 来简化代码

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 的构造器。还是刚才的那个问题,这次我们再换一种方法实现:

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

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

添加新的方法

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

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 支持的多继承来进行特性的组合

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

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

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

// 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 用来保存变量的绑定)

/// 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 中

// AllAlgebra.java
public interface AllAlgebra<T> extends
    BindingAlgebra<T>,
    IntAlgebra<T> {
}

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

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

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

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

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 中试着调用一下:

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));
    }
}

跑出了 6 , 这很好

Reference

https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf

https://blog.acolyer.org/2015/11/13/scrap-your-boilerplate-with-object-algebras/

https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-object-algebras-to-finally-tagless-interpreters-2/