for review: minimal model tabling

[Fergus Henderson]

On 20-Mar-1999, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> runtime/mercury_tabling.[ch]:
> 	The implementation of the new tabling system. Much of the new code here
> 	is stuff moved from library/private_builtin.m, but in a significantly
> 	rewritten form. There is also substantial new code, e.g. to handle
> 	the extension of saved stack segments, and to manage dependencies
> 	between subgoals in general.
...
> runtime/mercury_tabling.[ch]:
> 	Move the significantly reimplemented code that handles minimal model
> 	tabling here from library/private_builtin.m.
> 
> 	Improve the documentation considerably.
> 
> 	Replace lists stored as Mercury data structures with lists stored
> 	as linked structures in the usual C fashion. This allows us to use
> 	debuggers such as ddd on these data structures, whose complexity
> 	requires this.
> 
> 	Ensure that global names start with MR_.

You should combine those two parts of the log message.

> Index: compiler/code_info.m
...
> +		code_info__get_globals(Globals),
> +		{ globals__lookup_bool_option(Globals, use_minimal_model,
> +			UseMinimalModel) },
> +		{ HijackInfo = commit_temp_frame(MaxfrSlot, UseMinimalModel) },
> +		{
> +			UseMinimalModel = yes,
> +			Components = [
> +				pragma_c_raw_code("\tsave_transient_registers();\n"),
> +				pragma_c_raw_code("\tMR_commit_mark();\n"),
> +				pragma_c_raw_code("\trestore_transient_registers();\n")
> +			],
> +			MarkCode = node([
> +				pragma_c([], Components, will_not_call_mercury,
> +					no, no) - ""
> +			])
> +		;
> +			UseMinimalModel = no,
> +			MarkCode = empty
> +		},

A comment here explaining why we need to call MR_commit_mark()
if --use-minimal-model is set would be helpful.

Also, please stick to < 80 columns.

> @@ -1792,12 +1813,27 @@
> +		{
> +			UseMinimalModel = yes,
> +			Components = [
> +				pragma_c_raw_code("\tMR_commit_cut();\n")
> +			],
> +			CutCode = node([
> +				pragma_c([], Components,
> +					will_not_call_mercury, no, no)
> +					- "commit for temp frame hijack"
> +			])
> +		;
> +			UseMinimalModel = no,
> +			CutCode = empty
> +		},

Likewise a comment here would be helpful.

> Index: runtime/mercury_context.c
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/runtime/mercury_context.c,v
> retrieving revision 1.18
> diff -u -b -u -r1.18 mercury_context.c
> --- mercury_context.c	1998/12/16 17:10:28	1.18
> +++ mercury_context.c	1999/03/11 08:32:44
> @@ -117,6 +117,24 @@
>  	MR_succip_slot(c->context_curfr) = ENTRY(do_not_reached);
>  	MR_succfr_slot(c->context_curfr) = NULL;
>  
> +	if (c->generatorstack_zone != NULL) {
> +		reset_redzone(c->generatorstack_zone);
> +	} else {
> +		c->generatorstack_zone = create_zone("generatorstack", 0,
> +			generatorstack_size, next_offset(),
> +			generatorstack_zone_size, default_handler);
> +	}
> +	c->context_gen_sp = 0;
> +
> +	if (c->cutstack_zone != NULL) {
> +		reset_redzone(c->cutstack_zone);
> +	} else {
> +		c->cutstack_zone = create_zone("cutstack", 0,
> +			cutstack_size, next_offset(),
> +			cutstack_zone_size, default_handler);
> +	}
> +	c->context_cut_sp = 0;

I think all that code should be inside "#ifdef MR_USE_MINIMAL_MODEL"
or something like that.

Likewise for all the other new code added to mercury_context.h,
mercury_context.c, mercury_memory.c, mercury_stacks.c,
and mercury_tabling.c.  Also for the code in
trace/mercury_trace_internal.h.

> +++ mercury_init.h	1999/03/11 08:58:55
>  
> +#include "mercury_regs.h"	/* must be before prototypes */

