Alp Mestanogullari's Blog

Templates for unique id generation for types : a beginning

Posted in Uncategorized by alpmestan on 2009/10/31

After reading one of the comments on this blog post, I decided to publish here a proof of concept for the generation of unique ids for types.

Basically, it’s just about one template structure, using very basical templates techniques : specialization, metaprogramming-level recursion and nested enum for the computation. Either a familiarity with template metaprogramming or with functional programming is enough to understand the following code.

If you’re familiar with any scheme of functional recursion, or recursion in its mathematical sense, you’ll get it quite easily. Mathematically, we’re somehow defining a recursive function generate_id this way :

generateid(int) = 5
generateid(char) = 7
\forall T,\, generateid(\textit{pointer to T}) = 2 \cdot generateid(T)
\forall T,\, generateid(\textit{ref to T}) = 3 \cdot generateid(T)
\forall T,\, generateid(\textit{vector of T}) = 11 \cdot generateid(T)

Which, in C++, becomes :

template <typename T>
struct id_generator;

template <typename T>
struct id_generator<T*>
{
    enum { result = id_generator<T>::result*2 };
};

template <typename T>
struct id_generator<T&>
{
    enum { result = id_generator<T>::result*3 };
};

template <typename T>
struct id_generator< std::vector<T> >
{
    enum { result = id_generator<T>::result*11 };
};

template <>
struct id_generator<int>
{
    enum { result = 5 };
};

template <>
struct id_generator<char>
{
    enum { result = 7 };
};

And a minimal example of use :

int main()
{
    std::cout << "int : " << id_generator< int >::result << std::endl
              << "char**** : " << id_generator< char**** >::result << std::endl
              << "vector<int> : " << id_generator< std::vector<int> >::result << std::endl;
    return 0;
}
/* Output :
int : 5
char**** : 112
vector<int> : 55
*/

To make it really usable, you’ll have to add much (much much much) more :

  • base types, like int and char here, which help for terminating the recursive call
  • composition rules, like vector, references and pointers here, which help for propagating the recursion

To ensure the uniqueness here, I use prime numbers, simply [1]. Indeed, for the base types, I give a value being a prime number. For the different compositions, I multiply by a different prime number for each. However, most of you may have noticed that the id only lets you know about what type compositions and base types are used, but gives nothing about the order. If we add a rule for std::list, multiplying by 13 for example, then a list of vectors of ints will have the same id as a vector of lists of int. It’d need additional code and workarounds to take the order of the compositions in account — I guess it is possible though. If any reader here comes up with a solution, let us know. A possible solution would be to drop prime numbers, since they rely on a commutative (abelian) ring [2].

[1] http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
[2] http://en.wikipedia.org/wiki/Commutative_ring

Tagged with: , ,

Introduction to SFINAE

Posted in Uncategorized by alpmestan on 2009/10/29

Basically, SFINAE (for the smart guys who can remember the whole name : Substitution Failure Is Not An Error) is what makes this code compile.

struct Test 
{
    typedef int type;
};
 
template < typename T > 
void f( typename T::type ) {} // definition #1
 
template < typename T > 
void f( T ) {}                // definition #2
 
f< Test > ( 10 ); // calls #1 
f< int > ( 10 );  //calls #2 without error, thanks to SFINAE

To make it short (but not too much), if you have several overloads for a function, but particularly one of them being template, then if the template one doesn’t match the call you’re currently doing, the compiler — instead of raising a bright, clear and boring error — will try the other ones. In our case, the first definition of f asks for the type parameter to have a nested type type defined (either via class, struct, enum or typedef). Fortunately, Test has one ! But our lonely int type hasn’t. Again, fortunately, the compiler, thanks to SFINAE, will not issue an error and will call #2.

Ok, you got it, but now wonder how can this be useful ? Okay, imagine we basically are working on a widget library. After a huge amount of work, we came up with the following code :

class label
{
};

class button
{
};

Yeah, impressive, isn’t it ?
Okay, now, say we want to write show functions, to be able to show our two widgets. Basically, we can just write two overloads. But it’ll base the overload resolution on the strict name of the type. What if we rather want the overload resolution to be done using the structure of our type ? For example, depending on the presence of a ‘label_tag’ inner typedef, or ‘button_tag’, for button.

Then,, first, we’d modify our two classes this way :

class label
{
public:
    typedef void label_tag;
};

class button
{
public:
    typedef void button_tag;
};

Then, how can we apply the SFINAE principle here ? Well, here is one way :

template <typename widget_type>
typename widget_type::label_tag show(widget_type& w)
{
    std::cout<< "I'm a label" << std::endl;
}

template <typename widget_type>
typename widget_type::button_tag show(widget_type& w)
{
    std::cout << "I'm a button" << std::endl;
}

And then, the main function and its output :

int main()
{
    label l; 
    button b;
    show(l);
    show(b);
    return 0;
}
/* Output :
 * I'm a label
 * I'm a button
 */

