TypeLISP

From: netterdag_at_[hidden]
Date: 2000-11-30 17:49:56

Hi

Recently I made a *very* experimental typelist implementation
with some "LISP"-like functionality. Is something like this of
interest? Anyway, here it is... (Sorry if I've managed to break
any Boost posting rule with this one).

Note for those trying to compile this:
I've tested it using GCC-2.95.2 (Mingw32) with STLport 4.0.
You probably need to increase the template depth of GCC
(I've used -ftemplate-depth-30)

--
Regards
Gabriel
#include <iostream>
#include <cstddef>
struct nil {};
template<typename X, typename Y>
struct equal {
  static const bool result = false;
};
template<typename X>
struct equal<X, X> {
  static const bool result = true;
};
template<bool Cond, typename Then, typename Else>
struct select_if {
  typedef Else result;
};
template<typename Then, typename Else>
struct select_if<true, Then, Else> {
  typedef Then result;
};
template<typename Type, typename Next = nil>
struct type_list {
  typedef Type type;
  typedef Next next;
};
// car (car '(1 2 3)) => 1
template<typename List>
struct car;
template<typename T, typename N>
struct car<type_list<T, N> > {
  typedef typename type_list<T, N>::type result;
};
template<>
struct car<nil> {
  typedef nil result;
};
// cdr (cdr '(1 2 3)) => (2 3)
template<typename List>
struct cdr;
template<typename T, typename N>
struct cdr<type_list<T, N> > {
  typedef typename type_list<T, N>::next result;
};
template<>
struct cdr<nil> {
  typedef nil result;
};
// length (length '(1 2 3)) => 3
template<typename List, std::size_t I = 0>
struct length;
template<typename T, typename N, std::size_t I>
struct length<type_list<T, N>, I> {
  static const std::size_t result = length<typename cdr<type_list<T, 
N> >::result, I + 1>::result;
};
template<std::size_t I>
struct length<nil, I> {
  static const std::size_t result = I;
};
template<>
struct length<nil, 0> {
  static const std::size_t result = 0;
};
// nth (nth 1 '(1 2 3)) => 2
template<std::size_t Pos, typename List, std::size_t I = 0>
struct nth;
template<std::size_t Pos, typename T, typename N, std::size_t I>
struct nth<Pos, type_list<T, N>, I> {
  typedef typename car<type_list<T, N> >::result curr;
  typedef typename cdr<type_list<T, N> >::result next;
  typedef typename select_if<Pos == I,
                   curr,
                   typename nth<Pos, next, I + 1>::result>::result 
result;
};
template<std::size_t Pos, std::size_t I>
struct nth<Pos, nil, I> {
  typedef nil result;
};
// assoc (assoc 3 '((1 2) (3 4))) => (3 4)
template<typename Type, typename List>
struct assoc;
template<typename Type, typename T, typename N>
struct assoc<Type, type_list<T, N> > {
  typedef typename car<type_list<T, N> >::result curr;
  typedef typename cdr<type_list<T, N> >::result next;
  typedef typename car<curr>::result             test;
  typedef typename select_if<equal<Type, test>::result,
                             curr,
                             typename assoc<Type, 
next>::result>::result result;
};
template<typename Type>
struct assoc<Type, nil> {
  typedef nil result;
};
// cons (cons 1 '(2 3)) => (1 2 3)
template<typename Type, typename List>
struct cons;
template<typename Type, typename T, typename N>
struct cons<Type, type_list<T, N> > {
  typedef type_list<Type, type_list<T, N> > result;
};
template<typename Type>
struct cons<Type, nil> {
  typedef type_list<Type> result;
};
// reverse (reverse '(1 2 3)) => '(3 2 1)
template<typename List, typename NewList = nil>
struct reverse;
template<typename T, typename N, typename NewList>
struct reverse<type_list<T, N>, NewList> {
  typedef typename car<type_list<T, N> >::result curr;
  typedef typename cdr<type_list<T, N> >::result next;
  typedef typename cons<curr, NewList>::result newlist;
  typedef typename reverse<next, newlist>::result result;
};
template<typename NewList>
struct reverse<nil, NewList> {
  typedef NewList result;
};
// remove_if
template<template<class> class Pred, typename List, typename NewList 
= nil>
struct remove_if;
template<template<class> class Pred, typename T, typename N, typename 
NewList>
struct remove_if<Pred, type_list<T, N>, NewList> {
  typedef typename car<type_list<T, N> >::result curr;
  typedef typename cdr<type_list<T, N> >::result next;
  typedef typename select_if<Pred<curr>::result,
                             NewList,
                             typename cons<curr, 
NewList>::result>::result newlist;
  typedef typename remove_if<Pred, next, newlist>::result result;
};
template<template<class> class Pred, typename NewList>
struct remove_if<Pred, nil, NewList> {
  typedef typename reverse<NewList>::result result;
};
struct arg_omit {};
template<typename Type>
struct is_arg_omit : public equal<Type, arg_omit> {};
template<typename A, typename B = arg_omit, typename C = arg_omit, 
typename D = arg_omit,
                     typename E = arg_omit, typename F = arg_omit, 
typename G = arg_omit,
                     typename H = arg_omit, typename I = arg_omit, 
typename J = arg_omit>
struct make_list {
  typedef type_list<A, type_list<B, type_list<C, type_list<D,
                       type_list<E, type_list<F, type_list<G,
                       type_list<H, type_list<I, type_list<J> > > > > 
> > > > > list;
  typedef typename remove_if<is_arg_omit, list>::result result;
};
// Introduce some test types
struct A {};
struct B {};
struct key1 {};
struct key2 {};
struct key3 {};
// Test predicate for remove_if
template<typename Type>
struct is_int_or_char {
  static const bool result = equal<Type, int>::result or equal<Type, 
char>::result;
};
template<typename T>
const char* name(T)        { return "<unknown>"; }
const char* name(char)     { return "char"; }
const char* name(short)    { return "short"; }
const char* name(int)      { return "int"; }
const char* name(long)     { return "long"; }
const char* name(void*)    { return "void*"; }
const char* name(A)        { return "A"; }
const char* name(B)        { return "B"; }
const char* name(nil)      { return "nil"; }
const char* name(arg_omit) { return "arg_omit"; }
template<typename T, typename N>
std::ostream& operator<<(std::ostream& os, type_list<T, N>)
{
  typedef type_list<T, N> list;
  os << name(typename car<list>::result()) << ' ';
  return os << typename cdr<list>::result();
}
std::ostream& operator<<(std::ostream& os, nil)
{
  return os;
}
int main()
{
  // Create list with some types
  typedef make_list<int, short, long, char, void*, nil, int, A, 
B>::result list1;
  // Print length of lists
  std::cout << "Length of nil is " << length<nil>::result << '\n';
  std::cout << "Length of list1 is " << length<list1>::result << '\n';
  // Print members of list1
  std::cout << "Members in list1: " << list1() << '\n';
  // nth<1, list1>
  typedef nth<1, list1>::result r1;
  std::cout << "nth<1, list1> is: " << name(r1()) << '\n';
  // reverse<list1>
  typedef reverse<list1>::result r2;
  std::cout << "Reversed list1: " << r2() << '\n';
  // remove_if<is_int_or_char, list1>
  typedef remove_if<is_int_or_char, list1>::result r3;
  std::cout << "Removed int's and char's: " << r3() << '\n';
  // Create a [key, type] list
  typedef make_list<make_list<key1, int  >::result,
                    make_list<key2, short>::result,
                    make_list<key3, char >::result>::result list2;
  std::cout << "key1 maps to " << cdr<assoc<key1, 
list2>::result>::result() << '\n';
  std::cout << "key2 maps to " << cdr<assoc<key2, 
list2>::result>::result() << '\n';
  std::cout << "key3 maps to " << cdr<assoc<key3, 
list2>::result>::result() << '\n';
}