[boost] ML Interpreter for Template Metaprogramming

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".

ML_SYM(N);
ML_SYM(I0);
ML_SYM(I1);

typedef fn<N,
           app<fn<list<I0,I1,N>,
                  if_<eq<i<0>, N>,
                      I0,
                      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.

ML_SYM(Fn);
ML_SYM(R);
ML_SYM(L);

typedef fn<list<Fn,R,L>,
           app<fn<pair<R,L>,
                  if_<null<L>,
                      R,
                      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> > {};

ML_SYM(X);

typedef fn<L,
           fold_left<fn<list<R,X>,
                        pair<X,R> >,
                     nil,
                     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>,
           fold_left<fn<list<R,X>,
                        pair<app<Fn,X>,
                             R> >,
                     nil,
                     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 
test_8;
BOOST_STATIC_ASSERT((is_same<list<i<0>,i<1>,i<1>,i<2>,i<3>,i<5> >::type, 
test_8>::value));

...

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: http://mobile.msn.com