Should there be a function type?

[jonmeow]

This stems from discussion on Basic syntax #162:
https://github.com/carbon-language/carbon-lang/pull/162/files#r513840204

To summarize: should there be a function type, and if so, what form should it take? tituswinters highlights concerns about overload sets.

I think that key questions are:

• Do we want a function type that can point at a specific function signature? (if not, does that moot this discussion?)
• Do we want an introducer? If so, fn, fnty, or something else?
• Should the return type be required? That is, if -> return_type isn't present, is that a syntax error or does it indicate that an empty tuple is being returned?

[jsiek]

Given the concern with overload sets, a good next step would be to flesh out a proposal for overload sets, etc.

[github-actions]

We triage inactive PRs and issues in order to make it easier to find active work. If this issue should remain active or becomes active again, please comment or remove the inactive label. The long term label can also be added for issues which are expected to take time.
This issue is labeled inactive because the last activity was over 90 days ago.

[jonmeow]

I'm moving this to a question for leads because it's coming up a bit again on #912. Can we get a tentative decision on what function type syntax should look like?

In executable_semantics at present, supported syntax is both of fnty(arg_types) and fnty(arg_types)->ret_type.

Note #188 raises one complaint with a fnty returning a fnty:

fnty (Int) -> Int // OK
fnty (Int) -> fnty (Int) -> Int // repeated fnty
fnty (Int) -> (Int) -> Int // desired

Note we could do the "desired" syntax there with roughly:

fnty_base: "fnty" tuple "->" fnty_chain;
fnty_chain: expression | tuple "->" fnty_chain;

---

In Swift, function types look like(arg_types)->ret_type with no keyword:
https://docs.swift.org/swift-book/LanguageGuide/Functions.html#ID174

IIUC -> Void is required in Swift; the ret_type cannot be omitted.

I can think of a couple ways to get Swift behavior:

• tuple->expression is always a function type syntactically, not a -> operation.
• The operator -> on a tuple type creates a function type.
  • Note, this might confuse developers: var tuple: auto = (arg_types); var function: auto = tuple->return_type;

Note, both might confuse developers without an introducer. I'm not convinced I'd catch that var x: (Int, Int) = DoSomething() is getting a tuple, while var x: (Int, Int) -> Int = DoSomething() is getting a function when reading a large volume of code.

---

In Rust, function types look like fn (type, type) or fn (type, type)->ret_type:
https://doc.rust-lang.org/reference/types/function-pointer.html

I think we could do this because fn isn't used in expression syntax. It's only replacing fnty with fn under current syntax.

---

In Go, func behaves similarly to Rust.
https://golang.org/ref/spec#Function_types

[josh11b]

My preference would be to follow a similar approach to Rust: there are a few function-call interfaces that can be implemented for types, much like operator() in C++, see the Rust book. Rust does make non-closure function pointers a primitive type though. We might be able to avoid that: it seems to me that an overloaded function is well modeled by a type implementing several ClassCall traits, one per overload, as I brought up in Discord. We might need a function type to bootstrap, though.

[github-actions]

We triage inactive PRs and issues in order to make it easier to find active work. If this issue should remain active or becomes active again, please comment or remove the inactive label. The long term label can also be added for issues which are expected to take time.
This issue is labeled inactive because the last activity was over 90 days ago.

[zygoloid]

I would prefer that we do not have function types as first-class types, if we can avoid it. Rather, I would like to see if we can follow an approach like the one that @josh11b outlined:

• Define an interface for making a call on an object, eg Callable(...parameter types...).
• For an fn F(...), treat F as the name of an empty object of some new, unique type that implements Callable(like ...).
• For a parameterized fn F[...](...), the new unique type has an impl forall [...] typeof(F) as Callable(...).
• Special-case direct calls to functions for foundational / bootstrapping / efficiency reasons. The behavior should be the same as if the call were made through the Callable interface, however.

This seems like it would generalize nicely to lambdas (which would be new, unique types which are not necessarily empty) and callable user-defined class types. It would also mean that passing a plain function to an algorithm taking a callable would work the same as passing a function object or a lambda, and would monomorphize to making a direct call.

We'll still need to support function pointers in some way for efficient C++ interoperability. I think that function pointers would precisely correspond to DynPtr(Empty & Callable(...)), and I wonder if we could use that as our type-erased function pointer type in Carbon, and as the type that function pointers map into / from for interoperability purposes. We would need to add some special-casing to the representation of DynPtr so that such a type is represented exactly as a function pointer.

[chandlerc]

Beyond @zygoloid's comment, I'd like to add: as commented far above, it also seems good to flesh out function overloading first so that it can be fully incorporated into this story.

However, I don't think there is anything more to say on this question at this time. The answer is simply "no" -- the rationale is that we'd prefer instead to pursue a model that generalizes more smoothly with lambdas, callable class objects, and potentially overload sets. I think that's sufficient rationale for the "no" answer and a clear direction. How exactly the callable interface and all the machinery for DynPtr (for example getting pointer-sized and pointer-implemented object for the type erased cases where we can and where we desire interop) seems beyond the scope of what we can useful "answer" here, it's just a vague direction. But I think it is a really good vague direction that I'm very supportive of pursuing.

Given that I've not heard any concerns or counter arguments to the "no" as suggested here, lets call this decided for now. When we get to the callable design, that's when to fill in all of the needed details there.