[m-dev.] for review: independent AND parallelsim

[Fergus Henderson]

On 27-Apr-1998, Thomas Charles CONWAY <conway at cs.mu.OZ.AU> wrote:
> Index: compiler/hlds_out.m
...
> +hlds_out__write_goal_2(par_conj(List, _), ModuleInfo, VarSet, AppendVarnums,
> +		Indent, Follow, TypeQual) -->
> +	hlds_out__write_indent(Indent),
> +	( { List = [Goal | Goals] } ->
> +		io__write_string("( % parallel conjunction\n"),
> +		{ Indent1 is Indent + 1 },
> +		hlds_out__write_goal_a(Goal, ModuleInfo, VarSet, AppendVarnums,
> +			Indent1, "", TypeQual),
> +			% See comments at hlds_out__write_goal_list.
> +		hlds_out__write_goal_list(Goals, ModuleInfo, VarSet,
> +			AppendVarnums, Indent, "&", TypeQual),
> +		hlds_out__write_indent(Indent),
> +		io__write_string(")"),
> +		io__write_string(Follow),
> +		io__write_string("\n")
> +	;
> +		io__write_string("fail"),
> +		io__write_string(Follow),
> +		io__write_string("\n")
> +	).

It should be "true", not "fail".

But in fact it would be better if it output "/* parallel */ true",
so as to distinguish an empty parallel conjunction from an empty
sequential conjunction.

