[m-rev.] diff: major improvements to tabling (part 1 of 2)

Ralph Becket rafe at cs.mu.OZ.AU
Tue Jul 20 15:14:01 AEST 2004


Zoltan Somogyi, Tuesday, 20 July 2004:
> Index: compiler/table_gen.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/compiler/table_gen.m,v
> retrieving revision 1.64
> diff -u -b -r1.64 table_gen.m
> --- compiler/table_gen.m	21 Jun 2004 03:31:55 -0000	1.64
> +++ compiler/table_gen.m	17 Jul 2004 10:53:16 -0000
> @@ -498,19 +529,50 @@
>  %			B = C,
>  %			impure table_loop_mark_as_inactive(T)
>  %		else
> -%			impure table_loop_mark_as_inactive(T),
> +%			impure table_loop_mark_as_inactive_and_fail(T),
> +%		)
> +%	).
> +%
> +% Example of transformation for model_non loopcheck:
> +%
> +% :- pred p(int::in, int::out) is semidet.
> +%
> +% p(A, B) :-
> +% 	<original code>.
> +%
> +% The transformed code would be :
> +%
> +% p(A, B) :-
> +%	T0 = <table pointer for p/2>,
> +%	impure table_lookup_insert_int(T0, A, T),
> +%	impure table_loop_setup(T, Status),
> +%	(
> +%		Status = loop_active,
> +%		error("detected infinite recursion in ...")
> +%	;
> +%		Status = loop_inactive,
> +%		% status has been changed to active by the setup predicate
> +%		(
> +%			<original code>,
> +%			(
> +%				impure table_loop_mark_as_inactive(T)
> +%			;
> +%				impure table_loop_mark_as_active_and_fail(T),
>  %			fail
>  %		)

This looks to me like that `fail' should be a close-parenthesis instead.

> +%		;
> +%			impure table_loop_mark_as_inactive_and_fail(T)
> +%		)
>  %	).

[...]

> @@ -652,17 +754,66 @@
>  %		)
>  %	).
>  %
> +% Example of transformation for model_non memo:
> +%
> +% :- pred p(int::in, int::out) is semidet.
> +%
> +% p(A, B) :-
> +% 	<original code>.
> +%
> +% The transformed code would be :
> +%
> +% p(A, B) :-
> +%	CT0 = <table pointer for p/2>,
> +%	impure table_lookup_insert_int(CT0, A, CT1),
> +%	impure table_memo_non_setup(CT1, Record, Status),
> +%	(
> +%		Status = memo_non_complete,
> +%		semipure table_memo_return_all_nondet(T, Block),
> +%		semipure table_restore_int_answer(Block, 0, B)
> +%	;
> +%		Status = memo_non_incomplete,
> +%		error("detected need for minimal model tabling in ...")
> +%	;
> +%		Status = memo_non_active,
> +%		error("detected infinite recursion in ...")
> +%	;
> +%		Status = memo_non_inactive,
> +%	   	(
> +%			<original code>,
> +%
> +%				% Check for duplicate answers.
> +%			semipure table_memo_get_answer_table(Record, AT0),
> +%			impure table_lookup_insert_int(AT0, B, AT1),
> +%				% Fail if the answer is already in the table;
> +%				% otherwise, put it into the table.
> +%			impure table_mm_answer_is_not_duplicate(AT1),
> +%
> +%				% Save the new answer in the table.
> +%			impure table_memo_create_answer_block(Record, 1, Block),
> +%			impure table_save_int_answer(Block, 0, B),
> +%			(
> +%				impure table_memo_mark_as_incomplete(R)
> +%			;
> +%				impure table_memo_mark_as_active_and_fail(R),
> +%				fail

Again, either the `fail' here is redundant or the name
`table_memo_mark_as_active_and_fail' is inaccurate.

> +%			)
> +%		;
> +%			impure table_memo_mark_as_complete_and_fail(R)
> +%		)
> +%	).
> +%

[...]

> @@ -1165,6 +1429,312 @@
>  
>  %-----------------------------------------------------------------------------%
>  
> +% Example of transformation for nondet minimal_model_own_stack :
> +%
> +% :- pred p(int, int).
> +% :- mode p(in, out) is nondet
> +%
> +% p(A, B) :- e(A, B).
> +% p(A, B) :- p(A, C), e(C, B).
> +%
> +% The transformed code would be :
> +%
> +% p2_gen(A, B) :-
> +%	impure table_mmos_pickup_generator(Generator),
> +%	(
> +%		(
> +%			%
> +%			% Original goals
> +%			%
> +%		),
> +%
> +%			% Check for duplicate answers.
> +%		semipure table_mmos_get_answer_table(Generator, AT0),
> +%		impure table_lookup_insert_int(AT0, B, AT1),
> +%			Fail if the answer is already in the table;
> +%			otherwise, put it into the table.
> +%		impure table_mmos_answer_is_not_duplicate(AT1),
> +%
> +%			% Save the new answer in the table.
> +%		impure table_mmos_create_answer_block(Generator, 1,
> +%			AnswerBlock),
> +%		impure table_save_int_ans(AnswerBlock, 0, B),
> +%		impure table_mmos_return_answer(Generator, AnswerBlock)
> +%	;
> +%		impure table_mmos_completion(Generator)
> +%	).
> +%
> +% p(A, B) :-
> +%	table_mmos_save_inputs(1, A),		% into global variable
> +%	CT0 = <table pointer for p/2>,
> +%	impure table_lookup_insert_int(CT0, A, CT1),
> +%	impure table_mmos_setup_consumer(CT1, 1, p2_gen, "p/2", Consumer),
> +%	impure table_mmos_consume_next_answer_nondet(Consumer, AnswerBlock),
> +%	impure table_restore_int_ans(AnswerBlock, 0, B).

I'd reverse the order here so that p/2 is shown before p2_gen/2.


> +
> +:- pred table_gen__do_own_stack_transform(determinism::in, hlds_goal::in,
> +	pred_id::in, proc_id::in, pred_info::in, proc_info::in,
> +	list(prog_var)::in, list(prog_var)::in, list(prog_var)::in,
> +	vartypes::in, vartypes::out, prog_varset::in, prog_varset::out,
> +	table_info::in, table_info::out, generator_map::in, generator_map::out,
> +	prog_var::out, hlds_goal::out, list(table_trie_step)::out) is det.
> +
> +table_gen__do_own_stack_transform(Detism, OrigGoal, PredId, ProcId,
> +		PredInfo0, ProcInfo0, HeadVars, InputVars, OutputVars,
> +		!VarTypes, !VarSet, !TableInfo, !GenMap, TableTipVar,
> +		Goal, Steps) :-
> +	PredName = pred_info_name(PredInfo0),
> +	( map__search(!.GenMap, PredId, GeneratorPredIdPrime) ->
> +		GeneratorPredId = GeneratorPredIdPrime
> +	;
> +		clone_pred_info(PredInfo0, GeneratorPredId, !TableInfo),
> +		map__det_insert(!.GenMap, PredId, GeneratorPredId, !:GenMap)
> +	),
> +
> +	allocate_slot_numbers(InputVars, 0, NumberedInputVars),
> +	allocate_slot_numbers(OutputVars, 0, NumberedOutputVars),
> +
> +	% Even if the original goal doesn't use all of the headvars,
> +	% the code generated by the tabling transformation does,
> +	% so we need to compute the nonlocals from the headvars rather
> +	% than getting it from the nonlocals field in the original goal.
> +	set__list_to_set(HeadVars, OrigNonLocals),
> +	OrigGoal = _ - OrigGoalInfo,
> +	goal_info_get_instmap_delta(OrigGoalInfo, OrigInstMapDelta),
> +	goal_info_get_context(OrigGoalInfo, Context),
> +
> +	list__length(InputVars, NumInputVars),
> +	ModuleInfo = !.TableInfo ^ table_module_info,
> +
> +	SaveInputPred = "table_mmos_save_inputs",
> +	generate_save_input_vars_code(NumberedInputVars, !.VarTypes,
> +		SaveInputVarArgs, SaveInputVarCode),
> +	SaveMainCode = "MR_" ++ SaveInputPred ++ "(" ++
> +		int_to_string(NumInputVars) ++ ");",
> +	generate_foreign_proc(SaveInputPred, det, tabling_c_attributes,
> +		[], SaveInputVarArgs, "", SaveMainCode, SaveInputVarCode,
> +		impure_code, ground_vars([]), ModuleInfo, Context, SaveGoal),
> +
> +		% The type is a lie, but a safe one: the variable we create
> +		% is handled only by C code. The reason why we lie is that
> +		% creating the right type would be quite complicated.
> +	GeneratorPredType = c_pointer_type,
> +
> +	generate_new_table_var("GeneratorPredVar", GeneratorPredType,
> +		!VarTypes, !VarSet, GeneratorPredVar),
> +	generate_new_table_var("Consumer", consumer_type, !VarTypes, !VarSet,
> +		ConsumerVar),
> +
> +	ShroudedPredProcId =
> +		shroud_pred_proc_id(proc(GeneratorPredId, ProcId)),
> +	GeneratorConsId = pred_const(ShroudedPredProcId, normal),
> +	make_const_construction(GeneratorPredVar, GeneratorConsId,
> +		MakeGeneratorVarGoal),
> +
> +	% XXX use tabling via foreign_proc
> +	generate_call_table_lookup_goals(NumberedInputVars, PredId, ProcId,
> +		Context, !VarTypes, !VarSet, !TableInfo, TableTipVar,
> +		LookupGoals, Steps, _PredTableVar, _LookupForeignArgs,
> +		_LookupPrefixGoals, _LookupCodeStr),
> +
> +	TableTipVarName = table_tip_node_name,
> +	GeneratorPredVarName = generator_pred_name,
> +	ConsumerVarName = consumer_name,
> +
> +	TableTipArg = foreign_arg(TableTipVar,
> +		yes(TableTipVarName - in_mode), trie_node_type),
> +	GeneratorPredArg = foreign_arg(GeneratorPredVar,
> +		yes(generator_pred_name - in_mode), GeneratorPredType),
> +	ConsumerArg = foreign_arg(ConsumerVar,
> +		yes(ConsumerVarName - out_mode), consumer_type),
> +
> +	SetupPred = "table_mmos_setup_consumer",
> +	SetupCode = "MR_" ++ SetupPred ++ "(" ++
> +		TableTipVarName ++ ", " ++
> +		int_to_string(NumInputVars) ++ ", " ++
> +		GeneratorPredVarName ++ ", " ++
> +		"""" ++ PredName ++ """, " ++

It's a small thing, but I think `\"' is preferable to `""' for literal
double-quotes (I've always found the latter hard to read.)

-- Ralph
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------



More information about the reviews mailing list