Playing with OCaml and Haskell (Problem 34 again!)

In the past months I had the chance to have a deeper look at Haskell and Erlang (in a previous post about functional languages I dismissed them quickly). I have realized that Erlang is the best language when you need to run thousands of lightweight processes (e.g. serving web requests) but has little to offer to scientists. On the other side, Haskell has a lot of potential, as I found by porting my solution of Project Euler’s problem 34.

Let’s first recall my original purpose. I wanted to test how faster Scheme/LISP/Clojure were than Python (at the time my language of choice for quick development). I implemented a number of programs which solved problem 34 (finding the sum of all the numbers which are equal to the sum of the factorials of their digits, like 145 = 1! + 4! + 5!) and measured their performance. I found with great amazement that in some cases LISP-like languages were one order of magnitude faster than Python (14 seconds instead of 140).

This summer I decided to do the same test with OCaml and the Glasgow Haskell Compiler (GHC). First, here is my OCaml program:

The fast_fact variable is an array of 10 elements containing the factorials of all the digits. (Note that this implementation differs slightly from my LISP solutions, where I used a dictionary.) The digits function returns a list of the digits in a number. Unlike my LISP programs (where I converted the number into a string and then converted its characters back to numbers), here I chose to extract the digits by using a division by 10 in a loop: this should be faster, as I do no longer need to allocate space for a string. The test_number function determines if num satisfies the requirement of problem 34. The -- function returns a list containing the numbers from i to j.

OCaml programs can be run either using the interpreter or compiled using the optimizing compiler. I chose the latter and timed the running time of the executable using the Unix time program. On my computer the program takes roughly 3 seconds to execute, which makes it roughly 4 times faster than the fastest LISP solution I wrote (a Scheme program compiled with the now-discontinued Ikarus Scheme).

By navigating in the Project Euler’s website I found that one of the other users (“ix”) posted a Haskell solution that is incredibly compact:

I was struck in amazement by the compactness of the code. But the greatest surprise came when I used GHC to compile it and measured the running time: less than 0.2 seconds! These two lines of code are 4 orders of magnitude faster than my 24 lines of Python code. Four. Orders. Of. Magnitude. That is unbelievable. And note that the code does not pre-calculate the factorials for each digit (as I did in the OCaml program, see the definition of fast_fact).

The fact that the Haskell solution is one order of magnitude faster than OCaml is probably due to the use of -- in problem34.ml: this means that OCaml needs to build a list containing all the numbers from 10 to 10,000,000 before applying test_number. It is possible to overcome this limitation by building an explicit cycle, but I wanted something as much compact as possible. (The code would have been more compact had OCaml provided something like the Haskell syntax .. instead of making me define the -- operator.) On the contrary Haskell, thanks to its lazyness, never builds the list [10..10000000] in memory. (If you know Python, it is like if OCaml were using range while Haskell used xrange.)

Considering that debugging one line of (Haskell) code is considerably easier than debugging 24 lines of (Python) code, I think I shall use Haskell more and more in my next mathematical/scientific projects.

P.S.: This time I used markdown instead of Org-mode to write this post. It produces less bloated HTML and it seems to be enough for posts of this kind. I also used gist to include syntax-highlighted snippets of code, which is much better than the code produced by Org-mode.

Imperative vs. functional: the conditional construct

Slowly I am acquiring some experience with functional paradigms. In this post I shall do a comparison of how a common construct like if is handled in imperative and functional programming languages. This stuff is probably well-known to any expert in computer languages, but for me this has been an interesting discovery!

Let's start by explaining roughly what are the differences between ``imperative programming'' and ``functional programming''. In the first case you put together a set of instructions, which must be executed in some well-defined order and alter locations of memory to accomplish some task. In the second case you build a set of ``functions'' whose purpose is to take some input and produce some output, without altering the state of the machine (more or less).

The most part of modern languages incorporate some elements of iterative programming and others of functional programming: of course, each language has its own preference regarding how to do things. For instance, C, Pascal, Python, Ruby and so on are more imperative, while OCaml, Haskell, Scheme are more functional (although they support imperative constructs). Even GNU R, a language for doing data analysis, has some important functional characteristics, as we shall see.

