A few final words on functional programming

The previous two installments of C++ for the self-taught were both about functional programming. Before we get back to Chausette, I’ll put in a few final words on the topic, combining both run-time functional programming with compile-time functional programming and, while we’re at it, language and meta-language design.

This is fun stuff, but if you want to understand everything I will talk about in this installment you’ll have a bit of studying to do. In the code I will present in this installment we will use:

  • symbol tables
  • parsers
  • expression templates
  • the Backus-Naur Form (BNF)
  • iterators
  • the Factory Method pattern


A few days ago, I received a message over Twitter by @pauldoo

I was already pondering what I might put in the “few final words on functional programming” post and I like to lend a helping hand when I can, so I decided to do just that when he sent me a follow-up E-mail.

Grammar & BNF

What he wanted to do is parse expressions in a lisp-y functional language. To do that, he had defined a simple grammar that, in BNF, would look a bit like this:

expression ::= ( list )
list       ::= list_item+
list_item  ::= STRING | DOUBLE | expression
To see the Aside click here.To hide the Aside click here.
BNF is the Backus-Naur Form. It is a standard way of writing up the grammar of a language

BNF consists of terminals, which are tokens, and non-terminals which are groups of tokens that, together, have a meaning. In this grammar, the terminals are ( and ) — the parenthesis characters — and the multi-character STRING and DOUBLE tokens. Strings are basically sequences of ASCII characters whereas doubles are what you would normally expect a C compiler to interpret as a floating-point constant.

The non-terminals in this grammar are list, which consists of one or more list_items; list_item, which is either a string, a double, or an expression, and expression, which is a list between parentheses.

Note that the grammar doesn’t tell you that the strings in the grammar are intended to be function names and the doubles are intended to be constants. In that sense, the language being described here is a lot like the original version of Funky.

When you want to write a parser for something, you first have to have a good grasp of two important things: the first is the grammar, which we’ve just discussed; the second is what the grammar means. In this case, what the grammar means is that we have some kind of operator — which is the first thing after the opening parenthesis — which is followed by whatever it operates on: a possibly-empty list of values and expressions. Those expressions could be recursively evaluated and the results of those evaluations used as values in the surrounding expression, such that (+ 1 (+ 1 1)) becomes equivalent to (+ 1 2) which in turn becomes equivalent to 3, so there is no need to treat expressions any differently from other values, where the surrounding expression is concerned.

That means that we can model the expression itself as follows:

struct Expression;
typedef variant< double, Expression > ListItem;
typedef vector< ListItem > List;
struct Expression
{
	Operator operator_;
	List list_;
};

That is: an expression consists of an operator and a list of operands. Each one of those operands is either a double or an Expression. While we’re at it, we might as well include strings and integers in the mix of possible operands — so as to make our new little language a bit more useful — and model a ListItem as typedef variant< int, double, string, Expression > ListItem;

Evaluating an expression

Now, evaluating an expression becomes a question of evaluating any sub-expressions until only values are left, and then applying the right operator to those values. This is typical of functional programming: recursion.

Let’s say we define four operators for now: plus, minus, multiply and divide. We also have three primitive types: integers, doubles and strings. That means we have up to twelve functions to implement – one for each combination of operator and type. We’ll only implement them if they make sense, though, so we won’t multiply or divide strings.

To see the Aside click here.To hide the Aside click here.
Note, by the way, that we don’t have expressions as “primitive types” here: by the time we will want to apply the operators to the operands, the sub-expressions will all have been evaluated.

