27 April 2012

C++ Functional Style Tips

To say that C++ is a complex language would be an understatement—I had to spend years using it before properly understanding all of its many gotchas. Because I have plumbed its depths, I cannot recommend it to anyone for any purpose. If you know how to use the language effectively, then by all means do use it—but if you do not already know it, then there are plenty of other, perfectly good languages out there. Personally, I’m a fan of C, Haskell, and Scheme.

However, the language is still undeniably useful, particularly in game development. So I must try to benefit from the power of C++ while avoiding its failings in every way that I can. Following, then, are some brief guidelines that I have found to work well for me to write C++ code in a more functional style. And functional style makes it easier to grasp a program by reducing the effort required to understand its possible states—so you can focus more on solving problems than fixing bugs.

For the sake of concision, I’ll assume that using namespace std; and using namespace std::placeholders; are in effect. Obviously in real code you ought to import only what’s necessary, and in as small a scope as possible.

♦ ♦ ♦

1. Use const Obsessively

C++ unfortunately has no reasonable way of enforcing referential transparency. You cannot readily make the compiler complain when a function has externally visible side effects. Indeed, I hope C++2x gets a pure keyword. But in the meantime, at least we have the ability to enforce immutability with our good friend const.

In general, everything should be const unless it truly needs to be modified—whether because an in-place algorithm is more efficient than its non-mutating equivalent, or because of failings in the type system and standard library. As an example of the latter, you cannot use standard algorithms to initialise an immutable container, resulting in objects that are unnecessarily non-const.

Declare member functions const if they are logically non-mutating, that is, you would expect that calling the function in and of itself will have no effect on the observable state of the object.  “Observable” means that you can deduce said state through the public interface alone.

struct Point {
    double distance(const Point&) const;
    double distance(double, double) const;
    double x, y;

When taking parameters by lvalue reference, use const when possible.

    double distance(const Point&) const;

When taking parameters by value, declare the function as usual.

