Why no recursive type aliases?

Language Design
1

We can currently define a JSON AST like this:

class Json(
  val value: Double | String | Boolean | Null | Map[String, Json] | Seq[Json]
)

But we cannot do this:

type Json = Double | String | Boolean | Null | Map[String, Json] | Seq[Json]

But why not? The latter would be a more efficient implementation since it avoids one level of boxing. And more importantly: these kinds of types can be used to provide a more type-safe Scala façade for libraries from other ecosystems. For example, Avro4s currently uses Any as the return type for its Encoder type. It would be much nicer to define the return type as a union type as specificed in the Java Avro API

type AvroValue =
  GenericRecord |
  GenericEnumSymbol |
  Collection[AvroValue] |
  Map[String, AvroValue] |
  GenericFixed |
  CharSequence |
  ByteBuffer |
  Integer |
  Long |
  Float |
  Double |
  Boolean

Alas, it currency not possible. Projects like Avro4s therefore need to work around this with types like Any, or specify their own ADT and transform back and forth, degrading performance.

Maybe it’s possible to allow recursive type aliases in some restricted form that is easy to handle for the compiler? For example, we could allow cycles only within a single type definition, i. e. no mutually recursive type aliases.

2

there is some previous discussion at Unintuitive meaning of some recursive type aliases

1 Like
3

Yes, I saw that thread, thank you for pointing it out. To me it largely seemed to revolve around strange compiler behaviours/bugs and even stranger encodings of recursive type aliases.

But it doesn’t answer my real question, which is: recursive type aliases seem useful (for the reasons mentioned above, i. e. efficiency and, more importantly, interoperability), and every recursive type definition can be trivially rewritten as a class type, indicating that there’s no fundamental type-theoretical problem with them. So why aren’t they supported? And should we perhaps support them?

4

Recursive type aliases are not trivial at all. Essentially there are two variants: equi-recursive and iso-recursive. The PL community agrees that iso-recursive is unproblematic. Iso-recursive is essentially what we do with explicit wrappers. Equi-recursive is very tricky in isolation and even more so when it deals with subtyping. To start with some references: There’s a chapter in TAPL and a paper by Cardelli on subtyping recursive types.

2 Likes
5

Thank you Martin. I looked this up and apparently the difference between iso-recursive and equi-recursive types is that values of the former need to be explicitly introduced and eliminated with explicit operations (conventionally called roll and unroll), whereas these explicit operations are not needed for equi-recursive types.
IOW, iso-recursive types are essentially what you can achieve with classes with a single field like the above class Json, the problem of course being the run-time representation. We already have two attempts at solving that problem: opaque type and the old extends AnyVal. Maybe the solution would be a new form of opaque type that behaves more like class?

opaque type Json(
  value: Double | String | Boolean | Null | Map[String, Json] | Seq[Json]
)

The idea being that it works essentially like a class in that you have to wrap and unwrap the value, and like an opaque type in that it guarantees an unboxed representation, along with the associated issues (i. e. no override def toString). Or we could bring back the old extends AnyVal syntax with this new meaning.

2 Likes
6

This is specially important for tuples as they cannot be recursive, not even named tuples, in typescript this is not an issue as structural types can be recursive

2 Likes