Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Should the parameters be marked as erased in the types of constructors and projections? #4786

Closed
nad opened this issue Jun 28, 2020 · 16 comments · Fixed by #5366
Closed

Should the parameters be marked as erased in the types of constructors and projections? #4786

nad opened this issue Jun 28, 2020 · 16 comments · Fixed by #5366
Assignees
Labels
documented-in-changelog Issues already documented in the CHANGELOG erasure type: enhancement Issues and pull requests about possible improvements
Milestone

Comments

@nad
Copy link
Contributor

nad commented Jun 28, 2020

Parameters are currently not marked as erased in the types of constructors and projections. Perhaps they should be.

It is sometimes possible to create variants of the constructors and projections with erased type arguments:

private
 module Dummy where

  record Σ (A : Set) (B : A  Set) : Set where
    constructor _,_
    field
      proj₁ : A
      proj₂ : B proj₁

open Dummy public using (Σ) hiding (module Σ)

_,_ : {@0 A : Set} {@0 B : A  Set} (x : A)  B x  Σ A B
x , y = x Dummy., y

module Σ {@0 A : Set} {@0 B : A  Set} (p : Σ A B) where

  proj₁ : A
  proj₁ = let record { proj₁ = x } = p in x

  proj₂ : B proj₁
  proj₂ = let record { proj₂ = y } = p in y

However, these variants cannot be used as patterns/copatterns. Furthermore this trick does not work for record types with no-eta-equality unless pattern is also used.

I imagine that this change is straightforward for constructors. For projections there is a complication: some definition in the record module might use the parameters in a non-erased context. Perhaps we could fall back to the current behaviour if there is a non-trivial record module.

