On would–be const constructors

In this post I would like to discuss the idea of having constructors, or some equivalent, designed to build only objects that are const. My motivating example is an attempt to implement matrices and matrix views. I believe this is a canonical example where temptation to have const constructors appears in const methods of the principal class, the chief context in which one has limited data that suffice to only build a const–restricted object. I will try to be clever implementing them, and then show why it does not really work, and what lessons should be learnt from that exercise.
Read more of this post

Advertisements

Generating set partitions – replacing virtual functions with protected inheritance

The purpose of this long post is twofold: first, I really am in need of an efficiently implemented set partition enumerating library, and second, I would like to use this work as a pretext to share and discuss the designs that I considered. The latter is the main part here, as the algorithms themselves are taken from other people’s work, and the c++ discussion does not require a thorough understanding of them.

A set partition is a way to split elements of a finite set into disjoint subsets, called blocks. A way to model it is to take the set of natural numbers {0,1,2,…,n} as the initial set, and give each member a block number. Thus, for n=4 the partition (0,1,0,1) defines two blocks, block 0 containing elements 0 and 2, and block 1 containing elements 1 and 3. Of course, had we taken partition (1,0,1,0), we would have got the same split, so to avoid repetition there has to be a normalization rule: we start with block 0, and if a new block is needed, it gets the next number unused so far. A nice overview of the algorithms that accomplish this task has been gathered by Michael Orlov (section Technical reports at https://www.cs.bgu.ac.il/~orlovm/papers/ ), there’s even an accompanying implementation, but I think that with modern c++ one can now do better. And I need it for a student of mine who is doing research on some industrial process optimisation as well as for purely mathematical research, set partitions have a lot to do with probability, see for instance the explanatory paper by Roland Speicher: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.9723

1. Elementary solution for all partitions

Partitions of fixed size can be looked upon as an ordered collection of immutable elements, and the most natural way to implement this kind of objects in c++ is to have a collection object equipped with iterators, technically speaking const_iterators. Actually, most work is done in iterators in this case, the collection object is just needed for the convenience of having begin and end methods, which allows for instance the range for loop syntax. Michael Orlov’s paper details four algorithms: initialization of first and last partition and generation of next and previous partition, in terms of two sequences, a current partition k and a running maximum of used block numbers m. I will not analyse the algorithms themselves, it is not necessary for the c++ discussion that follows, and Michael has already done a prefect job, please consult his text. So, my first take at implementing the unrestricted set partitions is as follows:
Read more of this post

To const or not to const – the Liskov substitution principle

The Liskov priniple

When inheritance comes to play, it is not always clear how to design interfaces of classes to make reasonable and safe use of it. Most textbooks mention the Liskov substitution principle in this context. Informally speaking, it says that objects of derived classes must be transparently usable wherever objects of the base class are. In this article I try to get to the ultimate conclusions of this rule that I can think of. The ideas here are not entirely new, I admit I just reinvented them, (see for instance Kazimir Majorinc, Ellipse-Circle Dilemma and Inverse Inheritance), but, unfortunately, most discussions end prematurely in my opinion, and I was missing an exhaustive text to organize my thoughts and for teaching. I beg for your patience while reading this lengthy post. It is written with examples in C++11, but I believe it may be relevant to any language with inheritance.
Read more of this post

std::ios_base format flags are a resource that needs RAII

Suppose we wanted to write a class Fraction which would come equipped with an input operator>> that would accept input in the form -2/4 or 3/-8, but disallowing any spaces around the division bar. We would need the fraction class itself first, so, trying to stick to Test Driven Development rules, we would need to satisfy the following test function:
Read more of this post

Type pack metaprogramming

I did advertise once to my c++ students that my feelings tell me that variadic templates are going to be key in implementing type lists in c++ template metaprogramming soon, and showed them a half-baked sketch. But they were not happy with that, “So, you have that class that depends on the type pack, very nice, now, how do you write a method whose signature is calculated out of your type pack?” they asked immediately. Such students’ questions brighten your teacher’s day, even if all you have to say at that point is “I’ll tell you next week”. So I will try in this post to work on the answer step by step.
Read more of this post