[Haskell-cafe] Trying to write an Embedded DSL that threads a monad?

[Ian Bloom]

Hi,
Thanks for your reply. I think the Monad that I chose for my example code
was not the best. I've been hoping to generalize across all possible monads
but the real use case arises because I have an expensive computation that I
know will repeat multiple times within the evaluation of a given large
expression so in my monad I want to implement a cache. If I query the cache
and it has not done the computation it will perform the computation once
and then return the result plus a new cache holding the result, if the
computation has already been performed it is present in the cache and taken
from there. In my definition of Exp there would then be one more value, say
Ext that when applied to a parameter can access and modify the cache. In
this case the order of evaluation doesn't affect the result of the Monad,
I'm not sure if "commutative" is the right way to describe this.

There is a lot to think about here but let me try playing around with your
code.

Thanks,
Ian

On Thu, Oct 15, 2015 at 7:43 AM, wren romano <winterkoninkje at gmail.com>
wrote:

> On Wed, Oct 14, 2015 at 9:31 AM, Ian Bloom <ianmbloom at gmail.com> wrote:
> > Here is what I'd like from the language:
> >
> >  * To use haskell syntax for substitution and pattern matching rather
> than
> > implementing this myself.
> >  * To be able to express lambdas in my language.
> >  * To be able to embed any haskell terms including functions into the
> > language.
> >  * I'd like the Haskell type checker to tell me about bad terms.
> >  * I'd like to thread a monad through the entire expression.
>
> It's still not clear exactly what you want/need with that last bullet
> point. So I can try to offer help, but have no idea if this is on the
> right track...
>
>
> > So here is the first implementation that I tried of this (full source
> here:
> > http://lpaste.net/142959)
> >
> >     data Exp m x where
> >        Val :: m x -> Exp m x
> >        Lam1 :: m (a -> Exp m b)        -> Exp m (a -> b)
> >        Lam2 :: m (a -> Exp m (b -> c)) -> Exp m (a -> b -> c)
> >
> > a function liftE allows me to lift a haskell term into an expression:
> >
> >     liftE x = Val $ return x
> >
> > Application is a function <@> so:
> >
> >     (<@>) :: forall m a b. Monad m => Exp m (a -> b) -> Exp m a -> Exp m
> b
> >     (<@>) (Val  f) (Val x) = Val  $ f `ap` x
> >     (<@>) (Lam2 f) (Val x) = Lam1 $ f >>= \f' -> x >>= \x' -> unLam1 $
> f' x'
> >     (<@>) (Lam1 f) (Val x) = Val $ f >>= \f' -> x >>= \x' -> unVal $ f'
> x'
> >
> >[...]
> >
> > Ok so that's a lot. I was surprised I got this working. You can see from
> the
> > code that my main gripe with this is I haven't found a way to remove the
> > need to specify the number of embedded lambdas using Lam1 and Lam2 (we
> could
> > easily add more) and I haven't found a way to apply a Lam to another Lam.
> > I'm also curious if I am reinventing the wheel, I hadn't found a library
> yet
> > that let's me do something similar.
>
> So, two things to notice.
>
> First, the type for Lam2 is just a refinement of the type for Lam1.
> Thus, Lam2 gives you nothing new in terms of what can be made to
> typecheck; the only thing it gives you is the ability to make runtime
> decisions based on whether a particular expression was built with Lam1
> or Lam2 (or Val).
>
> Second, the apparent need for multiple lambdas stems from the fact
> that your (<@>) function needs to "count down by one" each time an
> argument is applied. This hides a big problem in the definition,
> namely that you're assuming that after the right number of arguments
> the resulting Exp will be built with Val; which isn't actually
> guaranteed by the types.
>
> After playing around with it for a while, it seems like the crux of
> the issue comes from not being able to embed m(Exp m a) into Exp m a.
> So, we can fix that by adding a new constructor:
>
>     data Exp m x where
>         Val :: m a -> Exp m a
>         Exp :: m (Exp m a) -> Exp m a
>         Lam :: m (a -> Exp m b) -> Exp m (a -> b)
>
>     Exp f <@> x     = Exp ((<@> x) <$> f)
>     f     <@> Exp x = Exp ((f <@>) <$> x)
>     Val f <@> Val x = Val (f <*> x)
>     Lam f <@> Val x = Exp (($) <$> f <*> x)
>     -- TODO: Val/Lam and Lam/Lam cases...
>
>     unVal :: Monad m => Exp m a -> m a
>     unVal (Val v) = v
>     unVal (Exp e) = e >>= unVal
>
> This at least works for the given test case with mapE, testExpression,
> and test— though it doesn't give exactly the same result about the
> number of binds. But again I'm not sure what you're really after here.
>
> (Note that, once we add the Exp constructor, we can redo Val to take a
> pure argument without losing anything re typeability. Though again,
> the exact semantics of dubious things like (>>=)-counting won't
> necessarily be preserved. Still, as a general rule, it makes sense for
> EDSLs to distinguish between pure values vs impure expressions...)
>
> --
> Live well,
> ~wren
>



-- 
718.755.5483
http://ianbloom.com/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151015/9cc5adeb/attachment.html>