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

[Jacques Carette]

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]
http://homepages.inf.ed.ac.uk/slindley/papers/unembedding.pdf
would make this easier.  I have not had a chance to try.

Jacques

[1]

@inproceedings{1542509,
 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},
 }

[2]

@inproceedings{1596644,
 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},
 }