Proposal to add Dependent Function Types to the Language


#1

Here’s a proposal to add dependent function types to Scala 3. A dependent function type such as

(x: A) => x.B

is the logical first-class version of a dependent method

def m(x: A): x.B

Here’s a link to the doc page.

Motivation

The main reason for adding dependent function types is more regularity. If methods can be dependent, why do you have to lift this into a class with an apply method if you want to do the same for functions? It’s clearer and more efficient if we can express the argument dependency directly in the function type.

Originally, Scala did not have dependent function types because we did not see a good way to map them into normal Scala types. Adding a fundamentally new type to your type system is a big decision which should not be taken lightly. The Dotty implementation uses a clever scheme, where a dependent function type is represented as a normal function type with a refinement. This avoids essentially all the added complexity on the type system side.

This proposal is open for discussion in the community and will be discussed in our next SIP meeting, where we’ll take all your feedback into account for the approval/dismissal of this feature.

Going Further

Once we have dependent function types, of course one would like to have polymorphic function types as well. There are some preliminary ideas about that floating around, but polymorphic function types should be a separate SIP, if they get to that stage.


Second batch of Scala 3 SIPs: additions to Scala's type system
#2

Apologies for maybe irrelevant question, but in context of method types <==> function types unification, are there any plans to define “overloaded functional types” ? In particular, even now it is possible to write

  type TOverloadedFunc = (Int => Int) with ((String, String) => String)
  trait OverloadedFunc extends (Int => Int) with ((String, String) => String)

But can we expect that something like ((Int, Int) => Int) with ((String, String) => String) become available and meaningful ?
By the way, right now it is possible to define that

  type TOverloadedFunc2 = ((Int, Int) => Int) with ((String, String) => String)

- and it compiles well, but I can’t find any way to instantiate it :slight_smile:

I’m totally aware of java runtime limitation, which makes this task not that straightforward, but perhaps it could be implemented at least in form of some “semi-structural” / inline types, which could be present only on compile type and used only in inline functions? (meaning that after inlining of that inline function body “overloaded function type” should be replaced by particular type where that overloaded methods was defined in some regular way)


#3

Probably you mean “or” instead of “and” (i.e. with) in your examples? With the Proposal to Add Union Types to the Language you will be able to write

(Int => Int) | ((String, String) => String)

#4

I did not get what you are referring to?


#5

I think what @ibaklan wants is that if you have overloaded methods, they could be seen as a single identifier with different potential function types. So you if you had

def func(i: Int): Int = ???
def func(a: String, b: String): String = ???

You could express that func is “either Int=>Int or (String, String)=>String,” i.e. if you pass it a single Int parameter you get the overload that returns Int, but if you pass it two String parameters it would call the overload that returns String. The set of potential paths should be expressible using a single type. The discussion was about what type that would be.


#6

If you manage to construct such a value, it should be of type (Int => Int) & ((String, String) => String). Indeed, you can either use it as an Int => Int or as a (String, String) => String, which by LSP means its type should be a subtype of both, which is exactly what & models.

However, it is not, in general, possible to automatically construct this magic thing which dynamically dispatch on the appropriate overload. With overloads that have a different number of formal parameters, you can do it, but not with same-number-but-different-types. For example, if you have

def func(x: Iterable[Int]): Int = ???
def func(x: Int => Boolean): Int = ???

its type could be (Iterable[Int] => Int) & ((Int => Boolean) => Int). You could call that with a Set[Int], and now at run-time you cannot know what overload needs to be called. Both are applicable.

In general, it is impossible to reproduce Scala’s compile-time overload resolution at run-time. I should know, it’s an important topic in the design of Scala.js.

So automatically constructing a combined function value of multiple overloads would be a lie. We must not do that.