Lack of context-dependent types

[TomasMikula]

This post is partly a scream for help (as I am drowning in boilerplate) and partly a language feature proposal that would fix the situation.

---

The basic problem

... is that to define a type that mentions a type member of a Context module, one has to place such definition within another class type. Given

trait Context {
  type Foo
}

a type definition like

type Bar = Option[Foo]

has to be placed inside a scope where Context is available, such as

class Module(using val c: Context) {
  type Bar = Option[c.Foo]
}

It is then hard to convince the compiler that, given

val c: Context
val m: Module = Module(using c)

the types c.Foo and m.c.Foo are the same type:

implicitly[c.Foo =:= m.c.Foo]
// Cannot prove that c.Foo =:= m.c.Foo.

The consequences for the ergonomics of module-style modularity are huge, as will be demonstrated below.

Proposed solution

Introduce context-dependent types, i.e. types that depend on some contextual value. I will be using the following hypothetical syntax in the rest of this post:

// This is not valid Scala, but the idea is that the type `Foo` depends on a value of type `Context`.
// The key point is that we did not have to place this definition inside a class type.
type Foo(using c: Context)[A, B] = c.Bar[A, c.Baz[B]]

// Usage
def go(using Context): Foo[Int, String] = // the type Foo is dependent on the contextual value of type `Context`,
  ???                                     // but does not have to mention that value explicitly

Such context-dependent types are a missing counterpart to context-dependent methods/functions:

trait Context {
  type Foo[A]
  def doStuff(x: Int): Unit
}

object Context {
  // lets us access the `c.doStuff` method without mentioning `c` explicitly
  def doStuff(using c: Context)(x: Int): Unit =
    c.doStuff(x)

  // desirable to also have this: access the `c.Foo` type without explicitly mentioning `c`
  type Foo(using c: Context)[A] = c.Foo[A]
}

import Context.{doStuff, Foo}

def go(using Context): Unit = {
  doStuff(42) // works in Scala
  id[Foo[Int]] // works in this proposal
}

Consequences

TL;DR

How it should be	Reality
def dequeueNel[A](using Dsl)( as: NonEmptyList[A], ): A <*> Queue[A] = snd(Queues.fromList[A]) { uncons(as) }	def dequeueNel[A](using dsl : Dsl, lists : Lists[dsl.type], nels : NonEmptyLists[dsl.type, lists.type], queues : Queues[dsl.type, lists.type], )( as: nels.NonEmptyList[A], ): dsl.<*>[A, queues.Queue[A]] = { import dsl.snd import nels.uncons snd(queues.fromList[A]) { uncons(as) } }

The current situation

It takes a bit of a build-up to demonstrate the paralyzing amount of boilerplate one has to write (and read!), so please, bear with me.

DSL

Let's have a little DSL

trait Dsl {
  infix type <*>[A, B] // analogous to (A, B)
  infix type <+>[A, B] // analogous to Either[A, B]
  type One             // analogous to Unit
  type Rec[F[_]]       // type-level fixed point
  
  /** Lifts the function into a function on the second element of a pair. */
  def snd[A, B, C](f: B => C): (A <*> B) => (A <*> C)
  
  // ... more methods
}

It is an abstract trait, since we will want to have multiple implementations of it.

We will be building modules and applications on top of this DSL, regardless of concrete implementations of the DSL.

Lists module

Here is a module defining a List data structure on top of the DSL:

trait Lists[DSL <: Dsl] {
  val dsl: DSL
  
  import dsl.{<*>, <+>, One, Rec}
  
  opaque type List[A] = 
    Rec[[X] =>> One <+> (A <*> X)]
  
  // ... methods to work with Lists
}

Notice the DSL <: Dsl type parameter. This will help convince the compiler that given

val dsl: Dsl
val lists: Lists[dsl.type]

the types dsl.One and lists.dsl.One are the same type, etc.

NonEmptyLists module

Here is another module, defining non-empty lists on top of the DSL and the Lists module:

trait NonEmptyLists[DSL <: Dsl, LISTS <: Lists[DSL]] {
  val dsl   : DSL
  val lists : LISTS & Lists[dsl.type]
  
  import dsl.<*>
  import lists.List
  
  opaque type NonEmptyList[A] =
    A <*> List[A]
  
  def uncons[A](as: NonEmptyList[A]): A <*> List[A]
}

Notice there are now two type parameters, DSL <: Dsl, LISTS <: Lists[DSL]. This will help convince the compiler that given

val dsl: Dsl
val lists: Lists[dsl.type]
val nels: NonEmptyLists[dsl.type, lists.type]

the types lists.List[A] and nels.lists.Lists[A] are the same type, as well as dsl.One, lists.dsl.One, nels.dsl.One, nels.lists.dsl.One are all the same type.

Queues module

Here's another module, Queues, defined again on top of the DSL and the Lists module.

trait Queues[DSL <: Dsl, LISTS <: Lists[DSL]] {
  val dsl   : DSL
  val lists : LISTS & Lists[dsl.type]
  
  import dsl.<*>
  import lists.List
  
  opaque type Queue[A] =
    List[A] <*> List[A] // list of incoming and list of outgoing elems
  
  def fromList[A](as: List[A]): Queue[A]
}

Method using all the modules

Now let's implement a method that needs all the modules:

/** Dequeues the first element from the given non-empty list
  * and returns the rest as a queue. 
  */
def dequeueNel[A](using 
  dsl    : Dsl,
  lists  : Lists[dsl.type],
  nels   : NonEmptyLists[dsl.type, lists.type],
  queues : Queues[dsl.type, lists.type],
)(
  as: nels.NonEmptyList[A],
): dsl.<*>[A, queues.Queue[A]] = {
  import dsl.snd
  import nels.uncons
  
  snd(queues.fromList[A]) {
    uncons(as)
  }
}

Wow, that is quite some bureaucracy! There ought to be a better way.

The complete typechecked version of these snippets is at https://scastie.scala-lang.org/G1rGxw83Qz2gl6yrDO97AA
Does anyone have a less boilerplatey solution to express this example?

How it could be

Now I will present how things could go if we had context-dependent types, as defined above.

DSL

The DSL trait remains the same

trait Dsl {
  infix type <*>[A, B] // analogous to (A, B)
  infix type <+>[A, B] // analogous to Either[A, B]
  type One // analogous to Unit
  type Rec[F[_]] // type-level fixed point
  
  /** Lifts the function into a function on the second element of a pair. */
  def snd[A, B, C](f: B => C): (A <*> B) => (A <*> C)
  
  // ... more methods
}

but we also add context-dependent types and functions to its companion object:

object Dsl {
  type <*>(using dsl: Dsl)[A, B] = dsl.<*>[A, B]
  type <+>(using dsl: Dsl)[A, B] = dsl.<+>[A, B]
  type One(using dsl: Dsl)       = dsl.One
  type Rec(using dsl: Dsl)[F[_]] = dsl.Rec[F]
  
  def snd[A, B, C](using dsl: Dsl)(f: B => C): (A <*> B) => (A <*> C) =
    dsl.snd(f)
}

Lists

import Dsl.{<*>, <+>, One, Rec} // imports can now be at the top level

object Lists {
  opaque type List(using Dsl)[A] =
    Rec[[X] =>> One <+> (A <*> X)] // Rec, One, <+>, <*> are dependent on the Dsl instance in scope
  
  // ... methods to work with Lists
}

Here is the key point that leads to great simplification: we didn't need to put the List type inside a trait as before. That will save us from having to track the equality of the class instances, which was the main cause of complexity.

NonEmptyLists

import Dsl.<*>
import Lists.List

object NonEmptyLists {
  opaque type NonEmptyList(using Dsl)[A] =
    A <*> List[A]
  
  def uncons[A](using Dsl)(as: NonEmptyList[A]): A <*> List[A]
}

Queues

import Dsl.<*>
import Lists.List

object Queues {
  opaque type Queue(using Dsl)[A] =
    List[A] <*> List[A] // list of incoming and list of outgoing elems
  
  def fromList[A](using Dsl)(as: List[A]): Queue[A]
}

Using all the modules

import Dsl.{<*>, snd}
import NonEmptyLists.{NonEmptyList, uncons}
import Queues.Queue

/** Dequeues the first element from the given non-empty list
  * and returns the rest as a queue. 
  */
def dequeueNel[A](using Dsl)(
  as: NonEmptyList[A],
): A <*> Queue[A] =
  snd(Queues.fromList[A]) {
    uncons(as)
  }

So much cleaner!

[smarter]

