2010/11/2 Günther Schmidt
I've been given a few hints over time when I asked question concerning DSLs but regretfully didn't follow them up.
I think this is probably to do with observable sharing. The problem in DSLs is if you have: fact :: Term -> Term fact = Factorial instance Num Term where fromIntegral = Int (+) = Plus e = let x = fact 2 :: Term in x + x :: Term (Lets say the terms of our deeply embedded DSL are of type Term). If you pattern match on "e" you will get something like (Factorial (Int 2)) `Plus` (Factorial (Int 2)). This has lost the work sharing implicit in the original term, where the Factorial computation was shared. To recover this sharing, you either need some sort of observable sharing, or some common subexpression elimination (which risks introducing space leaks if your DSL has lazy semantics). Quite a lot of papers have mentioned this issue: the one that springs to mind is Gill's "Type Safe Observable Sharing". Cheers, Max