The intrinsic tension between extending data types and operations of data types

Algorithms + Data Structures = Programs

Open–closed principle

Software entities should be open for extension, but closed for modification.

Operations are open for extension, but data types are closed for modification (aka functional programming)

pub enum PlaneShape {
    Triangle(f64, f64, f64),
}

fn perimeter(shape: PlaneShape) -> f64 {
    match shape {
        PlaneShape::Triangle(a, b, c) => a + b + c,
    }
}

// Adding operations to existing data.
fn area(shape: PlaneShape) -> f64 {
    match shape {
        PlaneShape::Triangle(a, b, c) => {
            let s = (a + b + c) / 2.0;
            (s * (s - a) * (s - b) * (s - c)).sqrt()
        },
    }
}

// Now what if I want to add a Square(x: f64) to PlaneShape.
// I will need to change algebraic sum PlaneShape to
pub enum PlaneShape {
    Triangle(f64, f64, f64),
    Square(f64),
}
// But in this way, functions perimeter and area does not work any more.
// as the pattern match is now in-exhaustive.

Data types are open for extension, but operations are closed for modification (aka object-oriented programming)

public abstract class PlaneShape {
    public abstract double perimeter();
}

public class Triangle extends PlaneShape {
    private double a, b, c;

    public Triangle(double a, double b, double c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    @Override
    public double perimeter() {
        return a + b + c;
    }
}

// Adding data to existing operations
public class Square extends PlaneShape {
    private double x;

    public Square(double x) {
        this.x = x;
    }

