Chad Perrin: SOB

14 December 2006

fibonacci sequence comparisons

Filed under: Geek — apotheon @ 04:51

I ran across an online attempt to claim that Haskell has something approaching the perfect programming language syntax. It compared the code for a fibonacci sequence generator in a number of different languages, including haskell. From what I’ve seen, the guy doesn’t seem to know much about any of the languages other than Haskell, because some of those fib generators are atrocious examples of code in their respective languages. All of them could be better written than they were.

For instance, this was his example of Perl:


sub fib {
  my ($n, $a, $b) = (shift, 0, 1);
  ($a, $b) = ($b, $a + $b) while $n-- > 0;
  $a;
}

I took the liberty of formatting the code to be a little prettier, and altered the subroutine name. Otherwise, it’s exactly the same.

Here’s an example of how I might write the same thing using recursion:


sub fib {
  my $n = shift;
  return $n if $n < 2;
  return fib($n - 1) + fib($n - 2);
}

That’s pretty much the canonical solution, matching the mathematical definition pretty closely. I’ve heard it said that it’s pretty slow, but running that on the number 20 is pretty much instantaneous when you use the Memoize module to optimize your Perl code:

!/usr/local/bin/perl -l

use strict; use warnings; use Memoize;

memoize('fib');

foreach my $x (0..$ARGV[0]) { print fib($x); }

sub fib { my $n = shift; return $n if $n < 2; return fib($n - 1) + fib($n - 2); }

That gives you the full sequence. If you just want the end number, replace the foreach loop with:


print fib($ARGV[0]);

(The same surrounding code and optimization works for the Haskell guy’s version as well.)

Blaming Perl for your own lack of ability to write code using the language’s commonly accepted best practices is hardly sporting — especially when the syntactic clarity of the Haskell code to which it’s being compared uses recursion, but the Perl example avoids it in favor of lengthy, complex lines of semi-obfuscated code.