> +instmap__unify_var([], _, Insts, Insts, Inst, Inst, ModuleInfo, ModuleInfo,
> +		Error, Error).
> +instmap__unify_var([InstMap - Nonlocals| Rest], Var, InstList0, InstList,
> +		Inst0, Inst, ModuleInfo0, ModuleInfo, Error0, Error) :-
> +	(
> +		set__member(Var, Nonlocals)
> +	->
> +		instmap__lookup_var(InstMap, Var, VarInst),
> +		(
> +			% We unify the accumulated inst and the inst from the
> +			% given instmap - we don't care about the determinism.
> +			% Variable locking during mode analysis ensures that
> +			% there is a unique producer for each variable - whether
> +			% or not the unification may fail is up to determinism
> +			% analysis.
> +
> +			abstractly_unify_inst(live, Inst0, VarInst, fake_unify,
> +				ModuleInfo0, Inst1, _Det, ModuleInfo1)
> +		->
> +			Inst2 = Inst1,
> +			ModuleInfo2 = ModuleInfo1,
> +			Error1 = Error0
> +		;

I think the comment here, in particular "whether or not the unification may
fail is up to determinism analysis", is confusing and/or misleading.
There's no real unification, only a fake_unify, so what is it that
determinism analysis going to analyze?  I think the comment is a red herring.
How about you have another try at explaining it.

> +unify_instmapping_delta_2([], _, _, _, InstMapping, InstMapping,
> +		ModInfo, ModInfo).
> +unify_instmapping_delta_2([Var | Vars], InstMap, InstMappingA, InstMappingB,
> +			InstMapping0, InstMapping, ModuleInfo0, ModuleInfo) :-
> +	( map__search(InstMappingA, Var, InstA) ->
> +		( map__search(InstMappingB, Var, InstB) ->
> +			(
> +			% We unify the accumulated inst and the inst from the
> +			% given instmap - we don't care about the determinism.
> +			% Variable locking during mode analysis ensures that
> +			% there is a unique producer for each variable - whether
> +			% or not the unification may fail is up to determinism
> +			% analysis.
> +
> +				abstractly_unify_inst(live, InstA, InstB,
> +					fake_unify, ModuleInfo0, Inst, _Det,
> +					ModuleInfoPrime)

Ditto.

> Index: compiler/llds.m
> +	;	init_sync_term(lval, int)
> +			% Initialize a synchronization term.

What's the semantics of the arguments?

> +	;	fork(label, label, int)
> +			% Create a new context.
> +			% fork(Child, Parent, NumSlots) creates a new thread
> +			% which will start executing at Child, then execution
> +			% in the current context branches to Parent.

s/then/while/ ?

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

That sentence missing word. ;-)

> +	;	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 specified by the given lval.

Ditto.

> (See the documentation in par_conj_gen.m
> +			% and runtime/context.mod for further information about
> +			% synchronisation terms.)

There should be a similar pointer in the documentation for init_sync_term.

The pointer to runtime/context.mod is a dangling pointer, because
the file has been renamed.

> +output_instruction(fork(Child, Parent, Lval), _) -->
> +	io__write_string("\tfork_new_context("),
> +	output_label_as_code_addr(Child),
> +	io__write_string(", "),
> +	output_label_as_code_addr(Parent),
> +	io__write_string(", "),
> +	io__write_int(Lval),
> +	io__write_string(");\n").
> +
> +output_instruction(join_and_terminate(Lval), _) -->
> +	io__write_string("\tjoin_and_terminate("),
> +	output_lval(Lval),
> +	io__write_string(");\n").
> +
> +output_instruction(join_and_continue(Lval, Label), _) -->
> +	io__write_string("\tjoin_and_continue("),
> +	output_lval(Lval),
> +	io__write_string(", "),
> +	output_label_as_code_addr(Label),
> +	io__write_string(");\n").

The macros used here really ought to be prefixed by `MR_'...

> Index: compiler/mode_errors.m
> ===================================================================
> RCS file: /home/staff/zs/imp/mercury/compiler/mode_errors.m,v
> retrieving revision 1.57
> diff -u -r1.57 mode_errors.m
> --- mode_errors.m	1998/03/03 17:35:11	1.57
> +++ mode_errors.m	1998/03/11 04:50:12
> @@ -40,6 +40,9 @@
>  	--->	mode_error_disj(merge_context, merge_errors)
>  			% different arms of a disjunction result in
>  			% different insts for some non-local variables
> +	;	mode_error_par_conj(merge_errors)
> +			% different arms of a parallel conj result in
> +			% mutually exclusive bindings

What do you mean by mutually exclusive?
Which bindings are considered mutually exclusive?
Why is this an error?

>  	;	mode_error_bind_var(var_lock_reason, var, inst, inst)
>  			% attempt to bind a non-local variable inside
> -			% a negated context
> +			% 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.

Why are there two different ways of recording invalid variable bindings
in parallel conjuncts?

> +:- 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("  mode error: mutually exclusive bindings in parallel conjunction.\n"),
> +	write_merge_error_list(ErrorList, ModeInfo).

The error message here needs to explain why these bindings are not
allowed.

> +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("  mode error: attempt to bind a variable already bound\n"),
> +	prog_out__write_context(Context),
> +	io__write_string("  in anonther parallel conjunct.\n"),

s/anonther/another/

> +	prog_out__write_context(Context),
> +	io__write_string("  The variable concerned was `"),
> +	mercury_output_var(Var, VarSet, no),
> +	io__write_string("'.\n").

If --verbose-errors is specified, you should add

	The current Mercury implementation only supports _independant_
	and-parallelism.

to this error message.

> %-----------------------------------------------------------------------------%
> % Copyright (C) 1995 University of Melbourne.
> % This file may only be copied under the terms of the GNU General
> % Public License - see the file COPYING in the Mercury distribution.
> %---------------------------------------------------------------------------%
> %
> % File: par_conj.m:

The copyright date looks wrong.

> % Main authors: conway.
> %
> % The predicates of this module generate code for parallel conjunctions.
> %
> %---------------------------------------------------------------------------%
> %
> % Notes on parallel conjunction:
> %
> % A parallel conjunction (A & B) denotes that the goals `A' and `B' should
> % be executed concurrently. Ideally, parallel conjunction should have exactly
> % the same declarative semantics as normal conjunction; in practice this is
> % not quite the case for a couple of reasons:

No, it *is* the case.  The reasons you give below talk about
differences in (1) legality and (2) operational semantics, but not
about declarative semantics.

So, I suggest you reword that, perhaps as follows:

    % A parallel conjunction (A & B) denotes that the goals `A' and `B' should
    % be executed concurrently.  Parallel conjunction has exactly
    % the same declarative semantics as normal conjunction,
    % but it has different (stricter) rules for mode-correctness and
    % determinism-correctness, and it has different operational semantics.

> %	- `,'/2 does not quite behave as *logical* conjunction;

Yes, it does.
I suggest you reword that, perhaps as

	[Operational semantics]
	  `,'/2 gives some operational guarantees that `&'/2 does not:

> %       by default,
> %	  if `--no-reorder-conj' is set, there is an implied ordering
> %	  in the code:  conjunctions must not be reordered beyond the
> %	  minimum necessary for mode correctness.
> %	  This is justified for reasons performance modeling and ensuring
> %	  predicatble termination properties.

s/predicatble/predicatable/

> %	- `,'/2 has a *sequential* behaviour `A, B' proves `A' *then*
> %	  proves `B'. Mode analysis only allows unidirectional data-

Inserting a heading
	[Mode correctness]
before this point might make it clearer here.

> % The runtime support for parallel conjunction is documented in the runtime
> % directory in context.mod.

A dangling pointer.

> par_conj_gen__generate_det_par_conj(Goals, GoalInfo, Code) -->

I hope this is correct; I haven't looked at the code in much detail.

You need to add some test cases!


OK, that's it for this review.  I think we need another round, though.
Could you please send a diff relative to this one when you've addressed
the issues raised in my review?

Thanks,
	Fergus.

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