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

1525
gasche•

If you have polymorphism, it doesn't work. For example with id : forall a . a -> a, the term id id id can be parsed as either (id id) id or id (id id).

18
hyperumOP•

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 A to get the identity function on A.

4
breck•

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?

1
stepstep•

This makes me wonder if it works as long as impredicativity is disallowed.

1
vanaur•

If there is not polymorphism, nor functions with variable arguments, even infinite, then what you propose to do is feasible to a lesser extent. I'm not able to do it myself, but it seems that context-free grammar parsing algorithms (the function call doesn't really have a context in itself), such as the Earley algorithm, could help you. Here is a paper that details in particular the parsing of mixfix expressions, and page 32 shows an example that looks very similar to what you want to achieve. However, such a function, in the paper, is not user-defined, it is indeed defined natively, but the algorithm is probably extensible to the addition of parsing rules, depending here on the type of functions.

11
hyperumOP•

The paper looks interesting, although the proof on the page after didn’t really seem like a proof. I’ll look into this lead later when I have time - thanks for the links!

2
panic•

I think Earley parsing or general mixfix parsing is overkill here. If you have a way to tell whether a function-typed term represents a function to be called or a function to be passed as an argument, you can create a parse tree like this:

set the current term to the first term in the list
follow these steps in a loop:
  if the current term is a function to be called:
    create a function call term, pushing it onto a stack of function call terms
  if the current term is something to be passed as an argument:
    append it to the argument list of the function call term at the top of the stack
  if the function call term at the top of the stack now has all of its arguments:
    set the current term to the top function call term, popping it off of the stack
  otherwise:
    set the current term to the next term in the list of terms; or if there are none left, exit the loop

After exiting the loop, you should be left with an empty stack and the current term set to the parsed function call. The parsed input ends exactly when the stack becomes empty—any functions left on the stack are still waiting for more arguments, and if the stack is empty when trying to access the top term's arguments, that means there were too many arguments passed.

6
svick•

I think the first question you have to ask yourself: would a human be able to figure out what that syntax means?

7
hyperumOP•

It is my opinion that it is fine. I mean, existing languages already use unary operators. I’ve seen it already used informally in mathematical papers and presentations, although never justified to be unambiguous. Adding parentheses makes expressions harder to read, not easier.

1
breck•

"Adding parentheses makes expressions harder to read, not easier."

I agree! Here's my class of languages that do away with parens, if you want some more examples to tinker with: http://treenotation.org/sandbox/build/.

Here's another one from 2003: https://srfi.schemers.org/srfi-49/srfi-49.html

2
swordglowsblue•

Adding parentheses makes expressions harder to read, not easier.

That really depends on the context. An overabundance of parentheses leads to losing clarity in the clutter, but a well placed pair of parentheses can make all the difference between an unreadable or ambiguous call and a perfectly clear, readable, unambiguous one.

2
stepstep•

Suppose the whole expression to parse is just f, and suppose f takes no arguments and returns a bool. Then I would expect that the expression can be parsed as either of the following:

  • f (which has type () -> bool)
  • f() (which has type bool)

However, I couldn't think of any counterexamples that don't involve nullary functions, given the information you've provided (explicit type applications, no variadic functions) and assuming partial application is not allowed. If the language doesn't support nullary functions (or if nullary applications are made explicit), I think it might be the case that the solution is always unique (if it exists).

5
hyperumOP•

Wait - assuming no partial application? Do you know of any ambiguities that follow from that? Because if functions are automatically curried, then application involving products is just repeated application which we are already dealing with. Aside from this - I also think it would be unique, but I just want to know for sure by means of some proof by contradiction or something.

3
stepstep•

Oh, I'm not sure if it works with partial application. I just assumed functions are not curried in this language since you gave this as one of your examples:

a(b, (c(d))(e(f, g)))

With currying, I would have expected this:

(a(b))((c(d))((e(f))(g)))

Or, if f(x, y, ...) is shorthand for f(x)(y)..., then I would have expected this:

a(b, c(d, e(f, g)))

​

Unrelated: Now that I think about it, equi-recursive types might pose a problem. Does the language have equi-recursive types?

​

Edit: I think I have the beginning of an informal proof that it works if functions are curried (all functions have exactly one argument), type application is explicit or non-existent, and types are non-recursive or iso-recursive (but not equi-recursive). So this applies, for example, to STLC and System F. Suppose we have a valid parse tree for some expression. Consider an arbitrary subtree of the form e1(e2(e3)). There's no way it could also parse as (e1(e2))(e3), because e2(e3) cannot possibly have the same type as e2 (due to lack of implicit type application and recursive types). This works the other way too: consider an arbitrary subtree of the form (e1(e2))(e3). There's no way it could also parse as e1(e2(e3)) because then the argument to e1 would have a different type. Now it just remains to show that all ambiguities ultimately involve at least one of these two situations.

5
hyperumOP•

To your note - no, I don’t think so. But that’s actually quite related as having recursive types of that kind actually induces ambiguity in a no-parentheses parse if currying is automatically applied to functions accepting tuples (this is from an EDIT in another one of my comments on this post).

1
stepstep•

Just as you posted this, I edited my post above with a sketch of a proof that it works under the right conditions. Let me know if that solves it.

2
ineffective_topos•

If your types are monomorphic, then it can be made unambiguous: Simply, f has a finite, fixed number of arrows: e.g. f: Int -> Int. So when parsing a structure, move back to front, keeping a stack of arguments passed over. When one of those is a function requiring arguments, give it the expected number of arguments. I.e. here we can translate everything into terms that take n elements from a stack and return one.

There's no type-directed way if the types can be declared as polymorphic: let f: forall a, a -> String, x: forall a, a -> a, y: Int. Then ((f x) y) and (f (x y)) both are well-typed with the same result type. If we have typeclasses (ala Haskell) or non-parametric operations (ala Java .toString), then we can extend this to a case where the results depend on the parse tree.

4
Felicia_Svilling•

If you have functions with a variable number of arguments this becomes impossible of course. I't might depend on the details of your type system, but in general I don't think this is possible. Concatenative languages does something like this, but I don't think they tend to have first class functions.

a: x -> x

b: y -> y

c: z -> z

a b c could be a(b)(c) or a(b(c))

1
hyperumOP•

Oh, no varargs in the language. But I don't think that example disproves it, right? For a(b)(c) to type check, if c: C and b: B then a: B -> (C -> A) for some A. But then for a(b(c)) to typecheck, B = C -> D and a: D -> A. But then there cannot ever a D for which B -> (C -> A) = D -> A.

Do you happen to know any research in this area?

EDIT: Upon closer analysis, they may be isomorphic via curry if D = B * C but that implies B = C -> (B * C) which is a weird recursive type and I don't even think it makes sense. They can also be isomorphic in another way if C = 1 but that is of no concern to me.

1
breck•

no varargs in the language.

Have you found this to be practical? I initially had this in my class of languages but in practice really needed variadics. Well actually, so far it seems like I need for the last arg to potentially be a list.

2
hyperumOP•

There are some things for which I’ve felt variadics (and, on occasion, implicit polymorphism) to be useful. I assume at some point, I should probably add a macro system to solve these issues. That would require parenthetical delimitation for sure, but that’s not too much of a concern.

2
Felicia_Svilling•

I gave you the types. All three values are generic identity functions. They take an argument of any type and then return it. x, y and z are type variables that can bind to any type.

Do you happen to know any research in this area?

Not this in specific.

1
hyperumOP•

Sorry, just misinterpreted your syntax. The language is not planned to have any implicit polymorphism/generics (the types must be fed in as arguments explicitly). Seems unfortunate - I'll try to see if there's a way to prove or disprove the uniqueness of a function call inference in a parse of this style directly.

1
Felicia_Svilling•

Wow. That seems very cumbersome.

1
[deleted]•

[deleted]

1