79616702

Date: 2025-05-11 16:44:08
Score: 0.5
Natty:
Report link

Here's a reason why the undecidable grammar of C++ could be a problem. When we program using a typed programming language, we are implicitly dividing up the work that the grammar does into two components: one of which is the type system, and it's supposed to be relatively easy. The other is the input-output behaviour of the program, and that input-output behaviour is not something that we have made up, it's something that is given to us by the world, and (as we well know) there are perfectly good questions about the world which are undecidable.

The type system, on the other hand, is something that we invent, possibly motivated by some real-world problem. But we use a type system in order to tame the difficulty which raw input-output behaviour might threaten us with; it is, as it were, a pair of spectacles which, when we put them on, will show us the parts of the worlds which are comprehensible. And so when a compiler assigns types to a program, it is giving you some information about what your program will do when it is executed.So type systems should, when they are applied to a real-world problem, show us how the problem could be simplified. And in order to do this, the type system should give us a view of program which was simpler (in some way) to the program itself. C++ doesn't actually do this, because of the undecidability of the grammar of C++. And it's possible to define a type system in C++ which, when applied to an equality such as 1+1 = 2, typed the sides of this equation by types which were computationally extremely complex, and maybe even undecidable.

Now some programmers think that's just OK, because they know how to write programs in C++ which are a) valid and b) use only type expressions which happen to be decidable, but other programmers think that this is horrible. It's probably worth remarking that C++ and Java are, as it were, mirror images of each other: Java has a type system which is nice and clean and decidable, but it's a type system which will be weaker than it could be. On the other hand, C++ has a huge type system, and that type system will probably be able to come up with types which cannot be easily described by humans.

Reasons:
  • Long answer (-1):
  • No code block (0.5):
  • Low reputation (1):
Posted by: Graham White