Tag Archives: c++

On ESR’s thoughts on C and C++

ESR wrote two blog posts about moving on from C recently. As someone who has been advocating for never writing new code in C again unless absolutely necessary, I have my own thoughts on this. I have issues with several things that were stated in the follow-up post.

C++ as the language to replace C. Which ain’t gonna happen” – except it has. C++ hasn’t completely replaced C, but no language ever will. There’s just too much of it out there. People will be maintaining C code 50 years from now no matter how many better alternatives exist. If even gcc switched to C++…

It’s true that you’re (usually) not supposed to use raw pointers in C++, and also true that you can’t stop another developer in the same project from doing so. I’m not entirely sure how C is better in that regard, given that _all_ developers will be using raw pointers, with everything that entails. And shouldn’t code review prevent the raw pointers from crashing the party?

if you can mentally model the hardware it’s running on, you can easily see all the way down” – this used to be true, but no longer is. On a typical server/laptop/desktop (i.e. x86-64), the CPU that executes the instructions is far too complicated to model, and doesn’t even execute the actual assembly in your binary (xor rax, rax doesn’t xor anything, it just tells the CPU a register is free). C doesn’t have the concept of cache lines, which is essential for high performance computing and on any non-trivial CPU.

One way we can tell that C++ is not sufficient is to imagine an alternate world in which it is. In that world, older C projects would routinely up-migrate to C++“. Like gcc?

Major OS kernels would be written in C++“. I don’t know about “major”, but there’s  BeOS/Haiku and IncludeOS.

Not only has C++ failed to present enough of a value proposition to keep language designers uninterested in imagining languages like D, Go, and Rust, it has failed to displace its own ancestor.” – I think the problem with this argument is the (for me) implicit assumption that if a language is good enough, “better enough” than C, then logically programmers will switch. Unfortunately, that’s not how humans behave, as as much as some of us would like to pretend otherwise, programmers are still human.

My opinion is that C++ is strictly better than C. I’ve met and worked with many bright people who disagree. There’s nothing that C++ can do to bring them in – they just don’t value the trade-offs that C++ makes/made. Some of them might be tempted by Rust, but my anedoctal experience is that those that tend to favour C over C++ end up liking Go a lot more. I can’t stand Go myself, but the things about Go that I don’t like don’t bother its many fans.

My opinion is also that D is strictly better than C++, and I never expect the former to replace the latter. I’m even more fuzzy on that one than the reason why anybody chooses to write C in a 2017 greenfield project.

My advice to everyone is to use whatever tool you can be most productive in. Our brains are all different, we all value completely different trade-offs, so use the tool that agrees with you. Just don’t expect the rest of the world to agree with you.

 

Advertisements
Tagged , , ,

Operator overloading is a good thing (TM)

Brains are weird things. I used to be a private maths tutor, and I always found it amazing how a little change in notation could sometimes manage to completely confuse a student. Notation itself seems to me to be a major impediment for the majority of people to like or be good at maths. I had fun sometimes replacing the x in an equation with a drawing of an apple to try and get the point across that the actual name (or shape!) of a variable didn’t matter, that it was just standing in for something else.

Programmers are more often than not mathematically inclined, and yet a similar phenomenon seems to occur with the “shape” of certain functions, i.e. operators. For reasons that make us much sense to me as x confusing maths students, the fact that a function has a name that has non-alphanumeric characters in them make them particularly weird. So weird that programmers shouldn’t be allowed to defined functions with those names, only the language designers. That’s always a problem for me – languages that don’t give you the same power as the designers are Blub as far as I’m concerned. But every now and again I see a blost post touting the advantages of some language or other, listing the lack of operator overloading as a bonus.

I don’t even understand the common arguments against operator overloading. One is that somehow “a + b” is now confusing, because it’s not clear what the code does. How is that different from having to read the documentation/implementation of “a.add(b)”? If it’s C++ and “a + b” shows up, anyone who doesn’t read it as “a.operator+(b)” or “operator+(a, b)” with built-in implementations of operator+ for integers and floating point numbers needs to brush up on their C++. And then there’s the fact that that particular operator is overloaded anyway, even in C – the compiler emits different instructions for floats and integers, and its behaviour even depends on the signedness of ints.

