## More resources

If you're into this sort of thing, you might also like:

- My lambda-calculus interpreter as a C++ template metaprogram.
- C++ Templates: The Complete Guide, which I used to write this.
- Boost C++, a library that provides anonymous functions.
- Functional C++ by Brian McNamara and Yannis Smaragdakis.
- Oleg's take on lambdas in C++.

## A quick decomposition

Let's break down the expression:

lambda<int> (x) --> x + 1

The expression

lambda<int> (x)

is a call to a templated function:

template <typename Y,typename X1> Function1<Y,X1> lambda (Var<X1>& x1) ;

So, from this, we see that what appears to be a variable parameter to
the lambda term, `x`

, is actually an expression of type
`Var<X1>`

.
In our DSEL, an expression of type `Var<X1>`

represents an argument that has type `X1`

.

This means that the variable `x`

must be declared outside the lambda term.
It's a good idea to declare all meta-parameters once at a global scope, e.g.:

Var<int> x, y, z ; Var<char*> r, s ;

so that any lambda term that wants to accept an integer can use
`x`

, `y`

or `z`

, and
`r`

or `s`

could be used for string arguments.
(It's safe to re-use meta-parameters between lambdas; they won't be mixed.)

The type `Function1<Y,X1>`

is a templated class
for functions that take an `X1`

and produce a
`Y`

.
So, a call to `lambda<T>`

produces an anonymous
function that returns type `T`

.
We don't have to specify `lambda<Y,X1>`

because it
can infer the type `X1`

from the meta-parameter supplied to the
`lambda`

function.

If we were willing to specify the body of the lambda term as the
last parameter, e.g., `lambda (x,x+1)`

, then it could also
infer the return type, but I don't think this looks as nice.

Glancing at the prototype for `Function1`

, we find several operator overloads:

template <typename Y,typename X1> class Function1 { public: Function1<Y,X1> (Var<X1>& p1) ; Function1<Y,X1>& operator -- (int) ; Function1<Y,X1>& operator > (Exp<Y>& body) ; Y operator () (const X1& x1) ; // ... } ;

This reveals how to implement the `-->`

operator:
it's actually just the juxtaposition of postfix decrement (`--`

) and
greater-than (`>`

).

The postfix `--`

operator just returns `this`

,
and the greater-than operator binds the body of the lambda term
to this function object.
That is, the `--`

is just a syntactic placebo that improves aesthetics.

The function object overloads application to give it the appearance of being a function whenever it's called.

The body of the lambda term, `x + 1`

, turns into a syntax
tree for an expression.

## Expression trees

The function objects store the bodies of lambda terms as trees that describe the structure of the computation.

Expression trees are parameterized by the type they return under evaluation:

template <typename T> struct Exp { virtual T eval() ; // ... } ;

And, there are subclasses to represent expressions like constants, variables and binary operations:

template <typename T> class Const : public Exp<T> // ... template <typename T> class Var : public Exp<T> // ... template <typename T> class BinOp : public Exp<T> // ...

And, specialized instances of the base expression template introduce operators for types that support them; for instance, integer arithmetic:

template < > struct Exp<int> { Exp<int>& operator + (Exp<int>& that) ; Exp<int>& operator * (Exp<int>& that) ; Exp<int>& operator + (int n) ; Exp<int>& operator * (int n) ; // Add any other operations you want here. // E.g.: / ^ - <= } Exp<int>& operator + (int n, Exp<int>& thiss) ; Exp<int>& operator * (int n, Exp<int>& thiss) ;

So, an expression like `x + 1`

is roughly equivalent to

new BinOp<int>(sum,x,new Const<int>(1))where

`sum`

is a function pointer to a function that performs addition.
If you want to add expressions like function calls or array indexing to the DSEL, you can add additional template classes and specializations.

## Code

What I've described so far gets you an interface that type-checks. To see the code that plumbs it all together, check out the full implementation. It's under 500 lines of heavily-commented C++ and includes testing examples.

This implementation is pretty fast, but it could be significantly optimized. Expressions templates and inlining annotations (assuming the compiler obeys them), for instance, could eliminate the small overhead. Please consider this a proof-of-concept implementation.