Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005724OCamlOCaml generalpublic2012-08-14 02:342013-04-23 02:40
Reporteryallop 
Assigned Togarrigue 
PrioritynormalSeveritymajorReproducibilityalways
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version4.00.0 
Target VersionFixed in Version4.01.0+dev 
Summary0005724: Interaction between GADTs and polymorphic variants
DescriptionOCaml reports an error for the last line of the following program:

type _ t =
| A : int t
| B : [`C] -> bool t

let isA (type a) (r : a t) = match r with
  | A -> true
  | B `C -> false
    ^^^^
Error: This pattern matches values of type bool t
       but a pattern was expected which matches values of type int t

If the `C in the pattern is replaced with an underscore, the program is accepted.
TagsNo tags attached.
Attached Files

- Relationships
child of 0005998assignedgarrigue GADT typing and exhaustiveness bugs 

-  Notes
(0007940)
garrigue (manager)
2012-08-14 03:01

This is a documented limitation of GADTs: types cannot be refined if a pattern-matching contains polymorphic variant.
This comes from the fact polymorphic variant pattern-matching typing is specified in the absence of type propagation and GADT type refinement requires type propagation.
This might be improved in the future, but there is no complete solution.
(0008808)
yallop (developer)
2013-01-28 13:21

It's good to see that the trunk typechecker now accepts the example.
(0008810)
garrigue (manager)
2013-01-29 01:26

Re-open before changing resolution.
(0008811)
garrigue (manager)
2013-01-29 01:28

This is now fixed in trunk, since revision 13221.

Here is the corresponding message sent to the caml-list:

As you may be aware from past threads, since the introduction of GADTs
in 4.00, some type information is propagated to pattern-matching, to allow
it to refine types.
More recently, types have started being used to disambiguate constructors
and record fields, which means some more dependency on type information
in pattern-matching.

However, a weakness of this approach was that propagation was disabled
as soon as a pattern contained polymorphic variants. The reason is that
typing rules for polymorphic variants in patterns and expression are subtly
different, and mixing information without care would lose principality.

At long last I have removed this restriction on the presence of polymorphic
variants, but this has some consequences on typing:

* while type information is now propagated, information about possibly
 present constructors still has to be discarded. For instance this means that
 the following code will not be typed as you could expect:

    let f (x : [< `A | `B]) = match x with `A -> 1 | _ -> 2;;
    val f : [< `A | `B > `A ] -> int

 What happens is that inside pattern-matching, only required constructors
 are propagated, which reduces the type of x to [> ] (a polymorphic variant
 type with any constructor…)
 As before, to give an upper bound to the matched type, the type annotation
 must be inside a pattern:

    let f = function (`A : [< `A | `B]) -> 1 | _ -> 2;;
    val f : [< `A | `B ] -> int = <fun>

* the propagation of type information may lead to failure in some cases that
 where typable before:

    type ab = [ `A | `B ];;
    let f (x : [`A]) = match x with #ab -> 1;;
    Error: This pattern matches values of type [? `A | `B ]
           but a pattern was expected which matches values of type [ `A ]
           The second variant type does not allow tag(s) `B

 During pattern-matching it is not allowed to match on absent type constructors,
 even though the type of the patterns would eventually be [< `A | `B], which allows
 discarding `B. ([? `A | `B] denotes a type obeying the rules of pattern-matching)

* for the sake of coherence, even if a type was not propagated because it
 was not known when typing a pattern-matching, we are still going to fail if a
 matched constructor appears to be absent after typing the whole function.
 (This only applies to propagable types, i.e. polymorphic variant types that
  contain only required constructors)

In particular the last two points are important, because previously such uses
would not have triggered even a warning.

The idea is that allowing propagation of types is more important than
keeping some not really useful corner cases, but if this is of concern
to you, I'm interested in feedback.

- Issue History
Date Modified Username Field Change
2012-08-14 02:34 yallop New Issue
2012-08-14 03:01 garrigue Note Added: 0007940
2012-08-14 03:01 garrigue Status new => resolved
2012-08-14 03:01 garrigue Resolution open => not fixable
2012-08-14 03:01 garrigue Assigned To => garrigue
2013-01-28 13:21 yallop Note Added: 0008808
2013-01-29 01:26 garrigue Note Added: 0008810
2013-01-29 01:26 garrigue Status resolved => confirmed
2013-01-29 01:28 garrigue Note Added: 0008811
2013-01-29 01:28 garrigue Status confirmed => resolved
2013-01-29 01:28 garrigue Fixed in Version => 4.01.0+dev
2013-01-29 01:28 garrigue Resolution not fixable => fixed
2013-04-23 02:40 garrigue Relationship added child of 0005998


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker