Hi Oleg, On 9 Mar 2010, at 17:52, oleg@okmij.org wrote:
Stephen Tetley wrote:
The finally tagless style is an implementation of the TypeCase pattern (Bruno C. d. S. Oliveira and Jeremy Gibbons):
http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/typecase.pdf
The finally tagless style is slightly more general.
The TypeCase paper emphasizes that TypeCase is a pattern to define a _closed_ type-indexed function -- the indexed family is fixed but the collection of functions is extensible. This is in contrast to type classes, where the collection of functions is fixed (by the class declaration) but the indexed family is extensible (more type class instances can be defined at any time).
The tagless final approach permits the definition of an extensible family of open type-indexed functions. For example, we can define a `data type' of expressions and extend it at any time with more expression forms *and* more processing functions (e.g., a new way to print or compile an expression). With the tagless final approach, we have the extensibility in both dimensions.
It is true that "Typecase" is aimed at closed type-indexed functions, although in Section 4.2 I note, in passing, that you can achieve extensibility too for the *explicit* representations variation of the typecase pattern (which is the same that is used by tagless final): "The smart datatype solution in this section is fully closed to extension. That is, in order to add another case in the formatting list, such as a constructor Chr that handles characters, we would need to modify the GADT itself. On the other hand, the solution in the previous section using the explicit version of the design pattern allows some form of extensibility. Adding a new case for printf that handles characters corresponds to adding a new function, which could even be in a different module." Fortunately, there is a whole paper devoted to the issue of extensibility for an application of the typecase pattern using *explict* representations: Extensible and Modular Generics for the Masses Bruno C. d. S. Oliveira, Ralf Hinze and Andres Loeh In Henrik Nilsson, editor, Trends in Functional Programming (TFP). Link: http://ropas.snu.ac.kr/%7Ebruno/papers/ExtensibleGM.pdf And the relation to the expression problem is pointed out there. Perhaps you'd like to have a look at the paper if you haven't seen it already. Bruno