Self-Driving Car Challenges

Mercedes recently announced level 3 self-driving that takes legal liability. Typically, the levels of autonomy are defined by situations where the car is able to operate without human intervention, but being able to assume legal liability is a huge step forward. Levels of autonomy would only remain a marketing slogan unless it can be tested in court. The cost of liability will be factored into the insurance premium, so self-driving only becomes economically viable if the insurance premium can be lower than that of a human driver.

However, Mercedes' legal responsibility comes with limits: on certain (already-mapped) highways, below 40 mph, during daytime, in reasonably clear weather, without overhead obstructions.

The first challenge that any camera based system must overcome is the stability of the footage. You can see from this test that a car mounted camera with improper image stabilization (circa 2016) would produce a wobbly and shaky image. The wobble can be counteracted by shortening exposure time (high camera shutter speed) but this requires good lighting condition, hence the reasonably clear weather requirement. Furthermore, when the car is traveling fast, you need a telephoto lens to look further ahead for hazardous conditions, but longer telephoto also exacerbates the wobble, hence the operating speed limit of the self-driving. If the video footage is bad, it won't help much if you feed this into machine learning because "garbage in, garbage out." More recent cameras such as a GoPro has improved image stabilization (circa 2021) that also works on a toy car (circa 2020) which is more challenging to stabilize. These cameras can produce clean image under more forgiving lighting conditions.

Car manufacturers who are serious about their self-driving should be licensing camera stabilization technology from the likes of GoPro.

Self-driving cars using LIDAR face a different challenge. LIDAR works by sending a short pulse of light and observe reflections, so it is not dependent on external lighting conditions. But when there are multiple LIDAR equipped cars on the road, they could be picking up each other's signals which might seem like noises. As such, a LIDAR has to encode its own unique ID into the light pulse and filter out any pulse not coming from itself.

A third challenge is about how to legally dispute a claim in court. A self-driving system must be able to produce a rationale why it made any given decision, and the decision has to be legally justifiable. Previously, machine learning is a black box that could produce surprising results (it recognized a dumbbell only because it has an arm attached to it), but explainable AI is making some progress. Similarly, self-driving technology must be explainable.

Explainable self-driving technology can be thought of as a driving instructor that happens to be a computer. The driving instructor not only has to make the right decision on the road, but it also has to explain to a student why it is the right decision given the circumstance.

Car manufacturers that want to assume legal responsibility should aim for a computerized driving instructor instead.

A musician would understand that in order to perform at 100%, they must practice up to 120%. This mindset applies to a lot of engineering problems where safety is at stake. Building structures such as elevators are often designed with load considerations at ~200% rated capacity or more (ASCE/SEI 7-10 1.4.1.1 (b)). When it comes to self-driving, the specs are less quantifiable, but the design qualifications must similarly exceed expectation in order for the technology to be viable.

Proof of Sum of Exponential Powers

My renewed interest in proof of exponent laws came from reading the Harvard Entrance Exam, 1869, which David Robert Palmer painstakingly typed up. In the exam there were sections of Latin and Greek, History and Geography, are various mathematics. It's fascinating that the words in Latin and Greek are already provided, so knowing how to conjugate is all that is required. The maths section are heavily calculation based. It seems that these sections serve to test only how nimble the minds are in solving known problems, but not so much whether the students exhibit the thought process of solving unknown problems. But one question intrigued me.

Question (3) in the algebra section reads, "What is the reason that when different powers of the same quantity are multiplied together their exponents are added?" It is asking about the exponent law for product of powers, \( a^x a^y = a^{x+y} \). Knowing the prestige of Harvard, giving an informal answer is likely not satisfactory. But most of the so called "proofs" that are prevalent in textbooks essentially boil down to the following reasoning.
\[ \underbrace{a a \dots a }_{x \text{ times}} \cdot \underbrace{a a \dots a}_{y \text{ times}} = \underbrace{a a a a \dots a a }_{x + y \text{ times}} \]
This appeals to the intuitive understanding that \( a^x \) is \(a\) multiplied \(x\) times, so when you multiply the result also by \(a\) for another \(y\) times, you get \( a^{x+y} \). This is hardly satisfying as a proof.

Another "proof" is to reduce this to the additive law of logarithms \( \log{xy} = \log{x} + \log{y} \), but this is like throwing the hot potato to someone else.
\[ \log{a^x a^y} = \log{a^x} + \log{a^y} = x + y \\
a^{\log{a^x a^y}} = a^{x+y} \]
And since \( a^{\log{c}} = c \) i.e. log is the inverse of exponent, so \( a^{\log{a^x a^y}} = a^x a^y = a^{x+y} \).

There are other exponent laws without formal proofs, but for this article I'm going to focus on the sum of powers.

Formal proof

We appeal to proof by induction for the formal proof. First we establish the base case for exponentiation:
\[ a^0 = 1 \]
Also recall that \(1\) is the multiplicative identity, so \( x\cdot 1 = 1\cdot x = x \), and \(0\) is the additive identity, so \( x+0 = 0+x = x \). From this, we can prove the base case where \( y = 0 \), i.e. \( a^x a^0 = a^x \cdot 1 = a^x = a^{x+0} \).

Now for the inductive case, we need both the axiom of exponentiation \( a^x \cdot a = a^{x+1} \) and the induction hypothesis \( a^x a^y = a^{x+y} \). We proceed to show that \( a^x a^{y+1} = a^{x+y+1} \).
\[ a^x (a^{y+1}) \underbrace{=}_{\text{axi.}} a^x (a^y a^1) \underbrace{=}_{\text{assoc.}} (a^x a^y) a^1 \underbrace{=}_{\text{I.H.}} a^{x+y} a^1 \underbrace{=}_{\text{axi.}} a^{(x+y)+1} \]
In the equations above, "axi." means the axiom of exponentiation, "I.H." means application of induction hypothesis, and "assoc." means associativity (which is true of all multiplicative groups, e.g. matrix multiplication).

