Re: What's the best language to start with? [was: Re: Should I learn C or Pascal?]

[ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe)]

"Tim Behrendsen" <tim@a-sis.com> writes:
>> Here you are making a claim to be able to compute non-computable
>> functions.  I don't believe you. 

>As I understood what you wrote, your optical computer was
>modulating a signal based on refraction index of a medium.  This
>sounds calculable to me, assuming we know how the refraction
>function of your crystal is set up.  We are getting a bit
>beyond my knowledge;  I don't know if you mean that the
>mathematics is unknown, or unknowable, but let me take both
>cases.

Neither.  "Computable" has a standard precise technical sense, which you
appear to be unaware of.

>Unknown: Just because a natural law is not understood, doesn't
>mean there is not an algorithm behind it.

For Ghu's sake, there are functions from the naturals to the naturals
which are not computable, let alone functions from nondenumerable spaces!

>Unknowable: There are certainly cases in physics where the
>underlying algorithm is not predictable; for example, the
>output of a geiger counter could not be simulated using pencil
>and paper (that we know of, anyway).  Now, this is a much more
>interesting question.  Is there an algorithm behind atomic
>decay?  There must be a *method*, even if it is not predictable
>(or known).  Your author's definition obviously wasn't designed
>to handle questions of this type; I think it comes down to
>opinion whether this fits a definition of algorithm.

You are confusing predictability with determinism.
Popper showed several decades ago that a Newtonian universe is not
*predictable* by any computing mechanism even though it is *deterministic*.
(To the best of my knowledge, Popper published this well before "chaos"
became a fashionable concept.)

The Universe *does* things which cannot be accurately modelled by
anything that has ever been proposed as a realistic physical model
of computation.  Weather is the most obvious case.

