Can a compiler uniquely infer a function call given its terms in order?
I've been working on a programming language for a short while whose syntax has started to clog up with a lot of functions/function-like expressions because I refused to add special operators to the language. I was thinking of ways to resolve this issue, and the thought came across my mind of whether a function call in a typed language with product types and function types is uniquely determined by the order of the terms.
As in, given, say, the terms a b c d e f g and their types, we can uniquely arrive at a(b, (c(d))(e(f, g))) and there is no other such function call with same list of terms in that order (no such a(b, c, d, e(f(g))) for example). Is this possible? Or are there counterexamples where some other list of terms and types here can lead to two different parses given different parsing strategies?
Posted Jul 6, 2019, 8:32 AM UTC
If you have polymorphism, it doesn't work. For example with
id : forall a . a -> a, the termid id idcan be parsed as either(id id) idorid (id id).Yeah, there's no implicit polymorphism in this language. That's actually one of the reasons why there was an explosion of function calls that caused me to look at no parentheses and possibly even no commas as a possible solution.
So that example would need to call
id Ato get the identity function onA.I'm currently working on a class of languages also without polymorphism. But I'm not sure if that's the best approach long term. Do you think you will relax that restriction, given the " explosion of function calls " you've seen?
This makes me wonder if it works as long as impredicativity is disallowed.