google-research / google-research/dex-lang

Feature Question: Record Subtyping

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

Description

We have been playing around with using Dex record types for generic name-based contraction. The lens / zipper example is clear about how make this work.

It does immediately make me wonder though if you can do broadcasting / subtyping on records. In particular given two record index types it would be nice to write a function like this:

```haskell
def promote (tab: {...b} => out) : {a & ...b} => out =
for i : {a & ...b}.
tab.(down i)
```
I thought a bit about how to do it, but was completely stumped. I realize that you can do it by providing the lens explicitly, but that is less satisfying.

```haskell
-- Probably an easier way to do this...
def push (name: Iso a (b & c))
(tensor1: b => c => d ) : a => d =
for i : a.
index1 = getAt name i
index2 = popAt name i
tensor1.index1.index2

def ndim (name: Iso a (b & c))
(tensor: c => out) : (a => out) =
push name for i: b. tensor
```

I see that this does exist in http://hackage.haskell.org/package/generic-lens-2.0.0.0/docs/Data-Generics-Product-Subtype.html , but perhaps it requires some trickery.

Seems related to https://github.com/google-research/dex-lang/issues/258

Contributor guide

Open the contributing guide

Research direction

Start with the lens/zipper example described in the issue and review the related discussion in issue #258. Compare the requested record broadcasting and subtyping behavior with Data.Generics.Product.Subtype and determine whether Dex needs a language or type-system change. Done means reaching a clear feasibility decision and documenting the required scope.

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
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.