Weblogs Forum - C++ Meta-Binders

Articles |
News |
Weblogs |
Books |
Forums

Artima Forums | Articles | Weblogs | Java Answers | News

Sponsored Link •

Weblogs Forum
C++ Meta-Binders

8 replies on 1 page. Most recent reply: May 25, 2005 7:50 AM by Terje Slettebø

Welcome Guest
Sign In

Back to Topic List

Reply to this Topic

Search Forum

Threaded View


Previous Topic		Next Topic

Flat View: This topic has 8 replies on 1 page

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

C++ Meta-Binders (View in Weblogs)

Posted: May 22, 2005 5:36 PM

Summary
The C++ functional header provides a way to bind values to function arguments. Here is a way to bind functions to function arguments using a technique I'm calling meta-binders for lack of a better term.

Here is a problem: given two vectors of booleans:

    std::vector<bool> v1;
    std::vector<bool> v2;

    v1.push_back(true);
    v1.push_back(true);
    v1.push_back(false);
    v1.push_back(false);
    v2.push_back(true);
    v2.push_back(false);
    v2.push_back(true);
    v2.push_back(false);

You can easily create a third vector which is the result of and-ing the values in the first vector with the values in the second vector as follows:

    std::vector<bool> v3;
    std::transform(
      v1.begin(),
      v1.end(),
      v2.begin(),
      std::back_inserter(v3),
      std::logical_and<bool>()
    );

If you want to do the same thing but instead apply a logical xor operation you would have to define a new binary predicate since the STL does not provide one:

  bool logical_xor(bool x, bool y) {
    return (x || y) && !(x && y);
  }

  std::vector<bool> v3;
  std::transform(
    v1.begin(),
    v1.end(),
    v2.begin(),
    std::back_inserter(v3),
    std::logical_xor()
  );

Even though this is easy enough, it brings up the question, can we create a predicate from existing predicates without declaring a new function or function object. The standard library isn't much help but it is possible if we introduce the concept of a meta-binder. A meta-binder binds function to the arguments of another function. An xor function could then be define inline as follows:

  std::vector<bool> v3;
  std::transform(
    v1.begin(),
    v1.end(),
    v2.begin(),
    std::back_insert(v3),
    meta_bind2(
      std::logical_and<bool>(),
      std::logical_or<bool>(),
      std::not2(std::logical_and<bool>())
    )
  );

Here is the meta-binder code for binding two binary functions to the arguments of another binary function object:

  template<class BinOp, class BinOpArg1, class BinOpArg2>
  class meta_binder2 : public std::binary_function
    <
      typename BinOp::first_argument_type,
      typename BinOp::second_argument_type,
      typename BinOp::result_type
    >
  {
    protected:
      BinOp op;
      BinOpArg1 arg1;
      BinOpArg2 arg2;
    public:
      meta_binder2(BinOp x, BinOpArg1 a1, BinOpArg2 a2) : op(x), arg1(a1), arg2(a2)
      { }
      typename BinOp::result_type operator()
      (const typename BinOp::first_argument_type& x,
       const typename BinOp::second_argument_type& y)
      {
        return op(arg1(x, y), arg2(x, y));
      }
  };

  template<class BinOp, class BinOpArg1, class BinOpArg2>
  meta_binder2<BinOp, BinOpArg1, BinOpArg2>
  meta_bind2(BinOp op, BinOpArg1 arg1, BinOpArg2 arg2) {
    return meta_binder2<BinOp, BinOpArg1, BinOpArg2>(op, arg1, arg2);
  }

I would be curious if there is an existing name for this technique, probably those more familiar with higher-order functional programming will have some good nomenclature for me.

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: C++ Meta-Binders

Posted: May 23, 2005 4:50 AM

Oooh, I get to be the first to comment. ;)

You may want to look into Boost.Lambda for this. Using it, your example may be written as (tested on g++ 3.2):

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <boost/lambda/lambda.hpp>

using boost::lambda::_1;
using boost::lambda::_2;

int main()
{
std::vector<int> v1;
std::vector<int> v2;

v1.push_back(true);
v1.push_back(true);
v1.push_back(false);
v1.push_back(false);

v2.push_back(true);
v2.push_back(false);
v2.push_back(true);
v2.push_back(false);

std::vector<int> v3;

std::transform(
v1.begin(),
v1.end(),
v2.begin(),
std::back_inserter(v3),
(_1 || _2) && !(_1 && _2)
);

for_each(v3.begin(), v3.end(), std::cout << _1 << ' '); // Prints "1 0 0 1"
}

Quite clean and clear, no? No need to mess around with binders or (explicit) function objects: this one makes a function object from the expression provided, and the two parameters to it are the "placeholders" _1 and _2. So the last line:

(_1 || _2) && !(_1 && _2)

creates something like:

struct (unnamed)
{
int operator()(int a,int b) { return (a || b) && !(a && b); }
} (unnamed);

As bitwise XOR works the same as logical, for bools, one might also use: "_1 ^ _2"

As you say in the blog: since we're passing functions to functions (std::transform), std::transform (like much of STL) is really a higher-order function, =:) which is just a fancy name for functions that take or return functions. We can't normally pass functions around in C++ (only pointer or reference to them), but we may get the same effect with function objects, as used here.

I don't know if there's a particular name for composing functions like this, though.

Regards.

Terje

P.S: I had to use vector<int>, as vector<bool> is a little... odd. Its use of a proxy as a return value didn't work with BLL.

Note also the cute way to print the values after the transformation. :)

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: C++ Meta-Binders

Posted: May 23, 2005 1:04 PM

> Oooh, I get to be the first to comment. ;)

:-)

> You may want to look into Boost.Lambda for this. Using it,
> your example may be written as (tested on g++ 3.2):

[snip]

Very nice. The boost lambda library provides a far more comprehensive and powerful solution to the general problem of binders.

> P.S: I had to use vector<int>, as vector<bool> is a
> little... odd. Its use of a proxy as a return value didn't
> work with BLL.

Probably just a small bug in BLL.

> Note also the cute way to print the values after the
> transformation. :)

Yes very cute!

On this topic, I just found the following paper for a proposal for an enhanced bind function to the TR1:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1455.htm

This makes me a bit excited for the next version of the standard.

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: C++ Meta-Binders

Posted: May 24, 2005 1:04 AM

>On this topic, I just found the following paper for a
>proposal for an enhanced bind function to the TR1:

>http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1455.htm

>This makes me a bit excited for the next version of the standard.

Indeed. This paper: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf gives the latest state of the Library Technical Report, and it includes a bunch of stuff, including Boost.Bind and Boost.Function.

The Library TR has now gone out for voting (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1789.html: "The registration ballot and PDTR ballot for the Library TR closed last Wednesday, and the results of the ballot have not yet been received."), and even though a TR isn't technically part of the next standard, from what I understand, it's pretty sure to end up in the next standard.

And that's just the start... The committee is now working on proposed features like language support for "concepts", DbC and modules (the two latter, like in your Heron language, too). "The future's so bright, I gotta wear shades." ;)

Concepts, DbC and modules, as well as other things, were being presented and discussed at the last standards meeting at Lillehammer (where I also attended).

Regards,

Terje

P.S. The mentioning of Heron reminds me to take a better look at that language, for potentially good ideas for C++ extensions. As you may have found, it can be hard to reach a "critical mass" of users with a new language (there's a reason C++ built from, and was compatible with, C, an already popular language), but by extending an existing popular language, you may be able to improve the situation for millions of people... :)

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: C++ Meta-Binders

Posted: May 24, 2005 6:56 AM

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: C++ Meta-Binders

Posted: May 24, 2005 12:58 PM

> P.S. The mentioning of Heron reminds me to take a better
> look at that language, for potentially good ideas for C++
> extensions. As you may have found, it can be hard to reach
> a "critical mass" of users with a new language (there's a
> reason C++ built from, and was compatible with, C, an
> already popular language), but by extending an existing
> popular language, you may be able to improve the situation
> for millions of people... :)

>You bring up a good point, and it could be a very >worthwhile direction to take Heron. I am considering it >seriously, but for the time being Heron is on hold.

Yes, maybe there was a misunderstanding. What I meant was that since it may be hard to get a large user base for a new language, another direction might be to work on improving one that is already in widespread use (like C++), using one's experience in the new language, if you like.

Regards,

Terje

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: C++ Meta-Binders

Posted: May 24, 2005 1:12 PM

Just to add to my posting:

>What I meant was that since it may be hard to get a large
>user base for a new language, another direction might be
>to work on improving one that is already in widespread use
>(like C++), using one's experience in the new language, if
>you like.

For example, your experience with implementing and using DbC in a C++-like language could probably be useful when considering a proposal for this currently existing for C++: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1773.html. Similarly for the modules proposal (http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1778.pdf).

Support for "concepts" and DbC are two of the more exciting proposals I think exists (and they may complement each other, as well: both adding compiler/runtime checkable information: one doing compile-time checking of type properties, and another checking the run-time properties, like semantics. This also enables decoupling of call site and definition, and checking each, independent of each other).

Regards,

Terje

indranil banerjee

Posts: 38
Nickname: indranil
Registered: Nov, 2004

Re: C++ Meta-Binders

Posted: May 24, 2005 3:49 PM

I agree there are great things in TR1. I wonder when compilers will catch up with it? Judging by C++98 it could take 3-5 years :-(

IMVHO the most important things missing from the language are Threading (which seems to require the introduction of a memory model for C++ as well as a standard thread library), Modules (the only proposal that is going to reduce build times for C++ projects rather than add to them) and some kind of Networking/Socket library (which seems to be further away from standardisation than ever)

BTW Christopher's original post is very similar to the compose functions in Josutti's book. According to the book there was something like this in the original SGI STL, but was not included in the standard. See the code samples at http://www.josuttis.com

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: C++ Meta-Binders

Posted: May 25, 2005 7:50 AM

> I agree there are great things in TR1. I wonder when
> compilers will catch up with it? Judging by C++98 it could
> take 3-5 years :-(

Well, given that this is a pure library extension (i.e. no change to the compiler is needed), and there already exists free versions of more or less all of it (which may need to be slightly changed, to fit the changes done in the standardisation), it shouldn't be that big of a job for vendors to incorporate the free versions in their own libaries, if the want to.

> IMVHO the most important things missing from the language
> are Threading (which seems to require the introduction of
> a memory model for C++ as well as a standard thread
> library)

Work is going on, on a memory model for C++, to start with. Then perhaps get basic threading primitives, and a threading library.

Regards,

Terje

Flat View: This topic has 8 replies on 1 page

Previous Topic

Next Topic