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

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

"Randy Brukardt" <randy@rrsoftware.com> writes:
> I don't see anything "cyclic" or "self-referential" here. This is just a set 
> of lists, and there is nothing particularly interesting about them (in 
> partcular, there are *no* references involved in a list unless you need to 
> keep a reference to a particular element, certainly doesn't happen here).

This list contains a reference to itself:

    x = 1 : 2 : 3 : x

If you try to print it, you'll see "1,2,3,1,2,3,1,2,3,1,2,3..." ad
infinitum until you interrupt the program.  It is infinitely long, but
occupies a finite amount of memory.

The the prime-generation program, imagine you have a sequence of lists
L1, L2, L3, etc.  We'll split each list into its head (first element)
and tail (rest of the elements).  L1 will be the infinite list

  2, 3, 4, 5 ....

And we can describe that as H1 and T1 (H=head and T=tail), so
H1=2 and T1=[3,4,5...].

Now recursively define H_n to be the first element of T_(n-1) and
T_n to be the result of filtering all the multiples of H_N from the
tail of T_(n-1).  So L2 is  3, 5, 7, etc.  That is, H2=3 and
L2=[5,7,9,...].

Following the recursion, we get H3=5 and L3=[5,7,11,...].  We eliminated
9 because it is a multiple of H3 so we filtered it out.

The primes then are just [H1,H2,H3...] which is what that definition said.

> I don't think an infinite list would do much memory
> allocation/deallocation

Well it depends on what you do with the contents: in the Hamming number
example you do have to keep a lot of them around.

> Ergo, the underlying implementation of the Haskell code has to do
> something like that in order to figure out the answers. (There's no
> free lunch. :-)

Yes, that's exactly right: the burden is moved from the application
programmer to the language implementation.  As an application programmer
who likes to avoid work, I like languages whose implementations do more
of it so that I don't have to.  Or alternatively, using the same amount
of application development effort with such languages, I can write a
program that does more.

> A lot of power tools should never be used by the untrained.

Sure, I agree with this, programming still takes some skill.  But that
Hamming number code isn't particularly mysterious.  Back in the day,
programmers would learn techniques like hash tables, recursion, etc.;
and then when given a problem they would either 1) see a solution from
techniques they knew; or 2) not immediately see a solution and have to
spend more time thinking, studying new techniques or whatever.  In an
interview setting a programmer who didn't understand hash tables might
miss a few questions that hash tables would immediately solve.  The
programmer could then cure the gap in their knowledge by reading about
hash tables in a programming book and working through a few examples.

The picture I'm trying to convey is that functional programming brings
some new techniques that (like hash tables) let you easily solve certain
problems once you know the tricks, that would be hard to solve
otherwise.  The idea of repeatedly filtering a lazily generated list is
one of those tricks, and makes the primes and the Hamming number
solutions very natural.  The well-known intro CS text "Structure and
Interpretation of Computer Programs" (mitpress.mit.edu/sicp) discusses
this trick quite a lot.

I got interested in Haskell about 5 years ago and have spent quite a bit
of time on it on and off since then.  I can report that it's one of the
most interesting things I've ever done as a programmer.  I've learned a
lot and enjoyed it and highly recommend it.  I don't think that it's the
answer to everything (there is no answer to everything, Ada is not the
answer to everything either), but it's a valuable tool to have in one's
toolbox.  If you like a tool and see a problem you can use it on, why
would you look for ways to *not* use it?