A Theoretically Correct C++ Compiler

I just realized that a C++ compiler can never be theoretically correct. This follows from the fact that C++ templates are Turing Complete (no, really) and the halting problem. We can never say for sure whether a template expression is indeed infinitely recursive or is just taking too long to “parse”.

Sweet, but disappointing.

This entry was posted in Computers and tagged , , , . Bookmark the permalink.

2 Responses to A Theoretically Correct C++ Compiler

  1. John H says:

    What do you consider correct to be? If you disregard that a compiler is a compiler, and instead just consider it a program, then then its a program in which templates play the role of a platform independent programming language that runs in C++ compilers (like Java running in the JVM). I wouldn’t really want to pursue this thought much further, but as long as we’re talking theoretically.

    • Sanjoy says:

      I agree that this is a purely theoretical thought — if you are template metaprogramming to the point of hitting the halting problem, then you’re screwed as it is. 🙂

      I was referring to a _correct_ compiler as one which accepts all _correct_ programs (and produces an output which conforms correctly to the semantics of the programming language). Most compilers are not correct (and hence have issue trackers). My epiphany was that it is not even _possible_ to write a C++ compiler which translates all correct programs.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s