Recent posts

The nature of the "this" pointer in C++


Posted by Diego Assencio on 2017.04.01 under Programming (C/C++)

Whenever you call a non-static member function of a class, you call it through an existing object of that class type. Inside the definition of such a member function, you can refer to this object through the this pointer. Unless there is a need to disambiguate the use of a certain variable name (for instance, if a class data member has the same name as a local variable of the member function), the this pointer is often not used by developers to explicitly refer to class data members. This is almost always not a problem, but as I will discuss in this post, there are situations which require special care in order to avoid certain pitfalls.

To start, consider the following piece of code:

class AddNumber
{
public:

	...

	int add(const int other) const;

private:
	int number;
};

int AddNumber::add(const int other) const
{
	return number + other;
}

When the compiler parses the code above, it will understand that on the definition of AddNumber::add, number refers to the class data member with that name, i.e., that the code above is equivalent to this:

class AddNumber
{
public:

	...

	int add(const int other) const;

private:
	int number;
};

int AddNumber::add(const int other) const
{
	return this->number + other;
}

However, if we change the name of the parameter other of AddNumber::add to number, the compiler will interpret any occurrence of number inside its definition as the function parameter number instead of the data member this->number:

class AddNumber
{
public:

	...

	int add(const int number) const;

private:
	int number;
};

int AddNumber::add(const int number) const
{
	return number + number; /* here number is not this->number! */
}

To fix this ambiguity, we can use the this pointer to indicate to the compiler that the first occurrence of number actually refers to the class data member instead of the function parameter:

class AddNumber
{
public:

	...

	int add(const int number) const;

private:
	int number;
};

int AddNumber::add(const int number) const
{
	return this->number + number; /* this is what we originally had */
}

I hope there was nothing new for you on everything discussed so far, so let's move on to more interesting things.

One could argue that classes as we see them don't really exist: they are purely syntactic sugar for avoiding having to explicitly pass object pointers around as we do in C programs. To clarify this idea, take a look at the code below: it is conceptually equivalent to the one above except for the absence of the private access specifier. To prevent any desperation in advance, the code below is not valid C++; its purpose is merely to illustrate the concepts we are about to discuss:

struct AddNumber
{
	...

	int number;
};

int AddNumber::add(const AddNumber* this, const int number)
{
	return this->number + number;
}

Why is the code above not valid? Well, for two reasons: AddNumber::add is not a valid function name in this context (it is not a member of AddNumber), and this, being a reserved keyword, cannot be used as a parameter name. While in the original version, AddNumber:add is called through an existing object of type AddNumber:

AddNumber my_adder;

...

my_adder.add(3);

in our (invalid) non-class version, AddNumber:add is called with an object as argument:

AddNumber my_adder;

...

AddNumber::add(&my_adder, 3);

Were it not invalid, the non-class version would do exactly the same as the original one. But in any case, it better represents how the compiler actually interprets things. Indeed, it makes it obvious that if we remove the this-> prefix from the first occurrence of number, we will end up with the problem discussed earlier: number will be interpreted exclusively as the function parameter. But don't take my word for it, see it for yourself:

struct AddNumber
{
	...

	int number;
};

int AddNumber::add(const AddNumber* this, const int number)
{
	return number + number; /* this pointer not used, return 2*number */
}

This brings us to the first lesson of this post: whenever you see a non-static member function, try to always read it as a stand-alone (i.e., non-member) function containing a parameter called this which is a pointer to the object the function is doing its work for.

One question which must be asked at this point is: what about static member functions? Do they also implicitly contain a this pointer? The answer is no, they don't. If they did, they would inevitably be associated with some existing object of the class, but static member functions, like static data members, belong to the class itself and can be invoked directly, i.e., without the need for an an existing class object. In this regard, a static member function is in no way special: the compiler will neither implicitly add a this parameter to its declaration nor introduce this-> prefixes anywhere on its definition.

Static member functions have, however, access to the internals of a class like any other member or friend function, provided it is given a pointer to a class object. This means the following code is valid:

class AddNumber
{
public:

	...

	static int add(const AddNumber* adder, const int number);

private:
	int number;
};

int AddNumber::add(const AddNumber* adder, const int number)
{
	return adder->number + number;
}

There is one type of situation in which the implicit presence of the this pointer on non-static member functions can cause a lot of headache to the innocent developer. Here it is, in its full "glory":

/* a global array of callable warning objects */
std::vector<std::function<void()>> warnings;

class WarningManager
{
public:

	...

	void add_warning(const std::string& message) const;

private:
	std::string name;
};

void WarningManager::add_warning(const std::string& message) const
{
	warnings.emplace_back([=]() {
		std::cout << name << ": " << message << "\n";
	});
}

The purpose of the code above is simple: WarningManager::add_warning populates the global array warnings with lambda functions which print some warning message when invoked. Regardless of how silly the purpose of this code may seem, scenarios like these do happen in practice. And being so, do you see what is the problem here?

If the problem is unclear to you, consider the advice given earlier: read the member function WarningManager::add_warning as a non-member function which takes a pointer called this to a WarningManager object:

/* a global array of callable warning objects */
std::vector<std::function<void()>> warnings;

struct WarningManager
{
	...

	std::string name;
};

void WarningManager::add_warning(const WarningManager* this,
                                 const std::string& message)
{
	warnings.emplace_back([=]() {
		std::cout << this->name << ": " << message << "\n";
	});
}

You may be puzzled with the fact that name on the original version of the code was replaced by this->name on the (remember, invalid) second version. Perhaps you are asking yourself: "isn't name itself actually copied by the capture list on the lambda function"? The answer is no. A "capture all by value" capture list (i.e., [=]) captures all non-static local variables which are visible in the scope where the lambda is created and nothing else. Function parameters fall into this category, but class data members don't. Therefore, the code above is conceptually identical to the following one:

/* a global array of callable warning objects */
std::vector<std::function<void()>> warnings;

struct WarningManager
{
	...

	std::string name;
};

void WarningManager::add_warning(const WarningManager* this,
                                 const std::string& message)
{
	warnings.emplace_back([this, message]() {
		std::cout << this->name << ": " << message << "\n";
	});
}

The problem is now easier to spot: in the original example, the name data member is not being captured directly by value, but is instead accessed through a copy of the this pointer to the WarningManager object for which WarningManager::add_warning is called. Since the lambda may be invoked at a point at which that object may no longer exist, the code above is a recipe for disaster. The lifetime of the lambda is independent from the lifetime of the WarningManager object which creates it, and the implicit replacement of name by this->name on the definition of the lambda means we can find ourselves debugging an obscure program crash.

A simple way to fix the problem just discussed is by being explicit about what we want: we want to capture name by value, so let's go ahead and make that very clear to everyone:

/* a global array of callable warning objects */
std::vector<std::function<void()>> warnings;

class WarningManager
{
public:

	...

	void add_warning(const std::string& message) const;

private:
	std::string name;
};

void WarningManager::add_warning(const std::string& message) const
{
	const std::string& manager_name = this->name;

	warnings.emplace_back([manager_name, message]() {
		std::cout << manager_name << ": " << message << "\n";
	});
}

Inside the capture list, the string this->name will be copied through its reference manager_name, and the lambda will therefore own a copy of this->name under the name manager_name. In C++14, this code can be simplified using the init capture capability which was added to lambda functions:

/* a global array of callable warning objects */
std::vector<std::function<void()>> warnings;

class WarningManager
{
public:

	...

	void add_warning(const std::string& message) const;

private:
	std::string name;
};

void WarningManager::add_warning(const std::string& message) const
{
	warnings.emplace_back([manager_name = this->name, message]() {
		std::cout << manager_name << ": " << message << "\n";
	});
}

In this case, we are explicitly coping this->name into a string called manager_name which is then accessible inside the lambda function. As discussed in a previous post, lambda functions are equivalent to functor classes, and in this case, manager_name is a data member of such a class which is initialized as a copy of this->name.

To close this post, I strongly recommend you read the Zen of Python. Look at the second guiding principle: "Explicit is better than implicit". After reading this post, I hope you can better appreciate what a wise statement that is! :-)

Comments (0) Direct link

How are virtual function table pointers initialized?


Posted by Diego Assencio on 2017.03.07 under Programming (C/C++)

A class declaring or inheriting at least one virtual function contains a virtual function table (or vtable, for short). Such a class is said to be a polymorphic class. An object of a polymorphic class type contains a special data member (a "vtable pointer") which points to the vtable of this class. This pointer is an implementation detail and cannot be accessed directly by the programmer (at least not without resorting to some low-level trick). In this post, I will assume the reader is familiar with vtables on at least a basic level (for the uninitiated, here is a good place to learn about this topic).

I hope you learned that when you wish to make use of polymorphism, you need to access objects of derived types through pointers or references to a base type. For example, consider the code below:

#include <iostream>

struct Fruit
{
	virtual const char* name() const
	{
		return "Fruit";
	}
};

struct Apple: public Fruit
{
	virtual const char* name() const override
	{
		return "Apple";
	}
};

struct Banana: public Fruit
{
	virtual const char* name() const override
	{
		return "Banana";
	}
};

void analyze_fruit(const Fruit& f)
{
	std::cout << f.name() << "\n";
}

int main()
{
	Apple a;
	Banana b;

	analyze_fruit(a);   /* prints "Apple" */
	analyze_fruit(b);   /* prints "Banana" */

	return 0;
}

So far, no surprises here. But what will happen if instead of taking a reference to a Fruit object on analyze_fruit, we take a Fruit object by value?

Any experienced C++ developer will immediately see the word "slicing" written in front of their eyes. Indeed, taking a Fruit object by value means that inside analyze_fruit, the object f is truly a Fruit, and never an Apple, a Banana or any other derived type:

/* same code as before... */

void analyze_fruit(Fruit f)
{
	std::cout << f.name() << "\n";
}

int main()
{
	Apple a;
	Banana b;

	analyze_fruit(a);   /* prints "Fruit" */
	analyze_fruit(b);   /* prints "Fruit" */

	return 0;
}

This situation is worth analyzing in further detail, even if it seems trivial at first. On the calls to analyze_fruit, we pass objects of type Apple and Banana as arguments which are used to initialize its parameter f (of type Fruit). This is a copy initialization, i.e., the initialization of f in both of these cases is no different from the way f is initialized on the code fragment below:

Apple a;
Fruit f(a);

Even though Fruit does not define a copy constructor, one is provided by the compiler. This default copy constructor merely copies each data member of the source Fruit object into the corresponding data member of the Fruit object being created. In our case, Fruit has no data members, but it still has a vtable pointer. How is this pointer initialized? Is it copied directly from the input Fruit object? Before we answer these questions, let us look at what the compiler-generated copy constructor of Fruit looks like:

struct Fruit
{
	/* compiler-generated copy constructor */
	Fruit(const Fruit& sf): vptr(/* what goes in here? */)
	{
		/* nothing happens here */
	}

	virtual const char* name() const
	{
		return "Fruit";
	}
};

The signature of the Fruit copy constructor shows that is takes a reference to a source Fruit object, which means if we pass an Apple object to the copy constructor of Fruit, the vtable pointer of sf (for "source fruit"), will really point to the vtable of an Apple object. In other words, if this vtable pointer is directly copied into the vtable pointer of the Fruit object being constructed (represented under the name vptr on the code above), this object will behave like an Apple whenever any of its virtual functions are called!

But as we mentioned on the second code example above (the one in which analyze_fruit takes a Fruit object by value), the Fruit parameter f always behaves as a Fruit, and never as an Apple or as a Banana.

This brings us to the main lesson of this post: vtable pointers are not common data members which are directly copied or moved by copy and move constructors respectively. Instead, they are always initialized by any constructor used to build an object of a polymorphic class type T with the address of the vtable for the T class. Also, assignment operators will never touch the values stored by vtable pointers. In the context of our classes, the vtable pointer of a Fruit object will be initialized by any constructor of Fruit with the address of the vtable for the Fruit class and will retain this value throughout the entire lifetime of the object.

Comments (0) Direct link

Solving Sudoku puzzles using Linear Programming


Posted by Diego Assencio on 2017.02.28 under Computer Science (Linear Programming)

In this post, I will show how solving a Sudoku puzzle is equivalent to solving an Integer Linear Programming (ILP) problem. This equivalence allows us to solve a Sudoku puzzle using any of the many freely available ILP solvers; an implementation of a solver (in Python 3) which follows the formulation described in this post can be found found here.

A Sudoku puzzle is an $N \times N$ grid divided in blocks of size $m \times n$, i.e., each block contains $m$ rows and $n$ columns, with $N = mn$ since the number of cells in a block is the same as the number of rows/columns on the puzzle. The most commonly known version of Sudoku is a $9 \times 9$ grid (i.e., $N = 9$) with $3 \times 3$ blocks (i.e., $m = n = 3$). Initially, a cell can be either empty or contain an integer value in the interval $[1,N]$; non-empty cells are fixed and cannot be modified as the puzzle is solved. The rules for solving the puzzle are:

1.each integer value $k \in [1,N]$ must appear exactly once in each row
2.each integer value $k \in [1,N]$ must appear exactly once in each column
3.each integer value $k \in [1,N]$ must appear exactly once in each block.

Each rule above individually implies that every cell of the puzzle will have a number assigned to it when the puzzle is solved, and that each row/column/block of a solved the puzzle will represent some permutation of the sequence $\{1, 2, \ldots, N\}$.

The version of Sudoku outlined by these rules is the standard one. There are many variants of Sudoku, but I hope that after reading this post, you will realize that the these variants can also be expressed as ILP problems using the same ideas presented here.

The rules above can be directly expressed as constraints of an ILP problem. Our formulation will be such that the constraints will enforce everything needed to determine a valid solution to the puzzle, and the objective function will therefore be irrelevant since any point which satisfies the constraints will represent a solution to the problem (notice, however, that some Sudoku puzzles may contain more than one solution, but I am assuming the reader will be content with finding a single one of those). Therefore, our objective function will be simply ${\bf 0}^T{\bf x} = 0$, where ${\bf 0}$ is a vector with all elements set to $0$ and ${\bf x}$ is a vector representing all variables used in the ILP formulation below.

The puzzle grid can be represented as an $N \times N$ matrix, and each grid cell can be naturally assigned a pair of indices $(i,j)$, with $i$ and $j$ representing the cell row and column respectively (see figure 1). The top-left grid cell has $(i,j) = (1,1)$, and the bottom-right one has $(i,j) = (N,N)$, with $i$ increasing downwards and $j$ increasing towards the right.

Fig. 1: A Sudoku puzzle with blocks of size $m \times n = 2 \times 3$. The cell indices $(i,j)$ are shown inside every cell, and the block indices $(I,J)$ are shown on the left and top sides of the grid respectively. Both the height (number of rows) and width (number of columns) of the puzzle are equal to $N = m n = 6$. The puzzle has $n = 3$ blocks along the vertical direction and $m = 2$ blocks along the horizontal direction.

Let us then define $N^3$ variables as follows: $x_{ijk}$ is an integer variable which is restricted to be either $0$ or $1$, with $1$ meaning the value at cell $(i,j)$ is equal to $k$, and $0$ meaning the value at cell $(i,j)$ is not $k$. Rule (1) above, i.e., the requirement that each $k \in [1,N]$ must appear exactly once per row, can be expressed as: $$ \sum_{j=1}^N x_{ijk} = 1 \quad \textrm{ for } \quad i,k = 1,2,\ldots,N \label{post_25ea1e49ca59de51b4ef6885dcc3ee3b_row_constraint} $$ In other words, for a fixed row $i$ and a fixed $k \in [1,N]$, only a single $x_{ijk}$ will be $1$ on that row for $j = 1, 2, \ldots, N$.

If the fact that the constraints above do not have any "$\leq$" is bothering you, remind yourself of the fact that $x = a$ can be expressed as $a \leq x \leq a$, which in turn is equivalent to the combination of $-x \leq -a$ and $x \leq a$, i.e., any equality constraint can be expressed as a pair of "less-than-or-equal-to" constraints like the ones we need in Linear Programming problems.

Rule (2), i.e., the requirement that each $k \in [1,N]$ must appear exactly once per column, can be expressed as: $$ \sum_{i=1}^N x_{ijk} = 1 \quad \textrm{ for } \quad j,k = 1,2,\ldots,N \label{post_25ea1e49ca59de51b4ef6885dcc3ee3b_column_constraint} $$ Expressing rule (3), i.e., the requirement that each $k \in [1,N]$ must appear exactly once per block, is a bit more complicated. A way to simplify this task is by assigning pairs of indices $(I, J)$ to each block in a similar way as we did for cells (see figure 1): $(I,J) = (1,1)$ represents the top-left block, and $(I, J) = (n,m)$ represents the bottom-right block, with $I$ increasing downwards and ranging from $1$ to $n$ (there are $n$ blocks along the vertical direction) and $J$ increasing towards the right and ranging from $1$ to $m$ (there are $m$ blocks along the horizontal direction). Block $(I,J)$ will therefore contain cells with row indices $i = (I-1)m + 1, \ldots, Im$ and column indices $j = (J-1)n + 1, \ldots, Jn$. Therefore, rule (3) can be expressed as: $$ \sum_{i=(I-1)m + 1}^{Im} \sum_{j=(J-1)n + 1}^{Jn} x_{ijk} = 1 \quad \textrm{ for }\quad \left\{ \begin{matrix} \; I = 1,2,\ldots,n \\[5pt] \; J = 1,2,\ldots,m \\[5pt] \; k = 1,2,\ldots,N \end{matrix} \right. \label{post_25ea1e49ca59de51b4ef6885dcc3ee3b_block_constraint} $$ Notice that both equations \eqref{post_25ea1e49ca59de51b4ef6885dcc3ee3b_row_constraint} and \eqref{post_25ea1e49ca59de51b4ef6885dcc3ee3b_column_constraint} represent $N^2$ constraints each. As it turns out, equation \eqref{post_25ea1e49ca59de51b4ef6885dcc3ee3b_block_constraint} contains $nmN = N^2$ constraints as well.

So far, our formulation does not prevent $x_{ijk}$ from being equal to $1$ for two or more distinct values $k$ at the same cell $(i,j)$. We need therefore to impose these constraints by hand: $$ \sum_{k=1}^N x_{ijk} = 1 \quad \textrm{ for } \quad i,j = 1,2,\ldots,N \label{post_25ea1e49ca59de51b4ef6885dcc3ee3b_cell_constraint} $$ Not all cells are initially empty on a Sudoku puzzle. Some cells will already contain values at the beginning, and those values are necessary so that the solution to the puzzle can be deduced logically (ideally, there should be a single valid solution). Let $\mathcal{C}$ be the set of tuples $(i,j,k)$ representing the fact that a cell $(i,j)$ contains the value $k$ at the beginning. We then have: $$ x_{ijk} = 1 \quad \textrm{ for } (i,j,k) \in \mathcal{C} \label{post_25ea1e49ca59de51b4ef6885dcc3ee3b_initial_puzzle_constraint} $$ Our last set of constraints limits the values which each variable $x_{ijk}$ can take: it's either $0$ or $1$ (our ILP formulation then technically defines a Binary Integer Linear Programming problem, or BILP for short): $$ 0 \leq x_{ijk} \leq 1 \quad \textrm{ for } \quad i,j,k = 1,2,\ldots,N \label{post_25ea1e49ca59de51b4ef6885dcc3ee3b_binary_constraint} $$ Since most ILP solvers allow bounds on the values which each $x_{ijk}$ can take to be set directly, this last set of constraints often does not need to be specified in the same manner as the previous ones.

We now have a complete ILP formulation of a Sudoku puzzle: our goal is to minimize the objective function $f(x_{111}, \ldots, x_{ijk}, \ldots x_{NNN}) = 0$ subject to all constraints specified on equations \eqref{post_25ea1e49ca59de51b4ef6885dcc3ee3b_row_constraint}, \eqref{post_25ea1e49ca59de51b4ef6885dcc3ee3b_column_constraint}, \eqref{post_25ea1e49ca59de51b4ef6885dcc3ee3b_block_constraint}, \eqref{post_25ea1e49ca59de51b4ef6885dcc3ee3b_cell_constraint}, \eqref{post_25ea1e49ca59de51b4ef6885dcc3ee3b_initial_puzzle_constraint} and \eqref{post_25ea1e49ca59de51b4ef6885dcc3ee3b_binary_constraint}.

After solving the ILP problem outlined above, the solution to the Sudoku puzzle can be constructed directly by placing, at each cell $(i,j)$, the value $k$ such that $x_{ijk} = 1$.

Comments (0) Direct link