Wednesday, 7 July 2010

F# vs Mathematica: red-black trees

Mathematica is an expensive commercial application sold as software for "interactive technical computing". In particular, the product centers around the Mathematica programming language which is a very powerful and dynamic language based upon term rewriting with excellent graphical capabilities and a wealth of useful functionality in its standard library. However, Microsoft's new F# programming language not only provides most of the useful functionality found in Mathematica but has many other benefits, not least that it is completely free!

We have previously compared F# and Mathematica in the context of 2D vector graphics. This post is the first in a series comparing these languages. Specifically, this post compares data structures. The F# programming language is designed for efficient compilation to native code whereas the Mathematica language is generally evaluated via term rewriting which is, essentially, a very inefficient form of interpretation. Consequently, F# code is typically 10-1,000× faster than Mathematica code unless computational burden can be shifted onto functions written in other languages (usually those in the vast standard library).

The latest Mathematica-related book, Mathematica Cookbook by Sal Mangano, contains many examples including a translation of Chris Okasaki's immutable red-black trees from Haskell to Mathematica augmented with a function to remove an element from a tree. Unfortunately, the new function written by Sal Mangano is incorrect and silently corrupts the shape of the tree. Thus, we shall focus on the subset of the code presented in Sal's book that is correct. This code may be written as follows in F#:

type color = Red | Black type 'a t = Node of color * 'a * 'a t * 'a t | Leaf let balance = function | Black, z, Node (Red, y, Node (Red, x, a, b), c), d | Black, z, Node (Red, x, a, Node (Red, y, b, c)), d | Black, x, a, Node (Red, z, Node (Red, y, b, c), d) | Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) -> Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d)) | x -> Node x let insert x s = let rec ins = function | Leaf -> Node (Red, x, Leaf, Leaf) | Node (color, y, a, b) as s -> if x < y then balance (color, y, ins a, b) elif x > y then balance (color, y, a, ins b) else s match ins s with | Node (Red, y, a, b) -> Node (Black, y, a, b) | t -> t

The Mathematica code is significantly more complicated (714 vs 1514 bytes) for two main reasons:

  • Mathematica has no types so it cannot express a type with an ordering, so a new rbTree data structure is created with an ordering and that must then be boxed and unboxed by hand.
  • Mathematica prohibits top-level or-patterns so the same pattern is repeated four times in the balance function.

The simpler F# solution is also 20× faster at inserting 100k elements and 100× faster at computing the range of depths in the resulting tree.

In the next post, we'll start to compare the graphical capabilities of the two languages.

4 comments:

fededevita said...

So you're basically saying: the problem can be solved in F# with fewer lines of code, that are more readable and the execution is faster. I guess that's I use F# and not Mathematica? :-)

However, it may be a bit unfair to compare the two: F# is a young technology, born for today's computers and technologies (such as the .Net CLR). Mathematica is an old technology, and when it was new we were all in awe - or am I wrong?

It seems clear to me that there is no reason why I should use Mathematica when I can get use a (way more) versatile language that can be integrated with the other code that I write with no problems whatsoever. Calculation libraries similar to those used by Mathematica are easily available for .Net (and hence for F#), visual stuff like WPF is way more powerful,... Bit of a no-brainer, really.

And another thing: there's hundreds of books on Mathematica. There's very few on F# (four or five?), but they are all very good

Flying Frog Consultancy Ltd. said...

@Federico: I think there are still several places where Mathematica can be slightly better than F# currently is, although most of those can be addressed by libraries without having to change the language itself. There are many more books on Mathematica but they are extremely poor quality. For example, the little decent content in Sal's book was taken from other authors without proper attribution.

@Anonymous: You expect me to do that when Sal did not extend me the same courtesy? If he wants to rebut my criticisms, he can do so on his own blog.

fededevita said...

You just confirm my impressions, then. :-)

On another note, I have no idea who this Sal Mangano is. Apart from closely reminiscing the name of a member of the Sicilian mafia who used to drive the Italian prime minister's children to school in days gone by, I have never heard of the guy.

From what I understand, there seems to be an ongoing argument between the two of you. Sal, if you read this, please bear in mind that arguing with Jon is pretty useless: the probability of him being right is extremely high. This I learned through experience. Sal, take it from a fellow Italian: let it go :-)

Flying Frog Consultancy Ltd. said...

@Federico: Not much of an on-going argument. I once stated that Mathematica is typically orders of magnitude slower than F# code due to the way it is evaluated (term rewriting vs compilation to native code) and Sal took offence. I felt it was interesting to note that Sal has taken to translating code from ML to Mathematica and that his own Mathematica code is orders of magnitude slower than the original ML. Indeed, the only part of this red-black tree implementation that Sal did not copy from someone else, his remove function, is completely wrong. Furthermore, I have since found a much more compelling example about finance taken from Sal's book (p.583).

I agree that Mathematica was awesome in its heyday but millions of people are still using it oblivious to the enormous advances easily available from free alternatives like F#. I still highly recommend Mathematica as an executive toy though.