Wednesday 9 July 2008

C++ pocket lambda library, the last

So, this will be definitely the last part! I promise! I planned this to be a three part series, and see how it has grown. But let's go down to the business: in the previous installments we achieved the following:
    // part 1: basics
find_if(vec.begin(), vec.end(), _$1 <= 10);
transform(vec.begin(), vec.end(), vec1.begin(), _$1*2);
sort(vp.begin(), vp.end(), *_$1 <= *_$2);
    // part 2: function applications
for_each(vec.begin(), vec.end(), bind(sinus, _$1*(pi/180.0)) );
    // part 2a: member access
find_if(vecx.begin(), vecx.end(), _$1->*(&XXX::getValue) <= 2);
    // part 3: output
for_each(vec.begin(), vec.end(), cout << delay("---") << _$1 << delay("\n"));
You can see, we had defined a kind of a custom (if not too counter-intuitive) mini-language for the lambda expessions. As each language has to be learnt, we'd like it to be kept simple! So I have only one more thing to add, namely:

1. Control structures


This is really fun, because it's not difficult at all and it let us define very cute lamdbas indeed. The entire code, as it stands in the library, is like that:
    // if_then
// ---

template <class S, class T> void eval_then_expr(S& e, T& t) { e(); }
    // helper: Assgn needs the iterator for: if_then(_$1==0, _$1=44)
// --- OPEN, TODO: make general for e.g.: if_then(_$1>=3, cout << _$1)
// --

template <class T> void eval_then_expr(Assgn<T>& e, T& t) { e(t); }
    template<class S, class T> struct IfThen  : public lambda_expr {
S if_expr;
T then_expr;
IfThen(S s, T t) : if_expr(s), then_expr(t) {}
template <class U>
// OPEN, TODO: check if then_expr needs the val argument!
bool operator()(U& val) { if(if_expr(val))
eval_then_expr(then_expr, val); }
};
    template <class S, class T>
IfThen<S, T> if_then(S s, T t) { return IfThen<S, T>(s, t); }
    // t.b.c....
you see, there are some TODOs, which we'll discuss in the due time, but the technique is simple: first we store the if_expr and the then_expr (as functors), and when the IfThen functor is evaluated, we just evaluate the sub-functors, and make the then_expr dependant on the value of the if_expr. I didn't think myself this would be so simple! As this isn't a ready library, but rather an exploration of some possibilities in code, ther are a lot of open ends here. First, we probably don't need the val parameter in the function call operator. Second, if the then_expr needs the iterator (i.e. _$1), I currently just hacked in only the overload for the assignment. This must be extended with some general forwarder mechamism. But even with this rudimentary support, we can do this now:
    // count occurences
for_each(vec.begin(), vec.end(), if_then(_$1 == 1, globvar(yyy_ctr)++));
    // replace values
for_each(vec.begin(), vec.end(), if_then(_$1 == 1, _$1 = 9));
I think it's pretty useful. Other possible control structures? Well, I think they are possible, but not so useful: a loop, a switch? I don't think that it would be good design. What we really would need sometimes, is rather a possiblility to nest STL algorithms than to use a loop functor. But it's not difficult, maybe something along the lines of:
    template <class U>
bool operator()(U& val) { auto it = val.begin(); // C++Ox
for(it != val->end(); it++)
eval_loop_body(loop_body, it); }
would do, and then we could process a container of containers:
    for_each(cc.begin(), cc.end(), loop_all(cout << _$1));
and perhaps even to extend it like that:
    for_each(cc.begin(), cc.end(), loop_some(_$2 < 1, cout << _$1));
for_each(cc.begin(), cc.end(), loop_counted(10, cout << _$1));
But do we need it? I think it's more a gimmick that an useful feature, because it's not orthogonal: you have a host of special loop_xxx lambdas instead of a single mechanism. What do you think?

2. Summing this all up


In conclusion? There are 2 conlusions:

1. lambda library is cool, all this stuff is cool, I'm cool.

2. Frankly, isn't that all just appalling? All that effort and what we got is an unnatural syntax! And it's not transparent: for each new combination of operators I've got to write new code in the library (or almost)! Makes you think of Phillip Greenspun's Tenth Rule of Programming: "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified bug-ridden slow implementation of half of Common Lisp." Please Mr. Stroustrup, why don't we have lambda-expressions as core language feature in C++???

Actually, as the things are, it seems like we are going to have lambda functions in the new C++0x standard*! For me, they look like Groovy lambdas (or are they really Ruby's ???), compare**:
Groovy: myMap.each { key, value -> println "$key => $value" }

C++0x: for_each(a.begin(), a.end(), <> (int x) -> int { return sum += x; } );
// or, equivalently, but not much Groovy-like:
for_each(a.begin(), a.end(), <>(int x) { return sum += x; } );
Should we rejoice then? The proposal paper itself lists the problems with lambda expressions:

1. lambda-libraries may render simpler code in basic cases, compare:
    // lambda lib.
os << _$1
// lambda expr.
<> (int i) extern(os) { os << i; }
You see, we need the old, ugly, annoying type specifications again! An we've just started to ejoy the typeless (ehm, generic...) programming in C++! Isn't that what the whole template thing is for! This leads immediately to the second problem:
2. there are no polymorfic lambda functions!!!

The proposal doesn't allow us to write templated, polymorfic lambda function (i.e. ones with implicit type recognition), as it would clash with the concepts feature. More specific, it wouldn't exaclty clash and explode, but rather the concepts couldn't guarantee the correct type checking in this case. So bye bye type freedom? Do we alway have to use the annoying explicite typing? Imagine a lambda function working with an iterator on a list of strings, an then write this type expicitely as input parameter. Ghastly! When you are using a lambda library solution, you'll simply write _$1, and that's it! In such a case, the whole point of the lambda expression, its conciseness, goes down the drain. I can write a standalone functor as well.
Summing up: if have only a simple thing to do, a lambda library solution is simpler. But if there is some more work to do, and we don't have elaborate type specifications for input parameters, the lambda expression solution has clearly an edge, as we don't have to learn a new, special-purpose mini-language, but can just use the standard C++ syntax.

As it seems none of the solutions is optimal: do we need both of them?. And I can say I'm rather not pleased, although the situation here is definitely better than in Python.

3. Personal note


In the past I thought (or rather believed) that you could just do everything in C++ with libraries, operator overloading and template tricks. But I guess I was just dazzled by the template syntax ;-). After this series I think there are limits to the flexibility of C++ which can be only worked around with ugly syntax (or macros).

---
* as in the last "State of C++ Evolution" document they are on the list of the features which are definitely planned to be included, see: "State of C++ Evolution (between Portland and Oxford 2007 Meetings)" of Dec.01.2007 - http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2142.html
** C++0x lambda expressions proposal - http://www.research.att.com/~bs/N1968-lambda-expressions.pdf