2012-11-09

What Ada and D taught me about C++

In the last weeks I needed to write some C++ code and immediately had strong dislike for the language. This has surprised me a bit, since I have used C++ for almost 20 years. (My first C++ compiler was Borland Turbo C++ 3.0 for Windows.)

This reaction of mine has been probably triggered by two facts: (1) reading Coders at work revealed that C++ is strongly disliked by many language designers, and (2) in the past two years I have learned many new languages whose features have often made myself thinking, "Oh, this approach is way better than C++'s!"

So I began thinking of any viable alternative to C++ for my "big" projects, i.e., those projects that are going to be more than a few hundreds SLOCs and therefore would take advantage by a statically-typed language, or projects that need to be really fast and therefore need a compiled language.

Two interesting languages that satisfy both requirements are Ada and D. In the next paragraphs I'll show what I learned about C++'s limitations from my study on both Ada and D.

C++ and its compatibility with C

I've realized that perhaps the biggest problem with C++ is Stroustrup's decision of preserving compatibility with C as much as possible. Although this decision probably offers a partial explanation of the success of C++, it has lead programmers to accept without question limitations and strange features that other modern languages do not have.

The C language was invented "between 1969 and 1973", as Wikipedia says. This means that it is of the same age as Wirth's Pascal, and some of its characteristics have already begun to show their age. Let's see a few examples.

Separation between the interface and the implementation of classes

Consider the declaration of this C++ class (file foo.hpp):

// File foo.hpp
#ifndef FOO_HPP_INCLUDED
#define FOO_HPP_INCLUDED

class Foo {
public:
    int value;
    
    Foo(int aValue) : value(aValue) {}
    void doSomethingFancy();
};

#endif

Any code which needs to use the Foo class should include this header fileusing #include "foo.hpp". Unless the implementation of Foo::doSomethingFancy is not only a few lines long, it should go in a separate .cpp file (foo.cpp):

// File foo.cpp
#include "foo.hpp"

void Foo::doSomethingFancy()
{
    // Do something fancy!
}

What is the problem with this approach? Let's reimplement class Foo in Python:

class Foo:
    value = 0

    def __init__(self, val):
        self.value = val
    
    def getValue(self):
        return self.value
    
    def doSomethingFancy(self):
        ... # Do something fancy!

As you can see, in Python, you only need one file, which defines both the interface and the implementation of the class. In C++, you need both the header (interface) and the .cpp file (implementation): in this way, you have to keep the two files continuously updated. Moreover, if you are looking for the implementation of a function, you cannot know if it has been inlined in the .hpp file or if it is in the .cpp file.

The problem is that this #include stuff is done by the preprocessor (the /usr/bin/cpp executable, a C heritage), and the C++ compiler is completely oblivious of any inclusion when it comes to parse the files (in principle). This leads to the well-known fact that if, after having compiled your program, you modify foo.hpp, recompiling all the files that depend on it, then the compiler will not be aware of this and strange things will happen. You must circumvent this by relying on other software (see the section of the GNU Make about automatic prerequisites).

Of course, this example is not completely fair as Python is interpreted while C++ is compiled. But consider that the guys that designed D (again, a compiled language) were able to devise a module mechanism that is similar to Python — at the expense of breaking compatibility with C/C++, of course. Here is file foo.d:

// Written in the D language

class Foo {
public:
    int value;
    this(int aValue) { value = aValue; }
    void doSomethingFancy()
    {
        // Do something fancy!
    }
}

To use this class in a program, put import foo; at the beginning of your source code. If the test program is testfoo.d, you can build the program using the command dmd -o testfoo testfoo.d foo.d. This is much like C++, where you would write cc -o testfoo testfoo.cpp foo.cpp, but in this case you do not need any header file at all! (Even if D allows for .di files that are similar to C++ header files, their usage is limited, as explained in this forum post: - also, .di files can be automatically generated by the compiler).

What is the situation with Ada? Its approach is somewhere in the middle between C++ and D: modules (in Ada terminology, packages) are split in two files, one (with extension .ads) providing the interface, the other one (with extension .adb) providing the implementation. But, unlike C++, Ada compilers are able to automatically decide which packages are up-to-date and which ones need to be rebuilt, without resorting to any GNU Make magic. (This feature was present in Borland Turbo Pascal's units as well: this is one of the reasons why I am still in love with Pascal.) Moreover, GNAT includes a handy tool, gnatstub, which automatically generates an .adb file from a .ads file (this is the contrary of what D does with .di files, but it fits the way programs are usually developed in Ada — first the interface, then the implementation.)

Multiple declaration of variables

In section 4.9.2 of the C++ programming language (third edition), Stroustrup warns the reader of a potentially confusing way of declaring variables. Consider this example (taken from Stroustrup's):

int* p, y;  // int* p; int y;

It can be potentially confusing, because it it not clear if y is a pointer to int like p or not. Stroustrup says that such constructs should be avoided. But then, one might ask, why are they accepted by the C++ standard? The answer is simple: to preserve compatibility with C.

On the other hand, both D and Ada forbid such constructs.

Implicit conversion between 0 and NULL

A particularly nasty problem with C++ is the use of NULL. Consider what happens if you want to initialize a string to "false", but forget the double quotes:

#include <iostream>
#include <string>

int main(void)
{
    std::string s = false; // What the programmer meant is "false";
    std::cout << s << std::endl;
    return 0;
}

(this is a real example, see this thread on StackOverflow.)

Compiling the program using g++ 4.4.6 does not produce any warning, yet the program crashes:

$ g++ -o stringtest stringtest.cpp
$ ./stringtest
terminate called after throwing an instance of 'std::logic_error'
  what():  basic_string::_S_construct NULL not valid
Aborted (core dumped)

(Note however that g++ 4.7.2 correctly produces the following warning: "warning: converting ‘false’ to pointer type for argument 1 of ‘std::basic_string<_CharT, _Traits, Alloc>::basic_string(constCharT*, const _Alloc&) [with _CharT = char; _Traits = std::char_traits; _Alloc = std::allocator]’ [-Wconversion-null]". Although it suffers from the usual GCC's verbosity, at least the compiler is now able to spot the problem.)

The problem is, the std::string type is not native in C++ but provided by a library. The only string-like type accepted by the raw C++ language is a null-terminated array of ASCII characters. Therefore, std::string is able to automatically convert char * into std::string. The problem is, false is equivalent to 0, which is in turns equivalent to NULL, i.e., a char * pointer. But std::string cannot be initialized to NULL, hence the std::logic_error exception.

Since D has native string types, this kind of errors is less likely to occur. Consider a straightforward translation of the C++ code above into D:

import std.stdio;

void main()
{
    string s = false;
    writeln(s);
}

Compiling it using DMD 2.060 will produce the following error message:

$ dmd stringtest.d
stringtest.d(5): Error: cannot implicitly convert expression (false) of type bool to string

Regarding Ada, this kind of error is impossible as the language avoids almost every implicit typecast. This can be annoying sometimes, but it makes me feel confident of what I'm writing. (It is often said that if your Ada program compiles without errors, then it is probably correct.)

2012-09-07

Discovering Ada

After almost one year since my last post, I am going to write something more regarding "exotic" languages. During the last year I was able to investigate the caracteristics of a well-known, underused language: Ada.

I was interested in it because I found two references to it in the realm of astrophysics: the first one is a spectral line synthesis code for magnetic stellar atmospheres, the second one is a list of satellites which are using software (partly) written in Ada. Also, I always heard of how Ada's typesistem is exceptionally safe and was truly interested in giving it a try.

So here is a list of features of Ada that caught my attention:

  • It is a statically typed language (like C/C++/Fortran/Haskell, unlike Python/Ruby/Scheme). However, unlike C and (to a lesser degree) C++, its type system is strong. This means that the compiler enforces type correctness and will not silently convert e.g. floats to integers.
  • Ada code looks verbose, but very readable. (As I understand, this was one of the driving requirements in the development of the language.)
  • It has a number of interesting features over C and C++, like keyword arguments (called named parameters), nested functions, and some primitive type-inference (e.g. you do not have to declare the type of a variable used in a for loop).
  • It allows code to be split into packages (more on this later).
  • Ada's versatile typesystem allows the programmer to make the compiler doing dimensionality checks. So, e.g., it will signal an inconsistency for code like if obj_speed < field_size, if obj_speed and field_size have been properly declared. Apparently, this feature was considerably extended with the latest version of the language (Ada 2012).
  • It has native support for multitasking. (As far as I know, Ada, Erlang and Go are the only non-academic languages that were designed from the ground up with this capability.)
  • Ada is compiled to machine code: the reference open-source implementation is GNAT, which is part of GCC (GNU compiler collection).
  • Being a tightly integrated component of GCC, it is extremely easy to develop bindings to C/C++ libraries (there is even a tool to do this automatically).
  • Interestingly enough, GNAT is developed by AdaCore, a commercial company which seems to have a quite large user base. It develops both the open-source compiler and a commercial version.

Is Ada outdated?

Before digging into Ada, I had the idea that it was an outdated language with virtually no users today. But I was wrong on both fronts:

  • Ada was born more or less in the same years as C++: work on Ada began in 1976, while Stroustrup's "C with classes" toy language dates back to 1979.
  • There are a lot of Ada users. Only, Ada programmers do not seem to work in the contexts I'm used to.

Is Ada verbose?

I do not like verbosity in general. I have always been amazed by the coinciseness of languages like Haskell: in my opinion, the shorter a program is, the quicker you're able to find problems in it. And, undoubtedly, Ada is quite verbose. A lot of grammar constructs are not strictly necessary for the compiler to understand what the code should do: e.g. the is at the end of procedure/function declaration.

However, I must admit that I've found more than once some source code that was so condensed that it is difficult to understand how it worked &edash; or why it was not working. Readability is probably as important as coinciseness. Ada's designers put a lot of effort in making the language easy to read, even to people that have never learned Ada.

Types, types and types

Ada's strongest advantage is probably its versatile typesystem. You can define "subtypes" which optimally limit the range of values of a primitive type (e.g. an integer which can hold values between 18 and 28): Ada will automatically add bounds checking code. (If you do not limit the range, your subtype works like typedefs in C.)

However, the most interesting feature is the ability to define new types from primitives. In this case you are not allowed to mix the new type with its primitive, unless you explicitly tell to compiler to allow you. So, you can e.g. create three new types distance, time, and speed from the primitive type float: you will not be allowed to combine (e.g. add/multiply) variables of different type, unless you manually override compiler's checks or redefine operators (like C++). This allows to check for measure unit's consistency in the code. (Such a feature is possible in C++, at the expense however of writing a lot of bolierplate code: basically, you have to define a class which wraps a float and implement manually every operation you need on them; on the contrary, Ada already knows how to sum two distance variables, as they behave the same as floats.)

Packages

I am not happy about how C/C++ programs are split into multiple files. You usually separate the classes and functions in different .cpp files, and in each of them you include a .h file which provide the class/function definition. However, the compiler is unaware of the difference between .h and .cpp files: the difference is relevant only to the C preprocessor.

Compare this with Ada packages. You have to write two files, as in C++: one with extension .ads (the specification file, analogous to .h files) and .adb (the implementation file, analogous to .cpp files). However, the Ada language allows you to specify what of the package has to be exported and what is meant to be private. This is similar to the concept of private/public methods in C++ classes, but it works at file level. It is much similar to units in Turbo Pascal, and it is much more effective. (Also, it allows the GNAT compiler to recompile outdated dependencies without the need of a Makefile.)

So, how fast is it?

I was particularly ingrigued by the fact that the GNAT Ada compiler is integrated into GCC. This allows Ada code to be optimized by the same machinery GCC employs for C/C++/Fortran/ObjC code, and it can in principle guarantee the same performance. I was however puzzled by the results of the Computer Language Benchmarks Game, which clearly showed that on average C++ code required less memory and in some cases much less time to run (here is the GNAT/g++ comparison, and here the GNAT/gcc comparison, which is even worse for GNAT).

So I investigated a bit why this difference. I picked the k-nucleotide example, for which the fastest C code is available at this link. I found that, even if Ada is considerably slower than C, it still ranks third. In my opinion, this indicates that the C program has been dramatically optimized, not that Ada is inefficient per se.

As a side note, I found that C/C++ programs in the Shootout are sometimes so optimized that it is difficult to understand what they are doing: look at this implementation of mandelbrot, expecially the function calcrow: do you now what __builtin_ia32_cmplepd and __builtin_ia32_movmskpd are supposed to do without reading the comments? Given the large number of C/C++ programmers, I bet that it's easier to find a relatively large subset which is good in low-level optimizations and assembly coding: this might explain why C/C++ Shootout programs often perform better than Fortran and Ada.

2011-10-14

Floating-point reference parameters in C++

Today I had some time to verify an idea I have always had: in C++ it is better to avoid unnecessary references when passing double arguments to functions.

The idea to verify this came while I was inspecting some C++ code. One of the functions had a parameter which was declared as double & despite the fact that such parameter was never changed in the function body. Consider this example:

The problem with the double & lies in the fact that the function receives a pointer to double instead of a double: therefore it has to look for the value pointed by the argument and copy it into a floating-point register:

Had we defined doubleThis with a double parameter (without the & indicating a reference) like this:

then GCC would have produced the following assembly code:

which is shorter and faster.

In short: avoid using unnecessary references. Apart from the fact that they obfuscate the meaning of the function (a reference parameter indicates that the function is going to alter its contents, while this is not true for doubleThis), depending on the type of the parameter they might also produce slower code.

2011-09-28

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.

2011-04-01

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!

2011-02-22

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).

2010-12-20

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:

NameVersionLanguageTiming
Ikarus0.4 RC1Scheme14
Larceny0.97Scheme15
Bigloo3.5aScheme16
Steel Bank CL1.0.44Common LISP17
MZScheme (DrRacket)5.0.1Scheme17
STklos1.0Scheme43
CMU CL20bCommon LISP47
Clozure CL1.5Common LISP62
Chicken4.6.3Scheme93
Chicken4.4.0Scheme102
CLISP2.49Common LISP106
CPython (fast)2.6.6Python135
CPython2.6.6Python145
ECL10.4.1Common LISP169

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.