Mar 06

Attributes: Functional vs. Side-effects

By Joel de Guzman Add comments

We (the spirit developers) are obviously advocates of FP (functional programming). We use as much FP as we can in the design of Spirit. Spirit is essentially a parser-combinator library in the likes of Haskell parser libraries such as Parsec. The similarities end however in how we deal with imperative constructs that are taboos in the FP world. We are in C++ after all, and we are not FP purists. We still embrace side-effects and all these “warts” whenever reasonable. Frank Dellaert has this to say in the Spirit list:

Hmmm. It seems there are two ways to use spirit: the “functional” way, and the “side-effect” way. I very much like the functional way, but this little exception breaks it (are there others?). Seems that if there are many questions about this, it also breaks the user’s model of how the parser works.

I think the copying and swapping is only a problem if the caller provided a reference, right? Otherwise you could allocate the attribute on the heap and just swap the pointers, internally? You could even get rid of the user-supplied reference altogether (spirit 3?) by returning a boost::optional instead of bool. If they want to use imperative style, users can always use semantic actions.

Here’s my reply:

We’ve deliberated long and hard on whether to (always) return/synthesize an attribute or pass it in by reference. You know now that we’ve chosen the “side-effect” path, for good reasons. Foremost is efficiency. Passing in an empty container for the parser to fill-in (“build” or “compile” if you will) was deemed more efficient than returning the attribute, especially if we are dealing with large objects; say a humongous AST. At the time, we didn’t have move semantics (it was in the horizon when V2 was being designed, but we don’t want to rely on future language features) — big objects are often containers or have containers. There’s also the issue of type deduction. Consider this expression:

double_ >> double_

what is its (synthesized) attribute? It’s a tuple<double, double> of course. But the expression alone does not allow you to specify the exact type that you want; e.g. std::complex. Say we want to compose this into:

*(double_ >> double)

now what is its type? Without any hints, we can only give you a generic type: std::vector<tuple<double, double> >; even if what you really want is std::list<std::complex>, say, or MyComplexVec.

You might be tempted to use semantic action and make its return type the attribute, e.g.:

(double_ >> double)[make_complex(_1, _2)]

but then you have to sprinkle *all* your nodes with SAs making your grammar unwieldy (SAs also have a tendency of polluting a grammar with imperative code and semantics which stifle generic reuse).

Then, adding MyComplexVec, we will have:

*((double_ >> double)[make_complex(_1, _2)])[make_MyComplexVec(_1)]

This, IMO, is ugly code -something I dislike with pure attribute grammars. It can and should be simply:

 *(double_ >> double)

Clear and decoration free! ..and let the library deduce the attribute in different ways:

parse(..., my_complex_vec)


parse(..., std_list_of_double_pairs)

such is the beauty of generic programming.

Frank Dellaert

One Response to “Attributes: Functional vs. Side-effects”

  1. anders li says:

    let’s think about GCC4.x. It implements LL(2) parser manually in the front end.Within the parsing, it embeds lots of semantic actions to form its tailored huge AST (GENERIC TREE in gcc). I think for such a large and complex gcc AST, how could we define the AST and make the productions as simple as the above example(double_ >> double_) and just use parse_phrase(…, gcc_AST) to fill the monster AST. If change the GCC front end to use spirit, I think SAs are the right choice. Of cause for such a simple example above, SA is not so necessary.

Leave a Reply

preload preload preload