Got it ? ;)

Maybe I’ll dive into more advanced uses of SFINAE (more complex and powerful interface detection) in further posts.

Stay tuned !

Tagged with: , ,

Can I haz teh boost::any C++ class plz ?

Posted in Uncategorized by alpmestan on 2009/10/18

Welcome,

This blog post will be about rewriting the boost::any class. For those of you who don’t know it, it lets you assign a value of any type to your boost::any instance, like in the following code :

boost::any a = 42;
a = "C++";
a = 3.14;
// and so on

First, ok, we must have templates somewhere, since there isn’t any base class of all the possible types, even less when we deal with primitive types. So, our any cass must hold a value than actually can hold any kind of stuffs… Some value_type template class then ! But wait, we must be able to store value_type<int>, value_type<std::string> and so on ! OK, fortunately, type erasure will save us here. We’ll create a base class value_base and then make a template class value_type inherit it.

class value_base
{
	public:
	virtual ~value_base() { }
};

template <class T>
class value_type : public value_base
{
	T t;
	
	public:
	value_type(const T& t_) : t(t_) { }
};

Thus, we can write the any class this way :

class any
{
	value_base* v;
	
	public:
	any() : v(0) { }
	
	template <class value_t>
	any(const value_t& v_) : v(new value_type<value_t>(v_)) { }
	
	~any() { delete v; }
};

Ok, now we miss a copy constructor and an overload for the “=” operator.
We must first add a cloning function in value_base (pure virtual) and value_type for being able to write a good copy constructor.

class value_base
{
  	public:
  	virtual ~value_base() { }
  	virtual value_base* clone() const = 0; /* new */
};

template <class T>
class value_type : public value_base
{
	T t;
	
	public:
	value_type(const T& t_) : t(t_) { }
	value_base* clone() const /* new */
	{
		return new value_type(t);
	}
};

And now, any(const any&) and any& operator=(const any&) can be implemented ;)

class any
{
	value_base* v;
	
	public:
	any() : v(0) { }
	
	template <class value_t>
	any(const value_t& v_) : v(new value_type<value_t>(v_)) { }

        /* new */
	any(any const & other) : v(other.v ? other.v->clone() : 0) {}

        /* new */
	any& operator=(const any& other)
  	{
  		if(&other != this)
  		{
  			any copy(other);
  			swap(copy);
  		}
    	        return *this;
  	}

        /* new */
  	void swap(any& other)
  	{
    	        std::swap(v, other.v);
  	}

	~any() { delete v; }
};

And you’re done !

For those of you who either already knew any or just read a bit its documentation, you may be interested in the any cast functions, that let you get back a value from an any instance. Here is the code (it requires very little modifications to our previous code).

class any;

template <class T>
T any_cast(any& a); // declaration for being able to make classes friend of it 		
		
// value_type template class modification
template <class T>
class value_type : public value_base
{
  	friend T any_cast<>(any& a);
  	// ...
};

// any class modification
class any
{
  	template <class T>
  	friend T any_cast(any& a);
  	// ...
};

// bad_any_cast exception class
class bad_any_cast : public std::exception
{
  	public:
  	const char* what() const throw()
  	{
    	return "Bad any_cast exception";
  	}
};

template <class T>
T any_cast(any& a)
{
  	value_type<T>* v = dynamic_cast<value_type<T>*>(a.v);
  	if(v == 0)
	{
		throw bad_any_cast();
	}
  	else
	{
		return v->t;
	}
}

I haven’t implemented all the cast functions. The ones with constant reference, pointer, and constant pointer are left as exercise for the reader.

Here is a code using all the things we’ve done so far.

int main()
{
  	any a = 42;
  	any b = 'c';
  	std::cout << "[1] a=" << any_cast<int>(a) << " b='" << any_cast<char>(b) << "'" << std::endl;
  	a.swap(b);
  	std::cout << "[2] a='" << any_cast<char>(a) << "' b=" << any_cast<int>(b) << std::endl;
  	try
	{
		std::string s = any_cast<std::string>(b);
	}
  	catch(const std::exception& e)
	{
		std::cout << "[3] " << e.what() << std::endl;
	}
  	any c(a);
  	std::cout << "[4] c='" << any_cast<char>(c) << "'" << std::endl;
  	return 0;
}
/* 
alp@mestan:~/cpp$ g++ -o te3 type_erasure3.cpp
alp@mestan:~/cpp$ ./te3
[1] a=42 b='c'
[2] a='c' b=42	
[3] Bad any_cast exception
[4] c='c'
*/

Enjoy ;)

Tagged with: , ,

A little WIP Haskell editor

Posted in Uncategorized by alpmestan on 2009/10/04
haskelled

haskelled

Tagged with: ,
Follow

Get every new post delivered to your Inbox.

Join 251 other followers