Categories

## Mersenne Twister in Clojure

The Mersenne Twiser is a random number generator that has a lot of applications, particularly in finance. After discovering that there was no Clojure implementation at Wikipedia I decided to give it a try as my first attempt at something useful in Clojure. As it turns out it’s problably not a good candidate to be implemented in a functional language because the whole thing requires modifying a mutable array for every call to (genrand).

I’m not very excited by the solution because it doesn’t seem very lispy. It much more resembles the reference implementation, and gives the same results as it for all the tests I tried.

I’m sure it could be better though.

If it’s of any use to anyone you can find it here.

Categories

## REPL to the rescue!

Yesterday I watched Dan Weinreb talking about ITA, Lisp, and well, really, really complex stuff 😉

The kind-of conclusion that he drew on the future of Lisp is that Clojure is the next Common Lisp. I’ve been dodging Clojure for about a year now. I bought the book from The Pragmatic Programmers when the book was in beta and eagerly followed the examples and decided it had promise. But, I figured that if I needed to really learn it (and by that I mean use it, not just talk about using it) it would have to come to me. It would do this, I reasoned, by being hard-to-ignore.

Well there seem to be more than enough smart-folks on-board now (like: Eric Normand, Bill Clementson to name only two) so I guess I better not miss the party. Not because I’m smart but because if I don’t make too much noise I can blend in and no one will notice I’m there.

So I came to the conclusion that I should try and use it for ad-hoc things that might cross-my-dome and are hard(er) to solve in non-functional languages.

For instance, this very afternoon I wanted to know how many possible hand distributions by suit there are in the card game Bridge. So four possible distributions might be:

• All 13 hearts
• 12 hearts, one diamond
• 11 hearts, one diamond, one club
• 10 hearts, one diamond, one club, one spade

The question is how many total distributions are possible?

I banged my head on the table-hard trying to figure out the answer to this. At first it seemed like a simple counting problem, but if it is I’m too simple to see it. Then I wondered if it could be an additive patitioning problem, but ordering is important so I don’t think it is. It didn’t feel NP complete. I know one thing though, at this late hour it might as well be.

