[m-dev.] Tabling [2/3]

[Fergus Henderson]

On 23-Mar-1998, Oliver Hutchison <ohutch at students.cs.mu.oz.au> wrote:
> Index: library/mercury_builtin.m

> +% 2)	Predicates to test and set the status of the tables. These predicates
> +%	expect ether a subgoal or answer table node depending there 
> +%	functionality.

s/ether/either/
s/there/on their/

> +% 3) 	Predicates to save answers into the tables. Answers are saved in
> +% 	an answer block which is a vector n elements where n is the number 
> +%	of output arguments of the predicate it belongs to. For	det and 
> +%	semidet tabling the answer block is connected directly to subgoal 
> +%	table nodes. In the case of nondet tabling answer blocks are connected 
> +%	to answered slots which are strung together to form a list. 

s/block which/block, which/
s/vector n elements/vector of n elements/

> +	% This type is used as a generic table it can in fact represent two
> +	% types ether a subgoal_table or an answer_table. The subgoal_table
> +	% and answer_table types are differentiated by what they have at the
> +	% table nodes but not by the actual underling trie structure.

s/table it can/table: it can/
s/types ether/types, either/

By the way, the use of different types for the different sorts of tables
makes the code *much* easier to read.  Thanks.

> +	% This is a dummy predicate, its pred_proc_id, but not its code, 
> +	% is used. See the comment in compiler/table_gen.m for more 
> +	% information. 
> +:- impure pred get_table(table).

s/predicate, its/predicate: its/

> +	% Create a new slot in the answer list.
> +:- impure pred table_new_ans_slot(subgoal_table_node, answer_slot).
> +:- mode table_new_ans_slot(in, out) is det.
> +
> +	% Return true if the subgoal represented by the given table is
> +
> +	% Save an integer answer in the given answer block at the given 
> +	% offset.
> +:- impure pred table_save_int_ans(answer_block, int, int).
> +:- mode table_save_int_ans(in, in, in) is det.

The unfinished comment in the middle looks like it is not meant to
be there.