The following chunk of code is rather long, but it does the evaluation of an expression:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
ListItem evaluate(Expression &expression)
{
	ListItemType result_type(int__);
	ListItem retval;
	// first pass: evaluate any sub-expressions
	for (List::iterator iter(expression.list_.begin()); iter != expression.list_.end(); ++iter)
	{
		if (iter->which() == expression__)
		{
			*iter = evaluate(get< Expression >(*iter));
		}
		switch (iter->which())
		{
		case int__ :
			// this is the default type - it doesn't change anything
			break;
		case double__ :
			if (result_type == int__)
			{
				result_type = double__;
			}
			else
			{ /* either already a double, or it's a string */ }
			break;
		case string__ :
			result_type = string__;
			break;
		default :
			throw logic_error("unexpected operand type");
		}
	}
	switch (result_type)
	{
	case int__ :
		// nothing to do in this case: this is the default for the variant, and it will be zero-initialized
		break;
	case double__ :
		retval = 0.0;
		break;
	case string__ :
		retval = string();
		break;
	default :
		throw logic_error("Unexpected result type");
	}
	boost::shared_ptr< Accumulator > accumulator = getAccumulator(retval, expression.operator_, result_type);
	for (List::const_iterator iter(expression.list_.begin()); iter != expression.list_.end(); ++iter)
	{
		(*accumulator)(*iter);
	}
 
	return retval;
}

In lines 6 through 31 of this code, all the sub-expressions are evaluated (lines 8 through 11) and the return type of the current expression is determined. Basically that determination goes like this: if all the operands are integers, the return type is an integer. If one or more of the operands is a double (and none are strings, so the operands are a mix of integers and doubles with at least done double), the return type is a double. If any of the operands is a string, the return type is a string.

In lines 32 to 45, the result value is initialized according to its determined type: either an integer zero, a floating-point zero or an empty string.

In line 46, we call a factory method to get the accumulator functor. We will look into that a little later.

In lines 47 through 50, the accumulator functor is called for every operands of the current operator. The result of this is transparently stored in retval, which is returned in line 52.

The Factory Method

The Factory Method is an often-used design pattern which allows you to implement a factory as a single function. In our case, we could have done this a bit more eloquently that I actually did — so feel free to optimize.

Here’s the code, including the Accumulator class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
struct Accumulator
{
	virtual ~Accumulator()
	{}
 
	virtual Accumulator* create(ListItem &result) const = 0;
 
	const Accumulator& operator()(const ListItem &list_item) const
	{
		call_(list_item);
		return *this;
	}
 
	ListItem operator*() const
	{
		return *result_;
	}
 
protected :
	virtual void call_(const ListItem &list_item) const = 0;
 
	Accumulator()
		: result_(0)
		, first_(true)
	{ /* no-op */ }
 
 
	Accumulator(ListItem &result)
		: result_(&result)
		, first_(true)
	{ /* no-op */ }
 
	ListItem *result_;
	mutable bool first_;
};
 
template < Operator operator_type__, ListItemType return_type__ >
struct Accumulator_ : Accumulator
{
private :
	Accumulator_()
	{ /* no-op */ }
 
	Accumulator_(ListItem &result)
		: Accumulator(result)
	{ /* no-op */ }
 
	Accumulator_* create(ListItem &result) const
	{
		return new Accumulator_(result);
	}
 
protected :
	/*virtual */void call_(const ListItem &list_item) const/* = 0*/
	{
		if (first_)
		{
			switch (result_->which())
			{
			case int__ :
				*result_ = cast< int__ >(list_item);
				break;
			case double__ :
				*result_ = cast< double__ >(list_item);
				break;
			case string__ :
				*result_ = cast< string__ >(list_item);
				break;
			}
			first_ = false;
		}
		else
		{
			*result_ = Operator_< operator_type__, return_type__ >::apply(*result_, list_item);
		}
	}
 
	friend boost::shared_ptr< Accumulator > getAccumulator(ListItem &result, Operator operator_type, ListItemType return_type);
};
 
