[Haskell-cafe] Re: Difficulties with tagless - create "primitives" or compose them

Jacques Carette carette at mcmaster.ca
Mon Jun 14 09:23:46 EDT 2010

Günther Schmidt wrote:
> I have recently found something new that might also prove to be useful 
> for EDSLs.
> http://blog.sigfpe.com/2009/05/three-projections-of-doctor-futamura.html
> Dan's blog post doesn't give any code or implementation but in a way 
> it tackles the same problem, and since you also mention partial 
> evaluation and transformation you might also find this interesting.

Actually, we tried to do the 2nd Futamura projection in tagless-final 
style -- and could not.  This paper
http://www.daimi.au.dk/~ko/papers/pldi142_rendel1.pdf [1]
documents why we were not able to: such self-embeddings need "infinite 
type towers", which neither Haskell not O'Caml have.  We did have a 
work-around using both a object-language-level 'let' and a 
meta-language-level 'let', but it was unsatisfactory and, in the end, we 
cut that whole section out of the JFP paper.

It would be interesting to see if using the techniques of 
Atkey-Lindley-Yallop [2]
would make this easier.  I have not had a chance to try.



 author = {Rendel, Tillmann and Ostermann, Klaus and Hofer, Christian},
 title = {Typed self-representation},
 booktitle = {PLDI '09: Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation},
 year = {2009},
 isbn = {978-1-60558-392-1},
 pages = {293--303},
 location = {Dublin, Ireland},
 doi = {http://doi.acm.org/10.1145/1542476.1542509},
 publisher = {ACM},
 address = {New York, NY, USA},


 author = {Atkey, Robert and Lindley, Sam and Yallop, Jeremy},
 title = {Unembedding domain-specific languages},
 booktitle = {Haskell '09: Proceedings of the 2nd ACM SIGPLAN symposium on Haskell},
 year = {2009},
 isbn = {978-1-60558-508-6},
 pages = {37--48},
 location = {Edinburgh, Scotland},
 doi = {http://doi.acm.org/10.1145/1596638.1596644},
 publisher = {ACM},
 address = {New York, NY, USA},

More information about the Haskell-Cafe mailing list