Then there’s the complaint that one could make operator+ do something stupid like subtract. Because, you know, this is totally impossible:

int add(int i, int j) {
    return i - j;}

Some would say that operator overloading is limited in applicability since only numerical objects and matrices really need them. But used with care, it might just make sense:

auto path = "foo" / "bar" / "baz";

Or in the C++ ranges by Eric Niebler:

using namespace ranges;
int sum = accumulate(view::ints(1)
                   | view::transform([](int i){return i*i;})
                   | view::take(10), 0);

I’d say both of those previous examples are not only readable, but more readable due to use of operator overloading. As I’ve learned however, readability is in the eye of the beholder.

All in all, it confuses me when I hear/read that lacking operator overloading makes a language simpler. It’s just allowing functions to have “special” names and special syntax to call them (or in Haskell, not even that). Why would the names of functions make code so hard to read for some people? I guess you’d have to ask my old maths students.

Tagged , , , ,

On the novelty factor of compile-time duck typing

Or structural type systems for the pendantic, but I think most people know what I mean when I say “compile-time duck typing”.

For one reason or another I’ve read quite a few blog posts about how great the Go programming language is recently. A common refrain is that Go’s interfaces are amazing because you don’t have to declare that a type has to satisfy an interface; it just does if its structure matches (hence structural typing). I’m not sold on how great this actually is – more on that later.

What I don’t understand is how this is presented as novel and never done before. I present to you a language from 1990:

template <typename T>
void fun(const T& animal) {
    cout << "It says: " << animal.say() << endl;
}

struct Dog {
    std::string say() const { return "woof"; }
};

struct Cat {
    std::string say() const { return "meow"; }
};

int main() {
    fun(Dog());
    fun(Cat());
}

Most people would recognise that as being C++. If you didn’t, well… it’s C++. I stayed away from post-C++11 on purpose (i.e. Dog{} instead of Dog()). Look ma, compile-time duck typing in the 1990s! Who’d’ve thunk it?

Is it nicer in Go? In my opinion, yes. Defining an interface and saying a function only takes objects that conform to that interface is a good thing, and a lot better than the situation in C++ (even with std::enable_if and std::void_t). But it’s easy enough to do that in D (template contraints), Haskell (typeclasses), and Rust (traits), to name the languages that do something similar that I’m more familiar with.

But in D and C++, there’s currently no way to state that your type satisfies what you need it to due to an algorithm function requiring it (such as having a member function called “say” in the silly example above) and get compiler errors telling you why it didn’t satisfy it (such as  mispelling “say” as “sey”). C++, at some point in the future, will get concepts exactly to alleviate this. In D, I wrote a library to do it. Traits and typeclasses are definitely better, but in my point of view it’s good to be able to state that a type does indeed “look like” what it needs to do to be used by certain functions. At least in D you can say static assert(isAnimal!MyType); – you just don’t know why that assertion fails when it does. I guess in C++17 one could do something similar using std::void_t. Is there an equivalent for Go? I hope a gopher enlightens me.

All in all I don’t get why this gets touted as something only Go has. It’s a similar story to “you can link statically”. I can do that in other languages as well. Even ones from the 90s.

Tagged , , ,

The main function should be shunned

The main function (in languages that have it) is…. special. It’s the entry point of the program by convention, there can only be one of them in all the object files being linked, and you can’t run a program without it. And it’s inflexible.

Its presence means that the final output has to be an executable. It’s likely however, that the executable in question might have code that others might rather reuse than rewrite, but they won’t be able to use it in their own executables. There’s already a main function in there. Before clang nobody seemed to stumble on the idea that a compiler as a library would be a great idea. And yet…

This is why I’m now advocating for always putting the main function of an executable in its own file, all by itself. And also that it do the least amount of work possible for maximum flexibility. This way, any executable project is one excluded file away in the build system from being used as a library. This is how I’d start a, say, C++ executable project from scratch today:

