[m-dev.] for review: change typeclass_info structure

David Glen JEFFERY dgj at cs.mu.OZ.AU
Fri Mar 31 15:38:11 AEST 2000


Hi,

Fergus or Zoltan can review this one.


===================================================================

Estimated hours taken: 10

Make an addition to the type class info structure; add type infos for
any type variables from the head of the instance declaration which are
unconstrained, and make the class method call mechanism insert these as
arguments to method calls.

Also move the documentation about the type class transformation from
polymorphism.m to a new file, compiler/notes/type_class_transformation.html.

compiler/base_typeclass_info.m:
	Generate the appropriate part of the new structure in the
	base_typeclass_info.
compiler/polymorphism.m:
	Add the appropriate type infos to the typeclass_info.
compiler/type_util.m:
	Add a new predicate `get_unconstrained_tvars'.
runtime/mercury_deep_copy_body.h:
	Update copy_typeclass_info to reflect the new structure.
runtime/mercury_ho_call.c:
	Copy the extra type infos to the beginning of the arguments when
	doing a class method call.
runtime/mercury_type_info.h:
	Update the macros used to access the type class info.

compiler/notes/type_class_transformation.html:
	The documentation about the type class transformation has been
	moved from polymorphism.m to here. This change corrects that
	documentation in several places and updates that documentation to
	reflect the changes to the typeclass_info structure from this diff.

tests/hard_coded/typeclasses/instance_unconstrained_tvar.exp:
tests/hard_coded/typeclasses/instance_unconstrained_tvar.m:
	A test case for this change.
tests/hard_coded/typeclasses/Mmakefile:
	Turn this test case on. For the moment, type specialisation is
	turned off for this test case as the specialiser does not insert the
	extra type infos that are needed.


===================================================================
Index: compiler/base_typeclass_info.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/base_typeclass_info.m,v
retrieving revision 1.17
diff -u -t -r1.17 base_typeclass_info.m
--- compiler/base_typeclass_info.m	2000/01/17 03:38:41	1.17
+++ compiler/base_typeclass_info.m	2000/03/30 07:17:00
@@ -8,9 +8,9 @@
 % to hold the base_typeclass_info structures of the typeclass instances defined
 % by the current module.
 %
-% See polymorphism.m for a description of the various ways to represent
-% type information, including a description of the base_typeclass_info
-% structures.
+% See notes/type_class_transformation.html for a description of the various 
+% ways to represent type information, including a description of the
+% base_typeclass_info structures.
 %
 % Author: dgj.
 %
@@ -37,6 +37,7 @@
 :- import_module hlds_data, hlds_pred, hlds_out.
 :- import_module code_util, globals, options, term.
 :- import_module bool, string, map, std_util, require, assoc_list.
+:- import_module type_util, int.
 
 %---------------------------------------------------------------------------%
 
@@ -90,8 +91,8 @@
                 DataName = base_typeclass_info(ClassId, InstanceString),
 
                 base_typeclass_info__gen_rvals_and_procs(PredProcIds,
-                        InstanceConstraints, ModuleInfo, ClassId, 
-                        Rvals, Procs),
+                        InstanceTypes, InstanceConstraints, ModuleInfo, 
+                        ClassId, Rvals, Procs),
                 
                         % XXX Need we always export it from the module?
                         % (Note that linkage/2 in llds_out.m assumes
@@ -110,17 +111,23 @@
 %----------------------------------------------------------------------------%
 
 :- pred base_typeclass_info__gen_rvals_and_procs(maybe(list(hlds_class_proc)),
-        list(class_constraint), module_info, class_id, list(maybe(rval)),
-        list(pred_proc_id)).
-:- mode base_typeclass_info__gen_rvals_and_procs(in, in, in, in, 
+        list(type), list(class_constraint), module_info, class_id,
+        list(maybe(rval)), list(pred_proc_id)).
+:- mode base_typeclass_info__gen_rvals_and_procs(in, in, in, in, in, 
         out, out) is det.
 
-base_typeclass_info__gen_rvals_and_procs(no, _, _, _, [], []) :-
+base_typeclass_info__gen_rvals_and_procs(no, _, _, _, _, [], []) :-
         error("pred_proc_ids should have been filled in by check_typeclass.m").
-base_typeclass_info__gen_rvals_and_procs(yes(PredProcIds0), Constraints,
+base_typeclass_info__gen_rvals_and_procs(yes(PredProcIds0), Types, Constraints,
                 ModuleInfo, ClassId, Rvals, PredProcIds) :-
-        list__length(Constraints, InstanceArity),
-        ArityArg = yes(const(int_const(InstanceArity))),
+
+
+        term__vars_list(Types, TypeVars),
+        get_unconstrained_tvars(TypeVars, Constraints, Unconstrained),
+        list__length(Constraints, NumConstraints),
+        list__length(Unconstrained, NumUnconstrained),
+        NumExtraArg = yes(const(int_const(NumConstraints+NumUnconstrained))),
+        NumConstraintsArg = yes(const(int_const(NumConstraints))),
         ExtractPredProcId = lambda([HldsPredProc::in, PredProc::out] is det,
                 (
                         HldsPredProc = hlds_class_proc(PredId, ProcId),
@@ -133,8 +140,8 @@
                         SuperClassCount, ClassArity),
         list__length(PredAddrArgs, NumMethods),
         NumMethodsArg = yes(const(int_const(NumMethods))),
-        Rvals = [ ArityArg, SuperClassCount, ClassArity, NumMethodsArg 
-                        | PredAddrArgs ].
+        Rvals = [ NumExtraArg, NumConstraintsArg, SuperClassCount, 
+                        ClassArity, NumMethodsArg | PredAddrArgs ].
 
 :- pred base_typeclass_info__construct_pred_addrs(list(pred_proc_id),
         module_info, list(maybe(rval))).
Index: compiler/polymorphism.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/polymorphism.m,v
retrieving revision 1.182
diff -u -t -r1.182 polymorphism.m
--- compiler/polymorphism.m	2000/03/24 10:27:31	1.182
+++ compiler/polymorphism.m	2000/03/31 04:58:50
@@ -13,6 +13,9 @@
 % These arguments are structures that contain, amoung other things,
 % higher-order predicate terms for the polymorphic procedures or methods.
 
+% See notes/type_class_transformation.html for a description of the
+% transformation and data structures used to implement type classes.
+
 % XXX The way the code in this module handles existential type classes
 % and type class constraints is a bit ad-hoc, in general; there are
 % definitely parts of this code (marked with XXXs below) that could
@@ -153,142 +156,8 @@
 %
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
-%
-% Tranformation of code using typeclasses:
-%
-% Every predicate which has a typeclass constraint is given an extra
-% argument for every constraint in the predicate's type declaration.
-% The argument is the "dictionary", or "typeclass_info" for the typeclass.
-% The dictionary contains pointers to each of the class methods.
-%
-%-----------------------------------------------------------------------------%
-%
-% Representation of a typeclass_info:
-%       The typeclass_info is represented in two parts (the typeclass_info
-%       itself, and a base_typeclass_info), in a similar fashion to the
-%       type_info being represented in two parts (the type_info and the
-%       type_ctor_info).
-%
-%               The base_typeclass_info contains:
-%                 * the number of constraints on the instance decl. (`l')
-%                 * the number of constraints on the typeclass decl. (`m')
-%                 * the number of parameters (type variables) from 
-%                        the typeclass decl. (`n')
-%                 * the number of constraints on the typeclass decl. (`p')
-%                 * pointer to method #1
-%                   ...
-%                 * pointer to method #p
-%
-%               The typeclass_info contains:
-%                 * a pointer to the base typeclass info
-%                 * typeclass info #1 for constraint on instance decl
-%                 * ...
-%                 * typeclass info #l for constraint on instance decl
-%                 * typeclass info for superclass #1
-%                   ...
-%                 * typeclass info for superclass #m
-%                 * type info #1 
-%                 * ...
-%                 * type info #n
-%
-% The base_typeclass_info is produced statically, and there is one for
-% each instance declaration. For each constraint on the instance
-% declaration, the corresponding typeclass_info is stored in the second
-% part.
-%
-% eg. for the following program:
-%
-%       :- typeclass foo(T) where [...].
-%       :- instance  foo(int) where [...].
-%       :- instance  foo(list(T)) <= foo(T) where [...].
-%
-%       The typeclass_info for foo(int) is:
-%               The base_typeclass_info:
-%                 * 0 (arity of the instance declaration) 
-%                 * pointer to method #1
-%                   ...
-%                 * pointer to method #n
-%
-%               The typeclass_info:
-%                 * a pointer to the base typeclass info
-%                 * type_info for int
-%
-%       The typeclass_info for foo(list(T)) is:
-%               The base_typeclass_info:
-%                 * 1 (arity of the instance declaration)
-%                 * pointer to method #1
-%                   ...
-%                 * pointer to method #n
-%
-%               The typeclass_info contains:
-%                 * a pointer to the base typeclass info
-%                 * typeclass info for foo(T)
-%                 * type_info for list(T)
-%
-% If the "T" for the list is known, the whole typeclass_info will be static
-% data. When we do not know until runtime, the typeclass_info is constructed
-% dynamically.
-%
 %-----------------------------------------------------------------------------%
 %
-% Example of transformation:
-%
-% Take the following code as an example (assuming the declarations above),
-% ignoring the requirement for super-homogeneous form for clarity:
-%
-%       :- pred p(T1) <= foo(T1).
-%       :- pred q(T2, T3) <= foo(T2), bar(T3).
-%       :- pred r(T4, T5) <= foo(T4).
-%
-%       p(X) :- q([X], 0), r(X, 0).
-%
-% We add an extra argument for each type class constraint, and one
-% argument for each unconstrained type variable.
-%
-%       :- pred p(typeclass_info(foo(T1)), T1).
-%       :- pred q(typeclass_info(foo(T2)), typeclass_info(bar(T3)), T2, T3).
-%       :- pred r(typeclass_info(foo(T4)), type_info(T5), T4, T5).
-%
-% We transform the body of p to this:
-%
-%       p(TypeClassInfoT1, X) :-
-%               BaseTypeClassInfoT2 = base_typeclass_info(
-%                       1,
-%                       ...
-%                       ... (The methods for the foo class from the list
-%                       ...  instance)
-%                       ...
-%                       ),
-%               TypeClassInfoT2 = typeclass_info(
-%                       BaseTypeClassInfoT2,
-%                       TypeClassInfoT1,
-%                       <type_info for list(T1)>),
-%               BaseTypeClassInfoT3 = base_typeclass_info(
-%                       0,
-%                       ...
-%                       ... (The methods for the bar class from the int
-%                       ...  instance)
-%                       ...
-%                       ),
-%               TypeClassInfoT3 = typeclass_info(
-%                       BaseTypeClassInfoT3,
-%                       <type_info for int>),
-%               q(TypeClassInfoT2, TypeClassInfoT3, [X], 0),
-%               BaseTypeClassInfoT4 = baseclass_type_info(
-%                       0,
-%                       ...
-%                       ... (The methods for the foo class from the int
-%                       ...  instance)
-%                       ...
-%                       ),
-%               TypeClassInfoT4 = typeclass_info(
-%                       BaseTypeClassInfoT4,
-%                       <type_info for int>),
-%               r(TypeClassInfoT1, <type_info for int>, X, 0).
-%
-%-----------------------------------------------------------------------------%
-%-----------------------------------------------------------------------------%
-%
 % Transformation of code using existentially quantified types:
 % 
 % The transformation for existential types is similar to the
@@ -2071,9 +1940,13 @@
                                 InstanceConstraints0, InstanceTypes0, _, _, 
                                 InstanceTVarset, SuperClassProofs0),
 
+                        term__vars_list(InstanceTypes0, InstanceTvars),
+                        get_unconstrained_tvars(InstanceTvars,
+                                InstanceConstraints0, UnconstrainedTvars0),
+
                                 % We can ignore the typevarset because all the
-                                % type variables that are created are bound.
-                                % When we call type_list_subsumes then apply
+                                % type variables that are created are bound
+                                % when we call type_list_subsumes then apply
                                 % the resulting bindings.
                         varset__merge_subst(TypeVarSet, InstanceTVarset,
                                 _NewTVarset, RenameSubst),
@@ -2097,6 +1970,14 @@
                         apply_rec_subst_to_constraint_proofs(InstanceSubst,
                                 SuperClassProofs1, SuperClassProofs),
 
+                        term__var_list_to_term_list(UnconstrainedTvars0,
+                                UnconstrainedTypes0),
+                        term__apply_substitution_to_list(UnconstrainedTypes0,
+                                RenameSubst, UnconstrainedTypes1),
+                        term__apply_rec_substitution_to_list(
+                                UnconstrainedTypes1, InstanceSubst, 
+                                UnconstrainedTypes),
+
                                 % Make the type_infos for the types
                                 % that are constrained by this. These
                                 % are packaged in the typeclass_info
@@ -2114,6 +1995,15 @@
                                 [], InstanceExtraTypeClassInfoVars0, 
                                 ExtraGoals0, ExtraGoals1, 
                                 Info1, Info2),
+
+                                % Make the type_infos for the unconstrained
+                                % type variables from the head of the
+                                % instance declaration
+                        polymorphism__make_type_info_vars(
+                                UnconstrainedTypes, Context, 
+                                InstanceExtraTypeInfoUnconstrainedVars, 
+                                UnconstrainedTypeInfoGoals,
+                                Info2, Info3),
                         
                                 % The variables are built up in 
                                 % reverse order.
@@ -2121,12 +2011,13 @@
                                 InstanceExtraTypeClassInfoVars),
 
                         polymorphism__construct_typeclass_info(
+                                InstanceExtraTypeInfoUnconstrainedVars,
                                 InstanceExtraTypeInfoVars, 
                                 InstanceExtraTypeClassInfoVars, 
                                 ClassId, Constraint, InstanceNum,
                                 ConstrainedTypes,
                                 SuperClassProofs, ExistQVars, Var, NewGoals, 
-                                Info2, Info),
+                                Info3, Info),
 
                         MaybeVar = yes(Var),
 
@@ -2134,10 +2025,14 @@
                                 % already been reversed, so lets
                                 % reverse them back.
                         list__reverse(TypeInfoGoals, RevTypeInfoGoals),
+                        list__reverse(UnconstrainedTypeInfoGoals, 
+                                RevUnconstrainedTypeInfoGoals),
 
                         list__append(ExtraGoals1, RevTypeInfoGoals,
                                 ExtraGoals2),
-                        list__append(NewGoals, ExtraGoals2, ExtraGoals)
+                        list__append(NewGoals, ExtraGoals2, ExtraGoals3),
+                        list__append(RevUnconstrainedTypeInfoGoals,
+                                ExtraGoals3, ExtraGoals)
                 ;
                                 % We have to extract the typeclass_info from
                                 % another one
@@ -2251,14 +2146,15 @@
                 )
         ).
 
-:- pred polymorphism__construct_typeclass_info(list(prog_var), list(prog_var),
-        class_id, class_constraint, int, 
+:- pred polymorphism__construct_typeclass_info(list(prog_var), list(prog_var), 
+        list(prog_var), class_id, class_constraint, int, 
         list(type), map(class_constraint, constraint_proof),
         existq_tvars, prog_var, list(hlds_goal), poly_info, poly_info).
-:- mode polymorphism__construct_typeclass_info(in, in, in, in, in, in, in, in,
-        out, out, in, out) is det.
+:- mode polymorphism__construct_typeclass_info(in, in, in, in, in, 
+        in, in, in, in, out, out, in, out) is det.
 
-polymorphism__construct_typeclass_info(ArgTypeInfoVars, ArgTypeClassInfoVars,
+polymorphism__construct_typeclass_info(ArgUnconstrainedTypeInfoVars, 
+                ArgTypeInfoVars, ArgTypeClassInfoVars,
                 ClassId, Constraint, InstanceNum,
                 InstanceTypes, SuperClassProofs, ExistQVars,
                 NewVar, NewGoals, Info0, Info) :-
@@ -2278,7 +2174,8 @@
                 % lay out the argument variables as expected in the
                 % typeclass_info
         list__append(ArgTypeClassInfoVars, ArgSuperClassVars, ArgVars0),
-        list__append(ArgVars0, ArgTypeInfoVars, ArgVars),
+        list__append(ArgVars0, ArgTypeInfoVars, ArgVars1),
+        list__append(ArgUnconstrainedTypeInfoVars, ArgVars1, ArgVars),
 
         ClassId = class_id(ClassName, _Arity),
 
Index: compiler/type_util.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/type_util.m,v
retrieving revision 1.80
diff -u -t -r1.80 type_util.m
--- compiler/type_util.m	2000/02/16 02:15:39	1.80
+++ compiler/type_util.m	2000/03/03 06:01:06
@@ -352,6 +352,9 @@
 :- pred constraint_get_tvars(class_constraint, list(tvar)).
 :- mode constraint_get_tvars(in, out) is det.
 
+:- pred get_unconstrained_tvars(list(tvar), list(class_constraint), list(tvar)).
+:- mode get_unconstrained_tvars(in, in, out) is det.
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -1299,5 +1302,9 @@
 
 constraint_get_tvars(constraint(_Name, Args), TVars) :-
         term__vars_list(Args, TVars).
+
+get_unconstrained_tvars(Tvars, Constraints, Unconstrained) :-
+        constraint_list_get_tvars(Constraints, ConstrainedTvars),
+        list__delete_elems(Tvars, ConstrainedTvars, Unconstrained).
 
 %-----------------------------------------------------------------------------%
Index: runtime/mercury_deep_copy_body.h
===================================================================
RCS file: /home/staff/zs/imp/mercury/runtime/mercury_deep_copy_body.h,v
retrieving revision 1.21
diff -u -t -r1.21 mercury_deep_copy_body.h
--- runtime/mercury_deep_copy_body.h	2000/03/24 10:27:47	1.21
+++ runtime/mercury_deep_copy_body.h	2000/03/30 05:03:29
@@ -681,6 +681,7 @@
         int     num_arg_typeinfos;
         int     num_super;
         int     arity;
+        int     num_unconstrained;
         int     i;
 
         /*
@@ -691,6 +692,9 @@
         base_typeclass_info = (Word *) *typeclass_info;
 
         arity = MR_typeclass_info_instance_arity(typeclass_info);
+        num_unconstrained = 
+                MR_typeclass_info_num_extra_instance_args(typeclass_info) 
+                - arity;
         num_super = MR_typeclass_info_num_superclasses(typeclass_info);
         num_arg_typeinfos = MR_typeclass_info_num_type_infos(typeclass_info);
         incr_saved_hp(LVALUE_CAST(Word, new_typeclass_info),
@@ -698,14 +702,24 @@
 
         new_typeclass_info[0] = (Word) base_typeclass_info;
 
-                /* First, copy all the typeclass infos */
-        for (i = 1; i < arity + num_super + 1; i++) {
+                /* First, copy typeinfos for unconstrained tvars from */
+                /* the instance declaration */
+        for (i = 1; i < num_unconstrained + 1; i++) {
+            new_typeclass_info[i] = (Word) copy_type_info(
+                (MR_TypeInfo *)(&typeclass_info[i]), lower_limit, upper_limit);
+        }
+                /* Next, copy all the typeclass infos */
+        for (i = num_unconstrained + 1; 
+                i < num_unconstrained + arity + num_super + 1; 
+                i++) 
+        {
             new_typeclass_info[i] = (Word) copy_typeclass_info(
                 &typeclass_info[i], lower_limit, upper_limit);
         }
-                /* Then, copy all the type infos */
-        for (i = arity + num_super + 1;
-            i < arity + num_super + num_arg_typeinfos + 1;
+
+                /* Then, copy the type infos */
+        for (i = num_unconstrained + arity + num_super + 1;
+            i < num_unconstrained + arity + num_super + num_arg_typeinfos + 1;
             i++)
         {
             new_typeclass_info[i] = (Word) copy_type_info(
Index: runtime/mercury_ho_call.c
===================================================================
RCS file: /home/staff/zs/imp/mercury/runtime/mercury_ho_call.c,v
retrieving revision 1.31
diff -u -t -r1.31 mercury_ho_call.c
--- runtime/mercury_ho_call.c	2000/03/24 10:27:48	1.31
+++ runtime/mercury_ho_call.c	2000/03/29 07:24:07
@@ -137,32 +137,33 @@
 {
         Code    *destination;
         int     num_in_args;
-        int     num_arg_typeclass_infos;
+        int     num_extra_instance_args;
         int     i;
 
         destination = MR_typeclass_info_class_method(r1, r2);
-        num_arg_typeclass_infos = (int) MR_typeclass_info_instance_arity(r1);
+        num_extra_instance_args = 
+                (int) MR_typeclass_info_num_extra_instance_args(r1);
 
         num_in_args = r3; /* number of input args */
 
         save_registers();
 
-        if (num_arg_typeclass_infos < MR_CLASS_METHOD_CALL_INPUTS) {
+        if (num_extra_instance_args < MR_CLASS_METHOD_CALL_INPUTS) {
                 /* copy to the left, from the left */
                 for (i = 1; i <= num_in_args; i++) {
-                        virtual_reg(i + num_arg_typeclass_infos) =
+                        virtual_reg(i + num_extra_instance_args) =
                                 virtual_reg(i + MR_CLASS_METHOD_CALL_INPUTS);
                 }
-        } else if (num_arg_typeclass_infos > MR_CLASS_METHOD_CALL_INPUTS) {
+        } else if (num_extra_instance_args > MR_CLASS_METHOD_CALL_INPUTS) {
                 /* copy to the right, from the right */
                 for (i = num_in_args; i > 0; i--) {
-                        virtual_reg(i + num_arg_typeclass_infos) =
+                        virtual_reg(i + num_extra_instance_args) =
                                 virtual_reg(i + MR_CLASS_METHOD_CALL_INPUTS);
                 }
         } /* else the new args are in the right place */
 
-        for (i = num_arg_typeclass_infos; i > 0; i--) {
-                virtual_reg(i) =
+        for (i = num_extra_instance_args; i > 0; i--) {
+                virtual_reg(i) = 
                         MR_typeclass_info_arg_typeclass_info(virtual_reg(1),i);
         }
 
Index: runtime/mercury_type_info.h
===================================================================
RCS file: /home/staff/zs/imp/mercury/runtime/mercury_type_info.h,v
retrieving revision 1.42
diff -u -t -r1.42 mercury_type_info.h
--- runtime/mercury_type_info.h	2000/03/26 15:57:35	1.42
+++ runtime/mercury_type_info.h	2000/03/29 07:38:22
@@ -288,17 +288,19 @@
 ** Mercury typeclass_info.
 */
 
-#define MR_typeclass_info_instance_arity(tci)                       \
+#define MR_typeclass_info_num_extra_instance_args(tci)              \
     ((Integer)(*(Word **)(tci))[0])
-#define MR_typeclass_info_num_superclasses(tci)                     \
+#define MR_typeclass_info_instance_arity(tci)                       \
     ((Integer)(*(Word **)(tci))[1])
-#define MR_typeclass_info_num_type_infos(tci)                       \
+#define MR_typeclass_info_num_superclasses(tci)                     \
     ((Integer)(*(Word **)(tci))[2])
-#define MR_typeclass_info_num_methods(tci)                          \
+#define MR_typeclass_info_num_type_infos(tci)                       \
     ((Integer)(*(Word **)(tci))[3])
+#define MR_typeclass_info_num_methods(tci)                          \
+    ((Integer)(*(Word **)(tci))[4])
 #define MR_typeclass_info_class_method(tci, n)                      \
-    ((Code *)(*(Word **)tci)[(n+3)])
-#define MR_typeclass_info_arg_typeclass_info(tci, n)                \
+    ((Code *)(*(Word **)tci)[(n+4)])
+#define MR_typeclass_info_arg_typeclass_info(tci, n)                \
     (((Word *)(tci))[(n)])
 
 /*
@@ -307,10 +309,10 @@
 ** number of superclass_infos for the class added to it.
 */
 
-#define MR_typeclass_info_superclass_info(tci, n)                   \
-    (((Word *)(tci))[MR_typeclass_info_instance_arity(tci) + (n)])
-#define MR_typeclass_info_type_info(tci, n)                         \
-    (((Word *)(tci))[MR_typeclass_info_instance_arity(tci) + (n)])
+#define MR_typeclass_info_superclass_info(tci, n)                   \
+    (((Word *)(tci))[MR_typeclass_info_num_extra_instance_args(tci) + (n)])
+#define MR_typeclass_info_type_info(tci, n)                         \
+    (((Word *)(tci))[MR_typeclass_info_num_extra_instance_args(tci) + (n)])
 
 /*---------------------------------------------------------------------------*/
 
Index: tests/hard_coded/typeclasses/Mmakefile
===================================================================
RCS file: /home/staff/zs/imp/tests/hard_coded/typeclasses/Mmakefile,v
retrieving revision 1.26
diff -u -t -r1.26 Mmakefile
--- tests/hard_coded/typeclasses/Mmakefile	2000/03/27 05:08:05	1.26
+++ tests/hard_coded/typeclasses/Mmakefile	2000/03/31 04:46:03
@@ -20,6 +20,7 @@
         implied_instance_missing_constraint \
         implied_instance_poly \
         impure_methods \
+        instance_unconstrained_tvar \
         inference_test \
         inference_test_2 \
         lambda_multi_constraint_same_tvar \
@@ -52,6 +53,7 @@
 MCFLAGS-unqualified_method = --intermodule-optimization
 MCFLAGS-unqualified_method2 = --intermodule-optimization
 MCFLAGS-unqualified_method3 = --intermodule-optimization
+MCFLAGS-instance_unconstrained_tvar = --no-user-guided-type-specialisation
 
 #-----------------------------------------------------------------------------#
 

New File: compiler/notes/type_class_transformation.html
===================================================================
<html>
<head>
<title>
	The Type Class Transformation
</title>
</head>

<body
	bgcolor="#ffffff"
	text="#000000"
>

<hr>
<!-------------------------->

This document describes
the transformation that the compiler does to implement type classes.

<hr>
<!-------------------------->

<h2> Tranformation of code using type classes </h2>

Every predicate which has a typeclass constraint is given an extra
argument for every constraint in the predicate's type declaration.
The argument is the "dictionary", or "typeclass_info" for the typeclass.
The dictionary contains pointers to each of the class methods.
<p>

Representation of a typeclass_info:
The typeclass_info is represented in two parts (the typeclass_info
itself, and a base_typeclass_info), in a similar fashion to the
type_info being represented in two parts (the type_info and the
type_ctor_info).
<p>

The base_typeclass_info contains:
<UL>
	  <LI> the sum of the number of constraints on the instance decl. 
	  and the number of unconstrained type variables 
	  from the head of the instance decl. (`n1')
	  <LI> the number of unconstrained type variables 
	  from the head of the instance decl. (`n2')
	  <LI> the number of constraints on the typeclass decl. (`n3')
	  <LI> the number of parameters (type variables) from 
	         the typeclass decl. (`n4')
	  <LI> the number of methods from the typeclass decl. (`n5')
	  <LI> pointer to method #1
	  <LI> ...
	  <LI> pointer to method #n5
</UL>
<p>

The typeclass_info contains:
<UL>
	  <LI> a pointer to the base typeclass info
	  <LI> type info for unconstrained type var #1 from the instance decl
	  <LI> ...
	  <LI> type info for unconstrained type var #(n1-n2) from the 
	  instance decl
	  <LI> typeclass info #1 for constraint on instance decl
	  <LI> ...
	  <LI> typeclass info #n2 for constraint on instance decl
	  <LI> typeclass info for superclass #1
	  <LI> ...
	  <LI> typeclass info for superclass #n3
	  <LI> type info #1 
	  <LI> ...
	  <LI> type info #n4
</UL>
<p>

The base_typeclass_info is produced statically, and there is one for
each instance declaration. For each constraint on the instance
declaration, the corresponding typeclass_info is stored in the second
part.
<p>

eg. for the following program:
<p>

<pre>
:- typeclass foo(T) where [...].
:- instance  foo(int) where [...].
:- instance  foo(list(T)) <= foo(T) where [...].
</pre>

The typeclass_info for foo(int) is:
<UL>
	<LI>The base_typeclass_info:
	<UL>
	  <LI> 0 (there are no unconstrained type variables and no constraints)
	  <LI> 0 (there are no constraints on the instance decl)
	  <LI> 0 (there are no constraints on the typeclass decl)
	  <LI> 1 (this is a single-parameter type class)
	  <LI> n5 (the number of methods)
	  <LI> pointer to method #1
	  <LI> ...
	  <LI> pointer to method #n5
	</UL>

	<LI>The typeclass_info:
	<UL>
	  <LI> a pointer to the base typeclass info
	  <LI> type_info for int
	</UL>
</UL>

The typeclass_info for foo(list(T)) is:
<UL>
	<LI>The base_typeclass_info:
	<UL>
	  <LI> 1 (no unconstrained tvars, 1 constraint on the instance decl)
	  <LI> 1 (there is 1 constraint on the instance decl)
	  <LI> 0 (there are no constraints on the typeclass decl)
	  <LI> 1 (this is a single-parameter type class)
	  <LI> n5 (the number of methods)
	  <LI> pointer to method #1
	  <LI> ...
	  <LI> pointer to method #n5
	</UL>

	<LI>The typeclass_info contains:
	<UL>
	  <LI> a pointer to the base typeclass info
	  <LI> typeclass info for foo(T)
	  <LI> type_info for list(T)
	</UL>
</UL>

If the "T" for the list is known, the whole typeclass_info will be static
data. When we do not know until runtime, the typeclass_info is constructed
dynamically.
<p>

<H3> Example of transformation </H3>

Take the following code as an example (assuming the declarations above),
ignoring the requirement for super-homogeneous form for clarity:
<p>

<pre>
:- pred p(T1) <= foo(T1).
:- pred q(T2, T3) <= foo(T2), bar(T3).
:- pred r(T4, T5) <= foo(T4).

p(X) :- q([X], 0), r(1, 0).
</pre>

We add an extra argument for each type class constraint, and one
argument for each unconstrained type variable.
<p>

<pre>
:- pred p(typeclass_info(foo(T1)), T1).
:- pred q(typeclass_info(foo(T2)), typeclass_info(bar(T3)), T2, T3).
:- pred r(typeclass_info(foo(T4)), type_info(T5), T4, T5).
</pre>

We transform the body of p to this:
<pre>
p(TypeClassInfoT1, X) :-
	BaseTypeClassInfoT2 = base_typeclass_info(
		1,
		1,
		0,
		1,
		n5, (ie. the number of methods)
		...
		... (The methods for the foo class from the list
		...  instance)
		...
		),
	TypeClassInfoT2 = typeclass_info(
		BaseTypeClassInfoT2,
		TypeClassInfoT1,
		<type_info for list(T1)>),
	BaseTypeClassInfoT3 = base_typeclass_info(
		0,
		0,
		0,  (presuming bar has no superclasses)
		1,
		...
		... (The methods for the bar class from the int
		...  instance)
		...
		),
	TypeClassInfoT3 = typeclass_info(
		BaseTypeClassInfoT3,
		<type_info for int>),
	q(TypeClassInfoT2, TypeClassInfoT3, [X], 0),
	BaseTypeClassInfoT4 = baseclass_type_info(
		0,
		0,
		0,
		1,
		...
		... (The methods for the foo class from the int
		...  instance)
		...
		),
	TypeClassInfoT4 = typeclass_info(
		BaseTypeClassInfoT4,
		<type_info for int>),
	r(TypeClassInfoT4, <type_info for int>, X, 0).
</pre>
<p>

<hr>
<!-------------------------->
<hr>
<!-------------------------->
Last update was $Date: 1997/10/30 08:33:01 $ by $Author: zs $@cs.mu.oz.au. <br>
</body>
</html>

New File: tests/hard_coded/typeclasses/instance_unconstrained_tvar.exp
===================================================================
[1, 2, 3]

New File: tests/hard_coded/typeclasses/instance_unconstrained_tvar.m
===================================================================
:- module instance_unconstrained_tvar.

:- interface.

:- import_module io, list.

:- pred main(io__state::di, io__state::uo) is det.

:- typeclass p(T) where [
	pred m(T, io__state, io__state),
	mode m(in, di, uo) is det
].

:- instance p(list(T)) where [
	pred(m/3) is io__write
].

:- implementation.

main -->
	m([1,2,3]),
	io__nl.


dgj
-- 
David Jeffery (dgj at cs.mu.oz.au) | If your thesis is utterly vacuous
PhD student,                    | Use first-order predicate calculus.
Dept. of Comp. Sci. & Soft. Eng.|     With sufficient formality
The University of Melbourne     |     The sheerist banality
Australia                       | Will be hailed by the critics: "Miraculous!"
                                |     -- Anon.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------



More information about the developers mailing list