View source for The Monad.Reader/Issue4/Why Attribute Grammars Matter

=Why Attribute Grammars Matter=
:''by Wouter Swierstra for The Monad.Reader Issue Four''; 01-07-05

==Introduction==
Almost twenty years have passed since John Hughes influential paper [http://www.math.chalmers.se/~rjmh/Papers/whyfp.html Why Functional Programming Matters]. At the same time the first work on
attribute grammars and their relation to functional programming
appeared. Despite the growing popularity of functional programming,
attribute grammars remain remarkably less renown.

The purpose of this article is twofold. On the one hand it illustrates how
functional programming sometimes scales poorly and how
attribute grammars can remedy these problems. On the other hand it aims to
provide a gentle introduction to attribute grammars for seasoned functional
programmers.

==The problem==
John Hughes argues that with the increasing complexity of modern
software systems, modularity has become of paramount importance to software
development. Functional languages provide new kinds of ''glue'' that create
new opportunities for more modular code. In particular, Hughes stresses
the importance of higher-order functions and lazy evaluation. There are
plenty of examples where this works nicely - yet situations arise where
the glue that functional programming provides somehow isn't quite enough.

Perhaps a small example is in order. Suppose we want to write a function
<tt>diff :: [Float] -> [Float]</tt> that given a list <tt>xs</tt>, calculates a new list where every element <tt>x</tt> is replaced with the difference between <tt>x</tt> and the
average of <tt>xs</tt>. Similar problems pop up in any library for performing
statistical calculations.

===Higher-order functions===
Let's tackle the problem with some of Haskell's most powerful glue - higher-order functions. Any beginning Haskell programmer should be able to concoct the solution presented in Listing One. The average is computed using functions from the Prelude. The obvious function using this average is then mapped over the original list. So far, so good.

<haskell>
--- Listing One ---

diff :: [Float] -> [Float]
diff xs = map (\x -> x - (avg xs)) xs

avg :: [Float] -> Float
avg xs = sum xs / genericLength xs
</haskell>

There are, however, a few things swept under the rug in this example. First
of all, this simple problem requires three traversals of the original
list. Computing additional values from the original list will require even
more traversals.

Secondly, the solution is so concise because it depends on Prelude
functions. If the values were stored in a slightly different data structure,
the solution would require a lot of tedious work. We could, of course,
define our own higher-order functions, such as <tt>map</tt> and <tt>fold</tt>, or even
resort to generic programming. There are, however,
more ways to skin this particular cat.

This problem illustrates the sheer elegance of functional programming. We
do pay a price for the succinctness of the solution. Multiple traversals
and boilerplate code can both be quite a head-ache. If we want to perform
complex computations over custom data structures, we may want to consider an
alternative approach.

Fortunately, as experienced functional programmers, we have another card up
our sleeve.

===Lazy evaluation===
The second kind of glue that functional programming provides is lazy
evaluation. In essence, lazy evaluation only evaluates expressions when
they become absolutely necessary.

In particular, lazy evaluation enables the definition of ''circular programs'' that bear a dangerous resemblance to undefined values. Circular
programs tuple separate computations, relying on lazy evaluation to feed
the results of one computation to another.

In our example, we could simply compute the length and sum of the list at
the same time:

<haskell>
average :: [Float] -> Float
average xs = let
 nil = (0.0, 0.0)
 cons x (s,l) = (x + s, 1.0 + l)
 (sum,length) = foldr cons nil xs
 in sum / length
</haskell>

We can eliminate traversals by tupling computations! Can we compute the
resulting list at the same time as computing the sum and length? Let's try:

<haskell>
diff :: [Float] -> [Float]
diff xs = let
 nil = (0.0, 0.0, [])
 cons x (s,l,rs) = (x+s, 1.0+l, (x - ....) : rs)
 (sum,length,res) = foldr cons nil xs
 in res
</haskell>

We run into trouble when we try to use the average to construct the
resulting list. The problem is, that we haven't computed the average, but
somehow want to use it during the traversal. To solve this, we don't actually
compute the resulting list, but rather compute a function taking the
average to the resulting list:

<haskell>
diff :: [Float] -> [Float]
diff xs =
 let
  nil = (0.0, 0.0, \avg -> [])
  cons x (s,l,rs) = (x+s, 1.0+l, \avg -> (x - avg) : rs avg)
  (sum,length,res) = foldr cons nil xs
 in
  res (sum / length)
</haskell>

We can generalize this idea a bit further. Suppose that we want to compute
other values that use the average. We could just add an <tt>avg</tt> argument to
every element of the tuple that needs the average. It is a bit nicer,
however, to lift the <tt>avg</tt> argument outside the tuple. Our final listing
now becomes:

<haskell>
--- Listing Two ---

diff :: [Float] -> [Float]
diff xs =
 let
  nil avg = (0.0, 0.0, [])
  cons x fs avg =
   let
    (s,l,ds) = fs avg
   in
    (s+x,l+1.0,x-avg : ds)
  (sum,length,ds) = foldr cons nil xs (sum / length)
 in
  ds
</haskell>

Now every element of the tuple can refer to the average, rather than just
the final list.

This ''credit card transformation'' eliminates multiple traversals by
tupling computations. We use the average without worrying if we have
actually managed to compute it. When we actually write the fold, however,
we have to put our average where our mouth is. Fortunately, the <tt>sum</tt> and
<tt>length</tt> don't depend on the average, so we are free to use these values to
tie the recursive knot.

The code in Listing Two only needs a single traversal and one
higher-order function. It apparently solves the problems with the code in
Listing One.

Hold on a minute. What ever happened to the elegance of our previous
solution? Our second solution appears to have sacrificed clarity for the
sake of efficiency. Who in their right minds would want to write the code
in Listing Two? I wouldn't. Maybe, just maybe, we can do a bit better.

==Attribute Grammars==
Before even explaining what an attribute grammar is, think back to when you
first learned about ''folds''. Initially, a fold seems like a silly
abstraction. Why should I bother writing simple functions as folds? After
all, I already know how to write the straightforward solution. It's only
after a great deal of experience with functional programming that you learn
to recognize folds as actually being a worthwhile abstraction. Learning
about attribute grammars is similar in more ways than one.

So what are attribute grammars? I'll have a bit more to say about that
later. For now, let's see what the attribute grammar solution to our
running example looks like.

===The attribute grammar solution===
I'll introduce attribute grammars using the syntax of the [http://www.cs.uu.nl/wiki/bin/view/HUT/AttributeGrammarSystem Utrecht University Attribute Grammar] system or UUAG for short. The UUAG system takes a file
containing an attribute grammar definition and generates a Haskell module
containing ''semantic functions'', determined by the attribute grammar. The
attribute grammar determines a computation over some data structure; the
semantic functions correspond to the actual Haskell functions that perform
the computation.

Although the UUAG system's syntax closely resembles Haskell, it is
important to realize that the UUAG system is a Haskell pre-processor and
not a complete Haskell compiler.

So what does an attribute grammar file look like? Well, first of all we
have to declare the data structure we're working with. In our example, we
simply have a list of Floats.

<haskell>
--- Listing Three ---

DATA Root
 | Root list : List
DATA List
 | Nil
 | Cons head : Float tail : List
</haskell>

Datatypes are declared with the keyword <tt>DATA</tt>, followed by a list of
constructors. Every node explicitly gives the name and type of all its
children. In our example we have an empty list <tt>Nil</tt> and a list constructor
<tt>Cons</tt> with two children, <tt>head</tt> and <tt>tail</tt>. For reasons that will become
apparent later on, we add an additional datatype corresponding to the root
of our list.

So now that we've declared our datatype, let's add some ''attributes''. If we
want to compute the average element, we'll need the length of the
list. Listing Four introduces our first attribute corresponding to
a list's length.

<haskell>
--- Listing Four ---

ATTR List [|| length : Float]
SEM List
 | Nil lhs.length = 0.0
 | Cons lhs.length = 1.0 + @tail.length
</haskell>

Let's go over the code line by line.

An attribute has to be declared before it can actually be defined. An
attribute is declared using the <tt>ATTR</tt> statement. This example declares a
single ''synthesized'' attribute called <tt>length</tt> of type <tt>Float</tt>. A
synthesized attribute is typically a value you are trying to compute bottom
up. Synthesized attributes are declared to the right of the second
vertical bar. We'll see other kinds of attributes shortly.

Now that we've declared our first attribute, we can actually define it. A
<tt>SEM</tt> statement begins by declaring for which data type attributes are
being defined. In our example we want to define an attribute on a <tt>List</tt>,
hence we write <tt>SEM List</tt>. We can subsequently give attribute definitions
for the constructors of our <tt>List</tt> data type.

Every attribute definition consists of several parts. We begin by
mentioning the constructor for which we define an attribute. In our example
we give two definitions, one for <tt>Nil</tt> and one for <tt>Cons</tt>.

The second part of the attribute definition describes which attribute is
being defined. In our example we define the attribute <tt>length</tt> for the
''left-hand side'', or <tt>lhs</tt>. A lot of the terminology associated with
attribute grammars comes from the world of context-free grammars. As this
tutorial focuses on functional programmers, rather than formal language
gurus, feel free to read <tt>lhs</tt> as "parent node". It seems a bit odd to
write <tt>lhs.length</tt> explicitly, but we'll see later on why merely writing
<tt>length</tt> doesn't suffice.

Basically, all we've only said that the two definitions define the <tt>length</tt>
of <tt>Nil</tt> and <tt>Cons</tt>. We still have to fill in the necessary definition. The
actual definition of the attributes takes place to the right of the equals
sign. Programmers are free to write any valid Haskell expression. In fact,
the UUAG system does not analyse the attribute definitions at all, but merely
copies them straight into the resulting Haskell module. In our example, we
want the length of the empty list to be <tt>0.0</tt>. The case for <tt>Cons</tt> is a bit
trickier.

In the <tt>Cons</tt> case we want to increment the length computed so far. To
do so we need to be able to refer to other attributes. In particular we
want to refer to the <tt>length</tt> attribute of the tail. The expression
<tt>@tail.length</tt> does just that. In general, you're free to refer to any
synthesized attribute ''attr'' of a child node ''c'' by writing <tt>@c.attr</tt>.

The <tt>length</tt> attribute can be depicted pictorally as follows:

[[Image:WAGM-Avg.png|The length attribute]]

'''Exercise:''' Declare and define a synthesized attribute <tt>sum</tt> that
computes the sum of a <tt>List</tt>. You can refer to a value <tt>val</tt> stored at a node as <tt>@val</tt>. For instance, write <tt>@head</tt> to refer to the float stored in a <tt>Cons</tt> node. Draw the corresponding picture if you're stuck.

Now we've defined <tt>length</tt> and <tt>sum</tt>, let's compute the average. We'll know the sum and the length of the entire list at the Root node. Using those attributes we can compute the average and ''broadcast'' the average through the rest of the list. Let's start with the picture this time:

[[Image:WAGM-Length.png|The average attribute]]

The previous synthesized attributes, <tt>length</tt> and <tt>sum</tt>, defined bottom-up
computations. We're now in the situation, however, where we want to pass
information through the tree from a parent node to its child nodes using an
''inherited'' attribute. Listing Five defines an inherited attribute <tt>avg</tt>
that corresponds to the picture we just drew.

<haskell>
--- Listing Five ---
ATTR List [ avg : Float|| ]
SEM Root
 | Root list.avg = @list.sum / @list.length

SEM List
 | Cons tail.avg = @lhs.avg

</haskell>

Inherited attributes are declared to the left of the two vertical
bars. Once we've declared an inherited attribute <tt>avg</tt> on lists, we're
obliged to define how every constructor passes an <tt>avg</tt> to its children of
type <tt>List</tt>.

In our example, there are only two constructors with children
of type <tt>List</tt>, namely <tt>Root</tt> and <tt>Cons</tt>. At the <tt>Root</tt> we compute the
average, using the synthesized attributes <tt>sum</tt> and <tt>length</tt>, and pass the
result to the <tt>list</tt> child. At the <tt>Cons</tt> node, we merely copy down the
<tt>avg</tt> we received from our parent. Analogous to synthesized attributes, we
can refer to an inherited attribute <tt>attr</tt> by writing <tt>@lhs.attr</tt>.

Admittedly, this inherited attribute is not terribly interesting. There are
plenty of other examples, however, where an inherited attribute represents
important contextual information. Think of passing around the set of
assumptions when writing a type checker, for instance.

'''Exercise:''' To complete the attribute grammar, define an attribute
<tt>res</tt> that computes the resulting list. Should it be inherited or
synthesized? You may want to draw a picture.

===Running the UUAG===
Now suppose you've completed the exercises and copied the examples in a
single file called <tt>Diff.ag</tt>. How do we actually use the attribute grammar?
This is were the UUAG compiler steps in. Running the UUAG compiler on the
source attribute grammar file generates a new <tt>Diff.hs</tt> file, which we can
then compile like any other Haskell file.

<haskell>
> uuagc -a Diff.ag
> ghci Diff.hs
</haskell>

The <tt>Diff.hs</tt> file contains several ingredients.

Firstly, new Haskell datatypes are generated corresponding to <tt>DATA</tt>
declarations in the attribute grammar. For every generated datatype a
corresponding <tt>fold</tt> is generated. The attribute definitions determine the
arguments passed to the folds. Browsing through the generated code can
actually be quite instructive.

Inherited attributes are passed to recursive calls of the fold. Synthesized
attributes are tupled and returned as the result of the computation. In
essence, we've reproduced our original solution in Listing Two - but now
without the hassle associated with spelling out [[catamorphism]]s with a higher
order domain and a compound codomain.

The attribute grammar solution is just as efficient as our earlier solution
relying on lazy evaluation, yet the code is hardly different from what we
would write in a straightforward Haskell solution. It really is the best of
both worlds. The two types of glue that John Hughes pinpoints in his
original article just aren't enough. I would like to think that sometimes
attribute grammars are sometimes capable of providing just the right
missing bit of glue.

===What are attribute grammars?===
So just what are attribute grammars? Well, that depends on who you ask,
really. I've tried to sum up some different views below.

Attribute grammars add semantics to a context free grammar. Although it is
easy enough to describe a language's syntax using a context free grammar,
accurately describing a language's semantics is notoriously
difficult. Attribute grammars specify a language's semantics by
'decorating' a context free grammar with those attributes you are interested
in.

Attribute grammars describe tree traversals. All imperative implementations
of attribute grammar systems perform tree traversals to compute some
value. Basically an attribute grammar declares ''which'' values to compute
and an attribute grammar system executes these computations. Once you've
made this observation, the close relation to functional programming should
not come as a surprise.

Attribute grammars are a formalism for writing catamorphisms in a
compositional fashion. Basically, the only thing the UUAG compiler does is
generate large folds that I couldn't be bothered writing myself. It takes
away all the elbow grease involved with maintaining and extending such
code. In a sense the compiler does absolutely nothing new; it just makes
life a lot easier.

Attribute grammars provide framework for aspect oriented programming in
functional languages. Lately there has been a lot of buzz about the
importance of ''aspects'' and ''aspect oriented programming''. Attribute
grammars provide a clear and well-established framework for splitting code
into separate aspects. By spreading attribute definitions over several
different files and grouping them according to aspect, attribute grammars
provide a natural setting for aspect oriented programming.

How do attribute grammars relate to other Haskell abstractions? I'll try to
put my finger on some of the more obvious connections, but I'm pretty sure
there's a great deal more that I don't cover here.

==What else is out there?==
Everyone loves monads. They're what makes IO possible in Haskell. There are
extensive standard libraries and syntactic sugar specifically designed to
make life with monads easier. There are an enormous number of Haskell
libraries based on the monadic interface. They represent one of the most
substantial developments of functional programming in the last decade.

Yet somehow, the single most common question asked by fledgling Haskell
programmers is probably ''What are monads?''. Beginners have a hard time
grasping the concept of monads and yet connoisseurs recognize a monad in
just about every code snippet. I think the more important question is:
''What are monads good for?''

Monads provide a simple yet powerful abstract notion of computation. In
essence, a monad describes how sequence computations. This is crucial in
order to perform IO in a functional language; by constraining all IO
actions to a single interface of sequenced computations, the programmer is
prevented from creating utter chaos. The real power of monads is in the
interface they provide.

John Hughes identified modularity as the single biggest blessing of
functional programming. The obvious question is: how modular is the monadic
interface? This really depends on you're definition of modularity. Let me
be more specific. How can you combine two arbitrary monads? You can't. This
is my greatest concern with monads. Once you choose your specific notion of
computation, you have to stick to it through thick and thin.

What about monad transformers? Monad transformers allow you to add a
specific monad's functionality on top of any existing monad. What seems
like a solution, more often than not, turns out to introduce more problems
than you bargained for. Adding new functionality to a monad involves
lifting all the computations from the previous monad to the new
one. Although I could learn to live with this, it gets even worse. As every
monad transformer really changes the underlying monad. The order in
which monad transformers are applied really makes a difference. If I want
to add error reporting and state to some existing monad, should I be forced
to consider the order in which I add them?

Monads are extremely worthwhile for the interface they provide. Monadic
libraries are great, but changing and extending monadic code can be a
pain. Can we do better? Well I probably wouldn't have started this monadic
intermezzo if I didn't have some sort of answer.

Let's start off with <tt>Reader</tt> monads, for instance. Essentially, <tt>Reader</tt>
monads adds an argument to some computation. Wait a minute, this reminds me
of inherited attributes. What about <tt>Writer</tt> monads? They correspond to
synthesized attributes of course. Finally, <tt>State</tt> monads correspond to
''chained'' attributes, or attributes that are both synthesized and
inherited. The real edge attribute grammars hold over monad transformers is that you
can define new attributes ''without'' worrying about the order in which you
define them or adapting existing code.

Do other abstractions capture other notions related to attribute grammars?
Of course they do! Just look at the function space arrows instance. The notion of
combining two distinct computations using the <tt>(&&&)</tt> operator relates to
the concept of ''joining'' two attribute grammars by collecting their
attribute definitions. When you look at the <tt>loop</tt> combinator, I can
only be grateful that an attribute grammar system deals with attribute
dependencies automatically.

There really is a lot of related work. Implicit parameters? Inherited attributes! Linear implicit parameters? Chained attributes! Concepts that are so natural in the setting of attribute grammars, yet seem contrived when added to Haskell. This strengthens my belief that functional programmers can really benefit from even the most fleeting experience with attribute grammars; although I'd like to think that if you've read this far, you're hungry for more.

==Further reading==
This more or less covers the tutorial section of this article. The best way
to learn more about attribute grammars is by actually using them. To conclude the tutorial, I've
included a small example for you to play with. I've written a parser for a very
simple wiki formatting language not entirely unlike the one used to produce this
document. So far the HTML generated after parsing a document is fairly poor. It's up to
you to improve it!

You can download the initial version here. Don't forget to install the [http://www.cs.uu.nl/wiki/bin/view/HUT/Download]. It might
be worthwhile to have a look at the [http://www.cs.uu.nl/wiki/bin/view/HUT/AttributeGrammarManual UUAG manual] as there's a lot of technical detail that I haven't mentioned.

If you're particularly daring, you may want to take a look at the [https://github.com/UU-ComputerScience/uhc Essential Haskell Compiler] being developed at Utrecht. It's almost completely written using the UUAG and is designed to be suitable for education and experimentation. The compiler was presented at the Summer School for Advanced Functional Programming in Tartu, Estonia last summer. As a result, there's a lot written about it already.

Dive on in!

[[Category:Article]]