lispy spirit demo

display.cpp

#include "display.hpp"
#include <boost/spirit/include/karma.hpp>

namespace karma = boost::spirit::karma;

template <typename It>
struct generator : karma::grammar<It, expr_t()> {
    generator() : generator::base_type(start) {
        start = karma::string | ('(' << start % ' ' << ')');
    }
    private: karma::rule<It, expr_t()> start;
};

std::ostream& operator<<(std::ostream& os, expr_t const& e)
{
    generator<boost::spirit::ostream_iterator> rule;
    return os << karma::format(rule, e);
}

display.hpp

#include <iosfwd>
#include "expr.hpp"

std::ostream& operator<<(std::ostream&, expr_t const&);

eval.cpp

#include "eval.hpp"
#include <boost/lexical_cast.hpp>
#include <boost/variant.hpp>
#include <boost/variant/static_visitor.hpp>
#include <boost/variant/apply_visitor.hpp>

#include <map>
#include <functional>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <stdexcept>
#include <iterator>

namespace
{
    // TODO refactor to take and return expr_t
    template <typename V>
        V apply_f(std::string const& f, std::vector<V> const& args)
    {
        using std::string;
        typedef std::vector<V> Args;

        // TODO check function arity
        auto registered = std::map<string, std::function<V(Args const&)> >
        {
            { "+",   [] (Args const& a) { return std::accumulate(a.begin()+1, a.end(), a.front(), std::plus<V>());  } },
            { "-",   [] (Args const& a) { return std::accumulate(a.begin()+1, a.end(), a.front(), std::minus<V>()); } },
            { "*",   [] (Args const& a) { return std::accumulate(a.begin()+1, a.end(), a.front(), std::multiplies<V>()); } },
            { "/",   [] (Args const& a) { return std::accumulate(a.begin()+1, a.end(), a.front(), std::divides<V>()); } },
            { "avg", [] (Args const& a) { return std::accumulate(a.begin()+1, a.end(), V()) / V(a.size()); } },
            { "trace", [] (Args const& a) 
                { std::cout << "trace( "; // TODO provide proper output interface
                  std::copy(a.begin(), a.end(), std::ostream_iterator<V>(std::cout, " "));
                  std::cout << ")\n";
                  return V();
                } 
            },
        };
        try { return registered[f](args); } 
        catch(std::exception const& e) // TODO improve error reporting (e.g. undefined function)
        {
            std::ostringstream oss;
            oss << "error: can't apply '" << f << "' to " << args.size() << " args (" << e.what() << ")\n";
            throw std::runtime_error(oss.str());
        }
    }

    template <typename V>
        struct eval_visitor : boost::static_visitor<V> // TODO refactor to return expr_t
    {
        V operator()(std::string const& v) const {
            try { return boost::lexical_cast<V>(v); } 
            catch(...) 
            {
                std::cerr << "warning: undefined '" << v << "'\n";
                return V();
            }
        }
        V operator()(std::vector<expr_t> const& v) const {
            switch (v.size())
            {
                case 0: return V();
                case 1: return boost::apply_visitor(*this)(v.front());
                default: // function application
                    std::vector<V> args;
                    for(auto it=v.begin()+1; it!=v.end(); ++it)
                        args.push_back(boost::apply_visitor(*this, *it));
                    return apply_f<V>(boost::get<std::string>(v.front()), args);
            }
        }
    };
}

template <typename V>
   V eval(expr_t const &e)
{
    return boost::apply_visitor(eval_visitor<V>(), e);
}

template double eval<double>(expr_t const &e);
template int eval<int>(expr_t const &e);

eval.hpp

#include "expr.hpp"

template <typename V> V eval(expr_t const &);

extern template double eval<double>(expr_t const &e);
extern template int eval<int>(expr_t const &e);

expr.hpp

#include <boost/variant/recursive_variant.hpp>
#include <vector>
#include <string>

typedef boost::make_recursive_variant<
        std::string, // TODO refactor to allow variable types (int, double etc) and 'nil'
        std::vector< boost::recursive_variant_ >
   >::type expr_t;

Makefile

all:test

test: display.o eval.o

