In this section I will collect short things that have taken me some time to figure out. The intent is that I would be able to avoid wasting time in the future after I have forgotten about them.
31.10.2012
The Matlab side of Pastel seems to grow in importance. Ideally, everything in Pastel would have Matlab bindings too. But how should the source code be organized?
A natural location to place the Matlab .m bindings would be with the actual C++ algorithms, and then also link them to the documentation, as first-class citizen of the system. However, there is also the C++ mex files which can not be placed there, because they are not part of the actual Pastel C++ libraries (they would create an unnecessary dependence to Matlab). In addition, the users of the C++ libraries would have unnecessary .m files lieing in the directories.
Perhaps a better approach is to create a binding library for each of Pastel’s sublibraries. The bindings require their own documentation. However, this documentation should be placed under whatever algorithms or data structures they bind to (so the documentation for PastelGeometryMatlab is located under the documentation for PastelGeometry).
05.08.2012
An algorithm is a halting program written in a Turing-equivalent programming language. It is a partial function which transforms data (input) to another form of data (output). Being a function means that a given input always results in the same output. Being partial means that the algorithm will only work with input which satisfies certain pre-conditions specific to that algorithm. The relationship between the input and the output is specified by post-conditions; conditions which must hold for the output given the input.
Consider the following algorithm:
real sqrt(real x)
{
ENSURE_OP(x, >=, 0);
real result = 0;
// Compute the square-root of 'x' of to 'result'.
return result;
}
The name of the algorithm is sqrt. Its input data consists of one
(object representing a) real number, and its output data consists of
another real number such that it is a square-root of x (post-condition).
The pre-condition of this algorithm is that x be non-negative,
which is enforced by the check ENSURE_OP.
The Church-Turing thesis is a conjecture which states that the definition given for the definition of an algorithm is the most general one. In other words, all Turing-equivalent programming languages are equivalent in the set of algorithms they can describe. Whatever you can do with Assembler, you can also do with C++. It is a conjecture, because such a claim can never be proved; if a more powerful computation paradigm were found, then we still could not prove that it was the most powerful one. Rather, the Church-Turing thesis is to be accepted on intuitive grounds; it does not take much programming experience to reach this acceptance.
If the Church-Turing thesis is to be accepted, then does this mean that the programming paradigm is simply a matter of taste? Certainly not. It just means that Turing-equivalence becomes a basic requirement expected from any serious programming language. In addition, there are numerous other requirements, the most important of which is the ability of the language to form domain-specific abstractions.
To understand what is meant by this term, consider an assembler programming language, which is very light abstraction over machine-code. In assembler, the programmer directly modifies the registers and memory addresses of the computer. For example, to compute the sum of first 30 integers starting from 1, one could do something like this:
mov eax, 0
mov ecx, 30
loop:
add eax, ecx
dec ecx
jnz loop
Here the eax and ecx are 32-bit integer registers. The mov
command is used to move content from right to left, while the add
command is used to add the contents of right to the contents of
left. The dec command subtracts one from the given register,
and the jnz transfers the program flow to the loop label if
the ecx register is not zero.
You might consider this low level. However, the assembler is already a welcome abstraction over the machine-code, where these almost-readable commands have equivalents as a small sequences of integers. Back in the days the pioneer programmers specified the machine-code directly.
The assembler-style languages recognize the need to abstract over
actual memory addresses: it is not important which absolute memory
address is used to, say, denote the start of a loop. Rather, the start
of the loop is marked relative to other commands, and the actual
machine address computed later. This enabled easy editing of programs,
since the addition or removal of commands do not shift the upcoming
memory addresses. In addition, the command mov is much easier to
remember and teach, than its corresponding command-identifier 0x8B
(hex number). While here we have only use registers of the processor
directly, in an assembler language the memory addresses can also
reserved by name by the user.
The assembler language quickly reveals a number of opportunies for abstraction. For example, to compute something, data must be moved from the memory to registers, the computation made, and then data moved back to memory. The problematic thing here is that the programmer must himself manage the use of the registers, something which can be automated. In addition, direct use of the registers means that the programmers code is irreversibly tied to the specific processor.
The procedural languages abstract away the registers of the processor, so that all operations are logically carried out in the memory of the computer. The compiler then translates this abstract representation to a process-specific assembler- or machine-code. One could then write things such as:
int a = 1;
int b = a + 5;
In addition, the procedural languages abstract away the concept of program flow, which is the transfer of the program pointer to another location. While in machine-code the transfers can be to any location, and in assembler the transfers can only be to any labeled location, in a procedural language the transfers can only be to well-defined pieces of code called functions, or to the start of loops or branches. This recognizes the fact that only a minority of the code locations are usable to be transferred control to. The pieces of code that are found in loops or branches of a conditional jump no longer need to be named; they are abstracted away as irrelevant details.
Examples of program-flow-constructs are for and while loops, and
the if statement (the program needs to transfer the control to the
right branch based on a condition). These are demonstrated here to
compute the sum of all even numbers between 1 and 30.
bool isEven(int x)
{
return (sum % 1) == 0;
}
int computeSum()
{
int sum = 0;
for (int i = 30;i != 0;--i)
{
if (isEven(x))
{
sum += i;
}
}
return sum;
}
A procedural languages massively improves the productivity of a programmer since it abstracts away much of what is irrelevant, meaning the things which can be automated without sacrificing any properties. In the same vein as with the assembler, after some time one starts to find ever-reoccuring patterns of general usefulness.
In particular, it seems that the data that occurs in the problems tends to be grouped, or tightly coupled together. For example, a person has a strong association to his name, age, and height. Representing this association can be done in many ways, however, perhaps the most natural way is to group the data into a single logical entity which contains this data in one place. The idea is that if one these data is needed, then they all probably are.
An object-based programming language is a programming language which supports the abstraction of several types into a new composite type containing an object of each given type. For example:
struct Person
{
string name;
int age;
int height;
};
Person a;
Person b;
Perhaps the best-known example of a procedural object-based programming language is C. However, its support for the object-based paradigm is only ad-hoc.
In the object-based programming paradigm, the programmer represents an object abstraction, such as the person, by a composite type containing the tightly coupled data related to the abstraction, and then makes sure that the data can only be modified through a well-defined interface, so as to prevent an unaware libary-user from making the data inconsistent by accident by breaking an object invariant. Doing this, the programmer abstracts away the object by encapsulating the details of the object’s functionality and representation. Continuing our example, we would write functions such as:
void personSetAge(Person* person, int age)
{
ENSURE_OP(age, >=, 0);
person->age = age;
}
int personAge(Person* person)
{
return person->age;
}
In this example the object invariant is that the age and the height must both be non-negative integers.
It can be said that a programming language only supports a paradigm if it makes it easy to program in the paradigm and enforces that paradigm (Bjarne Stroustrup). By this definition the C language does not properly support the object-based paradigm.
After programming using the ad-hoc object-based paradigm for some time, certain patterns appear yet again. First, while a given object should be accessed only through its interface, according to the programmer of the library, it is still possible to access the data directly (for example, the person’s age). This is because the programming language is lacking an abstraction mechanism for encapsulation, which means a way to hide, and protect, object information from the user of the object.
A programming language is said to support the object-based paradigm if it allows to define classes, where a class is a composite type together with functions that work with the composite type, such that selected data and functions can be hidden from the user of the class object, and which makes it easy to keep up object invariants, from construction to destruction. This means that the class has to make it possible for providing customized functions for
For example:
class Person
{
public:
// Constructor
Person()
: name_("")
, age_(0)
, height_(0)
{
}
// Destructor
~Person()
{
}
void setAge(int age)
{
ENSURE_OP(age, >=, 0);
age_ = age;
}
int age() const
{
return age_;
}
// These data are encapsulated.
private:
string name_;
int age_;
int height_;
};
13.07.2012
Consider data structures A and B, where B refers to parts of A. Then the modification, or destruction, of A, invalidates the state of B. How can we guarantee that it is not possible to make the state of a B invalid?
In this option we simply state in documentation that A must not be modified or destructed when it is referred to in B, and leave it to the user to enforce this.
A problem with this approach is that does not automatically enforce the validity of B. It is thus as prone to human error as before.
This option is unacceptable.
In this option the A has a version number associated with it. This version number is incremented every time a mutating operation is called on A. Before accessing A, the B always checks for the current version number of A against the version number of A when creating B. If the version numbers do not match, an error is generated.
A problem with this approach is that not all mutating operations may go through A. This is the case when A offers direct access to some of its parts. Another problem with this approach is that the versioning does not detect if A is destructed when it is still referred to by a B.
This option is unacceptable.
In this option A is moved into B. This guarantees that A can not be modified or destructed, as long as B exists and refers to A. The B can release the ownership of A to outside, given that it also clears its state.
A problem with this approach is that there can be only one data structure B which can refer to A.
This option is unacceptable.
In this option A is moved into a read-only-object. This is an object which contains a shared_ptr to an A to which A is move-constructed. Copying a read-only object copies the shared_ptr, not the A, thus making it possible to have multiple references to A. The read-only-object can only be used to access a const-reference of A. The read-only-object can release its object to outside given that it only has one single reference. The B object accepts a read-only-object of A, instead of A. This approach fixes the problem with option 3.
A problem with this approach is that it is a bit awkward to use:
Grammar grammar;
// Change grammar...
ReadOnly<Grammar> cGrammar = std::move(grammar);
{
LrZeroAutomaton lrZero(cGrammar);
LalrAutomaton lalr(cGrammar);
// Do some stuff..
}
grammar = cGrammar.release();
// Change grammar...
cGrammar = std::move(grammar);
Name suggestions: Complete, Locked, Protected, Const, Frozen, Static, Unchangeable, Preserve, Managed, Readable, Sealed, Final, Unmutable, Packed, Ref, ReadOnly.
Another problem is that it is easy to confuse cGrammar with
the grammar. This easily creates typo-bugs.
This option is acceptable, but perhaps too clumsy.
In this option B notifies A that it is being referred to. In each mutating operation of A, or when destructing A, A checks whether it is being referred to. If this is the case, an error is generated at run-time.
Grammar grammar;
// Change grammar...
LrZeroAutomaton lrZero(grammar);
LalrAutomaton lalr(grammar);
// Error: can't modify while being referred to.
grammar.change();
A problem with this approach is that the A is most often passed to B as a const-reference. This means that the reference-count in A must be mutable even if A is not, which means additional issues with concurrency.
This option is acceptable.
ReadOnlyPtr<Grammar> grammar_;
In this option B registers itself as an observer of A. Whenever A is modified, or destructed, the A notifies its observers of the change. B can then react appropriately. The problem is that the generality the observer pattern provides is not needed; the option 5 is enough. Another problem is again that the observer list needs to mutable at all times, which means additional issues with concurrency.
This option is acceptable, but unnecessarily complex.
The golden rule of abstraction:
If there exists two or more pieces of text, written in a language S,
for which you can easily describe an algorithm by which they are
similar, then either the language is lacking an abstraction
mechanism, or the mechanism is not taken advantage of.
In this rule, if the abstraction mechanism exists, but is hard to use, this also counts as lacking.
18.06.2012
I am seeing two approaches to implementing library-wide build switches, of which both are problematic. These are
In this approach the build switches are located in a such
.h file which is included in every file in the library,
i.e. environment.h. In this file the appropriate
preprocessor defines can be set to the desired values,
e.g. #define PASTEL_DEBUG_MODE 1, before the build.
The problem with this approach is that each configuration of the library (e.g. debug and release) needs a different set of these defines. Setting the switches in a header file does not work well with build tools where you can select any configuration to build.
In this approach the build switches are given to the
compiler when building the library, e.g.
/DPASTEL_DEBUG_MODE. This will avoid the problems with
the header file approach. However, it then creates new
problems. Consider a library B using a library A.
Then the library B needs to remember the build switches
that were used to build the library A and use those same
switches to build B, in addition to its own build switches.
In general, if there are n libraries in a sequence, then
the m:th library needs to remember m build switch sets.
Clearly this approach does not scale well.
Visual Studio 2010 introduces the pragma
detect_mismatch, which can be used as follows.
#pragma detect_mismatch("PASTEL_VERSION", "1.3.0")
It creates a key-value pair which is embedded into each
object file whose translation unit contains this pragma.
If the object file is later linked together with another
object file with a differing value for the same key,
it is reported as a linker error. In addition to the
version numbers of libraries, we should check each
ABI-incompatibility-causing build switch in this way,
such as the PASTEL_LARGE_INTEGER.
xx.06.2012
Of highest interest, and complete:
Of highest interest, and usable:
Of highest interest, but works incorrectly:
The features listed up to this point are the ones we will have to work with.
Of highest interest, but not available:
Of interest, but not available:
07.06.2012
Inside a data structure I have something like this:
typedef std::multimap<NonTerminal_ConstIterator, Rule,
Pastel::IteratorAddress_LessThan> RuleSet;
Using the map gives a fast access to Rules based on a NonTerminal key. I will then expose an iterator- or range-based interface directly to RuleSet.
The user of the data structure is only interested in the set of Rules, not in NonTerminal-Rule pairs. The pairs make the interface uncomfortable to use. How to expose only the Rule-part?
Rather than exposing direct iterators to the RuleSet, expose a facade iterator which gives access only to the Rule-part of the pair.
19.8.2011
Consider the function
template <typename Range>
void f(Range range)
Assume f requires the value-type of range to be hashable.
If this isn’t the case, how should this be made to work?
Add the hash function as an argument of f.
19.8.2011
Currently we name the models of a concept (and derived classes of an
abstract class) in the form Array_Range, where the modeled concept
is given by Range. Assume the Range concept has a refinement
IndexableRange, and that Array_Range also models the
IndexableRange concept. Should we then rename Array_Range as
Array_IndexableRange? That is, should the suffixed concept be the
weakest, or the strongest concept the type models?
To keep the names short, I think the naming should be by the weakest
concept, i.e. Array_Range in this case.
19.8.2011
Currently the ranges are named ForwardRange, BidirectionalRange,
and RandomAccessRange. The names are a bit too long. Could we find
shorter names? Some naming suggestions follows:
Best ones:
Others:
Best ones:
Others:
The names of the ranges should extend nicely to iterators.
This also gives a nice ‘associativity of names’:
17.8.2011
The problem is to transmit a set of pairs as an input to a function.
Transmit two sequences of equal length, the other corresponding to the first elements of pairs, and the other to the second elements of pairs.
Transmit a sequence of a known type, and require from the type a similar interface as some concrete type, such as std::pair.
Transmit a sequence of pairs, and an object to extract the elements of each pair.
14.7.2011
Say that Logger is an abstract class. A Logger can be attached as an observer to a (unique) Log object. Let us require that whenever an object with a type of a subclass of Logger is destructed, it reports this beforehand to its corresponding Log (if it exists). This means that each Logger object must store a pointer to the associated Log object. On the other hand, each subclass of Logger must remember to report the destruction to its Log.
If each subclass has to implement this reporting manually, the same functionality is implemented over and over again, which is redundant. On the other hand, the feature is not at all specific to the subclasses and can be completely implemented in the Logger superclass. This begs for factoring the functionality out of the subclass into the Logger class. But are there problems with such a factoring?
It is perfectly valid to have concrete functions implemented by the Logger, perhaps built using the abstract functions. However, how about member variables in an abstract superclass? This results in the need for ‘superclass delegation’, which is that constructors, copy constructors, and assignment operators must remember to call their superclass correspondences, an operation which is otherwise not needed (since the superclass has no state). This is again a redundancy, perhaps well described as ‘superclass delegation’, which the implementor of the subclass might forget to do with unfortunate consequences.
The choice is then between two redundancies: ‘superclass delegation’ or ‘reimplementation of a features common to all subclasses’. Between these two, the ‘superclass delegation’ is a better option. The reasons are that
The common functionality can be varied, if needed, without much effort. This option is not practically available when the functionality is replicated to all subclasses.
The superclass delegation approach scales with the increasing complexity of the common functionality.
2.7.2011
In general, invasive reference counting (e.g. via CountedPtr) suggests
that the counted objects should not be allocated in the stack.
But whether the lifetime of an object should be decided by the amount of
references or automatically by the stack, is object-dependent, and thus
should not be decided on the class level.
Pastel should get rid of CountedPtr and move on to use C++0x
shared_ptr as needed.
2.7.2011
The Log class redirects its output to attached observers, called
Loggers. The Log is itself a Logger, to allow for composition.
The loggers are attached by reference. Should Log accept these
references as raw pointers, or as reference-counted pointers?
The problem here is that with raw pointers the references can become
invalid if the referred objects are destructed. A bit of reflection
shows that the actual problem is to consider different options on
what should happen when an observer object is destructed.
After an observer object is destructed, the references to it become invalid. Subsequent use of the observer object then cause a crash or similar. Avoiding crashes requires the user to detach the observer before destruction. As always, leaving something to a human’s responsibility is a bad idea.
With reference counting, the observer is destructed only when the
references to it goes to zero. If the Log has a reference to the
observer, the observer is never destructed before detachment. This
is shared ownership. It is not clear though that the Log should
have such an ownership privilege. This forces the users of Log
to allocate loggers dynamically and store them in the smart pointer
given in the interface of Log.
When a logger is destructed, it is automatically detached from the log. This requires that each log knows its loggers, and that each logger knows its logs. This makes the lifetimes of logs and loggers independent. As a simplification, it could be useful to restrict the number of attached-to logs to one.