I don't understand the comment here.  Why must "mercury_regs.h"
be #included before the function prototypes?

> Index: runtime/mercury_tabling.c
...
> +static void
> +save_state(MR_SavedState *saved_state,
> +	Word *generator_maxfr, Word *generator_sp,
> +	const char *who, const char *what)

A comment explaining what this function is supposed to do
would be helpful.

> +{
> +	restore_transient_registers();
> +
> +	saved_state->succ_ip = MR_succip;
> +	saved_state->s_p = MR_sp;
> +	saved_state->cur_fr = MR_curfr;
> +	saved_state->max_fr = MR_maxfr;
> +
> +	saved_state->non_stack_block_start = generator_maxfr + 1;
> +	if (MR_maxfr > generator_maxfr) {
> +		saved_state->non_stack_block_size = MR_maxfr - generator_maxfr;
> +		saved_state->non_stack_block =
> +			table_allocate_words(saved_state->non_stack_block_size);
> +		table_copy_words(saved_state->non_stack_block,
> +			saved_state->non_stack_block_start,
> +			saved_state->non_stack_block_size);
> +	} else {
> +		saved_state->non_stack_block_size = 0;
> +		saved_state->non_stack_block = NULL;
> +	}
> +
> +	saved_state->det_stack_block_start = generator_sp;
> +	if (MR_sp > generator_sp) {
> +		saved_state->det_stack_block_size = (MR_sp - 1) - generator_sp;
> +		saved_state->det_stack_block =
> +			table_allocate_words(saved_state->det_stack_block_size);
> +		table_copy_words(saved_state->det_stack_block,
> +			saved_state->det_stack_block_start,
> +			saved_state->det_stack_block_size);
> +	} else {
> +		saved_state->det_stack_block_size = 0;
> +		saved_state->det_stack_block = NULL;
> +	}
> +
> +	saved_state->gen_sp = MR_gen_sp;
> +	saved_state->generator_stack_block = table_allocate_bytes(
> +			MR_gen_sp * sizeof(MR_GeneratorStackFrame));
> +	table_copy_bytes(saved_state->generator_stack_block,
> +		(char *) MR_gen_stack,
> +		MR_gen_sp * sizeof(MR_GeneratorStackFrame));

If MR_gen_sp is a pointer, then the above code is buggy.
If MR_gen_sp is actually an array index, rather than a pointer,
then I think perhaps `MR_gen_sp' is a misleading name.

Why the cast to `char *' here?

> +	saved_state->cut_sp = MR_cut_sp;
> +	saved_state->cut_stack_block = table_allocate_bytes(
> +			(MR_cut_sp + 1) * sizeof(MR_CutStackFrame));
> +	table_copy_bytes(saved_state->cut_stack_block,
> +		(char *) MR_cut_stack,
> +		(MR_cut_sp + 1) * sizeof(MR_CutStackFrame));

Why the cast to `char *' here?

> +#ifdef MR_USE_TRAIL
> +	/*
> +	** We ought to save the trail state here --
> +	** this is not yet implemented.
> +	*/
> +	fatal_error("Sorry, not implemented: "
> +		"can't have both tabling and trailing");
> +#endif

s/tabling/minimal model tabling/

> +static void
> +extend_consumer_stacks(MR_Subgoal *leader, MR_Consumer *suspension)

A comment explaining what this function is supposed to do would be
helpful.

> +static void
> +make_subgoal_follow_leader(MR_Subgoal *this_follower, MR_Subgoal *leader)

Likewise here.

> +/* 
> +** The following procedure saves the state of the mercury runtime 
> +** so that it may be used in the table_nondet_resume procedure below to return 
> +** answers through this saved state. The procedure table_nondet_suspend is 
> +** declared as nondet but the code below is obviously of detism failure, 
> +** the reason for this is quite simple.  Normally when a nondet proc
> +** is called it will first return all of its answers and then fail. In the 
> +** case of calls to this procedure this is reversed first the call will fail
> +** then later on, when the answers are found, answers will be returned.

I suggest

	s/mercury/Mercury/
	s/failure,/failure;/
	s/reversed first/reversed: first/

> +				*clobber_addr = (Word) ENTRY(mercury__table_nondet_resume_1_0);

Please stick to < 80 columns.

> +#ifdef	MR_TABLE_DEBUG
> +				if (MR_tablestackdebug) {
> +					printf("completing redoip of frame at ");

Ditto.

> +#ifdef	MR_TABLE_DEBUG
> +				if (MR_tablestackdebug) {
> +					printf("clobbering redoip of frame at ");

Ditto.

> +#if 1
> +	if (MR_cur_leader->resume_info->cur_consumer_answer_list != NULL) {
> +		GOTO_LABEL(mercury__table_nondet_resume_1_0_ReturnAnswer);
> +	}
> +#else
> +	if (*(MR_cur_leader->resume_info->cur_consumer->
> +		remaining_answer_list_ptr) != NULL)
> +	{
> +		MR_cur_leader->resume_info->cur_consumer_answer_list =
> +			*(MR_cur_leader->resume_info->cur_consumer->
> +				remaining_answer_list_ptr);
> +		GOTO_LABEL(mercury__table_nondet_resume_1_0_ReturnAnswer);
> +	}
> +#endif

A comment here would help...

>  #define MR_TABLE_GET_ANSWER(Offset, ABlock)				\
> -	(* ((AnswerBlock) ABlock))[Offset]
> +	(( MR_tabledebug ?						\
> +		(printf("using answer block: %p\n",			\
> +			((MR_AnswerBlock) ABlock)),			\
> +		printf("pointing to: %p\n",				\
> +			*((MR_AnswerBlock) ABlock)))			\
> +	:								\
> +		0 /* do nothing */					\
> +	),								\
> +	(* ((MR_AnswerBlock) ABlock))[Offset])

A a style issue, I suggest using `((void) 0)' rather than just
`0' for a do-nothing expression.

> +/*
> +** The state of a model_det or model_semi subgoal.
> +**
> +** Note that the word containing the MR_SimpletableStatus,
> +** which is at the end of the chain of trie nodes given by
> +** the input arguments of the tabled subgoal, will be overwritten
> +** by a pointer to the answer block containing the output arguments
> +** when the goal succeeds. The MR_SIMPLETABLE_SUCCEEDED status code
> +** is used only when the goal has no outputs. This is why
> +** MR_SIMPLETABLE_SUCCEEDED must the last entry in the enum,
> +** and why code looking at an MR_SimpletableStatus must test
> +** for success with "x >= MR_SIMPLETABLE_SUCCEEDED".
> +*/

I think "x >= ..." should be "(Unsigned) x >= ...".

> +++ mercury_wrapper.c	1999/03/18 21:24:17
...
> +/* virtual machine registers that we don't even try to make real ones */
> +Integer			MR_gen_sp = 0;
> +Integer			MR_cut_sp = 0;
> +MR_GeneratorStackFrame	*MR_gen_stack = NULL;
> +MR_CutStackFrame	*MR_cut_stack = NULL;

Hmm, shouldn't they go in the MR_Engine data structure?

If tabling is not supposed to work in conjunction with multithreading,
then that should be documented, with appropriate XXX comments,
calls to fatal_error("sorry, not implemented: ...") and/or
compile-time `#ifdef ... #error ... #endif' tests.

> Index: tests/tabling/Mmakefile
...
> +# We don't yet pass the following tests. The reason is that they contain
> +# interactions between tabling and constructs that function as negated
> +# contexts.
> +#
> +#	consumer_in_commit
> +#	consumer_in_solutions
...
> -# tc_loop is expected to abort, so we need to ignore the exit status
> +# Some test cases are expected to abort, so we need to ignore the exit status
>  # (hence the leading `-')
>  tc_loop.out: tc_loop
>  	-./tc_loop > tc_loop.out 2>&1;
> +
> +consumer_in_commit.out: consumer_in_commit
> +	-./consumer_in_commit > consumer_in_commit.out 2>&1;
> +
> +consumer_in_solutions.out: consumer_in_solutions
> +	-./consumer_in_solutions > consumer_in_solutions.out 2>&1;

Why is the exit status ignored in these two cases?

I think simply leaving them out of the list of test cases,
which you have already done, is enough.
If you also add code to ignore the exit status, 
then someone may eventually re-enable these test
cases but forget to delete the code that ignores the
exit status.

Not that tc_loop is *supposed* to abort (aborting is
the right answer for that test case), that's why its
exit status is ignored, but I that is not the case for
these two test cases.

> +++ coup_det_frame.m	Fri Feb 26 17:48:53 1999
> @@ -0,0 +1,51 @@
> +% This test is a variant of coup, with the commits around the recursive
> +% calls wrapped up inside exlicit predicates. This means that when a
> +% subgoal is suspended, coup2 will require a non-empty det stack segment

s/exlicit/explicit/
s/coup2/coup_det_frame/

> +++ generator_in_commit.m	Wed Mar 17 17:31:16 1999
> @@ -0,0 +1,44 @@
> +% This test case checks whether we get incorrect answers
> +% when a generated gets started but not finished inside a commit.

s/generated/generator/

> % File: private_builtin.m.
...
> % The interface for this module does not get included in the
> % Mercury library library reference manual.

s/library library/library/

> % Many of the predicates defined in this module are builtin -
> % they have definitions because the compiler generates code for them inline.

s/have definitions/do not have definitions/

> % The utility predicates that handle tries are combined lookup/insert
> % operations; if the item being searched for is not already in the trie,
> % they insert it. These predicates are used for implement both subgoal tables,

s/for implement/to implement/

> 	% These equivalences should be local to private_builtin. However,
> 	% at the moment table_gen.m assumes that it can use a single variable
> 	% sometimes as an ml_table and other times as an ml_subgoal_table_node
> 	% (e.g. by giving the output of table_lookup_insert_int as input to
> 	% table_have_all_ans). The proper fix would be for table_gen.m to
> 	% use additional variables and insert unsafe casts. However, this
> 	% would require significant work for no real gain, so for now
> 	% we fix the problem by exposing the equivalences to code generated
> 	% by table_gen.m.
> :- type ml_table == c_pointer.
> :- type ml_subgoal_table_node == c_pointer.
> :- type ml_answer_table_node == c_pointer.
> :- type ml_answer_slot == c_pointer.
> :- type ml_answer_block == c_pointer.

I think it would be clearer to write those as

	:- type ml_subgoal_table_node == ml_table.
	:- type ml_answer_table_node == ml_table.
	:- type ml_answer_slot == ml_table.
	:- type ml_answer_block == ml_table.

And is there any reason why the `type ml_table == c_pointer' equivalence
is exported?

> :- interface.
> 
> 	% Return true if the subgoal represented by the given table has an
> 	% answer.
> :- semipure pred table_simple_is_complete(ml_subgoal_table_node).
> :- mode table_simple_is_complete(in) is semidet. 

I find these kind of declarations are easier to read if the pred
and mode parts are aligned:

  :- semipure pred table_simple_is_complete(ml_subgoal_table_node).
  :-          mode table_simple_is_complete(in) is semidet. 

 
> 	% Return true if the subgoal represented by the given table has a
> 	% true answer.
> :- semipure pred table_simple_has_succeeded(ml_subgoal_table_node).
> :- mode table_simple_has_succeeded(in) is semidet. 
> 
> 	% Return true if the subgoal represented by the given table has
> 	% failed.
> :- semipure pred table_simple_has_failed(ml_subgoal_table_node).
> :- mode table_simple_has_failed(in) is semidet.
> 
> 	% Currently being evaluated (working on an answer).
> :- semipure pred table_simple_is_active(ml_subgoal_table_node).
> :- mode table_simple_is_active(in) is semidet.

For consistency you should insert

 	% Return true if the subgoal represented by the given table is

in front of that comment.
 
> :- pragma c_code("
> BEGIN_MODULE(private_builtin_module_XXX)

What's the XXX for?

Apart from that, it looks fine, but I still haven't finished
reviewing private_builtin.m.

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