By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,918 Members | 2,258 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,918 IT Pros & Developers. It's quick & easy.

Lambda Library

P: n/a
How does the lambda library actually works. How does it know how to
evaluate _1, how does it recognize _1 as a placeholder, how does it
then calculate _1+_2, or _1+2 etc. The source files seem a bit
complicated so any explanation would be appreciated.
Thanks

Oct 2 '06 #1
Share this Question
Share on Google+
5 Replies


P: n/a
Octal wrote:
How does the lambda library actually works. How does it know how to
evaluate _1, how does it recognize _1 as a placeholder, how does it
then calculate _1+_2, or _1+2 etc. The source files seem a bit
complicated so any explanation would be appreciated.
Here is a demonstration of some techniques that go into magic like that. The
following only implements _1, operator+, and operator*. Also, it always
assumes functions of one argument.

In this implementation, all types of the form LambdaTag< some_type are
supposed to be functions and all other types are treated as constants that
need to be wrapped.
template < typename Expr >
struct LambdaTag : public Expr {

LambdaTag ( void ) : Expr() {}

template < typename A >
LambdaTag ( A a ) : Expr(a) {}

};

struct proj_one {

template < typename T >
T const & operator() ( T const & t ) const {
return ( t );
}

template < typename T, typename S >
T const & operator() ( T const & t, S const & s ) const {
return ( t );
}

};

static LambdaTag<proj_one_1;
template < typename T >
struct Constant {

T const & value;

Constant ( T const & t_ref )
: value ( t_ref )
{}

T operator() ( void ) const {
return( value );
}

template < typename A >
T operator() ( A const & ) const {
return( value );
}

};

template < typename T >
LambdaTag< Constant<T
wrapper ( T const & t ) {
return ( Constant<T>( t ) );
}
template < typename ExprA, typename ExprB >
struct Sum {

ExprA const & a;
ExprB const & b;

Sum ( ExprA const & a_ref, ExprB const & b_ref )
: a ( a_ref )
, b ( b_ref )
{}

template < typename S >
S operator() ( S const & s ) const {
return ( a(s) + b(s) );
}

};

