Reading Notes about Expression Problem

In the past week, I read the papers you gave me. Basically, I understand the background, motivation and approaches. Here is some notes.

1. Background

Expression problem, by definition, is to define a data type by cases, where one can add new cases to the data type and new functions over the data type, without recompiling existing code, and while retaining static type safety.

In OOP language such as JAVA, we can use a example showed below to describe the problem.

Assume we want to implement a AST which supports literal and add(+) operation, one may write the code:

interface Exp {int eval(); }
class Lit implements Exp {
    int x;
    public Lit(int x){this.x = x; }
    public int eval() {return x; }
}
class Add implements Exp {
    Exp l, r;
    public Add(Exp l, Exp r) {this.l = l; this.r = r; }
    public int eval()   {return l.eval() + r.eval(); }
}

If we try to add a new variant such as times(*) operation, it's quiet easy.

class Mul implements Exp {
    Exp l, r;
    public Mul(Exp l, Exp r) {this.l = l; this.r = r; }
    public int eval()   {return l.eval() * r.eval(); }
}

However, once we are about to add a new operation like render, we have to modify existing code. Below is the example, the line 1, 6, 12 and 19 should be added to the old code.

interface Exp {int eval(); String render();}
class Lit implements Exp {
    int x;
    public Lit(int x){this.x = x; }
    public int eval() {return x; }
    public String render() {return "Int "+x; }
}
class Add implements Exp {
    Exp l, r;
    public Add(Exp l, Exp r) {this.l = l; this.r = r; }
    public int eval()   {return l.eval() + r.eval(); }
    public String render() {return "( "+l.render()+" + "+r.render()+" )"; }
}
class Mul implements Exp {
    Exp l, r;
    public Mul(Exp l, Exp r) {this.l = l; this.r = r; }
    public int eval()   {return l.eval() * r.eval(); }
    public String render() {return "( "+l.render()+" * "+r.render()+" )"; }
}

However, for most function programming languages, they face different challenge to this problem. Take Haskell as example.

data Exp = Lit Int | Add Exp Exp
eval :: Exp -> Int
eval (Lit n)   = n
eval (Add x y) = eval x + eval y

Above is the initial code. If we are going to add a operation, that's quiet simple.

render :: Exp -> String
render (Lit n)   = "Int " ++ n
render (Add x y) = "( " ++ render x ++ " + " ++ render y ++ " )"

In contrast to OOP, once we want to add a new variant, we must change the exisiting code. The final code is showed below.

data Exp = Lit Int | Add Exp Exp | Mul Exp Exp
eval :: Exp -> Int
eval (Lit n)   = n
eval (Add x y) = eval x + eval y
eval (Mul x y) = eval x * eval y
render :: Exp -> String
render (Lit n)   = "Int " ++ n
render (Add x y) = "( " ++ render x ++ " + " ++ render y ++ " )"
render (Mul x y) = "( " ++ render x ++ " * " ++ render y ++ " )"

2. Object Algebras

In 2012, a lightweight design pattern for OOP was came up. It utilizes the abstract factory. The original paper also relates it to visitor pattern, but avoid using accept method, or we might think it provides concrete internal visitor implementations.

Below is the example code I write, we can find it's simple but effective. Besides, since this approach combines the features from abstract factory and visitor pattern, we could do more than it, like multi-type, multi-class, etc.

// ==== initial AST ====
interface IntAlg<A> {
    A lit(int n);
    A add(A l, A r);
}
interface Exp {
    int eval(); // regards it as concrete internal visitor
}
class IntFactory implements IntAlg<Exp> {
    public Exp lit(int n) {
        return new Exp() {
            int eval() {return n;}
    }
    public Exp add(Exp l, Exp r) {
        return new Exp() {
            int eval() {return l.eval() + r.eval();}
        }
    }
}
// ==== initial AST ====
// ==== add variant ====
interface MulAlg<A> extends IntAlg<A> {
    A mul(A l, A r)
}
class MulFactory extends IntFactory implements MulAlg<Exp> {
    public Exp mul(Exp l, Exp r) {
        return new Exp() {
            int eval() {return l.eval() * r.eval();}
        }
    }
}
// ==== add variant ====
// === add operation ===
/**
* This code shows modularity 
*/
interface Render{
    String render();
}
class IntRenderFactory implements IntAlg<Render> {
    public Render lit(int n) {
        return new Render() {
            int render() {return "Int "+n; }
    }
    public Render add(Exp l, Exp r) {
        return new Render() {
            int render() {return "( "+l.render()+" + "+r.render()+" )"; }
        }
    }
}
/**
* Without retroactive implementation
* Here we direct define the render operation.
*/
class DirectRender implements IntAlg<String> {
    public String lit(int n) {
        return "Int "+n; 
    }
    public String add(Exp l, Exp r) {
        return "( "+l.render()+" + "+r.render()+" )";       
    }
}
// === add operation ===

3. Data types $\grave{a} la carte$

In my view, this method to EP is relatively straightforward.

---- initial AST ----
data Expr f = In ( f ( Expr f ) )
--In is a function we do not define here
data Val e = Val Int
type IntExpr = Expr Val
data Add e = Add e e
type AddExpr = Expr Add
---- initial AST ----

From the code above, one finding is that we have a mapping to combine this two different type into one "type" then we can solve this problem easily. Hence, the author mention the coproduct.

By coproduct of functor, one can unify the different types. More importantly, coproduct could be implement to more than two types.

However, it is because coproduct is key idea, one must ensure the types are disjoint, which limits the extensibility of coproduct.

4. Disjoint Intersection Types and Polymorphism

In 2012, Dunfield proposed a simply typed core calculus with intersection types and a merge operator, which may provide an alternative to replace coproduct. However, it is incoherence, in order words, when applying a functor to this type, the behavior is undefined, so you cannot foresee the result.

The paper Disjoint Intersection Types reviews some solutions to this issue and gives its idea. Firstly, it defined a type system which is disjoint. However, it cannot deal with both function and argument are disjoint intersection type. Thus authors add a type limit, i.e. bi-directional type-checking.

Compared with the last paper, the paper Disjoint Polymorphism is the extension of disjoint intersection types.

5. Thought

From my perspective, object algebras is a nice OO approach to solve EP. Coproduct is another method to EP but more related to FP. Due to the limit of coproduct, we want to replace it by another type system and extend its expressivity.

For me, the difficult for me is the background because they are not textbooks. I have some trouble understanding some notation and I am not familiar to proofs.

I believe there are still lots of things to do with the disjoint interaction types especially when it relates to subtype and inheritance. As the authors said, The naive addition of new features seems to be problematic.