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

nonrec misbehaves with GADTs #6934

Open
vicuna opened this issue Jul 21, 2015 · 9 comments
Open

nonrec misbehaves with GADTs #6934

vicuna opened this issue Jul 21, 2015 · 9 comments
Assignees

Comments

@vicuna
Copy link

vicuna commented Jul 21, 2015

Original bug ID: 6934
Reporter: @mmottl
Assigned to: @garrigue
Status: resolved (set by @garrigue on 2017-03-15T23:38:28Z)
Resolution: fixed
Priority: normal
Severity: minor
Version: 4.02.2
Fixed in version: 4.06.0 +dev/beta1/beta2/rc1
Category: typing
Monitored by: runhang @gasche @yallop @hcarty @mmottl

Bug description

Consider the following example:

type nonrec t = A : t

The above will fail with an unbound type constructor for "t". But it isn't really a recursive type, it's a GADT. I think "nonrec" shouldn't apply to the return type of a GADT, at least not to the outermost type constructor defining the GADT, though possibly to types in its parameters.

@vicuna
Copy link
Author

vicuna commented Jul 22, 2015

Comment author: @diml

I'd be in favor of just updating the error message to say that you can't use [nonrec] when defining a GADT. I don't like the idea of allowing [type nonrec t = A : t -> t] where the last two [t]s means two different things.

@vicuna
Copy link
Author

vicuna commented Jul 22, 2015

Comment author: @mmottl

@dim I agree that the syntax of GADTs doesn't compose nicely with "nonrec" here, and we don't want to break existing syntax. Maybe it would have been better to do something like:

type t as u = t * u

where the "t" on the RHS refers to the previous definition of "t", and "u" is the recursive alias for the current definition of "t".

@vicuna
Copy link
Author

vicuna commented Mar 14, 2017

Comment author: @garrigue

My understanding is that nonrec is essentially intended for type abbreviations.
So is its not working with GADTs really a problem?
I tend to concur with @dim.

@vicuna
Copy link
Author

vicuna commented Mar 15, 2017

Comment author: @mmottl

It's surely not a big problem. It's conceivable that a developer has opened a module and just wants to define type "t" in terms of a type "t" in the opened module. Though dropping "nonrec" and using an explicit module path would easily solve the issue, the error message will likely confuse the developer.

@vicuna
Copy link
Author

vicuna commented Mar 15, 2017

Comment author: @garrigue

Fixed in commit f900888 by introducing a new error message:

type nonrec t = A : t;;
Line _, characters 16-21:
Error: GADT case syntax cannot be used in a 'nonrec' block.

@mikeshulman
Copy link

I would like to be able to use nonrec with GADTs. I have a module A that defines a parametrized type t, but sometimes I want to wrap up an element of t with its type parameters into an unparametrized type. Sometimes it's enough to do

module A = struct
  type 'a t = ...
  type wrapped = Wrap : 'a t -> wrapped
end

but sometimes the reason I'm wrapping it up is to use it as an argument of a functor like Map.Make that requires to be passed a module containing a single unparametrized type t. So I would like to be able to write

module A = struct
  type 'a t = ...
  module Wrapped = struct
    type nonrec t = Wrap : 'a t -> t
  end
end

and then call e.g. Map.Make(A.Wrapped), but this doesn't work because nonrec GADTs are forbidden. Clearly this GADT is not actually recursive, and I don't think there's any potential confusion, particularly because the outer t is parametrized and the inner one isn't.

@gasche
Copy link
Member

gasche commented Nov 9, 2023

Given @mikeshulman's reasonable example above, I would be in favor of implementing the natural meaning of nonrec for GADTs, which is that the return type constructor is allowed to recursively reference the type name, but other occurrences of the name are resolved in the outer scope.

This allows for some somewhat confusing cases, such as:

type t
type nonrec _ t = Weird : t t

but there is no ambiguity.

On the other hand, I find nonrec limited here, because we cannot have a type where we mention both the current type and the previous type in scope. (This is not specific to GADTs, it applies also for standard sum types.) The syntax proposed by @mmottl above, type 'a t as u, which I would suggest to name type nonrec 'a t as u instead, would lift this restriction and be both more readable and more expressive. I wonder if we should consider exploring it. (Another option would be to let users use t/1 explicitly, but this is evil, especially since @Octachron mistakenly chose t/2 instead of t/1 to mean the previous binding in scope.)

So my recommendation:

  • in the short term: bite the bullet and allow nonrec for GADTs, with the reasonable specification that only the return type constructor refers to the current type; no warning, no nothing, people who want to write subtle code will write subtle code.
  • in the medium term: keep thinking about better designs

@Octachron
Copy link
Member

Note that at the signature level, I have the impression than writing:

type 'a inner_t := 'a t
type t = Wrap: 'a inner_t -> t

works well enough and I am not sure complexifying the scoping rule for nonrec is worth it.

However, the structure level variant

open struct type 'a inner_t = 'a t end
type t = Wrap: 'a inner_t -> t

feels less lightweight. I would be more tempted to add type t := ... as a syntactic sugar for the open struct ... end variant than altering the scoping rules for nonrec.

@gasche
Copy link
Member

gasche commented Nov 9, 2023

I am also okay with going that route, but to be done properly (as a proper AST node with its own type-checking code) is more work, I expect, than just extending nonrec to GADTs.

(Let me "reopen" this issue to indicate that a need for a different resolution has emerged.)

@gasche gasche reopened this Nov 9, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

5 participants