Friendly Robot Overlord

There are two armies on either side of an enemy city. They can't see each other. They can only communicate by sending messengers to each other. When they send a messenger, they might get captured. If both armies attack at the same time, then they will win. If only one army attacks, then they will both lose. All of the information in this question is known to both sides. What should the General commanding each army do?

This is the Two Generals' Problem which I've rephrased slightly to make it quicker to explain, and also to introduce a loophole so you can actually get a solution. I'm not being particularly formal about this, mainly because it makes it easier for me to handwave over the details that I'm trying to handwave over, but also because it is slightly more pleasant to read.

Why it is impossible

Suppose that there is a strategy which lets them agree on the plan. Then, there must also be some sequence of events that happen which mean that they can agree by sending the fewest number of messengers. What if, the very last messenger that was sent was captured? According to our assumption, there is still an agreement so that is fine. But in that case, the strategy could be simplified by not bothering to send that last messenger. Once you do that, you have a contradiction, because we were going for the fewest number of messengers - but we just found a strategy that sends one less messenger.

Why it is possible

The correct strategy is to just attack immediately and not send any messengers. Each General should realise that sending messages will result the problem mentioned above and they will never be able to attack. But, if no messengers are sent, then the proof breaks, as there is no 'last messenger' to capture. Each General should know that the other General is infinitely smart and perfectly rational, so they can know that the other General will realise that the only way they can win is to not send any messengers.

Sneaky Tricks

So in my rephrasing, I gave the Generals a bit more knowledge - they both knew that they were making their decision at the same time. The fact that they are both making the same decision at the same time was difficult to put into the wording without making it obvious that this was the trick I was doing - I tried to do it by not mentioning time at all, and presenting all the facts in the same tense, so there is some concept of a base reference of time.

So there you have it. If you word the problem poorly enough, you can solve it.

So this is something mainly for my own reference, so don't expect much interesting stuff unless you are writing a parser. But here is a tiny bit of background: When you want a computer to understand a language, you first get it to understand the words (called 'tokens') so it knows where each token starts and ends (see part 1 for slightly more on this). Once you do this, you get a list of words and you need to give them some structure so you know which adjectives relate to which nouns and that sort of thing. This is called parsing.

The obvious interesting thing in parsing is parsing mathematical equations. When you parse "1 + 2 * 3", you need to remember the order of operations, so you know that the "+" refers to the "1" and the "2 * 3", not to the "1" and the "2".

Typically, you write a description of the language in a language like in part 1:

EXPRESSION = EXPRESSION '+' MULTIPLY_EXPRESSION
           | MULTIPLY_EXPRESSION

MULTIPLY_EXPRESSION = MULTIPLY_EXPRESSION '*' PRIMARY_EXPRESSION
                    | PRIMARY_EXPRESSION

PRIMARY_EXPRESSION = number
                   | '(' EXPRESSION ')'

And then rewrite it so that it is easier for a computer to know which rule to apply:

EXPRESSION = MULTIPLY_EXPRESSION EXPRESSION_2
EXPRESSION_2 = nothing
             | '+' EXPRESSION_2

MULTIPLY_EXPRESSION = PRIMARY_EXPRESSION MULTIPLY_EXPRESSION_2
MULTIPLY_EXPRESSION_2 = nothing
                      | '*' MULTIPLY_EXPRESSION_2

PRIMARY_EXPRESSION = number
                   | '(' EXPRESSION ')'

With this form, we don't get stuck in loops trying to parse stuff. Unfortunately, if we were to parse "1 + 2 + 3", we would parse this as "1 + (2 + 3)", which doesn't seem like much of a problem with a "+" sign in there, but there is a big difference between: "(1 - 1) - 1" and "1 - (1 - 1)". So what has happened is that we have changed the associativity of the operators to being right to left.

I've always hated fixing this problem, but I found a very neat algorithm for parsing it in a top-down recursive descent parser called precedence climbing. It is a pretty simple idea in a way - instead of writing a set of functions per precedence level, write a general function and have a table of operators with their precedences and associativity, then the general function can just solve the big picture problems and you don't have to worry.

The relevant part of my parser now looks like this:

static ParseNode parse_general_expression(Tokeniser t, int precedence) {
    int num_operators = (sizeof binary_operators) / (sizeof binary_operators[0]);

    ParseNode t0 = parse_primary_expression(t);

    while (1) {
        Token op = tokeniser_current(t);

        int operator_index = -1;
        for (int i = 0; i < num_operators; i++) {
            if (binary_operators[i].type == token_get_type(op)) {
                operator_index = i;
                break;
            }
        }

        if (operator_index < 0) {
            break;
        }
        if (binary_operators[operator_index].precedence < precedence) {
            break;
        }

        tokeniser_consume(t);
        int q;
        if (binary_operators[operator_index].left_associative) {
            q = 1 + binary_operators[operator_index].precedence;
        }
        else {
            q = binary_operators[operator_index].precedence;
        }

        ParseNode t1 = parse_general_expression(t, q);

        t0 = create_parse_node_binary(PNT_BINARY_OPERATOR, op, t0, t1);
    }

    return t0;
}

