(start writing up description of expression problem + backend type parameters)
(add some references)
Revision as of 01:25, 23 April 2014
1 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.
2 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.
2.1 Static typing
This is the approach currently taken.
TODO describe current approach in detail along with pros and cons
2.2 Dynamic typing
TODO describe alternative approach with pros and cons