4 ms·

More generally this falls into a discussion of context-specific vs context-free grammars. Of which C++ falls into the former, Java falls into the latter.

MaxBarraclough 6y ago
The grammar of C++ is not a context-sensitive grammar. It's Turing-complete, on account of its template metaprogramming capabilities. I'd be very surprised if Java's grammar were context-free. Do you have a source for this? I wasn't able to find one with a quick search.
- battery_cowboy 6y ago
  It's Turing complete because it could simulate a Turing machine, not because of metaprogramming. The language brainfuck is Turing complete, for example.
  - saagarjha 6y ago
    Checking if a Brainfuck program is well formed (i.e. can be run) is a linear time operation. In C++ this can take forever. They have different complexities.
    - battery_cowboy 6y ago
      The original comment was about Turing completeness, and it was defined incorrectly. I was giving an example of a dead-simple language that was Turing complete, because the claim was that metaprogramming made C++ Turing complete.
      - tom_mellior 6y ago
        No, the claim was that metaprogramming made the grammar of C++ Turing complete.
        deleted 6y ago
        [deleted]
        battery_cowboy 6y ago
        Metaprogramming in C++ is TC, but it's not what makes C++ TC by itself.
        MaxBarraclough 6y ago
        You misunderstand. C++ is Turing-complete at compile time, due to template metaprogramming. This demonstrates that it isn't a context-free grammar. This isn't true of all programming languages.
        battery_cowboy 6y ago
        Thanks, i see what you were saying now, i misunderstood your original comment.
        tom_mellior 6y ago
        Yes, but it is the difference to other programming languages. In C you cannot encode a Turing machine that is executed by the compiler at compile time. In Brainfuck you cannot encode a Turing machine that is executed by the compiler at compile time. In C++ you can encode a Turing machine that is executed by the compiler at compile time. That is the difference we are discussing here.
        benibela 6y ago
        >In C you cannot encode a Turing machine that is executed by the compiler at compile time. But you can get quite close with macros
        tom_mellior 6y ago
        No. You would need the ability to write unbounded loops or unbounded recursion. You don't have that with the C preprocessor. Yes, you can do a lot with the C preprocessor. You can also do a lot in languages that only have bounded loops and are therefore not Turing complete. You can either express nonterminating computations (Turing completeness), or you can't (still powerful, but dramatically less poweful). This question is binary. There is no fuzziness, there is no approximation, there is no "quite close".
      - wtetzner 6y ago
        The claim wasn’t that C++ is Turing complete, that’s trivially true. The claim was that C++’s grammar is Turing complete. I don’t know if that’s exactly the right way to phrase it, but C++’s template expansion stuff is Turing complete.
        battery_cowboy 6y ago
        It was a weird phrasing to me, but i get what you were all saying now.
- tom_mellior 6y ago
  Pretty much every programming language has a nicely parseable context-free "rough syntax" (my term I just invented) that can be written down formally for the language documentation and a parsing tool. And then every language also has a notion of "well-formed programs", which introduces a whole bunch of additional constraints on what programs should actually be accepted by compiler frontend. Well-formedness includes type checking. But even without full type checking that can be done later, it also includes things like being aware, in C, of whether a given identifier is declared as a typedef in the current scope. So while C has a nice context-free "rough syntax" formally specified in the standard, its actual input language is context sensitive. As for Java, the first example that comes to mind is that constructors must have the same name as the class they belong to. This "choose whatever identifier you like, but at some later point repeat that exact same identifier" is a very typical example of something that is not context-free. You might disagree whether this constraint is part of what you consider Java's "grammar". So the answer to your question depends on what language level you are thinking of. But whichever level you apply to Java, you should apply the same to C++. C++ also has a context-free "rough syntax" in its standard.
battery_cowboy 6y ago
https://stackoverflow.com/questions/14589346/is-c-context-free-or-context-sensitive https://stackoverflow.com/questions/14589346/is-c-context-fr... Context free means something different to what you're saying here. This is a good discussion of this topic, I never knew C++ was so irregular and informal.

MaxBarraclough 6y ago

The grammar of C++ is not a context-sensitive grammar. It's Turing-complete, on account of its template metaprogramming capabilities. I'd be very surprised if Java's grammar were context-free. Do you have a source for this? I wasn't able to find one with a quick search.

battery_cowboy 6y ago
It's Turing complete because it could simulate a Turing machine, not because of metaprogramming. The language brainfuck is Turing complete, for example.
- saagarjha 6y ago
  Checking if a Brainfuck program is well formed (i.e. can be run) is a linear time operation. In C++ this can take forever. They have different complexities.
  - battery_cowboy 6y ago
    The original comment was about Turing completeness, and it was defined incorrectly. I was giving an example of a dead-simple language that was Turing complete, because the claim was that metaprogramming made C++ Turing complete.
    - tom_mellior 6y ago
      No, the claim was that metaprogramming made the grammar of C++ Turing complete.
      - deleted 6y ago
        [deleted]
      - battery_cowboy 6y ago
        Metaprogramming in C++ is TC, but it's not what makes C++ TC by itself.
        MaxBarraclough 6y ago
        You misunderstand. C++ is Turing-complete at compile time, due to template metaprogramming. This demonstrates that it isn't a context-free grammar. This isn't true of all programming languages.
        battery_cowboy 6y ago
        Thanks, i see what you were saying now, i misunderstood your original comment.
        tom_mellior 6y ago
        Yes, but it is the difference to other programming languages. In C you cannot encode a Turing machine that is executed by the compiler at compile time. In Brainfuck you cannot encode a Turing machine that is executed by the compiler at compile time. In C++ you can encode a Turing machine that is executed by the compiler at compile time. That is the difference we are discussing here.
        benibela 6y ago
        >In C you cannot encode a Turing machine that is executed by the compiler at compile time. But you can get quite close with macros
        tom_mellior 6y ago
        No. You would need the ability to write unbounded loops or unbounded recursion. You don't have that with the C preprocessor. Yes, you can do a lot with the C preprocessor. You can also do a lot in languages that only have bounded loops and are therefore not Turing complete. You can either express nonterminating computations (Turing completeness), or you can't (still powerful, but dramatically less poweful). This question is binary. There is no fuzziness, there is no approximation, there is no "quite close".
    - wtetzner 6y ago
      The claim wasn’t that C++ is Turing complete, that’s trivially true. The claim was that C++’s grammar is Turing complete. I don’t know if that’s exactly the right way to phrase it, but C++’s template expansion stuff is Turing complete.
      - battery_cowboy 6y ago
        It was a weird phrasing to me, but i get what you were all saying now.
tom_mellior 6y ago
Pretty much every programming language has a nicely parseable context-free "rough syntax" (my term I just invented) that can be written down formally for the language documentation and a parsing tool. And then every language also has a notion of "well-formed programs", which introduces a whole bunch of additional constraints on what programs should actually be accepted by compiler frontend. Well-formedness includes type checking. But even without full type checking that can be done later, it also includes things like being aware, in C, of whether a given identifier is declared as a typedef in the current scope. So while C has a nice context-free "rough syntax" formally specified in the standard, its actual input language is context sensitive. As for Java, the first example that comes to mind is that constructors must have the same name as the class they belong to. This "choose whatever identifier you like, but at some later point repeat that exact same identifier" is a very typical example of something that is not context-free. You might disagree whether this constraint is part of what you consider Java's "grammar". So the answer to your question depends on what language level you are thinking of. But whichever level you apply to Java, you should apply the same to C++. C++ also has a context-free "rough syntax" in its standard.

battery_cowboy 6y ago

https://stackoverflow.com/questions/14589346/is-c-context-free-or-context-sensitive https://stackoverflow.com/questions/14589346/is-c-context-fr... Context free means something different to what you're saying here. This is a good discussion of this topic, I never knew C++ was so irregular and informal.