Generics and overloading in Tide

Tide^[a] now has floats.

[a] See my previous article for an introduction.

In order to implement floats, I needed some sort of operator overloading. The cleanest way (to me) seemed to be something like typeclasses. That led to implementing generics, which required type inference.

So now Tide also has all of those.

In the past few months, I haven’t exactly been working on-and-off on Tide, but this last “sprint” brought up some important design decisions that have been quite tricky to navigate.

The original plan for generics

Originally, my idea was to keep the type system fully monomorphic at the core language level, and implement Ada-style generic modules.

// not real syntax
// in hash_map.td
module hash_map(
	// module parameters
	type K, V
	hash(T) int
)
// definitions omitted
pub type Hash is ...
pub insert(mut h Hash, key K, val V) { ... }
pub search(h Hash, key K) V { ... }

// in main.td
module main

import "os"
import "hash_map"(int, string, int_hash) as map_is
import "hash_map"(string, string, string_hash) as map_ss

int_hash(i int) int { ... }
string_hash(s string) int { ... }

pub main() {
	let mut english = map_is:Hash()
	map_is:insert(mut english, 10, "ten")
	map_is:insert(mut english, 20, "twenty")
	let mut german = map_ss:Hash()
	map_ss:insert(mut german, "ten", "zehn")
	map_ss:insert(mut german, "twenty", "zwanzig")
	os:println(map_ss:search(german, map_is:search(english, 10)))
}

The main benefit would be to hopefully make it easier to implement a simple “dumb” compiler. Also, because it’s not that convenient, it would discourage people from trying to abuse the system to do type-level computation^[a].

[a] I think type-level computation is not usually a good idea, at least for applications. If the program has a model encoded tightly in its types, modifying the program gets harder because you need to update the theorems at the same time. This can be useful if you are working with a well-specified problem, but most programs change their models of the world over time, as more features are added and the problem domain is better understood. You can’t practically encode everything in types, and trying to do too much with them causes pain if your model isn’t exactly up-to-date. This problem happens both with OOP-style world modeling and with functional-style type driven development.

However, this has a number of issues.

First, the syntax. The need to name imported modules is... uh... very explicit. I don’t think we need to be this explicit though. Also, note how the hashing functions are passed to the imported module syntactically before they are defined. This means we either have to provide forward declarations, or abandon the idea of single-pass compilation entirely. This already eliminates the benefit of a “simple compiler”.

Second, the implementation. The naive way to do this would be to recompile a generic module for each instatiation, but then any helper functions defined there that don’t depend on the type parameters would be instantiated along with the rest of the module, even though they don’t change at all. This means we’d get unnecessary bloat very easily, unless the compiler implemented a specific optimization for this. I don’t like requiring too many different optimizations.

Third, this would get in the way of iterators, operator overloading, and some of the other things I wanted to do. Those are all about making things more implicit, so this extra-explicit style would be mismatched with those.

So I decided not to use the Ada style.

But if the goal is for the calling syntax to be nice, we’d have to somehow infer the generic arguments, instead of writing them manually. This means we need type inference. But type inference is hard, isn’t it?

Type inference is surprisingly simple

It turns out type inference (at least the Hindley-Damas-Milner kind) is actually pretty simple. I followed a tutorial^[a] and got Algorithm J running in an afternoon. Then I had to restructure the whole compiler because my architecture didn’t fit nicely with it, but that won’t be a concern for my hypothetical future “dumb” compiler.

[a] Type Inference (part 1) by Akhil Indurti

More specifically, what I implemented was:

Basic type inference, using unification of type terms;
row types, for records and named function parameters;
row constraints, for field access syntax;
no let generalization, because I require generic functions to be annotated;
and monomorphization, because while most of my current prototype runtime is dynamically typed, there’s still a compile-time distinction between byte arrays and other arrays that the backend needed to be aware of. Also, I wanted to see how hard it was to implement (not very).

I also had to remove all instances of subtyping, which are really complicated to deal with in a HM-style type system. Fortunately, the language design didn’t really depend on subtyping for anything too interesting. It was there mostly to make up for the lack of explicit casts, which I just added.

This led to a full refactor of my compiler. Previously, typechecking was done in the backend, alongside codegen. But sometimes, type inference propagates type information backwards, and not all were inferred by the time the code generator ran. So I had to pull back the type inference into the frontend, during the parsing stage.

The compiler now has two passes: (Scan + Parse + Typecheck) → (Monomorphize + Codegen). I don’t think it’s possible to make a one-pass compiler for the language anymore, unless you have a fully dynamic runtime and don’t need to know the type of anything to generate code. You could still run the codegen stage one function at a time, though the current compiler does a whole file in one go.

After the type inference was implemented, generics were really simple to add.

When the backend compiles a variable reference, if that reference points to a generic function, it tries to find an existing specialization (aka “monomorphization”) for the specific types that were inferred by the frontend. If it can’t find one, it generates one on the spot, and stores it for later reuse.

Currently, generics look as follows:

