Functional

If you look more closely, you'll notice that Spirit is all about composition of parser functions. A parser is just a function that accepts a scanner and returns a match. Parser functions are composed to form increasingly complex higher order forms. Notice too that the parser, albeit an object, is immutable and constant. All primitive and composite parser objects are const. The parse member function is even declared as const:

    template <typename ScannerT>
    typename parser_result<self_t, ScannerT>::type
    parse(ScannerT const& scan) const;

In all accounts, this looks and feels a lot like Functional Programming. And indeed it is. Spirit is by all means an application of Functional programming in the imperative C++ domain. In Haskell, for example, there is what are called parser combinators which are strikingly similar to the approach taken by Spirit- parser functions are composed using various operators to create higher order parser functions that model a top-down recursive descent parser. Those smart Haskell folks have been doing this way before Spirit.

Functional style programming (or FP) libraries are gaining momentum in the C++ community. Certainly, we'll see more of FP in Spirit now and in the future. Actually, if one looks more closely, even the C++ standard library has an FP flavor. stealthily beneath the core of the standard C++ library, a closer look into STL gives us a glimpse of a truly FP paradigm already in place. It is obvious that the authors of STL knows and practices FP.

Semantic Actions in the FP Perspective

STL style FP

A more obvious application of STL-style FP in Spirit is the semantic action. What is STL-style FP? It is primarily the use of functors that can be composed to form higher order functors.

Functors

A Function Object, or Functor is simply any object that can be called as if it is a function. An ordinary function is a function object, and so is a function pointer; more generally, so is an object of a class that defines operator().

This STL-style FP can be seen everywhere these days. The following example is taken from SGI's Standard Template Library Programmer's Guide:

    //  Computes sin(x)/(x + DBL_MIN) for each element of a range.

    transform(first, last, first,
              compose2(divides<double>(),
                       ptr_fun(sin),
                       bind2nd(plus<double>(), DBL_MIN)));

Really, this is just currying in FP terminology.

Currying

What is "currying", and where does it come from?

Currying has its origins in the mathematical study of functions. It was observed by Frege in 1893 that it suffices to restrict attention to functions of a single argument. For example, for any two parameter function f(x,y), there is a one parameter function f' such that f'(x) is a function that can be applied to y to give (f'(x))(y) = f (x,y). This corresponds to the well known fact that the sets (AxB -> C) and (A -> (B -> C)) are isomorphic, where "x" is cartesian product and "->" is function space. In functional programming, function application is denoted by juxtaposition, and assumed to associate to the left, so that the equation above becomes f' x y = f(x,y).

In the context of Spirit, the same FP style functor composition may be applied to semantic actions. full_calc.cpp in the libs/example/fundamental/calc folder is a good example. Here's a snippet from that sample:

    expression =
        term
        >> *(   ('+' >> term)[make_op(plus<long>(), self.eval)]
            |   ('-' >> term)[make_op(minus<long>(), self.eval)]
            )
            ;

Boost style FP

Boost takes the FP paradigm further. There are libraries in boost that focus specifically on Function objects and higher-order programming.

Boost FP libraries
bind and mem_fn Generalized binders for function/object/pointers and member functions, from Peter Dimov
compose Functional composition adapters for the STL, from Nicolai Josuttis
function Function object wrappers for deferred calls or callbacks, from Doug Gregor
functional Enhanced function object adaptors, from Mark Rodgers
lambda Define small unnamed function objects at the actual call site, and more, from Jaakko Järvi and Gary Powell
ref A utility library for passing references to generic functions, from Jaako Järvi, Peter Dimov, Doug Gregor, and Dave Abrahams

The following is an example that uses boost Bind to use a member function as a Spirit semantic action. You can see this example in full in the file spirit_bind.cpp in the libs/example/fundamental/ directory.

    class list_parser
    {
    public:

        typedef list_parser self_t;

        bool
        parse(char const* str)
        {
            return spirit::parse(str,

                //  Begin grammar
                (
                    real_p
                    [
                        bind(&self_t::add, this, _1)
                    ]

                    >> *(   ','
                            >>  real_p
                                [
                                    bind(&self_t::add, this, _1)
                                ]
                        )
                )
                ,
                //  End grammar

                space_p).full;
        }

        void
        add(double n)
        {
            v.push_back(n);
        }

        vector<double> v;
    };

This parser parses a comma separated list of real numbers and stores them in a vector<double>. Boost.bind creates a Spirit conforming semantic action from the list_parser's member function add.

Lambda and Phoenix

There's a library, authored by yours truly, named Phoenix. While this is not officially part of the Spirit distribution, this library has been used extensively to experiment on advanced FP techniques in C++. This library is highly influenced by FC++ and boost Lambda (BLL).

BLL

In as much as Phoenix is influenced by boost Lambda (BLL), Phoenix innovations such as local variables, local functions and adaptable closures, in turn influenced BLL. Currently, BLL is very similar to Phoenix. Most importantly, BLL incorporated Phoenix's adaptable closures. Immediately after the release of Spirit v1.5.0, Spirit will fully support BLL.

Phoenix allows one to write semantic actions inline in C++ through lambda (an unnamed function) expressions. Here's a snippet from the phoenix_calc.cpp example (also found in the libs/example/fundamental/calc folder):

    expression
        =   term[expression.val = arg1]
            >> *(   ('+' >> term[expression.val += arg1])
                |   ('-' >> term[expression.val -= arg1])
                )
        ;

    term
        =   factor[term.val = arg1]
            >> *(   ('*' >> factor[term.val *= arg1])
                |   ('/' >> factor[term.val /= arg1])
                )
        ;

    factor
        =   ureal_p[factor.val = arg1]
        |   '(' >> expression[factor.val = arg1] >> ')'
        |   ('-' >> factor[factor.val = -arg1])
        |   ('+' >> factor[factor.val = arg1])
        ;

Notice the use of lambda expressions such as:

    expression.val += arg1

where expression.val is a closure variable of the expression rule (see Closures).