Having painstakingly established a formal proof of the product of powers, there is a notable limitation, namely that we only allow natural number exponents, \( \{x, y\} \subseteq \mathbb{N} \). In particular, we don't allow negative (e.g. -3) or fractions (e.g. 3.14159...). Indeed, the real number domain has declarative properties that evade the mere application of modus ponens in discrete logic, which gives rise to the famous satire Alice in Wonderland.

Proof sketch in real number domain

Fortunately, all is not lost in the real number domain. We can invoke Taylor's theorem to expand the infinite series for calculating \( e^x \) and \( e^y \), multiply the two series, and see if \( e^{x+y} \) expands to the result of the multiplication.

The Taylor series for \( e^x \) is:
\begin{array}{rcl}
e^x & = & \sum^{\infty}_{n=0} {x^n \over n!} \\
 & = & 1 + {x^1 \over 1!} + {x^2 \over 2!} + {x^3 \over 3!} + {x^4 \over 4!} + \dots \\
 & = & 1 + x + {x^2 \over 2} + {x^3 \over 6} + {x^4 \over 24} + \dots
\end{array}
The following table multiplies the Taylor series for \( e^x \) and \( e^y \).
\begin{array}{c|cc}
\times & 1 & x & x^2 \over 2 & x^3 \over 6 & x^4 \over 24 & \dots \\ \hline
1 & 1 & x & x^2 \over 2 & x^3 \over 6 & x^4 \over 24 & \dots \\
y & y & xy & x^2 y \over 2 & x^3 y \over 6 & x^4 y \over 24 & \dots \\
y^2 \over 2 & y^2 \over 2 & xy^2 \over 2 & x^2 y^2 \over 4 & x^3 y^2 \over 12 & x^4 y^2 \over 48 & \dots \\
y^3 \over 6 & y^3 \over 6 & xy^3 \over 6 & x^2 y^3 \over 12 & x^3 y^3 \over 36 & x^4 y^3 \over 144 & \dots \\
y^4 \over 24 & y^4 \over 24 & xy^4 \over 24 & x^2 y^4 \over 48 & x^3 y^4 \over 144 & x^4 y^4 \over 576 & \dots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{array}
The Taylor series for \( e^{x + y} \), expanded individually, is:
\begin{array}{c}
1 &+& (x+y) &+& {(x+y)^2 \over 2} &+& {(x+y)^3 \over 6} &+& {(x+y)^4 \over 24} &+& \dots \\
 & & || & & || & & || & & || \\
 & & x & & x^2 \over 2 & & x^3 \over 6 & & x^4 \over 24 \\
 & & y & & xy & & x^2 y \over 2 & & x^3 y \over 6 \\
 & & & & y^2 \over 2 & & xy^2 \over 2 & & x^2 y^2 \over 4 \\
 & & & & & & y^3 \over 6 & & xy^3 \over 6 \\
 & & & & & & & & y^4 \over 24
\end{array}
As you can see, the expansion of each term corresponds diagonally to the multiplication table above, so we can indeed show by Taylor expansion that \( e^x e^y = e^{x+y} \). This is only a proof sketch, but the enterprising mind could organize the table into a formal proof, using Binomial Theorem and Cauchy Product.

You might have noticed that we have only established the product law at base \(e\) but not other bases. For the other bases, recall that \( a^x = e^{x \ln a} \), so we have:
\[ a^x a^y = e^{x \ln a} e^{y \ln a} = e^{(x \ln a) + (y \ln a)} = e^{(x+y)\ln a} = a^{x+y} \]

Conclusion

There are two reasons why I suspect the Harvard entrance exam only expected the informal reasoning of counting the number of multiplicands. Cauchy (1789-1857) product is a fairly recent development to the time of the exam in 1869, which makes it unlikely to become part of the curriculum. There were no other questions that require the use of proof by induction so that it is also unlikely to be part of the curriculum either.

On the other hand, it is only after I became older (and overeducated) that I realize a lot of maths I was taught in grade school were really just informal proof sketches, and even so I didn't learn to question the profoundness of their limitations. The informal proof sketch of counting the multiplicands is limited to exponent in the natural number domain and would not work for real number exponents. I spent the better parts of my youth learning faux math!

Laws in the real number domain cannot be proven by counting alone because real numbers are uncountable. For this case I appealed to Taylor's Theorem, first expanding the polynomial series and showing the combined series are equal. I suspect many of the real number laws could use the same treatment.

Enforce RTOS in hypervisor

This is a brain dump of a simple idea of using the hypervisor to make sure that a real-time operating system is, honestly, real time.

An operating system can't be real-time if any parts of it masks interrupt. It also cannot be real-time if its interrupt handler runs for too long, causing some interrupts to be missed. However, in the kernel everything is run at privileged level, and there is no law enforcement in this wild-wild-west.

Unless you run the kernel under a hypervisor that enforces these policies.

When a kernel runs under a hypervisor, privileged instructions such as cli/sti (clear interrupt, set interrupt) is trapped by hypervisor. Since the hypervisor handles all the interrupts first, it would normally just disable or enable interrupt relay for that particular virtual machine. In our case, to ensure that the kernel never clears interrupt, all it has to do is to abort the kernel. Simply ignoring it would likely cause the kernel to corrupt its internal data structure and die sometime later anyway.

Alternatively, the hypervisor would simply log the cli/sti as they happen but still emulate them. A RTOS kernel will only pass certification if no such events are logged.

The hypervisor could also measure the time an interrupt handler in the kernel takes to execute. If handler takes too long, it would abort the VM. Alternatively, the hypervisor could detect and log a long running interrupt, or when an interrupt is about to be dropped due to a long running interrupt or masked interrupt.

ps. Some good references:

• http://pldi12.cs.purdue.edu/sites/default/files/slides_pldi12-oagesen.pdf
• http://deptinfo.cnam.fr/new/spip.php?pdoc7568

Mistake in my RC4 implementation

Jim Wilcoxson approached me two days ago regarding the skewed distribution I observed in RC4. He sent me a snippet from SQLite's implementation of RC4 and showed that it did not suffer the non-uniform result I saw.

After digging out my old code, I found two mistakes I made. One in the key scheduling algorithm:

  void initialize(const char *begin, const char *end) throw() {
    for (size_t i = 0; i < 256; ++i)
      s_[i] = i;

    const char *key = begin;
    uint8_t j = 0;

    for (size_t i = 0; i < 256; ++i, ++key) {
      if (key == end) key = begin;
      j = j + s_[i] + *key;
      std::swap(s_[i], s_[j]);
    }
  }

In the original code, I had forgotten to ++key, so the key scheduling is always done on the first byte of the key only. The addition for the fix is highlighted in yellow.

Another mistake is an index out of bounds error in the generation of bytes.

  uint8_t next() throw() {
    i_ = i_ + 1;
    j_ = j_ + s_[i_];
    std::swap(s_[i_], s_[j_]);
    return s_[s_[i_] + s_[j_]];
  }

There is an array index out of bounds error in the return line. The reason is that in C/C++ compiler, the intermediate result of an expression, if it's an int, does not inherit the int size of the sub-expressions, but instead is word sized. Since both s_[i_] and s_[j_] are (0...255), half of the times the result is in (256...511) which accesses some memory beyond s_[]. This explains why I get a skew where most byte value tallies are halved.

The fix is to replace the return line as follows:

    return s_[(uint8_t) (s_[i_] + s_[j_])];

Where an explicit cast to uint8_t solves the index out of bounds problem.

The suggestion I gave, to add ^ j, only obscures the problem.

Fortunately my code has never been used in a production system. It was written quickly to give me a PRNG for a memory usage simulator I wrote last year for testing a memory allocator where the PRNG (1) must not use memory allocation itself, (2) must not use locking, (3) is reasonably fast and easy to implement. The implementation satisfied all my original requirements but was not RC4.

Interface checking

One of my regrets for C++ is that it doesn't have interface checking when you instantiate templates. Coupled with the delayed instantiation (the code of a method is not fully type checked until you use it), static type checking of template code has been a hit or miss. Also, when you do get a type error, it is incomprehensible, riddled with the instantiation details that shouldn't be there in the first place. Interface checking means that the compiler can do better type checking before template instantiation. Interface checking has been in development for some time (e.g. Boost Concept Check, ConceptCpp, N2773), but it didn't make into the C++11 standard.

Interface checking in most programming languages follow a fulfillment model where an interface specifies a collection of function method signatures, and if a class implements all the functions (fulfills all signatures), then it is said to implement the interface. This is the case for Java and Go language as well as C++ concept checking in development so far.

However, if I were to develop interface for a new language, I would choose a declarative model where a class has to explicitly declare the interface it intends to implement. The interface is uniquely identifiable in the program's namespace. The motivation is to prevent a class from unintentionally implementing an interface by coincidence.

This is especially important for C++ since many operators are overloaded. For example, a random access iterator looks a lot like an integral type at the interface level (in fact it is a super concept because you can dereference an iterator), but manipulating the iterator like an integral without observing begin() and end() will cause the iterator to go out of bounds.

This semantic gap can be bridged by a more precise type specification using dependent type (not to be confused with C++ dependent type, a class that is complete if and only if a template argument refers to a complete type; complete type here simply means the compiler knows its memory layout so you can do a sizeof(type), for example, to get its size), but we don't yet have an object oriented dependent type system with interface checking. Even if we can bridge the semantic gap, I argue that a declarative interface checking is not less powerful than fulfillment interface checking.

Suppose you have a class Foo that implements all the methods required for interface Xyzzy, but Foo doesn't declare it so. In the fulfillment model, Foo can be used to instantiate any template (generic) that requires interface Xyzzy, but not in the declarative model, which requires Foo to explicitly state that it implements interface Xyzzy. Even if you cannot modify the definition of Foo, all you need to do is to subclass Foo and declare that it implements Xyzzy, and pass it to the template.

Another idea I have (in the context of C++ concept checking at least) is to get rid of the distinction between a class and an interface. Any class can be used as an interface. That's because C++ allows declaration and implementation to be separate. Furthermore, when a class is said to implement another class, it does not mean the class is a subclass of the other class. The compiler will only check that the method signatures are congruent.

Factories and rvalue reference

One of the benefits of rvalue references is that it provides perfect forwarding for libraries. One example is the factory. A factory here is taken in a loose sense to mean any function (as well as a constructor) that has to construct another object using a non-default constructor, taking the initializer from the function's argument. An example factory is shown below.

template<class T>
T *factory(const T& x = T()) {
  return new T(x);
}

Also, the constructor of std::pair is a factory.

A typical use of the factory is to pass in temporary object as the initializer. For example,

std::complex *p = factory(std::complex(1.0, -1.0));

One issue that factories face when the initializer retains resource is what to do with the resource. The resource could be a memory location, a file in the filesystem, or anything whose explicit ownership needs to be established or resource sharing and leak would be an unwanted consequence.

• Sharing the resource is out of the question, since this would violate ownership invariant.
• Stealing the resource may be desirable but not possible, since x is of type const T& which means you cannot modify x.
• Copying the resource could be expensive, for example if x contains a string or a vector with a lot of data.

Part of this issue could be mitigated by the copy constructor of T itself. It could be the case that T only wants to copy some defining characteristics from the initializer and not the data. For example, if T represents a file, then only the file permissions are copied but not file content; or if T is a string buffer, then only the open mode is copied but not the content of the buffer.

Note that std::stringstream does not have a copy constructor, so we're only talking about a hypothetical class. In the case of std::stringstream, most STL implementation probably did not prohibit copy constructor, so the compiler automatically generates one that could end up performing shallow copy of the underlying buffer. This happens to work for temporary initializer like this:

std::stringstream *p = factory(std::stringstream(...));

But if the initializer is an lvalue, then sharing of the underlying buffer would be undesirable.

std::stringstream ss(...);
std::stringstream *p = factory(ss);

Depending on what stringstream's copy constructor does, *p and ss might end up sharing the same buffer, and mutating ss or *p would make the internal states of the other object inconsistent.

With the introduction of rvalue references, we can now give a strong hint to the factory that the internal resources should be transferred.

template<class T>  // factory using copy semantics
T *factory(const T& x) {
  return new T(x);
}

template<class T>  // factory using move semantics
T *factory(T&& x) {
  return new T(std::forward<t>(x));
}

Note that without the std::forward<T>, a named rvalue reference is treated as an lvalue reference when used [N1377], and we would end up calling the non-const lvalue reference constructor (i.e. T(T& x)) or fall back to copy constructor (i.e. the const lvalue reference constructor).

Revisiting the factory using scenario above,

std::stringstream *p = factory(std::stringstream(...));

would use the move semantics rvalue reference factory, and

std::stringstream ss(...);
std::stringstream *p = factory(ss);

would use the copy semantics const T& factory.

This is consistent with N1377 move proposal which says that the most common anticipated overload to be,

void foo(const A& t);  // #1
void foo(A&& t);       // #2

Note that the factory examples in rvalue reference proposal [N1690] do not have a const T& overload. This means that the factory will only steal resources because of the move semantics. And that factory(ss) above will steal the underlying buffer of ss and render it unusable.

The conclusion is that factory must overload both const T& and T&&.

This actually works nicely with existing libraries. In pre-C++0x code, the factory will always copy. A preprocessor macro would detect the availability of C++0x features and add the rvalue reference version to support move semantics in factory.

One last word about regular functions with rvalue reference arguments. In N1377, regarding binding temporaries to references, it is mentioned that a value could be implicitly converted to a temporary, and this is why passing a temporary of T to T& is disallowed.

void incr(int& rr) {rr++;}
 
void g()
{
    double ss = 1;
    incr(ss);
}

Here, incr(ss) implicitly converts ss to an int, and increment is done on the temporary int value instead. This is properly disallowed in C++. However, in the case of rvalue reference, it is a good idea to make the constructor explicit to disallow implicit conversion.

class Foo {
 public:
  explicit Foo(Bar b);  // regular constructor
};

Otherwise, a function expecting Foo&& for argument but given a Bar object would implicitly convert Bar to Foo and operate on the temporary Foo. Furthermore, if Foo also has a rvalue reference constructor taking Bar&&, then the temporary Foo would steal all internal resources of Bar, get passed to the function, and self-destruct. In other words, implicit conversion from Bar to Foo would destroy Bar.

This is likely going to be a very common mistake when more people misuse rvalue reference. On the other hand, it would be wise to limit the use of rvalue reference and never use it like lvalue reference even if you declare the constructors to be explicit. In particular, rvalue reference may or may not modify the argument, so it should not be used as an "out" argument.

C++ enum default constructor

Every C++ enumeration type has a default constructor. Suppose we have the following enum specifier:

enum thing {
  foo = 13, bar = 31,
};

what would the following program print? The answer may be surprising.

#include <iostream>

int main() {
  thing x = thing();  // invokes enum's default constructor.
  std::cout << "x = " << x << std::endl;
  return 0;
}

It turns out that the code above will print x = 0, which is the integer value of neither foo nor bar. The reason is that enum is considered plain old data (ISO/IEC 14882 2003 section 3.9 clause 10), and all POD type have default initializer that initializes the value to zero (ISO/IEC 14882 2003 section 8.5 clause 5).

When dealing with an enum type value, we must always consider the possibility of 0 even if it was not one of our declared choices.

C++ STL std::vector capacity() Not A Substitute For size()

When you use the std::vector<> template in C++, one thing you notice is that the actual capacity(), the number of elements allocated for the internal array, may be different than size(), which is the number of items currently stored by the user. In general, size() <= capacity(). The capacity() can change when reserve() is called, and reserve() can be called by insert() or resize().

When accessing the vector using operator[], the index is not checked against valid bounds. The at() accessor defines valid bounds to be 0 <= i < size(), where i is the argument to at(), and the domain applies to operator[] as well. If you don't check for bounds explicitly, it should at least be an invariant of your code.

It is worthy to note that when size() <= i < capacity(), although your program technically does not access illegal memory (memory checker like Valgrind would not be able to detect it), the elements at those i's are strictly undefined, for the following reasons.

• When the next resize() expands the size(), it will attempt to overwrite the elements in the internal array from the previous size() up to the new size().
• insert(end(), ...) will overwrite the elements in the internal array after size().
• Even if you avoid using resize() and never uses insert(), and rely solely on reserve() and operator[], there could still be a problem when reserve() causes reallocation of the internal array: only up to size() elements are copied from the original array to the new array.

In other words, the elements in the internal array from size() through capacity() are ignored by the vector and assumed to be non-existent. A symptom is that elements with values previously stored by operator[] gets erased to the default, or some other value specified for resize(). It is a bad idea to use capacity() for bounds checking. The proper bounds are defined by size().

Bridging the high level concept with low level detail

I was fascinated with this blog post written by an undergrad, exclaiming with excitement his teaching fellow's announcement saying that "binary search tree and merge sort are broken." From the detail that he cited (posted at Google Research blog, written by Joshua Bloch, the author of Effective Java book), I think he meant binary search, and not binary search tree. The problem has to do with overflow in this line:

int mid = (low + high) / 2;

The assumption is that low, mid and high are both indices to some array, with low <= mid <= high. When you add low and high, the result could overflow and become negative, and mid becomes negative. This causes array index out of bounds. In Java, the code will crash right away due to the run-time array bounds check. In C/C++, it might access bad memory location and cause undefined behavior, including non-termination. The problem will be a different one if you change int to unsigned int, in which case mid will be smaller than both low and high. Although mid will fall inside array bounds, it's still a violation of loop invariant, which could make the code non-terminating in C (Java doesn't have unsigned int type). The fix that Joshua suggested was to write:

int mid = low + (high - low) / 2;

Another fix, if you know that you're using a binary computer (which is most computer nowadays), is this aggregate magic hack to average two integers using bitwise operators.

I'd like to point out that the algorithm is not broken. An algorithm is a high-level concept of how to do the work. The algorithm is correct, and it's provably correct. What is broken is the program, whose capability is restricted by the finite machine they're run on. However, when you translate from high-level to low-level, the loss in computing power (from infinite state to finite state) causes program error. The problem with the kind of computer science education I'm familiar with is that we often teach computer science in the high-level concept, with the (flawed) mentality that mapping it to low-level program will be straightforward. Only someone who actually writes the program will know that the devil is in the details.

Some programming languages are better at bridging the gap than others; one that came to mind is Scheme, which uses arbitrary precision integer, as well as built-in rational number. It is a very useful language for describing algorithms because many of the machine-specific aspects are hidden by the language and its run-time system. However, programs written in Scheme will run slower because of the arbitrary precision integer arithmetic. ML programs using the IntInf package also share the same benefit and shortcoming.

What I think would be very useful is to write the algorithm as a template program that can be instantiated with different integer sizes, but let the compiler deduce its limits. For example, the binary search bug could be avoided if overflow does not happen. The compiler will generate a precondition requiring that the caller of that function must check that low + high <= INT_MAX. If int is 32-bit, then INT_MAX is 2147483647; if int is 16-bit, then INT_MAX is 32767. Furthermore, since 0 <= low <= high < array_length, it suffices to show that if array_length <= INT_MAX / 2, then the function will be safe. The last step is perhaps not deducible by the compiler, but a programmer can use that fact to convince the compiler that the limits are satisfied.

You can almost write such code in the programming language ATS because the compiler statically checks for integer constraints. You will just have to use #include template technique: prepare the algorithm in a separate include file, while each instantiation will define the concrete type int and the value INT_MAX before including the algorithm. However, the language default + operator does not check for overflow, so you will have to write a new declaration of the + operator function type with the appropriate integer constraint. Maybe I'll write a tutorial in another post.

strxcpy—More Consistent, Safer String Copying and Concatenation

This is now published as a Google Project under the name strxcpy. The full motivation article that was previously found in this blog post has been relocated here.

The C language makes it easy to write programs with buffer overflow problems, but there is still something the library can do to help the programmer make fewer mistakes. For this reason, we propose strxcpy(), a variant of strcpy() and strcat(), which combines both string copying and concatenation.

char *strxcpy(char *dest, const char *dest_end, const char *src, size_t n);

The function takes two parameters to define the buffer, dest and dest_end. It guarantees that it will not overwrite the memory location past dest_end, and the string at dest is always NUL terminated. Furthermore, it does not require dest to be a NUL terminated string. The return value is a character pointer to the NUL terminator of the dest string, so that we can easily append another string to it by calling strxcpy() again.

We also propose the sprintf() variants using the same idiom.

char *vsxprintf(char *dest, const char *dest_end, const char *fmt, va_list ap);
char *sxprintf(char *dest, const char *dest_end, const char *fmt, ...);

See the motivation for buffer overflow problems.

Tracking Object Ownership in C++

Ever since the beginning when people program in C/C++, the need to track object ownership is recognized, but there has been a lot of confusions. We need ownership tracking in order to know who is responsible for freeing an object. This is essential for preventing memory leaks, since C++ does not typically use garbage collection (though it can use something like Boehm GC). Ownership tracking is also essential for preventing double-free, which can corrupt the memory allocator's internal data structure.

Ownership tracking does not sufficiently prevent all memory related error. For example, another part of the program could retain an aliased const reference to an object and use it after the true owner frees it. After the memory occupied by the object is returned to the allocator, it could be subsequently used for other purpose, which could be corrupted when someone modifies the aliased original object that no longer exists.

We will need to use the concept of linearity if we also want to prevent aliasing, but a lot of seasoned C++ programmers don't understand this. It is evident, for example, from their disdain about std::auto_ptr<>: when an STL algorithm such as sort() is broken when you use auto_ptr, they blame auto_ptr for the culprit. However, I would argue that the culprit is sort(), which creates an alias for an item in the container and abandons it without proof that it is safe to do so (perhaps because by default, C++ treats everything as plain old data, which means copying and assignment has no side-effect). If an algorithm observes object linearity, then it will work with auto_ptr<>. There has been significant research in the programming language ATS which strictly enforces linearity in its type system, and there is a lot of code implementing common algorithms that satisfy linearity.

While it is great if you can use a new language with built-in linearity checking, what if you're stuck with C++ (e.g. I miss template meta-programming and curiously recurring template pattern)?

The real problem I have with auto_ptr<> is that it automatically frees the object when the auto_ptr<> object is destructed. This means that non-linear code can run for a while, erroneously freeing objects until everything mysteriously disappears, and you will be puzzled by what is going on. Distinguishing move semantic and copy semantic is a start: it alleviates the need of the auto_ptr_ref hack (otherwise auto_ptr<> cannot be returned from functions due to the non-const copying constructor). But move semantics doesn't enforce linearity; items can still mysteriously disappear after they're moved out of the container but not moved back in.

C++ type system does not have the power to enforce linearity during compile time, but the next best thing to do is to make programs crash early when non-linearity is detected. I've been using a home-brew linear_ptr<> class which the only difference from auto_ptr<> is that, whenever there is a delete p, I remove it and replace it with assert(p == NULL). Regardless of move or copy semantics, a linear pointer only tracks the ownership but never frees an object. I've been using this ubiquitously in an implementation of a memory allocator with great success.

