Re: [boost] TypeLISP

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2000-11-30 22:36:47

Just want to note that a cons-list is conceptually similar to the tuple
of the LL, so we probably don't need multiple versions of "cons" in boost,
but it certainly would be good to have the list manipulation operations
shown here. Also, some STL algorithms would be appropriate to rewrite
in terms of these lists.

Cheers,
Jeremy

On Thu, 30 Nov 2000 netterdag_at_[hidden] wrote:

> 
> 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
> 
> //--- begin
> 
> #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 &" << lime(tyr1) << ' '';
> 
>   // ntverse<Nest1>
>   typedef ntverse<Nest1>
>  result r1;2  std::cout << "ntRerse&ldist1: " << lir2 << '\n';
> 
>   // ntmove_if<is_art_or_char {list1>
>   typedef ntmove_if<is_art_or_char {list1>
>  result r1;3  std::cout << "ntReve_idnt, 'snd
> har, '&" << lirest predicate fo;Neld_M;Nes typn]t_or_some types
>   typedef mak  typedef mak};
> svoid* ;T, 
> N> &gtlist<G,
>             typedef mak};
> 2ist<T, 
> N> &gtlist<G,
>             typedef mak};
> 3hort, ;T, 
> N> &gint, A, 
> B>::r2redicult r1;3  std::cout <};
> stmapsbabld
> har, '&" typenat;
> struct};
> svo
> ;::r2T, 
> N> &gint, A, 
> B&glt;< lirest preicult r1;3  std::cout <};
> 2tmapsbabld
> har, '&" typenat;
> struct};
> 2vo
> ;::r2T, 
> N> &gint, A, 
> B&glt;< lirest preicult r1;3  std::cout <};
> 3tmapsbabld
> har, '&" typenat;
> struct};
> 3vo
> ;::r2T, 
> N> &gint, A, 
> B&glt;< lirest pre}
> r=
> 
> 
> 
> 
> 

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------