google-research / google-research/dex-lang

Allow bundling associated types in interfaces

Open
#460 5 comments 3 reactions 0 assignees View on GitHub
language / concrete syntax
Dominant language
Haskell
Stars
1.7k
Forks
116
PR merge metrics
No merged PRs in 30d

Description

It is often convenient to have type-to-type maps (e.g. given a mapping type such as the `HashDict` of #343, what is its key and value type), and we could easily implement those by putting types in interfaces. For example:
```
interface Map m
keyType : Type
valueType : Type
lookup : m -> keyType -> Maybe valueType
```

One challenge here is that `keyType` has no way of resolving which type class it should use, because `m` is not mentioned in the type. A potential solution would be to allow prefixing the definitions with `indexed` (or some other word, naming is hard...) which would append the type parameter as an explicit argument instead of trying to infer it:
```
-- for keyType : Type we would generate
def keyType [Map m] : Type =

-- for indexed keyType : Type we would generate
def keyType (m : Type) [Map m] : Type =
```

cc @danieldjohnson who had some ideas

Contributor guide

Open the contributing guide

Research direction

No implementation files or tests are named. Start by tracing interface definitions and type-class resolution in the compiler, then compare the proposed indexed and non-indexed generated definitions. Done means an agreed syntax and behavior for associated types, including the Map-style keyType and valueType example.

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
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.