rjchen@phoenix.Princeton.EDU (Raymond Juimong Chen) (02/29/88)
I don't have a copy of dpANS so I don't know if this is addressed
in it. I also don't know if this has been discussed and rejected
by the Committee, so here goes...
Propose that there be a way to declare "true functions", ie, functions
whose return values depend on and are solely determined by the arguments
passed to it. They also have no side-effects.
Simple examples: min() max() abs() pow() time_diff() etc.
This would be a hint to the compiler that such function calls have
no side-effects and therefore can
1. be optimized away in expressions such as
if (0 * min(a,b)) ...
2. be calculated only once if the arguments are identical
in different statements:
foo = (time_diff(start, end) + bar) * snerg;
/* ... statements which do not alter start or end */
oog = time_diff(start, end);
3. be calculated at any time provided the arguments are known.
This also allows you to use such "true functions" in DEBUG macros
without having the compiler generate idle code. for example,
DEBUG(("x^2 is now %f\n", pow(x,2)));
(Normally, the compiler would have to generate a call to pow(), since
it doesn't know that pow() has no side-effects--even when DEBUG if
#define'd to a null string.)
Implementation:
I can think of two ways this could be implemented. Let foo() be a
"true function".
register int foo(...)
const int foo(...)
The first method is consistent with the notion of "register" as a
"hint to the compiler". The second is consistent with the notion of
"const" as "unchanging". (Observe that the use of "const" does not
conflict with soon-to-be-existing usage.
const char * foo(...)
and char * const foo(...)
would mean different things. One says that foo() returns a pointer to
a character in ROM, the other says that foo() returns a pointer to a
character which depends purely on the arguments. I don't know which
is which, however.)
The compiler can even check whether you're lying or not: If inside
your function you refer to anything other than an argument or a
local variable, or if you call a "non-true" function, then
the "trueness" of your function is suspect and can be
flagged by a suitably picky compiler (or lint).
Comments welcome.
--
Raymond Chen UUCP: ...allegra!princeton!{phoenix|pucc}!rjchen
BITNET: rjchen@phoenix.UUCP, rjchen@pucc
ARPA: rjchen@phoenix.PRINCETON.EDU
"Say something, please! ('Yes' would be best.)" - The Doctor
--
Raymond Chen UUCP: ...allegra!princeton!{phoenix|pucc}!rjchen
BITNET: rjchen@phoenix.UUCP, rjchen@pucc
ARPA: rjchen@phoenix.PRINCETON.EDU
"Say something, please! ('Yes' would be best.)" - The Doctordhesi@bsu-cs.UUCP (Rahul Dhesi) (02/29/88)
In article <1893@phoenix.Princeton.EDU> rjchen@phoenix.Princeton.EDU (Raymond Juimong Chen) writes: >Propose that there be a way to declare "true functions", ie, functions >whose return values depend on and are solely determined by the arguments >passed to it. They also have no side-effects. Such functions were almost but not quite included in Ada. They are discussed in the Rationale for Ada, published as a special SIGPLAN Notices issue in the early eighties. Declaring such functions is like using noalias--the compiler cannot easily confirm that what the programmer claims is really true. Only truly global flow analysis will do that, and if you are doing global flow analysis across separately compiled files, then there's no need for the programmer to know the difference anyway. -- Rahul Dhesi UUCP: <backbones>!{iuvax,pur-ee,uunet}!bsu-cs!dhesi
jbn@glacier.STANFORD.EDU (John B. Nagle) (03/01/88)
Declaration of "pure functions" doesn't really seem to be in keeping
with the spirit of C. This doesn't mean that I don't like the idea, though.
I put it in a dialect of Pascal in 1982, when I was working on program
verification. But the concept is perhaps too abstract for C. It would
fit better in Modula II, a more tightly constraining language.
John Nagleeric@snark.UUCP (Eric S. Raymond) (03/01/88)
In article <1893@phoenix.Princeton.EDU>, Raymond Juimong Chen writes: >Propose that there be a way to declare "true functions", ie, functions >whose return values depend on and are solely determined by the arguments >passed to it. They also have no side-effects. Compiler folklore (and at least one major dialect of Pascal in which you can declare them explicitly) calls such animals 'pure' functions. >Implementation: >I can think of two ways this could be implemented. Let foo() be a >"true function". > >register int foo(...) >const int foo(...) Not a bad idea. I'd prefer 'const' because it doesn't confuse the declaration of the function's (lack of) side-effects with the declaration of the storage class for its return type. Another kind of optimization this would permit would be inlining. Of course, the ANSI people will reject this on grounds of 'no prior art', even though it's a better and better-tested idea than 'noalias'. -- Eric S. Raymond (the mad mastermind of TMN-Netnews) UUCP: {{seismo,ihnp4,rutgers}!cbmvax,sdcrdcf!burdvax,vu-vlsi}!snark!eric Post: 22 South Warren Avenue, Malvern, PA 19355 Phone: (215)-296-5718
franka@mmintl.UUCP (Frank Adams) (03/02/88)
In article <2230@bsu-cs.UUCP> dhesi@bsu-cs.UUCP (Rahul Dhesi) writes: >In article <1893@phoenix.Princeton.EDU> rjchen@phoenix.Princeton.EDU (Raymond Juimong Chen) writes: >>Propose that there be a way to declare "true functions", ie, functions >>whose return values depend on and are solely determined by the arguments >>passed to it. They also have no side-effects. >Declaring such functions is like using noalias--the compiler cannot >easily confirm that what the programmer claims is really true. True, but the compiler can easily check for a set of conditions which is sufficient for a function to be a "true" function, and issue a warning if these are not met. Basically, the function may not access global or static variables, call any non-true functions, nor dereference a pointer. (I may be missing some conditions here.) This will cover a significant fraction of the functions in this category. (Particularly if we ignore the C "arrays are pointers" confusion.) Actually, I was thinking about this just the other day. I'm still not convinced that it is sufficiently useful to be included. Does anyone have any data on how many function calls a good compiler can eliminate by such a feature? -- Frank Adams ihnp4!philabs!pwa-b!mmintl!franka Ashton-Tate 52 Oakland Ave North E. Hartford, CT 06108
pardo@june.cs.washington.edu (David Keppel) (03/05/88)
[ True functions. How many func calls could we eliminate with this feature? ] Some advantages besides being able to "throw away" function calls are: (a) code motion (b) temporaries living across function calls I suspect these would have more optimizing effect than the number that we could throw away. ;-D on (Optimizing decompiler) Pardo