google-research / google-research/dex-lang

allow unreduced applications in types

Open
#710 0 comments 2 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
1.7k
Forks
116
PR merge metrics
No merged PRs in 30d

Description

Dex allows for computing a type from a value:
```
data T =
T1
T2
...

def f (t:T) : Type = ...
```

However, the usefulness of this ability is diminished due to the fact that the compiler cannot work with variables whose type depends on an application of `f`:
```
def g : f T1 = ...
```
Here, `f T1` trivially reduces to some type, yet `g` does not type-check:
```
Type error:Can't reduce type expression: (f T1)
```
(as of dex commit ad4e996a29552d2dc421a8c0bbc456ec35dee7b1)

In many real cases, trivial reduction as above is not even possible:
```
def g' (t:T) : f t = ...
```
or
```
def g'' (t:T) (x:f t) : () = ...
```
The usefulness of this ability is exemplified in #709. See also https://github.com/idris-lang/Idris2/blob/main/samples/fctypes.idr for a related test case in Idris.

Contributor guide

Open the contributing guide

Research direction

Start by examining the dependent-type examples in this issue and the related use case in #709. Compare them with Idris's samples/fctypes.idr to understand the intended behavior; done means variables and function arguments whose types contain unreduced applications of f are accepted without the reported reduction error.

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.