Independently Extensible Solutions to the Expression Problem

Abstract The expression problem is fundamental for the develop- ment of extensible software. Many (partial) solutions to this important problem have been proposed in the past. None of these approaches solves the problem of using different, independent extensions jointly. This paper pro- poses solutions to the expression problem that make it possible to combine independent extensions in a flexible, modular, and type-safe way. The solutions, formulated in the programming language Scala, are affected with only a small implementation overhead and are easy to imple- ment by hand. 1 The Expression Problem Since software evolves over time, it is essential for soft- ware systems to be extensible. But the development of extensible software poses many design and implemen- tation problems, especially, if extensions cannot be an- ticipated. The expression problem is probably the most fundamental one among these problems. It arises when recursively defined datatypes and operations on these types have to be extended simultaneously. The term ex- pression problem was originally coined by Phil Wadler in a post on the Java-Genericity mailing list [25], in which he also proposed a solution written in an extended version of Generic Java [3]. Only later it appeared that Wadler's solution could not be typed. For this paper, we paraphrase the problem in the fol- lowing way: Suppose we have a datatype which is defined by a set of cases and we have processors which operate on this datatype. There are primarily two directions along which we can extend such a system: * The extension of the datatype with new data vari-ants, * The addition of new processors. We require that processors handle only a finite number of data variants and thus do not provide defaults which could handle...