Advent of D

I wrote my Advent of Code in D. The programming language. It was the first time I used D in earnest every day for something substantial. It was fun and I learned things along the way, such as easy metaprogramming, concurrency I could write correctly, and functional programming that doesn’t feel like I have one arm tied behind my back. I would do it all over again.

My main programming languages are C++ and Python. For me, D is the combination of the best of these two: the power of C++ with the ease of use of Python. Or to put it another way, D is the C++ I always wanted. This used to be D’s sales pitch, down to its name. There’s lots of evident C++ heritage in D. It is a C++ successor worthy of consideration.

Why D?

This is the question people always ask me. Whenever I bring up D, I am faced with the following set of standard rebuttals:

  • Why not Rust?
  • D? That’s still around?
  • D doesn’t bring anything new or interesting
  • But the GC…

I’ll answer these briefly: D was easier for me to learn than Rust, yes, it’s still around and very lively, it has lots of interesting ideas, and what garbage collector? I guess there’s a GC, but I’ve never noticed and it’s never gotten in my way.

I will let D speak for itself further below. For now, I would like to address the “why D?” rebuttals in a different way. It seems to me that people would rather not have to learn another new thing. Right now, Rust has a lot of attention and some of the code, and right now it seems like Rust may be the solution we always wanted for safe, systems-level coding. It takes effort to work on a new programming language. So, I think the “why D?” people are mostly saying, “why should I have to care about a different programming language, can’t I just immediately dismiss D and spend time learning Rust instead?”

I posit that no, you shouldn’t immediately dismiss D. If nothing else, try to listen to its ideas, many of which are distilled into Alexandrescu’s The D Programming Language. I recommend this book as good reading material for computer science, even if you never plan to write any D (as a language reference itself, it’s already dated in a number of ways, but I still recommend it for the ideas it discusses). Also browse the D Gems section in the D tour. In the meantime, let me show you what I learned about D while using it.

Writing D every day for over 25 days

I took slightly longer than 25 days to write my advent of code solutions, partly because some stumped me a little and partly because around actual Christmas I wanted to spend time with family instead of writing code. When I was writing code, I would say that nearly every day of advent of code forced me to look into a new aspect of D. You can see my solutions in this Mercurial repository.

I am not going to go too much into details about the abstract theory concerning the solution of each problem. Perhaps another time. I will instead focus on the specific D techniques I learned about or found most useful for each.

Contents

  1. Day 1: parsing arguments, type conversions, template constraints
  2. Day 2: functional programming and uniform function call syntax
  3. Day 3: let’s try some complex arithmetic!
  4. Day 4: reusing familiar tools to find duplicates
  5. Day 5: more practice with familiar tools
  6. Day 6: ranges
  7. Day 7: structs and compile-time regexes
  8. Day 8: more compile-time fun with mixin
  9. Day 9: a switch statement!
  10. Day 10: learning what ranges cannot do
  11. Day 11: offline hex coding
  12. Day 12: for want of a set
  13. Day 13: more offline coding
  14. Day 14: reusing older code as a module
  15. Day 15: generators, lambdas, functions, and delegates
  16. Day 16: permutations with primitive tools
  17. Day 17: avoiding all the work with a clever observation
  18. Day 18: concurrency I can finally understand and write correctly
  19. Day 19: string parsing with enums and final switches
  20. Day 20: a physics problem with vector operations
  21. Day 21: an indexable, hashable, comparable struct
  22. Day 22: more enums, final switches, and complex numbers
  23. Day 23: another opcode parsing problem
  24. Day 24: a routine graph-search problem
  25. Day 25: formatted reads to finish off Advent of D

Day 1: parsing arguments, type conversions, template constraints

(problem statement / my solution)

For Day 1, I was planning to be a bit more careful about everything around the code. I was going to carefully parse CLI arguments, produce docstrings and error messages when anything went wrong, and carefully validate template arguments with constraints (comparable to concepts in C++). While I could have done all of this, as days went by I tried to golf my solutions, so I abandoned most of this boilerplate. Instead, I lazily relied on getting D stack traces at runtime or compiler errors when I messed up.

As you can see from my solution, had I kept it up, the boilerplate isn’t too bad, though. Template constraints are achieved by adding if(isNumeric!numType), which checks at compile time that my template was given a template argument of the correct type, where isNumeric comes from import std.traits. I also found that getopt was a sufficiently mature standard library for handling command-line parsing. It’s not quite as rich as Python’s argparse, merely sufficient. This about shows all it can do:

  string input;
  auto opts = getopt(
    args,
    "input|i", "Input captcha to process", &input
  );

  if (opts.helpWanted) {
    defaultGetoptPrinter("Day 1 of AoC", opts.options);
  }

Finally, a frequent workhorse that appeared from Day 1 was std.conv for parsing strings into numbers. A single function, to is surprisingly versatile and does much more than that, by taking a single template argument for converting (not casting) one type into another. It knows not only how to parse strings into numbers and vice versa, but also how to convert numerical types keeping as much precision as possible or reading list or associative array literals from strings if they are in their standard string representation. It’s a good basic example of D’s power and flexibility in generic programming.

Day 2: functional programming and uniform function call syntax

(problem statement / my solution)

For whatever reason, probably because I was kind of trying to golf my solutions, I ended up writing a lot of functionalish code, with lots of map, reduce, filter, and so forth. This started early on with Day 2. D is mostly unopinionated about which style of programming one should use and offers tools to do object-orientation, functional programming, or just plain procedural programming, presenting no obstacle to the mixing these styles. Lambdas are easily written inline with concise syntax, e.g. x => x*x, and the basic standard functional tools like map, reduce, filter and so on are available.

D’s approach to functional programming is quite pragmatic. While I rarely used it, because I wasn’t being too careful for these solutions, D functions can be labelled pure, which means that they can have no side effects. However, this still lets them do local impure things such as reassigning a variable or having a for loop. The only restriction is that all of their impurity must be “on the stack”, and that they cannot call any impure functions themselves.

Another feature that I came to completely fall in love with was what they call uniform function call syntax (UFCS). With some caveats, this basically means that

 foo.bar(baz)

is just sugar for

 bar(foo, baz)

If the function only has one argument, the round brackets are optional and foo.bar is sugar for bar(foo). This very basic syntactic convenience makes it so easy and pleasant to chain function calls together, lending itself to making it more inviting to write functional code. It also is a happy unification between OOP and FP, because syntactically it’s the same to give an object a new member function as it is to create a free-standing function whose first argument is the object.

Day 3: let’s try some complex arithmetic!

(problem statement / my solution)

For me, 2-dimensional geometry is often very well described by complex numbers. The spiral in the problem here seemed easy to describe as an associative array from complex coordinates to integer values. So, I decided to give D’s std.complex a try. It was easy to use and there were no big surprises here.

Day 4: reusing familiar tools to find duplicates

(problem statement / my solution)

There weren’t any new D techniques here, but it was nice to see how easy it was to build a simple word counter from D builtins. Slightly disappointed that this data structure itself wasn’t builtin like Python’s own collections.Counter but hardly an insurmountable problem.

Day 5: more practice with familiar tools

(problem statement / my solution)

Again, not much new D here. I like the relative ease with which it’s possible to read integers into a list using map and std.conv.to.

Day 6: ranges

(problem statement / my solution)

There’s usually a fundamental paradigm or structure in programming languages out of which everything else depends on. Haskell has functions and monads, C has pointers and arrays, C++ has classes and templates, Python has dicts and iterators, Javascript has callbacks and objects, Rust has borrowing and immutability. Ranges are one of D’s fundamental concepts. Roughly speaking, a range is anything that can be iterated over, like an array or a lazy generator. Thanks to D’s powerful metaprogramming, ranges can be defined to satisfy a kind of compile-time duck typing: if it has methods to check for emptiness, get the first element, and get the next element, then it’s an InputRange. This duck typing is kind of reminiscent of type classes in Haskell. D’s general principle of having containers and algorithms on those containers is built upon the range concept. Ranges are intended to be simpler reformulation of iterators from the C++ standard libary.

I have been using ranges all along, as foreach loops are kind of like sugar for invoking those methods on ranges. However, for day 6 I actually wanted to use a method that had to invoke an std.range method, enumerate. It simply iterates over a range while simultaneously producing a counter. This I used to write some brief code to obtain both the maximum of an array and the index in which it occurs.

Another range-related feature that appears for the first time here is slicing. Certain random-access ranges which allow integer indexing also allow slicing. The typical method to remove elements from an array is to use this slicing. For example, to remove the first five elements and the last two elements from an array:

 arr = arr[5..$-2];

Here the dollar sign is sugar for arr.length and this removal is simply done by moving some start and end pointers in memory — no other bytes are touched.

The D Tour has a good taste of ranges and Programming in D goes into more depth.

Day 7: structs and compile-time regexes

(problem statement / my solution)

My solution for this problem was more complicated, and it forced me to break out an actual tree data structure. Because I wasn’t trying to be particularly parsimonious about memory usage or execution speed, I decided to create the tree by having a node struct with a global associative array indexing all of the nodes.

In D, structs have value semantics and classes have reference semantics. Roughly, this means that structs are on the stack, they get copied around when being passed into functions, while classes are always handled by reference instead and dynamically allocated and destroyed. Another difference between structs and classes is that classes have inheritance (and hence, polymorphic dispatch) but structs don’t. However, you can give structs methods, and they will have an implicit this parameter, although this is little more than sugar for free-standing functions.

Enough on OOP. Let’s talk about the really exciting stuff: compile-time regular expressions!

For this problem, there was some input parsing to do. Let’s look at what I wrote:

void parseLine(string line) {
 static nodeRegex = regex(r"(?P<name>\w+) \((?P<weight>\d+)\)( -> (?P<children>[\w,]+))?");  
 auto row = matchFirst(line, nodeRegex);
 // init the node struct here
}

The static keyword instructs D that this variable has to be computed at compile-time. D’s compiler basically has its own interpreter that can execute arbitrary code as long as all of the inputs are available at compile time. In this case, this parses and compiles this regex into the binary. The next line, where I call matchFirst on each line, is done at runtime, but if for whatever reason I had these strings available at compile time (say, defined as a big inline string a few lines above the same source file), I could also do the regex parsing at compile time if I wanted to.

This is really nice. This is one of my favourite D features. Add a static and you can precompute into your binary just about anything. You often don’t even need any extra syntax. If the compiler realises that it has all of the information at compile time to do something, it might just do it. This is known as compile-time function execution, hereafter, CTFE. The D Tour has a good overview of the topic.

Day 8: more compile-time fun with mixin

(problem statement / my solution)

Day 8 was another problem where the most interesting part was parsing. As before, I used a compile-time regex. But the interesting part of this problem was the following bit of code for parsing strings into their corresponding D comparison operation, as I originally wrote it:

auto comparisons = [
  "<": function(int a, int b) => a  < b,
  ">": function(int a, int b) => a > b,
  "==": function(int a, int  b) => a == b,
  "<=": function(int a, int b) => a <= b,
  ">=": function(int a, int b) => a >= b,
  "!=": function(int a, int b) => a  != b,
];

Okay, this isn’t terrible. It’s just… not very pretty. I don’t like that it’s basically the same line repeated six times. I furthermore also don’t like that within each line, I have to repeat the operator in the string part and in the function body. Enter the mixin keyword! Basically, string mixins allow you to evaluate any string at compile time. They’re kind of like the C preprocessor, but much safer. For example, string mixins only evaluate complete expressions, so no shenanigans like #define private public are allowed. My first attempt to shorten the above looked like this:

bool function(int,int)[string] comparisons;
static foreach(cmp; ["<", ">", "==", "<=", ">=", "!="]) {
  comparisons[cmp] = mixin("function(int a, int b) => a "~cmp~" b");
}

Since I decided to use a compile-time static loop to populate my array, I now needed a separate declaration of the variable which forced me to spell out its ungainly type: an associative array that takes a string and returns a function with that signature. The mixin here takes a concatenated string that evaluates to a function.

However, this didn’t work for two reasons!

The first one is that static foreach was introduced on September 2017. The D compilers packaged in Debian didn’t have it yet when I wrote that code! The second problem is more subtle: initialisation of associative arrays currently cannot be statically done because their internal data structures rely on runtime computations, according to my understanding of this discussion. They might fix it some day?

So, next best thing is my final answer:

bool function(int,int)[string] comparisons;

auto getComparisons(Args...)() {
  foreach(cmp; Args) {
    comparisons[cmp] = mixin("function(int a, int b) => a "~cmp~" b");
  }
  return comparisons;
}

shared static this() {
  comparisons = getComparisons!("<", ">", "==",  "<=", ">=", "!=");
}

Alright, by size this is hardly shorter than the repetitive original. But I still think it’s better! It has no dull repetition where bugs are most often introduced, and it’s using a variable-argument templated function so that the mixin can have its values available at compile time. It uses the next best thing to compile-time initialisation, which is a module initialiser shared static this() that just calls the function to perform the init.

Day 9: a switch statement!

(problem statement / my solution)

Day 9 was a simpler parsing problem, so simple that instead of using a regex I decided to just use a switch statement. There isn’t anything terribly fancy about switch statements, and they work almost exactly the same as they do in other languages. The only distinct features of switch statements in D is that they work on numeric, string, or bool types and that they have deprecated implicit fallthrough. Fallthrough instead must be explicitly done with goto case; or will be once the deprecation is complete.

Oh, and you can also specify ranges for a case statement, e.g.

  case 'a': .. case 'z':
    // do stuff with lowercase ASCII
    break;

It’s the small conveniences that make this pleasant. Programming in D has a good discussion on switch statements.

Day 10: learning what ranges cannot do

(problem statement / my solution)

So, superficially, you might think that expressions like arr[2..$-2], which is valid, would also allow for things like arr[$-2..1] to traverse the array in reverse order or some other syntax for having a different step size than +1. At least I did. These kinds of array indexing are common in numeric-based arrays such as Octave, Julia, R, or Python’s numpy. So for day 10’s hash, which requires reversing an array, I thought I could just do that.

Turns out that the language doesn’t have syntax to allow this, but after a quick trip to the standard library I found the necessary functions. What I thought could be written as

arr[a..b] = arr[b..a];

instead became

reverse(arr[a..b]);

Other than this minor discovery about ranges, Day 10 was more about getting the algorithm right than using any specialised D utilities. Since real hashes typically allow several sizes, I templated the hash functions with the total size, rounds of hashing, and chunk size, with a template constraint that the chunk size must divide the total size:

auto getHash(int Size=256, int Rounds=64, int ChunkSize=16)(string input)
 if( Size % ChunkSize == 0)
{
  // ...
}

Nothing new here. I just like that template constraints are so easy to write.

Day 11: offline hex coding

(problem statement / my solution)

I did most of Day 11 on paper. It took me a while to figure out a proper hex coordinate system and what the distance function in that coordinate system should be. I had seen hex coordinates from playing Battle for Wesnoth, but took me a while to figure them out again. Once I had that, the actual D code is pretty simple and used no techniques I hadn’t seen before. I think this is the first time I used the cumulativeFold function, but other than that, nothing to see here. An immutable global associative array populated at module init time like before,

pure static this(){
  directions = [
    "ne": [1,1],
    "n": [0,1],
    "nw": [-1,0],
    "sw": [-1,-1],
    "s": [0,-1],
    "se": [1,0],
  ];
}

and that’s it.

Day 12: for want of a set

(problem statement / my solution)

The only new D technique for this problem was that I decided to use a set structure to keep track of which graph nodes had been visited. The only problem is that D doesn’t have a built-in set structure (yet?), but it does have a setDifference function. It’s a bit clunky. It only works on ordered arrays, but that was sufficient for my purpose here, and probably not much worse than hashing with a traditional set structure would have been.

One further observation: D has an in keyword, which can be used to test membership, like in Python (it also has an unrelated use for defining input and output arguments to functions), but unlike Python, only for associative arrays. This makes sense, because the complexity of testing for membership for other data structures can vary widely depending on the structure and the chosen algorithm, and there isn’t a clear universal choice like there is for associative arrays.

If desired, however, it’s possible to define the in operator for any other class, like so:

bool opBinaryRight!("in")(T elt) {
  // check that elt is in `this`
}

I would assume that’s what you could use to write a set class for D.

Day 13: more offline coding

(problem statement / my solution)

This one is another where I did most of the solution on paper and thus managed to write a very short program. No new D techniques here, just the usual functionalish style that I seem to be developing.

Day 14: reusing older code as a module

(problem statement / my solution)

The problem here is interesting because I’ve solved this labelling of connected components problem before in C++ for GNU Octave. I wrote the initial bwlabeln implementation using union-find. I was tempted to do the same here, but I couldn’t think of a quick way to do so, and talking to others in the #lobsters channel in IRC, I realised that a simpler recursive solution would work without overflowing the stack (because the problem is small enough, not because a stack-based algorithm is clever).

The interesting part is reusing an earlier solution, the hashing algorithm from Day 10. At first blush, this is quite simple: every D file also creates its own module, namespaced if desired by directories. It’s very reminiscent of Python’s import statement and module namespacing. The only snag is that my other file has a void main(string[] args) function and so does this one. The linker won’t like that duplicate definition of symbols. For this purpose, D offers conditional compilation, which in C and C++ is usually achieved via a familiar C preprocessor macro idiom.

In D, this idiom is codified into the language proper via the version kewyord, like so

version(standalone) {
  void main(string[] args){
    // do main things here
  }
}

This instructs the compiler to compile the inside of the version block only if an option called “standalone” is passed in,

gdc -O2 -fversion=standalone app.d -o day10

or, with regrettably slightly different flags,

ldc2 -O2 -d-version=standalone app.d -of day10

There are other built-in arguments for version, such as “linux” or “OSX” to conditionally compile for a particular operating system. This keyword offers quite a bit of flexibility for conditional compilation, and it’s a big improvement over C preprocessor idioms.

Day 15: generators, lambdas, functions, and delegates

(problem statement / my solution)

This problem was an opportunity to test out a new function, generate, which takes a function and iterates it repeatedly on a range. Haskell calls this one iterate, which I think is a better name. It’s also a lazy generator, so you need something like take to say how much of the generator do you want to use. For example, the Haskell code

pows = take 11 $ iterate (\x -> x*2) 1

can be translated into D as

auto x = 1;
auto pows = generate!(x => x*2).take(11);

There are other examples in the documentation.

Let also take a moment here to talk about the different anonymous functions in D. The following both declare a function that squares its input:

function(int a) { return a^^2;}
delegate(int a) { return a^^2;}

The difference is just a question of closure. The delegate version carries a hidden pointer to its enclosing scope, so it can dynamically close over the outer scope variables. If you can’t afford to pay this runtime penalty, the function version doesn’t reference the enclosing scope (no extra pointer). So, for a generator, you typically want to use a delegate, since you want the generator to remember its scoped variables across successive calls, like what I did:

auto generator(ulong val, ulong mult) {
  return generate!(delegate(){
      val = (val * mult) % 2147483647;
      return val;
    }
  );
}

This function returns a generator range where each entry will result in a new entry of this pseudorandom linear congruence generator.

The delegate/function is part of the type, and can be omitted if it can be inferred by context (e.g. when passing a function into another function as an argument). Furthermore, there’s a lambda shorthand that I have been using all along, where the {return foo;} boilerplate can be shortened to just => like so:

  (a) => a^^2

This form is only valid where there’s enough context to infer if it’s a delegate or a function, as well as the type of a itself. More details in the language spec.

Day 16: permutations with primitive tools

(problem statement / my solution)

This permutations problem made me reach for the std.algorithm function bringToFront for cyclicly permuting an array in place like so,

   bringToFront(progs[rot..$], progs[0..rot]);

It’s a surprisingly versatile function that can be used to perform more tricks than cyclic permutations. Its documentation is worth a read.

I also ran into a D bug here. I had to create a character array from an immutable input string, but due to Unicode-related reasons that D has for handling characters especially, I had to cast to ubyte[] instead of char[].

Besides that, for the second part where you had to realise that permutations cannot have too big of an orbit, I also ended up using a string array with the canFind from std.algorithm. I would have preferred a string set with hashing instead of linear searching, but it didn’t make a huge difference for the size of this problem.

I really want sets in the D standard library. Maybe I should see what I can do to make them happen.

Day 17: avoiding all the work with a clever observation

(problem statement / my solution)

This puzzle is a variation of the Josephus problem. I needed some help from #lobsters in IRC to figure out how to solve it. There aren’t any new D techniques, just some dumb array concatenation with the tilde operator for inserting elements into an array:

circ = circ[0..pos] ~ y ~ circ[pos..$];

The second part can be solved via the simple observation that you only
need to track one position, the one immediately following zero.

Day 18: concurrency I can finally understand and write correctly

(problem statement / my solution)

This day was an exciting one for me. Discussing this problem with others, it seems many people had much difficulty solving this problem in other programming languages. Most people seemed to have to emulate their own concurrency with no help from their programming language of choice. In contrast, D absolutely shined here, because it is based on the actor concurrency model (message passing), which precisely fits the problem statement. (There are other concurrency primitives in case the actor concurrency model isn’t sufficient, but it was sufficient for me.)

The basic idea of concurrency in D is that each thread of execution localises all of its state. By default, threads share no data. In order to communicate with each other, threads pass messages. A thread can indicate at any time when it’s ready to send or receive messages. Messages can be any type, and each thread says what type it’s expecting to receive. If a thread receives a type it’s not prepared to handle, it will throw an exception.

There are more details, such as what happens if a thread receives too many messages but doesn’t respond to any of them. Let’s not go into that now. Basic idea: threads get spawned, threads send and receive messages.

Let’s spend a little bit of time looking at the relevant functions and types I used, all defined in std.concurrency

spawn
Starts a thread of execution. The first argument is a reference to the function that this thread will execute, along with any arguments that function may take. Returns a Tid type, a thread ID. This is used as the address to send messages to. A thread can refer to its parent thread via the special variable ownerTid.

Unless explicitly declared shared, the arguments of a threaded function must be immutable. This is how the compiler guarantees no race conditions when manipulating those variables. Of course, with shared variables, the programmer is signalling that they are taking over synchronisation of that data, which may require using low-level mutexes.

send
Send a message to a particular thread. The first argument is the thread id. The other arguments can be anything. It’s up to the receiving thread to handle the arguments it receives.
receiveOnly
Indicate that this thread is ready to receive a single type, and returns the value of that type. The type must of course be specified as a compile-time argument.
receive
Indicates what to do with any of several possible types. The arguments to this function are a collection of functions, whose parameters types will be dynamically type-matched with received types. I didn’t need this function, but I wanted to mention it exists.
receiveTimeout
The problem statement is designed to deadlock. Although there probably is a more elegant solution, timing out on deadlock was the solution I wrote. This function does just that: listens for a message for a set of amount of time. If a message is received in the designated time, its handler function is executed and receiveTimeout returns true. If the timeout happens, it returns false instead.

Armed with these tools, the solution was a breeze to write. I first spawn two threads and save their thread ids,

  auto tid1 = spawn(&runProgram, opcodes, 0);
  auto tid2 = spawn(&runProgram, opcodes, 1);

Each of the two threads defined by runProgram then immediately stops, waiting for a thread id, to know whom to talk to,

void runProgram(immutable string[] opcodes, ulong pid) {
  auto otherProg = receiveOnly!Tid();
 // ...
}

The parent thread then connects the two worker threads to each other,

  send(tid1, tid2);
  send(tid2, tid1);

And off they go, the two threads run through the opcodes in the problem statement, and eventually they deadlock, which I decided to handle with a timeout like so,

    case "rcv":
      if (!receiveTimeout(100.msecs, (long val) {regs[reg] = val;})) {
        goto done;
      }
      // no timeout, handle next opcode
      goto default;

After the thread has timed out, it signals to the parent thread that it’s done,

  done:
  send(ownerTid, thisTid, sent);

The parent in turn receives two tuples with thread id and computed value from each thread, and based on that decides what to output, after figuring out which thread is which,

  // Wait for both children to let us know they're done.
  auto done1 = receiveOnly!(Tid, long);
  auto done2 = receiveOnly!(Tid, long);
  if (done1[0] == tid2) {
    writeln(done1[1]);
  }
  else {
    writeln(done2[1]);
  }

And voilà, concurrency easy-peasy.

Day 19: string parsing with enums and final switches

(problem statement / my solution)

The only new D technique here are final switches. A final switch is for enum types, to make the compiler enforce you writing a case to match all of the possible values. That’s what I did here, where I wanted to make sure I matched the up, down, left, and right directions:

    final switch(dir){
    case DIR.d:
      j++;
      break;
    case DIR.u:
      j--;
      break;
    case DIR.l:
      i--;
      break;
    case DIR.r:
      i++;
      break;
    }

The rest of the problem is merely some string parsing.

Day 20: a physics problem with vector operations

(problem statement / my solution)

I have not yet done serious numerical work with D, but I can see that it has all of the necessary ingredients for it. One of the most obvious amongst these is that it has built-in support for writing vector instructions. Given struct to model a particle in motion,

struct particle {
  double[3] pos;
  double[3] vel;
  double[3] acc;
}

the following function return another particle where all of the vectors have been divided by its norm (i.e. normalised to 1):

auto unit(particle p) {
  auto
    pos = p.pos,
    vel = p.vel,
    acc = p.acc;
  pos[] /= pos.norm;
  vel[] /= vel.norm;
  acc[] /= acc.norm;
  particle u = {pos, vel, acc};
  return u;
}

This vec[] /= scalar notation divides all of the vector by the given scalar. But that’s not all. You can also add or multiply vectors elementwise with similar syntax,

      double[3] diff1 = p.pos, diff2 = p.vel;
      diff1[] -= p.vel[];
      diff2[] -= p.acc[];

Here diff1 and diff2 give the vector difference between the position and velocity, and respectively, velocity in acceleration (I use the criterion of all of three of these being mostly collinear to determine if all particles have escaped the system and thus can no longer interact with any other particle).

This is mostly syntactic sugar, however. Although the D compiler can sometimes turn instructions like these into native vector instructions like AVX, real vectorisation has to be done via some standard library support

Day 21: an indexable, hashable, comparable struct

(problem statement / my solution)

I was happy to recognise, via some string mixins, that I could solve this problem by considering the dihedral group of the square:

immutable dihedralFun =
"function(ref const Pattern p) {
  auto n = p.dim;
  auto output = new int[][](n, n);
  foreach(i; 0..n) {
    foreach(j; 0..n) {
      output[i][j] = p.grid[%s][%s];
    }
  }
  return output;
}"
;

immutable dihedralFourGroup = [
  mixin(format(dihedralFun, "i",     "j")),
  mixin(format(dihedralFun, "n-i-1", "j")),
  mixin(format(dihedralFun, "i",     "n-j-1")),
  mixin(format(dihedralFun, "n-i-1", "n-j-1")),
  mixin(format(dihedralFun, "j",     "i")),
  mixin(format(dihedralFun, "n-j-1", "i")),
  mixin(format(dihedralFun, "j",     "n-i-1")),
  mixin(format(dihedralFun, "n-j-1", "n-i-1")),
];

This isn’t a new technique, but I’m really happy how it turns out. Almost like lisp macros, but without devolving into the lawless chaos of Python or Javascript eval or C preprocessor macros. As an aside, the format function accepts formatted strings with POSIX syntax for positional arguments, but there isn’t anything built-in as nice as Perl string interpolation or Python format strings.

The real meat of this problem was to implement a grid structure that could be hashed, compared, and indexed. This is is all done with a number of utility functions. For indexing and slicing, the basic idea is that for a user-defined type foo

  foo[bar..baz]

is sugar for

  foo.opIndex(foo.opSlice(bar, baz))

so those are the two functions you need to implement for indexing and slicing. Similarly, for equality comparison and hashing, you implement opEquals and toHash respectively. I relied on the dihedral functions above for comparison for this problem.

After implementing these functions for a struct (recall: like a class, but with value semantics and no inheritance), the rest of the problem was string parsing and a bit of logic to implement the fractal-like growth rule.

Day 22: more enums, final switches, and complex numbers

(problem statement / my solution)

Another rectangular grid problem, which I again decided to represent via complex numbers. The posssible infection states given in the problem I turned into an enum which I then checked with a final switch as before. The grid is then just an associative array from complex grid positions to infection states.

Nothing new here. By now these are all familiar tools and writing D code is becoming habitual for me.

Day 23: another opcode parsing problem

(problem statement / my solution)

This problem wasn’t technically difficult from a D point of view. The usual switches and string parsing techniques of days 8 and 18 work just as well. In fact, I started with the code of day 18 and modified it slightly to fit this problem.

The challenge was to statically analyse the opcode program to determine that it is implementing a very inefficient primality testing algorithm. I won’t go into an analysis of that program here because others have already done a remarkable job of explaining it. Once this analysis was complete, the meat of the problem then becomes to write a faster primality testing algorithm, such as dumb (but not too dumb) trial division,

auto isComposite(long p) {
  return iota(2, sqrt(cast(double) p)).filter!(x => p % x == 0).any;
}

and use this test at the appropriate location.

Day 24: a routine graph-search problem

(problem statement / my solution)

This problem required some sort of graph structure, which I implemented as an associative array from node ids to all edges incident to that node. The problem then reduces to some sort of graph traversal (I did depth-first search), keeping track of edge weights.

No new D techniques here either, just more practice with my growing bag of tricks.

Day 25: formatted reads to finish off Advent of D

(problem statement / my solution)

The final problem involved parsing a slightly more verbose DSL. For this, I decided to use formatted strings for reading, like so,

auto branchFmt =
"    - Write the value %d.
    - Move one slot to the %s.
    - Continue with state %s.
"
;

auto parseBranch(File f) {
  int writeval;
  string movedir;
  char newstate;

  f.readf(branchFmt, &writeval, &movedir, &newstate);
  return Branch(writeval ? true : false, movedir == "left" ? -1 : 1, newstate);
}

This is admittedly a bit brittle. Even the type check between the formatted string and the expected types is done at runtime (but newer D versions have a compile-time version of readf for type-checking the format string). An error here can cause exceptions at runtime.

Other than this, the only new technique here is that I actually wrote a loop to parse the program file:

auto parseInstructions(File f) {
  Instruction[char] instructions;

  while(!f.eof) {
    char state;
    f.readf("In state %s:\n", &state);
    f.readln; // "If the current value is 0:"
    auto if0 = f.parseBranch;
    f.readln; // "If the current value is 1:"
    auto if1 = f.parseBranch;
    f.readln; // Blank line
    instructions[state] = Instruction(if0, if1);
  }
  return instructions;
}

A small comfort here is that checking for eof in the loop condition actually works. This is always subtly wrong in C++ and I can never remember why.

What’s left of the problem is absolutely routine D by now: associative arrays, UFCS, foreach loops, standard library utilities for summing and iterating and so forth. A few of my favourite things.

Concluding remarks

The best part is that my code was also fast! I was comparing my solutions above with someone else who was doing their Advent of Code in C. I could routinely match his execution speed on the problems where we bothered to compare, whenever we wrote similar algorithms. I’m eager to see what D can do when faced with some real number-crunching.

After all this, I have come to appreciate D more, as well as seeing some of its weak points. I think I have already raved enough about how much I like its functional style, its standard library, its type-checking, and its compile-time calculation. I also ran into a few bugs and deprecated features. I have also observed some language questionable design choices. Not once did I notice having a garbage collector. It was lots of fun.

Merry belated Christmas!

Octave code sprint 2015

So, let’s get this going!

When should the Octave 2015 code sprint be?

Customising Mercurial Like a Pro

Consider the following Mercurial screenshot:

hg-wip

This might look bewildering at first. It’s a custom hg wip command, a variation of hg log. You can see the DAG on the left, what looks like commit summaries in white, and what looks like usernames in mauve. This is not what stock Mercurial looks like, but in my opinion, this looks great. It has so much information packed into such a small space, all colour-coded for your convenience. Let’s take a look.

Current commit

hg-wip-current

The current commit is simply where you’re standing. It’s the commit that hg diff or hg status would use as reference for telling you how the working copy has changed. All that I did for hg wip was to highlight more clearly what this commit is. Note in the DAG that this commit is marked with an “@”.

Bookmarks

hg-wip-book

I have chosen to display bookmarks in green. Recall that bookmarks are simply movable markers that follow along with the commits that they’re pointing to. They’re very similar to git branches. Here I am using them to refer to each of my feature branches. There is a special “@” bookmark that indicates where upstream development is.

Branches

hg-wip-branches

In cyan we see the branch names. In this case there are only two commits on the stable branch. Branch names are permanent names tattooed on commits. This is useful for when you want to have a permanent record of where a commit was done.

Phases

hg-wip-phases

This part is one of my favourites. Mercurial phases indicate whether commits have been published yet or not, and whether they should be shared or not. Commits that have been published and therefore immutable are in orange. The commits I’ve been working on but haven’t been accepted into upstream yet are yellow drafts. Finally, a couple of local patches that should never be shared are secret commits in blue. I am using local revision numbers to identify commits, but it would also be possible to use global hashes.

Selective about which commits to show

Another cool thing about my hg wip command is that it only shows what I consider interesting information about my work-in-progress commits, hence the name of the command. To be precise, it only shows my draft and secret commits, current open heads of development, and the minimum common commits. No other intermediate commits are shown. Actually, usually I don’t even need the extra newlines, and I prefer this more compact format:

compact-hg-wip

So, how is this command built? It actually depends on a number of different Mercurial features, all useful on their own. All of the following snippets go into your ~/.hgrc config file.

Revsets

Revsets are a very useful language for selecting a subset of commits. Here you can see me talking about them. The revset I used for hg wip was

[revsetalias]
wip = (parents(not public()) or not public() or . or head()) and (not obsolete() or unstable()^) and not closed()

It looks like quite a mouthful, so let’s pick it apart:

parents(not public())
Take the parents of all the non-public commits (i.e. drafts and secrets).
or not public() or . or head()
Also take all non-public commits, the current commit (that’s “.”), and all heads.
and (not obsolete() or unstable()^)
But exclude obsolete and unstable commits (this only matters if you’re using the experimental Evolve extension).
and not closed()
And also exclude any closed branch heads

The nice thing is that all of this complicated selection is also fast!

Templating the output

The next step is to show the output in the format that we want it. That’s what the templating engine is for. The template I used here was

[templates]
wip = '{label("log.branch", ifeq(branch, "default", "", branch))} {label("changeset.{phase}", rev)} {label("grep.user", author|user)}{label("log.tag", if(tags," {tags}"))} {bookmarks % "{ifeq(bookmark, currentbookmark, label('log.activebookmark', bookmark), label('log.bookmark', bookmark))} "}\n{label(ifcontains(rev, revset('parents()'), 'desc.here'),desc|firstline)}'

Whoa! That’s even worse than the revset. Unfortunately, due to the nature of the templating engine, inserting whitespace to make this more readable would also make this extra whitespace show up in the final output.

If we are willing to define more intermediate templates and move them to an external template file, it can actually be made readable:

wbrch = '{label("log.branch",
                 ifeq(branch, "default",
                      "",
                      branch))}'
wcset = '{label("changeset.{phase}",
                rev)}'
wuser = '{label("grep.user",
              author|user)}'
wtags = '{label("log.tag",
              if(tags," {tags}"))}'
wbook = '{bookmarks % "{ifeq(bookmark, currentbookmark,
                             label('log.activebookmark', bookmark),
                             label('log.bookmark', bookmark))} "
}'
wdesc = '{label(ifcontains(rev, revset('parents()'), 'desc.here'),
              desc|firstline)}'
changeset = '{wbrch} {wcset} {wuser} {wtags} {wbook}\n{wdesc}'

Okay, this is a bit better, but it requires using an extra config file. The syntax is a bit tricky, but most of it is self-explanatory. Special keywords in {braces} get expanded to their corresponding values. There are a few functions like if() and ifcontains() to selectively output extra information if that information exists. For example, I use ifeq() to hide the branch name if this name is “default”.

Once you’re in a function, keywords are already available. For example, rev gives you the revision number, and if you wanted global hashes instead, you could change that to node or shortest(node). You can even use a revset in the templating engine! In this case, for selecting the current commits and comparing it to the revision being printed. We use the parents() revset to select the current commit(s), because there may be more than one current commit if there’s an uncommitted merge state on the working directory. For template keywords that return a list of things, such as bookmark, we can iterate over elements of that list using “%” and then select different labels depending if the bookmark is the current bookmark or not.

But what is this label function? Ah, well, labelling is how the colour extension decides how to colourise the output.

Colourful Mercurial

The finishing touches are now to pick colours for all of the labels we defined. For this we enable the colour extension and we configure it:

[extensions]
color=

[color]
mode=terminfo

#Custom colours
color.orange=202
color.lightyellow=191
color.darkorange=220
color.brightyellow=226

#Colours for each label
log.branch=cyan
log.summary=lightyellow
log.description=lightyellow
log.bookmark=green
log.tag=darkorange
log.activebookmark = green bold underline

changeset.public=orange bold
changeset.secret=blue bold
changeset.draft=brightyellow bold

desc.here=bold blue_background

Here we set the mode to terminfo so that we can use 256 colours. Most modern terminals can support it, but sometimes you have to specify the $TERM enivronment variable to be xterm-256color or something similar. Then you can define your own colours from the 256 available, referring to the numbers on this chart. If you dislike my colour choices, this is where you can configure them.

Define the command

The final part is to just turn this on:

[alias]
wip = log --graph --rev=wip --template=wip

This defines the hg wip command to be an alias to hg log together with the parameters for displaying the graph, using the wip revset, and the wip template.

And voilà, fancy shmancy colourful hg command! Here is the complete addition to your ~/.hgrc all at once, for delicious copypasta:

[revsetalias]
wip = (parents(not public()) or not public() or . or head()) and (not obsolete() or unstable()^) and not closed()

[templates]
wip = '{label("log.branch", ifeq(branch, "default", "", branch))} {label("changeset.{phase}", rev)} {label("grep.user", author|user)}{label("log.tag", if(tags," {tags}"))} {bookmarks % "{ifeq(bookmark, currentbookmark, label('log.activebookmark', bookmark), label('log.bookmark', bookmark))} "}\n{label(ifcontains(rev, revset('parents()'), 'desc.here'),desc|firstline)}'

[extensions]
color=

[color]
mode=terminfo

#Custom colours
color.orange=202
color.lightyellow=191
color.darkorange=220
color.brightyellow=226

#Colours for each label
log.branch=cyan
log.summary=lightyellow
log.description=lightyellow
log.bookmark=green
log.tag=darkorange
log.activebookmark = green bold underline

changeset.public=orange bold
changeset.secret=blue bold
changeset.draft=brightyellow bold

desc.here=bold blue_background

[alias]
wip = log --graph --rev=wip --template=wip

Acknowledgements

This command comes from ideas cobbled together from Steven Losh, Augie Fackler, and Sean Farley. They are all great contributors to Mercurial, and they have taught me so much! Thanks, guys!

5 Things We Have Forgotten About Open Source

Note: in order to satisfy the exquisite tastes of today’s discerning internet readers, the following blog post is written in Cracked.com style.

We have been using open source for so long that we have forgotten, culturally, where it came from. It seems so natural and ubiquitous that we can no longer remember how things were before it. Some of us are young enough to have never even lived through times were open source wasn’t everywhere.

I am here to set the record straight on a few things, because I have noticed that even people who have lived through ye olden times have forgotten where things came from. Open source wasn’t spawned single-handedly by the sheer might of Linus Torvalds’s virtual gonads. Open source doesn’t mean that money is forbidden. Open source doesn’t mean that Richard Stallman is a twit.

1. “Open source” is a term coined by OSI

First things first, and the #1 thing most people have forgotten about open source: the term did not arise naturally. It was invented in early 1998 during the release of Netscape Navigator as the free Mozilla suite. The Open Source Initiative, composed of trailblazers such as
Eric Raymond and Bruce Perens, decided that we needed a new name for what was about to happen. They got together with other people and Christine Peterson suggested the term, to much rejoicing. She then vanished back into the shadows and went back to being a nanotechnologist or something.

Open source was created... by a girl?!?!
Wait, wait, wait, let me get this straight. Open source was created… by a girl?!?!

