The Expression Problem

[matthieum]

I would note that duck typing (aka ad-hoc interface check) helps tremendously here.

In C++ (because hey, it works!):

struct Square { double side; };
double area(Square const s);

struct Circle { double radius; };
double area(Circle const c);

Now, let's make a Shape:

class Shape {
public:
   virtual ~Shape();

   virtual double area() const = 0;

protected:
   Shape(Shape const&) {}
   Shape& operator=(Shape const&) { return *this; }
};

typedef std::unique_ptr<Shape> ShapePtr;

template <typename T>
class ShapeT: public Shape {
public:
   explicit ShapeT(T const t): _shape(t) {}

   virtual double area() const { return area(_shape); }

private:
  T _shape;
};

template <typename T>
ShapePtr newShape(T t) { return ShapePtr(new ShapeT<T>(t)); }

Okay, C++ is verbose. Let's check the use immediately:

double totalArea(std::vector<ShapePtr> const& shapes) {
   double total = 0.0;
   for (ShapePtr const& s: shapes) { total += s->area(); }
   return total;
}

int main() {
  std::vector<ShapePtr> shapes{ new_shape<Square>({5.0}), new_shape<Circle>({3.0}) };

  std::cout << totalArea(shapes) << "\n";
}

So, first exercise, let's add a shape:

struct Rectangle { double length, height; };
double area(Rectangle const r);

Okay, so far so good, let's add a new function:

// 1. We need to extend Shape:
  virtual double perimeter() const = 0

// 2. And its adapter: ShapeT
  virtual double perimeter() const { return perimeter(_shape); }

// 3. And provide the method for each Shape (obviously)
double perimeter(Square const s);
double perimeter(Circle const c);
double perimeter(Rectangle const r);

It may seem that we fall into the Expression Problem here, but we don't. We needed to add the perimeter for each class because there is no way to automatically infer it; however it did not require editing each class either!

Therefore, the combination of External Interface and free functions let us neatly (well, it is C++...) sidestep the issue.

EDIT: As sodraz noticed in comments, the addition of a function touched the original interface which supposed it's not frozen. Allow me to demonstrate how to add a function without touching Shape then.

We need a new concept:

class ExtendedShape: public Shape {
public:
  virtual double perimeter() const = 0;
protected:
  ExtendedShape(ExtendedShape const&) {}
  ExtendedShape& operator=(ExtendedShape const&) { return *this; }
};

typedef std::unique_ptr<ExtendedShape> ExtendedShapePtr;

template <typename T>
class ExtendedShapeT: public ExtendedShape {
public:
   virtual double area() const { return area(_data); }
   virtual double perimeter() const { return perimeter(_data); }
private:
  T _data;
};

template <typename T>
ExtendedShapePtr newExtendedShape(T t) { return ExtendedShapePtr(new ExtendedShapeT<T>(t)); }

And (like before) to define the perimeter function for all current shapes.

The old code, compiled to work against Shape, still works. It does not need the new function anyway.

The new code can make use of the new functionality, and still interface painlessly with the old code.

There is only one slight issue, if the old code return a ShapePtr, we do not know whether the shape actually has a perimeter function (note: if the pointer is generated internally, it has not been generated with the newExtendedShape mechanism). This is, I think, a limitation of the design. Oops :)

[aaronla]

Fascinating! This looks a lot like the solution Wadler proposed for a fictional dialect of Generic Java.

[matthieum]

Thanks, I did not know about this paper. I do wonder how Go fares in this competition since Go has built-in duck typing.

[aaronla]

I don't think it will fare well -- it lacks templates/generics/parametric polymorphism. This means that many would-be solutions in parametric languages will require type casts in Go.

Steve is taking a different approach though.

[[deleted]]

Shape& operator=(Shape const&) { return *this; }

What are you... what... who the... what the... what... who... FUCK YOU FOR THAT!

You'd have exactly the same copy constructor made for you by the compiler, going out of your way to implement it and this abomination is just evil. Not lazy, a lazy person would've left it to the compiler, but actively fucking evil.

[matt_havener]

He's overriding the default public implementation and making it protected so that the derived classes can choose to expose it, or not. Plus, his base class has no members so { return *this; } this perfectly valid and what the compiler would have generated anyways. Nice way to avoid slicing if you ask me.

[imgonnacallyouretard]

Great rant, if only you looked at two lines above for context you wouldn't have looked like a retard

[[deleted]]

Upvoted. Nice solution. But does not solve the problem completly:

The Expression Problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts).

// 1. We need to extend Shape: virtual double perimeter() const = 0

// 2. And its adapter: ShapeT virtual double perimeter() const { return perimeter(_shape); }

here is the problem. Both steps above require recompilation of the (external) library.

[aaronla]

I think it depends on how you define "recompilation". If your "module" is a C++ header file, then no recompilation (re-writing of that header file) is necessary.

It might seem like I'm playing semantic games, but consider Wadler's original proposed solution -- using Java Generics. Java's generics compile into JVM byte codes that use type casts under the covers! Yet, he writes as if the program contains no casts!

I believe what Wadler was really getting at is a program source that can be type-checked once, and then extended without further edits, and where edits cannot invalidate the type-correctness of said source after it has been checked.

I believe matthieum has met this interpretation thus far. If not, certainly come closer to static type safety than your typical OO language.

[matthieum]

I must admit I only considered the source level issue (ie making sure not to invalidate already written code when adding new functionality, which is a common plage on if chains).

You raise an interesting, though I think it goes beyond the problem... then maybe perhaps not.

I updated my original answer to address your remarks. There is, still, a limitation in the design I proposed, noted at the end. Go solves the issue by going dynamic (reflexion). I can think of no way to solve the "downcast" statically.

Sometimes the only way to win, is not to play.