Alice, Bob, and Mallory

I've been meaning to learn a functional language for years. I don't know what put me off besides the fear of parentheses and the notion that maybe, just maybe, Ruby could be an acceptable Lisp. For all I know, Ruby might be just that, but there's one thing about Ruby that is starting to get more and more unacceptable to me.

Ruby is actually not very well fit to take advantage of the multi-core world we are living in. The GIL and the prevalent mutable state are two big problems. As web applications go, that's often not a problem since it's almost always possible to scale without threads there. But if you want to use the full potential of your multi-core machine in a singe Ruby process/VM, you are out of luck. There are workarounds that get you somewhere and there are implementations of Ruby without a GIL (JRuby and soon Rubinius). Even without the GIL we still have the problem of having a lot of mutable state. That will, probably, make it hard to scale over multiple cores.

A little more than a week ago I watched the presentation Simple Made Easy by Rich Hickey. It's an excellent presentation and one of the best I've seen in years. I was also aware that Hickey is the man who designed Clojure. Finally, I was able to make a choice. I chose to begin to learn Clojure.

I'm still very early in this endeavor. Actually, still trying to decide what books I should read. Anyway, the day after I saw the presentation I downloaded clooj (a simple IDE), read some blogs and some documentation, and started to hack on something. Just to try to get a feel for how hard this was going to be. The parentheses didn't bother me all that much, it was much harder to accept that operators are just functions and that they get no special treatment. It seems you simply have to (+ 31 11) to add 31 and 11. I think I can get over that.

As a side note, it turns out I wrote my first Clojure program on 2011-10-24 and that happened to be the day that John McCarthy, the father of Lisp, died. Yet another of those strange coincidences that seems to happens more often than they should.

The program I wrote is yet another implementation of the stupid simple "algorithm" that I've got to call Leif. If you take Conway's Game of Life, remove the rules and replace them with randomness, you could end up with something like Leif. Quite silly, actually.

Hopefully I will have something more interesting to tell in a couple of weeksmonths, after I've got some more experience with Clojure. For now, Leif will have to do. Here it is.

This is what it looks like at the beginning

and after a couple of minutes it looks like this

One thing that surprised me is that it seems to use both of my cores even though I put no effort whatsoever in making it do so. Probably just the Java GC or something.

Inspired by Randomly not so random I decided to play around with the subject.

Both Java and C# uses a linear congruential generator as their pseudorandom number generators. I found this at MSDN

The current implementation of the Random class is based on a modified version of Donald E. Knuth's subtractive random number generator algorithm."

but I couldn't find any information on what values Microsoft uses for the m, a, and c parameters in their LGC implementation.

The German Federal Office for Information Security (BSI) has established four criteria for quality of deterministic random number generators. They are summarized here: K1 — A sequence of random numbers with a low probability of containing identical consecutive elements.

From the pseudorandom number generator article on Wikipedia. Let's see what we can do about that.

1
2
3
4
5

var random = new Random(116793166);
for (int i = 0; i < 9; i++)
{
    Console.Write(random.Next(10) + " ");
}

Outputs:

1 1 1 1 1 1 1 1 1

Did I just break the K1 criteria above? You know I didn't but you might be interested in how I found the seed number. It's easy but also quite computational intensive, that's why I used Parallel.For.

1
2
3
4
5
6
7
8
9
10
11
12

Parallel.For(0, int.MaxValue, i =>
{
    var rnd = new Random(i);
    bool allSame = true;
    for (int j = 0; j < 9; j++)
    {
        allSame = allSame && rnd.Next(10) == 1;
        if (!allSame) break;
    }
    if (allSame)
        Console.WriteLine(i); 
});

It took a couple of minutes for the number 116793166 to show up in my console.

To keep on playing I needed a random string generator. Mine looks like this.

1
2
3
4
5
6
7
8
9

private const string _chars = "abcdefghijklmnopqrstuvwxyz";

private static string RandomString(int size, Random rng)
{
    var buffer = new char[size];
    for (int i = 0; i < size; i++)
        buffer[i] = _chars[rng.Next(_chars.Length)];
    return new string(buffer);
}

If the random generators were the same it looks like it should give the same result as the Java one but RandomString(5, new Random(-229985452)) returns tfsld. Either my RandomString method works different than the Java one or it's the case that Java and .NET has slightly different settings of their LGCs.