Now that the SIP process has been rebooted (https://www.scala-lang.org/blog/2022/07/13/scala-improvement-process-reloaded.html), you might want to open a thread on contributors to discuss this as a pre-SIP for increased visibility: https://contributors.scala-lang.org/c/sip/13
The motivation section is good, but I would recommend spending more time detailing the semantics of your language extension.

I'm also wondering if it would make sense to have non-contextual parameters, e.g.:

  opaque type List(dsl: Dsl)[A] =
    dsl.Rec[[X] =>> dsl.<+>(One, (dsl.<*>(A, X))

This could be generalized to allow "extension types" which looks a lot more intuitive to me:

extension (dsl: Dsl)
  opaque type List[A] =
    dsl.Rec[[X] =>> dsl.<+>(One, (dsl.<*>(A, X))

This would avoid the boilerplate for tracking equality, but not the prefix-related boilerplate that can only be mitigated with imports.

[TomasMikula]

I'm also wondering if it would make sense to have non-contextual parameters

Absolutely.

This could be generalized to allow "extension types"

That would be nice to have. However, that would not give us the ability to import dsl.List, as List is not a member of Dsl, so we would always have to refer to it as dsl.List.

[LPTK]

Interestingly type projections in Scala 2 could be used to achieve reasonable ergonomics in such cases.

Here is an example of something you could write:

  def test[D <: Dsl, A](xs: D#STAR[A, Lists.List[D, A]])(using DslImpl[D]): Lists.List[D, A] =
    dsl._2(xs)

You lose the neat infix type syntax, but at least you don't have to introduce extremely verbose module hierarchies and the corresponding argument lists, unlike in your motivating example code.

And here is the valid Scala 2 code demonstrating how to achieve it:

trait Dsl {
  type STAR[A, B] // analogous to (A, B)
  type PLUS[A, B] // analogous to Either[A, B]
  type One             // analogous to Unit
  type Rec[F[_]]       // type-level fixed point
}
trait DslImpl[D <: Dsl] {
  def _2[A, B]: (D#STAR[A, B]) => B
  def snd[A, B, C](f: B => C): (D#STAR[A, B]) => (D#STAR[A, C])
  // ... more methods
}

class Example extends Dsl {
  type STAR[A, B] = (A, B)
  type PLUS[A, B] = Either[A, B]
  type One = Unit
  class Rec[F[_]](unrec: F[Rec[F]])
}
object ExampleImpl extends DslImpl[Example] {
  def _2[A, B] = _._2
  def snd[A, B, C](f: B => C): (Example#STAR[A, B]) => (Example#STAR[A, C]) =
    x => (x._1, f(x._2))
}

object Lists {
  type List[D <: Dsl, A] =
    D#Rec[({type F[X] = D#PLUS[D#One, D#STAR[A,X]]})#F] // Rec, One, <+>, <*> are dependent on the Dsl instance D
  
  // ... methods to work with Lists
  
  def test[D <: Dsl](implicit dsl: DslImpl[D]): (D#STAR[Int, String]) => (D#STAR[Int, Boolean]) =
    dsl.snd(_.length > 1)
}

object Main {
  
  def test[D <: Dsl, A](xs: D#STAR[A, Lists.List[D, A]])(implicit dsl: DslImpl[D]): Lists.List[D, A] =
    dsl._2(xs)
  
}

Unfortunately type projections were summarily removed from Scala 3 because Scala 2 was wrong about them in a corner case no one actually cares about (related to lower bounds). The thing is we've know how to make type projection sound for a while now: lampepfl/dotty-feature-requests#14 (comment)

[LPTK]

Note: there was a proposal a few years ago to add type synonyms of the form type T[x.type] = ... x.Member ... where x is a value parameter to the type synonym. This could be a good alternative way to achieve a similar thing to what I showed above. It's just unfortunate that we already had a working feature for this, and it was removed.

[TomasMikula]

Was the proposal discussed somewhere public? Do you have a link? It could serve as an intermediate step in the translation, meaning that

type List(using dsl: Dsl)[A] = ...

would be represented as

type List[(dsl: Dsl).type, A] = ...

(which is simpler because there is a single parameters list).

[LPTK]

Unfortunately it's buried somewhere in GitHub issue discussions. This was from a few years ago and I wouldn't know how to look for it easily. The issue is probably still open somewhere, or maybe in https://github.com/lampepfl/dotty-feature-requests/.

@smarter any ideas?

[smarter]

No sorry, that doesn't ring a bell.