Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   functions with no side-effects (http://www.velocityreviews.com/forums/t315740-functions-with-no-side-effects.html)

Rouben Rostamian 10-12-2003 08:33 PM

functions with no side-effects
 
Consider the following illustrative program:

#include <stdio.h>

double f(double x)
{
return x*x;
}

double g(double x)
{
puts("hello world");
return x*x;
}

int main(void)
{
double s = 0.0;
int i;

for (i=0; i<10000; i++)
s += f(2.0); /* f(2.0) is always 4.0 */

for (i=0; i<10000; i++)
s += g(2.0); /* g(2.0) is always 4.0 */

printf("s = %g\n", s);
return 0;
}

Does standard C provide a mechanism whereby one can reassure the
compiler that the function f() produces no side-effects while the
function g() has side-effects?

If such a mechanism existed, then an optimizing compiler might replace
f(2.0) by 4.0 to avoid 10000 function calls, but it wouldn't replace
g(2.0) by 4.0.

Something in the back of my mind tells me that such a mechanism exists
but I may be (a) just imagining it; (b) thinking of a non-standard
compiler; or (c) a language other than C.

I would appreciate it if someone would set me straight.

--
Rouben Rostamian <rostamian@umbc.edu>

Ben Pfaff 10-12-2003 08:46 PM

Re: functions with no side-effects
 
rouben@pc18.math.umbc.edu (Rouben Rostamian) writes:

> Does standard C provide a mechanism whereby one can reassure the
> compiler that the function f() produces no side-effects while the
> function g() has side-effects?


No. There is a GNU C extension for that, but it's non-standard.

The `inline' keyword in C99 may help, however.

> If such a mechanism existed, then an optimizing compiler might replace
> f(2.0) by 4.0 to avoid 10000 function calls, but it wouldn't replace
> g(2.0) by 4.0.


In the code you presented, the compiler can easily tell that f()
has no side effects, because it has already seen f() when it
compiles the call to it.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

Jeremy Yallop 10-12-2003 09:15 PM

Re: functions with no side-effects
 
Rouben Rostamian wrote:
> Does standard C provide a mechanism whereby one can reassure the
> compiler that the function f() produces no side-effects while the
> function g() has side-effects?


There's isn't a standard mechanism for doing this, although some
compilers have extensions. GCC, for example, supports so-called
"function attributes" which allow you to supply this information to
the compiler:

http://gcc.gnu.org/onlinedocs/gcc-3....n%20Attributes

(see "const" and "pure" in particular). In trivial cases, such as the
ones in your example, an optimizing compiler should be able to work
such things out by itself, but it's not always possible:

int every(int predicate(const void *),
const void *const*vals,
size_t nvals)
{
for (size_t i = 0; i < nvals; i++) {
if (!predicate(vals[i])) {
return 0;
}
}
return 1;
}

"every" itself doesn't have any side effects, but the function called
through "predicate" might; it can't be determined at compile-time in
general. If you have some way of telling the compiler that
"predicate" has no side effects then it could, in theory, do all sorts
of interesting optimizations, including memoizing both the "predicate"
and "every" functions, avoiding the overhead of calling them multiple
times with the same arguments. I doubt that any C compilers actually
do that sort of thing (unless the argument values are known at
compile-time), but it's by no means unknown in functional languages
(where side-effect free functions are more common).

Jeremy.

cody 10-12-2003 10:36 PM

Re: functions with no side-effects
 
"Jeremy Yallop" <jeremy@jdyallop.freeserve.co.uk> schrieb im Newsbeitrag
news:bmcgab$k7im1$1@ID-114079.news.uni-berlin.de...
>

http://gcc.gnu.org/onlinedocs/gcc-3....s.html#Functio
n%20Attributes
>
> (see "const" and "pure" in particular). In trivial cases, such as the
> ones in your example, an optimizing compiler should be able to work
> such things out by itself, but it's not always possible:
>
> int every(int predicate(const void *),
> const void *const*vals,
> size_t nvals)
> {
> for (size_t i = 0; i < nvals; i++) {
> if (!predicate(vals[i])) {
> return 0;
> }
> }
> return 1;
> }
>
> "every" itself doesn't have any side effects, but the function called
> through "predicate" might; it can't be determined at compile-time in
> general. If you have some way of telling the compiler that
> "predicate" has no side effects then it could, in theory, do all sorts
> of interesting optimizations, including memoizing both the "predicate"
> and "every" functions, avoiding the overhead of calling them multiple
> times with the same arguments. I doubt that any C compilers actually
> do that sort of thing (unless the argument values are known at
> compile-time), but it's by no means unknown in functional languages
> (where side-effect free functions are more common).



That should be no problem. If one could apply such attributes to function
pointer too,
then the compiler would know wheather side effects are possible or not:

int every(int predicate(pure const void *), /* note "pure" in the
declaration of the function pointer */
const void *const*vals,
size_t nvals)
{
for (size_t i = 0; i < nvals; i++) {
if (!predicate(vals[i])) {
return 0;
}
}
return 1;
}

if the function pointer is declared without pure one can pass every function
he likes, and the compiler must assume that
every() has side effects. But if you declare the function pointer as pure
one can only pass pure functions to every() and the compiler
can assume that every() doesn't have any side effects.

i don't know wheather or not that is the case, if not consider this as a
proposal for future compilers.

--
cody

[Freeware, Games and Humor]
www.deutronium.de.vu || www.deutronium.tk



Dan Pop 10-13-2003 04:19 PM

Re: functions with no side-effects
 
In <878ynqdw1e.fsf@pfaff.stanford.edu> Ben Pfaff <blp@cs.stanford.edu> writes:

>rouben@pc18.math.umbc.edu (Rouben Rostamian) writes:
>
>> Does standard C provide a mechanism whereby one can reassure the
>> compiler that the function f() produces no side-effects while the
>> function g() has side-effects?

>
>No. There is a GNU C extension for that, but it's non-standard.
>
>The `inline' keyword in C99 may help, however.


How? What is preventing a C99 inline function from calling printf?

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de

CBFalconer 10-13-2003 08:51 PM

Re: functions with no side-effects
 
Dan Pop wrote:
> Ben Pfaff <blp@cs.stanford.edu> writes:
> > rouben@pc18.math.umbc.edu (Rouben Rostamian) writes:
> >
> >> Does standard C provide a mechanism whereby one can reassure
> >> the compiler that the function f() produces no side-effects
> >> while the function g() has side-effects?

> >
> > No. There is a GNU C extension for that, but it's non-standard.
> >
> > The `inline' keyword in C99 may help, however.

>
> How? What is preventing a C99 inline function from calling printf?


I think you misconstrued Bens comments. If the function is
'inline' the compiler is generating its code within the piece that
calls it, so it can look at the generated sequence and see that
there are no side effects, without any help.

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!



Dan Pop 10-14-2003 12:00 PM

Re: functions with no side-effects
 
In <3F8AFE69.C093D8FD@yahoo.com> CBFalconer <cbfalconer@yahoo.com> writes:

>Dan Pop wrote:
>> Ben Pfaff <blp@cs.stanford.edu> writes:
>> > rouben@pc18.math.umbc.edu (Rouben Rostamian) writes:
>> >
>> >> Does standard C provide a mechanism whereby one can reassure
>> >> the compiler that the function f() produces no side-effects
>> >> while the function g() has side-effects?
>> >
>> > No. There is a GNU C extension for that, but it's non-standard.
>> >
>> > The `inline' keyword in C99 may help, however.

>>
>> How? What is preventing a C99 inline function from calling printf?

>
>I think you misconstrued Bens comments. If the function is
>'inline' the compiler is generating its code within the piece that
>calls it, so it can look at the generated sequence and see that
>there are no side effects, without any help.


It is not inline that magically does that, but the fact that the function
definition is visible to the compiler. You don't need inline in order to
make the function definition visible to the compiler.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de

CBFalconer 10-14-2003 04:00 PM

Re: functions with no side-effects
 
Dan Pop wrote:
>
> In <3F8AFE69.C093D8FD@yahoo.com> CBFalconer <cbfalconer@yahoo.com> writes:
>
> >Dan Pop wrote:
> >> Ben Pfaff <blp@cs.stanford.edu> writes:
> >> > rouben@pc18.math.umbc.edu (Rouben Rostamian) writes:
> >> >
> >> >> Does standard C provide a mechanism whereby one can reassure
> >> >> the compiler that the function f() produces no side-effects
> >> >> while the function g() has side-effects?
> >> >
> >> > No. There is a GNU C extension for that, but it's non-standard.
> >> >
> >> > The `inline' keyword in C99 may help, however.
> >>
> >> How? What is preventing a C99 inline function from calling printf?

> >
> >I think you misconstrued Bens comments. If the function is
> >'inline' the compiler is generating its code within the piece that
> >calls it, so it can look at the generated sequence and see that
> >there are no side effects, without any help.

>
> It is not inline that magically does that, but the fact that the function
> definition is visible to the compiler. You don't need inline in order to
> make the function definition visible to the compiler.


In theory, yes. However, do you know of any compilers that go to
the trouble of characterizing each function in that manner? I
suspect they all limit their knowledge to whatever is carried in
the prototype.

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!


Kevin Bracey 10-14-2003 05:04 PM

Re: functions with no side-effects
 
In message <3F8BFB2F.2C93549D@yahoo.com>
CBFalconer <cbfalconer@yahoo.com> wrote:

> Dan Pop wrote:
> >
> > It is not inline that magically does that, but the fact that the function
> > definition is visible to the compiler. You don't need inline in order to
> > make the function definition visible to the compiler.

>
> In theory, yes. However, do you know of any compilers that go to
> the trouble of characterizing each function in that manner? I
> suspect they all limit their knowledge to whatever is carried in
> the prototype.


I've not seen one. However, the majority of "pure" functions in practice are
likely to be ones small enough for a real-world compiler to consider
auto-inlining, which would achieve a similar effect.

--
Kevin Bracey, Principal Software Engineer
Tematic Ltd Tel: +44 (0) 1223 503464
182-190 Newmarket Road Fax: +44 (0) 1223 503458
Cambridge, CB5 8HE, United Kingdom WWW: http://www.tematic.com/

Dan Pop 10-15-2003 12:14 PM

Re: functions with no side-effects
 
In <3F8BFB2F.2C93549D@yahoo.com> CBFalconer <cbfalconer@yahoo.com> writes:

>Dan Pop wrote:
>>
>> In <3F8AFE69.C093D8FD@yahoo.com> CBFalconer <cbfalconer@yahoo.com> writes:
>>
>> >Dan Pop wrote:
>> >> Ben Pfaff <blp@cs.stanford.edu> writes:
>> >> > rouben@pc18.math.umbc.edu (Rouben Rostamian) writes:
>> >> >
>> >> >> Does standard C provide a mechanism whereby one can reassure
>> >> >> the compiler that the function f() produces no side-effects
>> >> >> while the function g() has side-effects?
>> >> >
>> >> > No. There is a GNU C extension for that, but it's non-standard.
>> >> >
>> >> > The `inline' keyword in C99 may help, however.
>> >>
>> >> How? What is preventing a C99 inline function from calling printf?
>> >
>> >I think you misconstrued Bens comments. If the function is
>> >'inline' the compiler is generating its code within the piece that
>> >calls it, so it can look at the generated sequence and see that
>> >there are no side effects, without any help.

>>
>> It is not inline that magically does that, but the fact that the function
>> definition is visible to the compiler. You don't need inline in order to
>> make the function definition visible to the compiler.

>
>In theory, yes. However, do you know of any compilers that go to
>the trouble of characterizing each function in that manner? I
>suspect they all limit their knowledge to whatever is carried in
>the prototype.


They don't have to do it for inline functions, either. Why should a
compiler care whether an inline function has side effects or not? The
reasons, whatever they are, apply to both kinds of functions.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de


All times are GMT. The time now is 04:30 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.