The idea
For some time since attending C++Now, I have been meaning to get around to playing with Eric Niebler’s range library. Eric presented ranges in a worked example as one of the keynotes at C++Now – a prior version of the talk that he gave at the Northwest C++ Users Group is currently available on Youtube, and the C++Now keynote should be up soon (under BoostCon).
Listening to Eric’s talk, I was immediately struck by how using ranges is quite functional in nature – composable, declarative, “wholemeal programming” as it’s sometimes called. And I also noticed Eric’s collection of range views and actions, many of which are of course familiar from the STL, but several more of which are clearly inspired by the Haskell Prelude. (And there are useful things in the Prelude that aren’t yet in ranges, for no particular reason other than nobody’s done the work yet.)
Then, the week after C++Now I attended LambdaConf in Boulder, and one talk in particular gave me some motivating examples to test out with ranges. So, a couple of weeks ago, experimenting with ranges finally made it to the top of my to-do list.
Starting out
Would-be range users are cautioned:
This code is fairly stable, well-tested, and suitable for casual use, although currently lacking documentation. No promise is made about support or long-term stability. This code will evolve without regard to backwards compatibility.
OK, just so we know what we’re getting into. Also, the range documentation is described as “woefully incomplete”. Most of it is stubs generated by doxygen. What is there in terms of explanatory prose is also somewhat dated at this point – for instance, recently some template classes were renamed – but having seen the talk, I knew some range fundamentals, so I took the approach of reading code instead of reading documentation. To what end that served me well or steered me wrong remains to be seen, but I got along OK.
Fundamentals
What I wanted to experiment with were views: that is, lightweight, non-owning constructs that (typically) present a way of iterating a range (or ranges). Existing examples are things like take, zip, concat.
From the talk, I knew some fundamentals of ranges and their iterator model. The iterator model used in ranges is a relaxed version of the STL’s begin
/end
paradigm, particularly with respect to end
. Instead of using a pair of iterators, ranges use the idea of an iterator/sentinel pair, so begin
is an iterator and end
is a sentinel. A sentinel can be compared to an iterator, indeed, it may be an iterator. But it also allows the end of a range to be marked with a sentinel value, or it can express a condition that terminates the range. So range views can express ideas like generate_n
, take_while
, or infinite ranges.
Concepts
Eric has done impressive work with Concepts, mentioned in his ranges talk almost as an aside, but representing a significant and important addition to the ranges library. It means two things: first, a user of ranges can get a nice compiler diagnostic that hopefully steers her quickly to a fix, rather than having to pore over pages of template errors. But second, and as importantly, many of the ideas behind ranges are explicit in the code, not just documented or implicitly understood. And that was a big help to me as a reader of the library.
In particular, Eric has adopted and extended the STL’s idea of the different iterator categories, applying representative concepts to both iterators and ranges. In my opinion, a working knowledge of these concepts is essential for the would-be range hacker. As a new range user, I was familiar with Input (and Output), Forward, Bidirectional, RandomAccess as applied to iterators and ranges. Then I had to gain familiarity with a few new concepts: BoundedRange and SizedRange being two of them. It took me a while to integrate the various strengths of range capabilities with the old STL iterator categories model.
Feeling like a novice again
For instance, one thing that came up frequently was that I would want to use view::reverse
on a range. In general, it might not be obvious which ranges can support this and I found that I had to think a bit and re-examine some assumptions. The fact that a range can be iterated bidirectionally is necessary but not sufficient for reversing it – you also have to be able to find the end. I’m not sure if Reversible exists as a Concept, but it might be a worthy addition.
It has been my experience that the nice Concept error messages aren’t always triggered. This isn’t to say they aren’t working, just that they aren’t sufficient to cover all cases nicely, perhaps especially as a library writer rather than as a user. Several times I scratched my head over a compile problem, and needed to experiment with things a bit to discover exactly what I had done wrong or had accidentally omitted. It’s been a while in my career since I had to noodle over a compiler error for that long!
Inspiration and motivation
At LambdaConf, I saw an excellent talk by Doug McIlroy about modelling power series in Haskell. In a dozen lines of code, he’s able to express arithmetic manipulation of infinite power series, as well as differentiation, integration, and functional composition. And in perhaps another dozen (just to deal with termination conditions) the code deals with polynomials (i.e. finite power series) as well. This is beautiful code, and with the power of ranges I wanted to see what I could do to get the same kind of declarative, natural style in C++.
All the code for my experiments is on github, and in the next part, I’ll cover my initial implementation steps, getting my hands dirty with ranges.
You might get a kick out of https://github.com/keithalewis/fms/tree/master/iter. It lets you compute exp(x) to machine precision as follows:
Time to digest Doug McIlroy’s cleverness. Thanks for pointing that out!