Sign in to follow this  

Statically typed, lisp-style cons lists in C++ :O

This topic is 4541 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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:
// (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));
}


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]

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
And here's my working code.

#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 >::type
operator,( 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]

Share this post


Link to post
Share on other sites
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? :/

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
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 :) )


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

Share this post


Link to post
Share on other sites
Quote:
Original post by Andrew Russell
Quote:
Original post by Shannon Barber
PS I'm pretty sure you can overload the comma operator.

You can *evil grin*.


And boost assignment library uses it [wink]. Did you know ->* (not * or ->) is overloadable [grin] i'm serious! its called member pointer operator

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
Quote:
Original post by Andrew Russell
Quote:
Original post by Shannon Barber
PS I'm pretty sure you can overload the comma operator.

You can *evil grin*.


And boost assignment library uses it [wink]. Did you know ->* (not * or ->) is overloadable [grin] i'm serious! its called member pointer operator


Not only did I know that, but I have indeed overloaded it. You see, I wanted to be able to use mem_fun_ptr with more than just raw pointers, so I created my own almost an exact clone (I think) of std::mem_fun_ptr that instead returned a structure who's operator() took a template parameter, rather than simply a raw pointer (although one could be provided as the template parameter) like so:
template < typename pointer_type >
result_type operator()( pointer_type pointer ) const {
return (pointer->*function)();
}

Of course, the pointer class in question must overload operator->*, which I found out was extremely nasty. Here's just for allowing ->* to work with zero and one argument functions, out of my cloning_ptr class:
//operator->* for pointer-to-member-0-argument-function
template < typename result_type >
boost::function< result_type ( void ) > operator->*( result_type (value_type::*function)( void ) ) {
return boost::bind( function , pointer );
}

template < typename result_type >
boost::function< result_type ( void ) > operator->*( result_type (value_type::*function)( void ) const ) const {
return boost::bind( function , pointer );
}

//operator->* for pointer-to-member-1-argument-function
template < typename result_type , typename argument_type >
boost::function< result_type ( argument_type ) > operator->*( result_type (value_type::*function)( argument_type ) ) {
return boost::bind( function , pointer );
}

template < typename result_type , typename argument_type >
boost::function< result_type ( argument_type ) > operator->*( result_type (value_type::*function)( argument_type ) const ) const {
return boost::bind( function , pointer );
}





Zahlman: I figured out how to get operator+= working with the left argument remaining a reference - you provide two functions:

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

template < std::size_t size , typename car_t, typename cdar_t, typename cddr_t>
const conslist< const car_t *, conslist<cdar_t, cddr_t> > operator+= (const car_t (&x)[ size ] , const conslist<cdar_t, cddr_t>& y) {
return conslist< const car_t *, conslist<cdar_t, cddr_t> >(x, y);
}




Pretty? No, but it works. You may want to provide a third version with the constness removed:

template < std::size_t size , typename car_t, typename cdar_t, typename cddr_t>
const conslist< car_t *, conslist<cdar_t, cddr_t> > operator+= (car_t (&x)[ size ] , const conslist<cdar_t, cddr_t>& y) {
return conslist< car_t *, conslist<cdar_t, cddr_t> >(x, y);
}


Because otherwise the following will not work (this may or may not be intended):

void do_capitalize( char * c_string ) {
char * i = c_string;
while ( *i ) {
*i = toupper( *i );
++i;
}
}

template < typename T >
void capitalize( const T & l ) {
do_capitalize( l.car() );
capitalize( l.cdr() );
}

template <>
void capitalize( const nil & n ) {}

char foo[] = "...";
char bar_array[] = "...";
char bar * = bar_array;
capitalize( foo += nil() ); //error without non-const version, foo treated like (const char *)
capitalize( bar += nil() ); //ok, bar treated like (char *)


Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
Because otherwise the following will not work (this may or may not be intended):


That was intended; the expectation would be that one would return a new list with the capitalized values: return do_capitalize(l.car()) += capitalize(l.cdr()) (and the nil version returning nil() of course). For better lisp flavour. OTOH, it's probably better C++ flavour not to restrict yourself so arbitrarily :)

Share this post


Link to post
Share on other sites
I don't particularly like Lisp; I find that the purer, early versions are just a poor fit for my thinking, and more elaborate systems are just plain weird. Plus, it's hard to think recursively *all* the time. ;)

Really, I'm just doing it for fun. Although, the static typing here results in significant gains in space efficiency (at the cost of potentially quite a bit of extra generated code) - dynamic typing systems typically get implemented with a lot of pointer trickery.

Share this post


Link to post
Share on other sites
All this talking about lisp in C++ reminds me of my attempt at smalltalk in C++.

Quote:
Originally posted by MaulingMonkey:
int main ( int argc , char ** argv ) {
try {
application_config config;
vector< string > args( argv + 1 , argv + argc );
parse( args ).into( config.wall ); //this line
} catch( const exception & e ) {
report_exception( e );
return 0;
}
}

Share this post


Link to post
Share on other sites

This topic is 4541 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this