diff: typeclasses (final) [1/6]

[David Glen JEFFERY]

Hi,

Here is the full version of the changes to support type classes. I am going to
commit it now.

For the record, here's my log message:

--

Estimated hours taken: 500 or so

This change implements typeclasses. Included are the necessary changes to
the compiler, runtime and library.

compiler/typecheck.m:
	Typecheck the constraints on a pred by adding constraints for each
	call to a pred/func with constraints, and eliminating constraints
	by applying context reduction.

	While reducing the constraints, keep track of the proofs so that 
	polymorphism can produce the tyepclass_infos for eliminated 
	constraints.

compiler/polymorphism.m:
	Perform the source-to-source transformation which turns code with
	typeclass constraints into code without constraints, but with extra
	"typeclass_info", or "dictionary" parameters.

	Also, rather than always having a type_info directly for each type
	variable, sometimes the type_info is hidden inside a typeclass_info.

compiler/bytecode*.m:
	Insert some code to abort if bytecode generation is used when 
	typeclasses are used.
compiler/call_gen.m:
	Generate code for a class_method_call, which forms the body of a class
	method (by selecting the appropriate proc from the typeclass_info).
compiler/dead_proc_elim.m:
	Don't eliminate class methods if they are potentially used outside
	the module
compiler/hlds_data.m:
	Define data types to store:
		- the typeclass definitions
		- the instances of a class
		- "constraint_proof". ie. the proofs of redundancy of a
		  constraint. This info is used by polymorphism to construct the
		  typeclass_infos for a constraint.
		- the "base_tyepclass_info_constant", which is analagous the
		  the base_type_info_constant
compiler/hlds_data.m:
	Define the class_method_call goal. This goal is inserted into the
	body of class method procs, and is responsible for selecting the
	appropriate part of the typeclass_info to call.
compiler/hlds_data.m:
	Add the class table and instance table to the module_info.
compiler/hlds_out.m:
	Output info about base_typeclass_infos and class_method_calls
compiler/hlds_pred.m:
	Change the representation of the locations of type_infos from "var"
	to type_info_locn, which is either a var, or part of a typeclass_info,
	since now the typeclass_infos contain the type_infos for the type that
	they constrain.

	Add constraints to the pred_info.

	Add constraint_proofs to the pred_info (so that typeclass.m can 
	annotate the pred_info with the reasons that constraints were
	eliminated, so that polymorphism.m can in turn generate the
	typeclass_infos for the constraints).

	Add the "class_method" marker.

compiler/lambda.m:
	A feable attempt at adding class ontexts to lambda expressions, 
	untested and almost certainly not working.
compiler/llds_out.m:
	Output the code addresses for do_*det_class_method, and output 
	appropriately mangled symbol names for base_typeclass_infos.
compiler/make_hlds.m:
	Add constraints to the types on pred and func decls, and add
	class and instance declarations to the class_table and instance_table
	respectively.
compiler/mercury_compile.m:
	Add the check_typeclass pass.
compiler/mercury_to_mercury.m:
	Output constraints of pred and funcs, and output typeclass and instance
	declarations.
compiler/module_qual.m:
	Module qualify typeclass names in pred class contexts, and qualify the
	typeclass and instance decls themselves.
compiler/modules.m:
	Output typeclass declarations in the short interface too.
compiler/prog_data.m:
	Add the "typeclass" and "instance" items. Define the types to store
	information about the declarations, including class contexts on pred
	and func decls.
compiler/prog_io.m:
	Parse constraints on pred and func declarations.
compiler/prod_out.m:
	Output class contexts on pred and func decls.
compiler/type_util.m:
	Add preds to apply a substitution to a class_constraint, and to
	a list of class constraints. Add type_list_matches_exactly/2. Also
	add typeclass_info and base_typeclass_info as types which should not
	be optimised as no_tag types (seeing that we cheat a bit about their
	representation).
compiler/notes/compiler_design.html:
	Add notes on module qualification of class contexts. Needs expansion
	to include more stuff on typeclasses.
compiler/*.m:
	Various minor changes.

New Files:
compiler/base_typeclass_info.m:
	Produce one base_typeclass_info for each instance declaration.
compiler/prog_io_typeclass.m:
	Parse typeclass and instance declarations.
compiler/check_typeclass.m:
	Check the conformance of an instance declaration to the typeclass
	declaration, including building up a proof of how superclass
	constraints are satisfied so that polymorphism.m is able to construct
	the typeclass_info, including the superclass typeclass_infos.

library/mercury_builtin.m:
	Implement that base_typeclass_info and typeclass_info types, as
	well as the predicates type_info_from_typeclass_info/3 to extract
	a type_info from a typeclass_info, and superclass_from_typeclass_info/3
	for extracting superclasses.
library/ops.m:
	Add "typeclass" and "instance" as operators.
library/string.m:
	Add a (in, uo) mode for string__length/3. 

runtime/mercury_ho_call.c:
	Implement do_call_*det_class_method, which are the pieces of code
	responsible for extracting the correct code address from the
	typeclass_info, setting up the arguments correctly, then executing
	the code.
runtime/mercury_type_info.h:
	Macros for accessing the typeclass_info structure.



--


love and cuddles,
dgj
-- 
David Jeffery (dgj at cs.mu.oz.au) |  Marge: Did you just call everyone "chicken"?
MEngSc student,                 |  Homer: Noooo.  I swear on this Bible!
Department of Computer Science  |  Marge: That's not a Bible; that's a book of
University of Melbourne         |         carpet samples!
Australia                       |  Homer: Ooooh... Fuzzy.