    @Override
    public double perimeter() {
        return 4 * x;
    }
}

// Now what if I want to add a area function to PlaneShape.
// Of cause, I need to change the parent class PlaneShape to
public abstract class PlaneShape {
    public abstract double perimeter();
    public abstract double area();
}
// Now subclasses Triangle and Square does not work anymore,
// as they do not implement method area.

Solving expression problem with rust

Make PlaneShape open to extension

trait PlaneShape {  }

struct Triangle(f64, f64, f64),

struct Square(f64);

impl PlaneShape for Triangle {}

impl PlaneShape for Square {}

fn perimeter(shape: dyn PlaneShape) -> f64 {
    unimplemented!("Now how do we pattern match a trait?");
}

Implementing a perimeter function based on a abstract type dyn PlaneShape?

fn perimeter(shape: dyn PlaneShape) -> f64 {
    unimplemented!("Now how do we pattern match a trait?")?
}

We now have a problem. How do we define perimeter based on a dynamic trait PlaneShape. If it is a concrete type called Triangle, this problem is simple. If it is a concrete type called Square, this problem is also simple. The problem is that we don’t know what this PlaneShape is exactly. We need some sort of patter match as in

match shape {
    Triangle(a, b, c) => (a+b+c),
    Square(x) => 4*x,
}

It is a whack-a-mole game. We can extend PlaneShape to support new data types now, but we lost our ability to pattern matching on PlaneShapes, which is required to implement new operations.

Not all hope has lost. In fact, you may have solved this problem yourself. You just don’t know the computer scientist in yourself.

I will detour through haskell to let you have a better self-reflection (you are indeed a computer scientist who is good at solving this kind of foundamental problems).

Type classes in haskell

A well known solution for the expression problem is haskell’s type classes (not coincidentally, the formulization of expression problem and the invention of type classes are both, to a large extent, contributed by Philip L. Wadler).

Type classes vs traits

class Areable shape where
  -- calculates the shape's area
  area :: shape -> Double

trait Areable {
    fn area(&self) -> f64;
}

Type classes > traits

-- Create a data type Triangle with one operation perimeter
data Triangle = Triangle { a :: Double, b :: Double, c :: Double }

class Perimeterable shape where
  -- calculates the perimeter of the shape
  perimeter :: shape -> Double

instance Perimeterable Triangle where
  perimeter Triangle {a,b,c} = a + b + c

-- Add an operation

class Areable shape where
  -- calculates the shape's area
  area :: shape -> Double

instance Areable Triangle where
  -- use Heron's formula to calculate area
  area Triangle {a, b, c} =
    let s = (a + b + c) / 2
    in sqrt (s * (s - a) * (s - b) * (s - c))

-- Add a data type

data Square = Square { x :: Double }

-- Implement the new operation for the new type

instance Perimeterable Square where
  perimeter Square {x} = x * 4

instance Areable Square where
  area Square {x} = x * x

Actually, this only solve part of the problem, see More thoughts on the Expression Problem in Haskell for the fault (warning, the rabbit hole is deep).

Type classes vs traits again

The crucial thing is

class Perimeterable shape where
  perimeter :: shape -> Double

instance Perimeterable Triangle where
  perimeter Triangle {a,b,c} = a + b + c

Note that to instantiate Triangle as a Perimeterable, we passed the type Triangle to the function perimeter, this means that we can acutally use the type information and pattern matching to caculate perimeter. This is how we implement fn perimeter(shape: dyn PlaneShape) -> f64 with explicit type information.

The missing piece in a rust lego

Now, let’s look into rust. Pedagogically we need

fn perimeter(shape: dyn PlaneShape) -> f64 {
    unimplemented!("Now how do we pattern match a trait?")?
}

// This still does not work as we need the concrete PlaneShape type to calculate perimeter, i.e. we need the next function
fn perimeter<X: PlaneShape>(shape: X) -> f64 { }

// But this is not a generic function. It has been monomorphizated, and is nothing more than next function.
fn perimeter<Triangle: PlaneShape>(shape: Triangle) -> f64 {
    match shape {
        Triangle(a, b, c) => (a+b+c),
    }
}

// This is of no use as what we want is to extend the definition of perimeter to other PlaneShapes.
fn perimeter(shape: Triangle) -> f64 {
    match shape {
        Triangle(a, b, c) => (a+b+c),
    }
}

Some solutions for rust

So how do we pass a concrete type to a abstract trait? There are serveral ways to do that.

trait PlaneShape {}

struct Triangle {
    a: f64,
    b: f64,
    c: f64,
}

impl PlaneShape for Triangle {}

// I will implement only the method ~perimeter~ for one type data ~Triangle~ below,
// as it should be evident on how to extend both methods and data types.

Associated type for traits

// Solution 1: Associated type
trait PerimeterableAT {
    type S: PlaneShape;
    fn perimeter(shape: Self::S) -> f64;
}

impl PerimeterableAT for Triangle {
    type S = Triangle;
    fn perimeter(shape: Self::S) -> f64 {
        shape.a + shape.b + shape.c
    }
}

Bounded generics for traits

// Solution 2: Bounded generics for traits
trait PerimeterableBG<S> where S: PlaneShape {
    fn perimeter(shape: S) -> f64;
}

impl PerimeterableBG<Triangle> for Triangle {
    fn perimeter(shape: Triangle) -> f64 {
        shape.a + shape.b + shape.c
    }
}

Generics for structs

// Solution 3: Bounded generics for structs
use std::marker::PhantomData;

struct PerimeterablePT<T> where T: PlaneShape {
    _unused: PhantomData<T>,
}

impl PerimeterablePT<Triangle> {
    fn perimeter(shape: Triangle) -> f64 {
        shape.a + shape.b + shape.c
    }
}

A simpler solution for rust

Yes, all above solutions are complicated and awkward.

And you are being deliberately led away from a simpler solution.

For a good reason.

explicitly typed self references

trait PlaneShape {  }

struct Triangle {
    a: f64,
    b: f64,
    c: f64,
}

impl PlaneShape for Triangle {}

trait Perimeterable {
    fn perimeter(&self) -> f64;
}

impl Perimeterable for Triangle {
    fn perimeter(&self) -> f64 {
        self.a + self.b + self.c
    }
}

This is what is called explicitly typed self references, without which, the following code to extract data in a specific type would be impossible.

self.a + self.b + self.c

self.a implies that you are using the concrete type Triangle which implements the abstract trait Perimeterable.

Many programming languages do not have the functionality to refer to a Self type in traits.

Another side of the coin (solving expression problem for OOP languages)

Remove methods from `PlaneShape`

The first thing is to remove all the methods from PlaneShape, otherwise we can’t extend new methods without modify the defintion of PlaneShape.

public abstract class PlaneShape { }

Define new functions on a `PlaneShape` with nothing in it (or the visitor pattern)

Chapter Visitor of the book Design Patterns: Elements of Reusable Object-Oriented Software

Intent: Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.

Making oop more fp

public abstract class PlaneShape {
    public abstract void accept(PlaneShapeVisitor visitor);
}

public class Triangle extends PlaneShape {
    private double a, b, c;

    public Triangle(double a, double b, double c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    @Override
    public void accept(PlaneShapeVisitor visitor) {
        visitor.visitTriangle(this);
    }
}

public class Square extends PlaneShape {
    private double x;

    public Square(double x) {
        this.x = x;
    }

