Is there any fundamental limitations that stops Scala from implementing pattern matching over functions?

Question

In languages like SML, Erlang and in buch of others we may define functions like this:

fun reverse [] = []
|   reverse x :: xs  = reverse xs @ [x];

I know we can write analog in Scala like this (and I know, there are many flaws in the code below):

def reverse[T](lst: List[T]): List[T] = lst match {
  case Nil     => Nil
  case x :: xs => reverse(xs) ++ List(x)
}

But I wonder, if we could write former code in Scala, perhaps with desugaring to the latter.

Is there any fundamental limitations for such syntax being implemented in the future (I mean, really fundamental -- e.g. the way type inference works in scala, or something else, except parser obviously)?

UPD
Here is a snippet of how it could look like:

type T
def reverse(Nil: List[T]) = Nil
def reverse(x :: xs: List[T]): List[T] = reverse(xs) ++ List(x)

Answer 1

It really depends on what you mean by fundamental.

If you are really asking "if there is a technical showstopper that would prevent to implement this feature", then I would say the answer is no. You are talking about desugaring, and you are on the right track here. All there is to do is to basically stitch several separates cases into one single function, and this can be done as a mere preprocessing step (this only requires syntactic knowledge, no need for semantic knowledge). But for this to even make sense, I would define a few rules:

• The function signature is mandatory (in Haskell by example, this would be optional, but it is always optional whether you are defining the function at once or in several parts). We could try to arrange to live without the signature and attempt to extract it from the different parts, but lack of type information would quickly come to byte us. A simpler argument is that if we are to try to infer an implicit signature, we might as well do it for all the methods. But the truth is that there are very good reasons to have explicit singatures in scala and I can't imagine to change that.
• All the parts must be defined within the same scope. To start with, they must be declared in the same file because each source file is compiled separately, and thus a simple preprocessor would not be enough to implement the feature. Second, we still end up with a single method in the end, so it's only natural to have all the parts in the same scope.
• Overloading is not possible for such methods (otherwise we would need to repeat the signature for each part just so the preprocessor knows which part belongs to which overload)
• Parts are added (stitched) to the generated match in the order they are declared

So here is how it could look like:

def reverse[T](lst: List[T]): List[T] // Exactly like an abstract def (provides the signature)
// .... some unrelated code here...
def reverse(Nil) = Nil
// .... another bit of unrelated code here...
def reverse(x :: xs ) = reverse(xs) ++ List(x)

Which could be trivially transformed into:

def reverse[T](list: List[T]): List[T] = lst match {
  case Nil     => Nil
  case x :: xs => reverse(xs) ++ List(x)
}
// .... some unrelated code here...
// .... another bit of unrelated code here...

It is easy to see that the above transformation is very mechanical and can be done by just manipulating a source AST (the AST produced by the slightly modified grammar that accepts this new constructs), and transforming it into the target AST (the AST produced by the standard scala grammar). Then we can compile the result as usual.

So there you go, with a few simple rules we are able to implement a preprocessor that does all the work to implement this new feature.

---

If by fundamental you are asking "is there anything that would make this feature out of place" then it can be argued that this does not feel very scala. But more to the point, it does not bring that much to the table. Scala author(s) actually tend toward making the language simpler (as in less built-in features, trying to move some built-in features into libraries) and adding a new syntax that is not really more readable goes against the goal of simplification.

Answer 2

In SML, your code snippet is literally just syntactic sugar (a "derived form" in the terminology of the language spec) for

val rec reverse = fn x =>
    case x of [] => []
            | x::xs  = reverse xs @ [x]

which is very close to the Scala code you show. So, no there is no "fundamental" reason that Scala couldn't provide the same kind of syntax. The main problem is Scala's need for more type annotations, which makes this shorthand syntax far less attractive in general, and probably not worth the while.

Note also that the specific syntax you suggest would not fly well, because there is no way to distinguish one case-by-case function definition from two overloaded functions syntactically. You probably would need some alternative syntax, similar to SML using "|".