[m-dev.] for review: accumulator introduction

[Fergus Henderson]

On 15-Jun-1999, Peter Ross <petdr at cs.mu.OZ.AU> wrote:
> On 04-Jun-1999, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> > 
> > > Add a new pass to the compiler, that attempts to introduce accumulators
> > > into a procedure so as to make that procedure tail recursive.
> >  
> > A test case or two in tests/general would be nice.
>
> I have lots of test cases, I will whittle them down to a few and post
> them for review in the next couple of days.

Great.  Don't whittle them down too hard -- when in doubt, it's much better
to have too many test cases than too few ;-)

> > > +	% If the earlier goal changes the instatiatedness of a variable

Here's one that I just noticed now:

	s/instatiatedness/instantiatedness/
			       ^    
> > > +	% accumulator__orig_base_case
> > > +	%
> > > +	% Determine the base case of the original goal.
> > > +	%
> > > +:- pred accumulator__orig_base_case(hlds_goals::in, hlds_goal::out) is det.
> > > +
> > > +accumulator__orig_base_case(BaseGoalList, BaseGoal) :-
> > > +	calculate_goal_info(conj(BaseGoalList), BaseGoal).
> > 
> > Will the computed goal_info be any different to that from the original
> > goal? If not, it would be clearer to just use the old one.
> 
> No it will not be any different, but it is just easier to rebuild it
> then to keep the original goalinfo around.  If you think the change is
> really necessary, I will make it.

No, but I think it would be worth adding a comment here explaining this.

> > > +:- pred calculate_goal_info(hlds_goal_expr::in, hlds_goal::out) is det.
> > > +
> > > +calculate_goal_info(GoalExpr, GoalExpr - GoalInfo) :-
> > > +	(
> > > +		GoalExpr = conj(GoalList)
> > > +	->
...
> > > +	;
> > > +		error("calculate_goal_info: not a conj.")
> > > +	).
> > 
> > All the uses of this predicate pass in a conj(Goals).
> > Would it be better just to pass in Goals, and avoid the error check.
> > This should probably go in hlds_goal.m.
>
> Well I just want to make sure that I do always pass in a conjunction.
> XXX come back to this.

OK, don't forget to come back to that one ;-)

> +++ accumulator.m	1999/06/15 02:35:40
> +% Currently which goals are associative is hard-wired into this module,
> +% at a later date we should add the ability to add pragmas to supply
> +% this information.

I suggest

	s/which goals/the knowledge of which goals/
	s/,/;/

> +% Another subtlty is that making the code tail recursive doesn't

s/subtlty/subtlety/

> +% necessarily improve the efficiency of code.  Note that the call 
> +% to compose in the accumulator version of the code has Hs located
> +% in a different position.  For append(in, in, out) it is the first
> +% argument which controls the complexity of append.  So if the compose
> +% goal was append, the complexity of the predicate as a whole will
> +% change.  This problem is defeated by ensuring that only a variable
> +% that is a member of Hs ends up in the first position of append,
> +% because in general the variables in Hs are smaller then those in As.

I suggest s/defeated/dealt with/

> @@ -279,7 +312,10 @@
>  		(
>  			accumulator__split_recursive_case(PredId, ProcId,
>  					InitialInstMap, ModuleInfo,
> -					GoalAList, Rec0)
> +					GoalAList, Rec0),
> +			\+ accumulator__split_recursive_case(PredId, ProcId,
> +					InitialInstMap, ModuleInfo,
> +					GoalBList, _)
>  		->
>  			Type = switch_rec_base,
>  			Base = base(GoalBList),
> @@ -287,7 +323,10 @@
>  		;
>  			accumulator__split_recursive_case(PredId, ProcId,
>  					InitialInstMap, ModuleInfo,
> -					GoalBList, Rec0)
> +					GoalBList, Rec0),
> +			\+ accumulator__split_recursive_case(PredId, ProcId,
> +					InitialInstMap, ModuleInfo,
> +					GoalAList, _)

A comment here explaining the two negated calls would be helpful.

>  	%
> -	% accumulator__split_recursive_case(Gs, DP, P, C)
> +	% accumulator__split_recursive_case(PredId, ProcId, IM0, MI, Gs, R)
>  	%
>  	% Split the goals, Gs, which make up the recursive case into the
> -	% decompose and process list of goals, DP, and the compose
> -	% goals, C, and the recursive goal P.
> +	% decompose and process list of goals, the compose goals and the 
> +	% recursive goal and place the compenents in the rec_goal
> +	% structure, R.

s/compenets/components/

> @@ -531,6 +571,11 @@
>  	solutions(accumulator__split_goals(Goals, PredId, ProcId), Solns),
>  	Solns = [recursive(DP0, R, C0)],
>  	calculate_instmap(DP0, InitialInstMap, InitialInstMapBeforeR),
> +
> +		% Any goal which doesn't depend on the recursive call is
> +		% moved before the recursive call, this means that only
> +		% goals which contain dynamic variables are left after
> +		% the recursive call, simplifying the latter stages.

I suggest s/this means/because this means/

> @@ -593,16 +633,24 @@
>  move_goals(_StartGoal, _InstMapBeforeStartGoal, _ModuleInfo, [], [], []).
>  move_goals(StartGoal, InstMapBeforeStartGoal, ModuleInfo,
>  		[Goal|Goals], PreGoals, PostGoals) :-
> +
> +	StartGoal = _GoalExpr - GoalInfo,
> +	goal_info_get_instmap_delta(GoalInfo, InstMapDelta),
> +	instmap__apply_instmap_delta(InstMapBeforeStartGoal,
> +			InstMapDelta, InstMapBeforeGoal),
>  	(
> +		% XXX thread down the argument before commiting.
> +		FullyStrict = yes,
> +		goal_util__can_reorder_goals(ModuleInfo, FullyStrict,
> +				InstMapBeforeStartGoal, StartGoal,
> +				InstMapBeforeGoal, Goal)
> +		% goal_depends_on_earlier_goal_with_error_check(Goal, StartGoal,
> +		%		InstMapBeforeStartGoal, ModuleInfo)
>  		% goal_depends_on_earlier_goal(Goal, StartGoal)
>  	->

You probably want to fix that XXX, or at least make the comment a bit
more understandable.  The two commented out goals should also be either
deleted or explained.

> @@ -1591,8 +1491,19 @@
>  	mode_is_output(ModuleInfo, Out).
>  
>  /*
> -	XXX this no longer works.  We need to go back to my original code for
> -	this to work.
> +	XXX this no longer works, because set__insert isn't associative.
> +
> +	However set__insert obeys the following axiom, providing that you 
> +	use user-defined equality (set__equals), not structural equality 
> +	for S.
> +
> +		p(A, S0, SA), p(B, SA, S) <=>
> +			p(B, S0, SB), p(A, SB, S)
> +
> +	My previous attempt at this transformation handled this case 
> +	and I thought the current one did as well.  I was wrong.  I need
> +	to reintergrate my old code.

s/intergrate/integrate/

Apart from that, those changes look fine.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------