[m-dev.] For review: compiler support for parallel conjunction

[Fergus Henderson]

Thomas Charles CONWAY, you wrote:
> +:- type slot_contents 
> +	--->	ticket			% a ticket (trail pointer)
> +	;	ticket_counter		% a copy of the ticket counter
> +	;	trace_data
> +	;	sync_term
> +	;	lval(lval).

Please document `sync_term'.

> +det_infer_par_conj([], _InstMap0, _SolnContext, _DetInfo, [], det, []).
> +det_infer_par_conj([Goal0 | Goals0], InstMap0, SolnContext, DetInfo, 
> +		[Goal | Goals], Detism, Msgs) :-
> +
> +	det_infer_goal(Goal0, InstMap0, SolnContext, DetInfo,
> +			Goal, DetismA, MsgsA),
> +	
> +	det_infer_par_conj(Goals0, InstMap0, SolnContext, DetInfo,
> +			Goals, DetismB, MsgsB),
> +	determinism_components(DetismB, CanFailB, MaxSolnsB),
> +
> +	determinism_components(DetismA, CanFailA, MaxSolnsA),
> +
> +	det_conjunction_canfail(CanFailA, CanFailB, CanFail),
> +	det_conjunction_maxsoln(MaxSolnsA, MaxSolnsB, MaxSolns),
> +	determinism_components(Detism, CanFail, MaxSolns),
>  	list__append(MsgsA, MsgsB, Msgs).

The code would be easier to read if it was ordered more consistently.
Either put the two calls to determinism_compenents together,
with the one for DetismA first, or put the call to
determinism_components(DetismA, ...) after the call to det_infer_goal.

> +det_report_msg(par_conj_not_det(InferredDetism, GoalInfo), _) -->
> +	{ goal_info_get_context(GoalInfo, Context) },
> +	prog_out__write_context(Context),
> +	{ determinism_components(InferredDetism, CanFail, MaxSoln) },
> +	(
> +		{ CanFail \= cannot_fail }
> +	->
> +		io__write_string("Error: parallel conjunct may fail.\n")
> +	;
> +		{ MaxSoln = at_most_many }
> +	->
> +		prog_out__write_context(Context),
> +		io__write_string("Error: parallel conjunct may have multiple solutions.\n")
> +	;
> +		{ error("strange determinism error for parallel conjunction") }
> +	),
> +	prog_out__write_context(Context),
> +	io__write_string(
> +		"  The current implementation supports only single-solutioned\n"
> +	),
> +	prog_out__write_context(Context),
> +	io__write_string("  non-failing parallel conjunctions.\n").

It is true that in English, any word can be verbed, but I think
"single-solution" would be better than "single-solutioned" here.

Also, shouldn't you report which part of the conjunct can fail
or can have multiple solutions?

> diff -u -r1.42 hlds_goal.m
> --- hlds_goal.m	1997/10/13 08:09:41	1.42
> +++ hlds_goal.m	1997/10/17 04:20:17
> @@ -166,7 +166,15 @@
>  			extra_pragma_info
>  					% Extra information for model_non
>  					% pragma_c_codes; none for others.
> -		).
> +		)
> +
> +	;	par_conj(hlds_goals, store_map)
> +					% parallel conjunction
> +					% The store_map specifies the locations
> +					% in which live variables should be
> +					% stored at the start of the parallel
> +					% conjunction.

At the start?  Are you sure that's correct?

> +	% hlds_out__write_disj is used to write both disjunctions and
> +	% parallel conjunctions.

I think you should rename it as hlds_out__write_goal_list or something
like that.

> +instmap__unify(NonLocals, InstMapList, ModeInfo0, ModeInfo) :-
> +	(
> +		list__member(unreachable - _, InstMapList)
> +	->
> +		mode_info_set_instmap(unreachable, ModeInfo0, ModeInfo)
> +	;
> +		InstMapList = [InstMap - _]
> +	->
> +		mode_info_set_instmap(InstMap, ModeInfo0, ModeInfo)
> +	;
> +		InstMapList = [InstMap0 - _|InstMapList1],
> +		InstMap0 = reachable(InstMapping0)
> +	->
> +		mode_info_get_module_info(ModeInfo0, ModuleInfo0),
> +		set__to_sorted_list(NonLocals, NonLocalsList),
> +		instmap__unify_2(NonLocalsList, InstMap0, InstMapList1,
> +			ModuleInfo0, InstMapping0, ModuleInfo,
> +			InstMapping, ErrorList),
> +		mode_info_set_module_info(ModeInfo0, ModuleInfo, ModeInfo1),
> +		( ErrorList = [FirstError | _] ->
> +			FirstError = Var - _,
> +			set__singleton_set(WaitingVars, Var),
> +			mode_info_error(WaitingVars,
> +				mode_error_par_conj(ErrorList),
> +				ModeInfo1, ModeInfo2)
> +		;
> +			ModeInfo2 = ModeInfo1
> +		),
> +		mode_info_set_instmap(reachable(InstMapping),
> +			ModeInfo2, ModeInfo)
> +	;
> +		ModeInfo = ModeInfo0
> +	).

Please add some comments here.
Procedures that are longer than about 5 lines long tend to be
much easier to read if you break them up into smaller parts
separated by comments describing what each part does.

> +	% instmap__unify_2(Vars, InitialInstMap, InstMaps, ModuleInfo,
> +	%		ErrorList):
> +	%       Let `ErrorList' be the list of variables in `Vars' for
> +	%       there are two instmaps in `InstMaps' for which the inst
> +	%       the variable is incompatible.

... for _which_ there are two instmaps ...
... the inst _of_ the variable ...

> +instmap__unify_2([], _, _, ModuleInfo, InstMap, ModuleInfo, InstMap, []).
> +instmap__unify_2([Var|Vars], InitialInstMap, InstMapList, ModuleInfo0, InstMap0,
> +			ModuleInfo, InstMap, ErrorList) :-
> +	instmap__unify_2(Vars, InitialInstMap, InstMapList, ModuleInfo0,
> +			InstMap0, ModuleInfo1, InstMap1, ErrorList1),
> +	instmap__lookup_var(InitialInstMap, Var, InitialVarInst),
> +	instmap__unify_var(InstMapList, Var, [], Insts, InitialVarInst, Inst,
> +		ModuleInfo1, ModuleInfo, no, Error),
> +	( Error = yes ->
> +		ErrorList = [Var - Insts | ErrorList1],
> +		map__set(InstMap1, Var, not_reached, InstMap)

Please add a comment explaining that line.

> +	% instmap__unify_var(InstMaps, Var, InitialInstMap, ModuleInfo,
> +	%		Insts, Error):
> +	%       Let `Insts' be the list of the inst of `Var' in the
> +	%       corresponding `InstMaps'.  Let `Error' be yes iff
> +	%       there are two instmaps for which the inst of `Var'
> +	%       is incompatible.

The following might be a little clearer:

	%       Let `Insts' be the list containing the inst of `Var'
	%	in each of the corresponding `InstMaps'.  ...

> +build_live_sets_in_goal_2(par_conj(Goals0, _SM), Liveness0, ResumeVars0,
> +		LiveSets0, GoalInfo, ModuleInfo, ProcInfo, Liveness,
> +		ResumeVars, LiveSets) :-
> +	goal_info_get_nonlocals(GoalInfo, NonLocals),
> +	set__union(NonLocals, Liveness0, LiveSet),
> +		% we insert all the union of the live vars and the nonlocals
> +		% each variables is one of:
> +		% 	bound and should be saved;
> +		%	an output of the par conj, so we need a stackslot
> +		%		for the reference;
> +		%	is mentioned, but unused and we wasted a stack slot.

For me, this comment raised more questions than it answered.
Could you try rephrasing it more clearly?

> +		% XXX Value numbering doesn't handle fork [yet] so
> +		% set DontValueNumber to yes.
...
> +		% XXX Value numbering doesn't handle join_and_terminate [yet] so
> +		% set DontValueNumber to yes.
...
> +		% XXX Value numbering doesn't handle join_and_continue [yet] so
> +		% set DontValueNumber to yes.

This is not a good solution...

> +	;	join_and_terminate(lval)
> +			% Signal that this thread of execution has finished in
> +			% the current parallel conjunction, then terminate it.
> +			% The synchronisation term is pointed to by the
> +			% given lval.

Is the lval really a pointer??

I think "is specified by" would be clearer than "is pointed to by".

Or, if the argument really is a pointer, it should be an rval, not an lval.

> +	;	join_and_continue(lval, label)
> +			% Signal that this thread of execution has finished
> +			% in the current parallel conjunction, then branch to
> +			% the given label. The synchronisation
> +			% term is pointed to by the given lval.

Ditto.

> -	% Locate all the labels which are the continutation labels for calls
> -	% or nondet disjunctions, and store them in ContLabelSet.
> +	% Locate all the labels which are the continutation labels for calls,
> +	% nondet disjunctions forks or joins, and store them in ContLabelSet.

s/continutation/continuation/
s/ forks/, forks/


> +	;	mode_error_bind_var(var, inst, inst, lock_context)
>  			% attempt to bind a non-local variable inside
> +			% a negated context, or attempt to re-bind a variable
> +			% in a parallel conjunct
...
> +	;	mode_error_parallel_var(var, inst, inst)
> +			% attempt to bind a non-local variable that has already
> +			% been bound in another parallel conjunct.
> +	.

I don't understand -- what is the difference between these two?
Are they both used?  Which is used when?

> +:- pred report_mode_error_par_conj(mode_info, merge_errors,
> +				io__state, io__state).
> +:- mode report_mode_error_par_conj(mode_info_no_io, in, di, uo) is det.
> +
> +report_mode_error_par_conj(ModeInfo, ErrorList) -->
> +	{ mode_info_get_context(ModeInfo, Context) },
> +	mode_info_write_context(ModeInfo),
> +	prog_out__write_context(Context),
> +	io__write_string("  incompatible bindings in parallel conjunction.\n"),
> +	write_merge_error_list(ErrorList, ModeInfo).

Every error message should include an indication of what sort of error
it is.  Hence that should be

	io__write_string("  mode error: incompatible bindings ...

> +report_mode_error_parallel_var(ModeInfo, Var, _VarInst, _Inst) -->
> +	{ mode_info_get_context(ModeInfo, Context) },
> +	{ mode_info_get_varset(ModeInfo, VarSet) },
> +	mode_info_write_context(ModeInfo),
> +	prog_out__write_context(Context),
> +	io__write_string("  error: attempt to bind a variable already bound in another\n"),
> +	prog_out__write_context(Context),
> +	io__write_string("  parallel conjunct.\n"),

s/error/mode error/

Also wrap the line a few words earlier.

> +	prog_out__write_context(Context),
> +	io__write_string("  the variable concerned was `"),

