gudeman@cs.arizona.edu (David Gudeman) (08/17/90)
In article <6465@helios.ee.lbl.gov> austern@ux5.lbl.gov (Matt Austern) writes: >In article <24043@megaron.cs.arizona.edu>, gudeman@cs (David Gudeman) writes: >>I am always disturbed by the idea that for a language to have some >>good property, it must forbid the programmer from doing X. > >I'm sure that this is obvious to everybody, but I think it bears >repeating: if the "good property" is efficiency, this is often best >achieved by forbidding the programmer from using certain >constructions. No, it is not obvious to me, and this idea is one that I was specifically thinking about when I made my statement above. >The more assumptions a compiler can make about a program, the better >it can do the optimization, and in many cases, the only way a compiler >can safely assume that a programmer doesn't do something is to make it >illegal. This is the assumption that I find obviously false. Lets say that the programmer is forbiden from doing X for efficiency reasons. Then there are three cases: (1) the compiler verifies the property when compiling individual modules. If the compiler can verify that a property holds for a program, then it can always use this information to decide whether to do the optimization or not. The programmer is given a choice between using X and taking the efficiency hit, or not using X and getting the same run-time performance as a language that forbids X. You have lost no performance, and you have gained expressiveness. (2) the compiler/linker verifies the property at link-time, but you want to do optimization at module compile time. The compiler for the extended language assumes that X is not used and generates code as efficient as a language that forbids X. But there is a special declaration that tells the compiler not to make this assumption. Again you have increased expressiveness at no penalty for those programs that do not make use of the increased expressiveness. The compiler does not do the verification if the declaration told it that X is used. (3) the compiler does not verify the property at all. As (2), except for the verification. Using your example: > >(The C calling convention is more complicated than the >FORTRAN calling convention, for example, because C allows recursion. Add to FORTRAN a procedure declaration that says a given routine may be recursive. Then the compiler uses the more complicated calling convention for those routines only. I suspect that FORTRAN is not required to verify non-recursiveness, so this is a case (3), where the compiler just trusts the user. This however is _no different_ than the current status, where the compiler must trust the user not to write recursive code. This does not introduce new sources for error, because it will not cause an error if a procedure is declared recursive when it is not. >Can you really imagine a C compiler/linker that can prove that a >program has no recursive calls, and use a simpler calling convention >for such programs?) In the first place, this has no bearing on my thesis. In the second place, yes. It's really quite trivial to prove that recursion is impossible in most non-recursive programs. The only programs where non-recursion cannot be proven automatically are those which have a recursive call in a section of code that will never be executed, but where the compiler cannot prove that the code will never be executed. Since such programs are almost guaranteed to be not what the programmer intended, I feel confident in saying that non-recursion can be automatically proven in correct non-recursive programs. -- David Gudeman Department of Computer Science The University of Arizona gudeman@cs.arizona.edu Tucson, AZ 85721 noao!arizona!gudeman
gl8f@astsun7.astro.Virginia.EDU (Greg Lindahl) (08/17/90)
In article <24279@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: >In article <6465@helios.ee.lbl.gov> austern@ux5.lbl.gov (Matt Austern) writes: >>The more assumptions a compiler can make about a program, the better >>it can do the optimization, and in many cases, the only way a compiler >>can safely assume that a programmer doesn't do something is to make it >>illegal. > >This is the assumption that I find obviously false. Try this for an example: FORTRAN doesn't allow aliased arguments in subroutine calls. This allows FORTRAN compilers to make all sorts of nice optimizations. Although it is possible to insert run-time checks to make sure aliasing doesn't happen, IF the programmer declared the array to the proper size in the subroutine, I have yet to meet a compiler which does so. I might also note that the Convex vectorizing C compiler has a switch which allows the compiler to assume that arguments are not aliased. Again, no run-time check is available, but it is theoretically possible. I'd write valid programs and like it when they run fast. I like compilers that can warn me of invalid programs at compile or run-time, but I hate compilers which skip optimizations because it might trip an invalid program. I'll debug where I have good compilers, and run where the machine is fast. If I'm using C, I'm willing to write with the restriction of no aliasing. -- "In fact you should not be involved in IRC." -- Phil Howard
gudeman@cs.arizona.edu (David Gudeman) (08/17/90)
In article <1990Aug16.204409.4744@murdoch.acc.Virginia.EDU> gl8f@astsun7.astro.Virginia.EDU (Greg Lindahl) writes: > >Try this for an example: FORTRAN doesn't allow aliased arguments in >subroutine calls. This allows FORTRAN compilers to make all sorts of >nice optimizations. This example fits so obviously into scenario (3) that I feel I must not have expressed myself at all clearly. Maybe if I explain this example in detail it will clear things up: Let's design FORTRAN++, a proper extension of FORTRAN. Legal FORTRAN programs are compiled exactly the same way in FORTRAN++ as in FORTRAN, including the optimizations that come from assuming no aliasing. But in FORTRAN++, there is a subroutine declaration that tells the compiler a given subroutine _can_ have aliased arguments. When it sees this declaration, a FORTRAN++ compiler does not do the optimizations, and does not check for aliasing in procedure calls (if it does otherwise). FORTRAN++ programs are just as efficient as FORTRAN programs as long as the programmer doesn't take advantage of the new declaration. If the programmer _does_ declare a subroutine as having aliased arguments, then presumably he feels the extra expressiveness is worth the performance loss. It would be a good idea to check the consistency of these declarations at link time, although if you don't, FORTRAN++ is no less secure than FORTRAN. I have this silly idea that the programmer (at coding time) is better at making decisions on how to write a particular program than is the language designer at language-design time. Face it, the programmer knows a lot more about the problem area and resource constraints than the language designer does (who had no idea that anyone would be using his language to solve that problem in that environment). -- David Gudeman Department of Computer Science The University of Arizona gudeman@cs.arizona.edu Tucson, AZ 85721 noao!arizona!gudeman
mikeb@ee.ubc.ca (Mike Bolotski) (08/17/90)
In article <24294@megaron.cs.arizona.edu>, gudeman@cs.arizona.edu (David Gudeman) writes: > > Let's design FORTRAN++, a proper extension of FORTRAN. Legal FORTRAN > programs are compiled exactly the same way in FORTRAN++ as in FORTRAN, > including the optimizations that come from assuming no aliasing. But > in FORTRAN++, there is a subroutine declaration that tells the > compiler a given subroutine _can_ have aliased arguments. When it > sees this declaration, a FORTRAN++ compiler does not do the > optimizations, and does not check for aliasing in procedure calls (if > it does otherwise). This sounds rather like the #pragma facility in C, but on a per-procedure basis. [Discussions to the portability of #pragma will be ignored]. > I have this silly idea that the programmer (at coding time) is better > at making decisions on how to write a particular program than is the > language designer at language-design time. Face it, the programmer The above may true for an experienced programmer who is aware of all the various levels between his language and execution on the bare metal. I'll bet that 50% of existing C programmers don't know what aliasing is. > knows a lot more about the problem area and resource constraints than > the language designer does (who had no idea that anyone would be using > his language to solve that problem in that environment). On the other hand, the resource constraints may change dramatically when the program is moved to a different platform, and the programmer may not be aware of the change. Example: a version of a CAD program I developed on a 68K based machine used 'short' integers for flags and small loop counters. When the program was moved to a sparc, the "fast" short integers cost a lot more than the 32-bit ones since the compiler kept inserting logical ANDs to ensure the value stayed at 16 bits. Sure, eventually I typedef'ed loop counters as "fastints" and did conditional definition based on #ifdef sparc [I bet Herman would enjoy this level of performance twiddling], but the point is that I wouldn't want to change this for every machine the program was ever ported to. The point is, a program may be installed and run under resource constraints that were unknown to the programmer at the time the code was written. This argues for letting the language do the optimization without programmer intervention. -- Mike Bolotski VLSI Laboratory, Department of Electrical Engineering mikeb@salmon.ee.ubc.ca University of British Columbia, Vancouver, Canada
gl8f@astsun9.astro.Virginia.EDU (Greg Lindahl) (08/17/90)
In article <24294@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: >In article <1990Aug16.204409.4744@murdoch.acc.Virginia.EDU> gl8f@astsun7.astro.Virginia.EDU (Greg Lindahl) writes: >> >>Try this for an example: FORTRAN doesn't allow aliased arguments in >>subroutine calls. This allows FORTRAN compilers to make all sorts of >>nice optimizations. > >This example fits so obviously into scenario (3) that I feel I must >not have expressed myself at all clearly. Actually, it doesn't fit into #3 because a run-time check is available. But it's not what you say, it's what you mean. >Let's design FORTRAN++, a proper extension of FORTRAN. Legal FORTRAN >programs are compiled exactly the same way in FORTRAN++ as in FORTRAN, >including the optimizations that come from assuming no aliasing. But >in FORTRAN++, there is a subroutine declaration that tells the >compiler a given subroutine _can_ have aliased arguments. I think this would probably just have the effect of lulling programmers into thinking they can alias some of the time, so they'll screw up and alias at the wrong time, and the error will not be caught because no compiler provides run-time checks for aliasing. I also can't think of a single reason why you'd ever want to do aliasing of the type which is illegal. I don't like kitchen sink languages. If your FORTRAN optimizer deals with non-aliased arguments, it needs more smarts to deal with aliased arguments. Why make the compiler and language bigger just to deal with someone's brain-damaged coding style? >I have this silly idea that the programmer (at coding time) is better >at making decisions on how to write a particular program than is the >language designer at language-design time. I have the silly idea that programmers appreciate concise languages. How much money would you have me pay to my compiler writers just to add that "feature"? But what do I know, I just *use* the language we're talking about. -- "In fact you should not be involved in IRC." -- Phil Howard
new@ee.udel.edu (Darren New) (08/17/90)
In article <1990Aug16.213113@ee.ubc.ca> mikeb@salmon.ee.ubc.ca writes: >On the other hand, the resource constraints may change dramatically >when the program is moved to a different platform, and the programmer >may not be aware of the change. > >Example: [about C deleted] The problem here is not that the constraints changed, but that you did not express the constraints properly. A type def. of something as (say) a "fastint range 0 .. 1567" would let the compiler choose what is best: a short on a 68K and a long on a SPARC. (Doesn't Ada have something like this?) C does not let you express such constraints directly, and forces you to express them in terms of the machine hardware; C is obviously not the "Universal Language". -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware ---
cik@l.cc.purdue.edu (Herman Rubin) (08/18/90)
In article <1990Aug17.043940.3337@murdoch.acc.Virginia.EDU>, gl8f@astsun9.astro.Virginia.EDU (Greg Lindahl) writes: > In article <24294@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: > >In article <1990Aug16.204409.4744@murdoch.acc.Virginia.EDU> gl8f@astsun7.astro.Virginia.EDU (Greg Lindahl) writes: > >> > >>Try this for an example: FORTRAN doesn't allow aliased arguments in > >>subroutine calls. This allows FORTRAN compilers to make all sorts of > >>nice optimizations. This might allow the compiler to make nice optimizations, but not the programmer. > >This example fits so obviously into scenario (3) that I feel I must > >not have expressed myself at all clearly. > > Actually, it doesn't fit into #3 because a run-time check is > available. But it's not what you say, it's what you mean. You mean you have never deliberately used range violations which would cause what you wanted to do to be done, even though your language did not allow it? You did not deliberately violate types so that you could come up with a reasonable program for your machine? How did you get the binary representation of that floating point constant into your program? ........................ > I don't like kitchen sink languages. If your FORTRAN optimizer deals > with non-aliased arguments, it needs more smarts to deal with aliased > arguments. Why make the compiler and language bigger just to deal with > someone's brain-damaged coding style? > > >I have this silly idea that the programmer (at coding time) is better > >at making decisions on how to write a particular program than is the > >language designer at language-design time. > > I have the silly idea that programmers appreciate concise languages. > How much money would you have me pay to my compiler writers just to > add that "feature"? But what do I know, I just *use* the language > we're talking about. There are programmers and there are programmers. If you want to program something so that it takes hours to do a .1-second job because the language is inadequate to handle the ideas involved, you use one type. If you want to put something in a library, that type should not be used. Can you modify the program to take advantage of machine architecture? It is not necessary to pay much to have an extensible compiler; much of the optimization should be done at the assembler level, or interactively between the compiler and the programmer. Why should the compiler be asked to do all of the optimizing? One might wish to use totally different algorithms on different machines. This is a type of optimizing which the compiler cannot do, especially if it involves creating the programmer. A first-class programmer must be able to create what the language designers have not envisioned. Not every programmer will be first-class, but to leave something out because only the good programmers can use it can only produce mediocre programming. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet) {purdue,pur-ee}!l.cc!cik(UUCP)
willis@cs.tamu.edu (Willis Marti) (08/24/90)
In article <24279@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: [lots of other stuff deleted] >impossible in most non-recursive programs. The only programs where >non-recursion cannot be proven automatically are those which have a >recursive call in a section of code that will never be executed, but >where the compiler cannot prove that the code will never be executed. >Since such programs are almost guaranteed to be not what the >programmer intended, I feel confident in saying that non-recursion can >be automatically proven in correct non-recursive programs. Not true. In C, with pointers to functions; in assembler, with indirect jumps; in FORTRAN, with computed GOTOs -- there are MANY times a compiler can't "prove" the execution path of a program without running it. And some of those paths may use recursion, some may never use it. I feel you really have the choice of the language designer making some assumptions (i.e., forbidding some coding practices) or making a language that's either extremely verbose (can you say PL/1 or Ada? 8-) or provides zero checking... Programmers should choose an appropriate tool & not complain that their one tool doesn't have feature XYZ. Willis Marti