Skip to content

Finite Recursive Type Aliases

Making Finite Recursive Type Aliases Compilation Fast

This is the third post in a short series on finite recursive type aliases in Pony. The first post told the story of the eleven years it took to allow them. The second post laid out the algorithm that decides which recursive aliases are legal.

That algorithm is correct. Correct isn’t enough. Past a certain size, a tangle of type aliases that all refer to each other sent the compiler’s type checker into exponential work. Slow at first. Then, on a bigger tangle, eleven minutes of churning with no end in sight. The compiler wasn’t rejecting these programs — the algorithm accepts them. It just couldn’t finish checking them in any reasonable time.

Inside Pony’s Finite Recursive Type Aliases

This is the second post in a short series on finite recursive type aliases in Pony. The first post told the story of why this took eleven years. As I write this, the pull request that adds the feature is open and in review on ponyc. It hasn’t merged yet. Details may shift before it does, but everything in this post is foundational. It should all hold.

So how does the compiler tell a finite recursive type alias from an infinite one?

The algorithm is Tarjan’s strongly connected components. I’ll walk through it. Then I’ll show you the two checks I built on top of it.

Eleven years to a finite recursive type alias

There’s a pull request open against the Pony compiler. It’s in review right now. When it lands, and it will land soon, you’ll be able to write this:

use "collections"

type JsonValue is
  ( String
  | F64
  | Bool
  | None
  | Array[JsonValue]
  | Map[String, JsonValue])

Today the compiler rejects it. JsonValue mentions Array[JsonValue], which mentions JsonValue, and ponyc throws up its hands: type aliases can't be recursive. That has been true for the entire history of the language. It’s about to stop being true, and the pull request that changes it closes out the oldest open issue in the ponyc repository.