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 which 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 know and practice 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 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)]
            )
            ;

The full source code can be viewed here. This is part of the Spirit distribution.

Boost style FP

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

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 bind.cpp.

    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;
    };

The full source code can be viewed here. This is part of the Spirit distribution.

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. In the future, 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:

    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])
        ;

The full source code can be viewed here. This is part of the Spirit distribution.

You do not have to worry about the details for now. There is a lot going on here that needs to be explained. The succeeding chapters will be enlightening.

Notice the use of lambda expressions such as:

    expression.val += arg1

Lambda Expressions? Lambda expressions are actually unnamed partially applied functions where placeholders (e.g. arg1, arg2) are provided in place of some of the arguments. The reason this is called a lambda expression is that traditionally, such placeholders are written using the Greek letter lambda .

where expression.val is a closure variable of the expression rule (see Closures). arg1 is a placeholder for the first argument that the semantic action will receive (see Phoenix Place-holders). In Boost.Lambda (BLL), this corresponds to _1.

Copyright © 1998-2003 Joel de Guzman

Use, modification and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)