Skip to content

Allow record fields and union alternatives to be types#91

Merged
Gabriella439 merged 1 commit intomasterfrom
gabriel/types_as_fields
Feb 17, 2018
Merged

Allow record fields and union alternatives to be types#91
Gabriella439 merged 1 commit intomasterfrom
gabriel/types_as_fields

Conversation

@Gabriella439
Copy link
Copy Markdown
Contributor

The motivation behind this change is to add support for "modules" to
Dhall, which are just large records that users can import bundling both
terms and types.

Users can already import terms and types separately and users can already
bundle terms into a single import using a record, but before this change
they cannot bundle types in the same way. The reason why is that the
typing judgments for record types and record literals forbid records
with type-valued fields. This change removes that restrictions,
allowing records to store types and type-level functions for fields.

For consistency, this change also loosens the same restriction for union
alternatives.

For example, after this change the following becomes a valid Dhall record:

{ x = True, y = Bool, z = List } : { x : Bool, y : Type, z : Type  Type }

... and this is a valid merge expression:

merge
{ x = λ(a : Type)  a
, y = λ(f : Type  Type)  f Bool
}
< x = Bool | y : Type  Type >

The practical benefit of this change is to improve the usability and
speed of Dhall programs. This allows users to shorten their programs by
consolidate their import list into a single import, which in turn speeds
up program interpretation by reducing the number of HTTP requests.

This change preserves soundness, which consists of the following four
rules:

  • Type-checking should never diverge
  • If a term type-checks, then normalizing that term should never diverge
  • Normalizing an inferred type should never diverge
  • Normalization doesn't change a term's type

Here is the informal proof of the above soundness properties for the
modified typing judgements:

  • Type-checking should never diverge

    By induction, both newly added type-checking rules still recurse on a
    strictly smaller input expression so type-checking still always
    terminates.

  • If a term type-checks, then normalizing that term should never diverge

    By induction, each field or alternative is type-checked, which means that
    each field or alternative is safe to normalize, which in turn means that
    the record or union is safe to normalize.

  • Normalizing an inferred type should never diverge

    By induction, the inferred type of each field or alternative is safe
    to normalize, therefore the inferred type of the record or union is
    safe to normalize.

  • Normalization doesn't change a term's type

    By induction, if normalizing the type of each field or alternative
    doesn't change their type then normalizing the record or union
    doesn't change its type.

Note that the records are still not dependent records (i.e. the type of
a field cannot depend on the value of another field) since fields are
not ordered.

The motivation behind this change is to add support for "modules" to
Dhall, which are just large records that users can import bundling both
terms and types.

Users can already import terms and types separately and users can already
bundle terms into a single import using a record, but before this change
they cannot bundle types in the same way.  The reason why is that the
typing judgments for record types and record literals forbid records
with type-valued fields.  This change removes that restrictions,
allowing records to store types and type-level functions for fields.

For consistency, this change also loosens the same restriction for union
alternatives.

For example, after this change the following becomes a valid Dhall record:

```haskell
{ x = True, y = Bool, z = List } : { x : Bool, y : Type, z : Type → Type }
```

... and this is a valid `merge` expression:

```haskell
merge
{ x = λ(a : Type) → a
, y = λ(f : Type → Type) → f Bool
}
< x = Bool | y : Type → Type >
```

The practical benefit of this change is to improve the usability and
speed of Dhall programs.  This allows users to shorten their programs by
consolidate their import list into a single import, which in turn speeds
up program interpretation by reducing the number of HTTP requests.

This change preserves soundness, which consists of the following four
rules:

* Type-checking should never diverge
* If a term type-checks, then normalizing that term should never diverge
* Normalizing an inferred type should never diverge
* Normalization doesn't change a term's type

Here is the informal proof of the above soundness properties for the
modified typing judgements:

*   Type-checking should never diverge

    By induction, both newly added type-checking rules still recurse on a
    strictly smaller input expression so type-checking still always
    terminates.

*   If a term type-checks, then normalizing that term should never diverge

    By induction, each field or alternative is type-checked, which means that
    each field or alternative is safe to normalize, which in turn means that
    the record or union is safe to normalize.

*   Normalizing an inferred type should never diverge

    By induction, the inferred type of each field or alternative is safe
    to normalize, therefore the inferred type of the record or union is
    safe to normalize.

*   Normalization doesn't change a term's type

    By induction, if normalizing the type of each field or alternative
    doesn't change their type then normalizing the record or union
    doesn't change its type.

Note that the records are still not dependent records (i.e. the type of
a field cannot depend on the value of another field) since fields are
not ordered.
@Profpatsch
Copy link
Copy Markdown
Contributor

I don’t quite understand the last remark. Why would accessing field order make it possible for types to depend on values?

@Gabriella439
Copy link
Copy Markdown
Contributor Author

@Profpatsch: A dependent record with ordered fields would allow things like:

{ x : Type, y : List x }

@Profpatsch
Copy link
Copy Markdown
Contributor

Ah, as in rec in nix or letrec in Scheme, but without allowing self-reference.

@Gabriella439 Gabriella439 merged commit a082257 into master Feb 17, 2018
@Gabriella439 Gabriella439 deleted the gabriel/types_as_fields branch February 17, 2018 01:44
Gabriella439 added a commit to dhall-lang/dhall-haskell that referenced this pull request Feb 17, 2018
Gabriella439 added a commit to dhall-lang/dhall-haskell that referenced this pull request Feb 18, 2018
@ramirez7 ramirez7 mentioned this pull request Feb 27, 2018
mheiber added a commit to mheiber/dhall-lang that referenced this pull request Oct 26, 2020
*Note that the spec change in this PR is not yet implemented in
dhall-haskell.*

Before this change, conditional branching based on
types was allowed using `merge` but not for plain `if` expressions.

per @Gabriel439 this was "an unintentional inconsistency
in the language due to how it evolved, and the inconsistency can be fixed."

source: https://stackoverflow.com/a/64525640/2482570

and reference to merged PR allowing record and union alternatives
to be types: dhall-lang#91
mheiber added a commit to mheiber/dhall-lang that referenced this pull request Oct 29, 2020
*Note that the spec change in this PR is not yet implemented in
dhall-haskell.*

Before this change, conditional branching based on
types was allowed using `merge` but not for plain `if` expressions.

per @Gabriel439 this was "an unintentional inconsistency
in the language due to how it evolved, and the inconsistency can be fixed."

source: https://stackoverflow.com/a/64525640/2482570

and reference to merged PR allowing record and union alternatives
to be types: dhall-lang#91
mheiber added a commit that referenced this pull request Oct 29, 2020
## Description 

Before this change, conditional branching based on
types was not allowed for `if` expressions.

```dhall
-- Error: ❰if❱ branch is not a term 
let f= \(b : Bool) -> if b == True then Natural else Integer
in 3
```

But types-that-depend-on-booleans is allowed using a union with `merge`:

```dhall
let MyBool = <T | F>
let myIf: MyBool -> Type = \(b: MyBool) ->
        merge
          { T = Bool
          , F = Natural
          }
          b    
in 3
```

per @Gabriel439 this was "an unintentional inconsistency
in the language due to how it evolved, and the inconsistency can be fixed."

source: https://stackoverflow.com/a/64525640/2482570

related: merged PR allowing record and union alternatives
to be types: #91

## Use case

If  `MyBool` is more capable than built-in `Boolean` people might start defining their own booleans, which will make for some hard-to-follow code. (This might be pretty far-fetched scenario.)
TristanCacqueray pushed a commit to TristanCacqueray/dhall-lang that referenced this pull request Jan 4, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants