Thursday 31 January 2008

C++ pocket lambda library, part 2


In the previous post in this series* I promised to tackle some more advanced topics from my pocket lambda library. To start with something, let us gratuitously choose "currying" first. Do you know what currying is? No, it has nothing to do with food, but rather with an american mathematician named, ehm..., Haskell B. Curry. In his formalization of the notion of a computable function (λ-calculus) he used (for simplicity's sake) only functions with one parameter. Come again? What about all the other functions? For this he used a trick: he defined a function which returns a new function where the first argument is fixed, and the second one remains unbound. When used recursively, we can reduce any function of n-arguments to n functions of 1 argument! Mathematics can be as cool as programming sometimes!

I bet you've seen (and used) it before! Yes, STL provides bind1st and bind2nd functions, which are doing exaclty that: currying! In other languages like Python, Perl, Ruby, Haskell, etc, it's possible too, though sometimes through a library extension. Groovy supports IMHO the most explicite (and cool) form:
    def triple_it = {x,y -> x*y }.curry(3);

1. Our task


What we want to do is to extend the STL binder such that they would work the _$1 placeholders. I think of something like the following:
    for_each(vec.begin(), vec.end(), bind(countVector, 'X', 1.222, _$1));
    for_each(vec.begin(), vec.end(), bind(countVector1, _$1, 1.222, 'Y'));
    for_each(vec.begin(), vec.end(), bind(countVector2, _$1));

    for_each(vec.begin(), vec.end(), bind(pr_sinus, _$1*2));
    const float pi = 3.14; // well, not exactly ;-)
    for_each(vec.begin(), vec.end(), -bind(sinus, _$1*(pi/180.0)) ); 
We assume here that the bind function is pulled in by the appropriate namespace definition, as I want avoid to have to write it like kmx::lambda::bind(sinus, kmx::lambda::_$1). In fact, I never tried out the fully qualified form, shame on me :-(((.

How can we do that? Well there's no need to reinvent the wheel - Boost library already has it, and it's even a part of the C++0x TR.1 standard library extension (tr1::bind). So we can look at the code, or even read about the techniques needed in the implementation**. So if you want, you can spare yourself this post and read ** instead!


2. Basic mechanisms


Well, here is the bind function for the 2 arguments case:
    // 2 args
    template <class F, class A1, class A2>
        binder<F, list2<A1, A2> > bind(F f, A1 a1, A2 a2)
    {
        typedef list2<A1, A2> list2_type;
        list2_type list(a1, a2);
        return binder<F, list2_type>(f, list);
    } 
What is it doing? Basically it stores the arguments to be bound in a custom argument list (class list2<>). Then the function and its arguments are used to create the instance of the actual binder class:
    template <class F, class List> class binder : public lambda_expr
    {
        F m_f;
        List m_list;

     public:
        binder(F f, List list): m_f(f), m_list(list) {}

        // OPEN TODO --> only working for void funct!!!
        template <class A1> void operator() (A1 a1)
        {
            list1<A1> list(a1); // store the actual arg
            m_list(m_f, list); // forward to curried funct: m_f+m_list
        }
    }; 
What is it doing now? It's a functor accepting (in the H.B.Curry's true manner) only one argument. Which one? In the context of an STL algorithm it will be the current value of the iterator. So our task is to sort out to which of the arguments of a function this iterator is bound. Take our previous example: for_each(vec.begin(), vec.end(), bind(countVector1, _$1, 1.222, 'Y')). Here the iterator has to be bound to the first argument of the function - 1.222, and 'Y' to the second and third ones. The binder object stores the actual argument in the custom argument list (class list1<>) and invokes the function m_f in the context of the bound arguments m_list, remembering the current argument in the custom argument list class list1<>. All this is accomplished by heavy use of the listN<> classes, to which we turn our attention now:
    template <class A1, class A2> class list2
    {
        // args: one of them is a placeholder!
        //  -- list1 will detect it!
        A1 m_a1;
        A2 m_a2;
     public:

       list2(A1 a1, A2 a2): m_a1(a1), m_a2(a2) {};

       // apply to arguments and placeholders!
       template <class F, class List1>
           void operator() (F f, List1 list1)
           {
               f(list1[m_a1], list1[m_a2]);
           }
    }; 
Well, list2<> doesn't do that much, it invokes the curried function, but the detection of bound arguments is redirected to the most important class here: list1<>! Let us have a look at it:
    template <class A1> class list1
    {
        A1 m_a1;

     public:
        explicit list1(A1 a1): m_a1(a1) {}

        // if placeholder:
        A1 operator[] (placeholder<1>) const { return m_a1; }

        // not placeholders: return the ball
        template <class T>
            T operator[] (T val) const { return val; }
    }; 
Well, this isn't very complicated: complier will detect when a placeholder was placed and use then the current argument (i.e. the iterator). In other cases, the stored argument value will be used, i.e. the value used to curry the function f. As the value is stored in the listN<> class, it is done via a trick: the listN<> class tries to access the placeholder's _$1 value by using the index operator of the list1<> class, but in non-placeholder cases the index value is simply returned to listN<> to be used as n-th argument (a kind of rebound!).

For the sake of completeness, i.e. in case of bind(sinus, _$1) (who'd need something like that?), we need the function call operator in the list1<> class:
    template <class A1> class list1
    {
       ...
       // apply to arguments and placeholders!
       template <class F, class List1>
           void operator() (F f, List1 list1)
           {
               f(list1[m_a1]);
           }
    };
To bind 3-argument functions we need two more templates to be added: the list3<> class and the bind(F f, A1 a1, A2 a2, A3 a3) function, for 4 arguments another two, and so on, and on... But I don't think anyone should need more than 5 arguments in their functions, do you?

3. Extensions


With the above techniques we can write bind(countVector1, _$1, 1.222, 'Y') but not bind(countVector, _$1*2) or bind(sinus, _$1*(pi/180.0)). What can we do about this? Above we wondered about the bind(sinus, _$1) case, but here we can use it to our advantage. We extend the list1<> class like that:
    template <class A1> class list1
    {
       ...
        template <class T>
            T operator[] (Mul<T>& e) const { return e(m_a1); }
   };
So we can see that the list1<> class is indeed a central one! We extended its rebound mechanism to support the multiplication. Oh, uhm, that wasn't pretty! Why couldn't we simply use a general forwading here? The reason is, I left is as a TODO in code (shame on me :-((() but never came around to implement this. I tried the following:
    A1 operator[] (lambda_expr& e) const { return e(); }
but I didn't finish it, and I don't remember if it worked and if it didn't, why. It was almost one year ago and I don't remember all the details, sorry. OK, that could be done better, but (as I said in my previous post*) "it's a simple library". If you need another operation to be supported in the bind context, simply add it to the list1<>. It remains to be clarified if the simplicity of this library is an advantage, but some measurements were reported, which say that the many layers in a fully grown-up lambda library (like Boost) have a detrimental effect on the performance, because the code gets so complex that the optimizers cannot cope with it!*** And the compilation gets longer too. So maybe such a primitive implementation isn't totally in the wrong?
There is another extension I tried. Again we have to extend the central list1<> class:
    template <class A1> class list1
    {
       ...
       // bind a void member function e.g.: int (T::*)(void *)
       template <class T, typename Ret, class List1>
           Ret operator() (Ret(T::*f)(void), List1 list1)
           {
               return ((list1[m_a1])->*f)();
           }
    };
What does it do? It is supposed to be used like that:
    vector<SomeClass> vec(10);
    for_each(vec.begin(), vec.end(), bind(&SomeClass::compute(), _$1);  
So for each object in a collection its (void) member function will be called. But again, I don't know if it actually worked, as there is no testcase for that in my code (but I think it should). And not everything that's possible makes sense anyway: here the code is misleading, we'd rather like to express this with _$1->compute()!

4. Last words


Well, that's everything I can say about currying support in my library. In the next post(s) I'll show you how to support lambda expressions like: cout << "---" << _$1 << "\n", and how to access a member or a member function of an object from a collection. What else? Maybe some conditional lambda expressions and some general discussion? Look out.

A general question can be answered here: what about the code of my library? Will it be publicly available? And what about the TODOS? And the missing orthogonality? The anwer is, I don't want to (and haven't got time, for that matter) polish the rough edges and add some more orthogonality. It was a fun writing the library, it took me only a couple of days (about 4, I think) , it is simple, and it has shown me that you don't have to be scared of the template metaprogramming. Of course, I wasn't a novice with templates, but I expected more resistance from C++. Maybe it's because of the library's simplicity?

Whatever. This library is not ready, is not complete, and I leave it as it is now.

---
* http://ib-krajewski.blogspot.com/2007/12/c-pocket-lambda-library.html
** Chris Gibson, "How Do Those Funky Placeholders Work?", Overload 73: http://www.accu.org/index.php/journals/1397
*** C++0x proposal: "Lambda expressions and closures for C++" : http://www.research.att.com/~bs/N1968-lambda-expressions.pdf

Friday 25 January 2008

SOA in practice: a YAMS?

In a recent installmet of this blog I already wrote about SOA a little*, but I said that I'm going to read a book of a highly valued author to answer a couple of questions which seemed to stem from my lack of understanding of the subject. Basically my gut feeling was, that SOA (and SOAP) is just a new hype, selling old concepts in new disguise and under new acronyms. Or, in other words: why do we need yet another middleware standard (YAMS)? On the other hand I wondered: if so many highly intelligent people are buying this (i.e. the YAMS), there must be some value in it!

As not to leave my judgements to the mercy of my gut feelings I decided to read some no-nonsense SOA book. This would be close to impossible until recently, as most SOA books were full of marketing drivel and pseudo-scientific, wishy-washy definitions. But recenly a more practical SOA book was published: "SOA in Practice" by N. Josuttis**. As for now, I've read somehow 1/3 of it, which enables me to present some thoughts based based on more solid fundaments.

OK, so was my gut feeling right? Well, both yes and no! SOA is about defining basic services (which can be compared to defining the remote procedures of old), then to combine those simple services (or RPC calls) into more complete, well... services, and then building a business process flow out of those building blocks. And this using SOAP protocol and Web-Services technology. Let me say it: there's nothing new here - nihil novi sub sole! The issues coming up when designing a SOA architecture (i.e. a service-oriented one) are all familiar to me from distributed system design, and the author himself admits it readily. So I was right in my previous post? Technically, yes, with perhaps an exception of BPEL. But???

...but I must admit that SOA indeed has brought in something new, althought in a rather unexpected way! At at the first sight, SOAis only an application of sound distributed system design in corporate settings. And here it is: in corporate settings! As it seems, that wasn't so common before, the organisational and departamental issues were most important then, and now system design issues are on par with them! And that's a huge step forward. Apparently, you need a massive hype vawe to convince corporate people to use some common sense when designing systems!*** And as a Garnter analyst coined the SOA term**** and other Gartner analysts hyped it, the busines people started to hear. And this, and not the usage of SOAP protocol or Web-Services is the real breaktrough of SOA.

PS: And, of course, SOA is SOAP and WS-* in practice, just as I conjectured*, contrary to what you'd read in some high-brow SOA books.

---
* here I tried to answer the question why SOAP and Web-Services aren't simple (which is the first letter of the SOAP acronym!): http://ib-krajewski.blogspot.com/2007/11/web-services-soa-and-rrest.html
** book's homepage: http://www.soa-in-practice.com/
*** or putting it more friendly: there's a huge chasm between business and technical people!
**** SOA-definition by Gartner: http://www.gartner.com/DisplayDocument?ref=g_search&id=302868&subref=browse and http://www.gartner.com/DisplayDocument?ref=g_search&id=302869&subref=browse