4

Does a programming language team have any tool to validate their new ideas about new code syntax?

As an example, let's assume the Java language team starts developing new feature, which requires new syntax. This feature is supposedly new public keyword, that is allowed to point which classes will see this class. One developer proposes an syntax:

//means that Class3 will be only visible to Class1 and Class2
public(Class1, Class2) Class3 

Now, how the developers will be absolutely sure, that this new syntax public(arg1, arg2) does not break someone's method named public with parameters?

The tool should recognize that public is a reserved word, meaning there can't be such a method, as an example validation.

3
  • 2
    Compilers can be written that automatically decide whether a program is well-formed or not. Why do you think that analyzers can't be written that check whether a new syntax could overlap with existing syntax? Dec 1, 2017 at 15:21
  • @KilianFoth I think that the OP is asking how does the language team choose the name of a new feature such that it doesn't conflict with existing source code. If so, then the answer is of course that they can't.
    – Peter M
    Dec 1, 2017 at 15:32
  • @KilianFoth: Because, as amon explained in his answer, this has been proven to be impossible? Dec 3, 2017 at 20:52

1 Answer 1

10

Formalized, your question is: given a grammar G that parses a language L(G) and an extended grammar G' that parses an extended language L(G') where L(G) is a subset of L(G'), how can it be shown that any program in the language L(G) produces the same parse tree with the grammar G and G'?

This is the language inclusion problem and is undecidable for context free grammars. It is also undecidable whether a CFG is ambiguous, e.g. whether the same program could be parsed in two different ways under the G' grammar.

However, these problems may be decidable for the CFG subsets actually used by most programming languages, such as LALR. It may also be decidable if the difference between G and G' has a specific structure. Unfortunately I'm not familiar with the necessary theory.

Instead, there are two practical ways two check the compatibility of such syntax changes.

First, there might be a corpus of existing programs including lots of edge cases. Using a grammar-driven parser that can parse all CFGs (such as GLR or Earley parsers), these parsers can report whether the programs in that corpus had an ambiguous parse.

The more common approach is to ask other people whether they can spot any problems.

In this particular case there is a clear argument that such syntax would not be ambiguous. (public is a keyword, ergo there can be no method or constructor called public(). Introducing such syntax would therefore not introduce ambiguities.) A tool may or may not be able to make that connection. An experienced human certainly us.

Of course syntactic compatibility is the easy problem. Much more difficult is retaining compatible semantics, which is a much harder problem even for humans and definitively can't be checked automatically by tools. For starters, most programming languages don't even have any formal semantics that could be the subject of a proof. Again, asking many experienced humans is the only viable approach. If a problem is overlooked (happens quite often), then that's a bug that needs to be addressed afterwards.

2
  • I remember the C♯ design team stating in an interview ~10 years ago that they mathematically / logically formalized C♯ 2.0's and (what would become) C♯ 3.0's (i.e. C♯ 2.0 + LINQ) syntax and modeled the statement "Adding LINQ TO C♯ 2.0's syntax does not alter the parse of legal programs" as well as "C♯ 3.0's syntax is unambigous" as logical theorems suitable for feeding into the Boogie verifier / Z3 SMT Solver, and had the SMT Solver prove the theorem, thus arriving at a machine-proven statement that C♯ 3.0 is unambiguous and a strict syntactic superset of C♯ 2.0. Dec 3, 2017 at 20:48
  • IOW: they machine-proved that C♯ 3.0 is backwards-compatible and unambiguous syntactically. That is an extreme case, though, most language designers use their tremendous experience and lots of peer review. Dec 3, 2017 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.