Re: a question about const and pure functions.

[Geert Bosch <bosch at gnat dot com>]

On Nov 11, 2004, at 08:57, Roger Sayle wrote:
> A "const" call has no side-effects and its results depend purely on the
> values of its arguments.  This closely follows the mathematical notion
> of a "function".  A "pure" call has no side-effects, but in addition to
> it's arguments may depend upon the memory/global variables of the 
> system.

The terms no "side effects" and "values of its arguments" are a
bit imprecise.  For example, there is no reason that a "const"
or "pure" call can't raise an exception or memoize results.
I find the definition in the Ada standard (ISO/IEC 8652:1995)
very useful in practice. Apart from Ada legality rules, the
definition is stated entirely in terms of implementation permissions:

                        _Implementation Permissions_

 18. If a library unit is declared pure, then the implementation is
     permitted to omit a call on a library-level subprogram of the
     library unit if the results are not needed after the call.
     Similarly, it may omit such a call and simply reuse the results
     produced by an earlier call on the same subprogram, provided that
     none of the parameters are of a limited type, and the addresses
     and values of all by-reference actual parameters, and the values
     of all by-copy-in actual parameters, are the same as they were at
     the earlier call. This permission applies even if the subprogram
     produces other side effects when called.

Specification in terms of permissions is very useful, as it allows for
functions that are conceptually pure to:
  - memoize results
  - gather statistics
  - raise exceptions
  - produce diagnostic output
These could all be counted as side effects, but they still allow
us to take advantage of the permissions mentioned above.

Note the explicit mention of addresses *and* values of by-reference
parameters. We've had issues in Ada when declaring functions taking
String arguments as Pure for example. This could be an issue in C as
well. We'd like to optimize calls "strlen"-like functions, even if
we write to some unrelated memory. Conceptually, we're just passing
a constant array value. In the Ada case, the representation is even
a bit more complicated as it includes bounds information.

  -Geert