1:57 bridge=> (count (for [spades (range 0 14)
hearts (range 0 14)
diamonds (range 0 14)
clubs (range 0 14)
:when (= 13 (+ spades hearts diamonds clubs))]
560

Functional programming rocks.

Categories

## What?

C++ was a boon for technical interviewers. There was a time when C++ was about the only viable object-oriented programming language in a business environment. In those days you pretty much had to know C/C++ to be an OO programmer. So you could test someone’s depth of C++ knowledge (and thus their overall suitability) by just asking about all the messed up edge cases that make C++ really tricky to use.

Today we’ll be observing a hypothetical candidate Phil. Phil has been a C++ programmer for 5 years (2 of which were at University) and has rated himself 9/10 on the C++ confidence scale that I asked him about at the beginning. I’ve been talking to Phil about the various ‘overloaded’ meanings of the keyword virtual in C++. Phil has correctly answered what a virtual method was, but couldn’t get the one about the virtual base class.

Even so, Phil is now into his stride and feeling pretty good about himself, so then I lay it on him:

Phil, is it possible to ever call a pure virtual method?

To which Phil (and about 95% of other candidates) would heartily reply “No”. And of course Phil would be wrong. But that’s ok. First I want Phil to tell me why a pure virtual method can not be called usually. This demonstrates a basic understanding, and then I would try and probe to see if Phil can guess the correct answer as to how a pure virtual method can be called and then the reason it’s possible.

## So, what?

If Phil didn’t get the answer straight away then Phil probably won’t get it at all. This is not terribly surprising I suppose, and it’s not a reason to reject Phil. The sad truth about being a C++ programmer is that you really need to know how C++ works, at some level, to be able to use it effectively. I’m here to find out what Phil’s level really is. The more oppurtunities I give him to tell me about those edge cases the better I can assess how good a (C++) programmer he is.

## How?

So here is a code sample that under a couple of compilers (VC++ 2005 – Express, and GCC 3.4.4) produces the (un?)desired behaviour. I wanted to try it under some more recent C++ compiler invocations but don’t have them available on the machine that I’m writing this. Anyway, these two compilers seem fairly representative of what a lot of people are currently using.


#include<stdio.h>

class A {
protected:
virtual void Reset() = 0;
void Init()	{
Reset();
}
public:
A()	{
Init();
}
};

class B : A {
protected:
void Reset() 	{
printf("Reset");
}
public:
B() {
}
};

int main(int argc, char** argv)
{
B b;
}
 

And here is the result:

$g++ pvirt.cpp$ ./a.out
pure virtual method called
9 [sig] a.out 180 _cygtls::handle_exceptions: Error while dumping state (p
robably corrupted stack)
Segmentation fault (core dumped)

So for those, like Phil, not fully aware of the vaguaries of calling pure virtual methods here is the explanation.

Pure virtual methods can be called from base-class constructors that attempt to indirectly call pure virtual methods.

The reason it's a problem is that C++ constructs objects inside-out, so base classes get built before derived classes. If you then try and call a virtual method on a partially constructed object you will end up calling the base class copy of the virtual method. This is because at the time you are in the base-class constructor the object is of type base-class and not of type derived-class. Calling pure virtual methods from constructors sounds like a really bad idea then, and it is. But there might be legitimate reasons to want to do it, which I'll come to in a minute.

Note that if you try and call the virtual method directly from the constructor, like so:

class A
{
protected:
virtual void Reset() = 0;
public:
A()	{
Reset();
}
};

You will probably get a linker error because Reset() is pure and has no implementation, as you'd expect.

## Why?

So why might you want to do this at all then? Well say you have a class hierarchy of objects that connect to a database for example.

So you dutifully create a Database base class with MySQLDatabase and OracleDatabase derived classes. Now when you disconnect an already established connection you need to reset all the structures as if they had just been created. The object is then ready to be reconnected. So you create a virtual Reset() method in the base class that does this. At the base level though this class should do nothing and you decide that your derived classes must define such a method so you very cleverly make it pure. You could then (but you probably wouldn't) write code like this:


void Database::Disconnect() {
Reset();
}

And have the derived class handle the gorey details of the reset. You want the same behaviour when you create a new object so you simply add the Reset() function to the Init() function that you created to deal with the fact that you had to write so many different types of copy constructor in C++! Hey presto pure virtual method called.

Note that if you had decided not to make the method pure and just put in an empty stub then this empty stub would be called instead (and not the derived version). In some ways this is a harder error to track because there is no error just a silent refusal by the object system to call the derived version because it can't, because it doesn't exist yet.

The correct way to deal with this, unsurprisingly, is to not call Reset() from the base-class Init() function but from the derived constructor directly.

## Phil

Thanks for coming Phil, we'll be in touch.

Categories

## The First Casualty

I had to read this paragraph from the BBC about the recent Iranian elections twice to make sure I understood it correctly:

The official said the state department contacted Twitter over the weekend to urge it to delay a planned upgrade that could have cut daytime service to Iranians.

So, let me get this straight. The US state department monitors Twitter traffic and is reviewing what Iranians are commenting on the topic of their government. The department wanted to prevent an upgrade to Twitter that might stop the flow of revolutionist propaganda getting back out on the street and starting a larger movement.

Don’t get me wrong, it’s a good call. It just caught me a little by surprise.

I guess I shouldn’t actually be surprised by this but it marks a very definite transition (to me at least) for Twitter. Folks at Twitter have probably been feeling it for years though. The point is though that it’s no longer a fun toy.

Twitter is now, amongst other things, a marketing place for the public, politicians, and companies. But for government departments it’s also a socio-political barometer.

Innocence lost.

Categories

I am ashamed to say that I wasn’t really sure if the Mono project would ever succeed. It seemed like such an enormous task, and one that would forever be playing catch-up with M$, that it just didn’t make sense. Even so, I’ve sort of been following it from the sidelines for a while and I’m excited to say that Mono 2.4 seems to be a drop-in replacement for the bits of the .NET SDK I was actually using. Now with the release of MonoDevelop 2.0 it seems that I’m also able to get a functioning alternative to the Visual Studio GUI I’ve been using. It’s a colossal achievement and one that makes me even more ashamed. Ashamed that I didn’t think it was possible, and ashamed that I didn’t help out. To get it working was a bit of a trial though. It turns out that because I already had the default MonoDevelop 1.0 installed that when I started trying to build a new version things got very confused. Not only that it turns out that the build instructions for MonoDevelop 2.0 aren’t exactly correct. After a lot of messing around I think I managed to damage the default installation and cross-link a few libraries here and there. I think if I was doing it again I should probably have followed these instructions Parallel Mono Environments before doing anything. Too late now though. After much building and swearing I ended up uninstalling all Mono environments and then rebuilding everything for Mono 2.4. I didn’t put the Hardy version back yet, I’ll do that if I need to. Here’s what I did, in case it helps anyone. First of all I decided that this is a temporary solution and that eventually I would be able to get MonoDevelop 2.0 running from APT, therefore I decided to install everything in /usr/local. ## Ubuntu Development Packages As ever with Ubuntu you will quite probably need to install a bunch of development libraries to make it work. I probably had a lot of the dependencies I needed installed before I began but here are the ones that I didn’t have that I needed. Your mileage might vary. sudo apt-get install bison gnunet-gtk-dev libpango1.0-dev libgtk2.0-dev libglade2-dev libgnome-dev libart-dev libgnome2-dev libgnome-dev libgnomeui-dev libgnomeprint2.2-dev libgnomeprintui2.2-dev libgnomecanvas2-dev libpanel-applet2-dev  ## Mono As per the parallel environments guide I set up this environment in a script and executed it. #!/bin/bash MONO_PREFIX=/usr/local GNOME_PREFIX=/usr export DYLD_LIBRARY_PATH=$MONO_PREFIX/lib:$DYLD_LIBRARY_PATH export LD_LIBRARY_PATH=$MONO_PREFIX/lib:$LD_LIBRARY_PATH export C_INCLUDE_PATH=$MONO_PREFIX/include:$GNOME_PREFIX/include export ACLOCAL_PATH=$MONO_PREFIX/share/aclocal
export PKG_CONFIG_PATH=$MONO_PREFIX/lib/pkgconfig:$GNOME_PREFIX/lib/pkgconfig
PATH=$MONO_PREFIX/bin:$PATH
MONO_GAC_PREFIX=/usr/local
PS1="[mono] \w @ "

I then downloaded the following libraries from the Mono 2.4 sources page.

wget http://ftp.novell.com/pub/mono/sources/libgdiplus/libgdiplus-2.4.tar.bz2
http://ftp.novell.com/pub/mono/sources/mono/mono-2.4.tar.bz2
http://ftp.novell.com/pub/mono/sources/gtk-sharp212/gtk-sharp-2.12.8.tar.bz2
http://ftp.novell.com/pub/mono/sources/gnome-sharp220/gnome-sharp-2.20.1.tar.bz2
http://ftp.novell.com/pub/mono/sources/mono-tools/mono-tools-2.4.tar.bz2
http://ftp.novell.com/pub/mono/sources/mono-debugger/mono-debugger-2.4.tar.bz2
http://ftp.novell.com/pub/mono/sources/monodevelop/monodevelop-2.0.tar.bz2
http://ftp.novell.com/pub/mono/sources/monodevelop-debugger-mdb/monodevelop-debugger-mdb-2.0.tar.bz2
http://ftp.novell.com/pub/mono/sources/monodevelop-database/monodevelop-database-2.0.tar.bz2
 

Extract all these and then run the below command in each. Because this is a dependency stack you will need to do them roughly in the order they're listed above.

./configure --prefix=/usr/local
make && sudo make install

After that you should be left with a working MonoDevelop 2.0!

## Troubles

I encountered a few problems on the way, mostly there were problems relating to not having the correct Ubuntu development libraries and headers installed when the parts of the stack were configured.

I also ran into some problems with the GAC having pre-installed versions of conflicting libraries installed. Eventually though this problem was resolved by uninstalling the default Hardy version of Mono and starting again. Hopefully you won't have this problem because you will have setup a parallel environment in the first place ...