#include "runtime.hpp"
#include <iostream>
#include <stdexcept>

int main(int argc, const char* argv[]) {
    try {
        run(argc, argv); // "real" main
        return 0;
    } catch(const std::exception& ex) {
        std::cout << "Oops: " << ex.what() << std::endl;
        return 1;
    }
}

In fact, I think I’ll go write an Emacs snippet for that right now.

Tagged ,

C is not magically fast, part 2

I wrote a blog post before about how C is not magically fast, but the sentiment that C has properties lacking in other languages that make it so is still widespread. It was with no surprise at all then that a colleague mentioned something resembling that recently at lunch break, and I attempted to tell him why it wasn’t (at least always) true.

He asked for an example where C++ would be faster, and I resorted to the old sort classic: C++ sort is faster than C’s qsort because of templates and inlining. He then asked me if I’d ever measured it myself, and since I hadn’t, I did just that after lunch. I included D as well because, well, it’s my favourite language. Taking the minimum time after ten runs each to sort a random array of 10M simple structs on my laptop yielded the results below:

  • D: 1.147s
  • C++: 1.723s
  • C: 1.789s

I expected  C++ to be faster than C, I didn’t expect the difference to be so small. I expected D to be the same speed as C++, but for some reason it’s faster. I haven’t investigated the reason why for lack of interest, but maybe because of how strings are handled?

I used the same compiler backend for all 3 so that wouldn’t be an influence: LLVM. I also seeded all of them with the same number and used the same random number generator: the awful srand from C’s standard library. It’s terrible, but it’s the only easy way to do it in standard C and the same function is available from the other two languages. I also only timed the sort, not counting init code.

The code for all 3 implementations:

// sort.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <sys/resource.h>

typedef struct {
    int i;
    char* s;
} Foo;

double get_time() {
    struct timeval t;
    struct timezone tzp;
    gettimeofday(&t, &tzp);
    return t.tv_sec + t.tv_usec*1e-6;
}

int comp(const void* lhs_, const void* rhs_) {
    const Foo *lhs = (const Foo*)lhs_;
    const Foo *rhs = (const Foo*)rhs_;
    if(lhs->i < rhs->i) return -1;
    if(lhs->i > rhs->i) return 1;
    return strcmp(lhs->s, rhs->s);
}

int main(int argc, char* argv[]) {
    if(argc < 2) {
        fprintf(stderr, "Must pass in number of elements\n");
        return 1;
    }

    srand(1337);
    const int size = atoi(argv[1]);
    Foo* foos = malloc(size * sizeof(Foo));
    for(int i = 0; i < size; ++i) {
        foos[i].i = rand() % size;
        foos[i].s = malloc(100);
        sprintf(foos[i].s, "foo%dfoo", foos[i].i);
    }

    const double start = get_time();
    qsort(foos, size, sizeof(Foo), comp);
    const double end = get_time();
    printf("Sort time: %lf\n", end - start);

    free(foos);
    return 0;
}


// sort.cpp
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <chrono>
#include <cstring>

using namespace std;
using namespace chrono;

struct Foo {
    int i;
    string s;

    bool operator<(const Foo& other) const noexcept {
        if(i < other.i) return true;
        if(i > other.i) return false;
        return s < other.s;
    }

};


template<typename CLOCK, typename START>
static double getElapsedSeconds(CLOCK clock, const START start) {
    //cast to ms first to get fractional amount of seconds
    return duration_cast<milliseconds>(clock.now() - start).count() / 1000.0;
}

#include <type_traits>
int main(int argc, char* argv[]) {
    if(argc < 2) {
        cerr << "Must pass in number of elements" << endl;
        return 1;
    }

    srand(1337);
    const int size = stoi(argv[1]);
    vector<Foo> foos(size);
    for(auto& foo: foos) {
        foo.i = rand() % size;
        foo.s = "foo"s + to_string(foo.i) + "foo"s;
    }

    high_resolution_clock clock;
    const auto start = clock.now();
    sort(foos.begin(), foos.end());
    cout << "Sort time: " << getElapsedSeconds(clock, start) << endl;
}


// sort.d
import std.stdio;
import std.exception;
import std.datetime;
import std.algorithm;
import std.conv;
import core.stdc.stdlib;


struct Foo {
    int i;
    string s;

    int opCmp(ref Foo other) const @safe pure nothrow {
        if(i < other.i) return -1;
        if(i > other.i) return 1;
        return s < other.s
            ? -1
            : (s > other.s ? 1 : 0);
    }
}

void main(string[] args) {
    enforce(args.length > 1, "Must pass in number of elements");
    srand(1337);
    immutable size = args[1].to!int;
    auto foos = new Foo[size];
    foreach(ref foo; foos) {
        foo.i = rand % size;
        foo.s = "foo" ~ foo.i.to!string ~ "foo";
    }

    auto sw = StopWatch();
    sw.start;
    sort(foos);
    sw.stop;
    writeln("Elapsed: ", cast(Duration)sw.peek);
}



Tagged , ,

The C++ GSL in Practice

At CppCon 2015, we heard about the CppCoreGuildelines and a supporting library for it, the GSL. There were several talks devoted to this, including two of the keynotes, and we were promised a future of zero cost abstractions that were also safe. What’s not to like?

Me being me, I had to try this out for myself. And what better way than when rewriting my C++ implementation of an MQTT broker from scratch. Why from scratch? The version I had didn’t perform well, required extensive refactoring to do so and I’m not crazy enough to post results from C++ that lose by a factor of 3 to any other language.

It was a good fit as well: the equivalent D and Rust code was using slices, so this seemed like the perfect change to try out gsl::span (née gsl::array_view).

I think I liked it. I say I think because the benefits it provided (slices in C++!) are something I’m used to now by programming in D, and of course there were a few things that didn’t work out so well, namely:

gsl::cstring_span

First of all, there was this bug I filed. This is a new one to shoot oneself in one’s foot and we were not amused. Had I just declared a function taking const std::string& as usual, I wouldn’t have hit the bug. The price of early adoption, I guess. The worst part is that it failed silently and was hard to detect: the strings printed out the same, but one had a silent terminating null char. I ended up having to declare an overload that took const char* and did the conversion appropriately.

Also, although I know why, it’s still incredibly annoying to have to use empty angle brackets for the default case.

Rvalues need not apply

Without using the GSL, I can do this:

void func(const std::vector<unsigned char>&);
func({2, 3, 4}); //rvalues are nice

With the GSL, it has to be this:

void func(gsl::span<const unsigned char>&);
const std::vector<unsigned char> bytes{2, 3, 4};
func(bytes);

It’s cumbersome and I can’t see how it’s protecting me from anything.

Documentation

I had to refer to the unit tests (fortunately included) and Neil MacIntosh’s presentation at CppCon 2015 multiple times to figure out how to use it. It wasn’t always obvious.

Conclusion

I still think this is a good thing for C++, but the value of something like gsl::not_null is… null without the static analysis tool they mentioned. It could be easier to use as well. My other concern is how and if gsl::span will work with the ranges proposal / library.

 

Tagged , ,

Rust impressions from a C++/D programmer, part 1

Discussion on programming reddit

Discussion on Rust reddit

C++ and D aren’t the only languages I know, I labeled myself that way in the title because as far as learning Rust is concerned, I figured they would be the most relevant in terms of the audience knowing where I’m coming from.

Since two years ago, my go-to task for learning a new programming language is to implement an MQTT broker in it. It was actually my 3rd project in D, but my first in Haskell and now that I have some time on my hands, it’s what I’m using to learn Rust. I started last week and have worked on it for about 3 days. As expected, writing an MQTT broker is a great source of insight into how a language really is. You know, the post-lovey-dovey phase. It’s like moving in together straight away instead of the first-date-like “here’s how you write a Scheme interpreter”.

I haven’t finished the project yet, I’m probably somewhere around the 75% mark, which isn’t too shabby for 3 days of work. Here are my impressions so far:

The good

The borrow checker. Not surprising since this is basically the whole point of the language. It’s interesting how much insight it gave me in how broken the code I’m writing elsewhere might be.  This will be something I can use when I write in other systems languages, like how learning Haskell makes you wary of doing IO.

Cargo. Setting up, getting started, using someone’s code and unit testing what you write as you go along is painless and just works. Tests in parallel by default? Yes, please. I wonder where I’ve seen that before…

Traits. Is there another language other than D and Rust that make it this easy to use compile-time polymorphism? If there is, please let me know which one. Rust has an advantage here: as in Dylan (or so I read), the same trait can be used for runtime polymorphism.

Warnings. On by default, and I only had to install flycheck-rust in Emacs for syntax highlighting to just work. Good stuff.

Productivity. This was surprising, given the borrow checker’s infamy. It _does_ take a while to get my code to compile, but overall I’ve been able to get a good amound done with not that much time, given these are the first lines of Rust I’ve ever written.

Algebraic types and pattern matching. Even though I didn’t use the former.

Slices. Non-allocating views into data? Yes, please. Made the D programmer in me feel right at home.

Immutable by default. Need I say more?

Debugging. rust-gdb makes printing out values easy. I couldn’t figure out how to break on certain functions though, so I had to use the source file and line number instead.

No need to close a socket due to RAII. This was nice and even caught a bug for me. The reason being that I expected my socket to close because it was dropped, but my test failed. When I looked into it, the reference count was larger than 1 because I’d forgotten to remove the client’s subscriptions. The ref count was 0, the socket was dropped and closed, and the test passed. Nice.

No parens for match, if, for, …

The bad

The syntax. How many times can one write an ampersand in one’s source code? You’ll break new records. Speaking of which…

Explicit borrows. I really dislike the fact that I have to tell the compiler that I’m the function I’m calling is borrowing a parameter when the function signature itself only takes borrows. It won’t compile otherwise (which is good), but… since I can’t get it wrong what’s the point of having to express intent? In C++:

void fun(Widget& w);
auto w = Widget();
fun(w); //NOT fun(&w) as in Rust

In Rust:

fn fun(w: &mut Widget);
let w = Widget::new();
fun(&mut w); //fun(w) doesn't compile but I still need to spell out &mut. Sigh.

Display vs Debug. Printing out integers and strings with {} is fine, but try and do that with a Vec or HashMap and you have to use the weird {:?}. I kept getting the order of the two symbols wrong as well. It’s silly. Even the documentation for HashMap loops over each entry and prints them out individually. Ugh.

Having to rethink my code. More than once I had to find a different way to do the thing I wanted to do. 100% of the time it was because of the borrow checker. Maybe I couldn’t figure out the magical incantation that would get my code to compile, but in one case I went from “return a reference to an internal object, then call methods on it” to “find object and call method here right now”. Why? So I wouldn’t have to borrow it mutably twice. Because the compiler won’t let me. My code isn’t any safer and it was just annoying.

Rc<RefCell<T>> and Arc<Mutex<T>>. Besides the obvious “‘Nuff said”, why do I have to explicitly call .clone on Rc? It’s harder to use than std::shared_ptr.

Slices. Writing functions that slices and passing them vectors works well enough. I got tired of writing &var[..] though. Maybe I’m doing something wrong. Coming from D I wanted to avoid vectors and just slice arrays instead. Maybe that’s not Rusty. What about appending together some values to pass into a test? No Add impl for Vecs, so it’s massive pain. Sigh.

Statements vs Expressions. I haven’t yet made the mistake of forgetting/adding a semicolon, but I can see it happening.

No function overloading.

Serialization. There’s no way to do it well without reflection, and Rust is lacking here. I just did everything by hand, which was incredibly annoying. I’m spoiled though, in D I wrote what I think is a really good serialization library. Good in the lazy sense, I pretty much never have to write custom serialization code.

The ugly

Hashmaps. The language has operator overloading, but HashMap doesn’t use it. So it’s a very Java-like map.insert(key, value). If you want to create a HashMap with a literal… you can’t. There’s no equivalent macro to vec. You could write your own, but come on, this is a basic type from the standard library that will get used a lot. Even C++ does better!

Networking / concurrent IO. So I took a look at what my options were, and as far as my googling took me, it was to use native threads or a library called mio. mio’s API was… not the easiest to use so I punted and did what is the Rust standard library way of writing a server and used threads instead. I was sure I’d have performance problems down the road but it was something to worry about later. I went on writing my code, TDDed an implementation of a broker that wasn’t connected to the outside world and everything. At one point I realised that holding on to a mutable reference for subscribers wasn’t going to work so I used Rc<RefCell<Subscriber>> instead. It compiled, my tests passed, and all was good in the world. Then I tried actually using the broker from my threaded server. Since it’s not safe to use Rc<RefCell<>> in threads, this failed to compile. “Good!”, I thought, I changed Rc to Arc and RefCell to Mutex. Compile, run, …. deadlock. Oops. I had to learn mio after all. It wasn’t as bad as boost::asio but it wasn’t too far away either.

Comparing objects for identity. I just wanted to compare pointers. It was not fun. I had to write this:

fn is_same<T>(lhs: &T, rhs: &T) -> bool {
    lhs as *const T == rhs as *const T;
}
fn is_same_subscriber<T: Subscriber>(lhs: Rc<RefCell<T>>, rhs: Rc<RefCell<T>>) -> bool {
    is_same(&*lhs.borrow, &*rhs.borrow());
}

Yuck.

Summary

I thought I’d like Rust more than I actually do at this point. I’m glad I’m taking the time to learn it, but I’m not sure how likely I’ll choose to use it for any future project. Currently the only real advantage it has for me over D is that it has no runtime and could more easily be used on bare metal projects. But I’m unlikely to do any of those anytime soon.

I never thought I’d say this a few years back but…I like being able to fall back on a mark-and-sweep GC. I don’t have to use it in D either, so if it ever becomes a performance or latency problem I know how to deal with it. It seems to me to be far easier than getting the borrow checker to agree with me or having to change how I want to write my code.

We’ll see, I guess. Optimising the Rust implementation to be competitive with the D and Java ones is likely to be interesting.

Tagged , , , ,

Haskell actually does change the way you think

Last year I started trying to learn Haskell. There have been many ups and downs, but my only Haskell project so far is on hold while I work on other things. I’m not sure yet if I’d choose to use Haskell in production. The problems I had (and the time it’s taken so far) writing a simple server make me think twice, but that’s a story for another blog post.

The thing is, the whole reason I decided to learn Haskell were the many reports that it made me you think differently. As much as I like D, learning it was easy and essentially I’m using it as a better C++. There are things I routinely do in D that I wouldn’t have thought of or bother in C++ because they’re easier. But it’s not really changed my brain.

I didn’t think Haskell had either, until I started thinking of solutions to problems I was having in D in Haskell ways. I’m currently working on a build system, and since the configuration language is D, it has to be compiled. So I have interesting problems to solve with regards to what runs when: compile-time or run-time. Next thing I know I’m thinking of lazy evaluation, thunks, and the IO monad. Some things aren’t possible to be evaluated at compile-time in D. So I replaced a value with a function that when run (i.e. at run-time) would produce that value. And (modulo current CTFE limitations)… it works! I’m even thinking of making a wrapper type that composes nicely… (sound familiar?)

So, thanks Haskell. You made my head hurt more than anything I’ve tried learning since Physics, but apparently you’ve made me a better programmer.

Tagged , , , , , ,

The craziest code I ever wrote

A few years ago at work my buddy Jeff was as usual trying to do something in Go. I can’t remember why, but he wanted to arrange text strings in memory so that they were all contiguous. I said something about C++ and he remarked that the only thing C++11 could do that Go couldn’t would be perhaps to do this work at compile-time. I hadn’t learned D yet (which would have made the task trivial), so I spent the rest of the day writing the monstrosity below for “teh lulz”. It ended up causing my first ever question on Stackoverflow. “Enjoy” the code:

//Arrange strings contiguously in memory at compile-time from string literals.
//All free functions prefixed with "my" to faciliate grepping the symbol tree
//(none of them should show up).

#include <iostream>

using std::size_t;

//wrapper for const char* to "allocate" space for it at compile-time
template<size_t N>
struct String {
    //C arrays can only be initialised with a comma-delimited list
    //of values in curly braces. Good thing the compiler expands
    //parameter packs into comma-delimited lists. Now we just have
    //to get a parameter pack of char into the constructor.
    template<typename... Args>
    constexpr String(Args... args):_str{ args... } { }
    const char _str[N];
};

//takes variadic number of chars, creates String object from it.
//i.e. myMakeStringFromChars('f', 'o', 'o', '') -> String<4>::_str = "foo"
template<typename... Args>
constexpr auto myMakeStringFromChars(Args... args) -> String<sizeof...(Args)> {
    return String<sizeof...(args)>(args...);
}

//This struct is here just because the iteration is going up instead of
//down. The solution was to mix traditional template metaprogramming
//with constexpr to be able to terminate the recursion since the template
//parameter N is needed in order to return the right-sized String<N>.
//This class exists only to dispatch on the recursion being finished or not.
//The default below continues recursion.
template<bool TERMINATE>
struct RecurseOrStop {
    template<size_t N, size_t I, typename... Args>
    static constexpr String<N> recurseOrStop(const char* str, Args... args);
};

//Specialisation to terminate recursion when all characters have been
//stripped from the string and converted to a variadic template parameter pack.
template<>
struct RecurseOrStop<true> {
    template<size_t N, size_t I, typename... Args>
    static constexpr String<N> recurseOrStop(const char* str, Args... args);
};

//Actual function to recurse over the string and turn it into a variadic
//parameter list of characters.
//Named differently to avoid infinite recursion.
template<size_t N, size_t I = 0, typename... Args>
constexpr String<N> myRecurseOrStop(const char* str, Args... args) {
    //template needed after :: since the compiler needs to distinguish
    //between recurseOrStop being a function template with 2 paramaters
    //or an enum being compared to N (recurseOrStop < N)
    return RecurseOrStop<I == N>::template recurseOrStop<N, I>(str, args...);
}

//implementation of the declaration above
//add a character to the end of the parameter pack and recurse to next character.
template<bool TERMINATE>
template<size_t N, size_t I, typename... Args>
constexpr String<N> RecurseOrStop<TERMINATE>::recurseOrStop(const char* str,
                                                            Args... args) {
    return myRecurseOrStop<N, I + 1>(str, args..., str[I]);
}

//implementation of the declaration above
//terminate recursion and construct string from full list of characters.
template<size_t N, size_t I, typename... Args>
constexpr String<N> RecurseOrStop<true>::recurseOrStop(const char* str,
                                                       Args... args) {
    return myMakeStringFromChars(args...);
}

//takes a compile-time static string literal and returns String<N> from it
//this happens by transforming the string literal into a variadic paramater
//pack of char.
//i.e. myMakeString("foo") -> calls myMakeStringFromChars('f', 'o', 'o', '');
template<size_t N>
constexpr String<N> myMakeString(const char (&str)[N]) {
    return myRecurseOrStop<N>(str);
}

//Simple tuple implementation. The only reason std::tuple isn't being used
//is because its only constexpr constructor is the default constructor.
//We need a constexpr constructor to be able to do compile-time shenanigans,
//and it's easier to roll our own tuple than to edit the standard library code.

//use MyTupleLeaf to construct MyTuple and make sure the order in memory
//is the same as the order of the variadic parameter pack passed to MyTuple.
template<typename T>
struct MyTupleLeaf {
    constexpr MyTupleLeaf(T value):_value(value) { }
    T _value;
};

