rlr@utastro.UUCP (Randy Ricklefs) (06/06/88)
We will soon start porting software from a number of different sources to a
micro-processor-based UNIX system. Most of the code is in various dialects
of FORTRAN. The question that arises is whether to convert all this stuff
to a more modern language, particularly c. This suggests several questions
which I hope the NET readers will help answer (without starting a 100-years
war on languages ... please! :-) ):
1) Are people actually initiating new projects in FORTRAN, or are they
maintaining and porting old FORTRAN code?
2) Does the answer to 1) change if we restrict discussion to PC's & Macs?
3) Is c a suitable replacement for FORTRAN in terms of mathematical capabil-
ities and portablility?
4) Are there reliable FORTRAN to c translators available under MS-DOS or UNIX
that will allow moving over to c without re-coding the world?
Thanks in advance for the help!
Randy
--
Randy Ricklefs
uucp: {ut-sally, ut-ngp, noao, charm}!utastro!rlr
arpa: rlr@utastro.UTEXAS.ARPA phone: (512) 471-1342jlg@beta.UUCP (Jim Giles) (06/07/88)
In article <2742@utastro.UUCP>, rlr@utastro.UUCP (Randy Ricklefs) writes: > We will soon start porting software from a number of different sources to a > micro-processor-based UNIX system. Most of the code is in various dialects > of FORTRAN. The question that arises is whether to convert all this stuff > to a more modern language, particularly c. This suggests several questions > which I hope the NET readers will help answer (without starting a 100-years > war on languages ... please! :-) ): C is not all that much more 'modern'. It was developed more recently. Fortran is a higher-level language than C (as admitted even by Ritchie). > 1) Are people actually initiating new projects in FORTRAN, or are they > maintaining and porting old FORTRAN code? Most code (new and old) in major scientifc computing environments is Fortran, even when C is available. Whether this is because Fortran is actually superior, or just programmer inertia is a qeustion that spurs that 100-years war you complained about. > 2) Does the answer to 1) change if we restrict discussion to PC's & Macs? I write Fortran code for PC's. I don't write C code for PC's. I prefer to write Modula-2 code for PC's. I like writing SmallTalk code for PC's, but the executables are too slow. I know some people who write Fortran exclusively - on PC's as elsewhere. > 3) Is c a suitable replacement for FORTRAN in terms of mathematical capabil- > ities and portablility? On UNIX and UNIX-like systems, the Fortran support library is written almost entirely in C. The only real problem with C is the lack of the concept of an array (such references are always turned into pointers). This makes some (admittedly rare) constructs difficult to do in C. > 4) Are there reliable FORTRAN to c translators available under MS-DOS or UNIX > that will allow moving over to c without re-coding the world? Depends on what you mean by 'reliable'. If your definition doesn't include efficiency as a requirement, there are probably some such tools. > Thanks in advance for the help! I'm afraid I didn't help much. Without specifics on the purpose and size of the code you want to move, I can't really advise you on the desirability of converting it. (Nor can anyone else.) J. Giles Los Alamos
jerry@violet.berkeley.edu ( Jerry Berkman ) (06/08/88)
In article <20008@beta.UUCP> jlg@beta.UUCP (Jim Giles) writes: >In article <2742@utastro.UUCP>, rlr@utastro.UUCP (Randy Ricklefs) writes: >> We will soon start porting software from a number of different sources to a >> micro-processor-based UNIX system. Most of the code is in various dialects >> of FORTRAN. The question that arises is whether to convert all this stuff >> to a more modern language, particularly c. >> 3) Is c a suitable replacement for FORTRAN in terms of mathematical capabil- >> ities and portablility? C is missing many useful intrinsics. I have trouble taking a language seriously for numeric computation if the language doesn't even know about absolute values, e.g.: x = abs(x); or signed numbers, e.g. x = +5; Both statements are illegal in C. And what about: i = j**k In C this becomes: i = pow( (double)j, (double)k); For that matter, how do you translate y = x**6 from FORTRAN to C? Most FORTRAN compilers will optimize this using only 3 multiplies. If you translate it to C as y = x*x*x*x*x*x, then there is a chance the compiler will do as well as FORTRAN, but I wouldn't bet on it. And if you use the translation y = pow(X,5.0), you have an out-of-line procedure call plus an expensive evaluation. Actually, C does not have a concept of intrinsic at all. In the FORTRAN statement: x = sqrt(y) you are guaranteed by the standard that the square root intrinsic is invoked (unless there is an external statement). By contrast, the C statement: x = sqrt(y); does not guarantee anything of the kind. A user defined function could be called, or "sqrt" could be a define. For sqrt(), this is not usually a problem. But I'd be a lot less sure of other names like acos or sinh. For that matter, since sqrt() is a FORTRAN intrinsics, I get an error message from any decent FORTRAN compiler for sqrt(integer). None from C of course (running lint is a hassle). Also, I like the semantics of sqrt() under FORTRAN better: on all FORTRAN systems I have used, if y = -1., the result is a fatal error. In C, it depends on what the library does. I have used C libraries which returned sqrt(abs(y)), others which return 0, and 4.3 BSD on a VAX returns the reserved operand. >On UNIX and UNIX-like systems, the Fortran support library is written >almost entirely in C. The 4.3 BSD math libraries for the VAX are written mostly in assembler. That the 4.3 BSD VAX FORTRAN I/O library is written in C using standard I/O may be why it is so slow. The VAX math library is about as fast as the VAX VMS math library while the BSD I/O library is up to 3 or 4 times as slow as the VAX VMS I/O library. Much of the Cray UNICOS math and I/O support libraries are written in assembler. - Jerry Berkman Central Computing Services, U.C. Berkeley jerry@violet.berkeley.edu
gil@limbic.UUCP (Gil Kloepfer Jr.) (06/08/88)
In article <2742@utastro.UUCP> rlr@utastro.UUCP (Randy Ricklefs) writes: |>We will soon start porting software from a number of different sources to a |>micro-processor-based UNIX system. Most of the code is in various dialects |>of FORTRAN. The question that arises is whether to convert all this stuff |>to a more modern language, particularly c. This suggests several questions |>which I hope the NET readers will help answer (without starting a 100-years |>war on languages ... please! :-) ): No problem...I hate those wars myself (being a fan of both languages!). |>1) Are people actually initiating new projects in FORTRAN, or are they |> maintaining and porting old FORTRAN code? Both. There are still a number of research groups who are solve mathematical problems in FORTRAN (simply because it's all they know). This code is many times proprietary, and the authors simply do not care to let anyone port the existing code. There are also a LOT of statistical (again mathematical) and graphics software in FORTRAN which is so large that it would be a great expense to port. It is therefore maintained (ported if the need is there). |>2) Does the answer to 1) change if we restrict discussion to PC's & Macs? Yes and no. It all depends on cost, although personally I would look more towards porting if I had the PC/Mac marketplace in mind. |>3) Is c a suitable replacement for FORTRAN in terms of mathematical capabil- |> ities and portablility? C can do almost anything. The question is with how much trouble. FORTRAN, in my book, handles mathematical stuff MUCH easier and clearly than C. As stated in a past net-debate (no flames please if it is slightly out of context), C lacks some of the array flexibility that FORTRAN has (although with FORTRAN, you need to know how big the arrays are, with C you can allocate memory at run-time). Once you have successfully ported a FORTRAN-based mathematical procedure to C, you can rest assured that the program is pretty-much portable (I am at a loss for a system it wouldn't be portable to). |>4) Are there reliable FORTRAN to c translators available under MS-DOS or UNIX |> that will allow moving over to c without re-coding the world? I have heard of some, but I haven't used any and don't know how well they work. |>Thanks in advance for the help! You're welcome. NOTE: The final decision on which language to use for your application should not rest on which is more "modern." There are FORTRAN compilers for almost every computer in existance nowadays. Whether you code in C or FORTRAN should rest in the application and what it does. Further, the conversion costs should be considered as well as portability when making the decision to convert. Standard (F77) FORTRAN that isn't I/O intensive will generally compile and run on any machine with the same compiler. There are people that still develop FORTRAN-based applications, but the number is decreasing because much of the mathematical stuff can be "black-boxed" (and possibly just that module written in FORTRAN), while the rest of the system (including file handling and user-interface) can be more easily (and elegantly) written in C. |> Randy Ricklefs uucp: {ut-sally, ut-ngp, noao, charm}!utastro!rlr |> arpa: rlr@utastro.UTEXAS.ARPA phone: (512) 471-1342 +------------------------------------+----------------------------------------+ | Gil Kloepfer, Jr. | Net-Address: | | ICUS Computer Group, Systems Dvlp. | {boulder,ihnp4,talcott}!icus!limbic!gil| | P.O. Box 1 | Voice-net: (516) 968-6860 | | Islip Terrace, New York 11752 | Othernet: limbic!gil@icus.UUCP | +------------------------------------+----------------------------------------+
grimlok@hubcap.UUCP (Mike Percy) (06/08/88)
From article <10655@agate.BERKELEY.EDU>, by jerry@violet.berkeley.edu ( Jerry Berkman ): > > C is missing many useful intrinsics. I have trouble taking a language > seriously for numeric computation if the language doesn't even know about > absolute values, e.g.: x = abs(x); or signed numbers, e.g. x = +5; x =+ 5 used to be an example of a C operator which is now x += 5. Most compilers I've used warned me about an obsolete operator or some such. Just write is as x = +5 rather than x =+5 and things should be fine. x = abs(x) is provided by virtually every math library. > For that matter, how do you translate y = x**6 from FORTRAN to C? For that matter, how do you translate *p %= 2 from C to FORTRAN? > For that matter, since sqrt() is a FORTRAN intrinsics, I get an error > message from any decent FORTRAN compiler for sqrt(integer). None from C > of course (running lint is a hassle). "Gosh Dad, why do those airline pilots have to run through that checklist, it's such a hassle" "Well, Beaver, if they didn't, they might miss some small detail that could cause a crash" "Geeee" > > Also, I like the semantics of sqrt() under FORTRAN better: on all > FORTRAN systems I have used, if y = -1., the result is a fatal error. > In C, it depends on what the library does. I have used C libraries > which returned sqrt(abs(y)), others which return 0, and 4.3 BSD on a > VAX returns the reserved operand. > Which is why you have the freedom to decide exactly what you want by redefining the function slightly, maybe with a #define. Also, if you like FORTRAN math stuff, why not call functions from a FORTRAN library. NAG comes to mind. It's easy enough to do. FORTAN does have an extreme advantage over C in one respect -- vectorizability (is that a word?) of certain things (some array processing for example). If I remember right, this was one of the things that noalias was supposed to help change.
eugene@pioneer.arpa (Eugene N. Miya) (06/09/88)
I have been asked to post this. Please send mail to him, not me. Thanks. --eugene ============mesg start=============== Some flames for thought ... I agree that Fortran is a somewhat primitive language and that a better language for scientific programming would be nice. I see two issues in making transition to something better. The first is the choosing of a suitable replacement language. The second is that of translating Fortran Dusty Decks. 1. Choice of Language I do lots of programming in both C and Fortran. I think C is not the answer. It's too low level. Multidimensioned arrays in C are hard to implement well and in a way that will be portable. One person's idea of how to implement multidimesioned arrays will differ from another's. Now try to write code that will handle both! YECH! Fortran 8X is not the answer. It's a "dirty" language (to put it mildly). This is my personal debatable opinion. The approch by the committee here seems to be "let's add stuff we think is neat and hope over the next 20 years that people decide on their own that they shouldn't use things like COMMON, EQUIVALENCE, and column oriented format." I don't see much chance of success in this approach. OK, How about Ada? I am _very_ new to this language but it seems to be able to handle much of what one might desire for scientific programming. Code writtin in Ada has a good chance of being portable. The problem with this language seems to be its complexity. It won't run nicely on a small (PC class) machine. I wonder whether a possible solution to this problem is to define a sublanguage of Ada for scientific computation. That is, maybe some features could be removed to make the language run on small machines and still be nice for scientific computation. Will removing the task handling and exception handling fix the complexity problem? 2. Tranlation What are the problem areas of tranlation of Fortran into other (more sane) languages (e.g., C, pascal, Ada)? A few problem areas I see are a. multidimensioned arrays. Fortran code is _often_ optimized to account for Fortran's columnwise storage of 2-D arrays. Pascal (and Ada, I assume) store rowwise. b. EQUIVALENCE c. COMMON Any more here? Matt Wette mwette%gauss@hub.ucsb.edu
jerry@violet.berkeley.edu ( Jerry Berkman ) (06/09/88)
This message is a reply to three of the people who commented on my previous message. wan@cory.Berkeley.EDU (Hank S. Wan) wants a FORTRAN type checker: > if FORTRAN is so great as in all the "RE: Should I convert FORTRAN code to C" > somebody must have a type checker so the following is not merrily accepted > by unix f77. > > PROGRAM bar > j = sub1( i ) > PRINT *, i, j > END > SUBROUTINE sub1( r ) > r = 1.0 > END > > lint would do the job for c code. (and NO, lint is not a hassle if you're > smart enough to use it often, and interpret the results right.) > Checking consistency in type is useful for any large project in any serious > language. Here is what IBM's VS FORTRAN, version 2, release 2 says about your sample program, when the ICA option is specified: VS FORTRAN VERSION 2 ENTERED. 13:04:37 **BAR** END OF COMPILATION 1 ****** **SUB1** END OF COMPILATION 2 ****** (W) CONFLICTING NAME USAGE -- THE NAME, SUB1, HAS BEEN REFERENCED AS A FUNCTION IN BAR(COMPILATION 1). IT IS DEFINED AS A SUBROUTINE IN SUB1(COMPILATION 2). (W) CONFLICTING TYPE - AT THE MAIN ENTRY TO SUBROUTINE, SUB1(COMPILATION 2), ARGUMENT NO. 1, "R", IS EXPECTED TO BE REAL*4; HOWEVER, BAR(COMPILATION 1), AT ISN 2 PASSES THIS ARGUMENT, "I", AS INTEGER*4. VS FORTRAN VERSION 2 EXITED. 13:04:40 Sorry, but it's not public domain. By the way, when you are asking for a type checker, you are commented on the implementation, not the language. If you want complete checking, try WATFOR77, which check not only for argument agreement, but also check subscripts, and for variables used before they are defined. Is there any C equivalent? swarbric@tramp.Colorado.EDU (Frank Swarbrick) comments: > To Jerry Berkman, > Gee, I just tried compiling x = +5; and x = abs(x); both in C and they both > worked. I just tried both on monet.berkeley.edu, where the most current distributed 4.3 BSD UNIX lives. The C compiler, given the program: main() { int i; i = +5; } comments: "junk.c", line 5: syntax error It may very well work in other compilers, and will probably be added in the new standard, but is not there now. > (Now I don't know why anyone would ever use x = +5, but I guess > that is not the point.) It could be output from a program which generates source code, or a person just likes symmetry. It does not seem unreasonable to ask a compiler to correctly compile it. As for "x = abs(x);", it does compile and load. However, it's calling a library function. What's wrong with that? (1) It's slow. (2) It returns the absolute value of integers. You can type it "float abs();" and it works on the VAX, but it may not work on all systems. The FORTRAN generic abs() which works on any numeric data type and generates in-line code is superior. grimlok@hubcap.UUCP (Mike Percy) says: >>> Also, I like the semantics of sqrt() under FORTRAN better: on all >> FORTRAN systems I have used, if y = -1., the result is a fatal error. >> In C, it depends on what the library does. I have used C libraries >> which returned sqrt(abs(y)), others which return 0, and 4.3 BSD on a >> VAX returns the reserved operand. >Which is why you have the freedom to decide exactly what you want by >redefining the function slightly, maybe with a #define. This makes it an act of faith in reading large programs as to what procedure calls do. I prefer intrinsics for common functions. - Jerry Berkman, U.C. Berkeley Computing Services jerry@violet.berkeley.edu
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/09/88)
The original poster was wondering if he should convert Fortran code to C. My answer to that is, not if you can get an adequate Fortran compiler for your system. If you think it would be useful, there is at least one automatic Fortran-to-C translator commercially available (Fortrix). If you plan to thoroughly revise your application (so that it amounts to a rewrite), you would be better off designing the replacement from scratch, and it might make sense to implement the replacement in C if you're not going to be dependent on EISPACK, IMSL, etc. Fortran's single biggest problem is that it has shitty support for data structures. If this doesn't bother you, then by all means continue to use Fortran. I think by now everyone who is likely to learn better techniques would have done so. It happens that many of our more interesting applications are primarily written in C, because Fortran is just too puny. And we do run them on our Crays as well as on small and medium sized systems. I find that with sufficient care, useful C code can be even more portable than Fortran, more efficient, and more maintainable. Of course with insufficient care, horrible code can be produced in ANY language. Use whatever tool seems right for the job and that you are comfortable using.
owen@wrs.UUCP (Owen DeLong) (06/09/88)
In article <2742@utastro.UUCP> rlr@utastro.UUCP (Randy Ricklefs) writes: >We will soon start porting software from a number of different sources to a >micro-processor-based UNIX system. Most of the code is in various dialects >of FORTRAN. The question that arises is whether to convert all this stuff >to a more modern language, particularly c. This suggests several questions >which I hope the NET readers will help answer (without starting a 100-years >war on languages ... please! :-) ): Ahh, Why not? Language wars are so much fun.... You get to tie up so many peoples telebits with such garbage, and everyone can flame you... :-) >1) Are people actually initiating new projects in FORTRAN, or are they > maintaining and porting old FORTRAN code? Some, but that's just because they haven't ported their programmers to c yet. >2) Does the answer to 1) change if we restrict discussion to PC's & Macs? Yes, more Mac and PC programmers have been ported to c than in the system 3 environment. (What, you mean someone besides IBM makes computers? :-) >3) Is c a suitable replacement for FORTRAN in terms of mathematical capabil- > ities and portablility? Absolutely not, for this, you need COBOL! :-)... Seriously, I wouldn't wish COBOL on my worst enemy. >4) Are there reliable FORTRAN to c translators available under MS-DOS or UNIX > that will allow moving over to c without re-coding the world? I haven't seen anything. There was a review of FORTRAN to LISP converters in Computer Language once, I think, and the author there basically said he hadn't seen any inter-language translator he found to be reliable. > >Thanks in advance for the help! > >Randy > I hope some of this is helpful, but I couldn't resist the opportunity to poke fun at a language that should have died before assembly was born. Owen Disclaimer: WRS won't give me execute access to cc yet.
swarbric@tramp.Colorado.EDU (Frank Swarbrick) (06/09/88)
To Matt Wette,
Am I totally missing something, or is this not a multidimentional array:
int array[10][15];
??
Certainly there are different ways of accessing them (as an array, as points,
or both at the same time), but they are all portable. If I have greatly
misunderstood something I'm sure I will get many corrections.
Frank Swarbrick (and, yes, the net.cat) swarbric@tramp.Colorado.EDU
...!{ncar|nbires}!boulder!tramp!swarbric
"...This spells out freedom, it means nothing to me, as long as there's a PMRC"swarbric@tramp.Colorado.EDU (Frank Swarbrick) (06/09/88)
(I am really wondering if this belongs in comp.lang.fortran at all, but I am
not sure if Jerry Berkman reads comp.lang.c. Sorry.)
Anyway, just because your outdated compiler doesn't compile x = +5 means only
that your compiler is outdated... Or maybe even buggy, as it should not really
think it means x =+ 5. And indeed, it doesn't, as it gave you a syntax error
instead of a warning saying you never initialized x. Or maybe C used to not
accept this format; I don't know.
Anyway, I'm not disagreeing that it's good that FORTRAN can generate differnt
things for x = abs(x) depending on whether or not x is float, int, or whatever.
It's just in C the compiler does not know what a function looks like. They
are just black boxes with a few restrictions. C was made this way for a
reason, and I like it. FORTRAN is different for a reason, and that's fine
too.
(Oh, by the way, if x is float or double use x = fabs(x);)
Frank Swarbrick (and, yes, the net.cat) swarbric@tramp.Colorado.EDU
...!{ncar|nbires}!boulder!tramp!swarbric
"...This spells out freedom, it means nothing to me, as long as there's a PMRC"mcdonald@uxe.cso.uiuc.edu (06/09/88)
I do believe that all this concern over functions in C is misplaced. There is a long list of math functions, which are essentially intrinsics - they can be put inline. Included are fabs,sin, cos, tan, asin, acos, atan, atan2(y,x), sinh, cosh, tanh, exp, log, log10, pow(x,y), sqrt, and a few lesser ones. These certainly CAN be made inline if the compiler is smart enough. On my PC, I found after a quick check that only fabs was inline, but I didnt test all of them. I am ASSUMING of course that you are talking about ANSI C . All this is in a quite non-controversial part of it. I asked about the x**2 translation some months ago and was informed that a compiler can transform pow(x,(double)2) into a single multiply instruction, if it is smart enough. Doug McDonald
walter@garth.UUCP (Walter Bays) (06/10/88)
jlg@beta.UUCP (Jim Giles) writes: >Most code (new and old) in major scientific computing environments is >Fortran, even when C is available. Whether this is because Fortran is >actually superior, or just programmer inertia is a question that spurs >that 100-years war you complained about. paolucci@snll-arpagw.UUCP (Sam Paolucci) writes: >Ah! Most major scientific computing environment use CRAYs as their >CPU. Do you know of a good C compiler on the CRAY that produces code >of somewhat comparable performance as CRAY's Fortran compilers? >There, I suggest, is part of the answer. I would venture that most C compilers have not produced code that is as fast as most Fortran compilers. And even as the computer industry continues doubling hardware performance, scientists like Jim Giles immediately use the new power by expanding the range of problems studied - and ask for more. Software efficiency will always be important to them. jlg@beta.UUCP (Jim Giles) writes: >Here you are putting the cart before the horse. There was no C compiler >for Crays until recently because there was no demand for it. The present >demand is almost entirely from within Cray and from other (non-scientific) >Cray customers. Again, whether this is from inertia or valid preference >is a combative issue. A chicken and egg problem. IF excellent C compilers had been available, would they have used them? Probably so. IF user demand had been present, would Cray (and others) have provided C compilers as fast as the best Fortran compilers? Probably not. C provides lower level primitives which a programmer can use to write fast code. So the worst C compilers are better than the worst Fortran compilers. But C's liberal assumptions about memory volatility and aliasing have interfered with many optimizations that are fairly easy to do on Fortran. So the best Fortran compilers are better than the best C compilers. Hence we have ANSI C and the battles over volatile (in the language) and noalias (rejected). Chris Torek captured the essence of the 'volatile' debate in many dozens of notes. If you personally have no use for 'volatile', but would like to see C displace Fortran (perhaps to protect yourself from having to use Fortran :-), read Chris' entire note. chris@mimsy.UUCP (Chris Torek) writes (Subject: volatile: a summary): >Is the [volatile] keyword necessary? >No. (As an existence proof, consider compilers that do not now have >the keyword. Most of them work by not doing much in the way of >optimisation. There is more to it, though.) > Summary of the summary: >Is the concept necessary? Yes. >Is the keyword necessary? No. >Is the keyword useful? Yes. >Is the keyword a `good thing'? Opinion: yes. jlg@beta.UUCP (Jim Giles) continues: >I use Fortran mostly because I know how to use it WELL. To some >extent, the lack of detailed knowledge of C is my reason for not using >it. (For example: why is 'a+=b' faster than 'a=a+b'? Seems to me that >the two are identical and should generate the exact same code.) ... If you're a Fortran programmer and have not tried C because you KNOW its' too slow, look again. Many C compilers have been getting much better, even before ANSI. Any good compiler will generate the same code for those constructs. There's a lot of folk wisdom about how to get around the pcc code generator and write fast C code. (Absolutely essential to such things as writing systems code.) Unfortunately, much of this wisdom is counter-productive today, because it obfuscates the code and interferes with the work of the optimizer. (Example: indiscriminate 'register' declarations steal from the compiler's pool of allocatable registers.) swarbric@tramp.Colorado.EDU (Frank Swarbrick) writes: >As for C not generating inline code for stuff like x = pow(x, 2); that is >just not "C's way." It has been discussed a lot in comp.lang.c. Some people >think C should generate inline code for it, and some do not. So far, it >doesn't. C compilers are starting to do more procedure inlining. The widespread use of the Dhrystone benchmark has accelerated this trend, since inlining strcpy() and strcmp() produce much higher Dhrystone numbers. (The Dhrystone rules forbid inlining, but many people only care that the program executes correctly - and don't care what the compiler does.) On some RISC CPU's (not ours) multiplication is a procedure call that is sometimes inlined. Who cares? That affects performance, certainly, but the bottom line of performance is all that matters. jlg@beta.UUCP (Jim Giles) provides an appropriate postscript: >Fortran does some things better, C does others, and both contain deficiencies. -- ------------------------------------------------------------------------------ I said it, not them. E-Mail route: ...!pyramid!garth!walter (415) 852-2384 USPS: Intergraph APD, 2400 Geng Road, Palo Alto, California 94303 ------------------------------------------------------------------------------
mat@emcard.UUCP (Mat Waites) (06/10/88)
In article <6551@sigi.Colorado.EDU> swarbric@tramp.Colorado.EDU (Frank Swarbrick) writes: > > Am I totally missing something, or is this not a multidimentional array: >int array[10][15]; >?? I think the problem is with variable size multidimensional arrays. It's hard(er) to write functions in C to handle multidimensional arrays of varying size. People have come up with wacky techniques for doing it, but if there is no standard way, it's difficult to use in standard libraries, etc. Mat -- W Mat Waites | PHONE: (404) 727-7197 Emory Univ Cardiac Data Bank | UUCP: ...!gatech!emcard!mat Atlanta, GA 30322 |
bobal@microsoft.UUCP (Bob Allison) (06/10/88)
In article <2742@utastro.UUCP> rlr@utastro.UUCP (Randy Ricklefs) writes: >1) Are people actually initiating new projects in FORTRAN, or are they > maintaining and porting old FORTRAN code? >2) Does the answer to 1) change if we restrict discussion to PC's & Macs? I'd say that on PCs most of the stuff going on is porting. But that is because there is a lot of stuff on mainframes which people want to run on PCs and are finally getting the horsepower to do. I was actually surprised by how much new development is going on. >3) Is c a suitable replacement for FORTRAN in terms of mathematical capabil- > ities and portablility? Plenty of other postings arguing this issue. I will just toss in my opinion that you'll almost always get better execution time on a FORTRAN program than a comparable C program (see my next posting). >4) Are there reliable FORTRAN to c translators available under MS-DOS or UNIX > that will allow moving over to c without re-coding the world? > I've seen some ads in typical PC magazines. Buy a few and take a look. But be skeptical: call them up, ask them hard questions. Most of them will require at least some user intervention. Almost all of them generate crummy source, which you practically have to rewrite before you can do any serious maintenance. Be prepared to do some debugging. All of this boils down to: how much are you willing to invest to move to a "modern" language? Is execution speed important? What are the real reasons for switching? Are you going to have to maintain this later? Try to figure out the economics of the effort, then decide. How much time/effort/money are you going to save down the road by investing a bunch of it now? It might be better to spend the time doing something else. >Thanks in advance for the help! > We're always willing to offer opinions when it isn't our project :-)
karl@haddock.ISC.COM (Karl Heuer) (06/11/88)
In article <10681@agate.BERKELEY.EDU> jerry@violet.berkeley.edu (Jerry Berkman) writes: >By the way, when you are asking for a type checker, you are commented on the >implementation, not the language. I'm glad you were the one to bring that up. Many of the issues you raise are not intrinsic to the language, either. >If you want complete checking, try WATFOR77, which check not only for >argument agreement, but also check subscripts, and for variables used >before they are defined. Is there any C equivalent? Yes, it's my understanding that some implementations of C have this. I haven't used them (though I've often threatened to write one). Certainly the language doesn't forbid it. >As for "x = abs(x);", it does compile and load. >However, it's calling a library function [which is slow]. That's an implementation issue. The better C compilers generate inline code. >(2) It returns the absolute value of integers [only]. The floating-point version is named fabs(). If you want to argue whether a single generic name is better than a family of typed functions, fine; but I think that the issue you raised (existence) is closed. >grimlok@hubcap.UUCP (Mike Percy) says [about the semantics of sqrt(-1.0)] >>Which is why you have the freedom to decide exactly what you want by >>redefining the function slightly, maybe with a #define. > >This makes it an act of faith in reading large programs as to what >procedure calls do. I prefer intrinsics for common functions. Mike Percy has fallen victim to a common misconception. The user does not have the guaranteed freedom to redefine standard functions. (It may happen to work; this is also true in FORTRAN.) The standard functions in C are quite analogous to the intrinsics of FORTRAN. (Note: "analogous" does not mean "identical".) Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
karl@haddock.ISC.COM (Karl Heuer) (06/11/88)
I really don't want to continue this cross-posted discussion, but I'd like to comment on the multi-dimensional array issues. In article <10032@ames.arc.nasa.gov> mwette%gauss@hub.ucsb.edu (Matt Wette) writes: >Multidimensioned arrays in C are hard to implement well and in a way that >will be portable. Since we're talking about FORTRAN conversion, the straightforward solution is to use the array notation supplied by the C language: "float a[3][5]". The only major problem is that FORTRAN allows an array parameter to be declared with a nonconstant dimension; to render the equivalent code in C (unless you have Gnu's gcc) requires explicit subscript calculation. (This is no less efficient than in FORTRAN, but it is tedious to write. A macro can be helpful.) >Fortran code is _often_ optimized to account for Fortran's columnwise storage >of 2-D arrays. Pascal (and Ada, I assume) store rowwise. No problem. You translate the FORTRAN expression A(J,I) into the C expression a[i][j], or its Pascal or Ada equivalent. (This is assuming your translator knows which parens are arrays rather than function calls.) Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
smryan@garth.UUCP (Steven Ryan) (06/11/88)
Another big problem is that Fortran programs run like a bat out of hell with a good compiler. It is hard to convince people to give up the performance for (?)ephermal advantages of maintainablity.
dc@gcm (Dave Caswell) (06/11/88)
In article <225800036@uxe.cso.uiuc.edu> mcdonald@uxe.cso.uiuc.edu writes:
.
.I do believe that all this concern over functions in C is misplaced.
.atan, atan2(y,x), sinh, cosh, tanh, exp, log, log10, pow(x,y), sqrt,
.and a few lesser ones. These certainly CAN be made inline if the compiler
.is smart enough. On my PC, I found after a quick check that only fabs
.was inline, but I didnt test all of them. I am ASSUMING of course that
Is it true that some compilers generate inline code for strcpy, fabs
and a host of other functions? How does the compiler know that I will
be linking with the standard library? Does ANSI C allows compilers to
"know" what these functions mean? I wasn't aware that any of those functions
were part of the C language. Specifically, does my SUN cc reserve any of
these symbols?
Please respond by email.
--
Dave Caswell
Greenwich Capital Markets uunet!philabs!gcm!dc
If it could mean something, I wouldn't have posted about it! -- Brian Casegwyn@brl-smoke.ARPA (Doug Gwyn ) (06/13/88)
In article <522@white.gcm> dc@white.UUCP (Dave Caswell) writes: >How does the compiler know that I will be linking with the standard library? >Does ANSI C allows compilers to "know" what these functions mean? >I wasn't aware that any of those functions were part of the C language. ANSI C distinguishes between "freestanding" and "hosted" implementations. (How you invoke either of these depends on the particular implementation; it's beyond the scope of the Standard for it to specify this.) A Standard-conforming hosted implementation provides a comfortably large set of standard library functions, and furthermore these external names are all reserved for the implementation. Therefore the compiler is free to treat the standard library functions as intrinsics whenever that would make sense. The lack of a standard library for hosted applications was one of the most glaring deficiencies in existing practice and thus one of the first things X3J11 decided to fix. (Actually /usr/group made a start on this.)
shenkin@cubsun.BIO.COLUMBIA.EDU (Peter Shenkin) (06/13/88)
In article<10032@ames.arc.nasa.gov> eugene@pioneer.UUCP (Eugene N. Miya) writes: > >I have been asked to post this. Please send mail to him, not me. [ note: "him" is: Matt Wette mwette%gauss@hub.ucsb.edu ] > ...I see two >issues in making transition to something better. The first is the >choosing of a suitable replacement language. The second is that of >translating Fortran Dusty Decks. > >1. Choice of Language > > Multidimensioned arrays in C are hard to >implement well and in a way that will be portable. One person's idea >of how to implement multidimesioned arrays will differ from another's. >Now try to write code that will handle both! YECH! Just on this issue, I wonder what other numerikers in the audience think of Press et al's solution to this problem, given in "Numerical Recipes in C", Wiley, 1988. To make a long story short, they supply a routine: float **matrix( int nrl, int nrh, int ncl, int nch ) which uses dope vectors to dynamically allocate a 2-dimensional array of floats with range [nrl...nrh][ncl...nch]. They also supply similar routines for double-precision and integer matrices (called dmatrix() and imatrix() ), and the corresponding "free" routines. They do a similar thing for vectors, and obviously an extension of this approach using varargs -- or whatever the hell it's called in the draft ANSI standard :-) -- could easily be accomplished for arbitrary dimensionality. This is, in Matt's words, just "one person's idea of how to implement multidimensioned arrays", but it seems like a reasonable one. The reason for raising this issue here on the net is simply that if we who do write numerical code in C (for better or for worse!) were to standardize on this practice, we could better understand each others' code (or at least this part of it!) For the record, this generalizes to the following: float **array( int Ndim, int n1l, int n1h, int n2l, int n2h, ..., int nNl, int nNh ) /* allocate an N-dimensional array of floats with range * [n1l, n1h][n2l,n2h]...[nNl,nNh] */ void free_array( float **ar, int Ndim, int n1l, int n1h, int n2l, int n2h, ..., int nNl, int nNh ) /* free array allocated with array() */ Then we also would have the following routines: int **iarray() /* allocate an N-dimensional array of ints.... */ double **darray() /* allocate an N-dimensional array of doubles.... */ and the corresponding free routines. Of course, we could then have: #define vector( NL,NH ) array( 1, (NL), (NH) ) #define matrix( NRL,NRH,NCL,NCH ) array( 2, (NRL), (NRH), (NCL), (NCH) ) and perhaps even (for "real" C programmers): #define vector0( N ) array( 1, 0, (N) ) #define matrix0( NR,NC ) array( 2, 0, (NR), 0, (NC) ) ...and so on. All presumably in some header file with a name like "arrays.h". Any thought on this? ("Numerical analysts of the world, unite....") -- ******************************************************************************* Peter S. Shenkin, Department of Biological Sciences, Columbia University, New York, NY 10027 Tel: (212) 280-5517 (work); (212) 829-5363 (home) shenkin@cubsun.bio.columbia.edu shenkin%cubsun.bio.columbia.edu@cuvma.BITNET
greg@csanta.UUCP (Greg Comeau) (06/13/88)
>> Gee, I just tried compiling x = +5; it worked. > i = +5; >comments: > "junk.c", line 5: syntax error >It may very well work in other compilers, and will probably be added in >the new standard, but is not there now. If an old compiler accepts this it is probably just being lazy for some reason. Since C does not have a unary plus, it should be a syntax error. Note that the ANSI draft does allow a unary plus now though since "hey, there's a unary minus so let's at least be consistent". Also, at one time ANSI did apply a binding characteristic to the unary plus applied to parenthised expression (say: a + +(b + c) if I recall), but that has since been withdrawn.
kjartan@raunvis.UUCP (Kjartan Pierre Emilsson Jardedlisfraedi) (06/13/88)
Now here there seems to be a little misunderstanding. I have never
understood why Fortran users keep saying that array indexing is awkward
in C. This is probably because they find the idea of having to allocate
memory for an array rather repulsive. I remember that when I made
the change from Fortran to C, I thought that the memory allocation
routine malloc() was only intended for compiler designers and other
computer wizards. But one quickly finds out that allocating memory
for whatever you are doing is not only simple but also helps you a lot
in keeping the whole program under control, since you have to have in
mind a clear image of all your variables.
For people that frequently use the same sort of data structures, e.g
two dimensional double precision array, it is a simple task to write
a little subroutine wich handles the allocation. For this particuliar
data structure, the subroutine is basically a one-liner:
double **Create2DArray(w,h)
int w,h;{ double **r;
for(r=(double**)calloc(h,sizeof(*r));h-->0;r[h]=(double*)calloc(w,sizeof(**r)));
return(r);}
This may look very cryptic but then you only write it once anyway! A small
extension of the routine above could handle multidimensional array of
arbitrary dimensions and arbitrary data structures.
If the array had been initialized with Create2DArray() then indexing
would be just as normal,i.e:
DoSomething(array,m,n)
double **array;
int m,n;
{
...
array[ i+k ][ j-i ]= 1.0;
...
}
More generally: if an array is initialized with arbitrary dimensions, its
indexing is exactly as in FORTRAN, and can be passed to functions in exactly
the same manner (that is by pointers, which in this case is simply the array
name).
I personally made the change from FORTRAN to C one year ago, and today I
do not regret it , though there came times when I wanted to do some really
mean things to that stupid computer. I haven't completely given up
FORTRAN though, as there are still many libraries in FORTRAN around here, but I
simply build jacket routines for them (i.e routines which interface calling
conventions of two different languages) with the JBL utility. In that way
I don't have to write anything in FORTRAN but I still can use all the
available FORTRAN subroutines. Knowing that FORTRAN calls everything by
reference and C calls everything by value, it is easy to pass the arguments
from the C program in such a way that the only interfacing you need to do is
converting the pre-underscored C routine function name to the upper-case
FORTRAN name.
I think that the C offers two qualities that makes it a very comfortable
scientific programming language:
i) Argument are passed by value, which translates to
the fact that to let a subroutine change a variable
you have to specify it (by passing its adress). This
makes subroutines more like real mathematical operators
which have a very definite input and a very definite
output. This is really a psychological quality, but I
think that it has its effect in organizing your program
(a What You Get Is What You Asked For quality).
ii) You can define your own data structures, which can be any
combination of system defined structures and user defined
structures, array of structures, self-referential
structures and so on. This I think is perhaps the most
interesting quality and probably anyone who has done some
mathematics will appreciate the fact that most complex
problems can be made simpler by a suitable change of
formalism which most often is a change of data structure
with accompagnment of new operators acting on these
structures. For example if you are working in
4-dimensional space you simply define the data structure
4-vector and then proceed to write the basic operators
that you are going to need (DotProduct(vector1,vector2)
,Add(vector1,vector2),Scale(scalar,vector), and so on).
Quickly you will see that your program is talking the
same mathematical language as you are, and program
writing then becomes a real FORmula TRANslation!
This is not meant as an artillery in the Language Wars, but rather as an
explanation and maybe a clarification for those who haven't had any special
experience with C ,and still think that indexing doesn't exist in C and that
C is bad because it doesn't have the complex data type!
Say it in any language you like, but say it clearly!
...........................................................................
"If you don't like what your left hemisphere thinks, shoot if off."
Kjartan Pierre Emilsson, Iceland.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~tps@chem.ucsd.edu (Tom Stockfisch) (06/14/88)
In article <522@white.gcm> dc@white.UUCP (Dave Caswell) writes: >Is it true that some compilers generate inline code for strcpy, fabs >and a host of other functions? How does the compiler know that I will >be linking with the standard library? The scheme used by the compiler on our machine (Celerity 1260D) is to enable inlining only if the library loader flag is given in the command for *compiling* (not just linking). E.g., to get in-line exp(), fabs(), etc., compile as cc -c foopack.c -lm cc main.o foopack.o -lm If you want to define your own fabs(), etc., then compile as cc -c foopack.c cc main.o foopack.o -lm Considering the viability of this scheme (that does not require reservation of any library names) and the undesirability of ecologically disastrous name-space pollution, does anyone know why the ANSI C committee chose to reserve all these names? -- || Tom Stockfisch, UCSD Chemistry tps@chem.ucsd.edu
henry@utzoo.uucp (Henry Spencer) (06/15/88)
> C is missing many useful intrinsics. I have trouble taking a language > seriously for numeric computation if the language doesn't even know about > absolute values, e.g.: x = abs(x); or signed numbers, e.g. x = +5; > Both statements are illegal in C. Curious, my compiler compiles the first one just fine :-). The second is admittedly a bit of a nuisance, but hardly a disaster. In any case X3J11 has fixed both: abs is one of the potentially-intrinsic functions defined in the standard, and unary plus is provided. > [Much moaning and groaning about the lack of exponentiation, an operator > whose general case is (a) notoriously hard to define well, and (b) very > seldom used.] > Actually, C does not have a concept of intrinsic at all. X3J11 (ANSI-to-be) C does. > (running lint is a hassle). Ah, we come to the heart of it: the man wants to convert to C without having to learn anything new, go to any trouble, or buy modern compilers. My nose bleeds for him. -- Man is the best computer we can | Henry Spencer @ U of Toronto Zoology put aboard a spacecraft. --Von Braun | {ihnp4,decvax,uunet!mnetor}!utzoo!henry
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/15/88)
In article <238@chem.ucsd.EDU> tps@chem.ucsd.edu (Tom Stockfisch) writes: >Considering the viability of this scheme (that does not require >reservation of any library names) and the undesirability of >ecologically disastrous name-space pollution, does anyone know >why the ANSI C committee chose to reserve all these names? Three things. First, the Standard cannot mandate an approach such as you described. Such invocation details are not within the proper scope of the Standard. Second, X3J11 has been quite aware of name space pollution issues and has carefully limited the extent to which a C implementation can infringe on the application's name space, for the first time in history. Third, many C library routines are most conveniently implemented if they are allowed to call other standard library routines. The simplest way to enable that is to reserve ALL the standard names for the implementation. As an application programmer I think this is the correct approach. I do not WANT an application to replace a standard library routine with one of its own. That way lies danger.
16012_3045@uwovax.uwo.ca (Paul Gomme) (06/15/88)
In article <6551@sigi.Colorado.EDU>, swarbric@tramp.Colorado.EDU (Frank Swarbrick) writes: > Am I totally missing something, or is this not a multidimentional array: > int array[10][15]; > ?? Try that sort of thing under MS-DOS, with a _BIG_ matrix -- try something like: int array[200][200]; I've tried this sort of thing with Turbo C, and know someone who checked out MSC for me. The compiler choked on it because the array exceeds 64K. However, I've used a Fortran compiler which will let me create such matricies with absolutely no complaint. ------------------------------------------------------------------------- Paul Gomme E-Mail: Department of Economics University of Western Ontario Bitnet: p.gomme@uwovax.bitnet London, Ontario, Canada p.gomme@uwovax.uwo.ca N6A 5B7 (519) 679-2111 ext. 6418
faustus@ic.Berkeley.EDU (Wayne A. Christopher) (06/16/88)
The best reason NOT to allow a compiler to expand standard functions in-line is that you can't substitute your own to fix a bug in the standard version. I've had to do this a number of times with bug-prone functions like floor() (too many versions round towards zero instead of down). Wayne
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/16/88)
In article <3946@pasteur.Berkeley.Edu> faustus@ic.Berkeley.EDU (Wayne A. Christopher) writes: >The best reason NOT to allow a compiler to expand standard functions in-line >is that you can't substitute your own to fix a bug in the standard version. >I've had to do this a number of times with bug-prone functions like floor() >(too many versions round towards zero instead of down). NO NO NO -- Don't do this! Assuming for the sake of argument that some implementation has a floor() function like that, it is quite possible that some of the other math library routines actually depend on that behavior. If you change it, you will break other routines in possibly subtle ways. A much better solution to this particular problem would be: #define Floor my_floor /* or "floor", if it works right */ extern double Floor(double); /* ... use "Floor" instead of "floor" ... */ double my_floor(register double x) /* adjust for floor() bug */ { extern double floor(double); /* from math library */ register double xf = floor(x); return x >= 0 ? xf : x == xf ? x : xf - 1; } Also report the floor() bug to the library implementor.
chpf127@ut-emx.UUCP (J. Eaton) (06/17/88)
In article <224@raunvis.UUCP>, kjartan@raunvis.UUCP (Kjartan Pierre Emilsson Jardedlisfraedi) writes: > > [stuff deleted about dynamic memory allocation] > > For this particuliar > data structure, the subroutine is basically a one-liner: > > double **Create2DArray(w,h) > int w,h;{ double **r; > for(r=(double**)calloc(h,sizeof(*r));h-->0;r[h]=(double*)calloc(w,sizeof(**r))); > return(r);} > > This may look very cryptic but then you only write it once anyway! Yes, perhaps, but you (and, most likely, someone else) will have to read it more than once. Will that future reader be able to quickly grasp what is being done (especially if that future person is a scientific "programmer")? > Say it in any language you like, but say it clearly! I agree. > Kjartan Pierre Emilsson, Iceland. J. Eaton UT Dept of Chemical Engineering Practice what you preach.
chpf127@ut-emx.UUCP (J. Eaton) (06/17/88)
In article <224@raunvis.UUCP>, kjartan@raunvis.UUCP (Kjartan Pierre Emilsson Jardedlisfraedi) writes: > > I personally made the change from FORTRAN to C one year ago, and today I > do not regret it , though there came times when I wanted to do some really > mean things to that stupid computer. I don't understand this idea of refusing to write code in more than one language. Why not write in whatever language is most convenient for the job at hand? I use mostly Fortran because there are a lot of numercial libraries available that I simply don't care to rewrite or translate to another language. However, I don't object to C or any other language (except BASIC :-) if it fits the requirements of the job... > I haven't completely given up > FORTRAN though, as there are still many libraries in FORTRAN around here, but > I simply build jacket routines for them (i.e routines which interface calling > conventions of two different languages) with the JBL utility. In that way > I don't have to write anything in FORTRAN but I still can use all the > available FORTRAN subroutines. Knowing that FORTRAN calls everything by > reference and C calls everything by value, it is easy to pass the arguments > from the C program in such a way that the only interfacing you need to do is > converting the pre-underscored C routine function name to the upper-case > FORTRAN name. But I DO object to this. At the present time, multilanguage programming is NOT a good idea. AVOID it if at all possible. It makes porting to new environments especially difficult, if not impossible in many cases. Fortran may not be your favorite, and C isn't perfect either, but mixing the two is bound to cause trouble for you or someone else in the future. The whole world is not VM/CMS, COS, NOS/VE, VMS, or even 4.3 BSD. Moving a program which contains only Fortran or only C from any one of those environments to another is hard enough. Don't make it any more difficult by mixing in a load of interface routines which are system dependent! This will make moving your code to new machines/operating systems such a pain in the ass that very few will even give it a second thought. Of course, if you really want your code to die with the machine it was written for, disregard the above. > Say it in any language you like, but say it clearly! I still agree, just say it in one at a time. > Kjartan Pierre Emilsson, Iceland. J. Eaton UT Dept of Chemical Engineering And old machines really do die. Just ask any old CDC 6600. What? You're still using one? Oh. Sorry. Maybe machines ARE forever.
firth@sei.cmu.edu (Robert Firth) (06/17/88)
The following code, contributed by a C programmer, allocates dynamic memory for a two-dimensional array: > For this particuliar > data structure, the subroutine is basically a one-liner: > > double **Create2DArray(w,h) > int w,h;{ double **r; > for(r=(double**)calloc(h,sizeof(*r));h-->0;r[h]=(double*)calloc(w,sizeof(**r))); > return(r);} Any Fortran programmer who seriously proposes to convert to C would, in my opinion, be advised to study this example very carefully. Verbum sapienta sufficit.
jlg@beta.lanl.gov (Jim Giles) (06/18/88)
In article <224@raunvis.UUCP>, kjartan@raunvis.UUCP (Kjartan Pierre Emilsson Jardedlisfraedi) writes: > Now here there seems to be a little misunderstanding. I have never > understood why Fortran users keep saying that array indexing is awkward > in C. > [...] Awkward isn't the problem. I don't like the double bracket notation, but anyone can write a macro to turn ARRAY(i,j,k) into array[i][j][k]. The Problem is that 2-d arrays are not optimizable because they are immediately turned into pointer-to-pointer-to-data type of constructs. > If the array had been initialized with Create2DArray() then indexing > would be just as normal,i.e: > > DoSomething(array,m,n) > double **array; > int m,n; > { > ... > array[ i+k ][ j-i ]= 1.0; > ... > } If your use of array here is in a loop (that might otherwise be vector- izable), the C compiler can't vectorize it because a pointer-to-pointer 'may' contain a vector dependency - the compiler doesn't know it's a 2-d array! (If you don't have a vector machine, the problem still exists, you can't unroll the loop for a pipelined archetecture because of the same possible dependency.) This problem is the reason that so much discussion on this news group has recently been about 'noalias' in C (not exactly an appropriate topic for comp.lang.fortran, but relevent to this particular issue anyway). > [...] > ii) You can define your own data structures, which can be any > combination of system defined structures and user defined > structures, array of structures, self-referential > structures and so on. [...] This capability is NOT an adequate replacement for the complex data type. Complex is more than just a pair of reals, there are several operations defined on complex (like plus) which should work naturally. No use of C programming constructs can do this: COMPLEX CVAR REAL RVAR INTEGER IVAR ... CVAR=(CVAR+RVAR)*IVAR ... The operations (including the mixed-mode type conversions) are all done IN-LINE and efficiently. C provides no way to even do this calculation without function calls. > This is not meant as an artillery in the Language Wars, but rather as an > explanation and maybe a clarification for those who haven't had any special > experience with C ,and still think that indexing doesn't exist in C and that > C is bad because it doesn't have the complex data type! Clarifications which contain false or misleading information don't clarify anything. In fact, such 'clarifications' DO add to the Language Wars in very unproductive ways. J. Giles Los Alamos
smryan@garth.UUCP (Steven Ryan) (06/18/88)
First of all I agree with Dijkstra with respect to Fortran. I feel the challenge designing a new language that can be Fortran at its own game, which C does not do. > Now here there seems to be a little misunderstanding. I have never >understood why Fortran users keep saying that array indexing is awkward >in C. This is probably because they find the idea of having to allocate >memory for an array rather repulsive. A Fortran compiler is permitted to allocate all arrays statically, before compilation, and many do this. Also Fortran subroutine are not required to be recursive and hence do not need a procedure frame. All allocation can be done in the compiler and the runtime overhead can be zero. Also it is easy for programmer to modify the array base address to implement nonzero lower bounds. It is also easy for the compiler. I suspect Fortran programmers know alot less about dope vectors biased base addresses and that ilk than C programmers (scientists and engineers vs. computer science and system programmers). > i) Argument are passed by value, which translates to > the fact that to let a subroutine change a variable > you have to specify it (by passing its adress). And simplifies defined/referenced detection for an optimiser. > ii) You can define your own data structures, Apparently some Fortran programmers equivalence different typed arrays to create structures (shudder). Nature is immacuately fair and implacably cruel -- Sara James.
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/18/88)
In article <5917@aw.sei.cmu.edu> firth@bd.sei.cmu.edu.UUCP (Robert Firth) writes: >Any Fortran programmer who seriously proposes to convert to C would, in >my opinion, be advised to study this example very carefully. They would be much better off studying literate code.
rrr@naucse.UUCP (Bob Rose ) (06/20/88)
In article <20340@beta.lanl.gov>, jlg@beta.lanl.gov (Jim Giles) writes: > In article <224@raunvis.UUCP>, kjartan@raunvis.UUCP (Kjartan Pierre Emilsson Jardedlisfraedi) writes: > > Now here there seems to be a little misunderstanding. I have never > > understood why Fortran users keep saying that array indexing is awkward > > in C. > > [...] > > Awkward isn't the problem. I don't like the double bracket notation, > but anyone can write a macro to turn ARRAY(i,j,k) into array[i][j][k]. > The Problem is that 2-d arrays are not optimizable because they are > immediately turned into pointer-to-pointer-to-data type of constructs. Ok, what gives. Some else post the following code (not exact but close enough) real a(5,2) ... call foo(a) ... end subroutine foo(a) real a(10) ... Now doesn't the following c code work to do the same double a[2][5] /* <-- note [2][5] not [5][2] */ ... foo(a) ... } void foo(a) double a[10] { If it is not the same, would someone please post or email a counter example. I would like to see what is wrong. Note there are problems if you dynamicly allocate arrays but you cannot dynamicly allocate arrays in fortran so this is a void arguement. -bob
g-rh@cca.CCA.COM (Richard Harter) (06/20/88)
In article <738@naucse.UUCP> rrr@naucse.UUCP (Bob Rose ) writes: >In article <20340@beta.lanl.gov>, jlg@beta.lanl.gov (Jim Giles) writes: >> Awkward isn't the problem. I don't like the double bracket notation, >> but anyone can write a macro to turn ARRAY(i,j,k) into array[i][j][k]. >> The Problem is that 2-d arrays are not optimizable because they are >> immediately turned into pointer-to-pointer-to-data type of constructs. >Ok, what gives. Some else post the following code (not exact but close enough) > > real a(5,2) > ... > call foo(a) > ... > end > > subroutine foo(a) > real a(10) > ... My example, but this isn't the right context. This code was posted in response to someone proposing a macro which would produce the following C code: double **a; a = (double **)malloc(2 * sizeof(double *)); for (i=0;i<2;i++) a[i] = (double *)malloc(5 *sizeof(double)); which is not the same thing at all as your example. However the quoted statement is not, as far as I know, correct. Two dimensional arrays in C are not pointer to array constructs. >Now doesn't the following c code work to do the same > double a[2][5] /* <-- note [2][5] not [5][2] */ > ... > foo(a) > ... > } > > void foo(a) > double a[10] > { Yes, it does. However in fortran you can do the following real a(10) ... call foo(a,2,5) call foo(a,5,2) ... subroutine foo(a,m,n) real a(m,n) ... This is what fortran users mean when they talk about variable dimensioning; all it really means is that the compiler will generate address calculations for arrays using variables as well as constants. You can do this by hand, but it is much more convenient if the compiler will do it for you. As far as I know, there is no good reason why this feature could not be added to C. The discussion revolves around ways to fake it in C, using preprocessor tricks. They all look kludgy to me. >Note there are problems if you dynamicly allocate arrays but you cannot >dynamicly allocate arrays in fortran so this is a void arguement. This is not quite right, but it is close enough for practical purposes. The correct statements are: (1) Does the language provide intrinsic dynamic storage allocation. Answer: Intrinsic dynamic storage allocation is not a part of either language. (2) Does the standard support environment include a dynamic storage allocator? Answer: C does, fortran doesn't. (3) Given a dynamic storage allocator, does the language permit use of it? Answer: The C language provides a convenient portable means for doing so. It can be done in fortran, but the means are not as convenient and cannot be guaranteed to be portable. -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.
mouse@mcgill-vision.UUCP (der Mouse) (06/20/88)
In article <10655@agate.BERKELEY.EDU>, jerry@violet.berkeley.edu ( Jerry Berkman ) writes: >> [C vs FORTRAN] > C is missing many useful intrinsics. I have trouble taking a > language seriously for numeric computation if the language doesn't > even know about absolute values, e.g.: x = abs(x); or signed > numbers, e.g. x = +5; Both statements are illegal in C. Not so. The first one is perfectly legal; any compiler that won't accept it is broken. The second one is legal under the dpANS (or at least in K&R V2), though it used to be illegal. (Why do we need a unary plus operator anyway? I never missed it.) > [ i = j**k and y = x**6 ] How do you express link->next->chain = vec[i++]; in FORTRAN? Why try to create a war of features? It sounds as though your sort of work is better expressed in FORTRAN. Please stick to FORTRAN, then, and stop complaining about C. You aren't complaining about how Snobol makes it difficult and slow to do what you want to do, are you? > Actually, C does not have a concept of intrinsic at all. It does under the dpANS, or very close to it. If we say, for example, #include <math.h> x = sqrt(y); then we are justified in believing the sqrt() routine to be the math library routine. > For that matter, since sqrt() is a FORTRAN intrinsics, I get an error > message from any decent FORTRAN compiler for sqrt(integer). None > from C of course (running lint is a hassle). In other words, you recognize that you have such a checking feature available, but using it is too much trouble, so you complain about the lack of checking. Riiight. (I certainly can't see the hassle in running lint; just say "lint" instead of "cc"....) der Mouse uucp: mouse@mcgill-vision.uucp arpa: mouse@larry.mcrcim.mcgill.edu
mouse@mcgill-vision.UUCP (der Mouse) (06/20/88)
In article <10681@agate.BERKELEY.EDU>, jerry@violet.berkeley.edu ( Jerry Berkman ) writes: > As for "x = abs(x);", it does compile and load. > However, it's calling a library function. What's wrong with that? > (1) It's slow. > (2) It returns the absolute value of integers. You can type it > "float abs();" and it works on the VAX, but it may not work on > all systems. Doesn't work on our VAX. Your VAX must be using a different floating-point format from the one in the VAX architecture manual. I tried compiling and running this: float abs(); main() { printf("%g\n",abs(123.456)); printf("%g\n",abs(-123.456)); } and it gave me -0.00210706 0.00210706 Of course, maybe you think that's what it means for it to work on the VAX....but I daresay most people would disagree. (You could also break down and use fabs, the floating-point absolute value routine - or is that cheating?) der Mouse uucp: mouse@mcgill-vision.uucp arpa: mouse@larry.mcrcim.mcgill.edu
rrr@naucse.UUCP (Bob Rose ) (06/21/88)
In article <29697@cca.CCA.COM>, g-rh@cca.CCA.COM (Richard Harter) writes: > In article <738@naucse.UUCP> rrr@naucse.UUCP (Bob Rose ) writes: > >Ok, what gives. Some else post the following code (not exact but close enough) > > [Some fortran code and the C equivalent] > > Yes, it does. However in fortran you can do the following > > real a(10) > ... > call foo(a,2,5) > call foo(a,5,2) > ... > subroutine foo(a,m,n) > real a(m,n) > ... > > This is what fortran users mean when they talk about variable dimensioning; > all it really means is that the compiler will generate address calculations > for arrays using variables as well as constants. You can do this by hand, > but it is much more convenient if the compiler will do it for you. As far > as I know, there is no good reason why this feature could not be added to > C. The discussion revolves around ways to fake it in C, using preprocessor > tricks. They all look kludgy to me. ^^^^^^ Here is the equivalent C code (right?) double a[10] ... foo(a,2,5) foo(a,5,2) ... #undef a void foo(a,m,n) double a[] #define a(x,y) a[(x)*n+(y)] /* works with ansi-c */ int m,n; { ... a(p,q) = ... /* same syntax as fortran, golly gee */ Yes, it is kludgy, but it does work. Sooo, the question again is is there any fortran constructs that cannot be translated into fortran through a brute force kludge. You know, something that a well trained ape couldn't do. I would like to see it. Please no complex numbers, these well just be function call (and if you are worried about speed, get a compiler that well do inline function calls.) -bob -
jlg@beta.lanl.gov (Jim Giles) (06/21/88)
In article <1171@mcgill-vision.UUCP>, mouse@mcgill-vision.UUCP (der Mouse) writes: > [...] (Why do we need a > unary plus operator anyway? I never missed it.) The proposed ANSI standard for C has unary plus operators. Among other uses, it can force ordering of expression evaluation. The famous case where C doesn't evaluate a+(b+c) in any particular order is fixed by doing a+ +(b+c). The unary plus forces the subexpression to be eval- uated before adding the other constant. > [...] It sounds as though your sort of work is > better expressed in FORTRAN. Please stick to FORTRAN, then, and stop > complaining about C. You aren't complaining about how Snobol makes it > difficult and slow to do what you want to do, are you? > This is exactly the point of previous responses. There really are things This is exactly the point of previous responses. There really are things which are best done in Fortran. The points raised about C in this discussion are reasons for not switching. No one is complaining about C in isolation, these are legitimate answers to the original posting about the desirability of switching to C. As such, discussion of the inadequacies of C for certain types of work are quite appropriate. J. Giles Los Alamos
leo@philmds.UUCP (Leo de Wit) (06/21/88)
In article <20340@beta.lanl.gov> jlg@beta.lanl.gov (Jim Giles) writes: >In article <224@raunvis.UUCP>, kjartan@raunvis.UUCP (Kjartan Pierre Emilsson Jardedlisfraedi) writes: >> Now here there seems to be a little misunderstanding. I have never >> understood why Fortran users keep saying that array indexing is awkward >> in C. >> [...] > >Awkward isn't the problem. I don't like the double bracket notation, >but anyone can write a macro to turn ARRAY(i,j,k) into array[i][j][k]. Matter of style. I don't like seeing an identifier that could be both an array and a function call (oh yeah, Fortran uses CALL in front of it 8-). >The Problem is that 2-d arrays are not optimizable because they are >immediately turned into pointer-to-pointer-to-data type of constructs. Depends on how you implement them. > >> If the array had been initialized with Create2DArray() then indexing >> would be just as normal,i.e: >> >> DoSomething(array,m,n) >> double **array; >> int m,n; >> { >> ... >> array[ i+k ][ j-i ]= 1.0; >> ... >> } > >If your use of array here is in a loop (that might otherwise be vector- >izable), the C compiler can't vectorize it because a pointer-to-pointer [stuff about vectorizing deleted]... So I suggest another alternative for Create2DArray(): double **Create2DArray(w,h) int w,h; { double **r, **a; for (a = calloc(w * h, sizeof(**r)), r = calloc(h,sizeof(*r)); --h >= 0; r[h] = a + w * h; return r; } This has two advantages: only 2 calls to calloc needed (while the original needed h + 1), and furthermore the data itself is contiguous in memory (pointed to by r[0]). Furthermore you can have both the speed of vectored arrays and flat ones (whatever is more appropriate). Another remark: perhaps it's better to replace the second calloc by a malloc, since the contents of r[h] is changed anyway. And you can combine the two allocations into one, as The Walking Lint pointed out. If you're out for speed, use flat arrays and pointers into these. > >> [...] >> ii) You can define your own data structures, which can be any >> combination of system defined structures and user defined >> structures, array of structures, self-referential >> structures and so on. [...] > >This capability is NOT an adequate replacement for the complex data type. >Complex is more than just a pair of reals, there are several operations >defined on complex (like plus) which should work naturally. No use of >C programming constructs can do this: > > COMPLEX CVAR > REAL RVAR > INTEGER IVAR > ... > CVAR=(CVAR+RVAR)*IVAR > ... >The operations (including the mixed-mode type conversions) are all done >IN-LINE and efficiently. C provides no way to even do this calculation >without function calls. This is simply not true. Even if the C compiler cannot generate inline code it is perfectly possible to use macro's to achieve the speed that FORTRAN boasts of (and I think even more than that). For instance: typedef struct { double c_re, c_im; } complex; #define C_MULT(p,q,r) \ ((r).c_re = ((p).c_re + (q).c_re, (r).c_im = (p).c_im + (q).c_im) complex z1, z2, result; /* ------- */ C_MULT(z1,z2,result); You can have even macro's for functions on complex numbers, and even the best Fortran compiler cannot forsee to implement all user functions inline (in fact I think only a very limited number of functions are supported). The only drawback of the macro approach is that most people don't like the splitting up of expressions into these elementary ones (if C had structure assignment and runtime declarators also this problem was solved). But I think Fortran would get into trouble if you had to work with quaternion calculations, e.g. Nice as it is to have predefined types and operations, it is even nicer to support creating you own types. What if you want to describe distributions in your data model? C offers a much cleaner approach. Pure number crunching: ok, Fortran. But compiler building? Databases? Operating systems? Juicy, juicy (You see: use C ;-). If I want speed, I'd better have no Fortranquilizers 8-). Leo.
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/21/88)
In article <20378@beta.lanl.gov> jlg@beta.lanl.gov (Jim Giles) writes: >The proposed ANSI standard for C has unary plus operators. Among other >uses, it can force ordering of expression evaluation. The famous case >where C doesn't evaluate a+(b+c) in any particular order is fixed by >doing a+ +(b+c). The unary plus forces the subexpression to be eval- >uated before adding the other constant. I'm afraid you're behind the times. There was so much public objection to this, and so much clamor for parentheses forcing order of evaluation, that this special property of unary plus was dropped from the proposed standard, and Fortran-like parentheses order forcing was adopted instead. >There really are things which are best done in Fortran. Fortunately not many really interesting things.
leo@philmds.UUCP (Leo de Wit) (06/26/88)
In article <750@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >First of all I agree with Dijkstra with respect to Fortran. I feel the >challenge designing a new language that can be Fortran at its own game, >which C does not do. So what IS FORTRAN's game? > [stuff deleted]... >A Fortran compiler is permitted to allocate all arrays statically, before >compilation, and many do this. Also Fortran subroutine are not required to >be recursive and hence do not need a procedure frame. All allocation can be >done in the compiler and the runtime overhead can be zero. A few remarks: A C programmer can CHOOSE (note: uppercase 8-) whether he wants arrays to be global, static or automatic. This means that the runtime overhead can be at least as little as that of a FORTRAN program (zero overhead is rubbish; you always have to page or swap the data in, whether you use data /heap space or stack space, or you at least have to claim core). Furthermore you make it sound as if it was a merit when functions cannot be recursive (are not required to..); procedure frame are more or less for compiler builders: you can do without them, making it much harder for yourself (most procedure frames can be build and broken down with a single, fast instruction; this goes also for pushing/popping sets of registers). If you can design a function in which the system spends significant time doing call, return, push, pop, link, unlink there must be very little code inside that function (try a macro; no, I do not mean an assembler! 8-). Dropping off these things (call, push ..) can only gain a few percent, at what other cost (inflexible subroutine scheme, permanent variables)? You can even totally rule out any use of subroutines if you're out for speed: large monolotic blocks with many pieces of repeated code, is that desirable? The scope of local variables can be more restricted than in FORTRAN if you wish so (yes, for auto AND for static vars); more like Algol block-bound. >Also it is easy for programmer to modify the array base address to implement >nonzero lower bounds. It is also easy for the compiler. I suspect Fortran >programmers know alot less about dope vectors biased base addresses and that >ilk than C programmers (scientists and engineers vs. computer science and >system programmers). The trouble here is obviously that scientists want their problem to map too literally onto the notation and possibilities of a computer language. Strange, because C you have to learn only once (that is, twice if that is not the proposed ANSI draft standard), scientific notations may change all the time. Knowing how to work with pointers can improve on speed considerably. > >> ii) You can define your own data structures, > >Apparently some Fortran programmers equivalence different typed arrays to >create structures (shudder). Now this one I cannot grasp (English not being my native language); what do you mean by this sentence (what are the predicate and the subject) ? Can you give an equivalence 8-) ? Leo.
mouse@mcgill-vision.UUCP (der Mouse) (06/26/88)
In article <20340@beta.lanl.gov>, jlg@beta.lanl.gov (Jim Giles) writes: > In article <224@raunvis.UUCP>, kjartan@raunvis.UUCP (Kjartan Pierre Emilsson Jardedlisfraedi) writes: >> [...] > The Problem is that 2-d arrays are not optimizable because they are > immediately turned into pointer-to-pointer-to-data type of > constructs. Real 2-d arrays turn into pointer-to-array, not pointer-to-pointer. If you have one of these dynamically-allocated arrays that have been bandied about, which is really an array of pointers to blocks of data, *that* is pointer-to-pointer. >> ii) You can define your own data structures, > This capability is NOT an adequate replacement for the complex data > type. Complex is more than just a pair of reals, [...] It's both more and less powerful. To put it another way, FORTRAN's COMPLEX data type is NOT an adequate replacement for the ability to define custom data types. > No use of C programming constructs can do this: [FORTRAN example] > C provides no way to even do this calculation without function calls. Sure it does, it just takes a little more code than the FORTRAN example. But that's a strawman anyway. For every such example, I can write one in C that FORTRAN similarly "can't" do. der Mouse uucp: mouse@mcgill-vision.uucp arpa: mouse@larry.mcrcim.mcgill.edu
mouse@mcgill-vision.UUCP (der Mouse) (06/26/88)
In article <738@naucse.UUCP>, rrr@naucse.UUCP (Bob Rose ) writes: > In article <20340@beta.lanl.gov>, jlg@beta.lanl.gov (Jim Giles) writes: >> The Problem is that 2-d arrays are not optimizable because they are >> immediately turned into pointer-to-pointer-to-data type of >> constructs. > Ok, what gives. Some else post the following code (not exact but > close enough) > real a(5,2) > call foo(a) > end > subroutine foo(a) > real a(10) > Now doesn't the following c code work to do the same > double a[2][5] /* <-- note [2][5] not [5][2] */ > ....foo(a).... > void foo(double a[10]) { ... } No, I'm afraid not. foo() is expecting an array of ten doubles. Instead, you're passing it an array of two arrays of five doubles. (Actually, a pointer to an array of five doubles.) What's the difference? To put it briefly, I find no guarantee that sizeof(double[5]) == 5*sizeof(double). (If that didn't make sense to you, read on.) Of course, most compilers won't produce surprises like this, but that's no guarantee that some machine won't come along on which there are good performance reasons for doing it. A is just an array of two elements. Like other arrays of two elements, the memory allocated for it can be thought of as being in two pieces: one for each element. By the definition of pointer arithmetic and its relation to arrays, the distance from the start of the first piece to the start of the second piece is the size of the thing a is an array of. When the elements of an array are, say, structures, nobody finds this surprising. For example, suppose we have struct { int i; char c; } b[2]; Now suppose sizeof(int)==2. Then that structure really *needs* only three bytes of storage. However, the compiler is free to waste a byte and decree that the structure type takes up four bytes, one of which has no name. As far as I can tell, the same is true of arrays: if I declare char c[3]; the compiler is free to do the same padding trick and make c take up four bytes, one of which has no name. Of course the same is true of arrays of five doubles. So when we allocate an array of two such arrays, the compiler may put padding in between. der Mouse uucp: mouse@mcgill-vision.uucp arpa: mouse@larry.mcrcim.mcgill.edu
bill@proxftl.UUCP (T. William Wells) (06/26/88)
In article <8098@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn ) writes: ) In article <3946@pasteur.Berkeley.Edu> faustus@ic.Berkeley.EDU (Wayne A. Christopher) writes: ) >The best reason NOT to allow a compiler to expand standard functions in-line ) >is that you can't substitute your own to fix a bug in the standard version. ) >I've had to do this a number of times with bug-prone functions like floor() ) >(too many versions round towards zero instead of down). ) ) NO NO NO -- Don't do this! ) ) Assuming for the sake of argument that some implementation has a floor() ) function like that, it is quite possible that some of the other math ) library routines actually depend on that behavior. If you change it, ) you will break other routines in possibly subtle ways. ) ) A much better solution to this particular problem would be: ) ) #define Floor my_floor /* or "floor", if it works right */ ) extern double Floor(double); ) ) /* ... use "Floor" instead of "floor" ... */ ) ) double my_floor(register double x) /* adjust for floor() bug */ ) { ) extern double floor(double); /* from math library */ ) register double xf = floor(x); ) ) return x >= 0 ? xf : x == xf ? x : xf - 1; ) } ) ) Also report the floor() bug to the library implementor. I agree with all of that, except one point. I would just take the original code which uses floor and place a #define floor my_floor in a configuration file surrounded by #ifdef BUGGY_FLOOR/#endif. I'd then put my_floor in a file in a file for configuration dependent code. I would only code a routine with the name my_floor if I wanted to write a routine similar to floor but with some minor differences.
g-rh@cca.CCA.COM (Richard Harter) (06/27/88)
In article <1189@mcgill-vision.UUCP> mouse@mcgill-vision.UUCP (der Mouse) writes: >>> ii) You can define your own data structures, >> This capability is NOT an adequate replacement for the complex data >> type. Complex is more than just a pair of reals, [...] >It's both more and less powerful. To put it another way, FORTRAN's >COMPLEX data type is NOT an adequate replacement for the ability to >define custom data types. The CDC 3600 version of fortran II had an interesting wrinkle. You could define your own data types with arithmetic operators. The compiler would generate calls to functions which you supplied. The issue really is -- what data types are supported by the language as primitives. Any type which is a primitive language type can be compiled much more efficiently than one which must be built up by hand. C has characters and pointers as primitives; fortran has complex as a primitive. C also has structures as a primitive. -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.
rob@kaa.eng.ohio-state.edu (Rob Carriere) (06/28/88)
In article <528@philmds.UUCP> leo@philmds.UUCP (L.J.M. de Wit) writes: > >The trouble here is obviously that scientists want their problem to map >too literally onto the notation and possibilities of a computer >language. Strange, because C you have to learn only once (that is, >twice if that is not the proposed ANSI draft standard), scientific >notations may change all the time. Knowing how to work with pointers >can improve on speed considerably. > Yes. I have written FORTRAN 66 programs where I could not set the array lower bound, and was forced to drag ``-lb'' through every array index in the entire code. Rest assured, it did absolute wonders to readability (and my nerves :-) I know how to work with pointers, I'm just not proud enough of the fact to have to demonstrate it throughout the code. I'll hide this stuff where it belongs, in a couple of low-level functions. Not to mention, *my* notation tends to be very consistent, I use whatever makes the problem the easiest to understand :-) > >>Apparently some Fortran programmers equivalence different typed arrays to >>create structures (shudder). > >Now this one I cannot grasp (English not being my native language); what do >you mean by this sentence (what are the predicate and the subject) ? >Can you give an equivalence 8-) ? > Methinketh the man useth ``equivalence'' as a verb, at least that's what Dijkstra likes to do (though he at least has the good sense to disambiguate to ``equivale'' -- don't you wish everybody spoke ``de enige echte taal ter wereld'' :-) :-) Rob Carriere "Never translate your formulae!"
smryan@garth.UUCP (Steven Ryan) (06/28/88)
>So what IS FORTRAN's game? Running big huge numerical models like a bat out of hell. Watching people getting bigger and faster computers is like watching a heroin addict: more! more! MORE! People who say nasty things about fortran are right, but what have they to offer? >A few remarks: >A C programmer can CHOOSE (note: uppercase 8-) whether he wants arrays >to be global, static or automatic. By only offering static allocation, the compiler does not have to support any overhead at all. A C program must keep the stack pointer correctly aligned and rest of the protocol straight even if it doesn't use the stack because somebody it calls may use the stack. Similarily, in supporting recursion, the stack has to be maintained in case some called program needs the stack. Further, supporting recursion means all automatic variables must be mapped into the stack because the procedure may recurse indirectly. Forbidding recursion means the compiler can map automatic variables into static areas. However convenient it might be, recursion is not strictly necessary in practical programs. In some numeric models, it would actually be inconvenient. This is another case where fortran gives up something of questionable value (for them) to simplify optimisation. (However, we can always use a transitive closure which takes (?)cubic time to detect recursion, but most customers would rather a fast compiler.) > (zero overhead is >rubbish; you always have to page or swap the data in, whether you use data >/heap space or stack space, or you at least have to claim core). Pagein cost vs. pagein + computation cost. > procedure frame are more >or less for compiler builders: you can do without them, making it much >harder for yourself Unless it is impossible for a procedure to recurse, directly or indirectly, local variables must be mapped onto the stack. You cannot avoid this overhead without avoiding recursion. > Dropping off these things (call, push ..) >can only gain a few percent, at what other cost (inflexible subroutine >scheme, permanent variables)? You can even totally rule out any use of >subroutines if you're out for speed: large monolotic blocks with many >pieces of repeated code, is that desirable? Unfortunately--some people do find that desirable. As far as few cycles, look back a few weeks when somebody said a C function should make the argument list length available. Many jumped on the poor guy because they didn't want their code to waste the single instruction necessary to load a register. Please, don't suggest I want speed or I find this desirable. My favorite compiler was an Algol60 compiler. I never turned off array bound checks or switch range checks. I think call-by-name (real call-by-name with deferred execution and not wimpy call-by-reference) is fun. The compiler permitted assembly procedures to have variable length lists. The calling protocol gave the parameter list length and a descriptor with type and kind for each element in the list. And the address of dope vector was passed along. >>Apparently some Fortran programmers equivalence different typed arrays to >>create structures (shudder). Some fortran programmers use the EQUIVALENCE statement to adjust the beginning address of different arrays with different types so that they map their elements into interleaved storage. Don't know details--just heard about some of things they do just to stay in fortran. Like using blank common as a heap.
jlg@beta.lanl.gov (Jim Giles) (06/28/88)
In article <1189@mcgill-vision.UUCP>, mouse@mcgill-vision.UUCP (der Mouse) writes: > In article <20340@beta.lanl.gov>, jlg@beta.lanl.gov (Jim Giles) writes: > > The Problem is that 2-d arrays are not optimizable because they are > > immediately turned into pointer-to-pointer-to-data type of > > constructs. > > Real 2-d arrays turn into pointer-to-array, not pointer-to-pointer. If > you have one of these dynamically-allocated arrays that have been > bandied about, which is really an array of pointers to blocks of data, > *that* is pointer-to-pointer. I'm sorry. To me a 2-d array is a 2-d array is a 2-d array is a .... Any routine that gets a 2-d array as an argument must assume that it is either static (which restricts you one way), or it must assume that it is dynamic (in which case it IS a pointer-to-pointer etc.). This means that you can't write a general routine which takes a 2-d array as an argument. This is EXACTLY the sort of problem that I meant originally when I said that C didn't have the concept of multi-dimensional arrays in the language. By the way, I've not seen any C compilers which optimize static 2-d arrays anyway. An early step in the compiler usually turns the array reference into a linear function on the indices - this throws out the dependency information. As a result, very similar code is actually generated whether the array was statically or dynamically allocated. C gives you the worst of both worlds - you can't treat them the same in source, and you can't get better optimization out of them in object code. > [...] > > type. Complex is more than just a pair of reals, [...] > > It's both more and less powerful. To put it another way, FORTRAN's > COMPLEX data type is NOT an adequate replacement for the ability to > define custom data types. I never claimed it was. To repeat: the ability to define derived data types, and the operations thereon, is very useful and Fortran SHOULD have it. This has NOTHING to do with the debate about whether COMPLEX should be built-in. It has NOTHING to do with the fact that C cannot do COMPLEX as efficiently as Fortran. > > > No use of C programming constructs can do this: [FORTRAN example] > > C provides no way to even do this calculation without function calls. > > Sure it does, it just takes a little more code than the FORTRAN > example. [... This 'little more code' that you're talking about does less than you think. Because COMPLEX is built-in to Fortran, the compiler writer is free to use his knowledge about the semantics of COMPLEX in designing optimizations. Whereas your 'little more code' spells out a specific sequence of operations to simulate complex artithmetic, the Fortran compiler is free to choose from all mathematically equivalent sequences for the most efficient one. User definable data types are useful, but commonly used data types should be built-in. > ...] But that's a strawman anyway. For every such example, I can > write one in C that FORTRAN similarly "can't" do. Please feel free to do so when someone asks the question: 'Should I convert C code to Fortran?' Why do you consider a direct answer to a question to be a 'strawman'? Or didn't you read the "subject" line on this article. J. Giles Los Alamos
chris@mimsy.UUCP (Chris Torek) (06/28/88)
>In article <738@naucse.UUCP> rrr@naucse.UUCP (Bob Rose) suggests that this C code is is legal: >> double a[2][5] /* <-- note [2][5] not [5][2] */ >> ....foo(a).... >> void foo(double a[10]) { ... } In article <1190@mcgill-vision.UUCP> mouse@mcgill-vision.UUCP (der Mouse) gets the right answer, and the right reason: >No, I'm afraid not. foo() is expecting an array of ten doubles. >Instead, you're passing it ... Actually, a pointer to an array of >five doubles.) but the wrong explanation: >What's the difference? To put it briefly, I find no guarantee that >sizeof(double[5]) == 5*sizeof(double). There is indeed such a guarantee. The one that is missing, which makes this particular example fail, is that pointers to arrays of objects need not at all resemble pointers to the objects themselves. Please remember that C is a strongly typed language (no matter what else you have been told). Mixing types is often legal, and the cross-checking required by the language is extremly weak, but the type system itself is quite strong. The difference is like that between an extensive law system and extensive enforcement: If the system is there, any missing enforcement can be provided later, at need, without much hassle. The whole example may be corrected quite simply: ... foo(&a[0][0]); /* or foo(a[0]) */ ... void foo(double a[10]) /* or void foo(double *a) */ { ... } -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
smryan@garth.UUCP (Steven Ryan) (06/29/88)
>> > type. Complex is more than just a pair of reals, [...] >> >> It's both more and less powerful. To put it another way, FORTRAN's >> COMPLEX data type is NOT an adequate replacement for the ability to >> define custom data types. C does not provide custom data types either. It permits new structures, but those are not orthogonal to the primitive types: no new operators, no new casts, (on some implementation) no new assignments, ...
smryan@garth.UUCP (Steven Ryan) (06/29/88)
>>>some Fortran programmers equivalence different typed arrays
In Fortranish, "equivalence" is verb: to equivalence A and B means to write
an EQUIVALENCE statement to control their relative starting addresses as in
DIMENSION A(100),B(101)
EQUIVALENCE (A(1),B(2))
------------------------------------------------------------
p.s. who says Fortran-66 doesn't support zero-based arrays?shenkin@cubsun.BIO.COLUMBIA.EDU (Peter Shenkin) (06/29/88)
A few points concerning the everpresent comparisons between C and Fortran. (I like *both*!!!) Anyway, my first point has to do with recursion. The second with EQUIVALENCE. If you're bored already, hit "n". In article <817@garth.UUCP> you write: >However convenient it might be, recursion is not strictly necessary in >practical programs.... POINT 1: I used to agree, and most people agree. Most textbook examples of recursion -- eg, calculation of factorial(n) -- would be much clearer and faster, in practice if coded using simple iteration. But I've come across a class of problem which can only be generally handled through recursion, I think. I'd be intrigued if someone can come up with a Fortran solution. (Mail it to me, and I'll post a summary to comp.lang.fortran.) This class involves, conceptually, nested DO-loops, when the depth of the nest is unknown at compile time. For example, the following C program generates grid points within a hypercube, given the number of degrees of freedom (dimensionality) of the space, and the number of gridpoints (number of levels) along each coordinate. Turns out I need to do more complicated versions of this sort of thing all the time in numerical work. NB: This *can* be coded in Fortran by setting up the maximum number of needed DO-loops and escaping early, if need be. But this is unwieldy, at best , unless this maximum is small. And here (if one malloc()'s -- see my note on MAXDF) a maximum need not be specified. /*****************************************************************************/ /* grid.c: generate grid points in a hypercube */ /* compile by saying, "cc -o grid grid.c" /* invoke by saying, eg, "grid 4 2", to generate the vertices, only, of * a 4-D hypercube. */ #define MAXDF 100 /* max number of degrees of freedom -- not really needed, * since we could malloc() value[] in grdgen() */ main(argc,argv) int argc; char *argv[]; { int df,nlev; /* number of deg. of freedom, number levels per df */ df= atoi(argv[1]); nlev= atoi(argv[2]); printf("df=%d; nlev=%d\n",df,nlev); grdgen(df,nlev); } /*****************************************************************************/ grdgen(df,nlev) int df; /* no. of degrees of freedom */ int nlev; /* no. of levels each df */ { static int begin=1; /* ==0 if func was called by itself */ static int totaldf; /* total no. of degrees of freedom (1st call)*/ static int value[MAXDF]; /* to hold current values of all df's */ int i,j; if(begin) totaldf=df; if(--df ==0) { /* iterate through last df and print values */ for(i=0; i<nlev; ++i) { value[df] = i; for(j=0; j<totaldf; ++j) { printf("%d ",value[j]); } printf("\n"); } begin=1; } else for(i=0; i<nlev; ++i) { value[df] = i; begin = 0; grdgen(df,nlev); } } /*****************************************************************************/ POINT 2: >>>Apparently some Fortran programmers equivalence different typed arrays to >>>create structures (shudder). > >Some fortran programmers use the EQUIVALENCE statement to adjust the >beginning address of different arrays with different types so that >they map their elements into interleaved storage. Generally it's the same storage, not interleaved storage, and it's not to create structures. (The conceptual equivalent (not real equivalent -- there is none) of structures in standard Fortran is labeled COMMON.) EQUIVALENCE is sometimes used to be able to reuse declared (C programmers would say "defined") storage for different purposes in different places. The conceptual equivalent of this in C is the union. -- ******************************************************************************* Peter S. Shenkin, Department of Biological Sciences, Columbia University, New York, NY 10027 Tel: (212) 280-5517 (work); (212) 829-5363 (home) shenkin@cubsun.bio.columbia.edu shenkin%cubsun.bio.columbia.edu@cuvma.BITNET
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/29/88)
In article <829@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >C does not provide custom data types either. It permits new structures, >but those are not orthogonal to the primitive types: no new operators, >no new casts, (on some implementation) no new assignments, ... Wrong on all those counts. C allows casting to any defined type and assignment of any structure type. (If you feel like using an array, wrap a structure around it -- it's free.) New operators can be defined as macros or functions. The one thing missing is overloading of existing built-in operator tokens such as "*"; C++ supports that but C does not. However, operator overloading is vastly overrated; most operations on extended data types do not map (unambiguously) onto the conventional arithmetic operations. Complex numbers are about the only case that does.
js07@bunny.UUCP (Jack Shaio) (06/30/88)
In a previous posting, der Mouse replies to: > >>> ii) You can define your own data structures, >> This capability is NOT an adequate replacement for the complex data >> type. Complex is more than just a pair of reals, [...] with: >It's both more and less powerful. To put it another way, FORTRAN's >COMPLEX data type is NOT an adequate replacement for the ability to >define custom data types. > In fact, the reverse is true: C's ability to define custom data types is no substitute for FORTRAN's COMPLEX type. COMPLEX is a standard, and you can link any packaged math subroutine to your own programs without having to worry about how complex was defined. I recently obtained three FFT algorithms in C from various sources and found three different ways of defining complex (all different from mine). Had I done everything in FORTRAN, a look at the subroutine header would have been enough. The point is that if you plan to do numerical work, and not program every last subroutine from scratch, one COMPLEX data type in FORTRAN is a plus; ten different definitions of complex in C are a pain. Perhaps a remmant of the days when people used computers to solve equations. js
ok@quintus.uucp (Richard A. O'Keefe) (06/30/88)
In article <8184@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >Wrong on all those counts. C allows casting to any defined type and >assignment of any structure type. Maybe I'm confused here, but I thought C only allowed casts to and from SCALAR types. In particular, I've never succeeded in casting to or from unions or structs. Doug Gwyn also claimed that operator overloading wasn't much use, because there aren't a lot of uses for it. If your language is APL, maybe not, but the arithmetic operations generalise to vectors, matrices, polynomials, &c very nicely indeed.
ddb@ns.UUCP (06/30/88)
In article <8184@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn ) writes: > However, operator overloading is vastly overrated; > most operations on extended data types do not map (unambiguously) onto > the conventional arithmetic operations. Complex numbers are about the > only case that does. Comparison and assignment. Operators aren't all arithmetic. C already supports assignment of structures, but I miss comparison regularly. (Note -- I'm not changing the subject to suggest yet again that equality comparison of structures be implemented, I'm talking about the uses of operator overloading; just in case the other is still a touchy subject here :-). -- -- David Dyer-Bennet Fidonet 1:282/341.0
clewis@spectrix.UUCP (Chris "where are you this week?" Lewis) (06/30/88)
In article <817@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >By only offering static allocation, the compiler does not have to support >any overhead at all. A C program must keep the stack pointer correctly >aligned and rest of the protocol straight even if it doesn't use the stack Not always - besides, do you really think the prologs have: if (stack is odd) align it ?? >because somebody it calls may use the stack. Some C (and other langs) compilers optimize a lot of function prolog and epilog stuff out. Prolog and epilog for C code is usually not noticable (compared to, say IBM 360 series FORTRAN). Especially interesting is that FORTRAN subroutines tend to be far larger than C ones. This is frequently due to people learning FORTRAN on IBM 360 series stuff where the prologs and epilogs are enormous in time and space - I've worked (internals) on an 360 series version of C that used it's own super simple calling convention - ran considerably faster (even tho 360's don't have stacks!). C's calling convention is actually absurdly simple - usually little more than saving the return address and some registers (register variables and temporaries) and decrementing the stack and then restoring same at the end. Unlike most Pascals (or ADA for that matter) which frequently have some rather spectacular stack frames formats to handle. Also, what's so bad about stacks? Many machines can do some stack references faster than static - sufficient in many cases to greatly outweigh the calling convention. Eg: short stack offset instructions on 386, 68020, VAXen(?) etc. are as short as two bytes instead of six for static - which at least saves you some additional memory fetches (which are usually far more expensive than register adds) and your pipelining gets to help a little more. Eg: on a 68020, these are some representative timings (in cycles): Best case Worst case mov Rn,-(SP) 3 6 mov Rn,n(SP) 3 7 mov Rn,addr.L 5 9 mov n(SP),m(SP) 6 13 mov a.L,b.L 8 16 Similarly, for expression intermediaries, machines with short stack offsetting modes can be a big win, and are usually less wasteful of memory than most static memory schemes (unless you have a million registers ;-). So, blanket statements like "automatic variables are a lot of overhead" are frequently wrong - frequently they are *less* overhead. I've done some fairly substantial compiler benchmarking, and have noted that auto variables are usually faster than static (depending on the circumstances and the CPU). >However convenient it might be, recursion is not strictly necessary >in practical Nobody is saying "recursion is necessary" - it's occasionally a handy tool to simplify some problems. That's all. I almost never use it in C - but I do sometimes, and I'd greatly miss it in a language that doesn't support it (I'd probably say "Oh sh*t - not another FORTRAN!" ;-). >> (zero overhead is >>rubbish; you always have to page or swap the data in, whether you use data >>/heap space or stack space, or you at least have to claim core). >Pagein cost vs. pagein + computation cost. Ah yes, but static memory allocation usually lead to programs that are bigger - taking *longer* to load (usually on swapping systems). Without stacks and/or dynamic storage allocation programmers usually don't have the ability to decide how much memory he needs depending on the data - another potential optimization loss (the program's data structure has to be as large as the largest set of data, rather than being able to start smaller and make it bigger if necessary). And the stack model is especially convenient for "deep returns" (use of setjmp/longjmp to be able to conveniently recover from errors way down a subroutine tree - have you ever seen the insides of Oracle? Sheesh!). -- Chris Lewis, These addresses will last only til June 30: (clewis@lsuc afterwards) UUCP: {uunet!mnetor, utcsri!utzoo, lsuc, yunexus}!spectrix!clewis Moderator of the Ferret Mailing List (ferret-list,ferret-request@spectrix)
gwyn@brl-smoke.ARPA (Doug Gwyn ) (07/01/88)
In article <148@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >Maybe I'm confused here, but I thought C only allowed casts to and from >SCALAR types. In particular, I've never succeeded in casting to or from >unions or structs. Well, yes, the two types involved (operand and result) need to be assignment compatible or the cast operation doesn't even make sense. How do you assign a 2-D matrix to a 1-D vector? >Doug Gwyn also claimed that operator overloading wasn't much use, because >there aren't a lot of uses for it. If your language is APL, maybe not, but >the arithmetic operations generalise to vectors, matrices, polynomials, &c >very nicely indeed. No, they do not. Some of them (e.g. addition) typically have a single accepted conventional meaning, but others (e.g. multiplication) are not uniqueley defined. For example, there are at least four "products" of commensurable vectors that I've had to deal with in the past, the result of NONE of which is a vector (although two of these result in pseudovectors, which people who don't know any better often treat as true vectors). Also, "division" is often ill-defined in extended algebras. Finally, there are often operators that are more important than the conventional arithmetic ones. I know of several cases where treating unsimple data types as having proerties just like ordinary arithmetic has led to serious errors. (I'm not even talking about noncommutativity here.) It is much better to require the designed of an abstract data type to specify the operations AND for the designer to not use misleading symbols for such operations.
smryan@garth.UUCP (07/01/88)
In article <8184@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >In article <829@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >>C does not provide custom data types either. It permits new structures, >>but those are not orthogonal to the primitive types: no new operators, >>no new casts, (on some implementation) no new assignments, ... > >Wrong on all those counts. C allows casting to any defined type and >assignment of any structure type. (If you feel like using an array, >wrap a structure around it -- it's free.) Just to clear up the terminology: in Algol68, the casts were introduced as as contruct "mode(value)" which told the compiler to coerce the mode of the value into the indicated mode. A C cast confuses two distinct concepts with one notation. For a "(primitive-type)value" cast, it coerces the value, using widenning, narrowing, lengthenning, and a slew of other ill-defined type conversions. For a "(complicated-type)value" cast, it overlays the value's mode with a new mode--no coercion or any type of conversion is applied. Hence a C cast is not orthogonal: it splits between a coercion cast in simple cases and an overlay cast in complicated cases. [Before correcting the above, I already know an A68 cast is "formal-mode clause".] > New operators can be >defined as macros or functions. The one thing missing is overloading >of existing built-in operator tokens such as "*"; C++ supports that >but C does not. Operators are conceptually distinct from function calls, both from the programmers point of view, in how formulas are written, and from the point of view of the compiler, in how the symbols and their operands are identified. In a sufficiently high level language (not C), operators and procedures are mapped into the same fundamental mechanism, but that mechanism is neither a procedure nor an operator. This discussion is why fortran should be converted to c, not c++. > However, operator overloading is vastly overrated; >most operations on extended data types do not map (unambiguously) onto >the conventional arithmetic operations. Eh? If you're talking about operator identification ambiguity that is a result of a poor mode system. If you're talking about limited number of operators, that is a result of poor operator syntax (it is possible to give operators a generative syntax that permits arbritrarily many operators). If you're trying to establish some kind mapping between operator meanings in any mode and operator meanings for primitive modes, why? To claim that C is an orthogonal and extensible language indicates a blithe naiviety about these terms. Its data structuring is on the same level of Pascal and just a little above Fortran. The only real difference is the existence of a heterogenous array (struct in C, record in Pascal). This shouldn't be considerred a criticism of C: lack of orthogonality has permitted many convenient notations; lack of extensibility permits a simpler language and compiler.
jgk@speech2.cs.cmu.edu (Joe Keane) (07/01/88)
In article <20454@beta.lanl.gov> jlg@beta.lanl.gov (Jim Giles) shows he hasn't used C. >Any routine that gets a 2-d array as an argument must assume that it is >either static (which restricts you one way), or it must assume that it >is dynamic (in which case it IS a pointer-to-pointer etc.). Whether an array is static or dynamic has nothing to do with whether it contains arrays or pointers. >[various implications of this assumption] >By the way, I've not seen any C compilers which optimize static 2-d >arrays anyway. So you've not seen any C compilers. Given `static foo[10][10][10]' the reference `foo[2][0][7]' is a single address. If foo were a parameter the reference would be a single offset. But see for yourself. >As a result, very similar code is actually >generated whether the array was statically or dynamically allocated. Yes, the same code. --Joe
mike@arizona.edu (Mike Coffin) (07/01/88)
From article <20454@beta.lanl.gov>, by jlg@beta.lanl.gov (Jim Giles): > By the way, I've not seen any C compilers which optimize static 2-d > arrays anyway. An early step in the compiler usually turns the array > reference into a linear function on the indices - this throws out the > dependency information. This is not true. How can information be lost by changing "a[i]" to "*(a+i)"? In fact at least one very fancy FORTRAN compiler converts array references to exactly that form to extract dependency information that is difficult to recognize otherwise. See "Interprocedural Dependency Analysis and Parallelization" by Michael Burke and Ron Cytron, in the 1986 SIGPLAN Symposium on Compiler Construction, pp 162-175. For instance they are able to parallelize a loop with the following references: DO i = 1 to N A(2i,2i+1) = ... ... = A(i,i) END They say (page 166) "Existing techniques separately analyze the two dimensions of A, and so separately consider two dependence equations, neither of which can demonstrate independence. However, the dependencies that exist independently in each dimension cannot hold simultaneously: for any value of i, the expressions at the definition (2i and 2i+1) are never equal but the expressions at the use (i and i) are equivalent. Since the dependencies cannot hold simultaneously, no dependence exists between the definition and use of A. By linearizing the references to A, we couple the two equations into one, allowing us to determine the independence of the accessed regions." -- Mike Coffin mike@arizona.edu Univ. of Ariz. Dept. of Comp. Sci. {allegra,cmcl2,ihnp4}!arizona!mike Tucson, AZ 85721 (602)621-4252
jlg@beta.lanl.gov (Jim Giles) (07/01/88)
In article <6067@megaron.arizona.edu>, mike@arizona.edu (Mike Coffin) writes: > From article <20454@beta.lanl.gov>, by jlg@beta.lanl.gov (Jim Giles): > > By the way, I've not seen any C compilers which optimize static 2-d > > arrays anyway. An early step in the compiler usually turns the array > > reference into a linear function on the indices - this throws out the > > dependency information. > > This is not true. How can information be lost by changing "a[i]" to > "*(a+i)"? In fact at least one very fancy FORTRAN compiler converts > array references to exactly that form to extract dependency > information that is difficult to recognize otherwise. See > "Interprocedural Dependency Analysis and Parallelization" by Michael > Burke and Ron Cytron, in the 1986 SIGPLAN Symposium on Compiler > Construction, pp 162-175. > Most simple compilers (read 'C compilers') can't vectorize the following (assume i is a loop index): A[i+N] = A[i+M] regardless of the values of N or M. However the following expression might have been the source of the above expression: A[4][i] = A[5][i] This clearly has no dependencies and even a simple compiler (read 'some Fortran compilers') can vectorize this (ie. A(i,4)=A(i,5)). Turning the references above into *(A+i+4*dim2) = *(A+I+5*dim2) which, after constant folding, is the expression I started out with is what causes the C compiler to incorrectly identify a dependency. Now, it is true that with careful analysis of M, N, and the range if i, the compiler could still have compiled this efficiently. No C compilers that I've seen do this very well. Thank you for the reference. I have always been convinced that dependency analysis should TRY the kind of stuff you suggest, but only if simplistic analysis fails to get rid of the dependencies (compiler speed should be considered too). The problem is that C doesn't use either analysis technique very well. C actually CAN'T analyse those dynamic multi- dimensional arrays (pointer-to-pointer) because it can't assume the pointers have any specific relationships. It is probably for this reason that it doesn't bother for static arrays either. (vote for 'noalias', that should help.) J. Giles Los Alamos
hutchson@convex.UUCP (07/02/88)
>Richard Harter, SMDS Inc., writes: >The issue really is -- what data types are supported by the language as >primitives. Any type which is a primitive language type can be compiled >much more efficiently than one which must be built up by hand. This is incontrovertable. >C has >characters and pointers as primitives; fortran has complex as a primitive. >C also has structures as a primitive. This is most inaccurate. C supports multiple lengths of integers (including a VERY short length unsuitable for anything larger than an ASCII character.) C "char's" are really wierdly-represented tiny ints. C has a well-defined library of operations on null-terminated character strings; but only with the advent of ANSI C will it be possible to consider character strings primitive. Fortran, on the other hand, DOES have character strings as primitives, and good compilers can generate inline code for many string operations. In addition, fortran has multiple lengths of floating-point values--ANSI C is adding this, I think.
gwyn@brl-smoke.ARPA (Doug Gwyn ) (07/02/88)
In article <836@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >For a "(complicated-type)value" cast, it overlays the >value's mode with a new mode--no coercion or any type of conversion is >applied. Wrong. A C cast operator ALWAYS behaves as if an assignment to an unnamed temporary variable is performed. All this talk about "modes" is incorrect. >To claim that C is an orthogonal and extensible language indicates a blithe >naiviety about these terms. So, who's making such a claim? Perhaps to make claims about C without understanding it indicates something, too...
gwyn@brl-smoke.ARPA (Doug Gwyn ) (07/02/88)
In article <292@ns.nsc.com> ddb@ns.nsc.com (David Dyer-Bennet) writes: > Comparison and assignment. Operators aren't all arithmetic. Ok, which is larger, 2-5i or 5+1i? Are you sure your answer is the only possibility?
smryan@garth.UUCP (Steven Ryan) (07/02/88)
>Not always - besides, do you really think the prologs have: > if (stack is odd) > align it > ?? > >>because somebody it calls may use the stack. On a previous machine I used, yes, the stack had to be kept at even word boundary at all times. >Some C (and other langs) compilers optimize a lot of function prolog and >epilog stuff out. Prolog and epilog for C code is usually not >noticable (compared to, say IBM 360 series FORTRAN). The compiler is cheaper if it never existed in the first place. I suspect part of the size of prolog goes for adjustable arrays. >Also, what's so bad about stacks? Many machines can do some stack >references faster than static - sufficient in many cases to greatly outweigh >the calling convention. I think this a base register+offset compared to a constant offset, which should be avoiding in any case because it makes the code nonreentrant. Again, on the previous machine I used, all data references were base register+offset so that no time/space difference existed. Then again, if you want to consider a machine designed for C, would you also consider a machine designed for fortran. >So, blanket statements like "automatic variables are a lot of overhead" >are frequently wrong - frequently they are *less* overhead. All that is being compared is addressing modes. >>However convenient it might be, recursion is not strictly necessary >>in practical > >Nobody is saying "recursion is necessary" - it's occasionally a handy >tool to simplify some problems. That's all. For most problems, recursion is the most natural technique for me. Most times I use loops is because compilers don't do recursion removal and most languages make it difficult to define procedures. Data structures also simplify many problems. The challenge is to design a language as fast as Fortran but a shade more advanced (by about 30 years). Fortran users are conservative and are already pushing their machines to the limit. I have seen compiler complaints, not that the code is wrong, but that uses one extra instruction. >Ah yes, but static memory allocation usually lead to programs that >are bigger - taking *longer* to load (usually on swapping systems). Unix has a disgusting loader, but this is not really a language issue. Also, once loaded, a program may be run many times. In this case, a longer load is offset by a shorter run. >Without stacks and/or dynamic storage allocation programmers usually don't >have the ability to decide how much memory he needs depending on the data - >another potential optimization loss (the program's data structure has >to be as large as the largest set of data, rather than being able to >start smaller and make it bigger if necessary). Some C programmers don't seem to notice--see previous complaints about Yacc.
smryan@garth.UUCP (Steven Ryan) (07/03/88)
>> An early step in the compiler usually turns the array >> reference into a linear function on the indices - this throws out the >> dependency information. > >This is not true. How can information be lost by changing "a[i]" to >"*(a+i)"? In fact at least one very fancy FORTRAN compiler converts >array references to exactly that form to extract dependency >information that is difficult to recognize otherwise. [at two fortran compilers--the vectorising compiler I worked on also operated on an affine function of the subscripts.] The C subscript, if taken literally, does lose dependency information. Strict C parse tree possible Fortran parse tree convert-*-to-variable subscript | / \ integer-add symbol: a integer-multiply / \ / \ symbol: a integer-multiply element-size i / \ element-size i By having an explicit subscript node, a Fortran optimiser can easily access the array spans for each dimension, necessary for vectorisation. It also simplifies determining what region is referenced or defined, necessary for common subexpressions. ------------------------------------ USA - home of the modern revolution. (tho we'd just soon fergit it.)
smryan@garth.UUCP (Steven Ryan) (07/03/88)
>Wrong. A C cast operator ALWAYS behaves as if an assignment to >an unnamed temporary variable is performed. All this talk about >"modes" is incorrect. Some people use the word "mode" where others use "type". Don't be picky. I have seen the error of my ways! I now see that similarity of casting (int)(1.2) to (struct a*)(struct-b*-value). Obviously truncating an floating point number is the same as accessing the identical bit pattern as two distinct structs. I now understand why every compiler and programmer agrees to meaning of (unsigned)((short)(-1)).
smryan@garth.UUCP (Steven Ryan) (07/05/88)
>A few points concerning the everpresent comparisons between C and Fortran. >(I like *both*!!!) I dislike both. >>However convenient it might be, recursion is not strictly necessary in >>practical programs.... Practical as in how many Fortran programmers need indefinite looping.
smryan@garth.UUCP (Steven Ryan) (07/06/88)
In Algorithmic Language and Program Development, Bauer and Wossner, they cite Paterson and Hewitt as proving, essentially, recursion is more powerful than iteration. > But I've come across a class of >problem which can only be generally handled through recursion, I think. I'd >be intrigued if someone can come up with a Fortran solution. I don't want to be in position of proving various examples can be done without recursion, given the above statement and my own opinions. However this example is interesting. A recursive solution assumes the existence of a sufficiently large stack. If this storage is made available to Fortran program (perhaps as blank common), a nonrecursive solution would store the loop parameters as array elements: while still-something-do do-it increment-lowest-stack-entry while it-overflows reset-it increment-the-next-lowest-stack-entry
bill@proxftl.UUCP (T. William Wells) (07/06/88)
In article <861@garth.UUCP>, smryan@garth.UUCP (Steven Ryan) writes: > I have seen the error of my ways! I now see that similarity of casting > (int)(1.2) to (struct a*)(struct-b*-value). Obviously truncating an floating > point number is the same as accessing the identical bit pattern as two > distinct structs. The expression (int)(1.2) means convert the floating point constant to an integer. This involves a representation change. The expression (struct a *)b, where b is a pointer to a struct b, also involves a representation change. For technical reasons, almost all compilers represent all structure pointers the same, thus making the representation change the identity transformation. The cast you mentioned is of POINTERS, not structures. In fact, casting a structure is not legal in C.
kenny@m.cs.uiuc.edu (07/06/88)
On the discussion of whether or not `recursion is necessary,' I have at least a nickel's worth of comment. The example shown is frightful! In article <817@garth.UUCP> someone writes (correctly): >However convenient it might be, recursion is not strictly necessary in >practical programs.... /* Written 9:15 am Jun 29, 1988 by shenkin@cubsun.BIO.COLUMBIA.EDU in m.cs.uiuc.edu:comp.lang.c */ Peter Shenkin <shenkin@cubsun.bio.columbia.edu> replies: >I used to agree, and most people agree. Most textbook examples of recursion >-- eg, calculation of factorial(n) -- would be much clearer and faster, in >practice if coded using simple iteration. But I've come across a class of >problem which can only be generally handled through recursion, I think. I'd >be intrigued if someone can come up with a Fortran solution. (Mail it to me, >and I'll post a summary to comp.lang.fortran.) >This class involves, conceptually, nested DO-loops, when the depth of the nest >is unknown at compile time. For example, the following C program generates >grid points within a hypercube, given the number of degrees of freedom >(dimensionality) of the space, and the number of gridpoints (number of levels) >along each coordinate. Turns out I need to do more complicated versions of >this sort of thing all the time in numerical work. >NB: This *can* be coded in Fortran by setting up the maximum number >of needed DO-loops and escaping early, if need be. But this is >unwieldy, at best , unless this maximum is small. And here (if one >malloc()'s -- see my note on MAXDF) a maximum need not be specified. That comment is utter poppycock. Recursion can *always* be eliminated, if necessary by setting up an auxiliary stack. I shall demonstrate the techniques with your sample program. I'm posting this, rather than emailing it, because I think it also gives a good example of stepwise refinement of a program. I give ten versions of the same program, using the same algorithm, each of which attempts to be an improvement on its predecessors. These discussions should give some idea of how I, at least, attack this type of problem. (The `>'s are omitted in the example program) PROGRAM 0. The example program, as originally posted. /*****************************************************************************/ /* grid.c: generate grid points in a hypercube */ /* compile by saying, "cc -o grid grid.c" /* invoke by saying, eg, "grid 4 2", to generate the vertices, only, of * a 4-D hypercube. */ #define MAXDF 100 /* max number of degrees of freedom -- not really needed, * since we could malloc() value[] in grdgen() */ main(argc,argv) int argc; char *argv[]; { int df,nlev; /* number of deg. of freedom, number levels per df */ df= atoi(argv[1]); nlev= atoi(argv[2]); printf("df=%d; nlev=%d\n",df,nlev); grdgen(df,nlev); } /*****************************************************************************/ grdgen(df,nlev) int df; /* no. of degrees of freedom */ int nlev; /* no. of levels each df */ { static int begin=1; /* ==0 if func was called by itself */ static int totaldf; /* total no. of degrees of freedom (1st call)*/ static int value[MAXDF]; /* to hold current values of all df's */ int i,j; if(begin) totaldf=df; if(--df ==0) { /* iterate through last df and print values */ for(i=0; i<nlev; ++i) { value[df] = i; for(j=0; j<totaldf; ++j) { printf("%d ",value[j]); } printf("\n"); } begin=1; } else for(i=0; i<nlev; ++i) { value[df] = i; begin = 0; grdgen(df,nlev); } } Not only can recursion be eliminated in this type of program; the recursion can be eliminated mechanically; a *really* good optimizing compiler could conceivably manage it. Let's first recode your example to a `purer' recursive form, eliminating the innermost _for_ loop. That change gives us simpler code to work with: PROGRAM 1 [main program is the same as before] static int nlev; static int totaldf; static int value [MAXDF]; /* to hold current values of all df's */ grdgen_aux (df) { int i; if (df < 0) { /* Print a grid point */ register int j; for (j = 0; j < totaldf - 1; ++j) printf ("%d ", value [j]); printf ("%d\n", value [j]); } else { /* Generate grid points with df degrees */ /* of freedom */ for (i = 0; i < nlev; ++i) { value [df] = i; grdgen_aux (df - 1); } } } grdgen(df,nl) int df; /* no. of degrees of freedom */ int nl; /* no. of levels each df */ { totaldf=df; nlev = nl; grdgen_aux (df - 1); } Here, all the recursion is handled in the `grdgen_aux' procedure. The useless variable `begin' is removed, and the control structure has been simplified significantly. Now let's work on eliminating the recursion in `grdgen_aux.' We note that the only two automatic variables that are destroyed on recursion are _df_ and _i_. We also note that _df_ is always decremented by 1, and that _i_ can be recovered from the _value_ array. (Were this not the case, we could maintain an auxiliary stack of values.) We can eliminate the recursion by replacing the recursive call by a _goto_ to the function entry (If you think that _goto_ is a dirty word, take heart; I'm going to take the _gotos_ out again!), and the function return with a test for the top-level invocation and a _goto_ to the return point, giving the following version of the program. PROGRAM 2. [main program is still the same] static int nlev; static int totaldf; static int value [MAXDF]; /* to hold current values of all df's */ grdgen_aux (df) { int i; start: if (df < 0) { /* Print a grid point */ register int j; for (j = 0; j < totaldf - 1; ++j) printf ("%d ", value [j]); printf ("%d\n", value [j]); } else { /* Generate grid points with df degrees */ /* of freedom */ for (i = 0; i < nlev; ++i) { value [df--] = i; goto start; finish: i = value [++df]; } } if (df < totaldf - 1) goto finish; } grdgen(df,nl) int df; /* no. of degrees of freedom */ int nl; /* no. of levels each df */ { totaldf=df; nlev = nl; grdgen_aux (df - 1); } Now our problem is getting rid of the _goto_ statements, and untangling this bowl of spaghetti back into something readable. There are a couple of ways to attack this. METHOD I. Use a finite-state machine. Here, we take some of the state information out of the program counter, and put it in an auxiliary variable. We use a _switch_ statement on this auxiliary variable to control program flow. Fortran hackers will recognize that a computed or assigned GO TO will do the switch quite nicely. PROGRAM 3. [main program is still the same] static int nlev; static int totaldf; static int value [MAXDF]; /* to hold current values of all df's */ grdgen_aux (df) { int i; enum { EXIT, WORK, PUSH, POP } state; state = WORK; for (;;) { switch (state) { default: return; case WORK: if (df >= 0) { i = 0; state = PUSH; } else { register int j; for (j = 0; j < (totaldf - 1); ++j) printf ("%d ", value [j]); printf ("%d\n", value [j]); state = POP; } break; case PUSH: if (i >= nlev) state = POP; else { value [df--] = i; state = WORK; } break; case POP: if (df >= (totaldf - 1)) state = EXIT; else { i = value [++df] + 1; state = PUSH; } break; } } } grdgen(df,nl) int df; /* no. of degrees of freedom */ int nl; /* no. of levels each df */ { totaldf=df; nlev = nl; grdgen_aux (df - 1); } Folding the `grdgen_aux' procedure back into `grdgen', now that the former is no longer recursive, and performing a few trivial optimizations, gives: PROGRAM 4. [main program is still the same] grdgen (df, nlev) register int df; /* no. of degrees of freedom */ register int nlev; /* no. of levels each df */ { register int i, j; register int totaldfm1; static int value [MAXDF]; /* to hold current values of all df's */ register enum { EXIT = 0, WORK, PUSH, POP } state; totaldfm1 = df - 1; state = WORK; while (state) { switch (state) { case WORK: if (df >= 0) { i = 0; state = PUSH; } else { register int j; for (j = 0; j < totaldfm1; ++j) printf ("%d ", value [j]); printf ("%d\n", value [j]); state = POP; } break; case PUSH: if (i >= nlev) state = POP; else { value [df--] = i; state = WORK; } break; case POP: if (df >= totaldfm1) state = EXIT; else { i = value [++df] + 1; state = PUSH; } break; } } } Pascal devotees will note that Program 4 doesn't require any non-Pascal control structures (although the _switch_ has to be replaced with a chain of if ... else if ... else ... constructs. That argument is probably the only really good argument in favor of the state-variable technique. METHOD II. Code copying. If code fragments in the `grdgen_aux' procedure are duplicated in a disciplined fashion, the code can indeed be unscrambled to a _goto_-less version. Note that any optimizer that performs interval analysis, node listings, or T1-T2 path compression will need to do the same sort of code copying as part of the optimization phase; I wouldn't be surprised if the object code generated by a good optimizing compiler for Program 2 resembles that generated for one of the following. PROGRAM 5. [main program is still the same] static int nlev; static int totaldf; static int value [MAXDF]; /* to hold current values of all df's */ grdgen_aux (df) { int i; for (;;) { for (;;) { if (df < 0) { /* Print a node */ register int j; for (j = 0; j < (totaldf - 1); ++j) printf ("%d ", value [j]); printf ("%d\n", value [j]); break; } i = 0; if (i >= nlev) break; /* This probably can't happen */ value [df--] = i; } for (;;) { /* Develop another node */ if (df >= (totaldf - 1)) return; i = value [++df] + 1; if (i < nlev) { value [df--] = i; break; } } } } grdgen(df,nl) int df; /* no. of degrees of freedom */ int nl; /* no. of levels each df */ { totaldf=df; nlev = nl; grdgen_aux (df - 1); } Program 5 was generated by a reasonable mechanical technique, given Program 2. We see that the control structures are needlessly complex; in particular, the statement marked, /*this probably can't happen*/, is executed only if the number of levels is zero or fewer. Since the program generates null output in that case, it probably pays to check nlev in advance and simplify the control structures, yielding the following. PROGRAM 6. [guess what? I haven't changed the main program.] static int nlev; static int totaldfm1; static int value [MAXDF]; /* to hold current values of all df's */ grdgen_aux (df) { int i; for (;;) { register int j; while (df >= 0) { i = 0; value [df--] = i; } for (j = 0; j < totaldfm1; ++j) /* Print a node */ printf ("%d ", value [j]); printf ("%d\n", value [j]); for (;;) { /* Develop another node */ if (df >= totaldfm1) return; i = value [++df] + 1; if (i < nlev) { value [df--] = i; break; } } } } grdgen(df,nl) int df; /* no. of degrees of freedom */ int nl; /* no. of levels each df */ { if (nl <= 0) return; /* Sanity check */ totaldfm1 = df - 1; nlev = nl; grdgen_aux (totaldfm1); } Once again, we can move `grdgen_aux' in line, and provide trivial optimizations. The final version then looks like: PROGRAM 7. [main program still hasn't changed] grdgen (df, nlev) register int df; /* no. of degrees of freedom */ register int nlev; /* no. of levels each df */ { register int i; register int j; register int totaldfm1 = df - 1; static int value [MAXDF]; /* to hold current values of all df's */ for (;;) { while (df >= 0) { /* Set up initial values */ i = 0; value [df--] = i; } for (j = 0; j < totaldfm1; ++j) /* Print a node */ printf ("%d ", value [j]); printf ("%d\n", value [j]); for (;;) { /* Develop another node */ if (df >= totaldfm1) return; i = value [++df] + 1; if (i < nlev) { value [df--] = i; break; } } } } There is another choice for code to be copied: we can, instead of Program 5, come up with: PROGRAM 8. [same main program] static int nlev; static int totaldf; static int value [MAXDF]; /* to hold current values of all df's */ grdgen_aux (df) { int i; for (;;) { if (df >= 0) i = 0; /* Initialize a level */ else { /* Print a node */ register int j; for (j = 0; j < (totaldf - 1); ++j) printf ("%d ", value [j]); printf ("%d\n", value [j]); if (df >= totaldf - 1) return; /* Probably can't happen */ i = value [++df] + 1; /* Advance to next node */ } for (;;) { /* Finish a level */ if (i < nlev) { value [df--] = i; break; } if (df >= (totaldf - 1)) return; i = value [++df] + 1; /* Advance to next node */ } } } grdgen(df,nl) int df; /* no. of degrees of freedom */ int nl; /* no. of levels each df */ { totaldf=df; nlev = nl; grdgen_aux (df - 1); } Once again, there are branches that can't be taken, this time unless the number of degrees of freedom is <=0, and there are needlessly complex control structures. We can clean those up as before: PROGRAM 9. [same main program] static int nlev; static int totaldfm1; static int value [MAXDF]; /* to hold current values of all df's */ grdgen_aux (df) { int i; for (;;) { if (df >= 0) i = 0; /* Initialize a level */ else { /* Print a node */ register int j; for (j = 0; j < totaldfm1; ++j) printf ("%d ", value [j]); printf ("%d\n", value [j]); i = value [++df] + 1; /* Advance to next node */ } while (i >= nlev) { if (df >= totaldfm1) return; i = value [++df] + 1; /* Advance to next node */ } value [df--] = i; } } grdgen(df,nl) int df; /* no. of degrees of freedom */ int nl; /* no. of levels each df */ { if (df <= 0) return; /* Sanity check */ totaldfm1 = df - 1; nlev = nl; grdgen_aux (df - 1); } And, just as with Program 7, we bring _grdgen_aux_ inline, and do some more trivial optimization: PROGRAM 10. [still the same main program] grdgen (df, nlev) int df; /* no. of degrees of freedom */ register int nlev; /* no. of levels each df */ { register int totaldfm1; register int i; register int j; static int value [MAXDF]; /* to hold current values of all df's */ if (df <= 0) return; /* Sanity check */ totaldfm1 = df - 1; for (;;) { if (df >= 0) i = 0; /* Initialize a level */ else { /* Print a node */ for (j = 0; j < totaldfm1; ++j) printf ("%d ", value [j]); printf ("%d\n", value [j]); ++i; /* Advance to next node */ df = 0; } while (i >= nlev) { if (df >= totaldfm1) return; i = value [++df] + 1; /* Advance to next node */ } value [df--] = i; } } CONCLUSIONS. We have compe up with three `final versions:' Programs 4, 7, and 10. How do we choose among them. Program 4 is likely to compile to the smallest amount of code, as none of the program text has been duplicated. It also does not use any control structures that can't be coded in Pascal without a GO TO; this is useful in places where Pascal is the language of choice and GO TOs are verboten. The disadvantage of Program 4 is that the control structure remains somewhat unclear; the `spaghetti' _gotos_ have simply been replaced with assignments to a state variable, and the program state still shifts in a way that's difficult to describe. Programs 7 and 10 don't have that problem quite as much, since the control flows from top to bottom. In my opinion, Program 7 wins somewhat on readability, since its action is divided into several distinct phases, that correspond to intuitive actions like `begin a new level.' Program 10 has a somewhat simpler control structure, though, and some may prefer it. If performance is the object (and performance may often be improved substantially by eliminating recursion), then I'd code all three, instrument them, and use the fastest. There is no substitute for the actual data from an instrumented program if you're after speed. Kevin Kenny UUCP: {ihnp4,pur-ee,convex}!uiucdcs!kenny Department of Computer Science ARPA Internet or CSNet: kenny@CS.UIUC.EDU University of Illinois BITNET: kenny@UIUCDCS.BITNET 1304 W. Springfield Ave. Urbana, Illinois, 61801 Voice: (217) 333-6680
rob@kaa.eng.ohio-state.edu (Rob Carriere) (07/06/88)
In article <879@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >In Algorithmic Language and Program Development, Bauer and Wossner, they cite >Paterson and Hewitt as proving, essentially, recursion is more powerful than >iteration. > I don't know the learned gentlemen, but it is certainly true that for anything that can run on a computer, recursion is *at most* as strong as iteration. Proof: the CPU is an iterative device, not a recursive one (it iterates through its' microcode or eqv) and it can excecute your program. Since a computer with unbounded memory is as strong as a Universal Turing machine, I have this nagging feeling that the proof of P&H was intended for a much more restricted environment than either B&W or the poster are (is) assuming. If I'm wrong, *do* tell me, this sounds interesting. Rob Carriere "He iterated until he had no recourse but to recurse his fate."
smryan@garth.UUCP (Steven Ryan) (07/07/88)
>>In Algorithmic Language and Program Development, Bauer and Wossner, they cite >>Paterson and Hewitt as proving, essentially, recursion is more powerful than >>iteration. >> >I don't know the learned gentlemen, but it is certainly true that for >anything that can run on a computer, recursion is *at most* as strong >as iteration. I will step aside. The bibliography reference is, I think, Paterson M S, Hewitt C E (1970): Comparative Schematology. Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, Woods Hole, Mass, 1970. New York: ACM 1970, p. 119-127 Have at it.
kenny@p.cs.uiuc.edu (07/07/88)
In an article written yesterday, I present: PROGRAM 7. >[main program still hasn't changed] >grdgen (df, nlev) > register int df; /* no. of degrees of freedom */ > register int nlev; /* no. of levels each df */ >{ > register int i; > register int j; > register int totaldfm1 = df - 1; > static int value [MAXDF]; /* to hold current values of all df's */ > > for (;;) { > while (df >= 0) { /* Set up initial values */ > i = 0; > value [df--] = i; > } > > for (j = 0; j < totaldfm1; ++j) /* Print a node */ > printf ("%d ", value [j]); > printf ("%d\n", value [j]); > > for (;;) { /* Develop another node */ > if (df >= totaldfm1) return; > i = value [++df] + 1; > if (i < nlev) { > value [df--] = i; > break; > } > } > } >} And I don't know what posessed me. The program can be simplified quite a bit. One of the assignments to i is useless, and a `break' statement can be drawn out of a loop. While no version is truly final, I'd prefer the following: PROGRAM 7A. [main program still hasn't changed] grdgen (df, nlev) register int df; /* no. of degrees of freedom */ register int nlev; /* no. of levels each df */ { register int i; register int j; register int totaldfm1 = df - 1; static int value [MAXDF]; /* to hold current values of all df's */ for (;;) { while (df >= 0) /* Set up initial values */ value [df--] = 0; for (j = 0; j < totaldfm1; ++j) /* Print a node */ printf ("%d ", value [j]); printf ("%d\n", value [j]); do { /* Develop another node */ if (df >= totaldfm1) return; i = value [++df] + 1; } while (i >= nlev); value [df--] = i; } } BTW, the program analysis techniques that I've been promulgating *do* come up with this fragment; I was just careless running them by hand (The fact that they *can* be automated doesn't mean that they *have* been automated). The more I look at this version, the more I like it. The loop breaks down into three steps: initialize, print a node, increment some index. It's particularly satisfying that a series of essentially mechanical steps was able to derive an iterative version as clean as this from the original recursive version. I doubt I'd have done as well setting out to write an iterative version by hand.
bill@proxftl.UUCP (T. William Wells) (07/07/88)
In article <4700015@m.cs.uiuc.edu>, kenny@m.cs.uiuc.edu writes: > > On the discussion of whether or not `recursion is necessary,' I have > at least a nickel's worth of comment. The example shown is frightful! > [...very long description of recursion elimination] It is the fact that most (but not all) recursion can be eliminated by techniques similar to those he describes that I advocate always giving an "it has to be recursive" routine a thorough examination to see whether that is true or not. However, I rarely write recursive routines, not because I optimize the recursion out, but because my programming habits are such that I almost always think first of iteration. When iteration is possible, it is usually better than recursion. Should that fail, then I write it recursively. Then I try to optimize it out. The only routines that this routinely fails for is data structure traversal routines where backup is necessary.
nevin1@ihlpf.ATT.COM (00704a-Liber) (07/08/88)
In article <836@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: |Operators are conceptually distinct from function calls, both from the |programmers point of view, in how formulas are written, and from the |point of view of the compiler, in how the symbols and their operands are |identified. Operators are NOT conceptually different from functions! Conceptually, operators are just a notational convienence for functions, period. -- _ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194 ' ) ) You are in a little twisting maze of / / _ , __o ____ email paths, all different. / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah
nevin1@ihlpf.ATT.COM (00704a-Liber) (07/08/88)
In article <4700015@m.cs.uiuc.edu> kenny@m.cs.uiuc.edu writes: >Recursion can *always* be >eliminated, if necessary by setting up an auxiliary stack. If you are using an auxiliary stack, then you haven't eliminated recursion, you have just moved it from being implicitly done by the function call mechanism to being explicitly done by having your program save/restore the values on your auxiliary stack. If, in all cases, you can get rid of the stack *model*, then I will agree that recursion can always be eliminated. -- _ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194 ' ) ) You are in a little twisting maze of / / _ , __o ____ email paths, all different. / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah
smryan@garth.UUCP (Steven Ryan) (07/09/88)
>>Recursion can *always* be >>eliminated, if necessary by setting up an auxiliary stack. > >If you are using an auxiliary stack, then you haven't eliminated recursion, >you have just moved it from being implicitly done by the function call Recursion usually refers to direct or indirect self-calling. Using an explicit auxillary stack with a loop is then elimenating recursion. An auxillary stack can be added to any loop (sensibly or not), so this means every loop is potentially recursive. In this case the term 'recursion' no longer conveys useful information. It may sound like it's all done with mirrors (it is), but the distinction is useful.
kenny@m.cs.uiuc.edu (07/11/88)
/* Written 1:42 pm Jul 9, 1988 by wayne@dsndata.uucp in m.cs.uiuc.edu:comp.lang.c */
I used to think that recursion was unnecssary and very expensive, but
now i am not so sure. what about the cases where you recurse from
more than one place? can you do that without a stack of flags and
lots of ifs? an example, how would you do something like this:
[example deleted]
/* End of text from m.cs.uiuc.edu:comp.lang.c */
You do it with a stack of state variables, true, but it's ideal to
encode the choice of return point into a single state variable, and
`switch' on it. You wind up with code that's very similar in
appearance to Program 4 in my earlier posting, but possibly with more
states.
In any case, though, most `recursions from more than one place' wind
up being used in `divide and comquer' techniques, and the trick here
is that one of them is generally a tail recursion. Tail recursions
can get folded out immediately (just change the parameter values and
branch to the top), leaving only the internal recursion to deal with.
For instance, consider the following procedure to print a tree, in
inorder:
struct node {
struct node *left;
struct node *right;
char *content;
};
ptree (n)
struct node *n;
{
if (n -> left) ptree (n -> left);
printf ("%s\n", n -> content);
if (n -> right) ptree (n -> right);
}
The first thing we do is eliminate the tail recursion, trivially:
ptree (n)
struct node *n;
{
start:
if (n -> left) ptree (n -> left);
printf ("%s\n", n -> content);
n = n -> right;
if (n) goto start;
}
Now we use an explicit stack to attack the remaining recursion, and don't need a state variable for the return address:
ptree (n)
struct node *n;
{
struct node *stack [MAXDEPTH];
int depth = 0;
start: if (n -> left) {
stack [depth++] = n;
n = n -> left;
goto start;
finish: n = stack [--depth];
}
printf ("%s\n", n -> content;
n = n -> right;
if (n) goto start;
if (depth) goto finish;
}
Now we untangle the spaghetti:
ptree (n)
struct node *n;
{
struct node *stack [MAXDEPTH];
int depth = 0;
for (;;) {
while (n -> left) {
stack [depth++] = n;
n = n -> left;
}
for (;;) {
printf ("%s\n", n -> content);
n = n -> right;
if (n) break;
if (depth == 0) return; /* 2-level break */
n = stack [--depth];
}
}
}
I agree that the recursive formulation is *much* clearer, which is why
I contend that really good optimizing compilers shoud do this for you.
Those of us who work in Fortran have to do it by hand.
BTW, I know that there are clearer ways to write the procedure
non-recursively; I was illustrating the mechanical way that an
optimizer would get from here to there.flaps@dgp.toronto.edu (Alan J Rosenthal) (07/12/88)
16012_3045@uwovax.uwo.ca (Paul Gomme) writes: >>Am I totally missing something, or is this not a multidimensional array: >>int array[10][15]; >>?? swarbric@tramp.Colorado.EDU (Frank Swarbrick) writes: >Try that sort of thing under MS-DOS, with a _BIG_ matrix -- try >something like: > int array[200][200]; >I've tried this sort of thing with Turbo C, and know someone who checked out >MSC for me. The compiler choked on it because the array exceeds 64K. However, >I've used a Fortran compiler which will let me create such matrices with >absolutely no complaint. GEE, this is not part of the C language. The purpose of a compiler is to hide, or possibly, in the case of MS-DOS, apologize for, the architecture. If you declare an object of greater size than 64K, pointers to it should use a different segment register value for accesses to elements 32768 and beyond. This isn't harder to do in C than in Fortran. In Fortran under MS-DOS you would also have to have every function decide for each of its input parameters whether it is a pointer-to-64K-or-less or a pointer-to-more-than-64K. Don't judge the C programming language by a few C compilers (and I use the term `C' loosely). MS-DOS C compilers seem only to accept a subset of the C language because it allows them to compile certain benchmarks into faster code. ajr -- owotd (rot13): fabgentf
nevin1@ihlpf.ATT.COM (00704a-Liber) (07/15/88)
In article <901@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >I (Nevin Liber) wrote: >>If you are using an auxiliary stack, then you haven't eliminated recursion, >>you have just moved it from being implicitly done by the function call >Recursion usually refers to direct or indirect self-calling. Using an >explicit auxillary stack with a loop is then elimenating recursion. I don't buy that. The 'algorithm' you are using is STILL recursive; all you have done is change the 'implementation' of the recursion. If you can eliminate the stack, then and only then have you eliminated the recursion. BTW, this is why tail recursion can truly be eliminated. With tail recursion, you need not store *any* values (state information) on the stack (because you never return to it), and the stack is effectively eliminated. -- _ __ NEVIN J. LIBER ..!att!ihlpf!nevin1 (312) 979-???? ' ) ) You are in a twisty maze of little / / _ , __o ____ email paths, all different. / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah
atbowler@watmath.waterloo.edu (Alan T. Bowler [SDG]) (07/15/88)
In article <817@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: > >By only offering static allocation, the compiler does not have to support >any overhead at all. A C program must keep the stack pointer correctly >aligned and rest of the protocol straight even if it doesn't use the stack >because somebody it calls may use the stack. Similarily, in supporting >recursion, the stack has to be maintained in case some called program needs >the stack. Further, supporting recursion means all automatic variables must >be mapped into the stack because the procedure may recurse indirectly. >Forbidding recursion means the compiler can map automatic variables into >static areas. > Then again depending on the machine archetecture, access to something mapped to a stack frame may be cheaper and faster than statically allocated memory. It depends on the addressing mechanisms of the machine, and the skill of whoever does the stack design and call/return mechanism. The blanket statement that stack accesses were more expensive than static memory accesses was true in the past, but stopped being universally true sometime in the 1960's. As hardware caches become more important, and as addressing extensions are added to increase the address space of existing architectures, the tradoff between stack and static allocation changes.
tat00@amdahl.uts.amdahl.com (Tom Thackrey) (07/16/88)
In article <8807121629.AA07169@explorer.dgp.toronto.edu> flaps@dgp.toronto.edu (Alan J Rosenthal) writes: > >swarbric@tramp.Colorado.EDU (Frank Swarbrick) writes: >>Try that sort of thing under MS-DOS, with a _BIG_ matrix -- try >>something like: >> int array[200][200]; >>I've tried this sort of thing with Turbo C, and know someone who checked out >>MSC for me. The compiler choked on it because the array exceeds 64K. However, Whomever checked MSC didn't RTFM or (s)he would have used the right model and it would have compiled correctly >GEE, this is not part of the C language. The purpose of a compiler >is to hide, or possibly, in the case of MS-DOS, apologize for, the >architecture. If you declare an object of greater size than 64K, >pointers to it should use a different segment register value for >accesses to elements 32768 and beyond. 32768 elements??? try 64k bytes. >Don't judge the C programming language by a few C compilers (and I use >the term `C' loosely). MS-DOS C compilers seem only to accept a subset >of the C language because it allows them to compile certain benchmarks >into faster code. I only use MSC (on the pc) and it is a full implementation and very close to the 'current' ANSI proposed standard. It has several extensions to make it easier to generate efficient code for the 808x and 80x86 cpus. My problem is trying to port programs written in MSC back to Unix where the compiler does not support some of the proposed ANSI features. -- Tom Thackrey tat00@amdahl.uts.amdahl.com <=> amdahl!tat00 [ My opinions are only my own. ]
smryan@garth.UUCP (Steven Ryan) (07/17/88)
[Suddenly, a pittrap opens beneath our hero's toes. From the darkness are heard faint cries of `my mainframe is bigger than your mainframe.' He neatly pirouettes out of danger.] >Then again depending on the machine archetecture, access to something >mapped to a stack frame may be cheaper and faster than statically >... I see three possibilities: (1) On the hardware, static nonrecursive code is faster than stack-based recursive code. Fortran wins; C loses. (2) Static and stack code are equally well supported. Fortran wins; C wins. (3) Stack code is faster than nonrecursive static code. C wins. Also, Fortran wins. Although a standard conforming *program* cannot be recursive, the implementation is unrestricted. A compiler can map a program into static nonrecursive code, stack-based recursive code, heap-based multithreaded recursive and reentrant code, or anything else as long as it accepts nonrecursive code. Is this cheating? Well..... This is a case of underconstraining the solution so that the implementor has greater freedom of action. A Fortran compiler writer has that many fewer constraints than C hence that much more freedom. The Fortran compiler may not be better but certainly will not be worse. This is similar to the alias ban in Fortran. [NO! I'm starting that again. This is just a fer instance, not an agreement/disagreement.] The Fortran optimiser can depend on the alias ban to produce better code than C. Doesn't have to, and it won't effect a conforming program either way. In general, the fewer constraints that are put on a compiler, or any other program, the more freedom the programmer has for getting any particular implementation fast. Hafa an godne daege. sm ryan ---------------------------------------- Bucky Bug sez: Poor Mother Earth.. No one takes care of her in her old age.. - Odd Bodkins
smryan@garth.UUCP (Steven Ryan) (07/17/88)
>I don't buy that. The 'algorithm' you are using is STILL recursive; all >you have done is change the 'implementation' of the recursion. I disagree, not with the thought, but with the terminology. But as long as each of us is clear about how we are using the terms, there is no need to fight. sm ryan The question is--who is the master, you or the words. -- h dumpty Does a tree falling in an empty forest make a sound?
smryan@garth.UUCP (Steven Ryan) (07/17/88)
>This is similar to the alias ban in Fortran. [NO! I'm starting that again.
^
[NO! I'm NOT starting that again.
Oh, well.