2

The newly published draft mentions in [expr.prim.req]/6:

If the substitution of template arguments into a requirement would always result in a substitution failure, the program is ill-formed; no diagnostic required. [ Example:

template<typename T> concept C =
requires {
  new int[-(int)sizeof(T)];     // ill-formed, no diagnostic required
};

— end example ]

But why can't we guarantee the diagnostic to always fail, rather than skip the diagnostic?

L. F.
  • 19,445
  • 8
  • 48
  • 82
con ko
  • 1,368
  • 5
  • 18

1 Answers1

6

Requirement expressions can do pretty much anything. They can provoke further template substitutions, cascading outwardly through an arbitrary amount of code. And recall that template substitutions constitute a Turning complete language.

So you're asking the compiler to, given a Turing complete program, prove whether there is some input which causes that program to be well-formed. This is just a restatement of the Halting Problem. Just like the Halting Problem, there are simple cases where it's obvious the program halts/doesn't halt. But when you're dealing with a Turing-complete language, it can get arbitrarily complex.

The standard isn't going to force compilers to solve the Halting Problem.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
  • To my mind, languages that support cross-compilation should be designed so that the build process will be primitive-recursive rather than Turing-complete. Execution, of course, should be Turing complete except for resource constraints, but processing should be split into a build process which is guaranteed to complete (successfully or unsuccessfully) in finite time with no unbounded side effects in the build environment, and a separate execution process which may be performed in a separate execution environment. Turing-completeness in the build process is a bug, not a feature. – supercat Mar 03 '20 at 05:37
  • Thanks for your explaination. I'm only a senior high school student, so maybe something about Turing-complete is too haze to me for the time being. In spite of all this, I still want to ask you want's the difference between making it ill-formed and making the always-fail concept effective? Will a complier do any extra work if the latter is true? – con ko Mar 03 '20 at 05:40
  • 1
    @supercat: Did you comment on the wrong answer? This question has nothing to do with the build process or cross-compilation. – Nicol Bolas Mar 03 '20 at 05:40
  • @JohnDing See as well [What makes a language Turing-complete?](https://softwareengineering.stackexchange.com/questions/132385/what-makes-a-language-turing-complete) – Richard Chambers Mar 03 '20 at 05:43
  • @JohnDing: The Halting Problem is a famous programming question. The Halting problem asks you to devise an algorithm which takes a program and tells you whether that program will halt on all possible inputs. It is proven to be *impossible* to devise such an algorithm that works on all programs. Asking the compiler to detect expressions that will never evaluate to a valid expression is asking the compiler to solve the Halting Problem. The C++ standard doesn't ask compilers to do something which is proven impossible. – Nicol Bolas Mar 03 '20 at 05:47
  • @NicolBolas I partly understood what you want to tell me. Yet I don't know whether it is because the problem in my understanding, I think my question still goes the same. From what I can see, Maybe judging whether a requirements of a concept will always fail is an attemt to solve *the halting problem*, but after successfully ensuring a concept will always generate *Substisution Failure*, making it ill-formed or well-formed(always generate an error), I think, is not. – con ko Mar 03 '20 at 06:13
  • @JohnDing: "*but after successfully ensuring a concept will always generate Substisution Failure*" That's like saying "after I successfully violate the laws of Physics;" whatever comes after that statement is irrelevant because you *can't do that*. What you might be able to achieve if you could do the impossible thing doesn't matter because it *requires an impossible thing*. – Nicol Bolas Mar 03 '20 at 06:16
  • @NicolBolas From what I've learned about it, the attemt to check whether the constraint will always fail is not completely equivalent to *the Halting Problem*, because the latter requires to solve it whatever the program is, but the former only need to check the only code block. Hence, for some program, I agree it's impossible for a complier to check wether it'll always fail. But in some senarios, like the example given by the draft, we can just ensure that it'll always fail. I think the meaning of my question is about for those that can be checked to always fiail, why no diagnostic isrequired – con ko Mar 03 '20 at 06:26
  • @JohnDing: "*but the former only need to check the only code block*" A code block which represents code of arbitrary complexity, because said code block can 1) instantiate templates (which is effectively like running code. That is what "Turing-complete" means), and 2) can invoke `constexpr` functions (which is *exactly* like running code). An expression in C++ can do pretty much anything because it can call functions, instantiate templates, and the like. – Nicol Bolas Mar 03 '20 at 06:29
  • @JohnDing: "*But in some senarios, like the example given by the draft, we can just ensure that it'll always fail.*" The standard cannot deal in "some scenarios". C++ as a language allows code of arbitrary complexity to go into such an expression, so the standard must not impose a requirement which cannot be applied to code of arbitrary complexity. If its impossible to *always* give a diagnostic, then the standard can't say something wishy-washy like "give a diagnostic if it's pretty obvious that it won't work". Either a diagnostic is *required* or it isn't. – Nicol Bolas Mar 03 '20 at 06:32
  • @NicolBolas Yes, I agree all you've mentioned about the Halting Problem. But if I didn't misunderstand the draft, "C++ as a language allows code of arbitrary complexity to go into such an expression, so the standard must not impose a requirement which cannot be applied to code of arbitrary complexity." I'm afraid the standard is just exactly doing this... – con ko Mar 03 '20 at 06:38
  • @JohnDing: "*I'm afraid the standard is just exactly doing this...*" How? The code is ill-formed, but nobody is required to actually *detect* that the code is ill-formed. Implementations are not required to do the impossible thing of detecting this scenario, so there's no problem. – Nicol Bolas Mar 03 '20 at 06:40
  • @NicolBolas Yes, but if you said is really true, I think "no diagnostic required" equals to nothing, for nobody knows whether it is ill-formed or not. – con ko Mar 03 '20 at 06:43
  • @JohnDing: If you take out this rule, then it is *wrong* for a compiler to actually detect one of the simple, detectable cases. A compiler would be required to compile such a program; it could spit out a warning, but that's all. By having the NDR rule as it currently stands, a compiler could see some construct that grammatically would never work and give an error. But it wouldn't be required to investigate too deeply into the mass of template substitutions and compile-time function evaluations. Don't confuse "no diagnostic required" with "no diagnostic *allowed*". – Nicol Bolas Mar 03 '20 at 06:56
  • @NicolBolas "By having the NDR rule as it currently stands, a compiler could see some construct that grammatically would never work and give an error. But it wouldn't be required to investigate too deeply into the mass of template substitutions and compile-time function evaluations" That's what I exactly mean. But my problem is why it's measure to deal with those code which is "obvious wrong" is to make the program ill-formed, rather than do nothing? Is there any sense to do extra work which might generate a result which is not wanted by programmers?(e.g. thousands of lines of complie errors)? – con ko Mar 03 '20 at 07:03
  • @JohnDing: "*But my problem is why it's measure to deal with those code which is "obvious wrong" is to make the program ill-formed*" You're not listening to me. All forms of this are ill-formed, whether they are "obviously wrong" or not. The NDR is there because detecting this circumstance in all cases is impossible. It's ill-formed so that compilers have the freedom to detect it in perhaps a few, easily detectable, cases and give an error. If it wasn't ill-formed, compilers would not be permitted to give an error. – Nicol Bolas Mar 03 '20 at 14:23
  • @NicolBolas Now I understood that, thanks for your patience. :) – con ko Mar 03 '20 at 14:38