//Use MyTupleLeaf implementation to define MyTuple.
//Won't work if used with 2 String<> objects of the same size but this
//is just a toy implementation anyway. Multiple inheritance guarantees
//data in the same order in memory as the variadic parameters.
template<typename... Args>
struct MyTuple: public MyTupleLeaf<Args>... {
    constexpr MyTuple(Args... args):MyTupleLeaf<Args>(args)... { }
};

//Helper function akin to std::make_tuple. Needed since functions can deduce
//types from parameter values, but classes can't.
template<typename... Args>
constexpr MyTuple<Args...> myMakeTuple(Args... args) {
    return MyTuple<Args...>(args...);
}

//Takes a variadic list of string literals and returns a tuple of String<> objects.
//These will be contiguous in memory. Trailing '' adds 1 to the size of each string.
//i.e. ("foo", "foobar") -> (const char (&arg1)[4], const char (&arg2)[7]) params ->
//                       ->  MyTuple<String<4>, String<7>> return value
template<size_t... Sizes>
constexpr auto myMakeStrings(const char (&...args)[Sizes]) -> MyTuple<String<Sizes>...> {
    //expands into myMakeTuple(myMakeString(arg1), myMakeString(arg2), ...)
    return myMakeTuple(myMakeString(args)...);
}

//Prints tuple of strings
template<typename T> //just to avoid typing the tuple type of the strings param
void printStrings(const T& strings) {
    //No std::get or any other helpers for MyTuple, so intead just cast it to
    //const char* to explore its layout in memory. We could add iterators to
    //myTuple and do "for(auto data: strings)" for ease of use, but the whole
    //point of this exercise is the memory layout and nothing makes that clearer
    //than the ugly cast below.
    const char* const chars = reinterpret_cast<const char*>(&strings);
    std::cout << "Printing strings of total size " << sizeof(strings);
    std::cout << " bytes:\n";
    std::cout << "-------------------------------\n";

    for(size_t i = 0; i < sizeof(strings); ++i) {
        chars[i] == '' ? std::cout << "\n" : std::cout << chars[i];
    }

    std::cout << "-------------------------------\n";
    std::cout << "\n\n";
}

int main() {
    {
        constexpr auto strings = myMakeStrings("foo", "foobar",
                                               "strings at compile time");
        printStrings(strings);
    }

    {
        constexpr auto strings = myMakeStrings("Some more strings",
                                               "just to show Jeff to not try",
                                               "to challenge C++11 again :P",
                                               "with more",
                                               "to show this is variadic");
        printStrings(strings);
    }

    std::cout << "Running 'objdump -t |grep my' should show that none of the\n";
    std::cout << "functions defined in this file (except printStrings()) are in\n";
    std::cout << "the executable. All computations are done by the compiler at\n";
    std::cout << "compile-time. printStrings() executes at run-time.\n";
}
Tagged , , , , , , ,

Haskell monads for C++ programmers

I’m not going to get into the monad tutorial fallacy. Also, I think this blog about another monad fallacy sums it up nicely: the problem isn’t understanding what monads are, but rather understanding how they can be used. Understanding the monad laws isn’t hard. Understanding how to use the Maybe monad isn’t hard either. But things get tricky pretty fast and there’ s a kind of monads that are similar to each other that took me a while to understand how to use. That is, until I recognised what they actually were: C++ template metaprogramming. I guess it’s the opposite realisation that Bartoz Milewski had.

The analogy is only valid for a few monads. The ones I’ve seen that this applies to are IO, State, and Get from Data.Binary. These are the monads that are referred to as computations, which sounds really abstract, but really functions that return these monads return mini-programs. These mini-programs don’t immediately do anything, they need to be executed first. In IO’s case that’s done by the runtime system, for State the runState does that for you (I’m stretching here – only IO really does anything, even runState is pure).

It’s similar to template metaprogramming in C++: at compile-time the programmer has access to a functional language with no side-effects that returns a function that at runtime (i.e. when executed) actually does something. After that realisation I got a lot better at understanding how and why to use them.

The monad issue doesn’t end there, unfortunately. There are many other monads that aren’t like C++ templates at all. But the ones that are – well, at least you’ll be able to recognise them now.

Tagged , , ,