What is a minimal example of why it is not possible to predict call pattern of functions?

67 Views Asked by At

A stack makes it possible to execute subroutines in any order, nested subroutines and recursive subroutines, and to jump to and back from the subroutines, and to call functions with arbitrary arguments. This is important because it is impossible to predict the call pattern of the functions (and therefore impossible to print out all uses of subroutines explicitly in the instruction sequence), this answer says.

What is a minimal example of a program that shows that this (call pattern of functions) cannot be known beforehand?

1

There are 1 best solutions below

1
BipedalJoe On

Peter Cordes comment mentions functions pointers and I agree that is a good example. I also disagree with that the answer in the linked question, recursion, is true (the call pattern is predictable, just not how much of the call pattern will be executed), so it was good that I asked and got a clarified answer that I can agree with.

I came up with a minimal example as a program (as question states, "what is a minimal example of a program") that shows clearly how function pointers make it impossible to predict call pattern.

It has 10 functions, all called using a function pointer.

It then requests the function pointer value from the user (so that it could not be known at compile time), and executes the function. It then loops, and does it again, and again, and again.

The possible combinations of call pattern for the functions is 10^n I think, where n is number of times the loop is run. It becomes a billion if you run the loop 9 times.

That is a pretty good minimal example, that shows it with probability theory.

#include <stdio.h>

void a() {}
void b() {}
void c() {}
void d() {}
void e() {}
void f() {}
void g() {}
void h() {}
void i() {}
void j() {}

int main(void) 
{

    void (*foo)(); //to store memory address
    while (true) {
        printf("Now, read/input the  memory address: ");
        scanf ("%p", &foo);
        foo();
    }
    return 0;
}