c++ - Why can't run-time polymorphism be solved at compile time?

Question

Consider:

#include<iostream>
using namespace std;

class Base
{
    public:
        virtual void show() { cout<<" In Base 
"; }
};

class Derived: public Base
{
    public:
       void show() { cout<<"In Derived 
"; }
};

int main(void)
{
    Base *bp = new Derived;
    bp->show();  // RUN-TIME POLYMORPHISM
    return 0;
}

Why does this code cause run-time polymorphism and why can not it be solved at compile time?

Answer 1

Because in the general case, it's impossible at compile time to determine what type it will be at run time. Your example can be resolved at compile time (see answer by @Quentin), but cases can be constructed that can't, such as:

Base *bp;
if (rand() % 10 < 5)
    bp = new Derived;
else
    bp = new Base;
bp->show(); // only known at run time

EDIT: Thanks to @nwp, here's a much better case. Something like:

Base *bp;
char c;
std::cin >> c;
if (c == 'd')
    bp = new Derived;
else
    bp = new Base;
bp->show(); // only known at run time 

Also, by corollary of Turing's proof, it can be shown that in the general case it's mathematically impossible for a C++ compiler to know what a base class pointer points to at run time.

Assume we have a C++ compiler-like function:

bool bp_points_to_base(const string& program_file);

That takes as its input program_file: the name of any C++ source-code text file where a pointer bp (as in the OP) calls its virtual member function show(). And can determine in the general case (at sequence point A where the virtual member function show() is first invoked through bp): whether the pointer bp points to an instance of Base or not.

Consider the following fragment of the C++ program "q.cpp":

Base *bp;
if (bp_points_to_base("q.cpp")) // invokes bp_points_to_base on itself
    bp = new Derived;
else
    bp = new Base;
bp->show();  // sequence point A

Now if bp_points_to_base determines that in "q.cpp": bp points to an instance of Base at A then "q.cpp" points bp to something else at A. And if it determines that in "q.cpp": bp doesn't point to an instance of Base at A, then "q.cpp" points bp to an instance of Base at A. This is a contradiction. So our initial assumption is incorrect. So bp_points_to_base can't be written for the general case.