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.

Recently N. asked a question on a list that made my geek-senses tingle. He had a test with 12 levels of questions. The testee should answer 10 questions. If a question was answered correctly the level would go up and if it was not correct it would go down. If a level 12 was answered correctly, another level 12 would be asked and vice versa. The first question would be a level 6. N. wanted to know how many questions of each level he needed.

Pretty soon he got a correct answer and several wrong. One of the incorrect answers was, and I don't like to admit this, provided by me. I took the recursive route (which I very seldom do) and then tried to present the result in ASCII. I failed. The result from the algorithm in itself was correct but the presentation was simplified so much it failed to deliver the correct answer. Here it is:

             06
            05 07
          04 06 08
         03 05 07 09
       02 04 06 08 10
      01 03 05 07 09 11
    01 02 04 06 08 10 12
   01 02 03 05 07 09 11 12
 01 02 03 04 06 08 10 11 12
01 02 03 04 05 07 09 10 11 12

The problem is that this result can be read as if the testee could get two level 2 questions in a row but the rules forbids that.

Then I remembered reading about Graphviz and especially Ruby-Graphviz. That's what I used to generate the graph to the right. The graph itself is nothing but a visualization of all the possible question sequences. To find the answer that N. was looking for you can follow a level from top to bottom and count the number of times it can occur. I have to admit that it's far from the most convenient way but it works.

The result
5 of level 1, 5, 6 & 7.
4 of level 3, 4, 8, 9 & 12.
3 of level 2, 10 & 11.

I had to jump a few hurdles to get there. First my old Ubuntu-install, for unknown reasons, had some ancient version of libfreetype in /usr/local/lib/ that I had to remove. In the end an rm /usr/local/lib/libfreetype* would have been good. I also did a sudo ldconfig but I'm not sure that was necessary. Let's just hope you're on a modern system where a sudo apt-get install graphviz followed by sudo gem install ruby-graphviz will be enough.

The recursive code I wrote produces every single path the testee can take. A graph of that would be quite big since it's 1023 nodes. I then found out about strict digraph in the Graphviz DOT language. It sounded like a perfect fit and it was! One problem though, Ruby-Graphviz didn't seem to know about it. The power of open source software let me patch ruby-graphviz-0.9.18/lib/graphviz/constants.rb so that GRAPHTYPE included it

1
2
3
4

## Const: graphs type
 GRAPHTYPE = [
   "digraph", "graph", "strict digraph"
 ]

Another awesome power of open source is Grégoire Lejeune because only hours after me contacting him he added it to the GitHub repository.

Here's the code that produced the Rooted Binary Directed Acyclic Graph (or is it Rooted Directed Binary Acyclic Graph?).

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

require 'rubygems'
require 'graphviz'

@min_level=1
@max_level=12
@max_depth=10
start_level=6

@g = GraphViz.new(:G, :type => "strict digraph" )

def add_node(level, depth, parent)
  if depth<@max_depth
    current=[level, depth].join(",")

    sub=level<=>@min_level
    add=@max_level<=>level
    add_node(level-sub, depth+1, current)
    add_node(level+add, depth+1, current)

    @g.add_node(current).label=level.to_s
    @g.add_edge(parent, current) unless parent=="00"
  end
end

add_node(start_level, 0, "00")

@g.output( :png => "graph.png" )

With the current parameters this problem might not be the most exciting but I believe that by just modifying them slightly we would, again, reach a wall of complexity.

There's more than one way to skin a cat and the same is true for looping in Ruby. This is a silly post with a silly number of ways to

print the integers from 1 to 10.

If you're a BASIC-programmer and are getting your feet wet with Ruby, you might end up with something like this.

1
2
3
4

while i<=10 do
   puts i
   i+=1
end

That and the following for-loop is not the usual Ruby way of looping.

1
2
3

for i in 1..10
 puts i
end

Instead rubyists often iterates over ranges or arrays with each.

(1..10).each {|i| puts i }

But for simple integer loops like this, we also have upto

1.upto(10) {|i| puts i }

and times.

10.times {|i| puts i+1}

Here's where I should've stopped but I can't help myself, I just have to show off with some Symbol#to_proc "magic".

(0..10).inject(&:p)

The above works because p is an alias of puts and & converts the symbol :p to a proc that is called with the numbers in the range as parameters.

The alias p also gives us, what I think has to be, the shortest possible way.

p *1..10

You could argue that it's a bad thing that there are so many ways to do something as simple as this. But I see no big problem here, if any at all, even though these are hardly all possible ways to loop over integers in Ruby.