26 Jan 2013 23:03

## catamorphisms and attribute grammars

Dear Haskellers,

I read some stuff about attribute grammars recently [1] and how UUAGC [2] can be used for code generation. I felt like this should be possible inside Haskell too so I did some experiments and I realized that indeed catamorphisms can be represented in such a way that they can be combined together and all run in a single pass over a data structure. In fact, they form an applicative functor.

[1] http://www.haskell.org/haskellwiki/Attribute_grammar
[2] Utrecht University Attribute Grammar Compiler

To give an example, let's say we want to compute the average value of a binary tree. If we compute a sum first and then count the elements, the whole tree is retained in memory (and moreover, deforestation won't happen). So it's desirable to compute both values at once during a single pass:

-- Count nodes in a tree.
count' :: (Num i) => CataBase (BinTree a) i
count' = ...

-- Sums all nodes in a tree.
sum' :: (Num n) => CataBase (BinTree n) n
sum' = ...

-- Computes the average value of a tree.
avg' :: (Fractional b) => CataBase (BinTree b) b
avg' = (/) <\$> sum' <*> count'

Then we can compute the average in a single pass like

runHylo avg' treeAnamorphism seed

My experiments together with the example are available at https://github.com/ppetr/recursion-attributes

I wonder, is there an existing library that expresses this idea?

Best regards,
Petr Pudlak

```_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
```
27 Jan 2013 01:20

### Re: catamorphisms and attribute grammars

```* Petr P <petr.mvd <at> gmail.com> [2013-01-26 23:03:51+0100]
>   Dear Haskellers,
>
> I read some stuff about attribute grammars recently [1] and how UUAGC [2]
> can be used for code generation. I felt like this should be possible inside
> Haskell too so I did some experiments and I realized that indeed
> catamorphisms can be represented in such a way that they can be combined
> together and all run in a single pass over a data structure. In fact, they
> form an applicative functor.
>
> ...
>
> My experiments together with the example are available at https://github
> .com/ppetr/recursion-attributes

Very nice! This can be generalized to arbitrary arrows:

{-# LANGUAGE ExistentialQuantification #-}

import Prelude hiding (id)
import Control.Arrow
import Control.Applicative
import Control.Category

data F from to b c = forall d . F (from b d) (to d c)

instance (Arrow from, Arrow to) => Functor (F from to b) where
fmap f x = pure f <*> x

instance (Arrow from, Arrow to) => Applicative (F from to b) where
pure x = F (arr \$ const x) id
F from1 to1 <*> F from2 to2 =
F (from1 &&& from2) (to1 *** to2 >>> arr (uncurry id))

Now your construction is a special case where 'from' is the category of
f-algebras and 'to' is the usual (->) category.

I wonder what's a categorical interpretation of F itself.

Roman
```
27 Jan 2013 09:58

### Re: catamorphisms and attribute grammars

Roman, this is interesting. Is this arrow generalization in some library already? And does it have a name?

Best regards,
Petr Pudlak

2013/1/27 Roman Cheplyaka
* Petr P <petr.mvd <at> gmail.com> [2013-01-26 23:03:51+0100]
>   Dear Haskellers,
>
> I read some stuff about attribute grammars recently [1] and how UUAGC [2]
> can be used for code generation. I felt like this should be possible inside
> Haskell too so I did some experiments and I realized that indeed
> catamorphisms can be represented in such a way that they can be combined
> together and all run in a single pass over a data structure. In fact, they
> form an applicative functor.
>
> ...
>
> My experiments together with the example are available at https://github
> .com/ppetr/recursion-attributes

Very nice! This can be generalized to arbitrary arrows:

{-# LANGUAGE ExistentialQuantification #-}

import Prelude hiding (id)
import Control.Arrow
import Control.Applicative
import Control.Category

data F from to b c = forall d . F (from b d) (to d c)

instance (Arrow from, Arrow to) => Functor (F from to b) where
fmap f x = pure f <*> x

instance (Arrow from, Arrow to) => Applicative (F from to b) where
pure x = F (arr \$ const x) id
F from1 to1 <*> F from2 to2 =
F (from1 &&& from2) (to1 *** to2 >>> arr (uncurry id))

Now your construction is a special case where 'from' is the category of
f-algebras and 'to' is the usual (->) category.

I wonder what's a categorical interpretation of F itself.

Roman

```_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
```
29 Jan 2013 16:23

### Re: catamorphisms and attribute grammars

```On Sun, Jan 27, 2013 at 12:20:25AM +0000, Roman Cheplyaka wrote:
> Very nice! This can be generalized to arbitrary arrows:
>
>   {-# LANGUAGE ExistentialQuantification #-}
>
>   import Prelude hiding (id)
>   import Control.Arrow
>   import Control.Applicative
>   import Control.Category
>
>   data F from to b c = forall d . F (from b d) (to d c)
>
>   instance (Arrow from, Arrow to) => Functor (F from to b) where
>     fmap f x = pure f <*> x
>
>   instance (Arrow from, Arrow to) => Applicative (F from to b) where
>     pure x = F (arr \$ const x) id
>     F from1 to1 <*> F from2 to2 =
>       F (from1 &&& from2) (to1 *** to2 >>> arr (uncurry id))

You only require that from b is Applicative, so that in turn can be
generalized:

data F g to c = forall d . F (g d) (to d c)

instance (Applicative g, Arrow to) => Functor (F g to) where
fmap f x = pure f <*> x

instance (Applicative g, Arrow to) => Applicative (F g to) where
pure x = F (pure x) id
F from1 to1 <*> F from2 to2 =
F ((,) <\$> from1 <*> from2) (to1 *** to2 >>> arr (uncurry id))

> I wonder what's a categorical interpretation of F itself.

It's a variety of left Kan extension (cf section 5 of "Constructing
Applicative Functors" at MPC'2012).
```
27 Jan 2013 08:20

### Re: catamorphisms and attribute grammars

```Hi Petr,

Congratulations -- you've just implemented a Moore machine! [1]

I posted something very much like this just last year [2]. It's a very
common pattern in Haskell, forming the basis of coroutines and
iteratees and many other things.

Edward Kmett includes it in his machines package [3]. His variation,
like mine, hides the state inside a closure, removing the need for
existentials. pipes 2.0 contains one implemented as a free monad [4].

[1] http://en.wikipedia.org/wiki/Moore_machine
[2] http://hackage.haskell.org/packages/archive/machines/0.2.3/doc/html/Data-Machine-Moore.html
[3] http://www.haskell.org/pipermail/haskell-cafe/2012-May/101460.html
[4] http://hackage.haskell.org/packages/archive/pipes/2.0.0/doc/html/Control-Pipe-Common.html

Chris

On Sun, Jan 27, 2013 at 11:03 AM, Petr P <petr.mvd <at> gmail.com> wrote:
>   Dear Haskellers,
>
> I read some stuff about attribute grammars recently [1] and how UUAGC [2]
> can be used for code generation. I felt like this should be possible inside
> Haskell too so I did some experiments and I realized that indeed
> catamorphisms can be represented in such a way that they can be combined
> together and all run in a single pass over a data structure. In fact, they
> form an applicative functor.
>
> [1] http://www.haskell.org/haskellwiki/Attribute_grammar
> [2] Utrecht University Attribute Grammar Compiler
>
> To give an example, let's say we want to compute the average value of a
> binary tree. If we compute a sum first and then count the elements, the
> whole tree is retained in memory (and moreover, deforestation won't happen).
> So it's desirable to compute both values at once during a single pass:
>
> -- Count nodes in a tree.
> count' :: (Num i) => CataBase (BinTree a) i
> count' = ...
>
> -- Sums all nodes in a tree.
> sum' :: (Num n) => CataBase (BinTree n) n
> sum' = ...
>
> -- Computes the average value of a tree.
> avg' :: (Fractional b) => CataBase (BinTree b) b
> avg' = (/) <\$> sum' <*> count'
>
> Then we can compute the average in a single pass like
>
>     runHylo avg' treeAnamorphism seed
>
> My experiments together with the example are available at
> https://github.com/ppetr/recursion-attributes
>
> I wonder, is there an existing library that expresses this idea?
>
>   Best regards,
>   Petr Pudlak
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
```
27 Jan 2013 08:49

### Re: catamorphisms and attribute grammars

```Hi Chris,

While the two things solve similar problems and have other similarities,
they are still quite different.

It's hard to call Petr's type a machine — there's no dynamics in it. It's
just a pair of an f-algebra and finalizer. Values of your type return
themselves — it is exactly this recursion that makes them "machines".

And the problem solved are different. Catamorphisms are not the same as
folds in the sense of Data.Foldable. Folds get elements one at a time,
while a catamorphism sees the structure of the tree.

For instance, it is possible to write an evaluator for an expression AST
using catamorphisms, but not using Moore machines[*], because you won't
know what the operations are.

[*] without linearizing the tree beforehand

Roman

* Chris Wong <chrisyco+haskell-cafe <at> gmail.com> [2013-01-27 20:20:07+1300]
> Hi Petr,
>
> Congratulations -- you've just implemented a Moore machine! [1]
>
> I posted something very much like this just last year [2]. It's a very
> common pattern in Haskell, forming the basis of coroutines and
> iteratees and many other things.
>
> Edward Kmett includes it in his machines package [3]. His variation,
> like mine, hides the state inside a closure, removing the need for
> existentials. pipes 2.0 contains one implemented as a free monad [4].
>
> [1] http://en.wikipedia.org/wiki/Moore_machine
> [2] http://hackage.haskell.org/packages/archive/machines/0.2.3/doc/html/Data-Machine-Moore.html
> [3] http://www.haskell.org/pipermail/haskell-cafe/2012-May/101460.html
> [4] http://hackage.haskell.org/packages/archive/pipes/2.0.0/doc/html/Control-Pipe-Common.html
>
> Chris
>
> On Sun, Jan 27, 2013 at 11:03 AM, Petr P <petr.mvd <at> gmail.com> wrote:
> >   Dear Haskellers,
> >
> > I read some stuff about attribute grammars recently [1] and how UUAGC [2]
> > can be used for code generation. I felt like this should be possible inside
> > Haskell too so I did some experiments and I realized that indeed
> > catamorphisms can be represented in such a way that they can be combined
> > together and all run in a single pass over a data structure. In fact, they
> > form an applicative functor.
> >
> > [1] http://www.haskell.org/haskellwiki/Attribute_grammar
> > [2] Utrecht University Attribute Grammar Compiler
> >
> > To give an example, let's say we want to compute the average value of a
> > binary tree. If we compute a sum first and then count the elements, the
> > whole tree is retained in memory (and moreover, deforestation won't happen).
> > So it's desirable to compute both values at once during a single pass:
> >
> > -- Count nodes in a tree.
> > count' :: (Num i) => CataBase (BinTree a) i
> > count' = ...
> >
> > -- Sums all nodes in a tree.
> > sum' :: (Num n) => CataBase (BinTree n) n
> > sum' = ...
> >
> > -- Computes the average value of a tree.
> > avg' :: (Fractional b) => CataBase (BinTree b) b
> > avg' = (/) <\$> sum' <*> count'
> >
> > Then we can compute the average in a single pass like
> >
> >     runHylo avg' treeAnamorphism seed
> >
> > My experiments together with the example are available at
> > https://github.com/ppetr/recursion-attributes
> >
> > I wonder, is there an existing library that expresses this idea?
> >
> >   Best regards,
> >   Petr Pudlak
> >
> >
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
```
27 Jan 2013 09:40

### Re: catamorphisms and attribute grammars

Hi Chris,

thanks for insightful links. At the first glance, I think the main difference is that machines and iteratees process streams of data, while catamorphisms work on general recursive data structures. (I used "count" + "sum" in the example, which could lead to the impression that it's list oriented.)

However, it seems to me that there is some connection between cata/anamorphisms and free (co)monads generated by a functor. I'm just guessing - perhaps using such a monad in a monadic pipe would lead to a similar result?

BTW, while it seems that using existentials in by Cata data type is natural, I'd like to know if I could do it without them. If you have any ideas, please let me know.

Best  regards,
Petr

PS: Is there actually anything left that ekmett hasn't implemented?

2013/1/27 Chris Wong
Hi Petr,

Congratulations -- you've just implemented a Moore machine! [1]

I posted something very much like this just last year [2]. It's a very
common pattern in Haskell, forming the basis of coroutines and
iteratees and many other things.

Edward Kmett includes it in his machines package [3]. His variation,
like mine, hides the state inside a closure, removing the need for
existentials. pipes 2.0 contains one implemented as a free monad [4].

[1] http://en.wikipedia.org/wiki/Moore_machine
[2] http://hackage.haskell.org/packages/archive/machines/0.2.3/doc/html/Data-Machine-Moore.html
[3] http://www.haskell.org/pipermail/haskell-cafe/2012-May/101460.html
[4] http://hackage.haskell.org/packages/archive/pipes/2.0.0/doc/html/Control-Pipe-Common.html

Chris

On Sun, Jan 27, 2013 at 11:03 AM, Petr P <petr.mvd <at> gmail.com> wrote:
>   Dear Haskellers,
>
> I read some stuff about attribute grammars recently [1] and how UUAGC [2]
> can be used for code generation. I felt like this should be possible inside
> Haskell too so I did some experiments and I realized that indeed
> catamorphisms can be represented in such a way that they can be combined
> together and all run in a single pass over a data structure. In fact, they
> form an applicative functor.
>
> [1] http://www.haskell.org/haskellwiki/Attribute_grammar
> [2] Utrecht University Attribute Grammar Compiler
>
> To give an example, let's say we want to compute the average value of a
> binary tree. If we compute a sum first and then count the elements, the
> whole tree is retained in memory (and moreover, deforestation won't happen).
> So it's desirable to compute both values at once during a single pass:
>
> -- Count nodes in a tree.
> count' :: (Num i) => CataBase (BinTree a) i
> count' = ...
>
> -- Sums all nodes in a tree.
> sum' :: (Num n) => CataBase (BinTree n) n
> sum' = ...
>
> -- Computes the average value of a tree.
> avg' :: (Fractional b) => CataBase (BinTree b) b
> avg' = (/) <\$> sum' <*> count'
>
> Then we can compute the average in a single pass like
>
>     runHylo avg' treeAnamorphism seed
>
> My experiments together with the example are available at
> https://github.com/ppetr/recursion-attributes
>
> I wonder, is there an existing library that expresses this idea?
>
>   Best regards,
>   Petr Pudlak
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

```_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
```
27 Jan 2013 21:12

### Re: catamorphisms and attribute grammars

You have applied the so-called banana-split theorem, as described e.g. in http://www.cs.ox.ac.uk/jeremy.gibbons/publications/acmmpc-calcfp.pdf

Indeed you are right in noticing the correspondence between AG's and catamorphims; actually I see AG's as a domain specific language for constructing algebras.

Since we  believe in embedded domain specific languages we have developed a library for constructing attribute grammars in Haskell, which is described in our ICFP paper:

<at> inproceedings{1596586,
Address = {New York, NY, USA},
Author = {Viera, Marcos and Swierstra, S. Doaitse and Swierstra, Wouter},
Booktitle = {ICFP '09: Proceedings of the 14th ACM SIGPLAN international conference on Functional programming},
Date-Added = {2009-10-05 22:06:26 +0200},
Date-Modified = {2009-10-05 22:06:26 +0200},
Isbn = {978-1-60558-332-7},
Location = {Edinburgh, Scotland},
Pages = {245--256},
Publisher = {ACM},
Title = {Attribute grammars fly first-class: how to do aspect oriented programming in Haskell},
Year = {2009}}

where you will find the problem you are solving done using the library.

On March 8 2013 Marcos Viera hopes to defend his Ph.D. thesis at Utrecht University. His thesis contains the progress we have made in this area in recent years. You can find it at the bottom op the page; amongst others you can use the UUAGC nowadays to generate this code form uuagc input.

Doaitse Swierstra

On Jan 26, 2013, at 23:03 , Petr P <petr.mvd <at> gmail.com> wrote:

Dear Haskellers,

I read some stuff about attribute grammars recently [1] and how UUAGC [2] can be used for code generation. I felt like this should be possible inside Haskell too so I did some experiments and I realized that indeed catamorphisms can be represented in such a way that they can be combined together and all run in a single pass over a data structure. In fact, they form an applicative functor.

[1] http://www.haskell.org/haskellwiki/Attribute_grammar
[2] Utrecht University Attribute Grammar Compiler

To give an example, let's say we want to compute the average value of a binary tree. If we compute a sum first and then count the elements, the whole tree is retained in memory (and moreover, deforestation won't happen). So it's desirable to compute both values at once during a single pass:

-- Count nodes in a tree.
count' :: (Num i) => CataBase (BinTree a) i
count' = ...

-- Sums all nodes in a tree.
sum' :: (Num n) => CataBase (BinTree n) n
sum' = ...

-- Computes the average value of a tree.
avg' :: (Fractional b) => CataBase (BinTree b) b
avg' = (/) <\$> sum' <*> count'

Then we can compute the average in a single pass like

runHylo avg' treeAnamorphism seed

My experiments together with the example are available at https://github.com/ppetr/recursion-attributes

I wonder, is there an existing library that expresses this idea?

Best regards,
Petr Pudlak

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

```_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
```
28 Jan 2013 12:05

### Re: catamorphisms and attribute grammars

```Patrick Bahr does something very similar in Modular Tree Automata [1],
also noting the relation to attribute grammars. It's implemented in the
compdata package [2].

[1] Patrick Bahr, Modular Tree Automata (MPC 2012),
http://dx.doi.org/10.1007/978-3-642-31113-0_14
[2] http://hackage.haskell.org/package/compdata

/ Emil

2013-01-26 23:03, Petr P skrev:
>    Dear Haskellers,
>
> I read some stuff about attribute grammars recently [1] and how UUAGC
> [2] can be used for code generation. I felt like this should be possible
> inside Haskell too so I did some experiments and I realized that indeed
> catamorphisms can be represented in such a way that they can be combined
> together and all run in a single pass over a data structure. In fact,
> they form an applicative functor.
>
> [1] http://www.haskell.org/haskellwiki/Attribute_grammar
> [2] Utrecht University Attribute Grammar Compiler
>
> To give an example, let's say we want to compute the average value of a
> binary tree. If we compute a sum first and then count the elements, the
> whole tree is retained in memory (and moreover, deforestation won't
> happen). So it's desirable to compute both values at once during a
> single pass:
>
> -- Count nodes in a tree.
> count' :: (Num i) => CataBase (BinTree a) i
> count' = ...
>
> -- Sums all nodes in a tree.
> sum' :: (Num n) => CataBase (BinTree n) n
> sum' = ...
>
> -- Computes the average value of a tree.
> avg' :: (Fractional b) => CataBase (BinTree b) b
> avg' = (/) <\$> sum' <*> count'
>
> Then we can compute the average in a single pass like
>
> runHylo avg' treeAnamorphism seed
>
> My experiments together with the example are available
> at https://github.com/ppetr/recursion-attributes
>
> I wonder, is there an existing library that expresses this idea?
>
>    Best regards,
>    Petr Pudlak
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
```

Gmane