I haven’t blogged for a while.  I recently submitted a paper I’ve been working on for some time and I find it hard to “multitask writing”.  It’s like the part of my brain responsible for writing (as opposed to programming or other stuff) cannot do two things at the same time.

Apart from writing this new paper I’ve been working on presentations for the SPLASH 2016 conference, in which I’m presenting three different things (a poster, a demo about Cloudlog and a workshop paper on Cedalion).  I will write about all of those sometime before the conference.

… and of-course, I’m also working on cedalion2.  Stay tuned for updates…

But today I want to write about something completely unrelated I came across recently.  I’ve been using C++ practically all my professional life.  I learned it from a book (in Hebrew) even before I learned C…

I don’t like C++ very much.  If you learned anything from my blog so far, I’m more into declarative languages, and if they have to be imperative, I prefer those where I cannot create buffer overruns by mistake, or use an allocation that has already been freed.  But somehow my professional career went a certain way and I came to use C++ for most of it.

For most of my time working with C++ I knew there was more to it than meets the eye.  But until I went there and checked for myself I didn’t realize how cool it can be.  In this post I’ll give a taste of C++, but not the way you (probably) know it.  Most people know it as an imperative, statically typed, eager, compiled object-oriented programming language.  In this post I’ll show you why it is a declarative, dynamically typed, lazy, interpreted functional programming language.

All the code examples in this post can be found here.  Comment-out and uncomment the different main() functions to get results from the different parts.

C++ is Three Languages

C++ is actually a combination of three different languages.  When programming C++ we are well aware of all three, but for some reason we focus on the least interesting one — the object-oriented, imperative, statically-typed, unmanaged variant of C. This language is the one that has the largest number of features, but it is for this feature richness that C++ is so criticized:

1983 - Bjarne Stroustrup bolts everything he's ever heard of onto C
to create C++. The resulting language is so complex that programs must
be sent to the future to be compiled by the Skynet artificial 
intelligence. Build times suffer. Skynet's motives for performing
the service remain unclear but spokespeople from the future say
"there is nothing to be concerned about, baby," in an Austrian
accented monotones. There is some speculation that Skynet is nothing
more than a pretentious buffer overrun.

The other two languages comprising C++ are the preprocessor macro language, and the template language.  The C++ preprocessor is inherited from C, and it makes C++ a pure functional programming language the same way it makes C.  But that is not (that much) interesting either.  The template language (or sub-language, if you will) is the one I find the most interesting part of C++, and the topic of this post.

C++ is a Dynamic Language

it’s all about perception.  When I was an undergrad, I was taught that in software you need to have a clear distinction between compile-time and run-time. One should not confuse between the two.  The compiler has partial information.  It only sees your code. It doesn’t see user input. At run-time, however, the program does not see things like function names and types.

So first, I was taught wrong. Function names and types do exist at run-time in some languages.  Not in C++ (ok, very partially in C++.  See dynamic_cast as one example). And of-course there are all these dynamic languages like Javascript and Python and Cedalion, where there is no compile-time because there is no compiler (or at least not one that users actually see).  But even in a language like C++, where the the traditional separation of compile-time/run-time still exists (at least to some extent), what happens if we treat one of them as the other?

Templates are evaluated at compile time.  This makes the C++ “compile-time” the “run-time” for its templates sub-language. If we embrace that, and refer to C++’s compile-time as our “run-time”, our language becomes dynamic.  The C++ compiler becomes an interpreter for the template language — it does not compile the template themselves into machine code.  Instead, it evaluates the templates into classes and functions, and then compiles them into machine code.  The compiled code can then run (at run-time), but the templates are long-gone by then.

Crunching Numbers

I think a small code example is in order here.  The following template takes a type parameter, and provides a class with a single print() method.  It assumes the given type T has a constant T::val member, and the print() method simply prints this constant.

template <typename T>
struct Print {
    static void print() {
        std::cout << T::val;
    }
};

Note that T::val is constant, so print() doesn’t calculate anything at run-time.  We are using run-time merely to print our result.  Now let’s create something we can print.

template <int N>
struct Int {
    typedef int type;
    static const type val = N;
};

Int<> is a class template that wraps an integer.  Why do we need a class template to wrap an integer? Because Print accepts a type, not an integer… So if we want to print 5, we can simply do:

int main() {
    Print<Int<5> >::print();
}

(depending on your C++ version, you need a space between the closing angle brackets: > >).

OK, this is not impressive.  We could have just printed 5… So let’s do something more impressive.

template <typename A, typename B>
struct Plus {
    typedef A::type type;
    static const val = A::val + B::val;
};
int main() {
    Print<Plus<Int<5>, Int<3> > >::print();
}

This should print 8!  I know.  It is not that impressive either,  but at least we saw some computation that took place… but not at run-time… at least not the C++ run-time.  The computation took place at C++’s compile-time.  As far as the Print::print() method is concerned, it printed a constant.

Obviously, it is possible to add more operators and create a rich expression language. Still not full-blown functional programming, but getting there. One thing to note here though is another change in perception. The values our templates are working on are not values for C++ — they are types. We treat types as values. This is an important analogy we are going to get back to shortly.

Lists

Lists and functional programming languages go together like love and marriage, horse and carriage, or the Buckingham Fountain and the “Married with Children” theme song. Lisp, the world’s first functional programming language ever was literally made out of lists. Since then every functional language I can think of has special syntax for lists.  So if C++ is functional, it can handle lists!

As in most functional programming languages, a list is one of two things. It is either an empty list, we call Nil, or it is a list item, which we will call Cons after its name in lisp.

struct Nil {
    typedef Nil self;
};
template <typename Head, typename Tail>
struct Cons {
    typedef Cons<Head, Tail> self;
};

Because Nil is just an empty list, we made it a struct and not a template.  Remember that types are our values? So what is a struct (or a class)? This is a type that is not augmented by arguments (unlike templates). This makes it a constant.  Cons, on the other hand, is a template getting two arguments: a Head and a Tail.  These represent the first element in the list and the rest of the list, respectively. Note that they are types, but types represent values. This list is untyped. Unlike languages like Scala, Haskell or ML, there is no guarantee that all element of such a list will be of the same “type”, because our language is dynamically typed.

One thing that may seem awkward here is the definition of the self type in both Nil and Cons. I’m not going to talk about it right now. We’ll get to that when talking about C++ as a lazy language.

List Sum

We defined a list, so let’s do something awesome with it. Let’s sum its elements.  OK, summing a list is not that exciting, but it’s a start.  For that we need to define a function. If types are values, what is a function? A template is sort-of a function, because it gets parameters and has some value, but how can we use it to construct another type? To do this, we pull another trick from C++ magic hat: inheritance.

template <typename List>
struct ListSum : public Int<0> {};

template <typename Head, typename Tail>
struct ListSum<Cons<Head, Tail> > : public
    Plus<Head, ListSum<typename Tail::self> > {};

Here there are a few things to notice. First, the definition of ListSum consists of two parts. The first is the default case, treating Nil or any other non-Cons (remember, this is a dynamically-typed language, so we have no guarantee we only get Cons and Nil in a list). In all non-Cons cases, the sum of the list is defined as zero. How? we just derive from Int<0>. This way, when we wish to print the value the Print::print() method will consult the val constant in our class. If we derive from Int<0>, we inherit val=0 from it.

The second part is a C++ template specialization, of ListSum, which specializes it for the case of Cons. Template specialization performs pattern matching, in a way very similar to many functional (and logic) programming languages. But again, it does it on types, which we treat as values. So we specialize ListSum for a list element (Cons). Here too we use inheritance, but here we derive from a more complex template, representing the sum of the first element and the rest of the list, which we get by recursively calling this function. Yes. our language supports recursion!

typedef Cons<Int<1>, Nil> l1;
typedef Cons<Int<2>, l1> l2;
typedef Cons<Int<3>, l2> l3;

int main() {
 Print<ListSum<l3> >::print(); // will print 6
}

“Real” Functional Programming

So we can define functions. Big deal… everybody who knows something about functional programming knows you can’t call it functional programming unless you have a Lambda. For readers not familiar with functional programming or the Lambda Calculus, a Lambda is a function, which is also a value. In functional programming functions are first-class, meaning you can pass functions to functions as arguments. If you can do this, there are a lot of neat things you can do. I don’t want to go into all of this. I just want to show you how you can define lambdas in C++ (and I’m not talking about C++11 lambda functions. These are part of the “boring” part of C++).