s/the/The/

> +:- type lock_context
> +		--->	negation
> +		;	if_then_else
> +		;	par_conj
> +		.

Hmm, I think there should be another alternative, `lambda_goal'.

> --- modecheck_unify.m	1997/10/13 10:24:18	1.24
> +++ modecheck_unify.m	1997/10/17 04:20:31
> @@ -381,10 +381,11 @@
>  	% lock the non-locals
>  	% (a lambda goal is not allowed to bind any of the non-local
>  	% variables, since it could get called more than once)
> +	% `negation' as the locked_var_context is a place holder.
>  	Goal0 = _ - GoalInfo0,
>  	goal_info_get_nonlocals(GoalInfo0, NonLocals0),
>  	set__delete_list(NonLocals0, Vars, NonLocals),
> -	mode_info_lock_vars(NonLocals, ModeInfo2, ModeInfo3),
> +	mode_info_lock_vars(NonLocals, negation, ModeInfo2, ModeInfo3),

You should use `lambda_goal' here rather than `negation'.

> Index: compiler/modes.m
> ===================================================================
> RCS file: /home/staff/zs/imp/mercury/compiler/modes.m,v
> retrieving revision 1.205
> diff -u -r1.205 modes.m
> --- modes.m	1997/09/15 21:12:24	1.205
> +++ modes.m	1997/09/16 00:14:30
> @@ -711,6 +711,34 @@
>  	),
>  	mode_checkpoint(exit, "conj").
>  
> +	% To modecheck a parallel conjunction, we modecheck each
> +	% conjunct independently (just like for disjunctions).
> +	% To make sure that we don't try to bind a variable more than
> +	% once (by binding it in more than one conjunct), we maintain a
> +	% datastructure that keeps track of three things:
> +	%	the set of variables that are nonlocal to the conjuncts
> +	%	(which may be a superset of the nonlocals of the par_conj
> +	%	as a whole);
> +	%	the set of nonlocal variables that have been bound in the
> +	%	current conjunct; and
> +	%	the set of variables that were bound in previous conjuncts.
> +	% When binding a variable, we check that it wasn't in the set of
> +	% variables bound in other conjuncts, and we add it to the set of
> +	% variables bound in this conjunct.
> +	% At the end of the conjunct, we add the set of variables bound in
> +	% this conjunct to the set of variables bound in previous conjuncts
> +	% and set the set of variables bound in the current conjunct to
> +	% empty.