Mathematically there's an infinite amount of inputs that results in a returned hello, for instance 1382472294, but here we are limited by the size of our integers.

I found the seed 1382472294 with the following little method and loop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

private static bool CompareToRandomString(string str, Random rng) 
{ 
    for (int i = 0; i < str.Length; i++)
    {
        if (_chars[rng.Next(_chars.Length)] != str[i])
            return false;
    }
    return true;
}

...

const string lookingFor = "hello";

Parallel.For(0, int.MaxValue, i =>
{
    var rnd = new Random(i);
    if (CompareToRandomString(lookingFor, rnd))
        Console.WriteLine(i);
});

I leave it up to you to implement a break out of that loop.

Ruby does not use a LGC but a Mersenne twister instead. It's still only pseudorandom so there's no problem finding patters you like and being able to repeat them.

1
2

srand(2570940381)
9.times { print "%d " % rand(10) }

Outputs:
1 2 3 4 5 6 7 8 9

1
2
3

charset=('a'..'z').to_a
srand(124931)
puts (0...4).map{ charset.to_a[rand(charset.size)] }.join

Outputs:
ruby

CoffeeScript is inspired by Ruby and Python but what's most peculiar with it is that it compiles to JavaScript. The generated JavaScript isn't all that bad and it even passes JavaScript lint without warnings.

"Underneath all of those embarrassing braces and semicolons, JavaScript has always had a gorgeous object model at its heart." - Jeremy Ashkenas

About a week ago I stumbled on the very clever Sudoku solver by Peter Norvig. I have nothing (or at least not much) against Python but I pretty soon checked out the Ruby translations of the solver. I then refactored one of the solutions to get a chance to get to know the algorithm better.

Now that I finally installed CoffeeScript the Sudoku solver came to mind. I dived in head first and got in trouble pretty soon. It turns out that Array Comprehensions in CoffeeScript differs some from the List Comprehensions in Python.

1
2
3

def cross(A, B):
       "Cross product of elements in A and elements in B."
       return [a+b for a in A for b in B]

returns an one-dimensional array if you call it with two arrays (or strings).

But in CoffeeScript

cross = (A, B) -> (a+b for a in A for b in B)

returns a two-dimensional array.

The jury is still out on if this is intended or not but either way the array comprehensions in CoffeeScript are still very useful.

For the cross-function I ended up with

1
2
3
4
5
6

cross = (A, B) ->
  results = []
  for a in A
    for b in B
      results.push a + b
  results

1
2

cross = (cols, rows) ->
  [].concat (cols.map (x) -> rows.map (y) -> y+x)...

You can find the CoffeScript Sudoku solver as a Gist. Compile it with
coffee -c sudoku.coffee
and then run it with
node sudoku.js

I don't know how I missed it but as Trevor pointed out below all you have to do is
coffee sudoku.coffee

    1 2 3 4 5 6 7 8 9
  |------+-----+-----|
A | 4 8 3|9 2 1|6 5 7|
B | 9 6 7|3 4 5|8 2 1|
C | 2 5 1|8 7 6|4 9 3|
  |------+-----+-----|
D | 5 4 8|1 3 2|9 7 6|
E | 7 2 9|5 6 4|1 3 8|
F | 1 3 6|7 9 8|2 4 5|
  |------+-----+-----|
G | 3 7 2|6 8 9|5 1 4|
H | 8 1 4|2 5 3|7 6 9|
I | 6 9 5|4 1 7|3 8 2|
  |------+-----+-----|

Here's the generated sudoku.js.

This is the only CoffeeScript I've ever written but I already like it (more than JavaScript). Please correct me if I strayed from the CoffeeScript way.

I'm currently at a company still running Windows XP. Last week Internet Explorer 9 was released and it requires at least Windows Vista. That requirement was a problem because we absolutely had to test our web applications in IE9. Microsoft had released Internet Explorer Application Compatibility VPC Images for earlier versions of IE but not for IE9. At least they still offer a VPC running Vista and that was the path we took to solve our testing problems. If you know of an easier way then please tell!

• Download and install Virtual PC.
  Edit 2011-09-25 It seems Microsoft has changed the download page. You can get Virtual PC 2007 for older versions of Windows here.
• Download and run/unpack the IE8-VIS VHD.
• Create a new virtual machine and select the VHD as the harddisk.
• In the virtual machine then download and install Vista SP2.
• Finally, obviously still in the VPC, download IE9.