> +/* Used to save the state of a subgoal */
> +typedef struct {
> +	Word *last_ret_ans;		/* Pointer to the last answer return
> +					   to the node */

Should that be "returned" instead of "return"?

> +/* Used to save info about a single subgoal in the table */  
> +typedef struct {
> +	TableStatus status;		/* Status of subgoal */
> +	Word answer_table;		/* Table of answers returnd by the
> +					   subgoal */
> +	Word num_ans;			/* Number of answers returnd by the
> +					   subgoal */
> +	Word answer_list;		/* List of answers returnd by the
> +					   subgoal */
> +	Word *ans_list_tail;		/* Pointer to the tail of the ans
> +					   list. This is used to update the
> +					   tail rather than the head of the
> +					   ans list. */
> +	Word suspend_list;		/* List of suspended calls to the
> +					   subgoal */
> +	Word *suspend_list_tail;	/* Dito for ans_list_tail */
> +	Word *non_stack_bottom;		/* Pointer to the bottom point of
> +					   the nondet stack from whicj to
> +					   copy */
> +	Word *det_stack_bottom;		/* Pointer to the bottom point of
> +					   the det stack from which to copy */

s/returnd/returned/g
s/whicj/which/
s/Dito/Ditto/
s/ans/answer/

> +:- pragma c_code(table_suspend(T::in, A::out), will_not_call_mercury, "
> +	Word *non_stack_top =  MR_maxfr;
> +	Word *det_stack_top =  MR_sp;
> +	Word *non_stack_bottom = NON_TABLE(T)->non_stack_bottom;
> +	Word *det_stack_bottom = NON_TABLE(T)->det_stack_bottom;
> +	Word non_stack_delta = non_stack_top - non_stack_bottom;
> +	Word det_stack_delta = det_stack_top - det_stack_bottom;
> +	Word ListNode;
> +	SuspendListNode *Node = table_allocate(sizeof(SuspendListNode));
> +	
> +	Node->last_ret_ans = &(NON_TABLE(T)->answer_list);
> +	
> +	Node->non_stack_block_size = non_stack_delta;
> +	Node->non_stack_block = table_allocate(non_stack_delta);
> +	table_copy_mem((void *)Node->non_stack_block, (void *)non_stack_bottom, 
> +		non_stack_delta);	
> +		
> +	Node->det_stack_block_size = det_stack_delta;
> +	Node->det_stack_block = table_allocate(det_stack_delta);
> +	table_copy_mem((void *)Node->det_stack_block, (void *)det_stack_bottom, 
> +		det_stack_delta);
> +
> +	Node->succ_ip = MR_succip;
> +	Node->s_p = MR_sp;
> +	Node->cur_fr = MR_curfr;
> +	Node->max_fr = MR_maxfr;
> +
> +	ListNode = list_cons(Node, *NON_TABLE(T)->suspend_list_tail);
> +	*NON_TABLE(T)->suspend_list_tail = ListNode;
> +	NON_TABLE(T)->suspend_list_tail = &list_tail(ListNode);
> +	
> +	A = 0;
> +	fail();	
> +").

Some comments here would be nice.
Why do you set A = 0?

I think the call to fail() should instead be a call to FAIL().

Deja vu, I said the same thing last time ;-)

| Some more documentation about the code for this predicate
| would be helpful.
| 
| Why is it declared as `nondet'?
| 
| Why assign to A if you're only going to immediately fail anyway?
|
| According to the nonexistant documentation for nondet pragma C ;-),
| the `fail()' here should be `FAIL()'.

> +:- external(table_resume/1).
> +
> +:- pragma c_code("
> +
> +typedef struct {
> +	NondetTable *table;
> +	Word non_stack_block_size;
> +	Word *non_stack_block;
> +	Word det_stack_block_size;
> +	Word *det_stack_block;
> +	
> +	Code *succ_ip;
> +	Word *s_p;
> +	Word *cur_fr;
> +	Word *max_fr;
> +
> +	Word changed;
> +	Word num_ans, new_num_ans;
> +	Word suspend_list;
> +	SuspendListNode *suspend_node;
> +	Word ans_list;
> +	AnswerListNode *ansNode;
> +} ResumeStackNode;
> +
> +Integer ML_resumption_sp = -1;
> +Word ML_resumption_stack_size = 256;	/* Half the initial size of 
> +						the stack */
> +ResumeStackNode** ML_resumption_stack = NULL;

Please see my comments from last time.

>  #define HASH_STRING_FUNC_BODY				\
> -	   int hash;					\
> -	   do_hash_string(hash, s);			\
> -	   return hash;
> +	   int _hash;					\
> +	   do_hash_string(_hash, s);			\
> +	   return _hash;

Ditto.

> +++ mercury_type_info.h	1998/03/20 05:21:09
> @@ -779,5 +779,26 @@
>  
> +Word * MR_create_type_info(Word *, Word *);
> +int MR_compare_type_info(Word, Word);
> +Word MR_collapse_equivalences(Word);

Ditto.

> +/* 
> +** definitions for creating type infos from pseudo_type_info's
> +*/
> +
> +/* for make_type_info(), we keep a list of allocated memory cells */
> +struct MemoryCellNode {
> +	void *data;
> +	struct MemoryCellNode *next;
> +};
> +typedef struct MemoryCellNode *MemoryList;
> +
> +Word * make_type_info(Word *term_type_info, Word *arg_pseudo_type_info,
> +	MemoryList *allocated);
> +void deallocate(MemoryList allocated_memory_cells);

MemoryCellNode, MemoryList, make_type_info, and deallocate
should all get an `MR_' prefix, since they're now in the
runtime header files and hence globally visible.

I'd like to see more documentation for table_resume/1 and
table_suspend/1.

That's it for part 2.

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