Why are types and grammar non-terminals so distinct?

Question

Sorry ahead of time if some of my terminology is inaccurate, my formal training isn't quite to the level it should be.

Almost all programming languages with types separate built-in functions a + b and user defined functions f(x) into different steps of the compiler. a + b is dictated by some grammar that says something like expr ::= expr + term, and is dealt with by the parser. The precedence/associativity of operations is also defined by the parser, and all user defined functions are dumped into a common bucket. f(x) is defined by a declaration that requires x to be some type, and the result to be a particular type - which is then commonly checked post-parse in static analysis.

Thinking about it, it seems as though f (assuming for example, f goes from int to bool) could be defined in a grammar similar to

bool ::= "true" | "false" | bool-expr
bool-expr ::= "f" "(" int ")"
int ::= int-constant | int-expr ...

But doing some searches, it seems as though computer science research around types and grammars are formal, but always distinct.

Sure, there are practical concerns. Grammars tend to be static, preventing user defined functions from being... user defined. Grammars tend to be hard to make correctly/unambiguously, and letting random users meddle is troublesome. Having huge grammars would be more troublesome than doing the same sort of work split off to a more limited type-checker.

But there's all sorts of research which is done regardless of practical concerns. I find it hard to believe that the two research areas wouldn't benefit from ideas from each other. And by treating types like non-terminals (or vice versa), it seems as though you get quite a few benefits not commonly available (function overloading by return type, extensible language using types rather than a separate meta-language, better integration of user defined operators).

Given my lack of training though, I'm guessing there's simply something I'm missing that breaks the correspondence or that it was researched and promptly discarded due to something obvious to others. So what am I missing?

---

Clarification for svick's comment

function overloading by return type:

Since statements/expressions would need to be integrated with types, statement would need to map to void or unit or some analogy - and expressions would be typed as above. For example, f(x:int) -> void and f(x:int) -> int, only one is viable as a statement. This requires function signatures to be processed before implementations (akin to C), but that is rather implied for all of the approach.

extensible language without meta-language:

By making types act like grammar non-terminals, it would allow the parser behavior to vary based on function declarations (and the various symbols in scope). Consider the above example where statements are required to be void. f(x) would not even parse without some declaration that both matches that input and results in void. The function/variable/type declarations of the language effectively become the meta-language. But that's what programmers do already...

better integration of user defined operators:

Previous extensible languages had approaches to user defined operators, requiring the user to define precedence (usually some numeric value, relative to the built-in operators), and associativity. Having user defined and built-in operators/functions "speak the same language" as it were should provide a more uniform interaction between the two.

But mostly, the benefits I would expect are more theoretical. Things that can be proven/used about grammars could be applied to type checking and vice versa if types and non-terminals had some correspondence.

Answer 1

About operators and syntax extensions

Dave Clark comment is correct: "types is about semantics, grammar non-terminals is about syntax." This said, you are perfectly right that the semantic and syntactic issues could, possibly should, be both in the hands of the programmer, or at least of the project designer. Indeed, that has actually been the case for various languages, including older ones from the early 1970s, when the concept of extensible languages was popular.

But first you should get your concepts rights. Though the addition may be seen as a built-in function, that is not what characterizes it in the context of your question. A built-in function is just a function that happens to be predefined in the standard environment of the language. For example sqrt (square-root) or abs (absolute value) may be builtin functions in a language, but they are still defined implicitly as function sqrt(r:real):real; .... and function abs(z:real):real; ...., though abs is often overloaded to work also with integer.

There could also be a built-in function plus, possibly overloaded, that would perform additions. But who would use it. We prefer to write it with the operator +.

There are built-in operators such as +, and one might want the programmer to be able to define new ones.

The use of operator has to do with the way we write things. It is a syntactic issue. Using them does not help you to do more, but it allows you to say it differently, if you think that makes things easier to write or read and understand, or simply makes them closer to standardized notations.

So you should see operators as nothing more than a special notation for calling some function, which may or may not be extended to new functions. Defining operators has nothing to do with typing. Whatever semantic problems it causes can be caused as well with the simple use of functions. But if it extends the syntax, it may create syntactic problems such as grammatical ambiguity.

Operators are often overloaded, like + that can be used for both integer and real, and possibly for boolean disjunction or set union. But functions can be overloaded as well. It is only a notational issue. And one constraint, for both functions and operators, is that you cannot overload them using twice the same type signature, but that is a semantic problem: finding which fuction is actually associated with what is written, functionally or with an operator.

Regarding extensions of a language, there are many ways to do it. One way is to allow overloading of existing operators with new function, having new type signatures. Some languages limit it at that.

Another possibility is to introduce new user defined operators, possibly written as a sequence of characters, such as >=, or **, or and, and then associate functions with them. This can be done without touching the grammar, by defining for example the associativity (left or right) and the precedence level of binary operators, or the position of the argument for unary ones. Analysing the actual structure of expression could be handled separately from the context-free parsing of the syntax, thus not be really a parser issue. but more associated with expressions evaluation.

A third possibility is to allow the introduction of new rules in the grammars, but that requires appropriate techniques to properly associate semantics to these rules, which can be very open, and thus quite complex to handle.

Note also that we tend to see operators as unary prefix and binary infix, but there are many other forms, such as postfix for factorial $n!$, or the absolute value notation (endfix?): $|x|$, and more.

A last point is that, though the grammatical structure shoud remain manageable, mostly for users to understand, the syntactic complexity is not a major issue for modern syntax analysis techniques. I seems that there is a tradition of trying to have very efficient parsers, but it is not clear that the performance bottleneck is still there (maybe for some programming environments). We can analyze quite efficiently ambiguous languages.

Ambiguity may be a problem, when too frequent. But frequent ambiguity can probably be detected statically, event though the problem is not decidable in general (I do not know whether there has been work in that direction). Then, ambiguity can be treated by the parser as a syntax error, requiring the programmer to write things differently.

Actually, it may well be that the syntax is not ambiguous, but the typing is. While a big expression is parsed correctly, the overloading of functions or operators can be such that there is ambiguity as to what code (function body) should actually be understood.

A very simple example is:

function f(x:S):T1; ....
function f(x:S):T2; ....
function g(z:T1):T; ....
function g(z:T2):T; ....
declare u:S, v:T .....
  .....
  v := g(f(u))

It is not possible to decide which pair of functions f and g is actually being called, because the typing of the expression is ambiguous.

A language such as Ada (at least in its first release) allows such ambiguity that is detected by the compiler. I would consider it a semantic ambiguity, though some people consider type checking as part of syntax. Whatever the case, is that any better or any worse than syntactic ambiguities that would be detected by the parser.

I avoided giving concrete examples (there are many) because my memory may fail me and I and not sure which language allows what. When I need to know, I look.

About types

You question is mixing a lot of (I think) unrelated issues. So It is taking me time to sort it out.

The existence of operators and their properties is not really related to typing, as I explain above.

I think I finally understand what you are trying to say with the example using bool as non-terminal.

However I fail to see how it relates to the use of operators, which comes first in your question. And I do not see what it is supposed to bring you in terms of programming power.

This said, there is something like it that is possible, associating types with non-terminal. It is actually a way to integrate type checking in the syntax, though I do not know that it has ever been used for programming languages. It is used for natural languages, and is called feature structures. For example it can be used to test number, gender or case agreement in natural language analysis, which is quite close to type agreement.

The idea is to associate parameters with non-terminal, which then become some kind of predicate. It can be seen as using an infinite number of CF rules, all derived from a finite set by instantiating the parameter to all possible values. But actually it is used by instantiating the parameters as needed with unification.

This is possible because CF grammars may be seen as a special type of Horn Clauses with binary predicates (the two arguments are the indices of the ends of the corresponding substring in the program text). Adding a type arguments to the grammar non-terminals is just adding a third argument to the corresponding Horn clauses.