Boost logo

Boost :

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2002-10-03 07:05:08

As a weekend project, I implemented a prototype interpreter for an ML-like
programming language using C++ templates. The intention was to create a
convenient way to express algorithms rather than just boost up the the
template mechanism a bit. Therefore the syntax and evaluation are separated
so that it isn't necessary to complicate algorithms by explicitly
introducing laziness. Unfortunately the interpretive nature of the technique
makes it about 20x slower than direct use of the C++ template mechanism.
Nevertheless I think that this might interest people who can see how
painstaking contemporary metaprogramming techniques are.

The ML-like syntax for expressions can be described roughly as follows:

expr : if_< c-expr, t-expr, e-expr > // selection construct
     | fn< pattern-expr, body-expr > // anonymous function
     | rec< arg-expr > // recursive call to anon. fn
     | app< fn-expr, arg-expr > // function application
     | pair< epxr, expr > // pair
     | list< expr, expr, ...> // list
     | SYM // symbol (see below)
     | i< ... > // integer literal
     | b< ... > // boolean literal

In addition there are a number of built-in functions for arithmetic, etc...

Symbols are declared using a macro `ML_SYM(C++-IDENTIFIER)', which creates a
new class to act as the symbol.

Expressions are interpreted using the `eval< EXPR >::type' metafunction.

Functions can be compiled, before they are interpreted, by using the syntax
`fn-expr::type'. During compilation, the symbols are replaced by a
construct, that directly accesses the appropriate element from the argument
(rather than searching the pattern). Many more optimizations could be
performed, but it is probably impossible to make this technique fast enough
for general use simply by optimizing at this level (optimizations in
compilers might help).

Here are some examples (taken directly from regression test code) of "ML".


typedef fn<N,
                  if_<eq<i<0>, N>,
                      rec<list<I1, plus<I0,I1>, plus<i<-1>, N> > > > >,
               list<i<0>, i<1>, N> > >::type fib_fn;
// The above defines the linear time fibonacci algorithm.
template<class N>
struct fib : app<fib_fn, N> {};
// The above is basically a macro for making it convenient
// to directly call the fib_fn function.

typedef eval< fib<i<40> > >::type test_3;
BOOST_STATIC_ASSERT((is_same<i<102334155>, test_3>::value));
// The above is a test for the fib_fn function.


typedef fn<list<Fn,R,L>,
                      rec<pair<app<Fn, list<R, fst<L> > >,
                               rst<L> > > > >,
               pair<R,L> > >::type fold_left_fn;
template<class Fn, class R, class L>
struct fold_left : app<fold_left_fn, list<Fn,R,L> > {};


typedef fn<L,
                        pair<X,R> >,
                     L> >::type rev_fn;
template<class L>
struct rev : app<rev_fn, L> {};

typedef eval< rev<list<i<0>,i<1>,i<2> > > >::type test_9;
BOOST_STATIC_ASSERT((is_same<list<i<2>,i<1>,i<0> >::type, test_9>::value));

typedef fn<list<Fn,L>,
                             R> >,
                     rev<L> > >::type map_fn;
// Note above the use of lexical closures (the Fn argument
// is in the closure). The fn<> construct builds lexical
// closures.
template<class Fn, class L>
struct map : app<map_fn, list<Fn,L> > {};

typedef eval< map<fib_fn,list<i<0>,i<1>,i<2>,i<3>,i<4>,i<5> > > >::type
BOOST_STATIC_ASSERT((is_same<list<i<0>,i<1>,i<1>,i<2>,i<3>,i<5> >::type,


If you are interested in the prototype ML interpreter, I'll be happy to
release it, but you must realize that it is a prototype and I probably don't
have time to polish or support it. The source code contains currently about
1100 lines (but it could be significantly shorter) and can be compiled on
g++ 2.95.

Send and receive Hotmail on your mobile device:

Boost list run by bdawes at, gregod at, cpdaniel at, john at