Analysis of programming languages on Rosetta

[Timon Gehr via Digitalmars-d]

On 09/25/2014 12:03 AM, Andrei Alexandrescu wrote:
> On 9/24/14, 2:43 PM, Joakim wrote:
>> On Wednesday, 24 September 2014 at 19:38:37 UTC, bearophile wrote:
>>> Joakim:
>>>
>>>> I wonder why they found Haskell to be so slow, I thought it was
>>>> compiled.
>>>
>>> The first reason for the performance of programs is how much care the
>>> programmer has to write a fast program, secondly how good the chosen
>>> algorithms are, and only then at a third place there are language
>>> implementations.
>>
>> So Haskell programmers don't care about fast programs and don't know how
>> to choose good algorithms? ;)
>
> Sadly that's only half of a joke.
> ...

Some (non-exhaustive!) basic evidence for the other half:

http://book.realworldhaskell.org/read/profiling-and-optimization.html
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

> Google for "Haskell tutorial", you'll get
> http://www.haskell.org/haskellwiki/Tutorials at the top. First "best
> place to start" leads to
> http://www.seas.upenn.edu/~cis194/lectures/01-intro.html. On that page,
> literally the first function defined is:
>
> sumtorial :: Integer -> Integer
> sumtorial 0 = 0
> sumtorial n = n + sumtorial (n-1)
>
> i.e. an linear-space way of doing summation.

sumtorial = foldl' (+) 0 . enumFromTo 0 :: Integer -> Integer

sumtorial n = n*(n+1) `div` 2 :: Integer

The next link, that wasn't considered, is 
http://book.realworldhaskell.org/read/types-and-functions.html which 
does a better job, by defining a function that is actually usable.

> Just a bit below there's:
>
> -- Compute the length of a list of Integers.
> intListLength :: [Integer] -> Integer
> intListLength []     = 0
> intListLength (x:xs) = 1 + intListLength xs
>
> i.e. an linear-space way of computing length. These are functions that
> are computationally bankrupt, we're not talking small constant fish here.
>...

Note that GHC has a history of transforming certain O(1) space 
computations to Ω(N) space computations with certain optimizations 
enabled. The relative overhead will decrease in such cases. :o)

But the other direction is allowed. I.e. it is not actually a given that 
those examples will use linear space. (IIRC they will in practice.)

> Well maybe that's not a very good tutorial. Let's move on to the second
> recommended reading, the famous "Learn You a Haskell for Great Good!"
> Sure that's going to be awesome. The first nontrivial function the
> tutorial ever defines from first principles at
> http://learnyouahaskell.com/syntax-in-functions#pattern-matching is...
>
> factorial :: (Integral a) => a -> a
> factorial 0 = 1
> factorial n = n * factorial (n - 1)
>
> ... again, a gratuitously linear-space function.
>
> Someone should do hard time for this.
> ...

To be fair, a "real" factorial uses Ω(n log n) space anyway.