A couple of days ago I accidentally landed on a page about implementing merge sort in C#. I thought it would be a nice exercise to try to implement that as a generic method and so I did.

I also wanted to learn more about the characteristics of IEnumerable so I used IEnumerable<T> instead of List<T>. That choice got me in trouble and I opted for help on Stack Overflow.

People said it was sorting correctly but Jon Skeet also asked if I tested it correctly and that I did not. I digged deeper into the problem and extended the question on SO. I had a hunch that it was the mutable state of List<T> and the lazy evaluation of IEnumerable that was the problem but I couldn't quite figure out how.

Along came Kobi and his answer finally made me understand why a .Sort() of the list messed up the result of my sorting.

I then changed the implementation to be fully lazy evaluated and now it looks like this.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class MergeSort<T>
{
    public IEnumerable<T> Sort(IEnumerable<T> arr)
    {
        if (arr.Count() <= 1) return arr;

        int middle = arr.Count() / 2;
        var left = arr.Take(middle);
        var right = arr.Skip(middle);
        return Merge(Sort(left), Sort(right));
    }

    private static IEnumerable<T> Merge(IEnumerable<T> left, IEnumerable<T> right)
    {
        IEnumerable<T> arrSorted = Enumerable.Empty<T>();

        while (left.Count() > 0 && right.Count() > 0)
        {
            if (Comparer<T>.Default.Compare(left.First(), right.First()) < 0)
            {
                arrSorted=arrSorted.Concat(left.Take(1));
                left = left.Skip(1);
            }
            else
            {
                arrSorted=arrSorted.Concat(right.Take(1));
                right = right.Skip(1);
            }
        }

        return arrSorted.Concat(left).Concat(right);
    }
}

Please be aware that this is but an exercise and not very efficient.

Now to the problems that you can encounter with the above and an explanation to the title of the post. Let's MergeSort a simple List<int> followed by a call to the built-in .Sort() on List<T>.

1
2
3
4
5
6

var ints = new List<int> { 2, 3, 1 };
var mergeSortInt = new MergeSort<int>();
var sortedInts = mergeSortInt.Sort(ints);
// sortedInts.ToList() is {1, 2, 3}
ints.Sort();
// sortedInts.ToList() is {3, 1, 2}

So what's going on here? As far as I can tell it's something like this. sortedInts isn't evaluated until the first call to MoveNext() (or Tolist() or any of those). Before that it only has lazy pointers to the original enumerable values. ints.Sort() messes up the beauty of lazy evaluation by changing the underlying data structure. It can do that because List<T> is mutable (writeable).

But why {3, 1, 2} after ints.Sort()? The original sequence was { 2, 3, 1} and that is what the MergeSort sorted, not by creating a new sequence but only by lazy pointers.

At first the MergeSort sorts like this

but after the source list has been sorted/changed it will do this

What can you do to stop this to happening to you? The boring way is to never use lazy evaluation but that is kind of hard if you happen to use LINQ (and you should, it's great). Another way is to use immutable data structures and that is how functional languages tackles this problem. In C# we have the ReadOnlyCollection and it obviously has no Sort() method.

A nice feature of the MergeSort above is that it has no problems with an immutable collection.

1
2
3
4
5

var rints = new ReadOnlyCollection<int>(ints);
var sortedRints = mergeSortInt.Sort(rints);
// sortedRints.ToList() is {1, 2, 3}
ints.Sort();
// sortedRints.ToList() is {3, 1, 2}

What?! How could an immutable collection get messed up like this? It turns out that ReadOnlyCollection<T> is only a facade for mutable collections and that is what bit us here. You have to pass a copy of the list. Example follows.

1
2
3

var rints = new ReadOnlyCollection<int>(new List<int>(ints));
var sortedRints = mergeSortInt.Sort(rints);
ints.Sort();

That also works for List<T>.

1
2
3
4
5
6

var ints = new List<int> { 2, 3, 1 };
var mergeSortInt = new MergeSort<int>();
var sortedInts = mergeSortInt.Sort(new List<int>(ints));
// sortedInts.ToList() is {1, 2, 3}
ints.Sort();
// sortedInts.ToList() is {1, 2, 3}

Finally I would like to send a big thank you to Kobi for sorting out my problems with the original solution.