Annotated ASTs, and the tension between Bound, Free, and Cofree...
Hi, So I'm playing around with using bound to define a simple AST using the bound library to deal with substitution/abstraction. Being a lazy haskeller I figured that ASTs map nicely onto Free and that I could get all the necessary Applicative, Monad, etc. instances for free by using something like: newtype Expr a = Expr { unExpr :: Free (ExprF Expr) a } deriving (Functor,Applicative,Monad,Foldable,Traversable) data ExprF f a = App (f a) (f a) | Lam Type (Scope () f a) | TmTrue | TmFalse | If (f a) (f a) (f a) deriving (Eq,Ord,Show,Read,Functor,Foldable,Traversable) Now, for an AST to be useful, it has to be annotated with things like source location, type info, etc. So I started looking into how to accomplish this in a way where it's easy to add/modify annotations on any node of the AST. My initial idea was to use FreeT with ((,) a) as a base monad for annotations, but I quickly realised this fails, because "((,) a)" is only a Monad if 'a' is a Monoid and there's no sensible Monoid for type information/source locations. Then I looked around more and realised that this actually sounds a lot like Cofree. But here's where I run into problems. Bound expects the type of variables to be in the functor position of my Expr type, whereas Cofree expects the type of *annotations* to be in the functor position. So I can't figure out an elegant way to both use bound to deal with substitution for me *and* use Cofree to deal with annotations, since there's no way to make the types line up sanely. So my question boils down too: Has anyone done all the hard work for me already? i.e. how can I have an annotated AST with substitution *and* an easy way to modify the annotations, without writing a ton of boiler plate to deal with substitution and/or annotations? Cheers, Merijn
Have you looked at this? https://hackage.haskell.org/package/Annotations
Alan
On Wed, Jul 29, 2015 at 5:43 PM, Merijn Verstraaten
Hi,
So I'm playing around with using bound to define a simple AST using the bound library to deal with substitution/abstraction.
Being a lazy haskeller I figured that ASTs map nicely onto Free and that I could get all the necessary Applicative, Monad, etc. instances for free by using something like:
newtype Expr a = Expr { unExpr :: Free (ExprF Expr) a } deriving (Functor,Applicative,Monad,Foldable,Traversable)
data ExprF f a = App (f a) (f a) | Lam Type (Scope () f a) | TmTrue | TmFalse | If (f a) (f a) (f a) deriving (Eq,Ord,Show,Read,Functor,Foldable,Traversable)
Now, for an AST to be useful, it has to be annotated with things like source location, type info, etc. So I started looking into how to accomplish this in a way where it's easy to add/modify annotations on any node of the AST.
My initial idea was to use FreeT with ((,) a) as a base monad for annotations, but I quickly realised this fails, because "((,) a)" is only a Monad if 'a' is a Monoid and there's no sensible Monoid for type information/source locations.
Then I looked around more and realised that this actually sounds a lot like Cofree. But here's where I run into problems. Bound expects the type of variables to be in the functor position of my Expr type, whereas Cofree expects the type of *annotations* to be in the functor position.
So I can't figure out an elegant way to both use bound to deal with substitution for me *and* use Cofree to deal with annotations, since there's no way to make the types line up sanely.
So my question boils down too: Has anyone done all the hard work for me already? i.e. how can I have an annotated AST with substitution *and* an easy way to modify the annotations, without writing a ton of boiler plate to deal with substitution and/or annotations?
Cheers, Merijn
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
On Wed, Jul 29, 2015 at 05:43:23PM +0200, Merijn Verstraaten wrote:
newtype Expr a = Expr { unExpr :: Free (ExprF Expr) a } deriving (Functor,Applicative,Monad,Foldable,Traversable)
data ExprF f a = App (f a) (f a) | Lam Type (Scope () f a) | TmTrue | TmFalse | If (f a) (f a) (f a) deriving (Eq,Ord,Show,Read,Functor,Foldable,Traversable)
Now, for an AST to be useful, it has to be annotated with things like source location, type info, etc. So I started looking into how to accomplish this in a way where it's easy to add/modify annotations on any node of the AST.
If you want *some* subterms to be annotated, can you just add another constructor to ExprF? | Annotation annotationType (f a) Or if you want *every* subterm annotated then how about newtype Expr f a = Expr { unExpr :: Free (ExprF (Compose f Expr)) a }
Tom Ellis
Or if you want *every* subterm annotated then how about
newtype Expr f a = Expr { unExpr :: Free (ExprF (Compose f Expr)) a }
Merijn, if you get something like this working, I'd be interested to see some of your code, since I too tripped over a similar problem when looking for a nice way to represent annotated ASTs with bound. Having a good solution seems like it would be widely useful. -- Mikael Brockman
On Wed, Jul 29, 2015 at 05:43:23PM +0200, Merijn Verstraaten wrote:
Being a lazy haskeller I figured that ASTs map nicely onto Free and that I could get all the necessary Applicative, Monad, etc. instances for free by using something like:
newtype Expr a = Expr { unExpr :: Free (ExprF Expr) a } deriving (Functor,Applicative,Monad,Foldable,Traversable)
data ExprF f a = App (f a) (f a) | Lam Type (Scope () f a) | TmTrue | TmFalse | If (f a) (f a) (f a) deriving (Eq,Ord,Show,Read,Functor,Foldable,Traversable)
By the way, when I was playing around with bound and free I guessed that it would be more appropriate to define a "higher order" free thing which is called Mu here: Was bound but now I'm free: http://lpaste.net/136836 I'd be grateful if you'd take a look and see if you think it has any benefit over just using Free. Tom
participants (4)
-
Alan & Kim Zimmerman -
Merijn Verstraaten -
mikael.brockman＠gmail.com -
Tom Ellis