Conditional constructs

In order to explain the difference between functional and iterative programming, I shall concentrate on how you specify a conditional expression using different languages. My example is extremely practical, and it deals with the way Planck/LFI radiometers are labeled. LFI has 22 radiometers but only 11 antennas: the radiation entering each antenna is split into two polarised components and each of them enters a separate radiometer, called either ``main'' or ``side'' and labeled with M or S. To indicate a radiometer, one append the number of the antenna to the string LFI, then it appends either M or S, depending on the radiometer. So for instance the ``main'' radiometer fed by the twentieth antenna is LFI20M.

Of course, since it is much easier to deal with numbers than with letters (e.g. to implement cycles), many codes used within the Planck/LFI collaboration internally use 0 and 1 to represent the main and side radiometers. A very common task is therefore to build the name of the radiometer given two integer variables horn and rad (the number of the antenna and of the radiometer, the latter being either 0 or 1). Let's see how we can implement this in Python:

if rad == 0:
    rad_letter = 'M'
else:
    rad_letter = 'S'

name = "LFI%d%s" % (horn, rad_letter)

This is a rather naive approach employing the if conditional statement. We can reduce the number of lines by throwing away the else part:

rad_letter = 'M'
if rad == 1:
    rad_letter = 'S'

name = "LFI%d%s" % (horn, rad_letter)

The best solution is however to forget about the if and use a dictionary:

rad_letter = { 0: 'M', 1: 'S' }
name = "LFI%d%s" % (horn, rad_letter[rad])

This is the shorter solution, but likes the ones above it forces us to define a new variable, rad_letter. It is not elegant if we are going to use it in the following line only.

Other imperative languages do not allow many alternatives: they usually require the very same code seen above. Here is e.g. the solution in Pascal (another imperative language which does not support dictionaries natively):

if rad = 0 then
    rad_letter := 'M'
else
    rad_letter := 'S';

name := 'LFI' + str(horn) + rad_letter

What offer functional languages in this context? Well, for any functional language every statement is an expression and can be therefore composed with other expressions. So the above example in Scheme would be rewritten in this way:

(string-append "LFI" (number->string horn) (if (= rad 0) "M" "S"))

A very similar expression can be coded using Haskell:

"LFI" ++ (show horn) ++ (if rad == 0 then "M" else "S")

(the ++ function concatenates strings.) Note that in both cases we do not need to define an ancillary variable: everything can be put in one line.

Conceptually, the Scheme/Haskell solution would be the same as the following pseudo-Python code:

name = 'LFI' + str(horn) + (if rad == 0: 'M' else 'S')

with the difference that this is not accepted by Python: it will generate a ``bad syntax'' error. Note that GNU R has no problems in accepting this construct:

name <- paste("LFI", horn, if(rad == 0) "M" else "S", sep = "")

(the paste command joins strings): this suggests that GNU R is more functional than Python.

You might have noticed that I left C outside of this discussion. Well, it turns out that C/C++ do not allow to include an if within an expression, but it has a useful shorthand, the ``question-mark operator'':

sprintf(name, "LFI%d%c", horn, rad == 0 ? 'M' : 'S');

The syntax of this operator is: cond ? iftrue : iffalse. Note however that this is not really the if operator, but something else that behaves exactly like it. (And it is a second-class operator, as you cannot use it with C++ strings.) Moreover, the generalisation of the if statement is the switch statement (where the decision is not based on a true/false value, but on arbitrary values): and the latter cannot be used in a C expression. On the other side, the analogue of switch in Scheme (cond), Haskell (case) or OCaml (match) can be used in expressions exactly like if.

This post has shown that even in simple cases functional constructs can lead to shorter code. To see some striking example, be sure to have a look at the site Bonsai code. Its author, Remco Niemeijer, posts the shortest possible Haskell program which solves each problem posted in Programming praxis. Sometimes I am astonished how short the Haskell solution is!

Experiments with Racket

In the last weeks I have played with Racket (formerly PLT Scheme), a powerful language derived from Scheme. Here I describe a couple of problems I solved using Racket, in order to underline the difference between this language and Python.

First, let me say that I am really impressed by the quality of the implementation of Racket. It is fast (apart from the execution times for the GUI), it has a huge set of libraries, it is easy to use and it has a number of nice facilities.

Project Euler again!

The first script I wrote was to solve one of the easiest problems proposed in the Project Euler site, that is problem 15. This kind of problem can be solved using a divide-and-conquer algorithm, so here comes my first attempt:

(define (num-of-solutions width height)
  (+ (if (> width 1)
         (num-of-solutions (sub1 width) height)
         1)
     (if (> height 1)
         (num-of-solutions width (sub1 height))
         1)))

Such solution relies on the fact that at any point in the grid one can only move left or down (provided that there is room to move in that direction), and that once you make a move you are trying to solve the same problem for a rectangular grid with a smaller size.

This solution however has a problem: when running num-of-solutions on a 20x20 grid, the function takes forever to evaluate. The problem lies in the fact that each non-trivial call to num-of-solutions spawns two recursive calls to itself, so that the number of calls grows quickly.

There is a simple solution: since many of the calls share the same parameters (and hence return the same number), we can use a technique called memoization: when calling num-of-solutions with some parameters for width and height, save the return value in a table so that subsequent calls to the function with the same parameter will simply look up the table instead of re-running the function. (See SICP for an example applied to the calculation of Fibonacci's numbers, a problem stunningly similar to the one we are solving here.)

In order to memoize num-of-solution I might have relied on standard techniques available for the Scheme language, but I instead had a look in the excellent Racket documentation and in PLaneT (the collection of separate packages available for Racket). In a few seconds I found the memoize package, which does exactly what I wanted: just changing define into define/memo will make num-of-solution orders of magnitude faster:

(require (planet dherman/memoize:3:1))

(define/memo (num-of-solutions width height)
  (+ (if (> width 1)
         (num-of-solutions (sub1 width) height)
         1)
     (if (> height 1)
         (num-of-solutions width (sub1 height))
         1)))

(num-of-solutions 20 20)

And here comes a nice touch. I did not know how to install this additional package in Racket, so I wrote the example above in the IDE and compiled it, hoping that any error message would help me to understand what to do. Guess what? The IDE automatically connected to PLanetT, downloaded and installed the package and continued the execution: in a few seconds I had the answer! (Compare this with Python: it is like if any time you import some library not available the interpreter downloads and installs it automatically. How nice!)

A more complex example

The second program I wrote was considerably longer. I had a problem with a TWiki site I am administering: every user would attach huge PDF files to wiki pages instead of properly using a separate site (I shall not bother you with details about how this site works: let just assume it is a FTP site). This caused any backup of the TWiki site to be quite huge, so I decided to fix this by manually moving the biggest PDF files to the FTP site and then change each link to the new place. As there are potentially thousands of links to fix, this clearly required an automated solution. And here comes Racket.

My plan was to download each page containing huge attachments in a text file, search for the TWiki markup signalling a link to any file already moved to the FTP site and modify the link properly. The caveats for such task are:

1. I am not going to move all the files, just the biggest ones. So the program should be smart enough to decide which links to change and which not.
2. So far I have considered the remote site as a FTP site, but this is not really the case. Specifically, to get a file from there the URL must contain the file name and a unique integer ID. So links to this site cannot be created automatically, they must be specified one by one. An example might be http:/foo/bar/filename.pdf?node=1234. Thankfully the file name is always present!

The program I created relies heavily on Racket's regular expressions, an addition of Racket over the Scheme language (note that regexps are native in Racket – like Ruby but unlike Python, which requires you to use import re at the beginning of your script). It takes two input files: the first one contains the wiki page, the second one contains a list of links to the remote site. The code extracts bare file names from the links and produces an associative list (similar to dictionaries in Python), which then uses to fix links in the wiki page.

The most difficult thing for me was to think how to implement iterations using recursion instead of for loops (and such code has a lot of iterations: looping over links, looping over markups…): however, I am willing to master this technique as the use of recursion is common in functional languages.

So far the code has worked like a charm. I have not benchmarked it, but it works so fast that execution times are negligible (of course I created a compiled executable in order not to start Racket every time I need to use it).

The Scheme of things/2

In one of my previous posts I compared Clojure with Python by implementing two identical versions of a program to solve problem 34 from Project Euler in both languages. My results showed that Clojure was able to be three times faster than Python when type hinting (TH) was enabled (even without TH Clojure was however faster than Python). My idea was then that any type-hinted (semi-)interpreted language like Clojure would have reached the same speed.

In the last month I have run some other tests, and I must say that my idea has changed. A number of Scheme/Common LISP implementation have proven to be even faster than Clojure, and this without type hints!

I am not going to provide my Common LISP and Scheme programs, as they are trivial conversions of the Clojure program I presented before. These are the compilers/interpreters I used to write and run my test programs:

Name	Version	Language	Timing
Ikarus	0.4 RC1	Scheme	14
Larceny	0.97	Scheme	15
Bigloo	3.5a	Scheme	16
Steel Bank CL	1.0.44	Common LISP	17
MZScheme (DrRacket)	5.0.1	Scheme	17
STklos	1.0	Scheme	43
CMU CL	20b	Common LISP	47
Clozure CL	1.5	Common LISP	62
Chicken	4.6.3	Scheme	93
Chicken	4.4.0	Scheme	102
CLISP	2.49	Common LISP	106
CPython (fast)	2.6.6	Python	135
CPython	2.6.6	Python	145
ECL	10.4.1	Common LISP	169

The "CPython (fast)" entry is a rewrite of my original Python program so that the body of solution does not call other Python functions:

sum ([num for num in xrange (10, max_n)
      if num == sum ([FAST_FACT[digit]
                      for digit in [int(x)
                                    for x in list (str (num))]])])

A few notes about these results:

• There is more than one order of magnitude between the slowest implementation (ECL) and the fastest (Ikarus Scheme);
• Compilers without TH (e.g. Ikarus, Larceny, Bigloo, SBCL) run much faster than Clojure with TH. I was really surprised!
• Avoiding function calls make CPython faster, but not much faster;
• The fastest program runs using Ikarus, a compiler in alpha stage that has been put on hiatus after the author (apparently) changed his job. What a pity! (Note however that Marco Maggi has forked Ikarus into Vicare, which seems to be actively developed.)
• While I had to change my Scheme program in order to make it runnable under various Scheme compilers/interpreters (nothing sensational, just one or two lines at the beginning), my Common LISP program ran unchanged under SBCL, ECL and CCL. One point for portability to Common LISP!

Here is a barchart of the results (click to zoom):

Update: After a suggestion by Water I included in my benchmarks also CLISP (and corrected the name) and CMU Lisp (which was mentioned in one of the pages at CLISP's site as being faster than CLISP – and indeed it is). In both cases I first compiled the program and then timed the execution of the bytecode. I have also added MZScheme, which I left out in the first version of this post. The table and the chart have been updated accordingly.

The Scheme of Things/1

In one of my previous posts I anticipated that I was going to study some functional programming languages in order to better understand how to write parallel programs for multi-core and multi-CPU architectures. During my (very slow!) quest I re-discovered a old language I used to be quite fond of: Scheme, a LISP-like language which dates back to the 1970s. In this post and the following I shall provide some information about my relationship with this wonderful small language, as well as some insights about how it might be useful for scientific computations.

Music Typesetting and Scheme

My first experience with Scheme dates back to about ten years ago. I am a passionate music lover, and I was looking for a good program to typeset music. I found the marvellous GNU Lilypond, which was well-suited for what I wanted to do at the time. I contributed a lot of pieces to the Mutopia project (mostly scores by Mozart and other classical composers, see e.g. Mozart's String Quartets from Op. 10), and at the same time I became quite good in extending Lilypond using its scripting language. Guess which language it was? Of course Scheme! Lilypond used GNU Guile, a Scheme interpreter sponsored by the Free Software Foundation (yes, the guys behind Gnu Emacs and GCC). The intention of the Guile coders was to develop an interpreter that could be used by other projects to provide a "plugin" language usable for extending large applications. (Unfortunately, the project did not suceed in gaining enough popularity and it has developed at a quite slow pace: just have a look at these dates and version numbers.)

Partial Differential Equations and Scheme

During 2001-2002 I worked on my master thesis. The main objective of the work was to study the solution of the heat equation given some well-defined boundary conditions, in order to better understand some properties of the reference loads of the Planck/LFI instrument. One of the tools I developed for my study was a small C program which used the Crank-Nicholson implicit method to solve the one-dimensional heat equation numerically.

Since the objective of the program was to simulate how the temperature of a body changes with time, the output was a quite large set of numbers: for each time step, there were tens of temperatures (sampled on a regular grid) that the program printed. According to the type of analysis I was doing, I had to throw away irrelevent temperatures and keep the ones I was interested: at the beginning I was using GNU Awk for the job, but this was not the optimal solution. At some time I realized that what I needed was some way to attach "plugins" to my program: each plugin would have been a small program which would have driven the program and instructed it to print only the information needed by the ongoing analysis.

This of course called for an embedded interpreter. At the time the one I knew best was of course Guile (see above), so I decided to implement Guile bindings in my program. All worked like a charm: once the C program was properly debugged and produce reasonable results, I could start writing Scheme snippets to perform every analysis I wanted and attach them to the program without the need to recompile it. It was like a dream! (Actually, one of the appendices of my thesis contains the source code for some of those Scheme plugins.)

Thermal Modeling and Scheme

After having defended my thesis, I continued studying the thermal performances of Planck. We used a number of closed-source thermal modeling tools based on Fortran 77 for doing the most complex analysis. Such tools required the user to create huge text files (called model files) containing details about how the object under study was to be discretized and what were its characteristics (e.g. density, specific heat…) at each point. Such files were interwoven with Fortran 77 code which calculated and extracted the information required for the analysis (much like Scheme plugins did for my program).

Managing such files was a pain, so I created a couple of programs to help me in the task. The first program, Thermal Scheme, looked for a specific signature in the contents of model files: every text between #{ and #} was interpreted as Scheme code, which was run and its result replaced the Scheme code in the model file. Therefore, giving a text file like

Hello #{(display "world")#}!

Thermal Scheme would translate it into

Hello world!

Of course, Thermal Scheme provided a number of Scheme functions to easily define and discretize complex structures.

Thermal Scheme was able to act like a "data provider": when some command-line flag was used, the program recorded every Scheme definition and built a text file containing a 3-D representation of the object. A companion program, Thermal Viewer, was able to connect to "Thermal Scheme", get this text file and create an interactive 3-D view of the object using OpenGL.

Things Go Awry!

After a few months working with Thermal Scheme, I was supposed to move to the Rutherford Appleton Laboratory (Oxford, UK) to continue working on Planck thermal analyses. I even arranged a demo of the capabilities of Thermal Scheme! But then in Spring 2003 the Italian Government obliged me to do ten months of civilian service, so I was forced to decline that job offer. Ten months after (May 2004) my duties were over and I got a temporary position at the National Institute of Astrophysics, where my first duty was to build a medium-sized software tool for Planck/LFI using RSI IDL (a Fortran-like language for data analysis). So I started studying IDL and completely forgot about Scheme… till a few weeks ago!

In one of my next posts I shall tell you how Scheme evolved in the meantimes, and what I discovered about the performances of some of the currently developed Scheme interpreters/compilers. Stay tuned!

Authenticating NIS users with PAM - Quirks

Last friday I had a large headache in trying to understand why the account of my friend Simona was not allowing her to authenticate on the computers of our institute. The rule here is to manage all the authentications using a NIS server, and keeping the home directories distributed among a number of servers. It seemed that Simona was not able to authenticate from any of the computers used by our team, but the sysadmin had no clues why this was happening.

The error messages written by our Debian machine (in /var/log/auth.log) clearly indicated that the computer was able to recognize Simona as one of its users, but it did not accepted her password. To understand why this was happening, I had to browse the documentation (and the source code!) of PAM. A really interesting read, but this did not explain why every user (including myself) but Simona was able to authenticate.

After hours of fruitless attempts, I realized there was something wrong when I used ypmatch passwd to compare Simona's key in the NIS map with mine: her encrypted password was much longer than mine. This hinted the nature of the problem: a mismatch in the authentication mechanism.

Remote authentication works by encripting password attempts and comparing them with the encripted password memorized by the server. (The comparison is not done on the passwords directly as they need to travel through the web, making this process insecure.) Of course, for the comparison to be effective the encription algorithm must be the same between the attempt and the password stored in the server!

Some time ago the sysadmin upgraded the operating system of the NIS server, and this apparently changed the default encription algorithm for new users to be Blowfish instead of MD5. (Note that old users like me kept the old MD5 encrypted password.) But our computers (running Debian Lenny 5.0) implemented the plain PAM module, which is only able to use MD5. Therefore, the comparison was made between the MD5-encrypted password entered by Simona (and encripted by our computer) and the Blowfish-encrypted password stored in the NIS server: this obviously failed! This also explained why I was still able to authenticate even after the sysadmin's upgrade.

The solution was to install the Debian package libpam_unix2, which provides a PAM module which recognizes both MD5 and Blowfish, and replace every occurrency of pam_unix.so with pam_unix2.so in the PAM configuration files (in /etc/pam.d/common-*). Phew!

Clojure and FP - First impressions

This blog entry is to report my achievements with Clojure and Functional Programming (see my previous post).

What I do not like

The first thing that one faces when trying to use Clojure is the difficulty in installing it. The downloads page only lists a few zip files, without saying anything about how to use them. (Sure, there is a Readme file, but I would have like to know something more before downloading anything.) In comparison, the Downloads page of Scala is much better in shape, and a number of pre-built packages are provided. Moreover, Scala is included in Macports, while Clojure is not. Once the ZIP file has been uncompressed, the Readme file is extremely laconic: it just reports the command required to run/build Clojure. Since the REPL has no editing facilities (i.e. you cannot use Backspace/delete to modify what you have written, and there is no history), I would have expected some reference to jLine or rlwrap as these can really save you the day.

In general, Clojure shows its young age in a number of other spots. The documentation is quite sparse, and you often have to look at the source code of some function in order to understand its behavior. Many tools I regularly use for source code (e.g. Vim, Source-highlight and others) do not have native support for Clojure (although you can usually find something in the Web - I find VimClojure one of the best Vim plugins I have ever seen, the "rainbow parentheses" mode is incredibly useful!).

What I like

Being a LISP dialect, Clojure can be extremely elegant. Here is some code I wrote to solve problem 34 from Project Euler.

A few things worth to note:

• Clojure implements a large number of high-level data structures, like dictionaries. I used the latters in fast-fact, a dictionary whose keys are the 10 digits and whose values are the corresponding factorials.
• It is really easy to call Java functions like toString: just prepend them with a dot. No need to import modules to do this!
• Although Clojure is a dynamically typed language (like e.g. Python), it allows to specify the type of the input parameters for functions and let bindings. I have verified that this allows to dramatically increase the speed of the code (3x or 4x times).
• Like Python, Clojure allows to use docstrings. They can be accessed from the REPL through the doc function.

Python vs. Clojure

Since I am an avid Python user, I immediately rewrote the program in Python:

I tried to follow the same logic used in the Clojure program, i.e. using a dictionary for the first 10 factorials and getting the list of digits for a number by first converting it to a string (an alternative would be to repeatedly apply division and modulus 10). Then, using the Clojure time function and the IPython %time command, I was able to record the times used by each program. In order to get sounder values, I repeated each measurement till the timing did not change significatively any more.

Results are shown in the plot on the right. They look quite impressive: as shown by the following graph, type hints allow Clojure to be more than three times faster than Python. Even not using type hints would have allowed Clojure to be approximately 20% faster than Python.

Preliminary conclusions

Despite its young age and a few rough edges, my overall impression is extremely positive: Clojure is really nice to use and the number of features it provides are extremely interesting. Its speed is also remarkable.