[m-dev.] for review: reordering for existential types [1]

[David Glen JEFFERY]

On 11-Jun-1999, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> 
> If anyone wants review this now, I'd appreciate their comments.

I realise you've probably already committed this to the branch, but I'll review
all your diffs now anyway. 

> --------------------
> 
> Estimated hours taken: 80
> 
> Change the order of the passes so that polymorphism comes before
> mode analysis.  This is necessary so that mode analysis can properly
> reorder code involving existential types.

When this gets merged onto the main branch, you will probably want a bit more
of an explanation here about what this diff is actually trying to achieve.

> compiler/notes/compiler_design.html:
> 	Document the new pass ordering.
> 
> compiler/mercury_compile.m:
> 	Invoke polymorphism.m before mode-checking.
> 	Invoke lambda.m where polymorphism used to be invoked,
> 	since polymorphism no longer invokes lambda.m now.
> 
> compiler/post_typecheck.m:
> 	Don't invoke copy_clauses_to_procs, because that is done by
> 	polymorphism.m now.
> 
> compiler/polymorphism.m:
> 	Don't invoke lambda.m, because that is done by mercury_compile.m now.
> 	Delete the code for calculating the typeclass constraints
> 	on lambda expressions -- this is now done in lambda.m.
> 
> 	Change this pass so that it now processes the clauses_info
> 	and the proc_info, calling copy_clause_to_proc for each procedure,
> 	rather than just processing the proc_infos.  This is needed so
> 	that unify_proc__request_proc can copy the clauses_info into the
> 	proc_info when creating new modes, without needing to rerun
> 	polymorphism (the polymorphism pass was not designed to be rerun).
> 
> 	Don't bother setting up the instmap_delta or determinism fields
> 	in the goal_info, since they will be computed by later passes
> 	(mode analysis and determinism analysis) now.
> 
> 	Add code to convert function calls into predicate calls
> 	(and higher-order function calls into higher-order predicate calls),
> 	adapted from the code to do that in modecheck_unify.m.
> 	Likewise add code to convert higher-order terms into
> 	lambda expressions.
> 
> 	Don't convert complicated unifications into procedure calls,
> 	since at this point in the complication we don't yet know whether
> 	var-var unifications are complicated unifications or assignments.
> 	Instead, just compute the type_infos that would be needed if the
> 	unification does turn out to be a complicated unification, and
> 	save this information in the HLDS for use by quantification.m
> 	and modecheck_unify.m.
> 
> 	Store the pred_info rather than just the pred_name in the
> 	poly_info.  Delete the aditi_owner and pred_markers fields from
> 	the poly_info, since they are no longer needed.
> 
> 	Rename init_poly_info as create_poly_info, to improve consistency
> 	with {pred,proc}_info_{init,create}.  Create a new init_poly_info
> 	function with a slightly different interface (it takes a
> 	clauses_info rather than a proc_info).
> 
> compiler/magic.m:
> 	s/init_poly_info/create_poly_info/
> 
> compiler/simplify.m:
> 	Convert complicated unifications into procedure calls.
> 
> 	Re-enable the optimization of replacing goals with no output
> 	variables with `true', since it should work OK even for
> 	existentially type predicates now that the polymorphism pass
> 	comes before simplify.m.
> 
> compiler/lambda.m:
> 	Add lambda__process_module for processing a whole module.
> 	Calculate the typeclass constraints on lambda expressions
> 	properly, using code adapted from polymorphism.m.
> 
> compiler/hlds_goal.m:
> 	Add new field to the `complicated_unify' functor to hold the
> 	type_info variables needed for a complicated unification,
> 	so that these can be set by polymorphism.m and used
> 	by modecheck_unify.m and quantification.
> 
> compiler/quantification.m:
> 	Include the new type_info variables field in the nonlocals for a
> 	complicated unify.
> 
> compiler/modecheck_unify.m:
> 	Delete the code to convert function calls into predicate
> 	calls, since that is now done by polymorphism.m.
> 
> 	Change create_var_var_unification so that it fills in the new
> 	type_info vars field properly.
> 
> 	Make categorize_unify_var_var local rather than exported,
> 	because it is not used outside this module, and because
> 	I had to change the interface slightly so that it preserves
> 	the value of the new field.
> 
> 	Split the checking of complicated unifications in
> 	categorize_unify_var_var into a new predicate
> 	modecheck_complicated_unify.
> 
> 	Add code to check that the type_info vars for complicated unifies
> 	(which it obtains from the new field) are ground.
> 
> compiler/modes.m:
> 	Don't try to modecheck typeclass methods, because they're created
> 	already mode-correct, and because the code to modecheck them
> 	has not been written (modecheck_goal_expr just calls error/1).
> 	Previously, typeclass methods didn't exist at mode analysis time,
> 	since they're created by polymorphism.m, but now they do exist at
> 	mode analysis time and so we have to explicitly check for them.
> 
> compiler/unify_proc.m:
> 	When computing modes for new unification procedures, make sure
> 	that we add extra modes for any typeinfos needed, if the type
> 	is polymorphic.
> 
> compiler/hlds_out.m
> 	Add code to print the new field of complicated_unifies.
> 
> compiler/bytecode_gen.m:
> compiler/code_util.m:
> compiler/common.m:
> compiler/dependency_graph.m:
> compiler/det_analysis.m:
> compiler/follow_code.m:
> compiler/follow_vars.m:
> compiler/goal_util.m:
> compiler/higher_order.m:
> compiler/hlds_goal.m:
> compiler/live_vars.m:
> compiler/make_hlds.m:
> compiler/mercury_to_c.m:
> compiler/modecheck_unify.m:
> compiler/pd_cost.m:
> compiler/polymorphism.m:
> compiler/rl_exprn.m:
> compiler/rl_key.m:
> compiler/simplify.m:
> compiler/term_traversal.m:
> compiler/unify_gen.m:
> compiler/unused_args.m:
> 	Trivial changes to handle the new field of complicated_unifies.
> 
> compiler/hlds_pred.m:
> 	Define and use typedefs `type_info_varmap', `type_class_info_varmap',
> 	and `constraint_proof_map', rather than duplicating complicated
> 	map(...) types everywhere.
> 
> 	Add two new fields to the clauses_info data structure:
> 	a type_info_varmap and a type_class_info_varmap.
> 	Define access predicates for the clauses_info data structure.
> 	Add type_info_varmap and type_class_info_varmap as extra
> 	arguments to proc_info_set_body.
> 
> compiler/check_typeclass.m:
> compiler/clause_to_proc.m:
> compiler/dead_proc_elim.m:
> compiler/higher_order.m:
> compiler/hlds_out.m:
> compiler/hlds_pred.m:
> compiler/intermod.m:
> compiler/make_hlds.m:
> compiler/mercury_to_c.m:
> compiler/modes.m:
> compiler/polymorphism.m:
> compiler/post_typecheck.m:
> compiler/purity.m:
> compiler/typecheck.m:
> compiler/unify_proc.m:
> 	Trivial changes to handle the two new fields of clauses_info.
> 	Change many places to use the the access predicates to access
> 	fields of the clauses_info rather than accessing them directly. 
> 
> compiler/purity.m:
> 	Fix some non-standard layout to match our usual coding conventions.
> 
> XXX TODO:
> 
> 	- termination analysis doesn't work; probably some mixup
> 	  regarding whether or not the pragmas in the .opt and
> 	  .trans_opt files are supposed to have the type_infos
> 	  included or not.
> 
> 	- fixup error messages (argument numbers offset)
> 
> 	- quite a few test cases are failing

> Index: compiler/hlds_goal.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/hlds_goal.m,v
> retrieving revision 1.59
> diff -u -r1.59 hlds_goal.m
> --- hlds_goal.m	1999/04/23 01:02:41	1.59
> +++ hlds_goal.m	1999/06/10 14:11:30
> @@ -310,7 +310,19 @@
>  
>  	;	complicated_unify(
>  			uni_mode,	% The mode of the unification.
> -			can_fail	% Whether or not it could possibly fail
> +			can_fail,	% Whether or not it could possibly fail
> +			list(prog_var)	% The type_info variables needed
> +					% by this unification, if ends up

s/if ends/if it ends/

BTW, it isn't that obvious why a complicated unification would require type
infos, so you might like to explain this further somewhere.

> Index: compiler/lambda.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/lambda.m,v
> retrieving revision 1.49
> diff -u -r1.49 lambda.m
> --- lambda.m	1999/06/01 09:43:53	1.49
> +++ lambda.m	1999/06/08 05:50:06

> @@ -117,6 +120,20 @@
>  
>  	% This whole section just traverses the module structure.
>  
> +lambda__process_module(ModuleInfo0, ModuleInfo) :-
> +	module_info_predids(ModuleInfo0, PredIds),
> +	lambda__process_preds(PredIds, ModuleInfo0, ModuleInfo1),
> +	% Need update the dependency graph to include the lambda predicates. 
> +	module_info_clobber_dependency_info(ModuleInfo1, ModuleInfo).

I assume that by clobbering the dependency graph, some later pass fills it
in again. Is that right?

> +	map__keys(TCVarMap, AllConstraints),
> +	map__apply_to_list(Vars, VarTypes, LambdaVarTypes),
> +	list__map(type_util__vars, LambdaVarTypes, LambdaTypeVarsList),
> +	list__condense(LambdaTypeVarsList, LambdaTypeVars),
> +	list__filter(lambda__constraint_contains_vars(LambdaTypeVars), 
> +		AllConstraints, UnivConstraints),
> +	Constraints = constraints(UnivConstraints, []),

This is conservative, right? This will give you all the constraints on the
variables in the lambda expression, regardless of whether the constraints
are generated inside or outside the expression.

I will review the rest of the parts of this diff soon.


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
--------------------------------------------------------------------------