[m-rev.] for review: allow repeated type variables in instance heads
Julien Fischer
jfischer at opturion.com
Thu Jul 4 02:53:37 AEST 2013
For review by anyone.
Allow repeated type variables in type class instance heads.
The Mercury compiler has long required that all of the type variables referred
to in type class instance head be distinct. There is no particularly good
reason for this restriction -- the implication that it helps to ensure that
there are no overlapping instances in the reference manual is misleading, since
the way that we do that (at least in the C grades), by using the names of the
base_typeclass_infos, is not affected by type variables.
The major implementation detail needed to support repeated type variables in
instance declarations is that when doing context reduction, we must do full
matching of instances against constraints (i.e. we need to keep track of the
type variable bindings). Since we already do this, the only change required to
support repeated type variables is to remove the error checking that prevents
it.
compiler/check_typeclass.m:
Do not require that type variables in instance heads be distinct.
doc/reference_manual.texi:
Document that repeated type variables are now allowed in instance
heads.
NEWS:
Announce the change.
tests/invalid/instance_dup_var.m:
Shift this test into the valid directory.
tests/valid/Mmakefile:
tests/invalid/Mmakefile:
Conform to the above change.
tests/invalid/invalid_instance_declarations.err_exp:
tests/invalid/invalid_instance_declarations.m:
Remove instances that are now valid.
Julien.
diff --git a/NEWS b/NEWS
index d3c6eac..91d0c3f 100644
--- a/NEWS
+++ b/NEWS
@@ -1,3 +1,14 @@
+NEWS since Mercury 13.05
+------------------------
+
+Changes to the Mercury language:
+
+* Repeated type variables may now occur in the heads of type class instances.
+ For example, instance declarations like the following are now allowed:
+
+ :- instance foo(list(T), map(T, T)).
+
+
NEWS for Mercury 13.05.2
------------------------
diff --git a/compiler/check_typeclass.m b/compiler/check_typeclass.m
index 3a4f440..c7d8c25 100644
--- a/compiler/check_typeclass.m
+++ b/compiler/check_typeclass.m
@@ -14,7 +14,7 @@
%
% (1) In check_instance_declaration_types/4, we check that each type
% in the instance declaration is either a type with no arguments,
-% or a polymorphic type whose arguments are all distinct type variables.
+% or a polymorphic type whose arguments are all type variables.
% We also check that all of the types in exported instance declarations are
% in scope here. XXX The latter part should really be done earlier, but with
% the current implementation this is the most convenient spot.
@@ -318,15 +318,12 @@ is_valid_instance_type(ModuleInfo, ClassId, InstanceDefn, Type,
!:Specs = [Spec | !.Specs]
;
Type = tuple_type(Args, _),
- each_arg_is_a_distinct_type_variable(!.SeenTypes, Args, 1, Result),
+ each_arg_is_a_type_variable(!.SeenTypes, Args, 1, Result),
(
Result = no_error,
set.insert_list(Args, !SeenTypes)
;
- ( Result = local_non_distinct
- ; Result = global_non_distinct
- ; Result = arg_not_type_variable(_)
- ),
+ Result = arg_not_type_variable(_),
Spec = badly_formed_instance_type_msg(ClassId, InstanceDefn,
N, Result),
!:Specs = [Spec | !.Specs]
@@ -336,7 +333,7 @@ is_valid_instance_type(ModuleInfo, ClassId, InstanceDefn, Type,
unexpected("check_typeclass", "kinded_type")
;
Type = defined_type(TypeName, Args, _),
- each_arg_is_a_distinct_type_variable(!.SeenTypes, Args, 1, Result),
+ each_arg_is_a_type_variable(!.SeenTypes, Args, 1, Result),
(
Result = no_error,
set.insert_list(Args, !SeenTypes),
@@ -361,10 +358,7 @@ is_valid_instance_type(ModuleInfo, ClassId, InstanceDefn, Type,
true
)
;
- ( Result = local_non_distinct
- ; Result = global_non_distinct
- ; Result = arg_not_type_variable(_)
- ),
+ Result = arg_not_type_variable(_),
Spec = badly_formed_instance_type_msg(ClassId, InstanceDefn,
N, Result),
!:Specs = [Spec | !.Specs]
@@ -421,29 +415,19 @@ is_visible_instance_type(TypeName, TypeArity, TypeDefn, ClassId,
:- type instance_arg_result
---> no_error
- ; local_non_distinct
- ; global_non_distinct
; arg_not_type_variable(int).
:- inst instance_arg_result_error
- ---> local_non_distinct
- ; global_non_distinct
- ; arg_not_type_variable(ground).
+ ---> arg_not_type_variable(ground).
-:- pred each_arg_is_a_distinct_type_variable(set(mer_type)::in,
+:- pred each_arg_is_a_type_variable(set(mer_type)::in,
list(mer_type)::in, int::in, instance_arg_result::out) is det.
-each_arg_is_a_distinct_type_variable(_, [], _, no_error).
-each_arg_is_a_distinct_type_variable(SeenTypes, [Type | Types], N, Result) :-
+each_arg_is_a_type_variable(_, [], _, no_error).
+each_arg_is_a_type_variable(SeenTypes, [Type | Types], N, Result) :-
(
Type = type_variable(_, _),
- ( list.member(Type, Types) ->
- Result = local_non_distinct
- ; set.member(Type, SeenTypes) ->
- Result = global_non_distinct
- ;
- each_arg_is_a_distinct_type_variable(SeenTypes, Types, N+1, Result)
- )
+ each_arg_is_a_type_variable(SeenTypes, Types, N + 1, Result)
;
( Type = defined_type(_, _, _)
; Type = builtin_type(_)
@@ -460,19 +444,9 @@ each_arg_is_a_distinct_type_variable(SeenTypes, [Type | Types], N, Result) :-
= (error_spec::out) is det.
badly_formed_instance_type_msg(ClassId, InstanceDefn, N, Error) = Spec :-
- (
- Error = local_non_distinct,
- EndPieces = [words("is not a type"),
- words("whose arguments are distinct type variables.")]
- ;
- Error = global_non_distinct,
- EndPieces = [words("contains a type variable"),
- words("which is used in another argument.")]
- ;
- Error = arg_not_type_variable(ArgNum),
- EndPieces = [words("is a type whose"), nth_fixed(ArgNum),
- words("argument is not a variable.")]
- ),
+ Error = arg_not_type_variable(ArgNum),
+ EndPieces = [words("is a type whose"), nth_fixed(ArgNum),
+ words("argument is not a variable.")],
Spec = bad_instance_type_msg(ClassId, InstanceDefn, N, EndPieces,
badly_formed).
@@ -524,7 +498,7 @@ bad_instance_type_msg(ClassId, InstanceDefn, N, EndPieces, Kind) = Spec :-
Kind = badly_formed,
VerbosePieces =
[words("(Types in instance declarations must be functors " ++
- "with distinct variables as arguments.)"), nl],
+ "with variables as arguments.)"), nl],
HeadingMsg = simple_msg(InstanceContext,
[always(HeaderPieces), always(ArgNumPieces),
verbose_only(VerbosePieces)])
diff --git a/doc/reference_manual.texi b/doc/reference_manual.texi
index e242558..99d1ce5 100644
--- a/doc/reference_manual.texi
+++ b/doc/reference_manual.texi
@@ -4998,28 +4998,28 @@ An instance declaration has the form
An @samp{instance} declaration gives a type for each parameter of the
type class. Each of these types must be either a type with no arguments, or
-a polymorphic type whose arguments are all distinct type variables.
+a polymorphic type whose arguments are all type variables.
@c If this restriction is ever lifted, the algorithms for encoding the names of
@c the data structures describing the instance, in base_typeclass_info.m
@c and/or rtti.m, would need to be updated as well.
-For example @code{int}, @code{list(T)} and @code{bintree(K,V)} are allowed,
-but @code{T}, @code{list(int)} and @code{bintree(T,T)} are not.
+For example @code{int}, @code{list(T)}, @code{bintree(K, V)} and
+ at code{bintree(T, T)} are allowed, but @code{T} and @code{list(int)} are not.
The types in an instance declaration must not be abstract types which
are elsewhere defined as equivalence types.
-A program may not contain more than one instance
-declaration for a particular type (or sequence of types, in
-the case of a multi-parameter type class) and typeclass.
-These restrictions ensure that there are no overlapping
-instance declarations, i.e.@: for each typeclass there is at
-most one instance declaration that may be applied to any
-type (or sequence of types).
-
-Each @var{methoddefinition} entry in the @samp{where [@dots{}]} part
-of an @code{instance} declaration defines the implementation of one of
-the class methods for this instance. There are two ways of defining
-methods. The first way is to define a method by giving the name of
-the predicate or function which implements that method. In this
-case, the @var{methoddefinition} must have one of the following forms:
+A program may not contain more than one instance declaration for a particular
+type (or sequence of types, in the case of a multi-parameter type class) and
+typeclass.
+These restrictions ensure that there are no overlapping instance declarations,
+i.e.@: for each typeclass there is at most one instance declaration that may be
+applied to any type (or sequence of types).
+
+Each @var{methoddefinition} entry in the @samp{where [@dots{}]} part of an
+ at code{instance} declaration defines the implementation of one of the class
+methods for this instance.
+There are two ways of defining methods.
+The first way is to define a method by giving the name of the predicate or
+function which implements that method.
+In this case, the @var{methoddefinition} must have one of the following forms:
@example
pred(@var{methodname}/@var{arity}) is @var{predname}
diff --git a/tests/invalid/Mmakefile b/tests/invalid/Mmakefile
index 448a0d2..72826fc 100644
--- a/tests/invalid/Mmakefile
+++ b/tests/invalid/Mmakefile
@@ -122,7 +122,6 @@ SINGLEMODULE= \
inline_conflict \
inst_list_dup \
instance_bug \
- instance_dup_var \
instance_no_type \
instance_var_bug \
invalid_event \
diff --git a/tests/invalid/instance_dup_var.m b/tests/invalid/instance_dup_var.m
deleted file mode 100644
index 393ee6f..0000000
--- a/tests/invalid/instance_dup_var.m
+++ /dev/null
@@ -1,16 +0,0 @@
-:- module instance_dup_var.
-:- interface.
-
-:- type foo(A, B) ---> foo(A, B).
-:- type bar ---> bar.
-
-:- typeclass baz(X, Y) where [].
-
-:- implementation.
-
- % Error: T is duplicated.
-:- instance baz(foo(T, T), bar) where [].
-
- % Error: A is duplicated.
-:- instance baz(foo(A, B), foo(C, A)) where [].
-
diff --git a/tests/invalid/invalid_instance_declarations.err_exp b/tests/invalid/invalid_instance_declarations.err_exp
index f7ef8ed..4b61451 100644
--- a/tests/invalid/invalid_instance_declarations.err_exp
+++ b/tests/invalid/invalid_instance_declarations.err_exp
@@ -1,20 +1,10 @@
-invalid_instance_declarations.m:015: In instance declaration for
-invalid_instance_declarations.m:015: `invalid_instance_declarations.tc(invalid_instance_declarations.t(T,
-invalid_instance_declarations.m:015: T))':
-invalid_instance_declarations.m:015: the first argument is not a type whose
-invalid_instance_declarations.m:015: arguments are distinct type variables.
-invalid_instance_declarations.m:016: In instance declaration for
-invalid_instance_declarations.m:016: `invalid_instance_declarations.tc(((func)
-invalid_instance_declarations.m:016: = T))':
-invalid_instance_declarations.m:016: the first argument is a higher order
-invalid_instance_declarations.m:016: type.
-invalid_instance_declarations.m:017: In instance declaration for
-invalid_instance_declarations.m:017: `invalid_instance_declarations.tc({T,
-invalid_instance_declarations.m:017: T})':
-invalid_instance_declarations.m:017: the first argument is not a type whose
-invalid_instance_declarations.m:017: arguments are distinct type variables.
-invalid_instance_declarations.m:018: In instance declaration for
-invalid_instance_declarations.m:018: `invalid_instance_declarations.tc(invalid_instance_declarations.t(int))':
-invalid_instance_declarations.m:018: the first argument is a type whose first
-invalid_instance_declarations.m:018: argument is not a variable.
+invalid_instance_declarations.m:013: In instance declaration for
+invalid_instance_declarations.m:013: `invalid_instance_declarations.tc(((func)
+invalid_instance_declarations.m:013: = T))':
+invalid_instance_declarations.m:013: the first argument is a higher order
+invalid_instance_declarations.m:013: type.
+invalid_instance_declarations.m:014: In instance declaration for
+invalid_instance_declarations.m:014: `invalid_instance_declarations.tc(invalid_instance_declarations.t(int))':
+invalid_instance_declarations.m:014: the first argument is a type whose first
+invalid_instance_declarations.m:014: argument is not a variable.
For more information, recompile with `-E'.
diff --git a/tests/invalid/invalid_instance_declarations.m b/tests/invalid/invalid_instance_declarations.m
index b14217b..c3c6674 100644
--- a/tests/invalid/invalid_instance_declarations.m
+++ b/tests/invalid/invalid_instance_declarations.m
@@ -6,13 +6,9 @@
:- typeclass tc(T) where [].
-:- type e(T) == t(T, T).
:- type f(T) == ((func) = T).
-:- type g(T) == {T, T}.
:- type h == t(int).
:- implementation.
-:- instance tc(e(T)) where [].
:- instance tc(f(T)) where [].
-:- instance tc(g(T)) where [].
:- instance tc(h) where [].
diff --git a/tests/valid/Mmakefile b/tests/valid/Mmakefile
index 6df4698..a65aa36 100644
--- a/tests/valid/Mmakefile
+++ b/tests/valid/Mmakefile
@@ -30,6 +30,7 @@ TYPECLASS_PROGS= \
func_method \
fundeps \
fundeps_poly_instance \
+ instance_dup_var \
instance_superclass \
instance_typequal \
instance_unconstrained_tvar \
diff --git a/tests/valid/instance_dup_var.m b/tests/valid/instance_dup_var.m
new file mode 100644
index 0000000..df76ec4
--- /dev/null
+++ b/tests/valid/instance_dup_var.m
@@ -0,0 +1,14 @@
+:- module instance_dup_var.
+:- interface.
+
+:- type foo(A, B) ---> foo(A, B).
+:- type bar ---> bar.
+
+:- typeclass baz(X, Y) where [].
+
+:- implementation.
+
+:- instance baz(foo(T, T), bar) where [].
+
+:- instance baz(foo(A, B), foo(C, A)) where [].
+
More information about the reviews
mailing list