// in map.td
pub type HashMap[K, V] is ...
pub insert[K, V](mut h HashMap[K, V], key K, val V) { ... }
pub search[K, V](h HashMap[K, V], key K) V { ... }

// in main.td
import "os"
import "map"

pub main() {
	let mut english = map:HashMap()
	map:insert(mut english, 10, "ten")
	map:insert(mut english, 20, "twenty")
	let mut german = map:HashMap()
	map:insert(mut german, "ten", "zehn")
	map:insert(mut german, "twenty", "zwanzig")
	os:println(map:search(german, map:search(english, 10)))
}

Now it’s much more like any other modern language. The syntax is kind of a hybrid of Go and Rust.

Of course, the example above would be even better with overloaded indexing operators, but those aren’t implemented yet.

On that note...

Overloading

Generally speaking, overloading and generics don’t play together very nicely. If you can overload a generic function, or have generic overloads, you can end up in situations where adding a new overload changes the behaviour of existing code:

// if Tide worked like C++
foo[T](x T) { ... }
bar() { foo("hello") }

// uncomment for a nasty surprise!
//foo(x string) { ... }

I don’t want this kind of spooky-action-at-a-distance in Tide.

Fortunately, there’s a little research language that has been doing a lot of experimentation in this problem space for the last thirty years: Haskell.

My previous experiences with Haskell were... interesting. After using it a whole lot of crazy GHC extensions for my undergraduate thesis, I came out of it thinking it’s really complicated.

But after reading the classic papers^[a]^[b], I got the impression that I had just misunderstood the whole thing. The experimental features in GHC are, well, experiments. Of course not all of them are stable. So I just need to find a reasonable, principled, well-behaved subset of those, from the pile of research papers I have open in my browser.

[a] Making ad-hoc polymorphism less ad-hoc, by Philip Wadler and Stephen Blott
[b] Type classes: an exploration of the design space, by Simon Peyton Jones, Mark Jones and Erik Meijer

So the current design looks like this:

// declare an overloadable name
overload from[T](x T) string

// these can be defined anywhere, as long as they are in scope when called
case from(a string) string { a }
case from(i int) string { __internal_from_int(i) }

// generics can use overloads only if the types implement them
print[T; from T](a T) { os:println(from(a)) }
// or use ... to let the compiler infer the type constraints
print[T; ...](a T) { os:println(from(a)) }

The idea is to give a single “shape” for an overloadable function, then restrict overload cases to that shape.

In other words, single-parameter, single-method type classes.

They only have a single method because that’s easier to explain than having multiple, like Haskell. If you need more than one, just define two separate methods and use them together.

We also don’t support Haskell-style subclassing for similar reasons.

You can also overload operators in the same way:

type Complex(real, imag float)

case +(a, b Complex) Complex { ... }
// sugar for:
case operator:plus(a, b Complex) Complex { ... }

The implementation on the backend is also really simple. When the backend encounters a variable reference, if that is referencing an overloaded function, it looks up the list of specializations for the specific type inferred by the frontend. If it finds one, it uses that. Otherwise, it’s an error.

The frontend required some more logic to do constraint inference, but it was fine.

I still haven’t implemented generic overloads, but it doesn’t seem too difficult either.

The problem at the start of this section is known in Haskell terminology as “overlapping instances”, and they have well-specified algorithms for detecting and disallowing it.

More parameters?

One problem with the above design is that it looks like you should be able to add more parameters to the type classes:

overload mul[T, U, V](T, U) V

case mul[Matrix, Vector, Matrix](m Matrix, v Vector) Matrix { ... }
case mul[Vector, Matrix, Matrix](v Vector, m Matrix) Matrix { ... }
case mul[Vector, Vector, Vector](a, b Vector) Vector { ... }

The syntax makes it look like you should be able to do that. It seems reasonable to allow it. But if you read the Haskell wiki^[a] on the subject, it immediately mentions that they can cause ambiguity, and mentions functional dependencies^[b] and type families^[c] as possible solutions, both features I really don’t want to deal with. On top of that, neither functional dependencies nor type families really solve the ambiguity problem completely.

[a] Multi-parameter type classes
[b] Functional dependencies
[c] GHC/Type families

I don’t think it’s particularly hard to implement these, but there’s no point if they won’t be usable in practice without a bunch of casts. Especially if I want to use them for arithmetic.

For now, I decided to keep them single-parameter, until and unless I actually need the feature.

YAGNI

For Tide, I’m trying to stick to YAGNI for the order of implementation. I only implement things once I actually need them (or they are trivial to implement en-passant).

I wanted overloads specifically so that I could have an overloadable “stringify” function, namely str:from. It took me two weeks of hacking and refactoring and reading papers to do that.

I could have solved this in many other ways: an introspection system, a source code generator, a special-purpose feature, asking a slop machine... I just chose the solution that I was planning to implement later anyway.

I now kinda want a way to automatically derive these kinds of functions, but I’m tired of hacking on the compiler, so I’ll leave it for when I’m tired of writing them by hand.

You can browse the current version of the compiler on SourceHut.