// (C) 2005 Karl A. Knechtel (Zahlman)
// This code may be used and modified freely as long as appropriate credit is given.
#include <utility>
#include <iostream>
#include <string>
struct _ {};
template <typename car_t, typename cdr_t>
class conslist {
const std::pair<const car_t, const cdr_t> storage;
public:
conslist(const car_t& x, const cdr_t& y) : storage(std::make_pair(x, y)) {}
const car_t car() const { return storage.first; }
const cdr_t cdr() const { return storage.second; }
bool nilT() const { return false; }
};
template <>
class conslist<_, _> {
public:
conslist<_, _> car() const { return *this; }
conslist<_, _> cdr() const { return *this; }
bool nilT() const { return true; }
};
typedef conslist<_, _> nil;
template <typename car_t>
conslist<car_t, nil> snoc(const car_t& last) {
return conslist<car_t, nil>(last, nil());
}
// Cons an item onto the list. The operator += is used rather than + because
// it has the needed associativity (even though the semantics are completely
// different from what += normally implies).
template <typename car_t, typename cdar_t, typename cddr_t>
const conslist<car_t, conslist<cdar_t, cddr_t> > operator+= (const car_t& x, const conslist<cdar_t, cddr_t>& y) {
return conslist<car_t, conslist<cdar_t, cddr_t> >(x, y);
}
// An example of writing a 'varargs' function using the above framework
template <typename T>
void printRecursively(const T& l, char* space = "") {
// TODO: introspection to ensure that T is a conslist<A, B> for some A and B
std::cout << space << l.car();
printRecursively(l.cdr(), " ");
}
template <>
void printRecursively<nil>(const nil& n, char* space) {
std::cout << "!" << std::endl;
}
// An example of using the function and passing it a conslist
int main() {
// The cast is needed when passing a string literal, because otherwise
// the type is deduced as char[] while the literal is passed as a char*,
// which breaks the templating :(
printRecursively(1 += (const char* const)("hi mom") += std::string("y helo thar") += 1.3f += 4 += nil());
printRecursively(1 += (const char* const)("hi mom") += std::string("y helo thar") += 1.3f += snoc(4));
}
Statically typed, lisp-style cons lists in C++ :O
Author
Check out what I just hacked together in the last hour or so - I've had the idea for a long time, but until now have not given it serious thought:
I suppose this is the very definition of Greenspunning :D The const-ness is deliberately heavy for Lisp-style "referential transparency flavour"; the idea is that input args are supposed to be entirely immutable - this would be used primarily for things like logging functions, as an alternative to "stream" approaches. Note how everything is done in the templates (the nil definition was particularly tricky; I had to play around with it a little to get all the "right" behaviour); compile times and generated code will explode, but there is no memory overhead for the structures whatsoever :)
P.S. In case you are wondering, "snoc" is "cons" backwards; I reversed the Lisp keyword because the call has to come at the end of the list. By using operator += and exploiting its reversed operator associativity, it is possible to write the items in the order that they will appear in the list, even though they have to be added in the reverse of that order (so that the car and cdr will work).
[Edited by - Zahlman on July 5, 2005 8:33:30 PM]
Funky, but cool. The += operator is a little clunky, as is having to add nil or snoc() at the end of a cons list. I'm curious as to why you didn't use a named function for cons?
Have you read 'Modern C++ Design'?
PS I'm pretty sure you can overload the comma operator.
PS I'm pretty sure you can overload the comma operator.
Quote:Original post by Shannon Barber
PS I'm pretty sure you can overload the comma operator.
You can *evil grin*.
Cool, but... well, I think I prefer boost's version. That is, I'd have used the same cons list as the tuples library does.
I'm working seeing if I can't bang up a version that works with operator,
I'm working seeing if I can't bang up a version that works with operator,
hrmmm, how does it go? Something like "at the core of any large project there's a hacked-up, buggy, reimplementation of common LISP".
Google isn't finding it for me. But that's basically the gist of it.
Google isn't finding it for me. But that's basically the gist of it.
And here's my working code.
Compiles and runs as expected on WinXP GCC 3.4.2 (MinGW special) with no errors or warnings.
The add_type_to_cons_list class is fairly ignorable, it's used to allow this code to work with the left-to-right associativity of operator, (this would also work with operator+).
Enjoy :-).
[Edited by - MaulingMonkey on July 4, 2005 11:33:43 PM]
#include <string>#include <iostream>#include <boost/tuple/tuple.hpp>/* Utility class: add_type_to_cons_tail< ... , D > * Converts a type: cons< A , cons< B , cons< C , null_type > > > * Into: cons< A , cons< B , cons< C , cons< D , null_type > > > > * Used in the implementation of operator, */template < typename cons_list_t , typename new_type_t >struct add_type_to_cons_tail { typedef boost::tuples::cons < typename cons_list_t::head_type , typename add_type_to_cons_tail < typename cons_list_t::tail_type , new_type_t >::type > type;};template < typename new_type_t >struct add_type_to_cons_tail< boost::tuples::null_type , new_type_t > { typedef boost::tuples::cons < new_type_t , boost::tuples::null_type > type;};/* Utility function: operator, * Converts a value of type: cons< A , cons< B , cons< C , null_type > > > * Into: cons< A , cons< B , cons< C , cons< D , null_type > > > > */template < typename new_element_t >boost::tuples::cons< new_element_t , boost::tuples::null_type >operator,( const boost::tuples::null_type & , new_element_t new_element ) { return boost::tuples::cons< new_element_t , boost::tuples::null_type >( new_element , boost::tuples::null_type() );}template < typename cons_list_lhs_t , typename cons_list_rhs_t , typename new_element_t >typename add_type_to_cons_tail< boost::tuples::cons< cons_list_lhs_t , cons_list_rhs_t > , new_element_t >::typeoperator,( const boost::tuples::cons< cons_list_lhs_t , cons_list_rhs_t > & list , new_element_t new_element ) { typedef typename add_type_to_cons_tail< cons_list_rhs_t , new_element_t >::type new_cons_list_rhs_t; return boost::tuples::cons< cons_list_lhs_t , new_cons_list_rhs_t >( list.get_head() , (list.get_tail() , new_element) );}/* Example function: print_recursively * Prints out a cons list */template < typename cons_lhs_t , typename cons_rhs_t >void print_recursively( const boost::tuples::cons< cons_lhs_t , cons_rhs_t > & list ) { std::cout << list.get_head() << " "; print_recursively( list.get_tail() );}void print_recursively( boost::tuples::null_type ) { std::cout << "!" << std::endl;}/* Example usage of print_recursively * both with make_tuple(...) and operator, */int main() { print_recursively( boost::tuples::make_tuple( 1 , "hi mom" , std::string("y helo thar") , 1.3f , 4 ) ); print_recursively(( boost::tuples::null_type() , 1 , "hi mom" , std::string("y helo thar") , 1.3f , 4 ));}Compiles and runs as expected on WinXP GCC 3.4.2 (MinGW special) with no errors or warnings.
The add_type_to_cons_list class is fairly ignorable, it's used to allow this code to work with the left-to-right associativity of operator, (this would also work with operator+).
Enjoy :-).
[Edited by - MaulingMonkey on July 4, 2005 11:33:43 PM]
Author
Quote:Original post by sjelkjd
Funky, but cool. The += operator is a little clunky,
Agreed. Overloading the comma operator is cool, but I didn't really want to have to mess around with the associativity - the problem is that in order for car and cdr to be simple, you need the first element of the list to be the least "wrapped", which implies creating the list in reverse order. By using an operator with reverse precedence, you get to do that while still displaying the list in normal order. Otherwise you have to take things apart and put them back together in a rather elaborate way (as MM is brave enough to attempt, with the help of boost::tuple :) )
Quote: as is having to add nil or snoc() at the end of a cons list.
Well, the indication has to go *somewhere* that you're creating a cons list. :)
Quote:I'm curious as to why you didn't use a named function for cons?
Don't know what you mean?
Anyway, does anyone have a fix for the char* literal problem? :/
Quote:Original post by ZahlmanQuote:Original post by sjelkjd
Funky, but cool. The += operator is a little clunky,
Agreed. Overloading the comma operator is cool, but I didn't really want to have to mess around with the associativity - the problem is that in order for car and cdr to be simple, you need the first element of the list to be the least "wrapped", which implies creating the list in reverse order. By using an operator with reverse precedence, you get to do that while still displaying the list in normal order. Otherwise you have to take things apart and put them back together in a rather elaborate way (as MM is brave enough to attempt, with the help of boost::tuple :) )
I use boost::tuple only as a base, all the ripping apart I had to do myself. If I felt like repeating the machoistic attempt, I could create a similar operator for your code :-).
That said, the way I've implemented it is inefficient, something like O(N*N) for adding a single element using "operator,", which equates to something like O(N*N*N) for constructing the entire list.
I'm fairly confident there's a way to optimize it much better, but that's more involved than I want to get.
A few more layers of template metamagic using references should be able to bring operator, down to O(N), and using a temporary cons list in reverse order to be swapped around upon completion (i.e. assignment to temporary or otherwise) like so: cons< C , cons< B , cons< A , null > > > instead of cons< A , cons< B , cons< C , null > > >, if possible, would bring operator, down to O(1).
Quote:Anyway, does anyone have a fix for the char* literal problem? :/
Changing the first argument of operator+= from "const car_t & x" to "const car_t x" seems to fix this for me, doing so allows car_t to be a pointer instead of an array. A better solution would involve more template metamagic...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
