google-research / google-research/dex-lang
Support inferred superclass instances
- Dominant language
- Haskell
- Stars
- 1.7k
- Forks
- 116
- PR merge metrics
- No merged PRs in 30d
Description
## Motivation
Haskell has fine-grained typeclass hierarchies. Consider:
```haskell
class Semigroup a where
(<>) :: a -> a -> a
class Semigroup m => Monoid m where
mempty :: m
-- Defining mappend is unnecessary, it copies from Semigroup.
mappend :: m -> m -> m
mappend = (<>)
```
I want to implement `Monoid` for `[a]`. To do so, I must provide two instances: one for `Monoid`, and one for all the superclasses (`Semigroup`).
```haskell
instance Semigroup [a] where
(<>) = (++)
instance Monoid [a] where
mempty = []
```
When implementing a typeclass with a long chain of superclasses, it may be nice to define all methods within the instance for the leaf typeclass — instead of writing one instance per typeclass in the chain.
## Design
In Dex, we could support inferred superclass instances. Consider the following typeclass hierarchy:
```haskell
-- Semigroup → Monoid → Group → Abelian
-- Other hierarchies: ... → SemiRing → Ring.
-- Defines "combine" operation.
-- Laws:
-- - Associativity: x <> (y <> z) = (x <> y) <> z
interface Semigroup a
(<>) : a -> a -> a
-- Defines unit operation.
-- Laws:
-- - Left identity: munit <> x == x
-- - Right identity: x <> munit == x
interface [Semigroup a] Monoid a
munit : a
-- Defines inverse operation.
-- Laws:
-- - x <> inverse x == munit
-- - inverse x <> x == munit
interface [Monoid a] Group a
invert : a -> a
-- Defines commutativity law.
-- Laws:
-- - x <> y == y <> x
interface [Group a] Abelian a
```
The proposed feature is: we can directly provide an instance for `Abelian Float` like so, inferring superclass instances:
```haskell
instance Abelian Float where
munit = 0.
(<>) = \x y. x + y
invert = \x. -x
```
An extension is to allow explicit declarations of superclass instances if desired, so they can be found in the source code:
```haskell
-- Tentative syntax: comma-separate explicit superclass instance declarations.
instance Semigroup Float, Monoid Float, Group Float, Abelian Float where
munit = 0.
(<>) = \x y. x + y
invert = \x. -x
```
## Alternatives considered
### Don't do it: favor clarity in source code
One downside of inferred superclass instances is that the superclass instances no longer appear in the source code. With `instance Abelian Float`: we cannot grep for `instance Semigroup Float` in the source code.
This concern seems mitigated with proper tooling support:
* In `dex web` and rendered HTML pages: hover tooltips on the instance declaration could show inferred superclass instance information.
* In IDEs: jump-to-definition on typeclass methods (from inferred superclass instances) should jump to the correct location. Everything can be traced back to source code (the explicit instance definition) so there are no gaps in coverage.
Contributor guide
Research direction
The issue names no files, tests, or entry points. Start by locating Dex's typeclass and instance elaboration or checking logic, then determine how superclass instances are represented. Done means an Abelian instance can provide inherited methods and the resulting superclass instances are handled correctly, with tests for the hierarchy shown in the issue.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100