But I do need to add some more magic to it, since I'm experimenting with some more whacky precedence rules: I've always thought that "1 * 2+3" should be parsed as "1 * (2+3)" since that's what it looks like, so I'm going to try to parse things that way and see if it stays sane. Typically I don't like whitespace dependence (since lots of things (like HTML) will collapse multiple consecutive spaces into 1), but it just seems so much more natural to me.

Compile and run with gcc blah.c && ./a.out:

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
    int x[2] = {618270585, 58852637};
    int i;
    for (i = 0; i < 2; i++) {
        srand(x[i]);
        while (1) {
            int c = rand() % 27;
            if (c == 0) {
                break;
            }
            putchar('a' + c - 1);
        }       
        putchar(' ');
    }
    putchar('\n');
}

In general, when someone says to compile and run some random code on the internet you should ignore them (since there are enough people out there writing dodgy code that will intentionally delete your stuff). I tell people to do it all the time, but typically it is with code where if you read it it would be obvious what it is doing. It isn't obvious what this code will actually do, but if you know a little bit of c, you can probably tell that it won't do anything bad.

When I run it on my webserver, I get this output: "zggwkrqcikhqycq kadmsdicbknhua". When I run it on my desktop I get a much more pleasant message.

I'm in the process of writing a tokeniser for a c-like programming language. A tokeniser takes a file and splits it up into meaningful chunks. For example, the program I'm using to write this has a tokeniser which splits up what I'm writing into chunks so it can spell check the individual words. So it needs to know that a word ends either on a space or a full stop or whatever. Unfortunately, it doesn't know that a word can continue on a ' so when I write a word like "doesn't", then it tells me that I mis-spelt "doesn" and suggests to replace it with "dozen" (leading to "dozen't", which at least sounds right when read).

There are lots of programs available that will generate the tokeniser for you, if you give them all the rules they need to know, expressed in some simple language. I'm not a huge fan of these, partially because the code generated is ugly, partially because the code is only maintainable with the use of those programs, but mainly because it is more fun to do it yourself.

The next step after the tokeniser is the parser. The grammar checker in a word-processor will have some form of parser, although since English is so horrible, it won't nearly be as pretty as the one for a designed language like a programming language. Once again you can either get a program to generate it for you, or you can do it yourself. When you get the program to generate the parser for you, you have to describe the language in an unambiguous way, so there are a few standard forms for doing this, here is one:

SYNTAX     = { PRODUCTION } .
PRODUCTION = IDENTIFIER "=" EXPRESSION "." .
EXPRESSION = TERM { "|" TERM } .
TERM       = FACTOR { FACTOR } .
FACTOR     = IDENTIFIER
            | LITERAL
            | "[" EXPRESSION "]"
            | "(" EXPRESSION ")"
            | "{" EXPRESSION "}" .
IDENTIFIER = letter { letter } .
LITERAL    = """" character { character } """" .

I saw this on Wikipedia and found it amusing enough to include here. So obviously, it isn't the sort of thing you say at a party or in a stand-up routine, and I think if you even smile when you read it then something is wrong. But what it is as the Wirth syntax notation being used to define itself. So it is about as funny as the equivalent of looking up "dictionary" in the dictionary, knowing that if you didn't know what a dictionary was then you wouldn't be looking in a dictionary to find out. Hilarious.

So, what is "c+"? c+ is the pet name of this programming language I'm working on. It also has a lame computer science-ish joke behind it. If you have a function that tells you the hypotenuse of a right angled triangle given the sides:

hypot(3, 4) => 5

Then that's a pretty cool function. If you wanted to make a function that gave you the hypotenuse of a right angled triangle that has one side of length 1, and the other of an unknown length you could make a new function called hypot1:

function hypot1(other_side) {
    return hypot(1, other_side)
}

Of if you had partial function application, you could just say that the new function is called hypot(1) - that is, you give "hypot" only 1 of the arguments. So 'c+' is just a function which will return the sum of the single argument and c. I don't know if I'll be so awesome as to allow it to work with operators like that... and the cost of muddying up function overloading might mean that either partial function application will be scrapped or given a different syntax.

The main goal of c+ is to have a fast language that is suitable for real-time stuff, but also safe. The safety will be done by not actually having any IO in the language, so a program in c+ will be a "pure" function, and won't be able to change the state of anything. At this point, you've either stopped reading because there are no pictures or links to follow, or you might be wondering how such a language is useful at all. The plan is that IO is done through explicit interfaces passed into the main function.

So, where a c program might look like this:

#include <stdio.h>
int main(int argc, char *argv[]) {
    printf("I'm printing to the screen\n");
    return 0;
}

And can be compiled and run standalone, a c+ program might look like this:

#include <printer>
public void main(Printer p) {
    p.print("I'm printing to the screen\n");
}

And rather than being able to be run straight off, you will need to have a driver program that supplies some sort of "Printer" object. A more complicated program might want a "NetworkAccess" object, or a "FileReader" object or whatever, but basically, where the c program says "I'm going to print stuff to the screen whether you like it or not", the "driver" of the c+ program gets to decide whether or not it will be able to print or not.

The model that seems to be popular in other modern languages is a sandboxed model (like C# or Java). These let the program be written in the c way, but when the program actually goes to print, it prints to a 'virtual' screen, which can then decide if the program should actually be allowed to print (simplified, and I probably don't understand it). The problem I have with this method is that the person running the program will find it difficult to make meaningful decisions when writing the security policy (if there were 1000 different things the program might want to do, they have to think about each one of those and decide if it should be allowed or not). Whereas with the c+ method, they only have to understand the things that the program declares that it wants to use (in this case, it wants to use a Printer object, so you could check and see that a printer just prints to your screen or whatever and know that the program is also wanting to access the internet or something).

The whole language design is subject to change, or to be thrown away as a bad idea, so don't start thinking about porting all your favourite applications to it. It probably seems a bit crazy to be writing the tokeniser for a language that has a design up in the air. But I find that actually implementing things makes the real issues much more visible.

I realised that computer science is a cool enough topic that it needs its own category. I spent most of my time making the icon than the actual content this time, and the icon isn't actually that good. I wanted an icon which conveys computer science, and I know that all scientists wear lab coats and have conical flasks full of green liquid, so they had to be there. I also know that drawing people is hard, especially the hands, so I chopped them out. But to convey the computer thing I couldn't think of much more than putting a monitor in there.

However, there is room for a nice segue from the icon to the topic of quines. When I was doing the computer screen, I thought it would be nice to have a real screen on there. At this point, many people go for a cheap shot at windows, or random mess. I thought it would be more fun to put a screenshot of what my screen looked like at the time, while editing the picture. Not a big issue, but suppose I decided that instead of the screenshot containing the half-finished picture, I wanted one containing the finished picture. The finished picture would have to contain a copy of itself, which contains a copy of itself, which contains a copy of itself, etc.

It is a bit like when you point a video camera at a screen which is showing what the camera is seeing, except even in that case, you start with a picture containing whatever the camera was showing before (say a bit of wall next to the tv screen), then the next frame (where there are probably roughly 30 frames per second) we get the picture of a tv with a picture of a wall, then the next frame we get the picture of a tv with a picture of a tv with a picture of a wall. And this continues, but we never quite get the original picture of the wall out completely (it becomes super small, and you can't see it... but you just have to know it is there).

A quine is basically the computer programmers version of this. You write a program, where the only thing the program does is prints out its output. So you might start like this:

my_program = "print my_program"
print my_program

Which when run would say:

print my_program

Which is nearly right, except we were missing the first line, we could then try extending it a bit:

my_program = "my_program = \"print my_program\"\nprint my_program"
print my_program

(for a non-programmer, a "\n" means newline, and a \" is the way of telling the compiler that the next " isn't ending the string, but a real literal inverted comma sign)

This version prints:

my_program = "print my_program"
print my_program

Which has the same problem - it gets most of the program, but doesn't get it all. You can probably see that extending the method this way will never get the desired program, so we need to be a bit tricky about it.

Here is my simple, but readable quine, written in ruby:

my_program = "my_program = REPLACE_ME\nputs my_program.sub('REPLACE_ME', my_program.inspect)"
puts my_program.sub('REPLACE_ME', my_program.inspect)

sub means substitute, and it takes the thing to find, and the thing to replace it with - it only does the first substitution. e.g. "hello".sub("l", "m") will give "hemlo".

inspect will write out a string the way you would write it in a program - so any " in the string are turned into \" and any newlines are turned into \n and it also puts a " at the start and end. e.g. "hello".inspect will give "\"hello\"".

So we first put the text of the program into the "myprogram" variable, except where we give the value of "myprogram" here, instead we set it to "REPLACEME". Then we print out "myprogram" after substituting "REPLACEME" with the inspected form of "myprogram".

So quines are typically just a fun thing that don't do much and aren't useful and you rarely have to consider them. But there is also a class of quines which I think are quite interesting. I didn't make this, but here is a zip file quine (from here). Unzip it, and you will get two files, one of which is a copy of the original zip file (so you can unzip it again and again).

Why is this so interesting? Well, one of the ways of getting around email filters that spammers use is to put the payload of their spam inside a zip file. So then obviously the antivirus/junk mail filter people will try to fight back by searching inside zip files. So as a programmer, if you are writing the search-inside-zip-file function, and you find another zip file inside the zip file, your initial response might be to check inside that zip file too. But being a programmer, you don't want to be duplicating code, so you just run your original search-inside-zip-file function to search inside the current zip file. Now, if you are faced with the zip file quine, your program is stuck inside an infinite loop.

It isn't like it is the end of the world - you just need to set a recursion limit to something reasonable that won't get in peoples way, but also won't crash your system if there is a limit. But the limit shouldn't be on depth, it should be a limit on the number of zip files unzipped (otherwise you might get beaten by an exponentially growing zip file, where each zip has 100 copies of itself, just with different names).