Since our language is a dynamic one, we define everything by how they are being used. A lambda function is used by applying it to an argument. In our implementation here, as in the Lambda Calculus, a lambda function receives only one argument. There are two different techniques for handling multiple arguments: tuples and curriying. Both are applicable here, but I will not go into these.

So in order to allow lambdas, we need to define the Apply operator:

template <typename Func, typename Arg>
struct Apply_ {};

template <typename Func, typename Arg>
struct Apply : public
    Apply_<typename Func::self, Arg> {};

We defined two very similar templates: Apply_ and Apply. Users should use Apply, but if you wish to define a function, you should do so using Apply_. What is the difference? The difference is that self thing we saw earlier. I’m still holding discussion on it until we see some lambdas in action.

So to that end, let’s define a function that takes a number and increments it.

struct Inc {
    typedef Inc self;
};

template <typename Arg>
struct Apply_<Inc, Arg> : public Plus<Arg, Int<1> > {};

There’s nothing new here. All we did was specialize a template, that is, use pattern matching to define a solution for the Apply_ function. This specialization gave meaning to the otherwise meaningless Inc struct.

So now we can do something fancy like a Map function, which converts one list into another, by applying the given function on each element.

template <typename List, typename Func>
struct Map_ : public List {};

The default definition returns the “List” unmodified (Nil will remain Nil).

template <typename Head, typename Tail, typename Func>
struct Map_<Cons<Head, Tail>, Func> : public
    Cons<Apply<Func, Head>, Map<Tail, Func> > {};

This specialization constructs a new Cons for each Cons being read from the input list, applies Func to the head, and Map to the tail.  The only piece missing is doing the ::self thing:

template <typename List, typename Func>
struct Map : public Map_<List, Func>::self {};

So now is a good time to talk about it.

C++ is Lazy

The C++ you probably know uses eager evaluation like most other programming languages. Eager evaluation means that when you have an expression that involves a function invocation (e.g., f(g(1), 2)), the arguments are evaluated first and then the function is applied on the values. This strict order of evaluation is needed in impure programming languages, because we need to know when side effect happen.

In contrast, lazy evaluation means that evaluation only occurs at the last possible moment. So in the above example, g(1) will not be evaluated until f() will actually need the value (e.g., when it will add or subtract or multiply it by something). Only a small minority of languages uses lazy evaluation. Haskell is the best known one. Lazy evaluation requires purity, so only pure languages can even consider lazy evaluation.

But the C++ template language is pure. And it is lazy! How do I know it? because I can define an infinite list, and still have a program terminate.

template <typename Val>
struct Inf : public Cons<Val, Inf<Val> > {};

The Inf function returns a list where the first element is the given value and the rest of the list is the same infinite list… The C++ compiler should have no problem evaluating this (e.g., typedef Inf<Int<2> > inf2), but don’t try to sum it…

Being lazy allows us to create crazy things like infinite lists and get away with it. But sometimes we need to force an evaluation. One example for such a time is when we wish to use template specialization (pattern matching). In such cases we need to tell the compiler we want the value, not the expression. So how do we do this? We add ::self. C++ template specialization does not consider inheritance.  If A derives from B, a specialization on B will not be considered for A. However, the self type we defined in “value” classes and templates like Nil, Cons and Inc is passed to derived classes, such as our functions. Since self is typedefed in all such cases to the value itself, by referencing it we force the compiler to figure out what the actual type is, and hence we force it to evaluate the function.

The following code will print 9:

int main() {
    Print<ListSum<Map<l3, Inc>::self> >::print();
}

We need to call ::self here so that ListSum will see a Cons and not a Map, which it does not know what to do with. In other words, we need to explicitly tell C++ to call Map and pass its returned value to ListSum.

Conclusion

So I showed how C++ can be treated as an interpreted, dynamically-typed, lazy functional programming language.  I want to stress that while this is kind of news to me, this is not new knowledge.  One question I can’t escape is “is it useful”?

At first glance, probably not. There are other dynamic functional programming languages out there. Most of them have much better syntax and run much faster (than the C++ compiler, not C++ itself). However, our weird language has one thing most other programming languages do not have: its output is a (standard) C++ program! And this kind of programs are known to run very fast.

So an interesting angle for all this is to think of ways to use the C++ compiler to build “compilers” written in C++’s template language, that run at compile-time, and emit C++ programs. I don’t know exactly how to do this, but I guess when an opportunity will present itself I may try…