[Haskell-cafe] Re: I love purity, but it's killing me.

[Heinrich Apfelmus]

Conal Elliott wrote:
> Sittampalam, Ganesh wrote
>> In my experience [1], observable sharing using GHC's stable names is a
>> pretty effective solution to this problem.
> 
> Plus unsafePerformIO and weak references as in *Stretching the storage
> manager: weak pointers and stable names in
> Haskell<http://citeseer.ist.psu.edu/peytonjones99stretching.html>
> *?
> 
> Lacking a more elegant alternative, that's what I'll probably do again, as
> in Pan, Vertigo, and Pajama.

Note that the lack of a more elegant alternative, i.e. one that avoids
unsafePerformIO  for observing sharing, is not a random inconvenience
but an unavoidable consequence of embedding a DSL into a host language.
In other words, there is a fundamental problem here and unsafePerformIO
is but the usual duct tape for inadequately fixing fundamental problems.


The problem is that there are two types of  let  expressions, the one of
the host language and the one of the embedded language. For instance,
consider the example

    let a = Add 2 3  :: Expr
        b = Add a a  :: Expr

Replacing equals with equals, this is the same as

    Add (Add 2 3) (Add 2 3)  :: Expr

and there is no sharing in the embedded language. But I argue that this
is a good thing, for sharing in the embedded language should be done
with  let  expressions of the embedded language, like for example

    Let ['a' := Add 2 3,
         'b' := Add (Var 'a') (Var 'a') ] :: Expr

Clearly, these are two different expressions of the embedded language,
even if one is an optimization of the other!

One could say that the  let  of the host language is a shorthand
notation for constructing large  Expr  and only the  Let  of the
embedded language can express sharing inside the embedded language. As
soon as we try to make the former synonymous to the latter, our ability
to use it as a shorthand notation is gone and it now becomes
*impossible* to represent

   Add (Add 2 3) (Add 2 3)  :: Expr

as

   let a = Add 2 3  :: Expr
       b = Add a a  :: Expr

Whether this is desirable or not is irrelevant; the host language
Haskell will rebel at this.


An analogous example would be the two fixed points of a  MonadFix ,
namely the "internal" (embedded) fixed point

   fixInternal :: (a -> m a) -> m a
   fixInternal = mfix

and the "external" (host) fixed point

   fixExternal :: (a -> m a) -> m a
   fixExternal = \f -> fix (>>= f)

(Perhaps not surprisingly, MonadFix was first discovered/used when
designing the DSL Lava, if I am informed correctly.)



Regards,
apfelmus

--
http://apfelmus.nfshost.com