Question

A programmer is having difficulty debugging the following C program. In theory, with infinite memory, this program would run forever but in practice, this program crashes because it runs out of memory.

Explain the behavior of the program by translating the definition of f into lambda calculus and then reducing the application f(f). This program assumes that the type checker does not check the types of arguments to functions.

int f(int (*g)(...)) { /* g points to a function that returns an int */
      return g(g);

}
int main() {

      int x;
      x = f(f);
      printf("Value of x = %d\n", x);
      return 0;

}

Answer 1

If we explain this using calculus.

let's assume

f(x) = X^2;

f(f(x)) = (f(x))^2 = (X^2)^2 = X^(2+2)

f(f(f(x))) = (f(f(x))^2 = ((f(x))^2)^2 = ((X^2)^2)^2 = X^(2+2+2)

------

f(f(f(f(f(f....... )))))) = X^(2+2+2+ .........)

= which will be great value

if we go like this forever.

  

int f(int (*g)(...)) { /* g points to a function that returns an int */

return g(g);

}

int main() {

int x;

x = f(f);

printf("Value of x = %d\n", x);

return 0;

}

  

If we consider this program each time function is called a stack frame is

generated in the memory and as we see this function calling will go forever

then stack boundry will be cross and it will result in a run-time program

crash which stack overflow.