    @Override
    public void accept(PlaneShapeVisitor visitor) {
        visitor.visitSquare(this);
    }
}

public interface PlaneShapeVisitor {
    void visitTriangle(Triangle triangle);
    void visitSquare(Square square);
}

public class PerimeterVisitor implements PlaneShapeVisitor {
    private double value;

    public double getValue() {
        return value;
    }

    @Override
    public void visitTriangle(Triangle triangle) {
        double a = triangle.a;
        double b = triangle.b;
        double c = triangle.c;
        value = a + b + c;
    }

    @Override
    public void visitSquare(Square square) {
        double x = square.x;
        value = 4 * x;
    }
}

Try fp

Now we are able to write

Triangle triangle = new Triangle(3, 4, 5);
Square square = new Square(2);

PerimeterVisitor visitor = new PerimeterVisitor();
triangle.accept(visitor);
double trianglePerimeter = visitor.getValue(); // 12.0

visitor = new PerimeterVisitor();
square.accept(visitor);
double squarePerimeter = visitor.getValue(); // 8.0

Make visitors generic

Flipping to the other side of the coin

Using visitor pattern actually does not solve the problem. It’s only turning a problem of extending operators into a problem of extending data types.

public interface PlaneShapeVisitor {
    void visitTriangle(Triangle triangle);
    void visitSquare(Square square);
}

Here we hardcoded 2 PlaneShape Triangle and Square, but we need to accept any PlaneShape. How can we visit any generic PlaneShape? i.e. how to do this?

public interface PlaneShapeVisitor<T extends PlaneShape> {
    void visit<T>(T shape);
}

Solution with Java

The above problem is reminiscent of our rust journey to expression problem. We need to some how inject a concrete type PlaneShape into visit function.

1. Wadler’s original solution in generic java

   class LangF<This extends LangF<This>> {
     interface Visitor<R> {
       public R forNum(int n);
     }
     interface Exp {
       public <R> R visit(This.Visitor<R> v);
     }
     class Num implements Exp {
       protected final int n_;
       public Num(int n) {n_=n;}
       public <R> R visit(This.Visitor<R> v) {
         return v.forNum(n_);
       }
     }
     class Eval implements Visitor<Integer> {
       public Integer forNum(int n) {
         return new Integer(n);
       }
     }
   }
   final class Lang extends LangF<Lang> {}
   
   class Lang2F<This extends Lang2F<This>> extends LangF<This> {
     interface Visitor<R> extends LangF<This>.Visitor<R> {
       public R forPlus(This.Exp e1, This.Exp e2);
     }
     class Plus implements Exp {
       protected final This.Exp e1_,e2_;
       public Plus(This.Exp e1, This.Exp e2) {e1_=e1; e2_=e2;}
       public <R> R visit(This.Visitor<R> v) {
         return v.forPlus(e1_,e2_);
       }
     }
     class Eval extends LangF<This>.Eval implements Visitor<Integer> {
       public Integer forPlus(This.Exp e1, This.Exp e2) {
         return new Integer(
           e1.visit(this).intValue() + e2.visit(this).intValue()
         );
       }
     }
     class Show implements Visitor<String> {
       public String forNum(int n) {
         return Integer.toString(n);
       }
       public String forPlus(This.Exp e1, This.Exp e2) {
         return "(" + e1.visit(this) + "+" + e2.visit(this) +")";
       }
     }
   }
   final class Lang2 extends Lang2F<Lang2> {}

2. Modern java Java pseudocode

