In Part 2 I showed the beginnings of a generic Range library implementation that approaches the problem by implementing a generic algorithm that deals with a Concept of a Range. In this third installment to the review of the book Elements of Programming by Alexander Stepanov and Paul McJones, I intend to present a logical thesis on how to approach application development at a higher level using generic programming techniques along with the strong mathematics and Concept-based approach that the book advocates.
Set-Up
So first, let's assume we're writing a simple application that takes a file input that contains a set of coordinates in a
cartesian plane. These coordinates show a set of points connected to each other. This is a fully-connected graph.
Our application is supposed to read all the coordinates and then store it in memory when the application starts. First we don't specify what kind of data structure we use, just that we're going to put it in memory. Second, we don't assume how we store it in memory or whether we put it in a database of some sort -- just that we store it somewhere. Third, we don't know yet how each coordinate is stored but rather that we're just going to assume we're going to have it stored somehow.
At this point of the description, the application isn't really that interesting. However what it's supposed to do is what's interesting.
Ready for Input
Once the application has read all the coordinates from the file, the application is then ready for input. At this state, the application will take the input from the standard input device (or std::cin) in the form of three numbers separated by white space -- which signifies another cartesian coordinate, and a threshold distance value.
First, we assume that the numbers are within the range [-INTMAX,+INTMAX) where INTMAX is the largest possible value represented in an 'int'. Second, we assume that we can store the coordinate the same way we store a coordinate we read from the file. Third, the absolute value of the threshold is used -- therefore negative values become positive values.
So far so good, but then we get to the meat of the application.
The Problem/Solution
What we want to do is find all the coordinates that are within the threshold distance from the input coordinate and print to standard output the coordinates in the form "[x,y] d" where 'x' is the coordinate on the x axis, y is the coordinate on the y axis, and d is the distance to the input coordinate. If you draw a circle around the input coordinate at its center with radius of the threshold distance, then the coordinates that lie within the circle are those coordinates we're looking for.
If you can imagine it in your head, what we're going to have to do is:
- Compute the distance between each coordinate and the source coordinate.
- Filter out the coordinates that aren't within the threshold distance.
- Display each coordinate in the prescribed format through standard output.
Understandably, we should be able to use already available STL containers and algorithms to do this. We can even model each coordinate as a std::pair<int,int> -- and then store them in a list.
In this first incarnation of the solution, we have a few distinct steps which are:
- Load the coordinates from the file.
- Get the distances and store it along with the pair into another list.
- Filter this list and remove the lists that aren't within a certain distance.
- Print the filtered list.
There is nothing wrong with this implementation per se -- however I see that we have three lists. We can optimize this implementation by removing the filtered list, and then hand-writing the iteration of the list of coordinates and distances.
Concepts
So in this implementation we're seeing that there is a certain concept called the coordinate. These are some basic operations defined against a Coordinate that should be valid (via ADL perhaps):
- coord_x(c)
- coord_y(c)
- distance(c1, c2)
In these operations, we assume that 'c', 'c1', and 'c2' are instances of a type that models the Coordinate concept. This gives us a set of primitive operations which we can work with in our application. In this domain of coordinates, we can then count on having the distance between two coordinates and retrieving the x and y components of the coordinate.
Algorithms
Here we can then define the algorithms we need to implement. In a generic (and orthogonal) fashion we find that we have a few basic algorithms required to satisfy the end result that we want to achieve in the program:
- read_coordinates(input_stream) -> range<input_iterator>
- copy_filtered(coordinates, filter, render, output) -> void
The read_coordinates(input_stream) algorithm returns a range of values. For this case we use the Boost.Range concept of a Range which is a pair of iterators for the sake of brevity. Below is a simple implementation of the read_coordinates algorithm:
template <class InputStream>
iterator_range<typename InputStream::iterator>
read_coordinates(InputStream & input_stream) {
return iterator_range<typename InputStream::iterator>(
istream_iterator<coordinate>(input_stream),
istream_iterator<coordinate>()
);
}
template <class InputStream>
InputStream & operator>>(InputStream & is, coordinate & c) {
is >> c.x >> c.y;
return is;
}
This version of read_coordinates relies on the std::istream_iterator<> template that relies on an overloaded shift right (operator>>) implementation that works with an istream and an instance of a coordinate type. This is why we overload the operator>> too above.
The we look at the algorithm for copy_filtered(coordinates, filter, renderer, output). Below is this generic implementation that takes four arguments:
template <class CoordinateRange, class Filter, class Renderer, class OutputIterator>
void copy_filtered(CoordinateRange coordinates, Filter filter, Renderer render, OutputIterator output) {
typename iterator_traits<CoordinateRange>::type iter = begin(coordinates),
end_ = end(coordinates);
while (iter != end_) {
if (filter(*iter)) {
*output++ = render(*iter++);
}
}
}
In the above algorithm we see that we treat coordinates as a range, and then iterate through each item to check if the filter algorithm returns true, we copy the rendered item to the output iterator. This is a very generic filter algorithm that we can use not only in the scope of the program we're building but also other programs. However, in our domain, we may encounter a few snags in terms of efficiency. Let me try and help by pointing out a few things:
- In our application, we intend to filter based on the distance between a certain coordinate and the coordinates we read from the file. This means we have to compute the distance in the filter function and the render function.
- The algorithm above assumes that the filter function will return only a bool. We can change it to get a pair of values instead, a boolean to indicate that it qualifies and the distance. The problem with that approach is that the algorithm then becomes very narrow and specific to our application.
- The renderer's return type should be convertible to the output iterator's value type -- this kind of undue coupling is something that is a fact of generic programming (even the STL does this with the copy algorithm). However in our application, the renderer -- which presumably will turn a coordinate into a string given the format we intend to output, will also need to compute the distance.
This isn't turning out very well for our approach; although we've identified the algorithms we'll be requiring and the concepts we're going to work with, we aren't able to make an implementation yet that is as efficient as hand-coding everything into a single loop. The first incarnation made too much use of memory by making different lists -- that approach won't scale if we have a huge list of coordinates to go through and we keep making extra lists. This second approach eliminates the intermediate lists but computes the distances between the input coordinate and each coordinate from the file twice.
Third Time's the Charm
So let's back up a bit here. Up until this point we've been trying to make generic algorithms from our simple program. Our first incarnation would work although it consumed too much memory. Our second incarnation was a little alright although we're doing multiple computations of the distance. Let's then see how we can do if we can introduce some laziness in our implementation.
First, let's look at our mathematical requirements:
- We have a tuple (x,y) which represents a point in a two dimensional integral plane.
- We have a function distance(p1, p2) which represents the distance between two points.
- We want to filter the points whose distance from a source point is within a certain threshold value.
- We want to print these points and their distance from the source point.
From here we then transform this into a nested pseudocode representation:
print( filter( _ < threshold, transform(distance(source, _), points) ) )
The idea above is that we want to "print" all "filtered" points, where the distance from a source is less than a threshold.
First problem we encountered (and dealt with) was that we had intermediate lists. We then imaging dealing instead with iterators in this solution. Second problem was that we computed distance twice -- first in the filtering, and second time in the rendering.
To solve both problems, we want to be able to transform each point as just a single tuple (x,y), into a bundling of the coordinate and the distance. So now we're looking at a tuple ((x,y), d) where d is the distance -- the reason we want to do this is so that we bundle the coordinate with the distance, so that we can filter them efficiently using our filter algorithm.
Let's see how we can implement our 'distance_bundler' function object:
template <class C>
struct distance_bundler {
typedef tuple<C, double> result_type;
distance_bundler(C const & source) : source_(source) {}
tuple<C, double> operator() (C coord) {
return make_tuple(coord, distance(source_, coord));
}
C source_;
};
So here we've made an effort already to make a specific data representation using our approach. However, consider that we are using a generic 'distance' function which can be easily retrieved via Argument Dependent Lookup (ADL) based on the type C's namespace.
Next we implement a unary predicate function that takes a coordinate-distance bundle, and returns true if the distance is within a threshold value. This is how we can implement that filtering predicate:
struct within_threshold { typedef bool result_type;
within_threshold(double threshold) : threshold_(threshold) {}
template <class C>
bool operator() (tuple<C, double> distance_bundle) {
return get<1>(distance_bundle) < threshold_;
}
double threshold_;
};
In both the preceding implementations, we can choose to use BCCL to make sure the type 'C' models the Coordinate concept. I purposely left that out here to yield more readable examples.
Our next step would be to transform a qualified coordinate and the distance to the source into a string which we can then output. Here we require a 'render' function which will turn a coordinate bundle into an STL string which we also implement:
template <class C>
string render(C const & c) {
ostringstream output_stream;
output_stream << "[" << coord_x(c) << "," << coord_y(c) << "]";
return output_stream.str();
}
struct bundle_printer {
typedef string result_type;
template <class C>
string operator() (tuple<C, double> bundle) {
ostringstream output_stream;
output_stream << render(get<0>(bundle)) << " " << get<1>(bundle);
return output_stream.str();
}
};
Again above we can use the BCCL to enforce that the type 'C' models Coordinate.
Next thing we do is we combine these elements into a lazily-applied construction that uses Boost.Iterators to stitch together the individual moving parts. The code follows, which is explained in greater detail later.
transform(
make_filter_iterator(
within_threshold(threshold),
make_transform_iterator(
begin(input_range),
distance_bundler(source)
)
),
make_filter_iterator(
within_threshold(threshold),
make_transform_iterator(
end(input_range),
distance_bundler(source)
)
),
ostream_iterator<string>(
cout, "\n"
),
bundle_printer()
);
If you happen to be using Boost.RangeEx you can use the algorithm version that supports ranges:
transform(
make_filtered_range(
within_threshold(threshold),
make_transformed_range(
input_range,
distance_bundler(source)
)
),
ostream_iterator<string>(cout, "\n"),
bundle_printer()
);
Or:
transform(
input_range
| transformed(distance_bundler(source))
| filtered(within_threshold(threshold)
, ostream_iterator<string>(cout, "\n")
, bundle_printer()
);
So in the preceding three sample listings, instead of applying the algorithms to different containers we turn them into lazily-applied functions to each element in the input range. Here we feed directly from the file into memory (in the form of a coordinate object that has been read from the input stream) then apply the transformations and filtering as we go through the coordinates.
We also preserve the information required from the initially applied function 'distance_bundler' by bundling it with the result so that it can be used in the filtering -- and therefore have the computed value of the distance only computed once. This chaining approach and using generic algorithms to solve problems is a key theme being proposed by the book at varying levels.
Conclusions
Using the techniques espoused by the book "
Elements of Programming" we can come up with a means of showing how we can use these techniques and apply them when building applications. Using generic algorithms and functions that do specific things at varying levels for both efficiency and correctness is a good practice that yields the desired result.
One of the biggest thrusts of the book is that of composition using building block functions in order to solve problems without having to resort to overly complex structural solutions. Instead of relying on object oriented programming alone, we can leverage functional programming and generic programming techniques to achieve efficient and expressive code. The role of composition in problem solving and extending software in general is something developers should be using more and more.
Instead of trying to re-inventing algorithms we should strive first to see if there are already algorithm implementations out there that we can leverage to allow us to solve problems faster by implementing the parts that are specific to our application. Short of using frameworks, libraries that are generic enough lend themselves to better re-use in more contexts than niche targeted solutions in the form of frameworks and platforms.