boost::shared_ptr< Accumulator > getAccumulator(ListItem &result, Operator operator_type, ListItemType return_type)
{
	static Accumulator_< plus__, int__ >		pi_accumulator__;
	static Accumulator_< plus__, double__ >		pd_accumulator__;
	static Accumulator_< plus__, string__ >		ps_accumulator__;
	static Accumulator_< minus__, int__ >		mi_accumulator__;
	static Accumulator_< minus__, double__ >	md_accumulator__;
	static Accumulator_< minus__, string__ >	ms_accumulator__;
	static Accumulator_< multiply__, int__ >	ui_accumulator__;
	static Accumulator_< multiply__, double__ >	ud_accumulator__;
	static Accumulator_< divide__, int__ >		di_accumulator__;
	static Accumulator_< divide__, double__ >	dd_accumulator__;
	static Accumulator* accumulators__[operator_count__][list_item_type_count__] = {
		{ &pi_accumulator__, &pd_accumulator__, &ps_accumulator__, 0 },
		{ &mi_accumulator__, &md_accumulator__, &ms_accumulator__, 0 },
		{ &ui_accumulator__, &ud_accumulator__, 0, 0 },
		{ &di_accumulator__, &dd_accumulator__, 0, 0 }
	};
 
	if (accumulators__[operator_type][return_type] != 0)
	{
		return boost::shared_ptr< Accumulator >(accumulators__[operator_type][return_type]->create(result));
	}
	else
	{
		if (operator_type == multiply__)
		{
			throw logic_error("Don't know how to multiply a string");
		}
		else
		{
			throw logic_error("Don't know how to divide a string");
		}
	}
}

As you an see, there are ten static instances of accumulators inside the getAccumulator function. None of these is ever made available to a called, however, because none of them is capable of doing the job of an Accumulator. That’s because they don’t have a valid value in the result_ member, which they need to accumulate into.

The getAccumulator function assumes that it won’t be called for any non-existent operators or list-item types and that it won’t be called for divisions or multiplications of strings. It will attempt to diagnose the latter condition, but in any case it will throw a logic_error when it is called incorrectly.

Of course, what this really does is map a dynamic type to a static one: the ten instances are pointed to by an array of pointers, from which the appropriate one is taken according to the parameters passed to the function. That instance creates a new instance of its own type which, in turn, can be used as a real accumulator.

Traits and policies

Once we have a static type, we should no longer need to bother finding out what to do with the types we need. That means that we should now be able to use C++’s type system to find out how to implement a given operator for the types we’d been given earlier. We do that with a policy class, that looks like this:

template < Operator operator__, ListItemType return_type__ >
struct Operator_;

We will need a specialization for every valid combination of operator and return type, which means we need ten policies in total:

template <>
struct Operator_< plus__, int__ >;
template <>
struct Operator_< plus__, double__ >;
template <>
struct Operator_< plus__, string__ >;
template <>
struct Operator_< minus__, int__ >;
template <>
struct Operator_< minus__, double__ >;
template <>
struct Operator_< minus__, string__ >;
template <>
struct Operator_< divide__, int__ >;
template <>
struct Operator_< divide__, double__ >;
template <>
struct Operator_< multiply__, int__ >;
template <>
struct Operator_< multiply__, string__ >;

Each of these can assume that the left-hand-side operand is already of the right type, but may potentially have to cast the right-hand side — except for the ones that deal with integers, which always have integers on both sides. That means we need something to cast our variants — something that looks like this:

template < ListItemType target_list_item_type__ >
unspecified cast(const ListItem & list_item);

The caveat is, ofcourse, the “unspecified” bit: we need to tell the compiler which type cast will return for each ListItemType value. We can easily do that with a little meta-function:

template < ListItemType target_list_item_type__ >
struct get_cast_target_type;
template <>
struct get_cast_target_type< int__ >
{
	typedef int type;
};
template <>
struct get_cast_target_type< double__ >
{
	typedef double type;
};
template <>
struct get_cast_target_type< string__ >
{
	typedef string type;
};

This means that we can now declare the cast function as follows:

template < ListItemType target_list_item_type__ >
/*unspecified*/typename get_cast_target_type< target_list_item_type__ >::type cast(const ListItem & list_item);

and specialize it like this:

template < >
int cast< int__ >(const ListItem & list_item)
{
	assert(list_item.which() == int__);
	return get< int >(list_item);
}
template < >
double cast< double__ >(const ListItem & list_item)
{
	assert((list_item.which() == int__) || (list_item.which() == double__));
	if (list_item.which() == double__)
	{
		return get< double >(list_item);
	}
	else
	{
		return static_cast< double >(get< int >(list_item));
	}
}
template < >
string cast< string__ >(const ListItem & list_item)
{
	assert(list_item.which() != expression__);
	if (list_item.which() == string__)
	{
		return get< string >(list_item);
	}
	else if (list_item.which() == int__)
	{
		return lexical_cast< string >(get< int >(list_item));
	}
	else
	{
		assert(list_item.which() == double__);
		return lexical_cast< string >(get< double >(list_item));
	}
}

