On 21/12/2010 09:09, Mathias Gaunard wrote:
Can you explain the difference with the Boost.Range adaptors?
I think these are the most important ones: * Lazy evaluation of every comprehension. In contrast, boost::filter_iterator applies the filter predicate to the entire wrapped range at construction time (via satisfy_predicate().) * As a consequence, there are several ways to limit the amount of computation based on the amount of output required rather than the length of the input ranges. * Predictable backtracking behavior that allows filter criteria to depend on each other. This enables a number of computations (e.g. looping over the elements within a range of ranges) that are otherwise difficult or impossible to express, and even in straightforward cases permits some efficiency improvements. For instance, your example Pythagorean triple comprehension using Boost.Range evaluates a number of combinations of the three indices equal to the n'th cubic number, while the 'i <<= range(1,n), j <<= range(i,n), k <<=range(j,n)' version evaluates the n'th tetrahedral number's worth of combinations. The ratio of these quantities approaches 6 as n increases, and is in fact greater that 5 by n=16. A factor of 5 speedup is surely worth something. * Somewhat more concise and I believe more readable syntax. My goal was to require fewer characters than a Python comprehension and ideally not many more than Haskell, and I think I'm there in the simple cases. (Neglecting the variable declarations, naturally.)
It is true Boost.Range is quite lacking in terms of range generators, and maybe your solution is what we need.
Don't get me wrong; I think Boost.Range is great, and the iterator adapters are a fantastic way to improve the iterator-based algorithms that tend to be somewhat clumsily expressed in a lot of traditional C++ code. I just don't think they're a fully satisfying substitute for the comprehension syntax (and backtracking, etc.) provided or easily defined in most functional languages.
It would be nice however, if it didn't reinvent the wheel and can be based on Phoenix for the functional part.
I definitely don't want to reinvent the wheel, and I was a little hesitant to publish this in case it largely duplicated work that someone else had done in Range or Phoenix or somewhere else. I've never used Phoenix; it seems fascinating but I'm a little wary of making it a dependency just to get something simple like a comprehension syntax. I also took a look at using Boost.Proto to provide the expression trees, but it seemed that the syntax was a little more verbose than it needs to be for things that will be evaluated only in the context of a comprehension expression. Either one of those libraries could likely replace most of the boilerplate in my expressions.hpp and operators.hpp; on the other hand, being boilerplate, it wasn't that hard to write or to get it to work exactly as I needed. At this point I'm leaning more toward providing adaptors to permit Proto or Phoenix expressions within a comprehension, rather than absolutely requiring the use of either.