Lisp in C++ templates: proof-of-concept

gistfile1.cpp


// NUM
template <typename T, T Val>
struct _NUM_IMPL
{
	static const T value = Val;
};

#define NUM(val) _NUM_IMPL <decltype (val), val>

typedef NUM (true) TRUE;
typedef NUM (false) FALSE;


// CONS
template <typename _CAR, typename _CDR>
struct CONS
{
	typedef _CAR CAR;
	typedef _CDR CDR;
};


// NIL
struct NIL
	: CONS <NIL, NIL>
{
};


// CAR
template <typename _CONS>
struct _CAR_IMPL
{
	typedef typename _CONS::CAR value;
};

template <typename _CONS>
using CAR = typename _CAR_IMPL <_CONS>::value;


// CDR
template <typename _CONS>
struct _CDR_IMPL
{
	typedef typename _CONS::CDR value;
};

template <typename _CONS>
using CDR = typename _CDR_IMPL <_CONS>::value;


// LIST
template <typename...>
struct _LIST_IMPL;

template <>
struct _LIST_IMPL <>
{
	typedef NIL value;
};

template <typename First, typename... Rest>
struct _LIST_IMPL <First, Rest...>
{
	typedef CONS <First, typename _LIST_IMPL <Rest...>::value> value;
};

template <typename... Args>
using LIST = typename _LIST_IMPL <Args...>::value;


// PLUS
template <typename...>
struct _PLUS_IMPL;

template <typename... Args>
using PLUS = typename _PLUS_IMPL <Args...>::value;

template <typename First>
struct _PLUS_IMPL <First>
{
	typedef First value;
};

template <typename First, typename... Rest>
struct _PLUS_IMPL <First, Rest...>
{
	typedef NUM (First::value + PLUS <Rest...>::value) value;
};


// LENGTH
template <typename _LIST>
struct _LENGTH_IMPL
{
	typedef PLUS <typename _LENGTH_IMPL <CDR <_LIST>>::value, NUM (1)> value;
};

template <>
struct _LENGTH_IMPL <NIL>
{
	typedef NUM (0) value;
};

template <typename _LIST>
using LENGTH = typename _LENGTH_IMPL <_LIST>::value;


// LEQ
template <typename A, typename B>
struct _LEQ_IMPL
{
	typedef NUM (A::value <= B::value) value;
};

template <typename A, typename B>
using LEQ = typename _LEQ_IMPL <A, B>::value;


// NTH
template <typename Pos, typename _LIST>
struct _NTH_IMPL
{
	typedef typename _NTH_IMPL <PLUS <Pos, NUM (-1)>, CDR <_LIST>>::value value;
};

template <typename _LIST>
struct _NTH_IMPL <NUM (0), _LIST>
{
	typedef CAR <_LIST> value;
};

template <typename Pos, typename _LIST>
using NTH = typename _NTH_IMPL <Pos, _LIST>::value;


// IF
template <typename, typename, typename>
struct _IF_IMPL
{
};

template <typename A, typename B>
struct _IF_IMPL <TRUE, A, B>
{
	typedef A value;
};

template <typename A, typename B>
struct _IF_IMPL <FALSE, A, B>
{
	typedef B value;
};

template <typename value, typename A, typename B>
using IF = typename _IF_IMPL <value, A, B>::value;


// MIN
template <typename A, typename B>
struct _MIN_IMPL
{
	typedef IF <LEQ <A, B>, A, B> value;
};

template <typename A, typename B>
using MIN = typename _MIN_IMPL <A, B>::value;


// MIN_INDEX
template <typename _LIST>
struct _MIN_INDEX_IMPL
{
	typedef IF <LEQ <CAR <_LIST>,
	                 NTH <typename _MIN_INDEX_IMPL <CDR <_LIST>>::value,
	                      CDR <_LIST>>>,
	            NUM (0),
		PLUS <typename _MIN_INDEX_IMPL <CDR <_LIST>>::value, NUM (1)>> value;
};

template <typename _CAR>
struct _MIN_INDEX_IMPL <CONS <_CAR, NIL>>
{
	typedef NUM (0) value;
};

template <typename _LIST>
using MIN_INDEX = typename _MIN_INDEX_IMPL <_LIST>::value;


// SUBSEQ
template <typename _LIST, typename Begin, typename End>
struct _SUBSEQ_IMPL
{
	typedef CONS <NTH <Begin, _LIST>,
	             typename  _SUBSEQ_IMPL <_LIST,
	                                     PLUS <Begin, NUM (1)>,
	                                     End>::value>
		value;
};

template <typename _LIST, typename Pos>
struct _SUBSEQ_IMPL <_LIST, Pos, Pos>
{
	typedef NIL value;
};

template <typename _LIST, typename Begin, typename End>
using SUBSEQ = typename _SUBSEQ_IMPL <_LIST, Begin, End>::value;


// APPEND
template <typename _LIST1, typename _LIST2>
struct _APPEND_IMPL
{
	typedef CONS <CAR <_LIST1>, typename _APPEND_IMPL <CDR <_LIST1>, _LIST2>::value> value;
};

template <typename _LIST2>
struct _APPEND_IMPL <NIL, _LIST2>
{
	typedef _LIST2 value;
};

template <typename _LIST1, typename _LIST2>
using APPEND = typename _APPEND_IMPL <_LIST1, _LIST2>::value;


// SORT
template <typename _LIST>
struct _SORT_IMPL
{
	typedef SUBSEQ <_LIST, NUM (0), MIN_INDEX <_LIST>> first_half;
	typedef SUBSEQ <_LIST,
	                PLUS <MIN_INDEX <_LIST>, NUM (1)>,
	                LENGTH <_LIST>> second_half;

	typedef CONS <NTH <MIN_INDEX <_LIST>, _LIST>,
	              typename _SORT_IMPL <APPEND <first_half, second_half>>::value>
		value;
};

template <>
struct _SORT_IMPL <NIL>
{
	typedef NIL value;
};

template <typename _LIST>
using SORT = typename _SORT_IMPL <_LIST>::value;




#include <iostream>
#include <typeinfo>

using namespace std;

std::ostream& operator << (std::ostream& os, NIL)
{
	return os;
}

template <typename T, T Val>
std::ostream& operator << (std::ostream& os, _NUM_IMPL <T, Val>)
{
	return os << Val;
}

template <typename _CAR, typename _CDR>
std::ostream& operator << (std::ostream& os, CONS <_CAR, _CDR>)
{
	return os << _CAR () << ' ' << _CDR ();
}

int main ()
{
	#define printtest(n) cout << typeid (NTH <NUM (n), LIST <int, double, std::string, std::ostream>>).name () << endl;
	printtest (0);
	printtest (1);
	printtest (2);
	printtest (3);
	printtest (4);
	printtest (5);
	#undef printtest

	typedef LIST <NUM (8), NUM (6), NUM (7), NUM (5), NUM (3), NUM (0), NUM (9)> typelist;
//	typedef SORT <typelist> sorted;

	cout << SUBSEQ <typelist, NUM (2), NUM (5)> () << endl;
	cout << SORT <typelist> () << endl;
}