   As I mentioned, if you can solve expression problem in a language easily, then 1). The expressiveness of this language is excellent 2). You have mastery of the language.

   Either I am a novice or java is simply not expressive enough, I can’t solve expression problem easily even with the hints from Wadler 30 years ago.

   // class Module1F<This extends Module1F<This>> with
   // final class Module1 extends Module1F<Module1> {}
   // can be used to make This type variable in Module1F refer to exactly the
   // same class (instead of possibly subclasses).
   // Quoting The Expression Problem by Philip Wadler
   // This use of `This' is the standard trick to provide accurate static typing in the prescence of subtypes (sometimes called MyType or ThisType).
   // See also Is there a way to refer to the current type with a type variable?
   // https://stackoverflow.com/questions/7354740/is-there-a-way-to-refeclass
   class Module1F<This extends Module1F<This>> {
       // A Visitor trait that is bounded by the trait Module1F.
       // We may think this as a Visitor specialized to the PlaneShape defined below.
       // Quoting The Expression Problem by Philip Wadler
       // The key trick here is the use of This.Exp and This.Visitor, via the
       // mechanism described in `Do parametric types beat virtual types?'.
       // Recall that mechanism allows a type variable to be indexed by any
       // inner class defined in the variable's bound.
       interface Visitor<R> {
           public R forTriangle(Double a, Double b, Double c);
       }
   
       // The data type we want to extend.
       interface PlaneShape {
           // Instead of passing a generic Visitor to this function, we pass a
           // This.Visitor.
           // This sibling interface Visitor may use methods specific to some data
           // variants,
           // e.g. forTriangle method specific to Triangles here!
   
           // There is actually an error in the code below. The error is:
           // Cannot make a static reference to the non-static type This Java (536871434),
           // which as far as I know means that This.Visitor<R> is not a static type,
           // and accessing This.Visitor<R> from a static context is not allowed.
           public <R> R visit(This.Visitor<R> v);
       }
   
       // A data type variant of the PlaneShape interface.
       class Triangle implements PlaneShape {
           protected final Double a_, b_, c_;
   
           public Triangle(Double a, Double b, Double c) {
               a_ = a;
               b_ = b;
               c_ = c;
           }
   
           // The public entry point for the visitor, used to run a specific operator for
           // this data variant.
           public <R> R visit(Visitor<R> v) {
               return v.forTriangle(a_, b_, c_);
           }
       }
   
       // Implement an operator based on visitor pattern.
       class Perimeter implements Visitor<Double> {
           public Double forTriangle(Double a, Double b, Double c) {
               return a + b + c;
           }
       }
   }
   
   final class Module1 extends Module1F<Module1> {
   }
   
   class Module2F<This extends Module2F<This>> extends Module1F<This> {
       interface Visitor<R> extends Module1F.Visitor<R> {
           public R forSquare(Double x);
       }
   
       class Square implements PlaneShape {
           protected final Double x_;
   
           public Square(Double x) {
               x_ = x;
           }
   
           public <R> R visit(Visitor<R> v) {
               return v.forSquare(x_);
           }
       }
   
       class Perimeter extends Module1F<This>.Perimeter implements Visitor<Double> {
           public Double forSquare(Double x) {
               return 4 * x;
           }
       }
   
       class Area implements Visitor<Double> {
           public Double forTriangle(Double a, Double b, Double c) {
               Double s = (a + b + c) / 2.0;
               Double area = Math.sqrt(s * (s - a) * (s - b) * (s - c));
               return area;
           }
   
           public Double forSquare(Double x) {
               return x * x;
           }
       }
   }
   
   final class Module2 extends Module2F<Module2> {
   }
   
   final class Main {
       static public void main(String[] args) {
           Module2 m1 = new Module2();
           Module2.PlaneShape e1 = m1.new Triangle(3.0, 4.0, 5.0);
           System.out.println("Perimeter: " + e1.visit(m2.new Perimeter()));
   
           Module2 m2 = new Module2();
           Module2.PlaneShape e2 = m2.new Square(3.0);
           System.out.println("Perimeter: " + e2.visit(m2.new Perimeter()));
           System.out.println("Area: " + e2.visit(m2.new Area()));
       }
   }

More methods

Solve expression problem with other language

multiple dispatch

The crux of the problem. Add a new method and dispatch this method one different types (these types are not predefined, we can add a new type as we wish). We can also solve expression problem with multiple dispatch in clojure and julia.

scala

Types in Object-Oriented Languages The Expression Problem in Scala (quite a few solutions to expression problem in scala)

java

Extensibility for the Masses Practical Extensibility with Object Algebras (They do not need the most advanced and difficult features of generics available in those languages, e.g. F-bounded quantification [6], wild-cards [44] or variance annotations. As a result, object algebras are applicable to a wide range of programming languages that have basic support for generics).

Generic references

• Expression problem - Wikipedia

• combinators/expression-problem: Synthesize a number of approaches (in multiple languages) that address the Expression Problem

• Solving the Expression Problem with Haskell · GitHub

• syntax - How do you solve Expression Problem in your language design? - Programming Language Design and Implementation Stack Exchange

• Dr. Ralf Laemmel Advanced FP - The Expression Problem - YouTube

• programming languages - What is the ‘expression problem’? - Stack Overflow

• Max.Computer - Solving the Expression Problem in Clojure

• The Expression Problem and its solutions - Eli Bendersky’s website

• More thoughts on the Expression Problem in Haskell - Eli Bendersky’s website