When you talk about about there being an "algorithm" or "method"
behind atomic decay, you enter the realms of science fiction.
(Wasn't it A.E.van Vogt who had 'electron psychology' in one of his
stories?)  Either I have completely misunderstood (which is likely,
because quantum mechanics was by far my worst subject) or the current
belief is that there are *no* hidden variables and there is *no*
"algorithm" or "method", quantum events just happen as often as their
amplitudes say they should.  (Mermin savaged Popper for failing to
distinguish between probabilities and amplitudes.  Rather a relief
to me, as I had never quite understood Popper's "propensities".)

If you are _right_ that everything in the real world including atomic
decay is procedural, then everything in modern physics is as wrong as
it can possibly be, not just incomplete but wrong-headed through and
through.

>Even a C program has "non-procedural" elements, if you take look
>at a function call such as printf as an atomic operation where
>you do not specify how to do it, only what you want to be done.
>In fact, "function call" pretty much says it all, doesn't it?

>I was mostly referring to the "pure" non-procedural languages
>that have *zero* procedural elements to it, and it's completely
>up to the compiler/interpreter to figure it out.

How often do I have to say it before you get the point?

    A.	THERE IS NO SUCH THING AS A FORM OF EXPRESSION FOR
	COMPUTABLE FUNCTIONS WHICH DOES NOT ADMIT A
	PROCEDURAL READING.

    B.	THERE IS SUCH THING AS A FORM OF EXPRESSION FOR
	COMPUTABLE FUNCTIONS WHICH DOES NOT ADMIT A
	NON-PROCEDURAL READING.

"Function" here is to be interpreted in a wide sense including mappings
from concurrent input streams to concurrent output streams ("functions
over histories").  The class of languages you are trying to talk about
simply does not exist.

>As far as SQL goes, it is a pure mathematical statement, with
>no procedural element at all (assuming we are not talking about
>cursors, etc.).

No, no, and no.  You are insisting that your reading of SQL is the
only possible correct one.  But it isn't.  I am allowed to read the
specification of a computable function any way I want as long as I
get the same answers.

The classical example of this is of course the lambda calculus.
There is a large body of work on alternative readings of the lambda
calculus.

>It simply describes a function on one or more
>matrices.

In exactly the same way, I can say of *any* program that it "simply
describes a function on" certain denotations.

>In fact, joins are usually described in terms of
>cartesian products, but we all know the implementation tries
>to avoid the cartesian product at all costs.

The readings a particular computer program applies to a formalism
place no upper bound on the set of readings the formalism admits,
not even on the set of *useful* readings.

>There may come a day when non-procedural languages can be used
>for more than very specialized uses, but let's fact it; the
>"normal" procedural languages such as C are domininant at this
>point in our computer history.  As such, I think it's very
>important to give the student a grounding in this type of thinking.
>This doesn't preclude them from learning more exotic types of
>languages, but we should give them a foundation based on where
>the state of the art is.


There are so many differences between us packed into this one little
paragraph that I think it is time for me to pull out of this thread
after listing a few of them.  Recall that the context is teaching;
nobody disputs that computing professionals should _eventually_ know
a whole lot of things.

1.  "The imperative paradigm is dominant."

    I wonder whether it is _true_ that the imperative paradigm is
    dominant.  Does anybody know what proportion of work is done
    using spreadsheets and data base languages compared with the
    proportion of work done using imperative languages?  I am
    supervising a Masters student doing a project on data quality;
    this student has a lot of experience with software engineering
    and commands high consulting pay from *big* companies, but hasn't
    written an imperative program in *years*.

2.  "Whatever is, is right."
    I'm Dr O'Keefe, not Dr Pangloss.  I don't believe this.

3.  "The initial approach to _teaching_ a subject should be confined
    to what is currently fashionable in some blinkered view of 'the
    real world'."

    This sounds to me like a good recipe for ensuring
    that your students will be obsolete when they graduate.

4.  "The initial approach to _teaching_ a subject should be based on
    what yesterday's practitioners identified as the foundations of
    the subject."

    This proved a disaster when applied to the teaching
    of mathematics in schools.  Should we expect computing to be
    different?  (I am not saying that foundations can or should be
    ignored, just that one starts a five-year-old with "one, two,
    three", not with metamathematics or category theory.)

5.  "Non-procedural languages cannot be used for anything but
    specialised uses."

    Talk about blinkered.  Take a look at what you can do with Clean.
    It's perhaps the easiest language I've found for writing GUIs, and
    its performance is darned good.  Take a look at FoxNet 2.0 (TCP/IP
    in ML).  Take a look at Sisal.  Take a look at Erlang.  Let's see,
    that's GUI, TCP/IP, scientific computing, telecoms, distributed,
    all covered.

    I have to concede that if I were doing any 8051 programming I would
    use C or assembler.  Hmm.  Maybe.  It might be better engineering
    to design a declarative language tailored to the application and to
    write a compiler for it.  In an application like that you really
    *really* cannot afford the kinds of errors that imperative programming
    allows.

6.  "Declarative forms of expression are exotic."

    Alas, there is some truth in this.  When I and my peers entered
    University and started to learn about computing, we already had a
    good grounding in differential and integral calculus, elementary
    probability and statistics, vector and matrix algebra, and had
    met differential equations.  We had studied Euclidean geometry
    (the textbook was basically Euclid's Elements) and the notion of
    proof, including proof by cases and proof by induction.  To us,
    _discrete_ mathematics was exotic; the idea of step-by-step
    calculations in the computer was exotic.

    Alas, we in this department are not allowed to turn down prospective
    students simply because they didn't do mathematics at high school.
    (Or so I was told when I helped in the selection process.)
    And the ones who _did_ do it don't seem to recognise much of it when
    they see it again.  One of the scariest things I've heard in the
    last decade was a student complaining to me because a lecture had
    been too 'mathematical':  "I took CS because I'm no good at maths"
    and a large group of his friends agreeing with him.

    So it is unfortunately true that declarative forms of expression
    are exotic to a majority of our students.

    It is also unfortunately true that the high schools offer computing
    subjects, and that students sometimes take these instead of mathematics.
    Now, I know a high school teacher.  She is qualified as a librarian.
    A couple of months ago she was complaining about having to learn
    Italian because the school was going to have to teach it, and she'd
    been selected as one of the teachers.  Friends of the Italian language,
    are you quaking in your boots?  Are you weeping?  If they do that for
    Italian, in a state with a lot of fluent speakers of Italian, what do
    think they do for computing?

    So it is unfortunately true that procedural forms of expression
    are _familiar_ to a lot of our students.  "Unfortunately" because
    they think they understand it, which makes it harder for us to teach
    them.  Which brings me to the next point:

7.  "It is always best to teach using familiar concepts."

    One of the reasons why a number of Universities are using Miranda,
    or Haskell, or Orwell, or something of the sort, and certainly one
    of the reasons why we carefully selected a procedural language that
    was not currently being taught in the local schools (Ada) was that
    we'd like to get the students' attention.  And we simply don't get
    it as long as we are trying to teach them something they _think_
    they already know.  We did seriously consider something less like
    Pascal, but we got phone calls from high school careers people saying
    "if you go 'academic' we'll tell our students to stay away from you".
    No good doing the best thing if you go out of business, so we're
    doing a _good_ thing (Ada) and staying in business.

    The fact remains that one good educational reason for selecting a
    declarative language like Haskell is "listen up, we've got things
    to tell you that you don't already know".

8.  "How last decade's computers used to execute programs is the most
    important thing to understand, so it should be taught first."

    Well, there are a _lot_ of things we have to teach.  How to use the
    index in a textbook.  How to look things up in a library.  How to
    use a spelling checker, a word processor, electronic mail.  How to
    write comments (we need to put more effort into that).  How to write
    documentation for a computer program (they're doing better than they
    used to before we started teaching this explicitly, but not well
    enough yet) or project.  (We really need to fit in a remedial English
    course.  The Center for English Learning already offers such courses
    for overseas students, and the department pays for students who need
    them badly to attend them, but very very few of those who need them
    actually go.  In another year or two we'll have to make it compulsory
    for all students.)  How to name things.  Elementary discrete
    mathematics.  Elementary probability and statistics.  The idea of
    testing.  I could go on and on and on.

    The machine our students use is four-way superscalar, with 6
    functional units, longish pipes, and loads may be up to 30 cycles
    "in flight" before a datum arrives.  I don't know if it does out-
    of-order execution or not; if it doesn't, then a paper I was reading
    yesterday from NYU would call it an "early" RISC!  This is why I call
    the 'classical' procedural reading of an imperative program "how
    last decade's computers used to execute programs."  The vendor's C
    compiler automatically does function inlining, loop unrolling, and
    apparently will do modulo scheduling (though the option for that is
    not documented).  The order specified in a C program isn't even
    close to the order in which things actually happen in the hardware.

    So why is an abstraction which is NOT genuinely the way the students'
    computer works the FIRST thing they should learn?  Why is it more
    important than, oh, first order predicate calculus?  Or elementary
    probability?  Or how to write a specification?  Or, come to that, how
    to _read_ a specification?  (Such as an assignment.  Some of our
    students, even articulate ones, have real trouble with that.  If they
    do what my high-school teachers called "comprehension" exercises, it
    doesn't seem to help enough.)

    I put it to the few remaining readers of this thread that it is MUCH
    more urgent to learn how to communicate with other human beings
    about what is to be computed than it is to learn how last decade's
    machines used to work.


>And there's a reason for the dominance of procedural languages
>such as C.  They are simply the most efficient way (in an
>execution sense) to express algorithms at this point.

This hasn't been true for some time.  Sisal is perhaps the oldest
counter-example.

The reason for the continued dominance of imperative languages is
economics, nothing else.  It doesn't matter if declarative languages
have now reached the point where their compilers can routinely run
rings around C compilers (but not Fortran compilers); if the bulk
of programmers are trained in old-fashioned techniques and the bulk
of development tools support old-fashioned techniques, then the
conversion cost may be prohibitive.

I gave an example in my last posting where abandoning C, going back to
a declarative notation, and then writing a specialised code generator
gave me a speed-up of about 5 or 6 over the best that C could do.
It turns out that using the next generation of the hardware gives a
factor of 7 speedup.  (The specialised code speeds up too, but it doesn't
speed up as much.  Improving the scheduler should restore the relative
positions of the "derived-from-declarative" and C code.  I hope to have
that--still fairly crude--scheduler finished today.)

The point here is that even a factor of 5 or 6 speedup for abandoning
the procedural paradigm isn't a big enough reward for people and
organisations already mired in the old procedural mindset.  Wait a
couple of years, buy new hardware, and you get about the same speed,
*without* retraining or retooling.  "Incumbent advantage" can survive
major challenges.

If the most efficient execution were the main, or even a very important,
reason for programming language choice, who would use Java?  or Visual
Basic?  Or C?  We would all be using High Performance Fortran.

The things I like in Ada (generics, packages, static type checking without
too tight a straitjacket, &c) have very little to do with its procedural
side.  We didn't pick it as our first year language because it was faster
than C!  Although for a number of benchmarks that I've tried, it _is_.  So
if execution speed were the most important thing, we'd see everyone jumping
from C to Ada 95.  We don't see that.  Incumbent advantage.

>There
>may come a time when they are less important, but we are
>far off from the point, and we do disservice to students when
>we try and give them exotic thinking modes as the primary
>outlook.  Secondarily is OK, to give them a balanced viewpoint,
>but the primary viewpoint should be procedural.

Now I begin to understand how Sun were able to release Java on the
world with a clear conscience.  A specification of what exactly the
security model is (not available), a specification of exactly what it
is that the byte code verifier has to do (not available), and a proof
that the latter ensures the former (not available) would have involved
"exotic thinking modes".  Better to ship a "secure" language implementation
with security holes and rely on net users to finish the debugging than to
"do disservice" to anyone by taking "exotic thinking modes" as primary.
All that counts is how it works, not what it is supposed to do, right?


			WELL I AM SICK OF IT!

You can rail at it as much as you like; you can call it exotic; you can
say it's a disservice; you can say that the real world is algorithmic
right down to the nuclei.  But the fact remains that the viewpoint you
advocate as primary is the one which has flooded us with buggy software.
(Java isn't even _close_ to being the worst offender.  I was unfair to
Sun.  Windows 95 is probably doing far more real damage.)

When our students have trouble writing a working program, it is not because
they don't understand how the computer works.  It's because they never sat
down and said clearly, even to themselves, what the program was *supposed*
to do.  We preach at them and preach at them "Write the comments FIRST",
and they keep on handing in uncommented stuff saying "I didn't have the
time to write the comments."  The students *HAVE* your primary view as
their primary view, and that's why they are bad programmers.  They *HAVE*
your primary view as their primary view, and that's why they are so
hopeless at debugging.  They will spend hours stepping through a program
rather than 10 minutes thinking about it.

Mind you, I'm talking about 1st and 2nd year students.  We put a *lot* of
effort into trying to teach software engineering, not just programming,
and by the time the students graduate they have improved somewhat.

>> Do we teach children about the mechanics of speech before they
>> learn to talk?

>I think I am taking exactly the opposite viewpoint.  I want to
>focus on the basics of execution. It sounds you like you want to
>teach them about the abstraction of phonemes and language
>construction before they learn to talk.

This is like Hitler calling the Chief Rabbi a fascist.  Sigh.

SEQUENTIAL EXECUTION IS AN ABSTRACTION.

This rather remote abstraction (which is not true to the
way modern distributed systems with multi-processor superscalar out-of-order
executing pipelined machines actually work) is not basic.

"WHAT DO YOU *WANT* TO COMPUTE?"

is basic.  I don't know any theory of child language learning that
doesn't start from the child having something it wants to say.

>> When I was taught to play the piano as a child, I was taught about
>> forms of expression (how to read music), not about how to build a
>> piano or what happens when you press a key.

>Yes, but first you were taught how to move your fingers in
>sequence and rhythm.

Not so.  Nobody ever taught me how to move my fingers.

>You were not taught the abstraction of composition first.

Perhaps not, but this is a point to me, not a point to you.
Because composition is precisely the analogue of the sequential
execution abstraction.

>> When my wife bought a knitting machine as a teenager, she was taught
>> how to read patterns, and how to control the machine, not how the
>> machine is constructed or operates.

>Exactly.  She focused on the practical aspects of taking the
>pattern and executing the steps.  Same principle.

No, it's the *opposite* of your principle.  When you use a knitting
machine, you have little or no concern with the steps that the MACHINE
follows.  You lay the pattern out SPATIALLY.  The machine does it
temporarlly, but the human being sets it out SPATIALLY.

There are admittedly data-flow constraints on the order of setups,
but they too are understood in structural/geometric rather than
algorithmic terms.

>> I got a ham license without having to learn what actually goes on inside
>> a valve or transistor.

>Yes, but drivers don't "program" the car.  These both are more the
>"user" model than the "programmer" model.

I built my own ham equipment.  The radio amateur license exam tests your
knowledge of circuit and antenna theory.  Building your own equipment is
a hell of a lot closer to the "programmer" model than the "user" model.
My point is that, just as I didn't have to understand the device physics
underlying valves and transistors, only the mathematical "transducer"
model, in order to read, understand, and build an electronic circuit,
neither do programmers need to understand the low level mechanics of
computers in order to build programs.

>> What is so different about computing?

>You make my point for me.  You argue above that teaching at
>a high level of abstraction is good, 

This is exactly the opposite of what I said and meant.

The point that I am making is that you start from

	WHAT DO YOU WANT TO DO?

in all these areas, not

	HOW DOES THE MACHINE DO IT?

You have consistently argued that the fundamental which must be mastered
first is the sequential execution abstraction, which is concerned with
the secondary question "how does the machine do it".

Children learn to talk by having something they want to say.
They are explicitly taught the sequential execution abstraction
(grammar) much later.

People learn to drive by having somewhere they want to go
and wanting to learn how to make the car go there.
They are explicitly taught the execution abstract "the steering wheel
is connected to the rack and pinion which is connected to the steering
rods which are connected to the front wheels" (or whatever it is, I
don't really know, don't really care, and don't have any particular
reason why I _should_ know or care) afterwards, if at all.

People learn to play a musical instrument by having a tune that
they want to produce.
They learn how a piano actually _works_ much later, if at all.
(How many drummers need to understand the physics of vibrating
membranes?  Apart from Richard Feynman, that is.)

*How things work* is secondary to *what they are for*.

>Just because you teach procedural concepts doesn't preclude
>the student from learning non-procedural concepts.

Given that we and the students have only limited time,  the more time
we spend on abstractions like sequential execution the less time we
have to spend on fundamentals like requirements and specifications.

Just because we teach Ada doesn't mean the students are precluded from
learning Sisal or Haskell or RAISE or ...   The fact remains that they
*don't* learn these things.  (We do teach some Z.  But they learn it
*only* as a specification language.  Alas.)  Heck, just because we
teach computing doesn't preclude them learning quantum chromodynamics
either.  But that doesn't happen.

>> As I don't teach first year, no.  It is, of course, Knuth, The Art
>> of Computer Programming, Volume 1.

>Erg; pretty heavy duty.  I always wondered if anyone used them
>as textbooks.

Pretty heavy duty?  Well, the mathematics is a lot of fun.  It's closely
related to recreational mathematics after all.  I take it you are
referring to all that MIX assembly code as the "heavy duty" stuff.

>But even your neural net is composed of stages, and in fact,
>the vast majority of problems break down the way I outlined.

The neural net is composed of *layers*, not *stages*.
The defining concept is *data* flow, not *control* flow.
One way to wring another nice big constant factor out of the
computation, which I am not going to bother with, is to throw yet
another sequential imposition down the toilet, and run several training
instances through the net in parallel.  This can be done in two ways,
both of which should be followed up:  folded into the code so that we're
doing level-3 BLAS rather than level-2 BLAS, which would make better use
of the cache, and true real-world parallelism with multiple CPUs crunching
at the same time.

The really important thing here is not the particular problem or the
details, but that the kind of thinking I need for this problem is the
kind of thinking you need to write parallel code.  Allowing myself to
be hypnotised by one-step-at-a-time thinking, or how C does things,
would have been *fatal*.
	
>> Done much parallel programming yet?  You are describing an approach
>> to understanding algorithms which makes parallel programming _very_
>> difficult.

>Not at all.  I can visual parallel processing very easily.

I didn't ask whether you can _visualise_ parallel processing,
but whether you have *done* much parallel programming.
Since the only "parallel" operation you mention is quicksort,
I suspect that the answer is "no".

>Let's take the brain.  I submit my visualization of the brain
>as a huge collection of "black box" neurons with signals
>flowing between them is more accurate (and practical) than
>a view of the brain in terms of mathematical formulas.

A fuzzy mental "visualisation" with no specification as to _how_
the signals are transformed is more accurate (and practical)?
Surely you are living on the other side of the looking glass.

>The latter seems to me a complete failure if someone ever wants
>to really understand what's going on.

For your information, people *do* model neurons by mathematical formulas.
In fact, it wasn't until the formulas fitted actual neural behaviour
reasonably well that people believed they understood what was going on
inside neurons.

And of course "neural nets" *are* mathematical formulas.


Enough.  It has taken me about an hour and a half to write this,
and while it has been good to let off steam (I am still outraged by
the idea that teaching people to say what their programs are supposed
to do, which is a declarative notion, is an "exotic mode of thinking"
and a "disservice") it probably won't accomplish much else.

The thread is going in my kill-file.
-- 
Australian citizen since 14 August 1996.  *Now* I can vote the xxxs out!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.