CPPFLAGS+=-std=c++0x
CPPFLAGS+=-g -O0
CPPFLAGS+=-I ~/custom/boost/

# CPPFLAGS+=-fopenmp
# CPPFLAGS+=-march=native

# LDFLAGS+=-L ~/custom/boost/stage/lib/
# LDFLAGS+=-lboost_system -lboost_regex -lboost_thread -lpthread

CXX=g++
CC=gcc
# CXX=~/Projects/CLANG/build/Debug+Asserts/bin/clang++
# CC=~/Projects/CLANG/build/Debug+Asserts/bin/clang

%:%.o
	$(CXX) $(CPPFLAGS) $^ -o $@ $(LDFLAGS)

test.cpp

// #define BOOST_SPIRIT_DEBUG
#include <boost/fusion/adapted.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>

#include "expr.hpp"
#include "display.hpp"
#include "eval.hpp"

namespace qi    = boost::spirit::qi;
namespace phx   = boost::phoenix;

template <typename It, typename Skipper = qi::space_type>
    struct parser : qi::grammar<It, expr_t(), Skipper>
{
    parser() : parser::base_type(start)
    {
        using namespace qi;
        // using phx::bind; using phx::ref; using phx::val;

        expr   = binop | s_expr;

        binop = (s_expr >> (string("+") | string("-") | string("*") | string("/")) >> expr)
            [
                phx::push_back(_val, _2),
                phx::push_back(_val, _1),
                phx::push_back(_val, _3)
            ];

        name = as_string [ lexeme [ +(graph - char_("()") ) ] ];

        s_expr = ('(' > +expr > ')') | name;

        start = s_expr;

        BOOST_SPIRIT_DEBUG_NODE(start);
        BOOST_SPIRIT_DEBUG_NODE(name);
        BOOST_SPIRIT_DEBUG_NODE(s_expr);
        BOOST_SPIRIT_DEBUG_NODE(binop);
        BOOST_SPIRIT_DEBUG_NODE(expr);
    }

  private:
    qi::rule<It, std::vector<expr_t>(), Skipper> binop;
    qi::rule<It, expr_t(), Skipper> expr, s_expr, name;
    qi::rule<It, expr_t(), Skipper> start;
};

template <typename C, typename Skipper>
    expr_t doParse(C const& input, Skipper const& skipper)
{
    auto f(std::begin(input)), l(std::end(input));

    parser<decltype(f), Skipper> p;
    expr_t data = "<no ast>";

    try
    {
        bool ok = qi::phrase_parse(f,l,p,skipper,data);
        if (ok)   
        {
            std::cout << "parse success\n";
            std::cout << "input       : " << input << "\n";
            std::cout << "ast parsed  : " << data  << "\n";
        }
        else std::cerr << "parse failed: '" << std::string(f,l) << "'\n";

        if (f!=l) std::cerr << "trailing unparsed: '" << std::string(f,l) << "'\n";
    } catch(qi::expectation_failure<decltype(f)> const& e)
    {
        std::string frag(e.first, e.last);
        std::cerr << e.what() << "'" << frag << "'\n";
    } catch(std::exception const& e)
    {
        std::cerr << e.what() << '\n';
    }

    return data;
}

int main()
{
    for (const auto input : std::list<std::string> {
         "",
         "(+ 1 3)",
         "(1 + 3)",
         "(1 + 4 / 2)",
         "(1 + (* 4 5 6) / 2)",
         "(avg   1 + (* 4 5 6) / 2)",
         "(trace 1 + (* 4 5 6) / 2 1 1 1 1 999)",
         "(avg   1 + (* 4 5 6) / 2 1 1 1 1 999)",
         "(avg   1 + (* 4 (unknown-function 5) 6) / 2 a b c)",
     })
    {
        std::cout << "----------------------\n";
        expr_t ast = doParse(input, qi::space);

        try 
        {
            std::cout << "eval<double>: " << eval<double>(ast) << std::endl;
            std::cout << "eval<int>   : " << eval<int   >(ast) << std::endl;
        } catch(std::exception const& e)
        {
            std::cerr << e.what() << '\n';
        }
    }
}