C++ template meta programming in a Lisp style.
C++11 is needed.
This is not something you would use in production. It's more like treating C++ template as an esolang, and create a "Lisp" on it just for fun.
See test.cc for examples.
#include <lmp.h>
using namespace lmp;
using reversed_list = reverse<IntList<1, 2, 3>>;
static_assert(length<reversed_list>::type::value == 3);
static_assert(nth<reversed_list, 0>::type::value == 3);
static_assert(nth<reversed_list, 1>::type::value == 2);
static_assert(nth<reversed_list, 2>::type::value == 1);
template<typename T>
using add1 = force<add<Int<1>, force<T>>>;
using mapped_list = map<add1, IntList<1, 2, 3>>;
static_assert(length<mapped_list>::value == 3);
static_assert(nth<mapped_list, 0>::type::value == 2);
static_assert(nth<mapped_list, 1>::type::value == 3);
static_assert(nth<mapped_list, 2>::type::value == 4);
template<typename T>
using is_even = equal<mod<T, Int<2>>, Int<0>>;
using even_numbers = filter<is_even, IntList<1, 2, 3, 4, 5, 6>>;
static_assert(equal<even_numbers, IntList<2, 4, 6>>::value);
using sum_list = IntList<1, 2, 3, 4, 5, 6, 7, 8>;
static_assert(apply<add,sum_list>::type::value == 36);#include <lmp.h>
using namespace lmp;
meta_fn(infinite_integers, int n) {
// `let_lazy(name, expr)` is similar to `(define name (delay expr))` in scheme
let_lazy(next, infinite_integers<n + 1>);
meta_return (cons<Int<n>, next>);
};
meta_fn(prime_sieve, class lst) {
static constexpr int n = car<lst>::value;
template<class T>
using not_divisible = not_<equal<mod<T, Int<n>>, Int<0>>>;
let_lazy(tail, prime_sieve<filter<not_divisible, cdr<lst>>>);
meta_return (cons<Int<n>, tail>);
};
using primes = prime_sieve<infinite_integers<2>>;
static_assert(nth<primes, 0>::type::value == 2);
static_assert(nth<primes, 1>::type::value == 3);
static_assert(nth<primes, 2>::type::value == 5);
static_assert(nth<primes, 3>::type::value == 7);
static_assert(nth<primes, 4>::type::value == 11);
static_assert(nth<primes, 5>::type::value == 13);This is similar to an infinite list of primes in Scheme:
(define (infinite-integers n)
(define next (delay (infinite-integers (+ n 1))))
(cons n next))
(define (prime-sieve lst)
(define n (car lst))
(define (not-divisible x) (not (= (modulo x n) 0)))
(define tail
(delay
(prime-sieve
(filter not-divisible(force (cdr lst))))))
(cons n tail))
(define primes
(prime-sieve (infinite-integers 2)))or in Haskell:
primes = filterPrime [2..] where
filterPrime (p:xs) =
p : filterPrime [x | x <- xs, x `mod` p /= 0]
// exmaple of a query EDSL
struct field1 {
static constexpr char name[] = "age";
using type = int;
};
struct field2 {
static constexpr char name[] = "height";
using type = double;
};
struct field3 {
static constexpr char name[] = "name";
using type = char*;
};
struct mytable {
static constexpr char name[] = "mytable";
using fields = list<field1, field2>;
};
template<typename query>
using is_valid_query = memberp<typename query::field, typename query::from::fields>;
constexpr char from_lit[] = "FROM";
constexpr char select_lit[] = "SELECT";
constexpr char space_lit[] = " ";
constexpr char semicolon_lit[] = ";";
meta_fn(build_query, typename query) {
meta_return (list2string<concat<
string2list<select_lit>,
string2list<space_lit>,
string2list<query::field::name>,
string2list<space_lit>,
string2list<from_lit>,
string2list<space_lit>,
string2list<query::from::name>,
string2list<semicolon_lit>>>);
};
// usage:
// checking validity of a query
struct myquery {
using from = mytable;
using field = field2;
};
static_assert(is_valid_query<myquery>::value);
struct invalid_query {
using from = mytable;
using field = field3;
};
// error:
// static_assert(is_valid_query<invalid_query>::value);
int main() {
printf("%s\n", build_query<myquery>::type::value);
return 0;
}
// result:
// SELECT height FROM mytable;#include <string>
#include "lmp.h"
template<typename... args>
struct ReflexObjectImpl;
template<typename N, typename T, typename... args>
struct ReflexObjectImpl<N, T, args...> : ReflexObjectImpl<args...> {
T value;
using name = N;
};
template<>
struct ReflexObjectImpl<> {};
#define DEFINE_LITERAL(_name_) \
namespace { \
inline static constexpr char _name_##_lit[] = #_name_; \
using _name_ = typename lmp::string2list<_name_##_lit>::type; \
} \
template<typename N, typename T, typename ...args>
T& getImpl(ReflexObjectImpl<args...> &obj) {
using lst = lmp::list<args...>;
static_assert(lmp::length<lst>::value >= 2);
if constexpr (lmp::eq<lmp::car<lst>, N>::value) {
return obj.value;
} else {
using BaseType = typename lmp::apply<ReflexObjectImpl, lmp::cddr<lst>>::type;
return getImpl<N, T>(static_cast<BaseType&>(obj));
}
}
template<typename N, typename T, typename ...args>
void setImpl(ReflexObjectImpl<args...> &obj, T&& new_value) {
using lst = lmp::list<args...>;
static_assert(lmp::length<lst>::value >= 2);
if constexpr (lmp::eq<lmp::car<lst>, N>::value) {
obj.value = std::forward<T&&>(new_value);
} else {
using BaseType = typename lmp::apply<ReflexObjectImpl, lmp::cddr<lst>>::type;
return setImpl<N, T>(static_cast<BaseType&>(obj), std::forward<T&&>(new_value));
}
}
template<typename... args>
void printImpl(ReflexObjectImpl<args...> &obj) {
using lst = typename lmp::list<args...>::type;
if constexpr (lmp::length<lst>::value >= 2) {
using N = typename lmp::nth<lst, 0>::type;
using T = typename lmp::nth<lst, 1>::type;
if constexpr (lmp::eq<T, int>::value) {
printf("%s: %d\n", lmp::list2string<N>::type::value, obj.value);
} else if constexpr (lmp::eq<T, double>::value) {
printf("%s: %lf\n", lmp::list2string<N>::type::value, obj.value);
} else if constexpr (lmp::eq<T, std::string>::value) {
printf("%s: %s\n", lmp::list2string<N>::type::value, obj.value.c_str());
}
using BaseType = typename lmp::apply<ReflexObjectImpl, lmp::cddr<lst>>::type;
printImpl(static_cast<BaseType&>(obj));
} else {
return;
}
}
template<typename... args>
struct ReflexObject {
ReflexObjectImpl<args...> value;
template<typename N>
using value_type = typename lmp::next_of<N, lmp::list<args...>>::type;
template<typename N>
value_type<N> get() {
return getImpl<N, value_type<N>, args...>(value);
}
void print() {
printImpl(value);
}
template<typename N>
void set(value_type<N> &&new_value) {
setImpl<N, value_type<N>, args...>(value, std::forward<value_type<N>&&>(new_value));
}
};
DEFINE_LITERAL(age)
DEFINE_LITERAL(height)
DEFINE_LITERAL(name)
using mytype = ReflexObject<
age, int,
height, double,
name, std::string
>;
int main (){
mytype x;
x.set<age>(1);
x.set<height>(3.1415926);
x.set<name>("hello");
x.print();
return 0;
}if you are using C++20, in this setting, concept becomes "type checking".
For exmaple, we have a meta function intp checking if a meta value value is an integer. So we define a concept Integer:
template<typename T>
concept Integer = intp<T>::value;And then we can type checking our meta functions:
meta_fn(myadd, Integer A, Integer B)
{
using a = force<A>;
using b = force<B>;
meta_return (add<a, b>);
has_value;
};
// success
using x = myadd<Int<1>, Int<2>>;
// error: template constraint failure for ‘template<class A, class B>
// requires (Integer<A>) && (Integer<B>) struct myfn’
using y = myadd<Int<1>, nil>;This chapter explains the core idea behind LMP: bring lazy evaluation ("thunks") into C++ template metaprogramming, so we can write branching (if/cond) and short-circuit logic (and/or/case) without resorting to heavy SFINAE boilerplate.
In template metaprogramming, you can mentally treat
F<A, B, C>like a function call.
The problem is that template metaprogramming is effectively eager: if you write something like
myif<Cond, TrueBranch, FalseBranch>you might expect it to only instantiate/evaluate the chosen branch. But in practice, both TrueBranch and FalseBranch get instantiated while forming the types—so you can't reliably use "function call style" to implement branching.
The classic workaround is SFINAE / enable_if / partial specialization dispatch. It works, but it tends to add lots of boilerplate, obscure the actual logic, and make code harder to read.
If we can wrap an expression in a type that does not evaluate it immediately, we can pass branches around safely and only evaluate the one we select.
A minimal "thunk" looks like this:
struct thunk_name {
using type = typename EXPR::type;
};thunk_name itself is just a wrapper type. Only when you access thunk_name::type do you force evaluation of EXPR::type. LMP provides a macro to generate such wrappers quickly:
#define let_lazy(__name__, ...) \
struct __name__ { \
using type = ::lmp::force<__VA_ARGS__>; \
};Usage:
let_lazy(do_a_thunk, do_a<x>);
let_lazy(do_b_thunk, do_b<x>);Now do_a_thunk / do_b_thunk are lazy expressions.
To evaluate something in LMP, you use force.
- If
Tis a thunk,force<T>evaluates the thunk, which using the::typeconvention:
template<typename T>
struct force_impl<T, void_t<typename T::type>> {
using type = typename T::type;
};If T is not a thunk, force<T> returns itself:
template<typename T, typename = void>
struct force_impl {
using type = T;
};This is a convention in LMP:
- Meta-functions return their result in
::type - You call
force<>when you want the evaluated result
With thunks, we can implement a real conditional branching that only evaluates one branch.
Conceptually, if_<Cond, TB, FB> does:
force<Cond>to get a boolean type (std::true_type/std::false_type)- based on that, it forces one of
TBorFB
So we define both branch as a thunk:
let_lazy(do_a_thunk, do_a<x>);
let_lazy(do_b_thunk, do_b<x>);
using result = lmp::force< lmp::if_<ok, do_a_thunk, do_b_thunk> >;This is still a bit more verbose than a real functional language, but it's predictable, composable, and avoids SFINAE-heavy branching patterns.
All other syntax involving hort-circuit logic (and_, or_, cond)
is built the same way. Once you have a conditional that only evaluates
one branch, you can implement short-circuiting constructs naturally:
or_evaluates left-to-right and stops at the first true conditionand_evaluates left-to-right and stops at the first false conditioncondchains(predicate, expression)pairs and picks the first matching one
All of them rely on the same mechanism: recursive structure + thunks +
cond_ so that the "rest of the computation" is delayed and only
forced when needed.
In LMP, function arguments might themselves be thunks. A common pattern is:
forcearguments at the start (because arguments could be thunks),- evaluate the expression,
forcethe result (because the expression may return a thunk).
For example:
template<typename Arg>
struct my_meta_func {
using arg = lmp::force<Arg>;
using type = lmp::force< do_something<arg> >;
};To make this style uniform and lightweight, LMP uses two macros:
#define meta_fn(__name__, ...) template<__VA_ARGS__> struct __name__
#define meta_return(...) using type = ::lmp::force<__VA_ARGS__>So the same function becomes:
meta_fn(my_meta_func, class Arg) {
using arg = lmp::force<Arg>;
meta_return(do_something<arg>);
};You need to follow the same convention when defining new
meta-functions with using. For example, to create a function which
add one to an integer:
template<typename T>
using add1 = force<add<Int<1>, force<T>>>;