tmplite

tmplite is a strongly-typed, functional programming language designed as a thin layer on top of C++ template metaprogramming (TMP). Tmplite programs cross-compile into C++ programs that execute at compile-time and yield a program that prints the result of the given computation. For example, consider the following simple program:

function Factorial:
   Factorial(0) = 1;
   Factorial(x) = x * Factorial(x - 1);
;

main:
   Factorial(10);
;

The generated C++ code for this program (omitted for the sake of brevity) will determine 10! at compile-time, then output a program that prints the result. In other words, once the generated program is compiled, the resulting executable will perform no computations and will simply print the result.

tmplite treats integers, booleans, and lists as primitive types and allows for user-defined types in the style of ML or Haskell. For example, here is a program to compute the height of a binary tree:

/* Define a parametrized binary tree type. */
type BinaryTree[$A]:
   Nil[];
   Node[$A, BinaryTree[$A], BinaryTree[$A]];
;

/* If function evaluates to second argument on true and third argument on false. */
function If:
  If(true, a, b) = a;
  If(false, a, b) = b;
;

/* Max function evaluates to larger of its arguments. */
function Max:
  Max(a, b) = If(a > b, a, b);
;

/* Height of a tree is 1 plus the max size of its subtrees. */
function Height:
  Height(BinaryTree.Nil[]) = 0;
  Height(BinaryTree.Node[val, lhs, rhs]) = 1 + Max(Height(lhs), Height(rhs));
;

As the above code might suggest, tmplite is a strongly-typed, pattern-matching based programming language with syntax somewhat similar to that of the ML family of languages.

tmplite also supports higher-order functions, such as the following Map function:

/* Map applies a function to each element in a range. */
function Map:
  Map(fn, {}) = {}; /* Map over the empty list is the empty list. */
  Map(fn, car :: cdr) = fn(car) :: Map(fn, cdr);
;

tmplite is primarily a proof-of-concept language designed to illustrate the computational power of the C++ template system without exposing programmers to some of the nastier details of C++ templates (e.g. the many uses of the typename and template keywords). While not designed for heavy-duty programming, it is nonetheless an interesting study in the C++ template system.

To see how tmplite compiles tmplite code into C++ source code, let's consider the Map function as an example. Tmplite represents functions as structs containing a templatized struct called apply parametrized over the arguments to the function, plus a final parameter which makes it simpler for the pattern-matching algorithm to work. This struct has a single field, type, which holds the result of the operation. When the code is generated for the template function, initially this template typedefs type to be void, as shown here:

/* Sample code generated by Map: */
struct MetaFnMap
{
    template <typename fn, typename list, typename dummy> struct apply
    {
        typedef void type;
    };
};

Once we have defined the initial class representing Map, we then provide template specializations of apply for each of its arguments. Each specialization specializes some of the function arguments, plus the final "dummy" argument. For example, here is the specialization of the Map function for the case where the function fn is applied to the empty list:

/* Specialization of Map for Map(fn, {}): */
template <typename fn> struct MetaFnMap::apply<fn, MetaNil, SpecializationTag>
{
    typedef MetaNil type; // Map(fn, {}) = {}
};

The second case of the Map function is more complicated, but illustrates how functions work and motivates the utility of having a language like tmplite to make template metaprogramming simpler:

/* Specialization of Map for Map(fn, car:: cdr): */
template <typename fn, typename car, typename cdr> struct MetaFnMap::apply<fn, MetaList<car, cdr>, SpecializationTag>
{
    typedef MetaList<typename fn::template apply<car, SpecializationTag>::type,
                     typename MetaFnMap::template apply<fn, cdr, SpecializationTag>::type> type;
};

Now, if we instantiate the MetaFnMap::apply type with the name of an appropriate metafunction, a typelist, and the special SpecializationTag type, the metaprogram will generate a new list formed by applying the specified function to the specified list. This is easily accomplished by simply placing a function call in the tmplite code and having the tmplite compiler do the rest of the work.

tmplite is an ongoing project that's still in development and currently there is no stable release - the compiler still lacks a good many features. If you are interested in the source code, send me an email and I'll be glad to send you the current working version.