Currently one also has the option to explicitly mark the parameters as erased, but this seems to lead to a problem (#4784).

I guess that this change is not backwards compatible.

@nad nad added type: enhancement Issues and pull requests about possible improvements erasure labels Jun 28, 2020
@nad nad added this to the 2.6.2 milestone Jun 28, 2020
@andreasabel
Copy link
Member

When originally implementing erasure, I did not have the guts to make parameters erased. In particular, to not confront users with errors concerning erasure if they did not use erasure at all.
We might want to revisit the original decision now.

@Saizan
Copy link
Contributor

Saizan commented Jul 1, 2020

For projections there is a complication: some definition in the record module might use the parameters in a non-erased context. Perhaps we could fall back to the current behaviour if there is a non-trivial record module.

I don't see a conflict between making parameters erased for projections while leaving them non-erased for definitions in the record module.

@nad
Copy link
Contributor Author

nad commented Jul 1, 2020

The projections are defined in the record module, and the module's telescope is built using the parameters.

@nad
Copy link
Contributor Author

nad commented Apr 15, 2021

The projections are defined in the record module, and the module's telescope is built using the parameters.

Apparently you can build a record module in such a way that the parameters are not erased in the telescope, but when you open the module you get projections with erased parameters. With my attempted fix of this issue (16f1118) the following code is accepted:

record R (A : Set) : Set where
  field
    x : A

open R

_ : (@0 A : Set)  R A  A
_ = λ A  x {A = A}

_ : (@0 A : Set)  R A  A
_ = λ A  R.x {A = A}

However, the following code is rejected:

open module R′ (@0 A : Set) (r : R A) = R {A = A} r

I wonder if the code that generates composition operations for data and record types needs to be changed. @Saizan, can you take a look at this?

@nad nad modified the milestones: 2.6.3, 2.6.2 Apr 15, 2021
nad added a commit that referenced this issue Apr 16, 2021
Perhaps something should be done about the code that generates
composition operations.
nad added a commit that referenced this issue Apr 17, 2021
Perhaps something should be done about the code that generates
composition operations.
@nad
Copy link
Contributor Author

nad commented Apr 18, 2021

@wenkokke, do you discuss how parameters affect the types of constructors or projections in PLFA? If so this change might "break" the text. As an example, the statement that the constructor c of the data type D below is {A : Set} → D A is no longer correct after this change, because the type is {@0 A : Set} → D A.

data D (A : Set) : Set where
  c : D

@andreasabel
Copy link
Member

Put erasure under a flag. (--erasure / --no-erasure).

@nad
Copy link
Contributor Author

nad commented Apr 21, 2021

@wenkokke, if this change is only active when --erasure is on, then it should not affect PLFA, so you can ignore my question.

@nad
Copy link
Contributor Author

nad commented Apr 21, 2021

The option --erasure should be infective. I wonder if one can still set things up so that (for instance) Agda.Builtin.Sigma._,_ can have erased parameter arguments.

One idea is to generate such arguments, but only print @0 if --erased is active. I wonder if anything would break if this approach is taken. If the only erased things are constructor arguments, what can go wrong? You can't include a parameter in a pattern, so I guess there won't be any erased variables or definitions. Consider the following code:

data D (@0 A : Set) : Set where
  c : D A

Is it possible to observe the difference between c : {@0 A : Set} → D A and c : {A : Set} → D A without using @0? The following code is accepted in the former case, but not the latter, but this code uses @0:

f : (@0 A : Set)  D A
f A = c {A = A}

Is there a risk that a meta-variable is created in an erased context, and thus cannot be used in a non-erased context? This could perhaps be addressed by ensuring that meta-variables are never created in an erased context when --erased is not active, but I wonder if that would create any new problems.

@Saizan
Copy link
Contributor

Saizan commented Apr 22, 2021

@nad the code for the composition operations still gets the parameter telescope from the datatype, so it's fine. The CubicalPrims test also passes, which confirms the generated code runs as expected.

@nad
Copy link
Contributor Author

nad commented Apr 22, 2021

Thanks.

If we take the approach that I speculate above, where @0 is inserted into the types of constructors and projections, but not printed, could the cubical composition operations be used to observe that the @0 annotations are present?

@nad
Copy link
Contributor Author

nad commented May 5, 2021

One option is to not have a --erasure option: the presence of --erasure should not rule out any models. The main disadvantage is perhaps that someone not familiar with erasure might see @0 in some type signature.

Consider the following code:

data D (A : Set) : Set where
  c : D A

record R (A : Set) : Set where
  constructor c
  field
    f : A

If you infer the type of c₁, then you get D _A_5, and for c₂ you get (f : _A_5) → R _A_5. However, for some reason the type inferred for R.f is {@0 A : Set} → R A → A. If you print the contents of the top-level module, then you get the following output:

Modules
  D
  R
Names
  D  : Set → Set
  R  : (A : Set) → Set
  c₁ : {@0 A : Set} → D A
  c₂ : {@0 A : Set} (f : A) → R A

For D and R you get the following results:

Modules
Names
  c₁ : {@0 A : Set} → D A
Modules
Names
  f : {@0 A : Set} → R A → A

nad added a commit that referenced this issue May 5, 2021
Perhaps something should be done about the code that generates
composition operations.
nad added a commit that referenced this issue May 5, 2021
According to Andrea Vezzosi nothing needs to be done about the code
that generates composition operations.
@nad
Copy link
Contributor Author

nad commented May 6, 2021

@nad the code for the composition operations still gets the parameter telescope from the datatype, so it's fine. The CubicalPrims test also passes, which confirms the generated code runs as expected.

@Saizan, doesn't it make sense to erase the parameters also in the composition operations?

nad added a commit that referenced this issue May 6, 2021
@Saizan
Copy link
Contributor

Saizan commented May 6, 2021

@nad it doesn't, why would it make sense? if you transport along (\ i -> List (ua e i)) I'd better be able to compute with that e. Even homogeneous composition needs them, as for e.g. \Sigma A B you'll need to transport along B composed with a filling.

@nad
Copy link
Contributor Author

nad commented May 6, 2021

I'm not familiar with the computation rules for the composition operations, that's why I asked you. If the parameters are (supposed to be) used for run-time computations, then it makes sense to not mark them as erased.

nad added a commit that referenced this issue May 8, 2021
@nad nad modified the milestones: 2.6.2, 2.6.3 May 14, 2021
@nad
Copy link
Contributor Author

nad commented Oct 19, 2021

One option is to not have a --erasure option: the presence of --erasure should not rule out any models. The main disadvantage is perhaps that someone not familiar with erasure might see @0 in some type signature.

I suggest that we merge my implementation of this variant now, and see if anyone complains. Any objections?

nad added a commit that referenced this issue Oct 20, 2021
This also fixes issue #5191.
@nad nad linked a pull request Oct 20, 2021 that will close this issue
nad added a commit that referenced this issue Oct 20, 2021
This also fixes issue #5191.
nad added a commit that referenced this issue Oct 20, 2021
This also fixes issue #5191.
nad added a commit that referenced this issue Oct 21, 2021
This also fixes issue #5191.
@nad
Copy link
Contributor Author

nad commented Oct 21, 2021

There were no objections, so I merged my changes.

@nad nad closed this as completed in #5366 Oct 21, 2021
nad added a commit that referenced this issue Oct 21, 2021
This also fixes issue #5191.
@nad nad added the documented-in-changelog Issues already documented in the CHANGELOG label Oct 25, 2022
nad added a commit that referenced this issue Dec 12, 2022
nad added a commit that referenced this issue Dec 12, 2022
nad added a commit that referenced this issue Dec 12, 2022
In the types of constructors and projections.
nad added a commit that referenced this issue Dec 12, 2022
In the types of constructors and projections.
EDT4 added a commit to EDT4/agda that referenced this issue Dec 20, 2022
commit 0ab714c
Author: EDT4 <36039342+EDT4@users.noreply.github.com>
Date:   Tue Dec 20 04:44:31 2022 +0100

    Allow quantified names when applying named arguments.

    Example:
      variable {l} : Agda.Primitive.Level
      variable {T} : Set l
      postulate x : let _ = T in Set₁
      y = test{T.l = Agda.Primitive.lzero} {T = Set}

commit 03466cc
Author: Nils Anders Danielsson <nad@cse.gu.se>
Date:   Mon Dec 12 12:48:11 2022 +0100

    [ agda#4786 ] Modified the changelog entry.
jespercockx pushed a commit that referenced this issue Dec 22, 2022
In the types of constructors and projections.
jespercockx pushed a commit that referenced this issue Dec 22, 2022
In the types of constructors and projections.
JobPetrovcic pushed a commit to JobPetrovcic/agda that referenced this issue Apr 5, 2024
In the types of constructors and projections.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
documented-in-changelog Issues already documented in the CHANGELOG erasure type: enhancement Issues and pull requests about possible improvements
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants