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=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public From: ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) Subject: Re: What's the best language to start with? [was: Re: Should I learn C or Pascal?] Date: 1996/09/19 Message-ID: <51qmib$kk2@goanna.cs.rmit.edu.au> X-Deja-AN: 181540524 references: <01bb8df1$2e19d420$87ee6fce@timpent.airshields.com> <515o3b$d7h@goanna.cs.rmit.edu.au> <01bb9fe6$7299d800$87ee6fce@timpent.a-sis.com> <5182u7$17b@goanna.cs.rmit.edu.au> <01bba125$4e8c4ca0$32ee6fcf@timhome2> <51b8i4$m9m@goanna.cs.rmit.edu.au> <01bba50d$b4e0a640$87ee6fce@timpent.a-sis.com> organization: Comp Sci, RMIT, Melbourne, Australia newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada nntp-posting-user: ok Date: 1996-09-19T00:00:00+00:00 List-Id: "Tim Behrendsen" 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.