I have been meaning for some time to tackle the RubyQuiz problems in Python.

The one from yesterday (#148) is quite interesting, taking postfix notated expressions and returning an infix version.

For example

1

2 3 5 +

goes to

1

2 * (3 + 5)

I spoilt it a bit by reading Reverse Polish Notation on Wikipedia, which gave away how to evaluate the postfix expressions.

Here is my python code to evaluate postfix expressions

ops = ["+","*","/","-"]

def evaluate(inputpfs):
    numstack =[]
    opstack = []
    for i in inputpfs.split():
        if i not in ops:
            numstack.append(i)
        else:
            right = numstack.pop()
            left = numstack.pop()
            #print (left + i +  right)
            numstack.append(str(eval(left + i +  right)))
    assert len(numstack) == 1
    return eval(numstack[0])

Then I realised all I needed to do was remove eval, add brackets and I would have what I needed.

def bracket(somestring):
    return "(" + somestring + ")"

def post2infix(inputpfs):
    numstack = []
    opstack = []
    resultstr = ""
    for i in inputpfs.split():
        if i not in ops:
            numstack.append(i)
        else:
            right = numstack.pop()
            left = numstack.pop()
            newresult = " ".join([left, i, right])
            newresult = bracket(newresult)
            numstack.append(newresult)
    return numstack[0]

Then only printing brackets when you must. If the operation is - or /; you always need them around the right hand expression, unless is is a plain number as they are not associative. If the operation is +, you never need them. If the operation is * then you need them if you have + or - in the right hand expression. Note that left is always a plain number as only the top element of the stack is a compound expression

def isnum (somestring):
    return all([i not in somestring for i in ops])

def post2infixpp(inputpfs):
    numstack = []
    opstack = []
    resultstr = ""
    for i in inputpfs.split():
        if i not in ops:
            numstack.append(i)
        else:
            right = numstack.pop()
            left = numstack.pop()
            if not isnum(right):
            #if (not all([i not in right for i in ops])):
                if i in ["/", "-"]:
                    right = bracket(right)
                elif i=="*" and ("-" in right or "+" in right):
                    right = bracket(right)
            newresult = " ".join([left, i, right])
            numstack.append(newresult)
    return numstack[0]

A subtle bug means I could not do isnum inline (commented out, line 15 here), I had to add an auxiliary function. Though this way is more comprehensible, I cannot figure out why swapping lines 14 and 15 breaks the code.

Testing: I know I should have done a bit more error checking in the above functions, but here is the little test sequence I wrote.

eg1 = "2 3 +"
eg2 = "2 3 5 + *"
eg3 = "56 34 213.7 + * 678 -"
egs = [eg1,eg2,eg3]

for i in egs:
    print "*********"
    print i
    print evaluate(i)
    print post2infix(i)
    print post2infixpp(i)
    assert (#evaluate(i) ==
            eval(post2infix(i)) ==
            eval(post2infixpp(i))
           )

I had to comment out the evaluate(i) part of the assertion as it failed on eg3 due to some sort of floating point rounding error. I will try and track down why tomorrow.

evaluate(eg3) == 13193.200000000001
eval(post2infixpp(eg3)) == eval(post2infix(eg3)) == 13193.199999999999

Get the file Here

Oxfam Unwrapped, it sounds like a site exposing the real harm done by Oxfam or something. It is actually a great idea, giving people a little card to show you donated an amount of money to Oxfam rather than spend a few quid on something they may not even like. Also there is nothing like a bit of conspicuous giving to alleviate guilt. It hits the emotions too, I bought part of a school in Africa apparently (I suppose because “£5 could buy part of a school” does not sound as good). I wonder if anyone really thinks that the money they spend does end up where it says on the card, half of oxfams money would go in the infrastructure to support the tracking and allocation of it all.

I went 50/50 for my £10 secret santa gift, getting some Fair Trade chocolate to wrap up alongside the card.

I just watched Faith, Evolution, and Programming Languages, a Google EngEDU video. It was by Philip Wadler, a chap who I had never heard of but who has done loads of cool things. He designed Haskell’s Type Classes and Java’s Generics, and is currently working on a bridge between strongly typed and dynamically typed languages. The talk starts off with a brief, fascinating explanation of links (more properly isomorphisms) between logics and programming languages and makes the point that aliens may not create Java but certainly will create (discover?, I suppose it depends if you are a Platonist) the lambda calculus (calculi ?).

For about 20 mins towards the end I lost the plot and could not really follow his argument, but I will revisit it when I know a bit more. I am glad I hung on as the 10 minutes of discussion at the end were quite interesting and Links (the recent work he did not have time to show the slides for, a web framework with every tier written in the same language) seemed very interesting.

For more on the language/logic link, see here

I saw Simon Peyton-Jones talk on Software Transactional Memory at OSCON and was amazed at how neat it sounded. Taking some ideas from databases to remove some of the pain of multithreaded programming is a great idea. His point that a thread-safe Dequeue is a post-doc publishable result convinced me that something is wrong with the threading models in widespread use, while STM reduces it to an undergrad problem. The maping from the complexity of the problem domain to your code should be sane, if implementing a a simple structure like a dequeue using threads makes the code lots longer and requires a large amount of effort by someone with a doctorate, something is wrong. I love python, but multithreaded programs suffer (at least in the C implementation) because of the global interpretor lock (GIL). So I decided to learn Haskell.

There are (as far as I know) two ways of doing concurrency; shared state and message passing. STM is a neat syntax and smart compiler technology that ultimately uses shared state. See a Java or C# implementation here.

Erlang is becoming increasingly popular and big successes with high availability at Ericsson are compelling real world examples of its use. It uses message passing concurrency and is a nice (mostly) functional language. I am happy with the choice of Haskell though, the syntax seems neat (because of my maths background) and the functional purity enforces functional thinking more than (say) Common Lisp or OCaml. There was a great post today on Planet Haskell on concurrency options in Haskell and I am keen to explore them.

Maybe I will not hack in Haskell full time, but I think some of the ideas will go mainstream (already appearing in Linq and C# from Microsoft, who have bought in a lot of talented folk from the FP world ), but maybe I will.

It fits my mind well so far.

At the weekend I went to see the Tutankhamun and Qin Shihuangdi exhibits in London. Tutankhamun is at the O2 (formally millennium) Dome and Qin Shihuangdi is at one of my favourite places in the world, The British Museum. Both are superb, well worth a visit.

I stayed with a good friend from uni and met up with another in covent garden along with one of my oldest friends and had a few beers and a really good buzz. I love London, such a vibrant city and so much to see and do (admittedly I have spent very little time in rush hour commuting on the tube, which is hellish)

That used to be my opinion, I thought philosophers had nothing to say on the subject, until I read an essay by Daniel Dennett called Where Am I? . Dennett’s thought experiment shows that the sense of self we have arises in a large part from viewing the world out of the middle of your head. He is a superb thinker on evolution, conciousness, free will and joined in on the recent flood of books on religion. To get an idea of his thoughts, see him at TED in 2002, 2003 and 2006. I agree with most of what Dennett says (his attack on the Cartesian dualism that most of us subscribe to, often unknowingly) but not his central thesis (that the mind simulates a Von Neumann machine). This idea seems in line with the habit of humans to draw analogies between the latest in technology and the brain, John Searle gives examples of folk likening the brain to a telephone exchange, a clock mechanism and even a catapult. I think the idea will seem less likely when computers soon stop being Von Neumann machines as we move towards multi-core, massively parallel, computers.

That said, neuroscientists can say more than most people realise about how our brains work and how surprisingly specialised parts of it are. A really superb neuroscientist is Vilayanur Ramachandran. I read “Phantoms in the Brain” a few years ago and he gave the BBC’s Reith Lectures in 2003 and gave a great talk at TED this year

You are singing the song that goes “I got love for you if you were born in the 80s” and your girlfriend (who was born in 1979) says “what, no love for me?” and you reply “actually what I said does not imply that at all, you cant just negate both sides of a proposition and expect to get a true statement, if you reverse the implication too (to get the contrapositive) then you have a true statement, ie if I don’t love you you weren’t born in the 80s.”

If you have not seen it, go and checkout the OLPC project. Technologically it is superb: The screen is revolutionary, having two display modes (a 800x600 colour display mode and a 1200x900, 200DPI black and white mode that can be used in direct sunlight). The wireless networking can create a mesh to connect children and share any internet access between them all. All the software is Free (as in freedom). You can get hold of one now using give one get one.

I know this will not solve all of the worlds problems, people who have no food to eat or are in a war zone will not benefit from having a neat little laptop. OLPC is not simply a charity project, it is made to be useful to children and low cost (governments all over the world are signed up to buy them). Education can make a real difference to a society once the basic necessities are met.

I saw on the TED blog a talk by Andrew Mwenda on why aid is not the answer to problems in Africa, economic growth is. I agree, particularly after seeing the wonderful presentations by Hans Rosling (first , second) also at TED. Please do watch these as they are inspiring and really show the power of good data to shed light rather than heat on complex situations. Go play with the data yourself at gapminder.org .

I posted last time about TeXmacs and remembered the plugins for using it to display output from some of the superb free maths packages (which sometimes lack a nice display).

The one I am excited about most is for SAGE. SAGE is written in python and leverages the hard work of the other projects (its motto is Building the Car Instead of Reinventing the Wheel). See the TeXmacs plugin here and some screenshots of SAGE here.

I will take a look at the code and see if I can contribute anything, it will be nice to get involved in a big project.

While I am not all that particular about most things, poor fonts annoy me; particularly if most of the desktop is OK. The Linux (strictly speaking XFree86) font display was always either ugly or hard to get working. Ubuntu has sorted this out in the main, but emacs-gtk was ugly. Emacs wizards will not be bothered about the GTK version as they are so productive from the command line but I like having the menus there. Fortunately I found this package.

While I am on the topic of fonts, I must recommend learning LaTeX. If you have ever read a maths or science paper you will recognise the output; beautiful, well structured documents. LaTeX is an extension to TeX, which was created by Donald Knuth as he was unhappy with the quality of maths journals. Checkout AUCTeX and Flyspell (a syntax-aware spellchecker) to more easily create the source files in emacs. For a WYSIWYG tex editor, see TeXmacs. For a WYSIWYM (What you see is what you MEAN) editor, see LyX.

I was looking for a good template to use for a CV, as Jane needs one and I would like to keep mine up to date with things I am currently doing, when I found this advice. I will probably create a LaTeX style using some of the hints there as my current CV was made using some crappy windows software. The site points to quite an interesting article on using type heirachys to show the relative importance of parts of a document, graphic designer types should check out that page as it is pretty interesting.