RE: pure and const functions

[Chris Lattner <sabre@nondot.org>]

> int fib(int n) {
>   if (n==0 || n==1) return n;
>   return fib(n-1) + fib(n-2);
> }

> According to the definitions given above, this function is const,
> but not total, because it does not return for negative n.

While this is true in a practical sense, given infinite resources, this is
certainly not the case.  Assuming you had a whole lot of stack space and
bunch of time, the negative values for 'n' would wrap around to positive
values.  Eventually it would get to 1 and terminate.

As this is the case, for this example...

int double_or_nothing (int n) {
  fib(n);
  return 2*n;
}

... it should be optimizable to:

int double_or_nothing (int n) {
  return 2*n;
}

...because on an ideal, theoretical, machine, they results are exactly the
same.

IOW: we don't try to predict stack overflow in other cases, so why should
     we have to worry about that possibility here?

There may be other cases where functions are "partial", can you give
another example?

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/~sabre/Projects/