Software Assurance Reference Dataset

[Timon Gehr via Digitalmars-d]

On 07/22/2014 08:34 PM, Walter Bright wrote:
> On 7/20/2014 8:15 PM, Timon Gehr wrote:
>> So does Haskell.
>>
>> import Control.Monad
>> import Control.Monad.ST
>> import Data.STRef
>>
>> factorial :: Integer -> Integer
>> factorial n = runST $ do
>>    r <- newSTRef 1
>>    forM_ [1..n] $ \i->
>>      modifySTRef r (*i)
>>    readSTRef r
>
> Would you rather write that or:
>
>    int factorial(int i) pure {
>      auto r = 1;
>      foreach (i; 1..n + 1)
>      r *= i;
>      return r;
>    }
> ...

If I fix the typo, this computes the same numbers for inputs int.min up 
to and including 12.

> And I'd love to see what native code is generated for the Haskell example.

Well, the _actually_ corresponding D code using BigInt and DMD is 
significantly slower than what GHC generates here.

In any case, I don't think that this kind of mutation-heavy code is a 
core focus of GHC, so the assembly will probably not be nearly as well 
optimized as it could be.

But if you'd like to compare the offers of D and Haskell a little 
further, consider the following cute code, which I wrote in 5 minutes 
and which computes the 1000000th natural number that is a product of 
powers of 2, 3 and 5 well below a second on my machine:

merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] xs = xs
merge xxs@(x:xs) yys@(y:ys) =
   case compare x y of
     LT -> x : merge xs yys
     EQ -> x : merge xs ys
     GT -> y : merge xxs ys

hamming :: [Integer]
hamming = 1 : merge    (map (*2) hamming)
                 (merge (map (*3) hamming)
                        (map (*5) hamming))

main = print $ last $ take 1000000 hamming

519312780448388736089589843750000000000000000000000000000000000000000000000000000000

What do you think would be the corresponding idiomatic/fast D code? Does 
it outperform the Haskell code?