Re: How to get Ada to ?cross the chasm??

[Paul Rubin <no.email@nospam.invalid>]

"Randy Brukardt" <randy@rrsoftware.com> writes:
> Right: "spaghetti data". Again, why is spaghetti data acceptable but 
> spaghetti code not acceptable? Data with random references to other data is 
> no more structured than code full of gotos. We never allow the latter, why 
> allow the former??

Here's a complete Haskell program for printing the first 20 prime
numbers, using cyclic data (what you call "spaghetti"):

    main = print . take 20 . sieve $ [2..] where
      sieve (p:xs) = p : sieve [a | a <- xs, a`rem`p /= 0]

The idea is that sieve is a self-referential list, created by taking the
infinite list [2,3,4,5...], and yielding its first element followed by
what you get by (recursively) sieving the result of filtering out
multiples of the first element from the rest of the list.  So the sieve
output is prime numbers.  The program then just takes 20 elements of the
sieve output and prints them.

Obviously there are more efficient algorithms and you could code
something like the above with arrays and loops and whatnot, but the
above was very easy to write.

Here's a harder problem: generate a list of numbers that have no prime
factors bigger than 5.  These are called "Hamming numbers".  The first
20 of them are:

   1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

Question: what is the 1691st Hamming number?  (Answer: 2125764000, that
was chosen because it's the largest one that fits in 32 bits).  Or if
you have 64-bit ints, what is the 10000th one?  

The page

   http://rosettacode.org/wiki/Hamming_numbers

has a bunch of implementations including in Ada and Haskell.  The
Haskell example ("The classic version") is very simple and fast, using
"spaghetti".  It finds the 1691st and 10000th Hamming numbers instantly,
and the millionth one in about 0.5 seconds on an Intel i5.

Implementing the same algorithm in Ada is of course possible but it's
enough of a pain that whoever wrote the Ada code on that page didn't
even try (maybe someone here can fix that).  Instead it just counts
upwards and tests each number.  It takes about 15 seconds to find the
1691st number on the same machine, and at that rate would take about 64
years to find the 10000th.  It doesn't attempt to find the millionth (it
claims that's just a matter of using bignums, overlooking how long it
would take to count up to the answer, which is around 5e83).

Despite that, the Ada code is still about 5x longer than the Haskell
code.  Fixing the algorithm would likely bloat it by another 2x or so.

So basically it's not "spaghetti", it's having power tools and the
ability to use them.