In using linear_ptr<>, I came to realize that a lot of times, a function or method doesn't intend to take ownership of the object passed in as an argument, nor does it alias the object pointer, but we want to have call-by-reference argument semantics. In these cases, I use the idiom const linear_ptr<T>& which means that the pointer itself should not be modified (still points to the same object, not taking ownership) but the object itself is non-const, so it could be mutated.

It turns out that in a regular C++ program, you don't need to use linear pointer to express the intention that a function does not intend to take ownership of an object. Just use a reference! The key idea is that delete takes a pointer, not a reference. Since a reference cannot be deleted, it signifies the fact that the caller does not pass ownership of the object to the function. Furthermore, it signifies that the reference cannot be NULL, so the object has to exist prior to the call. The caller loans the object to the function; the function borrows the object from the caller. Of course, the function should still refrain from converting the reference to a pointer or making an alias of the reference, but it is much easier for a programmer to self-discipline in a local context of a function.

The role of references in C++ is often under-appreciated. For example, Google C++ Style Guide imposes a rule on references that prevents you from writing a function that wishes to mutate an object but will not claim ownership.

However, it is important to note that, unlike pointers, C++ references cannot be reassigned. Assignment on a reference will be applied on the object being referenced to, not the reference itself. This means that if you want to repeatedly borrow objects in a recursively defined data structure (e.g. singly linked list, binary search tree), you will have to write recursive functions rather than doing it in a loop.

In the case where you really want to write a loop that repeatedly borrows objects from a data structure, you can use a loan pointer, where the object pointer is cast to a pointer of a loan class of that object. A loan class is a mixin that merely disables the constructor and destructor by making them private.

template<class superTp>
class loan : public superTp {
 private:
  // Disallow constructor and destructor.
  loan();
  ~loan();
};

It most certainly should disallow copy constructor as well, but this is left for an exercise to the reader. When we want to signify the intention to retain ownership, we will make a loan pointer using the following function:

template<class superTp>
loan<superTp> *make_loan(superTp *objp) {
  return static_cast<loan<superTp>*>(objp);
}

A similar function can be written for linear_ptr<> as well, to convert from a const linear_ptr<T>& to loan<T> *.

A loan pointer can be reassigned to reference a different object, but the usual caution about aliasing applies. A function should not retain the alias beyond the scope of the function. I rarely use the loan<T> * idiom myself because C++ reference works most of the times for me to write a function with the intent not to claim object ownership from the owner.

In conclusion, yes, there is a difference between pointer and reference in C++, and the difference is often under-appreciated. You may use pointer argument to signal the intent of the function to take ownership from the caller; but when you use a reference argument, the caller keeps ownership, and the function merely borrows the object for use in the function scope. This takes care of ownership dispute in function call. However, outside of a function call, auto_ptr<> is not enough to enforce linearity in code. Since C++ type system does not statically enforce linearity, the next best alternative is to use linear_ptr<> that detects non-linearity and crashes the program in run-time the earliest possible. These facilities can be used together to help programmers write linear code that is free of memory leak and memory corruption problems due to double-free and free-after-use.

Use try-finally to prevent resource leak

This is not a tutorial, but a critique of a programming language feature known as try-finally.

Mom always tells you to clean up after yourself, or to put things back to where it was when you're done with it. If you don't do that, your room becomes a mess, and your stuff gets lost. A good programmer also follow a similar rule: if you acquired the ownership of an object, you have to release it. A program that doesn't follow the rule leaks resource every here and there, and it consumes more and more resource without being able to reuse them. Sharing might be a virtue in human etiquette, but it makes resource tracking difficult, and poor tracking will eventually lead to resource leak, both in the real world and inside the computer.

The most prominent kind of resource leak is memory leak, and it is the kind of leak most visible to the user thanks to how Task Manager (or top/ps in Unix) shows you the amount of memory used per program. The symptom is that the program uses more and more memory over time, until the operating system can no longer supply its insatiable gluttony, at which point the program crashes in a nasty way. (Greedy humans will eventually crash in a similar way—a forewarning to people who wanted to work for Google in order to indulge in its unlimited supply of gourmet food).

But even if a programmer is in good faith to clean up after himself, some programming languages make it harder than others to do it. For example, the following construct arises often in a non-trivial program:

thing_t *obj = acquire_thing(...);
...
if (...) {
  ...
  release_thing(obj);
  return ...;
} else {
  ...
  release_thing(obj);
}

The reason we could not factor release_thing(obj) out of the two branches of if-then-else is because the then-clause has a control flow that escapes current scope—the return statement, which could also be a continue or break statement, and our discussion still applies. Fortunately, in this case, the code is manageable because:

• The clean up only requires releasing one object.
• There are only two conditional branches, then and else.

Anything more than that, the code starts to become unmanageable.

Some languages make the code easier to write by providing the try-finally construct, so we could rewrite our code like this:

thing_t *obj = acquire_thing(...);
...
try {
  if (...) {
    ...
    return ...;
  } else {
    ...
  }
} finally {
  release_thing(obj);
}

The finally block is executed whenever the control flow escapes the try block. This allows us to write the clean up code only once. You're not required to use exceptions in order to use try-finally.

If your language provides this syntax, the finally statement is the only safe place you put any clean-up code. This is a very useful facility to combat any type of resource leak, especially memory leak. However, taking a look at languages that feature exception handling, many of the languages with finally support are garbage collected, such as C#, Java, JavaScript, Python, Ruby. In particular, C# and Java programs tend to put clean-up code in the object destructor, but garbage collection prevents you from explicitly destroy an object at a precise moment of time. The clean-up code is delayed for an unspecified duration, until the collection cycle kicks in. Rather than using try-finally, you might as well leak the garbage and wait for its collection. This renders try-finally useless for C# and Java—they have no business implementing try-finally in their language.

The only manual memory managed languages with try-finally support are Delphi (Object Pascal) and Objective-C. Try-finally is absent from the C language that is in dire need of the feature.

An interesting exception is C++, which implicitly calls an object's destructor when the control flow leaves the scope the object is declared in, known as resource acquisition is initialization. If we have a pointer to an object allocated in heap using operator new, we could use scoped_ptr<> to delete the pointer when the object leaves the scope. Apparently auto_ptr<> in STL also works, where the copy and assignment semantics moves object ownership from one pointer to another. Some people prefer to outright disallow copying and assignment, so they use scoped_ptr<> instead.

Although scoped_ptr<> and auto_ptr<> facilitates memory resource clean-up, they are not usable with other kinds of resources such as file descriptors and locks, which need other types of clean-up code. Also, any C library managed resource such as graphics context need their own clean-up code. This is why, in C++, it is fashionable to wrap C system or library calls as C++ objects. This requires a humongous start-up effort to want to use C++ along with a C library!

Finally (finally!), I conclude with two recommendations for the language design committee:

• The C language needs try-finally, even if it does not need to support exception handling.
• The C++ language also needs try-finally even if it does have exception handling syntax. This makes interoperability with resources managed in the C language easier.

Emulating C++0x auto keyword in C++

GCC has a typeof(e) operator (more pedantically, __typeof__(e), as typeof is not in C99 nor C++89 standard) that can compute the type of any expression e. It's typically used by macros, whose arguments aren't typed, to create local variables that has the same type as its arguments. For example,

#define max(a, b) \
  ({ __typeof__(a) _a = (a), \
     __typeof__(b) _b = (b), \
     (_a >= _b)? _a : _b })

This definition of max(a, b) prevents evaluating the expressions a and b more than once. These expressions can cause side-effects, such as printing a message to the screen.

The typeof operator apparently also works for C++. It is sometimes awkward to write out the type of the whole expression. For example,

void foo() {
  std::vector<int> v;
  for (std::vector<int>::const_iterator iter = v.begin();
       iter != v.end();
       iter++) {
    /* ... */
  }
}

Writing the type for the iterator is cumbersome. In C++0x, this code can be written like this using the auto keyword.

void foo() {
  std::vector<int> v;
  for (auto iter = v.begin(); iter != v.end(); iter++) {
    /* ... */
  }
}

In C++, using the __typeof__ keyword, we can write a macro like this:

#define autovar(x, exp) __typeof__(exp) x = (exp)

And the code above would look like this:

void foo() {
  std::vector<int> v;
  for (autovar(iter, v.begin()); iter != v.end(); iter++) {
    /* ... */
  }
}

Here is another use of the typeof operator: sometimes C++ can't figure out how to instantiate a template, and manually writing the type arguments can be tedious. You can use __typeof__ to help the compiler figure out the correct template parameter.

Apparently Boost provides a BOOST_AUTO macro that uses pretty much the same technique.

In C++0x, the typeof keyword is called decltype.

Unit testing not a good fit for exhaustiveness

So I implemented a layered memory allocator from scratch, somewhat in the fashion of Hoard (mine has a different abstraction). My allocator heavily uses C++ Mixin and Curiously Recurring Template Pattern (CRTP). Mixin is an overloaded term, but the concept I'm citing here is a class whose superclass is a template parameter. This allows a limited form of aspect-oriented programming where the Mixin is an added aspect of an existing class. CRPT is a recursive use of Mixin, which coerces the inheritance hierarchy of the user and the Mixin to form one class. The result allows static dispatch of methods which would otherwise have to be declared virtual, and subsequently dispatched dynamically using a virtual table.

Anyway, long story short. After creating many composable layers of memory allocator, I also created corresponding unit test for each layer. However, the unit tests only covered the best case scenario, that Alloc() never returns NULL. It worked well. But I also wanted to test the case where some allocation returns NULL, in order to tell if the layer handled NULL pointer propagation correctly. This unit test scenario turns out to be much of a nuisance.

To briefly explain why, no allocator always deterministically returns a valid pointer, nor does it always deterministically returns NULL, and it's the handling of the non-determinism that matters. Constructing a mock allocator that always returns NULL would still bypass some code paths. To make sure we traverse all code paths, we would have to construct an allocator that returns NULL after n successes for an arbitrary n, and run the unit tests for n = 1, 2, ... and so on. It may never exhaust all possibilities for a complex allocator layer such as the free list allocator. But then, what about a code path that is not reached unless the allocator succeeds every 2 attempts, or one that succeeds every 3 attempts, and so on?

NULL pointer is a special form of the 'a option datatype in ML. The concept is really simple. The 'a option datatype has two constructors, SOME which carries an item of type 'a, and NONE which doesn't carry an item. When a pointer is not NULL, it is assumed that it refers to a valid object, hence corresponds to SOME; when a pointer is NULL, it is assumed that no such object exists (typically due to an exception), hence corresponds to NONE. When you pattern match against the constructors of a datatype, ML also performs exhaustive analysis. Forgetting to check for NULL is a kind of non-exhaustive pattern matching. Since exhaustiveness is a local property, using unit test (which tests for a property that is much wider in scope) is overkill and ineffective. It is very hard to create a unit test that will run all possible execution paths, especially for the error handling code, because simulating all possible combinations of error condition is impractical.

Although a lot of times it's easier to write unit test for operations that are in-spec (e.g. to make sure a sorting algorithm permutes the sequence in order), it is best to leave exhaustive analysis to a compiler, like ATS, which effectively deals with out-of-spec situations.

Captain's Log on Quest