    double distance(double, double) const;

Then make the parameters const in the definition, unless of course they are to be modified.

double Point::distance(const double x, const double y) const {

Don’t bother returning by const value—all it does is arbitrarily prevent calling mutating member functions on temporaries—but do return const references where appropriate.

const vector<double>& TreeNode::get_children() const {
    return children;

Make local variables const when possible.

double Point::distance(const double x, const double y) const {
    const auto dx = this->x - x;
    const auto dy = this->y - y;
    return sqrt(dx * dx + dy * dy);

Be sure to use const qualification for pointers where appropriate.

T* x;             // Mutable pointer to mutable T.
const T* x;       // Mutable pointer to immutable T.
T* const x;       // Immutable pointer to mutable T.
const T* const x; // Immutable pointer to immutable T.

This also applies to smart pointers such as unique_ptr (which you should use a lot) and shared_ptr (which you probably don’t need).

shared_ptr<T> x;             // Mutable shared pointer to mutable T.
shared_ptr<const T> x;       // Mutable shared pointer to immutable T.
const shared_ptr<T> x;       // Immutable shared pointer to mutable T.
const shared_ptr<const T> x; // Immutable shared pointer to immutable T.

Related to const is constexpr, which allows you to ensure that if a function can be evaluated at compile time, then it will be. This has less to do with functional style and is more a matter of optimisation, so I mention it only for the sake of completeness.

♦ ♦ ♦

2. Use <functional>, <algorithm>, <numeric>, and <iterator>

The C++ standard library has a number of common algorithms abstracted into iterator-based functions. While iterators have some flaws, they can often help you write code that is more readable than the alternative using explicit loops.

bind() lets you perform partial application of function objects.

const auto succ = bind(plus<int>(), _1, 1);
cout << succ(3) << '\n';

Here, bind(plus<int>(), _1, 1) is equivalent to the section (+1) in Haskell.

There are two versions of transform() to be found in <algorithm>. The first is analogous to the familiar functional map, applying a unary function to each element in a range and sending the results to an output iterator.

const vector<int> a{1, 2, 3, 4, 5};
vector<int> b;
transform(a.begin(), a.end(), back_inserter(b),
    bind(plus<int>(), _1, 1));

The second version is analogous to zipWith, which takes two input ranges, applies a binary function to each pair of elements, and sends the results to an output iterator.

const vector<int> a{1, 2, 3, 4, 5};
const vector<int> b{5, 4, 3, 2, 1};
vector<int> c;
transform(a.begin(), a.end(), b.begin(),
    back_inserter(c), plus<int>());

accumulate(), from the <numeric> header, is by default a sum:

const vector<double> values{3.1, 4.1, 5.9, 2.6, 5.3, 5.8};
const auto sum = accumulate(values.begin(), values.end(), 0.0);

With a binary function, it becomes a left fold:

const auto product = accumulate(values.begin(), values.end(),
    1.0, multiplies<double>());

C++11 introduces lambdas to C++, which are largely syntactic sugar for anonymous classes—the members of the class are the (explicit) closure from the lambda’s lexical environment, and the operator() of the class is the lambda body. When you need to use a non-trivial function in a standard algorithm, it’s clearest to use a lambda rather than trying to compose function objects.

const auto paraboloid_product = accumulate(values.begin(), values.end(),
    2.0, [](double x, double y) { return (x - 1.0) * (y + 1.0); });

On the other hand, sometimes it’s better to use a simple for loop. Case in point: the for_each() algorithm, which conveys no more information than an ordinary range-based for, and can become unreadable when the types are non-trivial.

// Do this.
for (auto& p : symbols)

// Or this!
for (auto p = symbols.begin(); p != symbols.end(); ++p)

// Not this.
for_each(symbols.begin(), symbols.end(),
    [](pair<const string, shared_ptr<Value>>& p)
        { p.second->method(); });

♦ ♦ ♦

3. Use auto and decltype()

The C++11 auto keyword allows you to omit the manifest type of a variable, if a type can be deduced from the variable’s initialiser. Combined with const, this makes C++ variables look an awful lot like single static assignment registers.

const auto v = f(x, y);

Just as auto is used to deduce a declaration from an initialiser, decltype() is used to deduce a type from an expression:

decltype(v[0]) w;

Like sizeof(), decltype() does not evaluate its argument, so it’s safe to use side-effectful functions in a decltype() expression. Like const, you ought to use auto and decltype() wherever possible, specifying manifest types only when necessary. auto lets you avoid repetition at the type level, and decltype() lets you express types as contracts in terms of other types.

♦ ♦ ♦

4. Use Higher-Order Macros

One of the reasons I’m fond of functional and concatenative programming is an increased ability to reduce repetition through factoring. A functional style, and in particular a point-free style, is vastly more amenable to refactoring than imperative code. Unfortunately, C++ often makes it unwieldy to do such refactoring, even with functional style, because it is inherently an imperative language.

Despite its limitations and caveats, the C preprocessor is useful for eliminating repetition. Unlike, say, Lisp macros, which are Turing-complete, CPP is only equivalent in power to a pushdown automaton. Still, macros have one powerful feature that I use regularly: they can take other macros as arguments. Thus you can define a sequence like so:

#define FUNCTIONS(M) \
    M(add, +) \
    M(sub, -) \
    M(mul, *) \
    M(div, /)

And apply macros to every term in the sequence:

#define DECLARE(N, O) \
    int N(int, int);

#define DEFINE(N, O) \
    int N(int x, int y) { return x O y; }


#undef DEFINE
#undef DECLARE

When C++ fails to provide a mechanism of semantic abstraction for a particular problem, higher-order macros at least allow you to abstract syntactically repetitive code. Judicious use of macros to reduce repetition is a Good Thing, even if it might make you feel a bit dirty.

♦ ♦ ♦

I’m sure there’s more I’m forgetting, but that’s the meat of it. Functional style can help you out, and here are some ways to do it. These aren’t rules, just guidelines, and you should always evaluate each problem individually to determine if the usual patterns really fit. Programming is, after all, a very subtle magic. But if there’s any way to make that magic a little more fun, I’ll take it.

16 April 2012

Frighteningly Ambitious Programming Language Ideas

Use versus Mention

The use–mention distinction—in addition to being one of the rare opportunities to use an en dash—is a distinction between application of a term for its inherent meaning (Brian is alive and has no letters) and examination of the term for its superficial representation (“Brian” has five letters and is not alive). In natural languages, we typically use quotation to differentiate between use and mention.

This distinction is one of those apparently mundane linguistic phenomena that turns out to have rather subtle and interesting philosophical implications. In particular, use without mention is the basis of pronouns and demonstratives—in “He picked up the book and studied it”, it refers to the same thing as the book, without repeated mention of the book. These structures in turn allow self-reference, as in the liar paradox (“This statement is false”) and Quine’s paradox:

“Yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation.

Reference and self-reference are two things that come up quite often in programming. If you’re a language designer with a mind to fundamentally alter how programming is done, then the ideas that follow are yours for the taking. They are difficult, unattractive, dragonish ideas, and it will be many years before ordinary developers take them seriously.

But first, some background.

♦ ♦ ♦

Reference and Quotation

Every aspect of natural language has a parallel in artificial language. Concrete referential types such as pointers are also references in the abstract sense. Pointers are like pronouns in that they allow you to refer to a thing itself, rather than through its name. Take this C code:

T x;
T *y = &x;

Here, *y refers to the very thing that x does. In addition, it allows a form of lazy evaluation: we can pass around copies of y as much as we want, without creating copies of *y. Deferred evaluation thus has performance benefits, but more fundamentally, pointers allow us to create data structures of a wholly different shape than the memory in which they live—trees and graphs and so forth. More on that later.

So in C, taking the address of a variable is a form of quotation, preventing the evaluation (copying) of that variable until the pointer is dereferenced. In Lisp, the quote special form likewise denotes mention rather than use, but of any expression:

(f x y)         ; Use
(quote (f x y)) ; Mention
'(f x y)        ; (Shorthand for the above.)

Concatenative languages have this as well:

y x f     # Use
[ y x f ] # Mention

This is essentially a generalisation of pointers—deferring evaluation through quotation. Lisp programs can pass around code unevaluated as easily as C programs pass around data uncopied. This largely eliminates the distinction between data and code, and allows still more kinds of laziness. Anonymous functions are similar to quotations, but a bit heavier in that they also have a closure of variables from their (lexical or dynamic) environment.

♦ ♦ ♦

To Infinity

But as it turns out, it’s not even strictly necessary to make a distinction between use and mention. The most visible example of this in practice is probably Haskell, where evaluation is non-strict by default. Every expression is nominally a reference (thunk) to be evaluated only as needed. To support this, most types are implicitly referential (boxed). Non-referential (unboxed) types are available for internal use and low-level optimisations.

In a way, lazy evaluation is rather like garbage collection. GC simulates a machine with infinite memory; lazy evaluation simulates a machine capable of infinite computations. In Haskell, it’s normal practice to construct infinite lists and cull them as needed. That’s backward as far as most languages are concerned, but it also turns out to be a very intuitive way of modelling many kinds of problems.

So we can work with infinities of space and time on finite machines. But can we generalise further? Well, yes, but the results look pretty alien. Here be the aforementioned dragons.

♦ ♦ ♦

Dimensionality and Topology

Our computations are essentially two-dimensional, with one dimension of space (memory) and one of time. More time dimensions are possible, but I don’t see the use, considering our universe seems to have only one. I’d appreciate comments from anyone who can offer an application of such a thing.

You can very easily generalise to more memory dimensions, though. 2D memory allows you to construct, say, a matrix where each element is adjacent in memory to all of its neighbours. You just allocate memory in rectangular rather than linear regions. Unfortunately, you lose a sane ordering relation on pointers.

You can also play with the memory topology—cylindrical, spherical, or toroidal memory lets you construct fixed-size circular arrays, where each element is adjacent to the next, and the last is also adjacent to the first. Slightly stranger topologies allow variable-length circular arrays. And beyond familiar shapes and grids, any lattice graph can serve: in a 2D hexagonal topology, for instance, each memory location is adjacent to six others.

Our programming languages, too, tend to be one-dimensional, much like our natural languages; but this, too, is not a requirement. Indeed, two-dimensional languages and higher-dimensional languages have been made, but it’s probably more practical to add 2D features to a predominantly 1D language:

# Probably a good idea:

matrix = 1 2 3
         4 5 6
         7 8 9

# Maybe a good idea:

lispy_boxes = +-------------+
              | * +-------+ |
              |   | + 2 3 | |
              |   +-------+ |
              |   +-------+ |
              |   | + 4 5 | |
              |   +-------+ |


         (   divisor  ) exponent    n
result = | ---------- |          * sum set(i)
         (  dividend  )            i=0

Furthermore, 1D languages require jumps for flow control, but since any graph can be embedded in three dimensions, languages of three or more dimensions can be written jump-free. An easy way to do this is to allow changing the direction of the instruction pointer rather than its position.

And for you CS theory types looking for something to do a Ph.D. on, it’s a fun problem to figure out whether a language with a strictly planar state diagram can be Turing-complete. Go nuts.

♦ ♦ ♦

Diffing, Visualisation, and Editing

As with memory, languages could be given any number of interesting topologies beyond the usual grid. Tool support, of course, becomes something of an issue. It’s relatively easy to see how a diff would work in a 2D or 3D Cartesian language, but more complex spaces are problematic.

In one dimension, diffing relies on the longest common subsequence problem (LCS). While this problem is NP-hard, it can be solved in polynomial time using dynamic programming for a constant number of sequences—usually two, the previous and current versions of a file.

In more complex spaces, you have to rely on the maximum common subgraph isomorphism problem (MCS), which too is NP-hard. Luckily, MCS is solvable in polynomial time when the circular ordering of edges around vertices in an embedding is constrained, as it would (almost?) certainly be. But you don’t need to add complexity when you generalise—hell, for some languages, you might only need simple graph difference.

No, the really problematic things are visualisation and editing. How do you display removals and insertions in multiple dimensions and unusual topologies? Even for 2D images there are many equally good ways to visualise differences. How do you let a programmer efficiently and reliably create, alter, and share programs outside the realm of 1D text?

♦ ♦ ♦

And Beyond

Programming is still a fairly new field. Our languages are hovering around a local maximum, but there’s little reason to think we couldn’t come up with something better, more fun, and more productive. We need to be willing to sacrifice some of the things that make existing languages great, because they might have no analogue in a better system.

In other words, we should not imagine aliens in terms of the creatures we know. A green dog with antennae is still a dog. We should instead imagine things that make us legitimately uncomfortable to think about. Things that are unattractive not because they’re peculiar or dangerous, but because they’re deeply unsettling. Think Marvin the Martian versus the blind idiot demon sultan Azathoth. If those aliens exist, then not only does it mean we’re not alone—it means we’ve been wrong this whole time. And that, unfortunately, is how progress works.