Solving the expression problem with type classes

Sorry if this is OT, but I can't for the life of me figure out which paper I saw this in. I'm trying to gather some papers on the expression problem, and I recall one paper that was not specifically about the expression problem, but that mentioned a solution, hence my difficulty finding it.

The paper dealt with type classes, and one of the subsections specifically mentioned that the structure described in the paper incidentally implied a solution to the expression problem using type classes. So the mention of the expression problem was only an aside; not a footnote, it was discussed in a subsection of the paper itself. I don't recall if the solution described was actually novel, but IIRC the discussion in the paper implied that it was.

I remember the paper was in a two-column format if that helps, and I believe it was published after 2005, but I can't be certain. I'm almost certain I have it somewhere on my hard drive, but I haven't been able to find it in all my manual inspections, greping and file system searching. I'm pretty sure I came across it in the past 6 months, a year at the most, so it may have been posted to LtU. It doesn't seem to be on any list of links describing solutions to the expression problem, like this one.

If anyone has any clue, I'd very much appreciate a heads up!

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Maybe this is the paper you

Maybe this is the paper you are looking for?

Afraid not. That one's in my

Afraid not. That one's in my list already, so I'm aware of the technique discussed in section 2.4. I'm not sure whether the technique in the paper I'm looking for differs from that described in your paper, but I'd really like to find it so I ascertain that for myself.

I wish I could remember something else distinct about the paper so that I can figure out where I filed it, or what to search for... The expression problem is a rather central theme of your paper, but not of the paper I'm looking for IIRC.

A la carte...

This is the paper that occurred to me for some reason, although I'm sure it's already in your reading list. Thought I'd mention it anyway, just in case...

Indeed, that was the best

Indeed, that was the best paper about solving the expression problem prior to the introduction of type families. It's on the list I linked to in the post though, so that's not it. Darn. :-)



Particularly the "extensible" interpreter in the source which does not use OOHaskell techniques, but just type classes.

Unembedding Domain-Specific Languages

It sounds like you may be looking for Unembedding Domain-Specific Languages.

No longer in the Unembedding paper

An earlier draft of that paper had a section on the expression problem, but it's not in the final version. However, essentially the same idea appears in Section 1.6 of Extensible and Modular Generics for the Masses.

I have the Modular Generics

I have the Modular Generics paper, but I don't seem to have the unembedding paper, so this very well could be it. Is an earlier draft with the section intact available for download somewhere? Just for the sake of my sanity? :-)

Not available for download

Not available for download, but if you email me (e.g. at the address in the unembedding paper) I'll send you a draft.

Extensibility problem

See also the "extensibility problem", which was an alternative to Wadler's name coined by the PLT (e.g., if you want to see how units solve the expression problem, use extensibility problem instead). Definitely not the paper you are referring to, as the term is pre-2002.

Anyways, isn't this problem solved already? It used to be that OOPSLA/ECOOP would get 3 or 4 solutions to the expression problem published every year, but I've lost interest in counting.

Is this the paper you're

Is this the "extensibility problem" paper you're referring to?

Thats one of them. Given

Thats one of them. Given that I studied under Matthew, everything that I published on the expression problem will also refer to it as the extensibility problem. The MultiJava work also refers to it by this name. Names are a funny thing.

Another paper

Software Extension and Integration with Type Classes, by Ralf Lämmel and Klaus Ostermann. This paper has a pretty clear discussion of this pattern.