template < typename ExprA, typename ExprB >
LambdaTag< Sum< ExprA, ExprB
operator+ ( LambdaTag< ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Sum< ExprA, ExprB >( a, b ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Sum< ExprA, Constant<ExprB >
operator+ ( LambdaTag< ExprA const & a, ExprB const & b ) {
return ( Sum< ExprA, Constant<ExprB( a, wrapper(b) ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Sum< Constant<ExprA>, ExprB
operator+ ( ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Sum< Constant<ExprA>, ExprB >( wrapper(a), b ) );
}
template < typename ExprA, typename ExprB >
struct Product {

ExprA const & a;
ExprB const & b;

Product ( ExprA const & a_ref, ExprB const & b_ref )
: a ( a_ref )
, b ( b_ref )
{}

template < typename S >
S operator() ( S const & s ) const {
return ( a(s) * b(s) );
}

};

template < typename ExprA, typename ExprB >
LambdaTag< Product< ExprA, ExprB
operator* ( LambdaTag< ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Product< ExprA, ExprB >( a, b ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Product< ExprA, Constant<ExprB >
operator* ( LambdaTag< ExprA const & a, ExprB const & b ) {
return ( Product< ExprA, Constant<ExprB( a, wrapper(b) ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Product< Constant<ExprA>, ExprB
operator* ( ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Product< Constant<ExprA>, ExprB >( wrapper(a), b ) );
}


#include <iostream>

int main ( void ) {
std::cout << ( ( ( _1 + 6 ) * _1 )( 5 ) ) << '\n';
}

Best

Kai-Uwe Bux
Oct 3 '06 #2

P: n/a
Kai-Uwe Bux wrote:
Octal wrote:
>How does the lambda library actually works. How does it know how to
evaluate _1, how does it recognize _1 as a placeholder, how does it
then calculate _1+_2, or _1+2 etc. The source files seem a bit
complicated so any explanation would be appreciated.

Here is a demonstration of some techniques that go into magic like that.
The following only implements _1, operator+, and operator*. Also, it
always assumes functions of one argument.

In this implementation, all types of the form LambdaTag< some_type are
supposed to be functions and all other types are treated as constants that
need to be wrapped.
[bogus code snipped]

Aaaaargh, that always happens: I never get the lifetime issues straightened
out on the first try. Here is a version that should handle them more
gracefully:

template < typename Expr >
struct LambdaTag : public Expr {

LambdaTag ( void ) : Expr() {}

template < typename A >
LambdaTag ( A a ) : Expr(a) {}

};

struct proj_one {

template < typename T >
T const & operator() ( T const & t ) const {
return ( t );
}

template < typename T, typename S >
T const & operator() ( T const & t, S const & s ) const {
return ( t );
}

};

static LambdaTag<proj_one_1;
template < typename T >
struct Constant {

T value;

Constant ( T const & t )
: value ( t )
{}

T operator() ( void ) const {
return( value );
}

template < typename A >
T operator() ( A const & ) const {
return( value );
}

};

template < typename T >
LambdaTag< Constant<T
wrapper ( T t ) {
return ( Constant<T>( t ) );
}

template < typename Expr >
struct ExprRef {

typedef Expr const & type;

};

template < typename Expr >
struct ExprRef< Constant< Expr {

typedef Constant< Expr type;

};
template < typename ExprA, typename ExprB >
struct Sum {

typename ExprRef< ExprA >::type a;
typename ExprRef< ExprB >::type b;

Sum ( ExprA const & a_ref, ExprB const & b_ref )
: a ( a_ref )
, b ( b_ref )
{}

template < typename S >
S operator() ( S const & s ) const {
return ( a(s) + b(s) );
}

};

template < typename ExprA, typename ExprB >
LambdaTag< Sum< ExprA, ExprB
operator+ ( LambdaTag< ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Sum< ExprA, ExprB >( a, b ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Sum< ExprA, Constant<ExprB >
operator+ ( LambdaTag< ExprA const & a, ExprB const & b ) {
return ( Sum< ExprA, Constant<ExprB( a, wrapper(b) ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Sum< Constant<ExprA>, ExprB
operator+ ( ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Sum< Constant<ExprA>, ExprB >( wrapper(a), b ) );
}
template < typename ExprA, typename ExprB >
struct Product {

typename ExprRef< ExprA >::type a;
typename ExprRef< ExprB >::type b;

Product ( ExprA const & a_ref, ExprB const & b_ref )
: a ( a_ref )
, b ( b_ref )
{}

template < typename S >
S operator() ( S const & s ) const {
return ( a(s) * b(s) );
}

};

template < typename ExprA, typename ExprB >
LambdaTag< Product< ExprA, ExprB
operator* ( LambdaTag< ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Product< ExprA, ExprB >( a, b ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Product< ExprA, Constant<ExprB >
operator* ( LambdaTag< ExprA const & a, ExprB const & b ) {
return ( Product< ExprA, Constant<ExprB( a, wrapper(b) ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Product< Constant<ExprA>, ExprB
operator* ( ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Product< Constant<ExprA>, ExprB >( wrapper(a), b ) );
}


#include <iostream>

int main ( void ) {
std::cout << ( ( ( _1 + 6 ) * _1 )( 5 ) ) << '\n';
}
Now, this prints 55, as it should.
Best

Kai-Uwe Bux
Oct 3 '06 #3

P: n/a
That works pretty nice.
Thanks a lot
Kai-Uwe Bux wrote:
Kai-Uwe Bux wrote:
Octal wrote:
How does the lambda library actually works. How does it know how to
evaluate _1, how does it recognize _1 as a placeholder, how does it
then calculate _1+_2, or _1+2 etc. The source files seem a bit
complicated so any explanation would be appreciated.
Here is a demonstration of some techniques that go into magic like that.
The following only implements _1, operator+, and operator*. Also, it
always assumes functions of one argument.

In this implementation, all types of the form LambdaTag< some_type are
supposed to be functions and all other types are treated as constants that
need to be wrapped.
[bogus code snipped]

Aaaaargh, that always happens: I never get the lifetime issues straightened
out on the first try. Here is a version that should handle them more
gracefully:

template < typename Expr >
struct LambdaTag : public Expr {

LambdaTag ( void ) : Expr() {}

template < typename A >
LambdaTag ( A a ) : Expr(a) {}

};

struct proj_one {

template < typename T >
T const & operator() ( T const & t ) const {
return ( t );
}

template < typename T, typename S >
T const & operator() ( T const & t, S const & s ) const {
return ( t );
}

};

static LambdaTag<proj_one_1;
template < typename T >
struct Constant {

T value;

Constant ( T const & t )
: value ( t )
{}

T operator() ( void ) const {
return( value );
}

template < typename A >
T operator() ( A const & ) const {
return( value );
}

};

template < typename T >
LambdaTag< Constant<T
wrapper ( T t ) {
return ( Constant<T>( t ) );
}

template < typename Expr >
struct ExprRef {

typedef Expr const & type;

};

template < typename Expr >
struct ExprRef< Constant< Expr {

typedef Constant< Expr type;

};
template < typename ExprA, typename ExprB >
struct Sum {

typename ExprRef< ExprA >::type a;
typename ExprRef< ExprB >::type b;

Sum ( ExprA const & a_ref, ExprB const & b_ref )
: a ( a_ref )
, b ( b_ref )
{}

template < typename S >
S operator() ( S const & s ) const {
return ( a(s) + b(s) );
}

};

template < typename ExprA, typename ExprB >
LambdaTag< Sum< ExprA, ExprB
operator+ ( LambdaTag< ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Sum< ExprA, ExprB >( a, b ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Sum< ExprA, Constant<ExprB >
operator+ ( LambdaTag< ExprA const & a, ExprB const & b ) {
return ( Sum< ExprA, Constant<ExprB( a, wrapper(b) ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Sum< Constant<ExprA>, ExprB
operator+ ( ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Sum< Constant<ExprA>, ExprB >( wrapper(a), b ) );
}
template < typename ExprA, typename ExprB >
struct Product {

typename ExprRef< ExprA >::type a;
typename ExprRef< ExprB >::type b;

Product ( ExprA const & a_ref, ExprB const & b_ref )
: a ( a_ref )
, b ( b_ref )
{}

template < typename S >
S operator() ( S const & s ) const {
return ( a(s) * b(s) );
}

};

template < typename ExprA, typename ExprB >
LambdaTag< Product< ExprA, ExprB
operator* ( LambdaTag< ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Product< ExprA, ExprB >( a, b ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Product< ExprA, Constant<ExprB >
operator* ( LambdaTag< ExprA const & a, ExprB const & b ) {
return ( Product< ExprA, Constant<ExprB( a, wrapper(b) ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Product< Constant<ExprA>, ExprB
operator* ( ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Product< Constant<ExprA>, ExprB >( wrapper(a), b ) );
}


#include <iostream>

int main ( void ) {
std::cout << ( ( ( _1 + 6 ) * _1 )( 5 ) ) << '\n';
}
Now, this prints 55, as it should.
Best

Kai-Uwe Bux
Oct 3 '06 #4

P: n/a
Octal wrote:
That works pretty nice.
[snip]

a) Please do not top-post in this news group. It is considered poor form.
Also, please trim your replies to not include material that you do not
refer to.

b) When you understand how the first version works, you might turn your
attention to this one. I added support for _2 and operator<. Also,
determining the result-type of arithmetic operations now has a hook for
improvements (which are omitted for the sake of clarity).

// specialize this for pairs of built in types
// ===========================================

template < typename A, typename B >
struct binary_arithmetic_op {

typedef A type;

};

template < typename A, typename B >
struct binary_comparison_op {

typedef bool type;

};
// expression tagging
// ==================

template < typename Expr >
struct LambdaTag : public Expr {

LambdaTag ( void ) : Expr() {}

template < typename A >
LambdaTag ( A a ) : Expr(a) {}

};
// _1 and _2
// =========

struct proj_one {

template < typename S >
S const & operator() ( S const & s ) const {
return ( s );
}

template < typename S >
struct result_1 {
typedef S type;
};

template < typename S, typename T >
S const & operator() ( S const & s, T const & t ) const {
return ( s );
}

template < typename S, typename T >
struct result_2 {
typedef S type;
};

};

static LambdaTag<proj_one_1;

struct proj_two {

template < typename S >
S const & operator() ( S const & s ) const {
return ( s );
}

template < typename S >
struct result_1 {
typedef S type;
};

template < typename S, typename T >
T const & operator() ( S const & s, T const & t ) const {
return ( t );
}

template < typename S, typename T >
struct result_2 {
typedef T type;
};

};

static LambdaTag<proj_two_2;
// constant expressions
// ====================

template < typename T >
struct Constant {

T value;

Constant ( T const & t )
: value ( t )
{}

T operator() ( void ) const {
return( value );
}

template < typename dummy >
T operator() ( dummy const & ) const {
return( value );
}

template < typename dummy_a, typename dummy_b >
T operator() ( dummy_a const &, dummy_b const & ) const {
return( value );
}

template < typename dummy >
struct result_1 {
typedef T type;
};

template < typename dummy_a, typename dummy_b >
struct result_2 {
typedef T type;
};

};

template < typename T >
LambdaTag< Constant<T
wrapper ( T t ) {
return ( Constant<T>( t ) );
}

template < typename Expr >
struct ExprRef {

typedef Expr const & type;

};

template < typename Expr >
struct ExprRef< Constant< Expr {

typedef Constant< Expr type;

};
// operators
// =========

template < typename ExprA, typename ExprB >
struct Sum {

typename ExprRef< ExprA >::type a;
typename ExprRef< ExprB >::type b;

Sum ( ExprA const & a_ref, ExprB const & b_ref )
: a ( a_ref )
, b ( b_ref )
{}

template < typename S >
struct result_1 {

typedef typename ExprA::template result_1<S>::type type_A;
typedef typename ExprB::template result_1<S>::type type_B;
typedef typename binary_arithmetic_op< type_A, type_B >::type type;

};

template < typename S, typename T >
struct result_2 {

typedef typename ExprA::template result_2<S,T>::type type_A;
typedef typename ExprB::template result_2<S,T>::type type_B;
typedef typename binary_arithmetic_op< type_A, type_B >::type type;

};

template < typename S >
typename result_1<S>::type
operator() ( S const & s ) const {
return ( a(s) + b(s) );
}

template < typename S, typename T >
typename result_2<S,T>::type
operator() ( S const & s, T const & t ) const {
return ( a(s,t) + b(s,t) );
}

};

template < typename ExprA, typename ExprB >
LambdaTag< Sum< ExprA, ExprB
operator+ ( LambdaTag< ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Sum< ExprA, ExprB >( a, b ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Sum< ExprA, Constant<ExprB >
operator+ ( LambdaTag< ExprA const & a, ExprB const & b ) {
return ( Sum< ExprA, Constant<ExprB( a, wrapper(b) ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Sum< Constant<ExprA>, ExprB
operator+ ( ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Sum< Constant<ExprA>, ExprB >( wrapper(a), b ) );
}
template < typename ExprA, typename ExprB >
struct Product {

typename ExprRef< ExprA >::type a;
typename ExprRef< ExprB >::type b;

Product ( ExprA const & a_ref, ExprB const & b_ref )
: a ( a_ref )
, b ( b_ref )
{}

template < typename S >
struct result_1 {

typedef typename ExprA::template result_1<S>::type type_A;
typedef typename ExprB::template result_1<S>::type type_B;
typedef typename binary_arithmetic_op< type_A, type_B >::type type;

};

template < typename S, typename T >
struct result_2 {

typedef typename ExprA::template result_2<S,T>::type type_A;
typedef typename ExprB::template result_2<S,T>::type type_B;
typedef typename binary_arithmetic_op< type_A, type_B >::type type;

};

template < typename S >
typename result_1<S>::type
operator() ( S const & s ) const {
return ( a(s) + b(s) );
}

template < typename S, typename T >
typename result_2<S,T>::type
operator() ( S const & s, T const & t ) const {
return ( a(s,t) * b(s,t) );
}

};

template < typename ExprA, typename ExprB >
LambdaTag< Product< ExprA, ExprB
operator* ( LambdaTag< ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Product< ExprA, ExprB >( a, b ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Product< ExprA, Constant<ExprB >
operator* ( LambdaTag< ExprA const & a, ExprB const & b ) {
return ( Product< ExprA, Constant<ExprB( a, wrapper(b) ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Product< Constant<ExprA>, ExprB
operator* ( ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Product< Constant<ExprA>, ExprB >( wrapper(a), b ) );
}
template < typename ExprA, typename ExprB >
struct Less {

typename ExprRef< ExprA >::type a;
typename ExprRef< ExprB >::type b;

Less ( ExprA const & a_ref, ExprB const & b_ref )
: a ( a_ref )
, b ( b_ref )
{}

template < typename S >
struct result_1 {

typedef typename ExprA::template result_1<S>::type type_A;
typedef typename ExprB::template result_1<S>::type type_B;
typedef typename binary_comparison_op< type_A, type_B >::type type;

};

template < typename S, typename T >
struct result_2 {

typedef typename ExprA::template result_2<S,T>::type type_A;
typedef typename ExprB::template result_2<S,T>::type type_B;
typedef typename binary_comparison_op< type_A, type_B >::type type;

};

template < typename S >
typename result_1<S>::type
operator() ( S const & s ) const {
return ( a(s) < b(s) );
}

template < typename S, typename T >
typename result_2<S,T>::type
operator() ( S const & s, T const & t ) const {
return ( a(s,t) < b(s,t) );
}

};

template < typename ExprA, typename ExprB >
LambdaTag< Less< ExprA, ExprB
operator< ( LambdaTag< ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Less< ExprA, ExprB >( a, b ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Less< ExprA, Constant<ExprB >
operator< ( LambdaTag< ExprA const & a, ExprB const & b ) {
return ( Less< ExprA, Constant<ExprB( a, wrapper(b) ) );
}

template < typename ExprA, typename ExprB >
LambdaTag< Less< Constant<ExprA>, ExprB
operator< ( ExprA const & a, LambdaTag< ExprB const & b ) {
return ( Less< Constant<ExprA>, ExprB >( wrapper(a), b ) );
}
// a little sanity check
// =====================

#include <iostream>
#include <iomanip>

int main ( void ) {
std::cout << ( ( ( _1 + 6 ) * _2 )( 0, 0 ) ) << '\n';
std::cout << ( ( ( _1 + 6 ) * _2 )( 1, 0 ) ) << '\n';
std::cout << ( ( ( _1 + 6 ) * _2 )( 2, 0 ) ) << '\n';
std::cout << ( ( ( _1 + 6 ) * _2 )( 0, 1 ) ) << '\n';
std::cout << ( ( ( _1 + 6 ) * _2 )( 0, 2 ) ) << '\n';
std::cout << ( ( ( _1 + 6 ) * _2 )( 1, 1 ) ) << '\n';
std::cout << std::boolalpha << ( _1 < 2*_2 ) ( 0,0 ) << '\n';
std::cout << std::boolalpha << ( _1 < 2*_2 ) ( 0,1 ) << '\n';
std::cout << std::boolalpha << ( _1 < 2*_2 ) ( 1,0 ) << '\n';
std::cout << std::boolalpha << ( _1 < 2*_2 ) ( 1,1 ) << '\n';
std::cout << std::boolalpha << ( _1 < 2*_2 ) ( 1,2 ) << '\n';
std::cout << std::boolalpha << ( _1 < 2*_2 ) ( 2,0 ) << '\n';
std::cout << std::boolalpha << ( _1 < 2*_2 ) ( 2,1 ) << '\n';
std::cout << std::boolalpha << ( _1 < 2*_2 ) ( 2,2 ) << '\n';
}

// end of file
Best

Kai-Uwe Bux
Oct 3 '06 #5

P: n/a
Octal wrote:
How does the lambda library actually works. How does it know how to
evaluate _1, how does it recognize _1 as a placeholder, how does it
then calculate _1+_2, or _1+2 etc. The source files seem a bit
complicated so any explanation would be appreciated.
Sorry for the long post: I somehow got into this, and it just would not let
go of me. Here is a toy implementation of some core functionality found in
boost::lambda together with a little bit of explanation as to how one can
go about doing stuff like this. It is considerably easier than the Boost
implementation but it is still tricky (and about 600 lines of code proper
and 300 lines of comment). I tried to chop it into digestable pieces with
some fairly extensive big picture comments at the beginning. Later, the
code is supposed to convey most of what is going on.

Hope it helps. Criticism is very welcome.
Best

Kai-Uwe Bux
// lambda.cc (C) Kai-Uwe Bux [2006]
// ================================
/*
This file tries to explain basic techniques for expression
templates. For concreteness, we re-implement parts of the
lambda library from Boost. This is by no means intended to
be used as a replacement. It is for instruction only: many
issues have been simplified at the cost of generality and
customizability.
*/

// Section I: enter lambda-expressions
// ===================================
/*
| The goal is that we can write something like
|
| std::remove_if( vec.begin(), vec.end(), _1 < 5 );
|
| Thus, we want the expression '_1 < 5' to evaluate to a
| function object that can be called with one argument.
|
| At the same time, we want
|
| std::sort( vec.begin(), vec.end(), _2 < _1 );
|
| So, we want expressions like '_2 < _1' to evaluate to
| something that can be called with two arguments.
|
| We will introduce a class of types/objects that we refer
| to as lamdba-expressions. They are characterized by the
| fact that they can be called with one or two arguments of
| undeterminate type. Thus, the basic outline for a class
| that qualifies as a lambda-expression will be that it
| conforms to the following concept:
|
| class lamda_expression {
|
| template < typename S >
| struct result_1 {
| typedef some_type_depending_on_S res_type;
| };
|
| template < typename S >
| typename result_1<S>::res_type
| operator() ( S ) const;
|
| template < typename S, typename T >
| struct result_2 {
| typedef some_type_depending_on_S_and_T res_type;
| };
|
| template < typename S >
| typename result_1<S>::res_type
| operator() ( S, T ) const;
|
| };
|
| The member-templates result_1 and result_2 describe how the
| result type varies with the argument types (note that an object
| like _1 has to be able to evaluate to the first coordinate of
| any argument list ( S s, T t ). The templated operator() members
| realize the actual mapping.
|
| As a special rule, we allow that some lambda-expressions only
| implement result_2 and the two argument operator() template: it
| just does not make sense to call _2 with only one parameter since
| it means projection on the second coordinate and we want a
| compile time error if someone tries.
*/

// Section II: expression tagging
// ==============================
/*
| Let us consider again the expression '_1 < 5'. The result shall be
| a lambda-expression. However, we cannot do anything about the way the
| compiler interprets 5: it will be an int. Thus, _1 has to perform
| all the magic. If we had '( _1 * 5 ) < 20', the sub-expression
| '_1 * 5' would have to be as magical.
|
| Here is where tagging enters the scene. All types that qualify
| as lambda-expressions will be of the form
|
| LambdaTag< some_underlying_type >
|
| where LambdaTag is very simple template. Here is the basic outline:
|
| template < typename Expr >
| struct LambdaTag : public Expr {
|
| LambdaTag ( void ) : Expr () {}
|
| template < typename A LambdaTag ( A a ) : Expr ( a ) {}
|
| };
| This is not quite correct due to member operators that we need
| to provide. But the basic idea is that this is just a wrapper.
*/

namespace lambda {

template < typename Expr >
struct LambdaTag;

} // namespace lambda

/*
| To see, how this helps, let us consider the implementation of operator*:
| We will define five version of multiplication:
|
| template < typename ExprA, typename ExprB >
| LambdaTag< Product< ExprA, ExprB
| operator* ( LambdaTag< ExprA const &, LambdaTag< ExprB const & );
|
| template < typename ExprA, typename ExprB >
| LambdaTag< Product< Constant<ExprA>, ExprB
| operator* ( ExprA const &, LambdaTag< ExprB const & );
|
| template < typename ExprA, typename ExprB >
| LambdaTag< Product< Reference<ExprA>, ExprB
| operator* ( ExprA &, LambdaTag< ExprB const & );
|
| template < typename ExprA, typename ExprB >
| LambdaTag< Product< ExprA, Constant< ExprB >
| operator* ( LambdaTag< ExprA const &, ExprB const &);
|
| template < typename ExprA, typename ExprB >
| LambdaTag< Product< Reference<ExprA>, ExprB
| operator* ( LambdaTag< ExprA const &, ExprB & );
|
| Now it is clear that '5 * 7* will not match any of these,
| but as soon as one operand qualifies as a lambda-expression, we
| have a match.
*/
// Section III: handling member operators
// ======================================
/*
| The above method of defining operator* works fine for operators that
| can be implemented as free standing functions. However, some operators
| like the subscripting operator[] or the dereferencing operator* can
| only be implemented as non-static member functions. This effectively
| means that we have to enlarge the concept for lambda-expressions:
|
| class lamda_expression {
|
| template < typename S >
| struct result_1 {
| typedef some_type_depending_on_S res_type;
| };
|
| template < typename S >
| typename result_1<S>::res_type
| operator() ( S ) const;
|
| template < typename S, typename T >
| struct result_2 {
| typedef some_type_depending_on_S_and_T res_type;
| };
|
| template < typename S >
| typename result_1<S>::res_type
| operator() ( S, T ) const;
|
| some_type operator* ( void );
| some_type operator* ( void ) const;
| // more for other operators.
| };
|
| We will restrict ourselves to the dereferencing operator.
|
| The idea is that *( some_lambda_expression ) should return yet
| another lambda expression. Thus, we introduce the template
|
| template < typename Expr >
| struct Dereference {
| Expr underlying_lambda_expression;
|
| Derefence ( Expr from )
| : underlying_lambda_expression ( from )
| {}
|
| template < ... >
| result_type_magic
| operator ( ... ) {
| return ( * ( underlying_lambda_expression( ... ) ) );
| }
|
| // more stuff from the lambda-expression concept
| };
|
| and now, every lambda expression just will implement operator*
| as follows:
|
| class lambda_expression {
|
| //...
|
| LambdaTag< Dereference< lambda_expression
| operator* ( void ) const {
| return ( *this );
| }
|
| };
|
| Unfortunately, this is over-simplified: we cannot in general store a
| copy of the underlying lambda-expression. In fact, some will be stored
| by value, some by const reference and some y reference. Thus, we need
| a policy for that kind of decisson first. This leads us to a template
| governing storage policies. Generally, lambda-expressions will be
| passed on by constand reference.
*/

namespace lambda {

// storage policies
// ================

template < typename Expr >
struct ExprRef {
typedef Expr const & storage_type;
typedef Expr const & init_type;
};

template < typename Expr >
struct ExprRef< LambdaTag< Expr {
typedef Expr const & storage_type;
typedef Expr const & init_type;
};

// support for dereferencing operator*
// ===================================

template < typename T >
struct dereference_op;

template < typename T >
struct dereference_op < T * {
typedef T & res_type;
};

template < typename T >
struct dereference_op < T const * {
typedef T const & res_type;
};

template < typename ExprA >
struct Dereference {

typename ExprRef< ExprA >::storage_type a;

Dereference ( typename ExprRef<ExprA>::init_type a_ )
: a ( a_ )
{}

template < typename S >
struct result_1 {
typedef typename ExprA::template result_1 < S >::res_type res_type_A;
typedef typename dereference_op < res_type_A >::res_type res_type;
};

template < typename S, typename T >
struct result_2 {
typedef typename ExprA::template result_2 <S,T>::res_type res_type_A;
typedef typename dereference_op < res_type_A >::res_type res_type;
};

template < typename S >
typename result_1 < S >::res_type
operator () ( S const &s ) const {
return ( * ( a ( s ) ) ) ;
}

template < typename S, typename T >
typename result_2 < S, T >::res_type
operator () ( S const &s, T const &t ) const {
return ( * ( a ( s, t ) ) ) ;
}

LambdaTag< Dereference< Dereference
operator* ( void ) const {
return ( *this );
}

}; // Dereference

} // namespace lambda
// Section IV: the LambdaTag implementation
// ========================================

namespace lambda {

template < typename Expr >
struct LambdaTag : public Expr {

LambdaTag ( void ) : Expr () {}

template < typename A LambdaTag ( A a ) : Expr ( a ) {}

LambdaTag< Dereference< Expr
operator* ( void ) const {
return( *this );
}

}; // LambdaTag

} // namespace lambda
// Section V: integrating non-lambda-expressions
// =============================================
/*
| Let us consider an expression like '_1 * 5'. Above, we said
| that operator*( LambdaTag<type_of_1>, int const & ) should
| match. It will return an object of type
|
| LambdaTag< Product< type_of_1, Constant<int >
|
| and one might wonder, why a simple
|
| LambdaTag< Product< type_of_1, int
|
| would not suffice. The answer lies in the definition of the Product
| template:
|
| template < typename ExprA, typename ExprB >
| struct Product {
| ExprA a; // warning: this is a lie.
| ExprB b; // warning: this is a lie.
|
| template < typename S >
| result_type_magic
| operator() ( S s ) const {
| return ( a(s) * b(s) );
| }
|
| // more stuff
| };
|
| Now we see that we want to say b(something) and 5(something) will
| not do: int does not overload operator() for us. Thus, we provide
| the wrapper Constant<intthat turns the int 5 into the int valued
| function that always returns 5.
|
| The template Reference<does the same thing for expressions that
| match, say, operator*( LambdaTag<type_of_1>, int & ).
*/

namespace lambda {

template < typename T >
struct Constant {

T value;

Constant ( T const & t ) : value ( t ) {}

template < typename dummy struct result_1 {
typedef T res_type;
};

template < typename dummy_a, typename dummy_b struct result_2 {
typedef T res_type;
};
T operator () ( void ) const {
return ( value ) ;
}

template < typename dummy >
typename result_1 < dummy >::res_type
operator () ( dummy const & ) const {
return ( value ) ;
}

template < typename dummy_a, typename dummy_b >
typename result_2 < dummy_a, dummy_b >::res_type
operator () ( dummy_a const &, dummy_b const & ) const
{
return ( value ) ;
}

}; // Constant
template < typename T >
Constant < T const_wrapper ( T const & t ) {
return ( t ) ;
}

/*
We have to specialize the storage policy for Constants:
*/
template < typename Expr >
struct ExprRef < Constant< Expr {
typedef Constant< Expr storage_type;
typedef Constant< Expr init_type;
};

template < typename T >
struct Reference {

T & value;

Reference ( T & t ) : value ( t ) {}

T & operator () ( void ) const {
return ( value ) ;
}

template < typename dummy struct result_1 {
typedef T & res_type;
};

template < typename dummy_a, typename dummy_b struct result_2 {
typedef T res_type;
};

template < typename dummy >
typename result_1< dummy >::res_type
operator () ( dummy const & ) const {
return ( value ) ;
}

template < typename dummy_a, typename dummy_b >
typename result_2< dummy_a, dummy_b >::res_type
operator () ( dummy_a const &, dummy_b const & ) const {
return ( value ) ;
}

template < typename dummy >
typename result_1< dummy >::res_type
operator () ( dummy const & ) {
return ( value ) ;
}

template < typename dummy_a, typename dummy_b >
typename result_2< dummy_a, dummy_b >::res_type
operator () ( dummy_a const &, dummy_b const & ) {
return ( value ) ;
}

}; // Reference

template < typename T >
Reference< T wrapper ( T & t ) {
return ( t ) ;
}

/*
We have to specialize the storage policy for References:
*/
template < typename Expr >
struct ExprRef < Reference< Expr {
typedef Reference< Expr storage_type;
typedef Reference< Expr init_type;
};

} // namespace lambda

#include <iostream>
// Section VI: result type deduction for operators
// ===============================================
/*
So far, we have referred to result_type_magic in a few places.
The following templates are the nuts and bolts for what goes
under the hood of that kind of magic.
*/

namespace lambda {

// result type deduction
// =====================
/*
specialize these for pairs of (built-in) types
*/

template < typename A >
struct strip_ref {
typedef A type;
};

template < typename A >
struct strip_ref< A & {
typedef A type;
};
template < typename A >
struct unary_arithmetic_op {
typedef typename strip_ref<A>::type res_type;
};

template < typename A >
struct unary_logic_op {
typedef typename strip_ref<A>::type res_type;
};

template < typename A, typename B >
struct binary_arithmetic_op {
typedef typename strip_ref<A>::type res_type;
};

template < typename A, typename B >
struct binary_comparison_op {
typedef bool res_type;
};
/*
specializations for iostreams:
(no reference stripping!)
*/
template < typename A >
struct binary_arithmetic_op< std::ostream&, A {
typedef std::ostream& res_type;
};

template < typename A >
struct binary_arithmetic_op< std::istream&, A {
typedef std::istream& res_type;
};

} // namespace lambda
// Section VII: the magic constants _1 and _2
// ==========================================
/*
| Finally, we are ready to introduce the two most simple
| lambda-expressions in this code: projections onto the
| arguments.
*/

// Section VII A: _1
// =================
/*
| This is the projection onto the first coordinate. I.e., we want
| the members
|
| template < typename S >
| S operator ( S s ) const { return s; }
|
| template < typename S, typename T >
| S operator ( S s, T t ) const { return s; }
|
| The rest is machinery to make it a nice citizen among the
| lambda-expressions (i.e., make it participate in result-type
| deduction).
*/
namespace lambda {

struct proj_1 {

template < typename S >
struct result_1 {
typedef S res_type;
};

template < typename S, typename T >
struct result_2 {
typedef S res_type;
};

template < typename S >
typename result_1 < S const & >::res_type
operator () ( S const & s ) const {
return ( s ) ;
}

template < typename S >
typename result_1 < S & >::type
operator () ( S & s ) const {
return ( s ) ;
}

template < typename S, typename T >
typename result_2 < S const & , T const & >::res_type
operator () ( S const & s, T const & t ) const {
return ( s ) ;
}

template < typename S, typename T >
typename result_2 < S & , T const & >::res_type
operator () ( S & s, T const & t ) const {
return ( s ) ;
}

}; // proj_1

static LambdaTag< proj_1 _1_obj;

} // namespace lambda

static lambda::LambdaTag< lambda::proj_1 const & _1 = lambda::_1_obj;
// Section VII B: _2
// =================
/*
| This is projection onto the second coordinate. This is inherently
| a function that always requires two arguments.
*/
namespace lambda {

// the type of _2
// ==============

struct proj_2 {

template < typename S, typename T >
struct result_2 {
typedef T res_type;
};

template < typename S, typename T >
typename result_2 < S, T const & >::res_type
operator () ( S const & s, T const & t ) const {
return ( t ) ;
}

template < typename S, typename T >
typename result_2 < S, T & >::type
operator () ( S const & s, T & t ) const {
return ( t ) ;
}

}; // proj_2

static LambdaTag< proj_2 _2_obj;

} // namespace lambda

static lambda::LambdaTag< lambda::proj_2 const & _2 = lambda::_2_obj;
// Section VIII: implementing freestanding unary operators
// ================================================== =====
/*
| This is one of the few places where macros increase the
| maintainability of code.
|
| This is the part, where all the pieces come together.
| Note in particular how the member templates result_1
| and result_2 use the result-type deduction helpers from
| above. (Those are passed as the op_type parameter to
| the macro.)
*/

namespace lambda {

#define KUBUX_LAMBDA_UNARY_OP( op, op_type, name ) \
template < typename ExprA \
struct name; \
\
template < typename ExprA \
LambdaTag < name< ExprA \
operator op ( LambdaTag < ExprA const & a ) \
{ \
return ( name< ExprA >( a ) ) ; \
} \
\
template < typename ExprA \
struct name { \
\
typename ExprRef< ExprA >::storage_type a; \
\
name ( typename ExprRef<ExprA>::init_type a_ ) \
: a ( a_ ) \
{} \
\
template < typename S \
struct result_1 { \
typedef \
typename ExprA::template result_1<S>::res_type \
res_type_A; \
typedef \
typename op_type< res_type_A >::res_type \
res_type; \
}; \
\
template < typename S, typename T \
struct result_2 { \
typedef \
typename ExprA::template result_2<S,T>::res_type \
res_type_A; \
typedef \
typename op_type < res_type_A >::res_type \
res_type; \
}; \
\
template < typename S \
typename result_1<S>::res_type \
operator () ( S const & s ) const \
{ \
return ( op( a(s) ) ); \
} \
\
template < typename S, typename T \
typename result_2<S,T>::res_type \
operator () ( S const & s, T const & t ) const \
{ \
return ( op( a(s,t) ) ); \
} \
\
} \

KUBUX_LAMBDA_UNARY_OP( !, unary_logic_op, Not );
KUBUX_LAMBDA_UNARY_OP( -, unary_arithmetic_op, Minus );

#undef KUBUX_LAMBDA_UNARY_OP

} // namespace lambda
// Section IX:: implementing freestanding binary operators
// ================================================== =====
/*
| We use again a macro. This time it pays off even more.
|
| Here we have to take care of five versions of the
| free standing operator since there are 5 admissible
| combinations of argument types where at least one
| argument is a lambda-expression.
*/

namespace lambda {

#define KUBUX_LAMBDA_BINARY_OP( op, op_type, name ) \
template < typename ExprA, typename ExprB \
struct name; \
\
\
template < typename ExprA, typename ExprB \
LambdaTag < name< ExprA, ExprB \
operator op ( LambdaTag < ExprA const & a, \
LambdaTag < ExprB const & b ) \
{ \
return ( name< ExprA, ExprB >( a, b ) ) ; \
} \
\
template < typename ExprA, typename ExprB \
LambdaTag < name< Constant< ExprA >, ExprB \
operator op ( ExprA const & a, LambdaTag< ExprB const & b ) \
{ \
return ( name< Constant< ExprA >, ExprB \
( const_wrapper(a) ,b ) ); \
} \
\
template < typename ExprA, typename ExprB \
LambdaTag < name< ExprA, Constant< ExprB \
operator op ( LambdaTag < ExprA const & a, ExprB const & b ) \
{ \
return ( name< ExprA, Constant< ExprB \
( a, const_wrapper(b) ) ) ; \
} \
\
template < typename ExprA, typename ExprB \
LambdaTag < name< Reference< ExprA >, ExprB \
operator op ( ExprA & a, LambdaTag< ExprB const & b ) \
{ \
return ( name< Reference<ExprA>, ExprB \
( wrapper(a), b ) ); \
} \
\
template < typename ExprA, typename ExprB \
LambdaTag < name< ExprA, ExprB & \
operator op ( LambdaTag < ExprA const & a, ExprB & b ) \
{ \
return ( name< ExprA, Reference<ExprB \
( a, wrapper(b) ) ) ; \
} \
\
template < typename ExprA, typename ExprB \
struct name { \
\
typename ExprRef< ExprA >::storage_type a; \
typename ExprRef< ExprB >::storage_type b; \
\
name ( typename ExprRef<ExprA>::init_type a_, \
typename ExprRef<ExprB>::init_type b_ ) \
: a ( a_ ) \
, b ( b_ ) \
{} \
\
template < typename S \
struct result_1 { \
typedef \
typename ExprA::template result_1<S>::res_type \
res_type_A; \
typedef \
typename ExprB::template result_1<S>::res_type \
res_type_B; \
typedef \
typename op_type< res_type_A, res_type_B >::res_type \
res_type; \
}; \
\
template < typename S, typename T \
struct result_2 { \
typedef \
typename ExprA::template result_2<S,T>::res_type \
res_type_A; \
typedef \
typename ExprB::template result_2<S,T>::res_type \
res_type_B; \
typedef \
typename op_type < res_type_A, res_type_B >::res_type \
res_type; \
}; \
\
template < typename S \
typename result_1<S>::res_type \
operator () ( S const & s ) const \
{ \
return ( a(s) op b(s) ); \
} \
\
template < typename S, typename T \
typename result_2<S,T>::res_type \
operator () ( S const & s, T const & t ) const \
{ \
return ( a(s,t) op b(s,t) ); \
} \
\
} \

KUBUX_LAMBDA_BINARY_OP( -, binary_arithmetic_op, Difference );
KUBUX_LAMBDA_BINARY_OP( +, binary_arithmetic_op, Sum );
KUBUX_LAMBDA_BINARY_OP( *, binary_arithmetic_op, Product );
KUBUX_LAMBDA_BINARY_OP( /, binary_arithmetic_op, Quotient );
KUBUX_LAMBDA_BINARY_OP( %, binary_arithmetic_op, Remainder );
KUBUX_LAMBDA_BINARY_OP( <<, binary_arithmetic_op, LeftShift );
KUBUX_LAMBDA_BINARY_OP( >>, binary_arithmetic_op, RightShift );
KUBUX_LAMBDA_BINARY_OP( &, binary_arithmetic_op, BitWiseAnd );
KUBUX_LAMBDA_BINARY_OP( |, binary_arithmetic_op, BitWiseOr );
KUBUX_LAMBDA_BINARY_OP( ^, binary_arithmetic_op, BitWiseXor );
KUBUX_LAMBDA_BINARY_OP( &&, binary_arithmetic_op, And );
KUBUX_LAMBDA_BINARY_OP( ||, binary_arithmetic_op, Or );
KUBUX_LAMBDA_BINARY_OP( <, binary_comparison_op, Less );
KUBUX_LAMBDA_BINARY_OP( >, binary_comparison_op, Greater );
KUBUX_LAMBDA_BINARY_OP( ==, binary_comparison_op, Equal );
KUBUX_LAMBDA_BINARY_OP( !=, binary_comparison_op, NotEqual );
KUBUX_LAMBDA_BINARY_OP( <=, binary_comparison_op, LessEqual );
KUBUX_LAMBDA_BINARY_OP( >=, binary_comparison_op, GreaterEqual );

#undef KUBUX_LAMBDA_BIN_OP

} // namespace lambda
// Section X: a little sanity check
// ================================
/*
| Although the above certainly contains bazillions of bugs,
| it seems to pass few innocent checks.
*/

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

int main ( void ) {
std::cout << ( ( ( _1 - 6 ) * ( _2 << 2 ) )( 0, 1 ) ) << '\n';
std::cout << ( ( ( _1 + 6 ) * _2 )( 1, 0 ) ) << '\n';
std::cout << ( ( ( _1 + 6 ) * _2 )( 2, 0 ) ) << '\n';
std::cout << ( ( ( _1 + 6 ) * ( _2 << 2 ) )( 0, 1 ) ) << '\n';
std::cout << ( ( ( _1 + 6 ) * _2 )( 0, 2 ) ) << '\n';
std::cout << ( ( ( _1 + 6 ) * _2 )( 1, 1 ) ) << '\n';
std::cout << std::boolalpha << ( ( _1 < 2 * _2 )( 0, 0 ) ) << '\n';
std::cout << std::boolalpha << ( ( _1 < 2 * _2 )( 0, 1 ) ) << '\n';
std::cout << std::boolalpha << ( ( _1 < 2 * _2 )( 1, 0 ) ) << '\n';
std::cout << std::boolalpha << ( ( _1 < 2 * _2 )( 1, 1 ) ) << '\n';
std::cout << std::boolalpha << ( ( _1 < 2 * _2 )( 1, 2 ) ) << '\n';
std::cout << std::boolalpha << ( ( _1 < 2 * _2 )( 2, 0 ) ) << '\n';
std::cout << std::boolalpha << ( ( _1 < 2 * _2 )( 2, 1 ) ) << '\n';
std::cout << std::boolalpha << ( ( _1 >= 2 * _2 )( 2, 2 ) ) << '\n';

int *ip = new int ( 5 ) ;
std::cout << ( *_2 + 7 )( 7, ip ) << '\n';

std::vector < int *>iv;
iv.push_back ( new int ( 3 ) ) ;
iv.push_back ( new int ( 2 ) ) ;
iv.push_back ( new int ( 1 ) ) ;
iv.push_back ( new int ( 5 ) ) ;
iv.push_back ( new int ( 4 ) ) ;
std::sort ( iv.begin () , iv.end () , ! ( *_2 <= *_1 ) ) ;
std::for_each( iv.begin(), iv.end(), std::cout << *_1 << ' ' );
std::cout << '\n';

// BEWARE: OS is supposed to reclaim newed memory.
}

// end of file

Oct 4 '06 #6

This discussion thread is closed

Replies have been disabled for this discussion.