dsill@nswc-oas.arpa (06/24/88)
"T. William Wells" <bill@proxftl.uucp> writes: >In article <14522@brl-adm.ARPA>, dsill@nswc-oas.arpa (Dave Sill) writes: >> You are implying that programmers can solve unsolvable problems but >> that programs cannot, which is simply not true. > >Actually, you should keep your referents straight. I might be >implying that humans can solve problems that are unsolvable by >COMPUTERS. The truth of that is a matter of conjecture. You're absolutely right. I *have* been assuming that the computational power of the human brain is subject to the Church-Turing Thesis. I have no reason to believe that that is an incorrect assumption. >This of course ignores the fact that aliasing is a property of >the DESIGN of the program, not just of the program itself. It is >entirely possible to design a program which has some particular >aliasing property which can't be found by inspecting the code. >Consider this contrived example: > > scanf("%d %d", &i, &j); > p = &a[i]; > q = &a[j]; > >Can p and q point to the same object? In the general case, yes. >However, the programmer might intend this to be in a system where >the two numbers can never be the same. So, the noalias keyword >would add information that is not present in the program. Yes, we've been through all this before. Your example is exactly the kind of thing I've been preaching against. It is too likely that somebody will port such code to a system where the same assumptions aren't true. And without something in the code stronger than a comment like "/* of course i can never equal j */", a bug will be silently introduced. I propose something along the lines of scanf("%d %d", &i, &j); assert (i != j); p = &a[i]; q = &a[j]; which makes the compiler aware of the assumptions made by the programmer in a rigorous and verifiable manner. The advantages of this over the storage-class/keyword approach are many: - when testing a port on a new system, the `assert' macro can be enabled, alerting the developers/porters when a previously made assumption fails. - the programmer is unable to introduce subtle bugs through incorrect use of `noalias'. - the language is kept smaller, simpler, and cleaner. - the optimization is available to all users of the language that take the time to "document" the assumptions they make, not just those that understand the aliasing problem. - other types of optimization can be enabled by the same method without requiring the introduction of new keywords. The only disadvantages of this approach that I'm aware of are: - it requires smarter compilers. - it is not able to enable all kinds of optimization that the storage-class approach can. (how would one indicate that a variable is or is not volatile?) Unfortunately, X3J11, or ANSI (I don't know which), has simultaneously enabled and precluded possibly the best solution: standardized pragmas. How hard would it have been for them to set up a system for registering the syntax and semantics of various vendor-implemented pragmas? Maybe it's not too late for a secondary organization to provide this service. In conclusion, although the storage-class method is, in my opinion, a poor method of enabling optimizations, it will probably be the method of choice for compiler implementors because it is easier than adding the necessary smarts to their compiler. ========= The opinions expressed above are mine. Thus spake the master programmer: "Though a program be but three lines long, someday it will have to be maintained." -- The Tao of Programming
smryan@garth.UUCP (Steven Ryan) (06/25/88)
In article <16271@brl-adm.ARPA> dsill@nswc-oas.arpa (Dave Sill) writes: >>> You are implying that programmers can solve unsolvable problems but >>> that programs cannot, which is simply not true. >> >>Actually, you should keep your referents straight. I might be >>implying that humans can solve problems that are unsolvable by >>COMPUTERS. The truth of that is a matter of conjecture. > >You're absolutely right. I *have* been assuming that the >computational power of the human brain is subject to the Church-Turing >[hypo-]Thesis. I have no reason to believe that that is an incorrect >assumption. I have reason to believe that is an incorrect assumption, and I have no reason to believe it's a correct assumption. No proof of course. Dear friends, not everybody assumes this. So puleeeease, don't hold compilers up to this possible/impossible standard. If you want something everybody can accept, deal with the existing technology rather than building castles in the air. >Yes, we've been through all this before. Your example is .... Before another round of examples and counterexamples, are you prepared to write a total recursive predicate that can verify all practical cases of aliassing? (Not all possible cases--a sufficiently large set of practical cases will do.) Given the modern technology, can you guarentee a compiler could recognise the predicate? > assert (i != j); Actually on Vax or Cyber 180, words need not be on word boundaries, so you need assert(abs(i-j)>=word_separation) The real issue is not whether this can be detected, but what is the cost/risk tradeoff? Is it so risky we might as well use assembly? Is it so costly we have to use assembly? ----------------------------------- Neurotics build castles in the air. Psychotics live in them. Psychiatrists collect the rent.
bill@proxftl.UUCP (T. William Wells) (07/03/88)
In article <16271@brl-adm.ARPA>, dsill@nswc-oas.arpa (Dave Sill) writes: > "T. William Wells" <bill@proxftl.uucp> writes: > >In article <14522@brl-adm.ARPA>, dsill@nswc-oas.arpa (Dave Sill) writes: > >> You are implying that programmers can solve unsolvable problems but > >> that programs cannot, which is simply not true. > > > >Actually, you should keep your referents straight. I might be > >implying that humans can solve problems that are unsolvable by > >COMPUTERS. The truth of that is a matter of conjecture. > > You're absolutely right. I *have* been assuming that the > computational power of the human brain is subject to the Church-Turing > Thesis. I have no reason to believe that that is an incorrect > assumption. Well, since we are bandying about concepts without any real reference to reality, let me toss this possible reason at you: computers are discrete devices, the brain is (or at least might be) a continuous device. It is undecidable whether aleph-1 (the cardinal for the power set of the integers, here representing discrete systems) is equal to c (the cardinal for real numbers here representing real systems). This suggests that there is a fundamental difference between these two systems, and that difference might be reflected in the possibilities open to digital machines and brains. Anyway, this is empty vaporing and besides the point, so lets not beat it to death. > Yes, we've been through all this before. Your example is exactly the > kind of thing I've been preaching against. It is too likely that > somebody will port such code to a system where the same assumptions > aren't true. I think you completely missed the point. Were I to write such a program, it would be a property of the system the program was in that the two inputs could NOT be the same; were they the same, the whole system would be broken. To make this concrete, suppose that these numbers represented a node and its parent in a tree. In this case there are two possibilities: the program feeding the data works, in which case the data read is valid and everything is OK, or the program feeding the data is broken and the system fails, regardless of what the compiler is doing. Porting has nothing to do with it. > And without something in the code stronger than a > comment like "/* of course i can never equal j */", a bug will be > silently introduced. The comment is going to be something more like: /* i is the parent node and j is the child node. */. Actually, the variable names would be chosen to reflect this. In the rest of your article you suggest (as others have) the use of assert() to accomplish what noalias does. Given the problems with noalias (among other things, the difficulty of understanding exactly what it does), I would prefer your macro to noalias; but it does have the drawback, as others have noted, of not being able deal properly with the real problem: pointers. Here is why: char *p1; char *p2; if (p1 < p2) ... is not portable unless the two pointers point within the same object, a condition which is often not the case when one is trying to specify that the two pointers do not alias. An assert macro is going to have to generate comparisons like this to say that the two pointers are not aliased. I hope that there will be no further discussion on the noalias keyword; it is moot since it is gone from the standard. Sometime in the distant future, when we have given the alias problem some real thought, perhaps we will come up with a solution to the problem that does not require clairvoyant compilers or supergenius programmers. Until that time, let's not debate irrelevant stuff about aliasing.
markb@sdcrdcf.UUCP (Mark Biggar) (07/04/88)
In article <408@proxftl.UUCP> bill@proxftl.UUCP (T. William Wells) writes: >Well, since we are bandying about concepts without any real >reference to reality, let me toss this possible reason at you: >computers are discrete devices, the brain is (or at least might >be) a continuous device. I think that it is easy to demonstrate that the brain IS a discrete device. Nerve impulses are transmitted across the synaptic gaps using certain neuro-transmitter molecules. Since a fraction of a molecule is nonsence, the brain is a discrete device. Given that electric changes and even energy are quantized, I am willing to take the position that all realizable material devices are discrete. There are no such things as continuous devices (at least in this universe). Mark Biggar {allegra,burdvax,cbosgd,hplabs,ihnp4,akgua,sdcsvax}!sdcrdcf!markb markb@rdcf.sm.unisys.com
friedl@vsi.UUCP (Stephen J. Friedl) (07/06/88)
In article <408@proxftl.UUCP> bill@proxftl.UUCP (T. William Wells) writes: < ... computers are discrete devices, the brain is (or at least might < be) a continuous device. In article <5368@sdcrdcf.UUCP>, markb@sdcrdcf.UUCP (Mark Biggar) writes: < I think that it is easy to demonstrate that the brain IS a discrete < device. Nerve impulses are transmitted across the synaptic gaps < using certain neuro-transmitter molecules. Since a fraction of a molecule < is nonsence, the brain is a discrete device. Given that electric changes < and even energy are quantized, I am willing to take the position that < all realizable material devices are discrete. There are no such things < as continuous devices (at least in this universe). An anecdote along these lines: A friend and I were talking about hardware design. I have a very informal background, and as such am only really comfortable with building-block style digital design. My friend, who is an EE and uses analog a lot, says "If you're good, everything is analog, but if you're *real* good, everything is digital". Steve :-) :-) :-) :-) -- Steve Friedl V-Systems, Inc. (714) 545-6442 3B2-kind-of-guy friedl@vsi.com {backbones}!vsi.com!friedl attmail!vsi!friedl --------Nancy Reagan on Professor Chomsky: "Just say Noam" --------
smryan@garth.UUCP (Steven Ryan) (07/06/88)
In article <5368@sdcrdcf.UUCP> markb@sdcrdcf.UUCP (Mark Biggar) writes: >I think that it is easy to demonstrate that the brain IS a discrete >device. Nerve impulses are transmitted across the synaptic gaps >using certain neuro-transmitter molecules. Since a fraction of a molecule >is nonsence, the brain is a discrete device. Given that electric changes >and even energy are quantized, I am willing to take the position that >all realizable material devices are discrete. Ah! But is the interarrival time of pulses continously or discretely distributed? Are neurons synchronised so that the brain makes continuous or discrete state transistions? When neurons form new connections (and they do) is according to a predetermined plan or is it response from the environment== does the brain have a finite number of discrete states? >all realizable material devices are discrete. There are no such things >as continuous devices (at least in this universe). What, no four dimensional space-time continuum?
rob@kaa.eng.ohio-state.edu (Rob Carriere) (07/06/88)
In article <877@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: > [...] When neurons form new connections (and they do) >is according to a predetermined plan or is it response from the environment== >does the brain have a finite number of discrete states? Finite number of braincells, each makes only a finite number of connections during its' liftime (planned or otherwise, I don't care) => finite number of available states => your ``=='' s.b. ``!='' >In article <5368@sdcrdcf.UUCP> markb@sdcrdcf.UUCP (Mark Biggar) writes: >>all realizable material devices are discrete. There are no such things >>as continuous devices (at least in this universe). > >What, no four dimensional space-time continuum? Irrelevant. Total number of atoms is finite. Rob Carriere
smryan@garth.UUCP (Steven Ryan) (07/07/88)
>> [...] When neurons form new connections (and they do) >>is according to a predetermined plan or is it response from the environment== >>does the brain have a finite number of discrete states? correction: a bounded number of discrete states. >Finite number of braincells, each makes only a finite number of >connections during its' liftime (planned or otherwise, I don't care) >=> finite number of available states => your ``=='' s.b. ``!='' You need to be able to prove that the total number of states is bounded by a specific number. Simply stating finite neurons making finite connections ignores the quality of the connections. Neurons are not silicon chips but complex organic cells. It takes more than an assertion they can be modelled with sufficient accuracy by a discrete process. The constraints of formal systems are - fixed number of discrete states. - finite number of discrete state transistions. - discrete storage in a fixed alphabet. >>>all realizable material devices are discrete. There are no such things >>>as continuous devices (at least in this universe). >> >>What, no four dimensional space-time continuum? > >Irrelevant. Total number of atoms is finite. Therefore a finite number of particles, virtual or otherwise. Therefore a finite bound on the number of spontaneously created and destroyed particle. Therefore a finite number of interconnections, that is a finite number of paths through the continuum.
eric@snark.UUCP (Eric S. Raymond) (07/07/88)
In article <745@vsi.uucp>, friedl@vsi.UUCP (Stephen J. Friedl) writes: >In article <408@proxftl.UUCP> bill@proxftl.UUCP (T. William Wells) writes: >> ... computers are discrete devices, the brain is (or at least might >> be) a continuous device. > >In article <5368@sdcrdcf.UUCP>, markb@sdcrdcf.UUCP (Mark Biggar) writes: >> I think that it is easy to demonstrate that the brain IS a discrete >> device. Nerve impulses are transmitted across the synaptic gaps >> using certain neuro-transmitter molecules. Since a fraction of a molecule >> is nonsence, the brain is a discrete device. Given that electric changes >> and even energy are quantized, I am willing to take the position that >> all realizable material devices are discrete. There are no such things >> as continuous devices (at least in this universe). > > My friend, who is an EE and uses analog a lot, says "If >you're good, everything is analog, but if you're *real* good, >everything is digital". I'd like to agree with you (markb@sdcrdcf), but your argument isn't anywhere near sharp enough. There are huge numbers of continuous quantities that may be involved in the microlevel of informatoin representation in the brain. Consider all the parameters involved in protein shape. And the brain's magnetic flux is known to carry high-level information about its state (experiments using SQUID magnetography had demonstrated crude but dramatic thought-reading by nachine as far back as 1984; the stuff's probably all classified by now). Can you show that these things are also quantized? I have redirected followups to sci.philosophy.tech. -- Eric S. Raymond (the mad mastermind of TMN-Netnews) UUCP: ..!{uunet,att,rutgers!vu-vlsi}!snark!eric Smail: eric@snark.UUCP Post: 22 South Warren Avenue, Malvern, PA 19355 Phone: (215)-296-5718