Re: Who discovered the type erasure technique in C++?
on Wed Aug 20 2008, "Roshan Naik" <naikrosh-AT-gmail.com> wrote:
{ Edits: top-posting rearranged. Roshan: please don't top-post in this
group
(see the FAQ). -mod }
On Tue, 19 Aug 2008 14:18:15 -0700, Marco Manfredini
<ok_nospam_ok@phoyd.net> wrote:
If defined that way, then "type erasure" is an attempt to copy
Haskell's type classes, introduced 1989 by Wadler & Blott.
Marco
Im not a Haskell expert but ... Type classes are much closer to Concepts
in C++0x. A type class is not a concrete type but a category of types. But
boost::function and castor::relation are concrete types which can be
instantiated.
I'm also not a Haskell expert, but IIUC...
The interesting thing is that Type classes in Haskell are implemented
using type erasure -- a "vtable" is built each time a distinct function
template is instantiated. The most important result is that --- unlike
with C++ concepts --- haskell typeclasses can't call specializations the
way that binary_search calls a more efficient implementation of advance
for random access iterators. In Haskell, once the type information is
gone, it's gone.
Here's a sketch of some C++ that implements a Haskell-style generic
for_each.
struct for_each_concepts
{
// Forward Iterator
void (*iter_copy)(void const* src, void* dst);
bool (*iter_not_equal)(void const*, void const*);
void (*iter_destroy)(void const*);
void* (*iter_deref)(void const*);
void (*iter_inc)(void*);
// Unary Function
void (*finvoke)(void const*f, void* arg);
};
template <class T>
bool not_equal(void const* x, void const* y)
{
return *static_cast<T const*>(x)
!= *static_cast<T const*>(y);
}
template <class T>
void* deref(void const* x)
{
return &**static_cast<T const*>(x);
}
template <class T>
void inc(void* x)
{
++*static_cast<T*>(x);
}
template <class T>
void copy(void const* src, void* dst)
{
new (dst) T(
*static_cast<T const*>(src));
}
template <class T>
void destroy(void const* x)
{
static_cast<T const*>(x)->~T();
}
template <class F, class A>
void finvoke(void const* f, void* arg)
{
( *static_cast<F const*>(f) )(
*static_cast<A*>(arg) );
}
template <class ForwardIterator, class UnaryFunction>
inline void for_each(
ForwardIterator const& start, ForwardIterator const& finish,
UnaryFunction const& f
)
{
typedef ForwardIterator fi;
static for_each_concepts const models = {
copy<fi>, not_equal<fi>, destroy<fi>, deref<fi>, inc<fi>
, finvoke< UnaryFunction, typename std::iterator_traits<fi>::value_type>
};
aligned_storage< alignment_of<fi>::value, sizeof(fi) > storage;
for_each_impl( &start, &finish, &f, storage.address(), models );
}
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]