Okay, not quite captain's log.
My office mate has been working on this operating system called Quest, and I'm keeping a record for him about what happened. He had been testing the OS on a virtual machine, and yesterday he decided to try it on real hardware. He found a reasonably recent hardware with APIC support in the lab. He would burn a CD-R, run upstairs, something goes wrong, write down some diagnostic on a piece of paper, run downstairs back to the office, change some code, burn a new CD-R, and run upstairs.
I hate to see CD-Rs being thrown into trash at an incredible rate. After all, CD-Rs are supposed to last for 100 years; whether they still preserve any data or not at that point is an entirely different question. Since each image is small (~2MB), I suggested burning multi-session CDs instead. He tried but couldn't get it to boot. I don't have any other ideas.
Today he bought some CD-RWs, which is an improvement. He also brought his laptop and stayed in the lab most of the time, which cuts the turnaround time a lot. When I visited him, he showed me a strange error that he fixed.
There is a static char arena[1000000]; in the code which is used for rudimentary memory allocation. He found out that if he did not initialize this arena to zero, then the code that initializes this memory with free list pointers would have page fault, accessing memory at some outrageous location (this is typical of array out of bounds problem somewhere else, polluting the arena).
I told him to try to memset to 0x5A instead. It will give us a clear indicator of what's wrong. He burned the CD-RW (had to erase the whole disk first) and booted it up. Lo and behold! The whole text-mode screen was then filled with bright green Z with pink background (thank goodness I didn't suggest 0xA5, or it would be filled with *blinking* purple Ñ on green). It seemed that the arena overlapped with text mode video buffer.
Another lesson learned about writing operating systems: double check special hardware physical address mappings.

Manifesto of a Very Hard To Find Memory Leak (To Be)

I'm implementing a hash table that will become the basis of a free list memory allocator. The hash table uses singly linked list for buckets. In the list implementation, there is a RemoveAll function written like this:

void RemoveAll(Predicate& p, Consume& c)
{
Node **result;
for (result = &first_; *result != NULL; result = &(*result)->next_) {
if (p(**result)) {
Node *node = *result;
*result = node->next_;
node->next_ = NULL;
c(node);

if (*result == NULL)
break;
}
}
}

Admittedly, the code is copied from a similar function called Remove(), which removes only the first node that satisfies the predicate. However, when it is modified to remove all nodes, an unintended side effect is, if a node is to be removed, it always skips the next node. When I wrote a unit test, I inserted nodes for 0 through 16, and removed all the even nodes, so this problem was not detected. However, when I used this function with a predicate that always returns true, I noticed that the list is not cleared properly.
Now, this function is used in the hash table to clear all the buckets. Each item in the bucket would be a free list for a certain size of objects. When a free list memory allocator uses this hash table, it will see memory leak on a certain size of objects, and the size would appear to be at random.
Fortunately, when a list is destructed, I have it do nothing but to assert that the list is empty. This helped detecting the problem early. Unit test for the hash table to clear all entries helped bringing this problem to the surface.

Kernel page tables

My office mate has been working on an operating system kernel, and apparently page table manipulation is very error prone. Here are some important things that are easy to forget:

• Special memory I/O pages cannot be freed into the general page pool, such as the physical address used for I/O APIC. If it happens, then another program would allocate the memory I/O page and then write to that physical address as if it's RAM.
• If two address spaces share a page (mmap w/ MAP_SHARED, or shmat), then pages need to be reference counted.
• If two processes share the same page table (clone system call), then page tables need to be reference counted.

Since he's too engaged in debugging, I'm writing these down for him in case he forgets. I said to him, maybe the reason why people haven't made ground-breaking research into redesigning operating system architecture because the moment you walk in, you get lost in the woods, and you don't see the forest anymore.

Interview Question

Yet another interview question that I came up with. This one tests the interviewee's ability to read and understand basic specifications.
You have a C program written to run on Linux that uses strndup(3), size-bounded string duplication. The function returns a copy of a source string only up to n characters. The copy is allocated using malloc(), and the copy is always zero-terminated even when the source string may not be. When you try to compile the program on Mac OS X, you found out that their Standard C library doesn't have strndup().
After browsing around, you found the functions strlcpy(3) and strlcat(3) which are the size-bounded string copying and concatenation. Can you use them along with malloc() to implement strndup()? If so, show your work. If not, explain why not.

Objective-C memory management

Here is a quick summary of Objective-C memory management.

Objects are reference counted, so if you do:

NSClass *objp = [[NSClass alloc] init];

It will need an accompanying:

[objp release];

But many Core Foundation classes also have factory (class) methods that look like:

NSSomething *objp = [NSSomething somethingWithInitializer:initializer];

For example, NSArray methods +array, +arrayWithArray, +subarrayWithArray, ...; NSString methods +string, +stringWithString, ...; and so on. The convention used by Core Foundation is that the object returned by factory methods still have reference count of 1, but they are added to the "autorelease" pool. You do not release nor autorelease these objects!

The "autorelease" pool is simply a list of objects to be released at a later time. The pool is dynamically scoped (like exception frames) and is unrelated to the static (lexical) scope of the program. When the program leaves an autorelease scope, all the objects in the pool of that scope are released. An object can be added to the pool several times, in which case it will be released the same number of times they are added to the pool. There doesn't seem to be any way to take an object out of autorelease pool.

Cocoa's Event Manager always creates an autorelease pool frame prior to handling an event. The frame is popped after calling the event handler. This means your program typically creates some garbage that is cleaned up altogether after finishing an event. Objects that outlive the scope of an event must be explicitly retained.

Apparently, Leopard also supports garbage collection with the -fobjc-gc GCC flag.

Making NULL-pointer reference legal

Normally, NULL pointer reference results in access violation and is illegal. However, it is possible to make NULL pointer reference legal on several operating systems. There are two ways to do that: (a) using mmap(2) with MAP_FIXED flag (works on Linux and Mac OS X), and (b) using shmat(2) with the SHM_RND flag (works on Linux). Consider the following program:

#include "stdio.h"
#include "sys/mman.h"

int main()
{
void* p = mmap(
NULL, 4096, PROT_READ | PROT_WRITE,
MAP_FIXED | MAP_PRIVATE | MAP_ANON, -1, 0);

if (p == NULL)
printf("*(NULL) = %x.\n", *((int*) NULL));
else
perror("mmap(2)");

return 0;
}

The program, when run on Linux and Mac OS X, prints *(NULL) = 0, and that's the result of the program doing a NULL pointer reference. This doesn't work on AIX.