OSI is an organisation that got together for a single purpose: to keep saying “open source, open source, open source” so much until everyone else was saying it too. Tim O’Reilly was a big driving force behind this too, putting money into the campaign. This was all in February 1998, remember. That means open source is barely a year older than The Matrix. Neo had probably not even heard about it, because…

2. Nobody called it “open source” before OSI

The greatest testament to how good OSI’s marketing campaign was is that we have come to believe that the term is so natural that we always just called it that. They have convinced us all that “open source” was our idea, without needing to get into our dreams to do so.

... and from now on, you will worship penguins and red t-rexes.
… and from now on, you will worship penguins and red t-rexes.

Needless to say, it was not our idea. Check it out, Google cannot find any mention of “open source” before 1998. That is because, by far, the most common way to refer to “open source” before 1998 was “free software”.

Now, I know what you’re thinking. “Oh god, not this stupid flamewar again. Jordi, we know you’re a FSF-spouting propaganda drivel machine, why do you keep pushing the stupid term for open source that Richard Stallman keeps talking about?”

Wait, wait, hear me out. It wasn’t just Richard Stallman who called it “free software”. You know FreeBSD? The “free” in there doesn’t just mean “without a fee”. They really do mean free as in freedom. Or look at what OpenBSD calls itself a few times while rocking out to sweet, sweet, pufferfish freedom:

[…] we instead celebrate the 10 years that we have been given (so far) to write free software, express our themes in art, and the 5 years that we have made music with a group of talented musicians.

Here is a cartoony yellow pufferfish fighting a fearsome cartoony black blob... but is it art?
Here is a cartoony yellow pufferfish fighting a fearsome cartoony black blob… but is it art?

That’s right, even the biggest haters of the FSF and the GPL, and the most ardent opponents of His Exalted Bearded Gnuliness Richard the Stallman call themselves “free software”.

Amusingly enough, you probably never really noticed this, but the very same Mozilla for whom “open source” was initially coined, tried to call itself “organic software” for a while. No, seriously, they did.

100% GMO-free. No pesticides. Hacked into being by loony hippies.
100% GMO-free. No pesticides. Hacked into being by loony hippies.

3. Open source has a precise definition

Now, here’s the thing: OSI didn’t just say, “here is open source, go wild and free, call anything you want open source!” Nope, in what might appear at first blush to be a cruel ironic twist, OSI did not make the definition of “open source” itself open source. In fact, they even trademarked “open source”, and ask that you only use the phrase according to their trademark guidelines!

Those controlling bastards trampling on our freedom with their smug little ®
Those controlling bastards trampling on our freedom with their smug little ®

Alright, so what does “open source” mean?

Well, in the beginning, Bruce Perens wrote the Debian Free Software Guidelines (there’s that pesky “free” term again). Then, he decided he was just going to grab those very same guidelines, run sed -i s/Debian/Open Source/g, and make that the official definition of open source.

This means that “open source” means a lot more than just “show me the code”. In particular it means that,

  • If you don’t let people sell it, it’s not open source.
  • If you don’t let people give it to their friends, it’s not open source.
  • If you don’t treat all receipients of your software equally, it’s not open source.
If you're not a pinko commie ideologue, it's not open source.
If you’re not a pinko commie ideologue, it’s not open source.

So why did OSI insist so much on a precise definition of open source? Well, because…

4. “Open source” is a synonym for “free software”

Okay, this is one that really gets people riled and the one where the flamewars arise. I am here to tell everyone that if you’re flaming over whether stuff is open source or if it’s free software, you guys need to chill the fuck out: everything that is open source is also free software, and vice versa.

I bet that declaration alone is gonna rile everyone up even more, eh?

This guy has tuned to perfect his built-in flamewar radar under his beard through years of hard labour in the Usenet grand banks.
This guy has tuned to perfection the built-in flamewar radar under his beard through years of hard labour in the Usenet grand banks.

Okay, let’s look at this from a different angle with an analogy. The issue here is with something that philosophers like to call intensionality vs extensionality.

You know how Canada is a constitutional monarchy, right? And you know how there is a Queen of Canada who is the head of government? The Constitution Act of 1867 establishes that Canada has a monarch. She has fun duties such as for example being assigned the copyright of anything an employee of Her Majesty’s Government does. Great fun, I once had someone send us Octave patches under the name of Her Majesty the Queen in Right of Canada.

An elite hacker if I've ever seen one.
An elite hacker if I’ve ever seen one.

Now, you might recognise that lady above, and you probably also know that England also has a queen, and by now my astute readers and you have doubtlessly put together that the Queen of Canada also happens to be the Queen of England. Two names for the same person!

However, Canada’s Constitution Act doesn’t actually specify “The Queen of Canada will be whoever occupies the position of Queen of England”. It just says that Canada has a queen and goes on to list the duties of said queen. This is called the intensionality, the words by which we describe what something is. The extensionality refers to the actual objects in the world that are described by these words. In this case, “Queen of Canada” and “Queen of England” could, perhaps, under some weird political shenanigans end up being two different people, but in practice they end up referring to the same person. So the extensionalities of “Queen of Canada” and “Queen of England” are the same.

Couldn't resist putting another picture of this lovely lady's stylin' fashion...
Couldn’t resist putting another picture of this lovely lady’s stylin’ fashion…

It is the same with free software and open source. The definitions look different, but in practice the software that they refer to ends up being the same. Oh, sure, there are some very minor disagreements over whether this or that license is OSI-approved but not FSF-approved or vice versa, but the whole point of coining “open source” was to have another word to refer to “free software”.

In other words, it was always OSI’s intention for “open source” to be a synonym for “free software”. Hell, even Bruce Perens said so. Why did OSI want a synonym?

5. Open source came with certain promises

The whole point of coining the phrase “open source” was to push a certain point of view. The biggest proponent for the “open source” phrase was Eric Raymond. He and OSI have always described open source as marketing for free software.

So this marketing campaign came with certain promises, promises that we have forgotten were ever part of a marketing campaign by OSI, because they’re so ingrained into open source itself. Stop me if you’ve heard any of these before

  • Open source is a cheaper model to develop software
  • Open source ensures that software has fewer bugs, because more eyes can look at the source code
  • Release early, release often.
  • The best software is created by scratching an itch.

And so on… the whole point was to make free software attractive to business by de-emphasising the whole “freedom” part of it. Instead, OSI promised that by making your software open source, you would have better software, that open source was a better development model, leading to cheaper, less buggy software.

Less buggy? Really?
Less buggy? Really?

The “cheaper model” thing is also still a fairly popular meme nowadays. When you look at free projects in Ohloh.com, one of the lines is how much money it would have cost to build this or that under some model called COCOMO.

I’m not trying to say that OSI is right or wrong about its promises. Some free software really is less buggy than non-free variants. It probably is way cheaper to develop Linux when all of the big companies chip in a few developers here and there to maintain it. All I’m saying is that we have forgotten that with the word “open source”, certain promises came attached to it. Some of these promises might even appear to be broken in some cases.

So next time you hear someone tell you that there will be fewer bugs and everyone will come sending you patches the moment you reveal your source code, remember that they’re repeating campaign slogans. And remember that even if those slogans might not always be true, there might be other reasons why you should give everyone else freedom to enjoy and distribute and hack your software.

X-Men: Days of Future Past, Explained in Mercurial Evolve

So this post made the rounds a couple of days ago, and it got me thinking… can Mercurial (hg) do any better? I think it can, especially with Evolve. Here is me describing how Evolve works:

As to the movie, if you have not seen it yet, you might want to wait until after you do, but the basic gist is a time-travel plot where they go back and fix timelines.

In the beginning

History is terribly wrong, an awful, crippling bug has been discovered way back in history, and it’s so terrible that a big chunk of current history has to be thrown out. Someone created evil sentinels, so evil that they decided to exterminate all mutants and most humans.

Finding the problem

Everyone digs back through the logs to find the cause of the problem. They know everything is bad now,

$ hg bisect --bad

but remember that some time in the past it was ok

$ hg bisect --good xmen-release-1.0

After some discussion,

$ hg bisect --good
$ hg bisect --bad
$ hg bisect --good
$ hg bisect --bad

the problem is revealed:

The first bad revision is:
changeset:   1024:0adf0c6e2698
user:        Raven Darkhölme <mystique@x-men.org>
date:        Fri May 18 12:24:50 1973 -0500
summary:     Kill Trask, get DNA stolen

A bookmark is placed here for future reference

$ hg bookmark mystiques-first-kill -r 1024

Preparing Wolverine

Professor X and Magneto brief Wolverine on his impending task. The history has been made public, but the situation is so hopeless that hg admin Kitty Pryde decides to operate on Wolverine’s repo, the only one that could withstand the changes:

$ cd /home/wolverine/xmen
$ hg phases --draft --force -r 'descendants("mystiques-first-kill")'

Now Wolverine’s repo can endure any change. It’s a desperate move, but these are desperate times. Kitty sends Logan back:

$ hg update -r mystiques-first-kill

Making the fixes

Wolverine dispatches some minor thugs and squashes a few bugs, but the first change needs to alter the timeline,

$ hg amend -m "Attempt some wisecracks with some thugs"
137 new unstable changesets

Now all of the history that was based on top of this commit is unstable. It’s still there, for now, but things are rocky. Sentinels are approaching in the bad future and might kill everyone. Shit will get real there.

That’s ok, though, Wolverine is badass, doesn’t give a fuck, and goes about his business,

$ hg ci -m "Psychoanalyse Charles Xavier"  #Acceptable spelling for a Canadian
$ hg ci -m "New recruit: Peter Maximoff <quicksilver@x-men.org>"
$ hg ci -m "Use Quicksilver to rescue Magneto"
$ hg ci -m "Stop Mystique from killing Trask (WIP)"
$ hg ci -m "Stop Mystique again from killing Trask"
$ hg fold -r .^ -m "Stop Mystique from killing Trask"
$ hg ci -m "Get metal painfully inserted into body. Then get drowned for good measure"

He decided that he didn’t want two separate commits for the same effect of stopping Mystique, so he folded those two commits into one. This is ok, because he’s still in draft mode.

Shelving working changes

Now Wolverine can’t do much about his current situation, and it’s up to others. So he decides to put his memory away for a while,

$ hg shelve

and now it’s up Mystique’s less buggy version, disguised as Stryker, to revive Wolverine,

$ hg ci -m "Rescue Wolverine from only thing that *might* kill him"

and a whole lot of other merry developments happen offscreen:

$ hg ci -m "Rebuild the school"
$ hg ci -m "Get new recruits"
$ hg ci -m "Everyone's happy"
$ hg ci -m "Etc, etc"

Finalising

At this point, the unstable history with the bad timeline is no longer needed. If the X-Men had wanted to keep any part of it, they might have used the hg evolve command, but they just want to forget the whole mess

$ hg bookmark --delete mystiques-first-kill
$ hg prune -r "unstable()"

and the whole thing just fades away. Wolverine reawakens in the future, along with his memories,

$ hg unshelve

and it’s up to him and future Professor X in the good timeline to fix all the merge conflicts that will ensue from this unshelving.

Python is an excellent lingua franca

I just spent 5 days at PyCon 2014 here in Montréal (3 days for the actual conference, 2 days sprinting), and wow, what a great conference that was.

There are many things I want to praise about the whole experience. The venue was great, the organisation was superb, the talks were interesting, the infrastructure was amazing, the atmosphere was friendly… but most of all, I think I want to praise the entire culture of inclusiveness that the Python community is trying to promote.

It is interesting that the only true common thread at the conference was a programming language (and not even that, sometimes, some of the talks were hardly about the Python programming language at all). Python was originally conceived as a programming language that was meant to be as easy as possible to understand. Whether it has succeeded from a purely language-design point of view is hard to say, and not everything about Python is great. The language has its gotchas here and there, just like any other language. And yet, despite not being a perfect language programming language, it’s able to bring together such a diverse group of individuals together to accomplish common goals.

Python is an excellent programming lingua franca for everyone, not just for Unix nerds (witness: Windows support is taken seriously) and not just for programming geeks (witness: Software Carpentry). Just take a look at the wide range of topics covered in the talks. General software development, the benefits of software freedom, cryptography and security (lol, heartbleed)…

Of particular note is that 1/3 of all attendees and speakers were female. Can any other tech conference boast such inclusiveness of the usually tech-neglected half of humankind? Look at all the talks related to gender issues: sexism in rap lyrics via machine learning, being a transgender Python hacker, or how to bring more Python to girls in school.

Now, to be clear, I don’t think that PyCon has eliminated sexism or that we have “won” this battle. As I overheard someone say, PyCon will not be inclusive enough for women unless the lines for the women’s bathroom are as long as the lines for the men’s. And there are still many issues, such as women still being “invisible” and ignored, or as I overheard someone else say, she actually had to say to some guy to look up from her breasts while she was talking to him. It’s not there all the way yet.

This just seems like a good start. I hope next year at PyCon 2015, we’ll be able to get 50% women attendees and speakers!

Poutine bought with bitcoins

I am cautiously hopeful for bitcoin. I just ate pizza and poutine with a group of friends, paying at the restaurant with bitcoins!

Acquiring the bitcoins

I am not a speculator. I am not an investor. I am not a miner. I am not trying to get rich nor make any money whatsoever by manipulating bitcoins. I just want to be able to earn and spend money on the internet without needing the permission of a bank, or the permission of Paypal, or making it anyone’s business but mine and the person I’m actually doing business with.

I acquired some bitcoins about a year ago, at the time it was about 1.8 bitcoins worth around 30 USD. I did not buy them. I did not invest on bitcoins. I did not mine them. I received them as a payment for tutoring mathematics in an IRC channel for an hour and a half. I earned these bitcoins through my labour, just like I would earn any other currency.

At the time there was not much I could do with bitcoins. Although I freely encouraged and accepted the payment in bitcoins, I did it more with amusement than conviction. I am not a criminal, but since at the time Silk Road still had a sort of forbidden underground allure, my client suggested that I could use the bitcoins to buy illegal drugs on the black market. I had no intention to do so, but I decided to keep the bitcoins around, as a cautious hope I could use them for something else.

First purchases

I kept the bitcoins for quite some time, since I could not find anything to spend them on. The first thing I could find that seemed interesting was a 4chan “account” (in reality, just an exemption from its captcha). Despite the website’s bad reputation as being the cesspool of the internet, I think that there is value in its pro-anonymity ethos, something that is slowly being eroded away in today’s online world. This was also my first test case for the possibility of anonymous online currency. In keeping with this ethos, I made the payment, and when there was a slight hiccup with the transaction, used a throw-away email address to resolve the issue. No chargebacks, but people are still people and are still mostly nice. I thus obtained my 4chan captcha exemption. I have not really used it since then, but I am satisfied knowing that I have made a small contribution towards promoting anonymity.

I kept my eye out for news stories of more opportunities to spend bitcoins on. The currency seemed to be slowly gaining more adoption, especially for non-material goods and services. My next purchase was one month of reddit gold as a gift for a particularly witty commentator. These two purchases together had already given a significant blow to my bitcoin balance, but I was not duly concerned. After all, this was just pocket change I acquired for 90 minutes of a hobby task.

Then, suddenly, over a couple of weeks the bitcoin price exploded from 20 USD per bitcoin to over 1000 USD per bitcoin. I didn’t exactly become a millionaire, but my paltry fraction of a bitcoin now had the power to buy more things.

Bitcoin starting to look like a possibility

I made a few more purchases. A PDF copy of Julian Assange’s et al Cypherpunks book. A month of VPN access. Sent bitcoins to a kind stranger on the internet in exchange for digital albums from indie band Nectarphonic. When Gyft.com started selling gift cards to Amazon.com in exchange for bitcoins, I obtained my first physical product for bitcoins: a boxed set of Susan Collin’s The Underland Chronicles.

This really had just been my time getting used to bitcoin and how it works. The fluctuations in price, the cryptography behind it, the UI presented first by the “official” bitcoinqt client and understanding more how the alternative bitcoin client Electrum works. The security model, what it means to “own” bitcoins. Passwords and private keys. The workings of the blockchain. Using Tor for enhanced anonymity of transactions.

I finally got around to reading Satoshi Nakamoto’s whitepaper. Wow. I don’t know if this person or group is a genius or just a child of the times, but Nakamoto seems to have solved a cryptography protocol problem that nobody had solved before. Nakamoto didn’t invent the idea of cryptocurrencies, but merely built upon the ideas of others in order to build a decentralised system. I was duly impressed.

Then two days ago I saw that the first restaurant in Montréal was proclaiming to accept bitcoins. I could now buy Québec’s signature dish, poutine, with bitcoins! Excited, I started making plans.

Food for bitcoins

I eagerly announced yesterday on IRC that I was planning to go to this restaurant to try out my bitcoins. Another chatter local to Montréal decided to tag along for fun. We made plans to go that very evening for a night of socialising, three couples. I eagerly explained to everyone my excitement over finally being able to pay someone face-to-face with bitcoins.

My fiancée and I got to Montréal Poutine in the Old Port a few minutes earlier than everyone else. It was a small location, hardly more than a greasy spoon, but par for the course for a poutine joint. There were signs all over the establishment announcing the possibility of paying with bitcoins and a wifi password on their chalkboards.

We eyed the menu, and I nervously made a few preliminary checks to ensure the transaction would go smoothly. Due to one of my many quirks, I do not own a pocket computer (“smartphones”, neither smart and hardly phones), so I was prepared to pay with my laptop and a webcam for scanning a QR code. I ensured that the internet connection was stable and that I could scan a QR code. As instructed in bitcoinaccepted.ca (or in payezenbitcoin.ca, because this is .ca), I proudly announced to my server that I was going to pay with bitcoins. “Oh, wow, it’s my first time,” she said in French. “Mine too,” I replied with a smile.

Our company arrived, the two other couples. We ordered various kinds of poutine, pizza, avocado fries, beer and mineral water. We chatted about many things, and soon predictable discussions about bitcoins ensued. Their method of operation, their security, their volatility but recent relative stability. Musings if they would ever work or not. The more techy in the bunch were showing signs of optimism, while those who found the idea more foreign were predicting the eventual doom for bitcoins.

After a very pleasant evening, it was time to pay the bill.

The moment of truth

I announced that I had enough bitcoins to pay for all the food, but I asked everyone else to divvy up the drinks between them. I also told them that I had read that tips were not accepted in bitcoins yet, so that would have to be paid elsehow.

I readied my laptop and the webcam, to the growing amusement of my companions. The server came with one bill for food and another for drinks. I reminded her that I was going to pay with bitcoins, but I wasn’t quite sure what to expect. I had seen videos online of handheld machines that displayed a QR code with the bitcoin address to pay to, and that was my guess for what I would see. Instead, she pointed me to a static QR code pasted next to the cash register. Was this the bitcoin address to pay to? I walked with my baroque laptop-and-webcam rig over to the cash register, in good fun as I heard my giggling friends behind me.

I used Electrum to scan the QR code, looking for the address. Instead of a bitcoin address, this was a Bitpay URL. I wasn’t quite sure what to do with it, and I floundered for a few seconds. I opened a generic QR code scanner to get the URL. One of the guys with us helpfully walked over to help me scan the QR code, but I had already managed to get the URL loaded in Firefox by this time. The server was re-reading the instructions next to the QR code on how to pay.

At the Bitpay URL, there were two fields to fill out: an order number and the amount in CAD to pay. The server read the instructions again and said to leave the order number blank. I filled in the amount with taxes, showed it to her, and we agreed it was correct. I clicked enter. A bitcoin address showed up. I went back to Electrum to send money to that address. I stumbled when typing my wallet password. The server, getting the hang of the transaction, said bemusedly, “I cannot help you with that.” Finally I got it, and the familiar “this invoice has been paid” message showed up on the Bitpay website.

A few seconds passed, and the restaurant staff confirmed on another computer that they had received the payment. I showed everyone at the table the paid invoice on my laptop screen. A few other customers in the restaurant were showing some interest. I announced to everyone, “it’s ok, bitcoin has worked, I made the payment!”

Everyone relaxed and proceeded to tackle the more familiar problem of paying for the drinks with more conventional currency.

Future of bitcoins

I don’t know if bitcoin is going to crash or not. I don’t understand enough economics to comment on what the value of bitcoins is, or if it really is different from the value that we give to any other currency. I have a rough understanding of the cryptography behind it and what makes the whole thing work. I know people are working on making bitcoins more accessible to people less enthusiastic than me, and I very much wish they succeed.

All I know is that so far bitcoins have worked for me. I look forward to getting better acquainted with this new way to conduct business. I wish good fortune to everyone else who is also trying to build a new currency for an internet-powered age.

Polling for OctConf 2014

So, we want to know if this is going to work out.

SOCIS 2012 students

Octave has acquired two students for the European Space Agency’s Summer of Code In Space.

Wendy Liu is a Django enthusiast who will be working on finishing Agora Octave. She is a capable webdev, having already built several successful websites, and she is also no stranger to free software and free development, as she is involved with the phpBB community.

Andrius Sutas is familiar with hardware interfaces and will be working on our low-level I/O project for Octave. He has been active in his university robotics student team which has recently announced the development of BLUEbot. In addition to this, he is a capable Unix sysadmin and is familiar with C++ and low-level C and assembly.

Let’s welcome them both and help them achieve success with their projects.


P. S. я играю на гармошке…

OctConf 2012 report

OctConf 2012 was a success. Over the course of five days, we had 20 participants involved, and all but two were there for at least four days. Big thanks to the Centre de Recherches Mathématiques who helped us with all of the organising and logistics.

The first two days were informational and dedicated to getting everyone up to speed on development methodologies. The next three days were a more involved open discussion and development. The schedule was followed with almost no modification. We were sadly unable to record talks due to not being able to secure proper equipment, but we do have the slides.

The following talks took place:

What is Octave? by Jordi Gutiérrez Hermoso
Introductory talk. Raised a few points for future discussion.
Octave’s architecture by Jordi Gutiérrez Hermoso
A discussion about the source code diretory layout and how to find code. Prompted a wiki page about debugging.
Status of Octave by John W. Eaton
Guiding talk about principles and policies plus general state of Octave development given by lead dev.
Octave Speed and Cell Arrays by Daniel Sebald
Raised problems with execution speed related to cell arrays along with possible solutions. Prompted some ideas for how to proceed.
JIT Compiler by Max Brister
First GSoC talk. An explanation of JIT compiling and the important single static assignment (SSA) technique.
The Octave GUI by Jacob Dawid
Second GSoC talk. The upcoming GUI design and layout. Implementation details in Qt. Lots of discussion about how it should look and what Qt can do.
Agora Octave and Packaging by Carlo de Falco, David Pinto and Juan Pablo Carbajal.
An open discussion about how we need to reorganise Octave and code distribution. Resulted in moving Agora to the agora.octave.org domain, and a roadmap for how to proceed.
Bringing Least-Squares Spectral Analysis to Octave by Ben Lewis
Third GSoC talk. Discussion of the method and implementation details. Lots of healthy discussion.
BIM package by Carlo de Falco
An interesting discussion about how to solve an diffusion-advection reaction boundary value problem with Octave tools and other free software.

In addition to the talks, many other important ideas were discussed and decisions about the development of Octave took place. A few highlights:

  • OctConf will now take place annually, with the next one taking place in Europe. The details should be ready within six months from today.
  • Various suggestions on where to improve documentation.
  • Rearrangements of source tree layout
  • Distribution of Windows and Mac OS X binaries will occur in the future, but we will charge for them on a pay-what-you-want scale.
  • Paid support for Octave and specialised binaries (rpms, debs) for enterprise setting will be produced and promoted.
  • Max’s JIT compiling branch got merged back into Savannah. It will be released with Octave 3.8 as an experimental compile-time feature, disabled by default.
  • Have a public list of release goals, editable only by project admins.
  • Better advertisement for Octave. Who uses it, how, write a semiannual newsletter about new developments in Octave.

Lastly, there was also much informal socialising. Lunch every day at various locations, and on Tuesday we went for beer at L’Amère à Boire and that same night saw Greece’s fireworks in Montreal’s international fireworks competition. The final farewell on Saturday was a Mexican brunch at El Sombrero with a few people who stayed for the weekend.

Much fun was had by all.