Diagrams/Dev/Expression

The problem

The Expression Problem, coined by Phil Wadler, describes a situation where you have a sum type and some operations on it; the problem is to be able to both add new cases to the sum type as well as add new operations. Some approaches, e.g. OOP, make it easy to add new disjuncts (just make a new subclass, and implement all the appropriate methods) but annoying to add new operations (you have to go back through and add a new method implementation for every existing class); others, e.g. algebraic data types, make it easy to add new operations (just write a new function) but annoying to add new disjuncts (you can add a new constructor to your data type but then you have to go through and add a new case to the implementation of every existing function).

This problem shows up, in a disguised form, in diagrams. Our "sum type" is the set of primitives that can be used to build diagrams; our "operations" are different backends. We have adopted a somewhat more dynamic solution: primitives can be any type, and backends declare which primitives they can handle by implementing an instance of Renderable. This means that new primitives can be easily added (just make a new type; it does not require changing existing backends, which will simply not be able to render it) but also new backends.

This is sort of like having an algebraic data type for primitives, but allowing the backends (thought of as functions) to have "incomplete pattern matching", i.e. to simply not handle some primitives. Literally implementing it that way would be undesirable, however, because then handing a diagram to a backend which contained primitives it did not handle would cause the program to crash with a runtime pattern match failure.

Note, if we did away with the ability of different backends to support different primitive types, these problems would all go away. We could just have a single algebraic data type specifying the static list of primitives that all backends must support, and that would be that. (This is the approach taken by many simpler drawing libraries, e.g. gloss.) However, (it seems to me at least) that the added flexibility of backends which can't support certain primitives, or support extra special backend-specific primitives, is a really nice feature that would be very painful to give up.

The solution, and a Choice

Instead, the "algebraic data type" of primitives is left implicit, with each primitive simply represented by its own type. At this point, however, there are two choices, corresponding, essentially, to static vs. dynamic typing.

Static typing

This is the approach currently taken. Each backend has a "token type" and must implement instances of the form Renderable Prim Backend. Prims get wrapped up in an existential wrapper along with an appropriate Renderable instance. When a backend goes to render some primitives, it just unwraps them and uses the enclosed Renderable instance; it doesn't even need to know what type they are.

This does mean, however, that the backend type must show up as a parameter to the Diagram type---otherwise the existentially quanitifed Renderable instances would be useless, as there would be no way to know which backend they are for! However, this also makes sense, in a way. If a diagram has type Diagram Foo R2, then we know statically that it can only contain primitives which can be rendered by backend Foo---because any primitive of type P must be wrapped up with a Renderable P Foo instance, and the only way to obtain such an instance is if it is provided by the backend.

More generally, diagrams can be given polymorphic types like

(Backend b R2, Renderable (Path R2) b, Renderable Image b) => Diagram b R2

with one constraint for each different type of primitive contained in the diagram.

Pros

• Rendering will never fail at runtime. We know statically that if it typechecks to give a certain diagram to a certain backend, the backend knows what to do with all the primitives it contains.

Cons

• The backend type parameter ends up "infecting" quite a lot of types, including XXX list

Dynamic typing

The alternative is to use a dynamic typing approach. We do away with the Renderable type class and simply package up each primitive with a Typeable constraint. Then at render time, a backend unwraps each primitive and checks whether it corresponds to a type which that backend knows how to render. If not, it "fails at runtime"---which could mean many different things, e.g.

• literally crashing (not very nice)
• treating the primitive as if it were mempty (graceful, but might lead to weird hard-to-debug behavior for users who don't realize a certain primitive is not supported by a certain backend)
• the above, plus returning some sort of warning/error message (we could e.g. change the Backend type class to allow/require backends to return errors and warnings).

Pros

• No more backend type parameter "infecting" the types. 2D diagrams have the simple type Diagram R2.

• The above makes it much easier to hand a diagram to different backends, or even to use multiple backends at once.

• More graceful degrading of service---if a diagram has a single small feature that is not supported by backend X,

• Makes it possible to have a

References

• Relevant #diagrams discussion
• The expression problem