[Haskell-cafe] Re: more thoughts on "Finally tagless"

[Bruno Oliveira]

Hi Oleg,

On 9 Mar 2010, at 17:52, oleg at 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100309/c3d17946/attachment.html