How to solve an Expression Problem in Java

What is Expression Problem?

http://maoe.hatenadiary.jp/entry/20101214/1292337923

How can I add new data types and new functions in a statically typed language without recompiling?

Is the problem. If you design a class without thinking,

1. Easy to add data structures but difficult to add operations
2. Easy to add operations but difficult to add data structures It is easy to become either. The problem awareness of the Expression Problem is how to add data structures and operations.

Java solution

The solution method using advanced language functions such as Haskell, OCaml, and Scala is already famous (?), But it shows that the Expression Problem can be solved by the Java language function as well.

1. How to use subtyping + return value covariance
2. How to use subtyping + Generics

There are the above two methods. This article introduces two methods.

example

First, consider a simple interpreter as an example. Note that Lombok is used for code simplification.

import lombok.AllArgsConstructor;
import lombok.Data;

interface Exp {
    int eval();
}

@Data
@AllArgsConstructor
class Add<E extends Exp> implements Exp {
    private E e1;
    private E e2;

    @Override
    public int eval() {
        return e1.eval() + e2.eval();
    }
}

@Data
@AllArgsConstructor
class Lit implements Exp {
    private int x;

    @Override
    public int eval() {
        return x;
    }
}

The miso is where the field of the Add class is a type parameter called E.

Add operation

Add a print operation to this class.

interface ExpP extends Exp {
    String print();
}

class LitP extends Lit implements ExpP {

    LitP(int x) {
        super(x);
    }

    @Override
    public String print() {
        return String.valueOf(getX());
    }
}

class AddP<E extends ExpP> extends Add<E> implements ExpP {

    AddP(E e1, E e2) {
        super(e1, e2);
    }

    @Override
    public String print() {
        return getE1().print() + " + " + getE2().print();
    }
}

I was able to add the existing class without any problems.

Add class

Add a class that represents Sub (subtraction).

@Data
@AllArgsConstructor
class Sub<E extends Exp> implements Exp {
    private E e1;
    private E e2;

    @Override
    public int eval() {
        return e1.eval() - e2.eval();
    }
}

class SubP<E extends ExpP> extends Sub<E> implements ExpP {

    SubP(E e1, E e2) {
        super(e1, e2);
    }

    @Override
    public String print() {
        return getE1().print() + " - " + getE2().print();
    }
}

In either case, operations can be added / classes can be added without modifying the existing class. The class that uses these is as follows.

public class Main {

    public static void main(String[] args) {
        new Add<Exp>(new Lit(1), new Lit(3)).eval();
        new Sub<Exp>(new Lit(1), new Lit(3)).eval();

        new AddP<ExpP>(new LitP(1), new LitP(3)).print();
        new SubP<ExpP>(new LitP(1), new LitP(3)).print();
    }
}

In situations where high extensibility is required (expected to extend both data structures and operations), I think it's worth remembering this design pattern (unknown name?). If you are also interested in the method of "using subtyping + covariance of return value", please refer to the following references. (* The content of this article is the plagiarism of the following paper)

References

Wang, Yanlin, and Bruno C. D. S. Oliveira. "The expression problem, trivially!." Proceedings of the 15th International Conference on Modularity. ACM, 2016.