Allow record fields and union alternatives to be types#91
Merged
Gabriella439 merged 1 commit intomasterfrom Feb 17, 2018
Merged
Allow record fields and union alternatives to be types#91Gabriella439 merged 1 commit intomasterfrom
Gabriella439 merged 1 commit intomasterfrom
Conversation
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.
Contributor
|
I don’t quite understand the last remark. Why would accessing field order make it possible for types to depend on values? |
Contributor
Author
|
@Profpatsch: A dependent record with ordered fields would allow things like: |
Contributor
|
Ah, as in |
Gabriella439
added a commit
to dhall-lang/dhall-haskell
that referenced
this pull request
Feb 17, 2018
... as standardized in dhall-lang/dhall-lang#91
Gabriella439
added a commit
to dhall-lang/dhall-haskell
that referenced
this pull request
Feb 18, 2018
... as standardized in dhall-lang/dhall-lang#91
Merged
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
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
mergeexpression: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:
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.