Re: [boost] Interest in a list comprehension library?
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.
On 22/12/2010 06:40, Brent Spillner wrote:
* 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().)
That's incorrect. satisfy_predicate() only advances the inner iterator until the first element that satisfies the predicate is found, so as to skip the elements that do not satisfy it. It is indeed called at construction time, and also at each increment. Doing it some other way (advancing in decrement) would lead to more branches and data than is necessary.
* 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.
I hope this backtracking can be efficiently implemented. I'll have to take a look at your implementation.
* 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.)
You could predeclare a set of variables in a specific namespace to reduce that boilerplate to a certain point.
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.
It shouldn't matter at all what is being used. You should really allow any function object to be passed to define your criteria. Phoenix is just a powerful way to create function objects in an inline fashion. You just have to make sure the type you use for x, y, z etc. is compatible with Phoenix.
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.
Using Proto would mean defining a grammar for your syntax, and defining a transform that converts a C++ AST into the desired C++ code, here a lazily evaluated range. It's practical for various reasons: maintenance, validation, reusability, and better interoperability with other embedded languages defined using Proto.
Brent Spillner wrote:
On 21/12/2010 09:09, Mathias Gaunard wrote:
<snip>
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.
I think this comprehension syntax would be a wonderful addition to phoenix. In fact i was thinking of adding it to phoenix V3 myself. By basing your work on phoenix v3 you would introduce a kind of big dependency, true. However, that dependency is imho not a bad thing, it would provide you with a powerful basis for your work. The only thing that needed to be done is to code the logic for the list comprehension ... everything else is already done for you.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (3)
-
Brent Spillner -
Mathias Gaunard -
Thomas Heller