14 Comments

  1. i can’t say i see much wrong with the first example. maybe i’ve been using perl for too long. i suppose it could use a comment.

    i hadn’t really thought about it, but i suppose Memoize essentially turns that subroutine into a proper “functional” sub – but optionally, not dogmatically.

    Comment by sosiouxme — 14 December 2006 @ 05:46

  2. There’s nothing “wrong” with it, per se — it’s just ugly and more complex than it needs to be.

    Comment by apotheon — 14 December 2006 @ 06:54

  3. I think you’re misunderstanding the elegance of the given perl example.

    Ordinarily, with double tail recursion, you’re looking at exponential growth of the required memory and processor time to calculate each fibonacci number. With your clever memorize example (I’m guessing that perl saves the result of each function call based on the input number to save processor cycles) you’ve achieved close to O(N) memory growth.

    However the elegance of the haskell programmer’s perl example is because when calculating the fibonacci sequence, you only have to keep track of the previous two integers. His example has a tiny memory footprint, and could quickly give you any specific fibonacci number, until it hits the maximum size of an integer that perl can represent (the 1477th fibonacci number is the first that’s too large on a 32-bit machine, in case you’re curious). For this reason, and because it would take only a minor modification to print the entire list of fibonacci numbers without any significant increase in processor or memory requrements, I’d have to say that you’re suffering from premature optimization.

    Because Python is so darn elegant for this application, here’s a script that uses a generator very similar to the haskell programmer’s example. The great part isn’t so much the code, it’s that Python supports arbitrary precision integers, so it can calculate extremely large fibonacci numbers with full precision. For example, on my 1.1GHz laptop, I calculated the 100,000th fibonacci number, which is 20900 digits long, in an mean average of 3.432 (real) seconds over ten runs.

    #!/usr/bin/env python import sys

    def fib():    a, b, n = 0, 1, int(sys.argv[1])+1    while n > 0:       yield a       a, b, n = b, a+b, n-1

    for x in fib():    pass else:    print x

    If you want to use the same code to print the entire sequence of fibonacci numbers, one per line, delete the “pass” and “else:” lines.

    I compared all three versions for the 1476th fibonacci number (only printing the last, not each), each with 10 runs. Here are the mean averages in real time:

    Your perl: 0.305s My Python: 0.056s Example perl: 0.044s

    This isn’t a completely fair comparison for Python, since it did the calculation in full precision

    130698922376339931803631155380271983098392443907412640726006659460192793070479231740288681087777017721095463154979012276234322246936939647185366706368489362660844147449941348462800922755818969634743348982916424954062744135969865615407276492410653721774590669544801490837649161732095972658064630033793347171632

    compared to the rounded perl number: (1.3069892237634e+308).

    Comment by scoth — 15 December 2006 @ 04:03

  4. Must have been getting tired. This is cleaner in fib()

    a, b, n = 0, 1, int(sys.argv[1]) while n >= 0:

    Comment by scoth — 15 December 2006 @ 04:36

  5. I’d agree with your statements about the Perl examples if the point of the discussion was efficiency of code. Since it was simply prettiness of syntax, on the other hand, what you’ve said is kinda irrelevant to the core point.

    Comment by apotheon — 15 December 2006 @ 01:47

  6. I took the liberty of formatting the code to be a little prettier, and altered the subroutine name. Otherwise, it’s exactly the same.

    But it’s not the same! You sacrificed crucial algorithmic efficiency in the name of syntactic vanity, and though it returns the same values, it can now starve system memory (or at the very least print an error like “Deep recursion on anonymous subroutine at ./perlfib line 16.” for not very large numbers).

    Blaming Perl for your own lack of ability to write code using the language’s commonly accepted best practices is hardly sporting

    Critisizing somone else’s code by comparing it to a pretty, but buggy algorithm is like scoring touchdowns in the wrong endzone. Why not take a look around before you start running? The fibbonaci sequence is frequently an example when analyzing algorithms and the dangers of recursion. Also be aware that what you’re critisizing is listed at several sites as the canonical iterative solution in perl. If you really wanted to be prepared for the big game, why not look at Math::Fibonacci? That algorithm uses a calculation based on the golden ratio, avoiding iteration and recursion altogether!

    Comment by scoth — 16 December 2006 @ 03:04

  7. But it’s not the same! You sacrificed crucial algorithmic efficiency in the name of syntactic vanity, and though it returns the same values, it can now starve system memory (or at the very least print an error like “Deep recursion on anonymous subroutine at ./perlfib line 16.” for not very large numbers).

    That sentence of mine was referring to the slightly prettied-up version of the other guy’s algorithm. That was not a description of the recursive version I added.

    Critisizing somone else’s code by comparing it to a pretty, but buggy algorithm is like scoring touchdowns in the wrong endzone.

    The point was syntactic elegance, not algorithm efficiency. If it was algorithm efficiency, I would not have offered the example I did.

    The fibbonaci sequence is frequently an example when analyzing algorithms and the dangers of recursion.

    In this case, it was an example when comparing how pretty a language’s syntax can be.

    Comment by apotheon — 16 December 2006 @ 04:13

  8. OK, I misunderstood what you said about which version you beautified.

    So where does this article about haskell live?

    As far as pretty fibonacci programs in perl, I like this one from about.com (link in my previous comment).

    perl -Mbigint -le '$a = 1; print $a += $b while print $b += $a

    I also tried my hand at reducing the obfuscation in the iterative version using an array as a FIFO queue.

    sub fib {    my $n = shift;    my @seq = (0, 1);    while ($n-- > 0) {       push @seq, $seq[0]+$seq[1];       shift @seq;    }    $seq[0]; }

    Comment by scoth — 17 December 2006 @ 12:04

  9. So where does this article about haskell live?

    I keep forgetting to link to the thing. It’s at Haskell Hacking.

    As far as pretty fibonacci programs in perl, I like this one from about.com

    Yes, that is pretty. I quite like it, and I like the fact that it makes use of some of Perl’s idomatic syntax in particular.

    I also tried my hand at reducing the obfuscation in the iterative version using an array as a FIFO queue.

    . . . and you did a good job of it. Thanks.

    Comment by apotheon — 17 December 2006 @ 12:23

  10. Wow, that guy is pretty annoying. The inconsistent use of whitespace and indent styles are also clues that he copied the snippets from other places either with distain, or without understanding the syntax. His python example makes me cringe; I don’t understand why he uses so much white space in the if/else block.

    The only change it looks like you made to the iterative perl version is that of changing the indent style from BSD/Allman to K&R. I’m a fan of K&R too.

    After reading his article, it’s also clear that he wasn’t selecting versions through any consistent idea of performance. I believe some languages (like lisp) are optimized for recursion so that even deep tail recursion doesn’t fill up the program stack with function pointers. But it’s just not possible to do double recursion efficiently. The about.com page gives the same version of the haskell code he gives with the warning, “the only point of this exercise is that it looks exactly like the mathematical definition.”

    The more standard version looks nothing like a mathematical definition and isn’t at all intuitively obvious about what it does:

    fibo = 1 : 1 : zipWith (+) fibo (tail fibo)

    It’s an interesting and quite debatable assumption, that languages should be closer to a formal mathematic language. Then mathematicians could write buggy code too.

    Comment by scoth — 17 December 2006 @ 12:05

  11. He does have a point, in that ideally any programming task should be accomplishable using the most efficient syntactic representation possible — without sacrificing the efficiency of the algorithm in terms of system resources. My complaint was simply that he provided examples that were not chosen to represent the most elegant representational forms possible in various syntactic systems, thus showing that a given syntax is “better” than another, but that he just kinda grabbed whatever happened to be lying around, ending up with some “unfairly” ugly representations that don’t actually provide a clear idea of the comparative benefits and detriments of various approaches to defining a language syntax.

    In other words, code that looks more like the mathematical definition would be much prettier and more elegant, and much more intuitive. This would contribute to cleaner, more maintainable code, and greater expressiveness of the language in practice as opposed to merely in theory. In theory, Perl and Haskell can both be used to very effectively, efficiently, expressively, and elegantly (four Es of good code, perhaps?) represent a Fibonacci number generator, but in practice you must take a less intuitive, and more fugly, approach to achieve greater efficiency.

    Because he only addressed how pretty the syntax can be, he’s right insofar as the Haskell simple recursive syntax is pretty, and it would be nice to be able to write code that way without worrying about overrunning the system resources. On the other hand, the way it is presented is kinda broken. Maybe I should take a whack at tackling the same issue.

    Comment by apotheon — 17 December 2006 @ 01:19

  12. In other words, code that looks more like the mathematical definition would be much prettier and more elegant, and much more intuitive.

    Which sounds good, but is a bit simplistic. That’s not to say that it’s not good to strive towards elegant language abstraction or syntax. It just that programming languages are a different type of problem than natural languages (which are overly complex, context dependent and ambiguous) or a formal math language (which is not general-purpose enough and already has too many ugly bits of syntax). There’s a joke that goes something like “if it were possible to have a programming language whose syntax and grammer were a natural languge, the programmers would suddenly have problems speaking”.

    This would contribute to cleaner, more maintainable code, and greater expressiveness of the language

    The goal of cleaner/more maitainable code is usually at odds with greater expressiveness of the language.

    Haskell simple recursive syntax is pretty, and it would be nice to be able to write code that way without worrying about overrunning the system resources. On the other hand, the way it is presented is kinda broken.

    Agreed. To his credit, he didn’t mention the names of any of the other languages, so he wasn’t intending to direct it at any language in particular, but more of a critique of the approach that language designers take towards syntax and grammar.

    Comment by scoth — 17 December 2006 @ 02:29

  13. The goal of cleaner/more maitainable code is usually at odds with greater expressiveness of the language.

    I don’t really think this is the case. Rather, many approaches to a syntax that makes for cleaner and more maintainable code are at odds with greater expressiveness for the language. For instance, languages like Perl are both capable of cleaner and more maintainable code than C and more expressive for most purposes. Similarly, languages like Python are both capable of cleaner and more maintainable code than C++ and more expressive for most purposes.

    Lisp syntax, as originally envisioned (using an M-expression syntax, rather than the S-expression syntax that actually prevailed due in large part to inertia), can be some of the cleanest and most expressive in the world of programming. Some would argue that even the S-expression syntax of languages like Common Lisp (and particularly Scheme) contribute to cleaner and more expressive programming than other languages, despite (or, in some respects, even because of) the ubiquity of parentheses. Maintainability, meanwhile, is comprised of a combination of clean syntax, good programming practice, and transparency of the semantic structure of the language — the latter of which is often easily overcome by familiarity, though that’s no excuse for an obtuse semantic structure.

    When done right, I think expressiveness and clean/maintainable syntax go hand in hand. The problem is that the “done right” part is so elusive.

    Comment by apotheon — 17 December 2006 @ 04:38

  14. […] Over on SOB, apotheon has a couple of posts and some good discussion on Fibonacci sequences in various programming languages. As a combination response to those posts, programming exercise, and lesson in the language – I decided to tackle the problem in Synergy/DE. The download below contains a testing harness and three versions of a Fibonacci number function. […]

    Pingback by Synergy fibs -- Chip’s Tips for Developers — 21 December 2006 @ 05:09

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

All original content Copyright Chad Perrin: Distributed under the terms of the Open Works License