Hmm, what about examples like

	:- pred p(out) is det.
	p(X) :-
		(
			X = a,
			...
			error("blah")
		&
			X = b,
			...
		).

?

> Index: library/nc_builtin.nl
> ===================================================================
> RCS file: /home/staff/zs/imp/mercury/library/nc_builtin.nl,v
> retrieving revision 1.15
> diff -u -r1.15 nc_builtin.nl
> --- nc_builtin.nl	1997/07/27 15:06:59	1.15
> +++ nc_builtin.nl	1997/09/08 22:54:57
> @@ -50,6 +50,8 @@
>  :- op(1179, xfy, (--->)).
>  :- op(1175, xfx, (::)).
>  
> +:- op(1025, xfy, (&)).
> +
>  :- op(950, fxy, (lambda)).
>  
>  :- op(400, yfx, (rem)).
> Index: library/sp_builtin.nl
> ===================================================================
> RCS file: /home/staff/zs/imp/mercury/library/sp_builtin.nl,v
> retrieving revision 1.13
> diff -u -r1.13 sp_builtin.nl
> --- sp_builtin.nl	1997/07/27 15:07:13	1.13
> +++ sp_builtin.nl	1997/09/08 22:54:57
> @@ -53,6 +53,7 @@
>  :- op(1199, fx, (mode)).
>  :- op(1199, fx, (inst)).
>  :- op(1179, xfy, (--->)).
> +:- op(1025, xfy, (&)).
>  :- op(975, xfx, ('::')).
>  :- op(700, xfx, ( \= ) ).
>  :- op(500, fx, ( \ ) ).

You also need to modify library/ops.m and compiler/mercury_to_mercury.m.

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