Writing the parser

Now that we know what we want to parse into — an expression — we can decide how to parse. We already have the grammar, so we can now try to express it in code.

Boost.Spirit is a template library that allows you to generate parsers from a BNF-like meta-language expressed in C++. It uses expression templates extensively to allow you to put BNF in your code and generate a parser from that code.

To see the Aside click here.To hide the Aside click here.

Let’s first have a closer look at the BNF we will want to express: it has changed a bit since the beginning of this post as we’re no longer looking strictly at what @pauldoo wanted to achieve with his grammar. The new grammar now looks a bit like this:

expression ::= ( OPERATOR list )
list       ::= list_item+
list_item  ::= expression
           | INTEGER
           | DOUBLE
           | STRING

An OPERATOR is one of the following characters: + - * /; and a STRING is a double quote, followed by zero or more escaped characters (\a, \b, \f, \n, \r, \t, \v, \\, \’, \”) or hex characters (\xHH where HH is a hexadecimal code) or characters that are not double quotes; followed by a double quote; an INTEGER is one or more numerical characters; and a DOUBLE is zero or more numerical characters followed by a dot followed by one or more numerical characters.

The fun thing with Boost.Spirit is that you can express something like this directly in code:

expression_ = '(' >> operator_ >> list_ >> ')'
            ;
operator_.add
            ("+", plus__)
            ("-", minus__)
            ("*", multiply__)
            ("/", divide__)
            ;
list_       = +list_item_
            ;
list_item_  = expression_
            | qi::int_
            | qi::double_
            | string_
            ;
string_     = lexeme['"' >> *(unescape_char_ | ("\\x" >> qi::hex) | (qi::char_ - qi::char_('"'))) >> '"']
            ;
unescape_char_.add
            ("\\a", '\a')("\\b", '\b')("\\f", '\f')("\\n", '\n')
            ("\\r", '\r')("\\t", '\t')("\\v", '\v')("\\\\", '\\')
            ("\\\'", '\'')("\\\"", '\"');

As you can see, Boost.Spirit must have overloaded a ton of operators to be able to do this. The point is, though, that with only very little additional boilerplate code (we have to declare the variables being used here) we have a working parser.

Note that both operator_ and unescape_char_ are symbol tables: they map a given character or string value to another value, possibly of a different type. Also note that each of these parsers provides an analogous structure as a result of its parse (if successful), so list_ yields a vector< ListItem >, a.k.a. a List; string_ yields a std::string, etc.

So, here’s all of the code of a parser and evaluator for the little language we’ve just designed: on IDEOne.com

Show codehide code

/* Copyright (c) 2011, Ronald Landheer-Cieslak <rlc at vlinder dot ca>
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the Vlinder Software nor the name of Ronald 
 *       Landheer-Cieslak names of its contributors may be used to endorse or 
 *       promote products derived from this software without specific prior 
 *       written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL RONALD LANDHEER-CIESLAK BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE
 */
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/spirit/include/phoenix_stl.hpp>
#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/fusion/include/io.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string/erase.hpp>
 
namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
using namespace std;
using namespace boost;
 
enum Operator {
	plus__,
	minus__,
	multiply__,
	divide__,
	operator_count__
};
 
enum ListItemType {
	int__,
	double__,
	string__,
	expression__,
	list_item_type_count__
};
 
struct Expression;
typedef variant< int, double, string, Expression > ListItem;
typedef vector< ListItem > List;
struct Expression
{
	Operator operator_;
	List list_;
};
BOOST_FUSION_ADAPT_STRUCT(
    Expression,
	(Operator, operator_)
	(List, list_)
)
 
template < ListItemType target_list_item_type__ >
struct get_cast_target_type;
template <>
struct get_cast_target_type< int__ >
{
	typedef int type;
};
template <>
struct get_cast_target_type< double__ >
{
	typedef double type;
};
template <>
struct get_cast_target_type< string__ >
{
	typedef string type;
};
 
template < ListItemType target_list_item_type__ >
/*unspecified*/typename get_cast_target_type< target_list_item_type__ >::type cast(const ListItem & list_item);
template < >
int cast< int__ >(const ListItem & list_item)
{
	assert(list_item.which() == int__);
	return get< int >(list_item);
}
template < >
double cast< double__ >(const ListItem & list_item)
{
	assert((list_item.which() == int__) || (list_item.which() == double__));
	if (list_item.which() == double__)
	{
		return get< double >(list_item);
	}
	else
	{
		return static_cast< double >(get< int >(list_item));
	}
}
template < >
string cast< string__ >(const ListItem & list_item)
{
	assert(list_item.which() != expression__);
	if (list_item.which() == string__)
	{
		return get< string >(list_item);
	}
	else if (list_item.which() == int__)
	{
		return lexical_cast< string >(get< int >(list_item));
	}
	else
	{
		assert(list_item.which() == double__);
		return lexical_cast< string >(get< double >(list_item));
	}
}
 
template < Operator operator__, ListItemType return_type__ >
struct Operator_;
 
template <>
struct Operator_< plus__, int__ >
{
	static ListItem apply(ListItem lhs, ListItem rhs)
	{
		assert(lhs.which() == int__);
		assert(rhs.which() == int__);
		get< int >(lhs) += get< int >(rhs);
		return lhs;
	}
};
 
template <>
struct Operator_< plus__, double__ >
{
	static ListItem apply(ListItem lhs, ListItem rhs)
	{
		get< double >(lhs) += cast< double__ >(rhs);
		return lhs;
	}
};
 
template <>
struct Operator_< plus__, string__ >
{
	static ListItem apply(ListItem lhs, ListItem rhs)
	{
		string r = cast< string__ >(rhs);
		string &l = get< string >(lhs);
		l.insert(l.end(), r.begin(), r.end());
		return lhs;
	}
};
 
template <>
struct Operator_< minus__, int__ >
{
	static ListItem apply(ListItem lhs, ListItem rhs)
	{
		assert(lhs.which() == int__);
		assert(rhs.which() == int__);
		get< int >(lhs) -= get< int >(rhs);
		return lhs;
	}
};
 
template <>
struct Operator_< minus__, double__ >
{
	static ListItem apply(ListItem lhs, ListItem rhs)
	{
		get< double >(lhs) -= get< double >(rhs);
		return lhs;
	}
};
 
template <>
struct Operator_< minus__, string__ >
{
	static ListItem apply(ListItem lhs, ListItem rhs)
	{
		using boost::algorithm::erase_first;
 
		string r = cast< string__ >(rhs);
		string &l = get< string >(lhs);
		erase_first(l, r);
		return lhs;
	}
};
 
template <>
struct Operator_< divide__, int__ >
{
	static ListItem apply(ListItem lhs, ListItem rhs)
	{
		assert(lhs.which() == int__);
		assert(rhs.which() == int__);
		get< int >(lhs) /= get< int >(rhs);
		return lhs;
	}
};
 
template <>
struct Operator_< divide__, double__ >
{
	static ListItem apply(ListItem lhs, ListItem rhs)
	{
		get< double >(lhs) /= cast< double__ >(rhs);
		return lhs;
	}
};
 
template <>
struct Operator_< multiply__, int__ >
{
	static ListItem apply(ListItem lhs, ListItem rhs)
	{
		assert(lhs.which() == int__);
		assert(rhs.which() == int__);
		get< int >(lhs) *= get< int >(rhs);
		return lhs;
	}
};
 
template <>
struct Operator_< multiply__, double__ >
{
	static ListItem apply(ListItem lhs, ListItem rhs)
	{
		get< double >(lhs) *= cast< double__ >(rhs);
		return lhs;
	}
};
 
struct Accumulator
{
	virtual ~Accumulator()
	{}
 
	virtual Accumulator* create(ListItem &result) const = 0;
 
	const Accumulator& operator()(const ListItem &list_item) const
	{
		call_(list_item);
		return *this;
	}
 
	ListItem operator*() const
	{
		return *result_;
	}
 
protected :
	virtual void call_(const ListItem &list_item) const = 0;
 
	Accumulator()
		: result_(0)
		, first_(true)
	{ /* no-op */ }
 
 
	Accumulator(ListItem &result)
		: result_(&result)
		, first_(true)
	{ /* no-op */ }
 
	ListItem *result_;
	mutable bool first_;
};
 
template < Operator operator_type__, ListItemType return_type__ >
struct Accumulator_ : Accumulator
{
private :
	Accumulator_()
	{ /* no-op */ }
 
	Accumulator_(ListItem &result)
		: Accumulator(result)
	{ /* no-op */ }
 
	Accumulator_* create(ListItem &result) const
	{
		return new Accumulator_(result);
	}
 
protected :
	/*virtual */void call_(const ListItem &list_item) const/* = 0*/
	{
		if (first_)
		{
			switch (result_->which())
			{
			case int__ :
				*result_ = cast< int__ >(list_item);
				break;
			case double__ :
				*result_ = cast< double__ >(list_item);
				break;
			case string__ :
				*result_ = cast< string__ >(list_item);
				break;
			}
			first_ = false;
		}
		else
		{
			*result_ = Operator_< operator_type__, return_type__ >::apply(*result_, list_item);
		}
	}
 
	friend boost::shared_ptr< Accumulator > getAccumulator(ListItem &result, Operator operator_type, ListItemType return_type);
};
 
boost::shared_ptr< Accumulator > getAccumulator(ListItem &result, Operator operator_type, ListItemType return_type)
{
	static Accumulator_< plus__, int__ >		pi_accumulator__;
	static Accumulator_< plus__, double__ >		pd_accumulator__;
	static Accumulator_< plus__, string__ >		ps_accumulator__;
	static Accumulator_< minus__, int__ >		mi_accumulator__;
	static Accumulator_< minus__, double__ >	md_accumulator__;
	static Accumulator_< minus__, string__ >	ms_accumulator__;
	static Accumulator_< multiply__, int__ >	ui_accumulator__;
	static Accumulator_< multiply__, double__ >	ud_accumulator__;
	static Accumulator_< divide__, int__ >		di_accumulator__;
	static Accumulator_< divide__, double__ >	dd_accumulator__;
	static Accumulator* accumulators__[operator_count__][list_item_type_count__] = {
		{ &pi_accumulator__, &pd_accumulator__, &ps_accumulator__, 0 },
		{ &mi_accumulator__, &md_accumulator__, &ms_accumulator__, 0 },
		{ &ui_accumulator__, &ud_accumulator__, 0, 0 },
		{ &di_accumulator__, &dd_accumulator__, 0, 0 }
	};
 
	if (accumulators__[operator_type][return_type] != 0)
	{
		return boost::shared_ptr< Accumulator >(accumulators__[operator_type][return_type]->create(result));
	}
	else
	{
		if (operator_type == multiply__)
		{
			throw logic_error("Don't know how to multiply a string");
		}
		else
		{
			throw logic_error("Don't know how to divide a string");
		}
	}
}
 
void ping()
{
	cout << "ping" << endl;
}
 
template < typename Iterator >
struct Grammar : qi::grammar< Iterator, Expression(), ascii::space_type >
{
	Grammar()
		: Grammar::base_type(expression_)
	{
		using qi::_val;
		using qi::_1;
		using phoenix::push_back;
		using qi::lexeme;
 
		expression_ = '(' >> operator_ >> list_ >> ')'
					;
		operator_.add
					("+", plus__)
					("-", minus__)
					("*", multiply__)
					("/", divide__)
					;
		list_		= +list_item_
					;
		list_item_	= expression_
					| qi::int_
					| qi::double_
					| string_
					;
		string_		= lexeme['"' >> *(unescape_char_ | ("\\x" >> qi::hex) | (qi::char_ - qi::char_('"'))) >> '"']
					;
		unescape_char_.add
					("\\a", '\a')("\\b", '\b')("\\f", '\f')("\\n", '\n')
					("\\r", '\r')("\\t", '\t')("\\v", '\v')("\\\\", '\\')
					("\\\'", '\'')("\\\"", '\"');
 
	}
 
	qi::rule< Iterator, Expression(), ascii::space_type > expression_;
	qi::rule< Iterator, List(), ascii::space_type > list_;
	qi::rule< Iterator, ListItem(), ascii::space_type > list_item_;
	qi::rule< Iterator, string(), ascii::space_type > string_;
	qi::symbols< char const, char const > unescape_char_;
	qi::symbols< char const, Operator > operator_;
};
 
ListItem evaluate(Expression &expression)
{
	ListItemType result_type(int__);
	ListItem retval;
	// first pass: evaluate any sub-expressions
	for (List::iterator iter(expression.list_.begin()); iter != expression.list_.end(); ++iter)
	{
		if (iter->which() == expression__)
		{
			*iter = evaluate(get< Expression >(*iter));
		}
		switch (iter->which())
		{
		case int__ :
			// this is the default type - it doesn't change anything
			break;
		case double__ :
			if (result_type == int__)
			{
				result_type = double__;
			}
			else
			{ /* either already a double, or it's a string */ }
			break;
		case string__ :
			result_type = string__;
			break;
		default :
			throw logic_error("unexpected operand type");
		}
	}
	switch (result_type)
	{
	case int__ :
		// nothing to do in this case: this is the default for the variant, and it will be zero-initialized
		break;
	case double__ :
		retval = 0.0;
		break;
	case string__ :
		retval = string();
		break;
	default :
		throw logic_error("Unexpected result type");
	}
	boost::shared_ptr< Accumulator > accumulator = getAccumulator(retval, expression.operator_, result_type);
	for (List::const_iterator iter(expression.list_.begin()); iter != expression.list_.end(); ++iter)
	{
			(*accumulator)(*iter);
	}
 
	return retval;
}	
 
int main()
{
	using boost::spirit::ascii::space;
 
	Expression expression;
	Grammar< string::const_iterator > grammar;
	string test("(+ 1 (+ 1 1.2))");
	string::const_iterator iter = test.begin();
	string::const_iterator end = test.end();
	if (qi::phrase_parse(iter, end, grammar, space, expression))
	{
		assert(expression.operator_ == plus__);
		ListItem result(evaluate(expression));
		assert(result.which() == double__);
		assert(get< double >(result) == 3.2);
	}
	else
	{
		assert(!"parse failed");
	}
	test = "(* 1 2)";
	iter = test.begin();
	end = test.end();
	expression.list_.clear();
	if (qi::phrase_parse(iter, end, grammar, space, expression))
	{
		assert(expression.operator_ == multiply__);
		ListItem result(evaluate(expression));
		assert(result.which() == int__);
		assert(get< int >(result) == 2);
	}
	else
	{
		assert(!"parse failed");
	}
	test = "(+ \"Hello, \" \"world!\")";
	iter = test.begin();
	end = test.end();
	expression.list_.clear();
	if (qi::phrase_parse(iter, end, grammar, space, expression))
	{
		assert(expression.operator_ == plus__);
		ListItem result(evaluate(expression));
		assert(result.which() == string__);
		assert(get< string >(result) == "Hello, world!");
	}
	else
	{
		assert(!"parse failed");
	}
	test = "(+ \"Goodbye\" (- \"Hello, world!\" \"Hello\"))";
	iter = test.begin();
	end = test.end();
	expression.list_.clear();
	if (qi::phrase_parse(iter, end, grammar, space, expression))
	{
		assert(expression.operator_ == plus__);
		ListItem result(evaluate(expression));
		assert(result.which() == string__);
		assert(get< string >(result) == "Goodbye, world!");
	}
	else
	{
		assert(!"parse failed");
	}
}

About rlc

Software Analyst in embedded systems and C++, C and VHDL developer, I specialize in security, communications protocols and time synchronization, and am interested in concurrency, generic meta-programming and functional programming and their practical applications. I take a pragmatic approach to project management, focusing on the management of risk and scope. I have over two decades of experience as a software professional and a background in science.
This entry was posted in C++ for the self-taught and tagged , , , , . Bookmark the permalink.