Type parameters at uncommon locations

georg-w-mueller · October 20, 2022, 2:29pm

Ladies, Gentlemen, hello,

in scala.util.control.TailCalls.scala (see details below) there is something that looks to my untrained eyes like the introduction of generic type parameters within a match-expression .

github.com

scala/scala/blob/v2.13.10/src/library/scala/util/control/TailCalls.scala#L62

    
      
          final def map[B](f: A => B): TailRec[B] =
            flatMap(a => Call(() => Done(f(a))))
          
          
/** Continue the computation with `f` and merge the trampolining
            * of this computation with that of `f`. */
          final def flatMap[B](f: A => TailRec[B]): TailRec[B] =
            this match {
              case Done(a) => Call(() => f(a))
              case c @ Call(_) => Cont(c, f)
              // Take advantage of the monad associative law to optimize the size of the required stack
              case c: Cont[a1, b1] => Cont(c.a, (x: a1) => c.f(x) flatMap f)
            }
          
          
/** Returns either the next step of the tailcalling computation,
            * or the result if there are no more steps. */
          @annotation.tailrec final def resume: Either[() => TailRec[A], A] = this match {
            case Done(a) => Right(a)
            case Call(k) => Left(k)
            case Cont(a, f) => a match {
              case Done(v) => f(v).resume
              case Call(k) => Left(() => k().flatMap(f))

The specifiers a1 and b1 are neither mentioned at the enclosing level (which is TailRec[+A]) nor at the method (flatMap[B]) itself.

{Note: The expression c.f(x) becomes a TailRec[b1] and a1 is used as type for x.}

The case, so one can play with it, is extracted to:

My questions: What is the magic behind this ~local type-parameters~? Is this documented and what must the compiler infer about this type-parameters behind the scenes?

Addition: A similar code being 10 years old now tried to solve this without ~local type-parameters~ but solely the type Any for x instead, but that does not compile today (found: (x: Any) required A$1):

github.com

runarorama/Days2012/blob/master/Main.scala#L130

    
      
          
          
def pureState[S, A](a: A): State[S, A] =
            State(s => (a,s))
          
          
sealed trait Trampoline[+A] {
            def map[B](f: A => B): Trampoline[B] =
              flatMap(x => More(() => Done(f(x))))
            def flatMap[B](f: A => Trampoline[B]): Trampoline[B] =
              this match {
                case FlatMap(a, g) =>
                  FlatMap(a, (x: Any) => g(x) flatMap f)
                case x => FlatMap(() => x, f)
              }
            @tailrec final def resume: Either[() => Trampoline[A], A] =
              this match {
                case Done(v) => Right(v)
                case More(k) => Left(k)
                case FlatMap(a, f) => a() match {
                  case Done(v) => f(v).resume
                  case More(k) => Left(() => k() flatMap f)
                  case b FlatMap g => b().flatMap((x:Any) => g(x) flatMap f).resume

BalmungSan · October 20, 2022, 5:48pm

It is not matching but rather extracting them, it basically says that c is a Cont[a1, a2] for some types a1 & a2 that are not known. Is just like Foo[_] as a type means Foo[x] forSome { type x }, is “just” an existential type.

SethTisue · October 20, 2022, 8:49pm

relevant:
• SLS 8.2, Pattern Matching | Scala 2.13
• SLS 8.3, Pattern Matching | Scala 2.13

not sure if this is the absolute best SO question/answer in this area, but:

georg-w-mueller · October 22, 2022, 2:54pm

Thanks for your swift and kind reply!

I agree regarding the ‘extraction’. What I’ve learned in the meantime due to the documents referenced by @SetTissue: It’s not type-parameters but type-variables.

By the way: the original line from the Scala-library …

case c: Cont[a1, b1] => Cont(c.a, (x: a1) => c.f(x) flatMap f)

… can be rewritten without any losses to:

case c: Cont[?, ?] => Cont(c.a, x => c.f(x) flatMap f)    // 1

or even more concise:

case Cont(ca, cf) => Cont(ca, x => cf(x) flatMap f)    // 2

So we’re having two simpler alternatives where we either do not care (// 1.) or we do not mention the existence of types at all (// 2).

georg-w-mueller · October 22, 2022, 3:06pm

Thanks a lot, Seth, that was very helpful! What I dig up additionally in the meantime for that topic:
“Type level Programming in Scala - Matt Bovel”:

accompanying material:

charpov · October 26, 2022, 10:28pm

I reimplemented something like TailCalls, with the type variables, as an example for a book I wrote (using the original paper by Bjarnason as a starting point). I was pleasantly surprised when switching to Scala 3 that the types variables in the pattern were not needed anymore. If you haven’t, I suggest you try the same code with Scala 3.

georg-w-mueller · October 26, 2022, 11:23pm

Yep, it’s pretty neat without any types at all. The flip side (if there even is one): It’s almost impossible to port this kind of ‘super slick’ code to other statically typed languages. Even if you could express it in the target language, - without tooling in non-trivial cases one would seldomly draw the same conclusions about the involved types as the compiler does. Combine that with additional given and using for added complexity and even a rather experienced developer could get lost pretty quick trying to figure out what is going on.
As often: Pleasure and curse lay close together.

charpov · October 27, 2022, 9:12pm

The way I see it, type systems are getting better and inference is getting better. Some languages are ahead and others are catching up, but it’s all moving in the right direction.