Independently Extensible Solutions to the Expression Problem
Matthias Zenger, Martin Odersky · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2004
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 arbitrary cases of future extensions. The challenge is now to find an implementation technique which satisfies the following list of requirements: * Extensibility in both dimensions: It should be possible to add new data variants and adapt existing opera- tions accordingly. Furthermore, it should be possible to introduce new processors. * Strong static type safety: It should be impossible to apply a processor to a data variant which it cannot handle.