[Haskell-cafe] catamorphisms and attribute grammars

[Doaitse Swierstra]

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:


@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},
	Doi = {http://doi.acm.org/10.1145/1596550.1596586},
	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.

http://www.cs.uu.nl/wiki/bin/view/Center/PhDs

 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130127/4ebc9bff/attachment.htm>