======================
Lispy Meta Programming
======================

C++ template meta programming in a Lisp style.

C++11 is needed.

This is not something you would use in production. It's super slow and easily
hit the max depth of template expansion. It's more like treating C++ template as
an esolang, and create a "Lisp" on it just for fun.

See "test.cc" for examples.

Examples
========

Basic List Operations
---------------------

    #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);


Infinite List of Primes (Sieve of Eratosthenes)
-----------------------------------------------

    #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]

A (toy) compile-time query EDSL
-------------------------------

    // 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;

(C++17) Compile-time reflection
-------------------------------

    #include <string>

    #include "lmp.h"

    template<typename... args>
    struct ReflObjImpl;

    template<typename N, typename T, typename... args>
    struct ReflObjImpl<N, T, args...> : ReflObjImpl<args...> {
        T value;
        using name = N;
    };

    template<>
    struct ReflObjImpl<> {};

    #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(ReflObjImpl<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<ReflObjImpl, lmp::cddr<lst>>::type;
            return getImpl<N, T>(static_cast<BaseType&>(obj));
        }
    }

    template<typename N, typename T, typename ...args>
    void setImpl(ReflObjImpl<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<ReflObjImpl, lmp::cddr<lst>>::type;
            return setImpl<N, T>(static_cast<BaseType&>(obj), std::forward<T&&>(new_value));
        }
    }

    template<typename... args>
    void printImpl(ReflObjImpl<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<ReflObjImpl, lmp::cddr<lst>>::type;
            printImpl(static_cast<BaseType&>(obj));
        } else {
            return;
        }
    }

    template<typename... args>
    struct ReflObj {
        ReflObjImpl<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 = ReflObj<
        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;
    }

C++20 Concepts
==============

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>;

How This Works
==============

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.

Templates feel like function calls, it's eager.
-----------------------------------------------

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.

### A thunk: delay evaluation by wrapping an expression

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.

"force": evaluate a thunk (or any meta-object with "::type")
------------------------------------------------------------

To evaluate something in LMP, you use "force".

If "T" is a thunk, "force<T>" evaluates the thunk, which using the
  "::type" convention:

    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:

1. Meta-functions return their result in "::type"
2. You call "force<>" when you want the evaluated result


Branching with "if_": only evaluate the selected branch
-------------------------------------------------------

With thunks, we can implement a real conditional branching that only evaluates
one branch.

Conceptually, "if_<Cond, TB, FB>" does:

1. "force<Cond>" to get a boolean type ("std::true_type" / "std::false_type")
2. based on that, it forces one of "TB" or "FB"

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 condition
* "and_" evaluates left-to-right and stops at the first false condition
* "cond" chains "(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.

The meta-function pattern: force inputs, and force the returned expression
--------------------------------------------------------------------------

In LMP, function arguments might themselves be thunks. A common pattern is:

* "force" arguments at the start (because arguments could be thunks);
* evaluate the expression;
* "force" the 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>>>;