From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=unavailable autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Paul Rubin Newsgroups: comp.lang.ada Subject: Re: How to get Ada to ?cross the chasm?? Date: Wed, 02 May 2018 15:28:09 -0700 Organization: A noiseless patient Spider Message-ID: <87lgd1heva.fsf@nightsong.com> References: <1c73f159-eae4-4ae7-a348-03964b007197@googlegroups.com> <87k1su7nag.fsf@nightsong.com> <87po2la2qt.fsf@nightsong.com> <87in8buttb.fsf@jacob-sparre.dk> <87wowqpowu.fsf@nightsong.com> <16406268-83df-4564-8855-9bd0fe9caac0@googlegroups.com> <87o9i2pkcr.fsf@nightsong.com> <87in88m43h.fsf@nightsong.com> <87efiuope8.fsf@nightsong.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: reader02.eternal-september.org; posting-host="c542ccd1be7cc45dffb8a8de81e34fd0"; logging-data="29262"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/kv5fGUi/Y6ekjHOgiwwIJ" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux) Cancel-Lock: sha1:iAwEwQiAlYjPtr1EfLXVYrcuodw= sha1:nP0qhf3Zfq+1OhETyxTm6T4SVS4= Xref: reader02.eternal-september.org comp.lang.ada:51928 Date: 2018-05-02T15:28:09-07:00 List-Id: "Randy Brukardt" 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.