Tabling round 2 [3/3]

[Fergus Henderson]

On 13-Mar-1998, Oliver Hutchison <ohutch at students.cs.mu.OZ.AU> wrote:
> New File: compiler/table_gen.m
...
> % This module transforms HLDS code to a form that allows tabled evaluation,
> % minimal model evaluation and loop detection.
> % 
> % Main author: ohutch
> %
> % The tabling transformation adds calls to several tabling predicates as 
> % well as restructuring the HLDS to implement answer clause resolution,  
> % suspension and loop detection.

It would be good to cite a paper which describes this stuff in more detail,
e.g. Kostis' thesis.

> table_gen__process_module(Module0, Module) :-
> 	module_info_preds(Module0, Preds0),
> 	map__keys(Preds0, PredIds),
> 	table_gen__process_preds(PredIds, Module0, Module).
> 
> :- pred table_gen__process_preds(list(pred_id), module_info, module_info).
> :- mode table_gen__process_preds(in, in, out) is det.
> 
> table_gen__process_preds([], Module, Module).
> table_gen__process_preds([PredId | PredIds], Module0, Module) :-
> 	table_gen__process_pred(PredId, Module0, Module1),
> 	table_gen__process_preds(PredIds, Module1, Module).
> 
> :- pred table_gen__process_pred(pred_id, module_info, module_info).
> :- mode table_gen__process_pred(in, in, out) is det.
> 
> table_gen__process_pred(PredId, Module0, Module) :-
> 	module_info_pred_info(Module0, PredId, PredInfo),
> 	pred_info_procids(PredInfo, ProcIds),
> 	table_gen__process_procs(PredId, ProcIds, Module0, Module).
> 
> :- pred table_gen__process_procs(pred_id, list(proc_id),
> 					module_info, module_info).
> :- mode table_gen__process_procs(in, in, in, out) is det.
> table_gen__process_procs(_PredId, [], Module, Module).
> table_gen__process_procs(PredId, [ProcId | ProcIds], Module0,
> 		Module) :-
> 	module_info_preds(Module0, PredTable),
> 	map__lookup(PredTable, PredId, PredInfo),
> 	pred_info_procedures(PredInfo, ProcTable),
> 	map__lookup(ProcTable, ProcId, ProcInfo),

Any particular reason why this code doesn't use the routines
in passes_aux.m?

> table_gen__create_new_det_goal(EvalMethod, OrigGoal, Module, HeadVars, 
> 		HeadVarModes, VarTypes0, VarTypes, VarSet0, VarSet, Goal) :-
...
> 	(
> 		(
> 			EvalMethod = eval_memo
> 		;
> 			EvalMethod = eval_loop_check
> 		)
> 	->
> 		(
> 			EvalMethod = eval_loop_check
> 		->
> 			SaveAnsGoal = DoneWorkingGoal
> 		;
> 			SaveAnsGoal = SaveAnsGoal0
> 		),
		... lots of code ...
> 	;
> 		error(
>     "table_gen__create_new_det_goal: unsupported evaluation model")
> 	),

It would be simpler to write this as

	( EvalMethod = eval_loop_check ->
		SaveAnsGoal = DoneWorkingGoal
	; EvalMethod = eval_loop_check ->
		SaveAnsGoal = SaveAnsGoal0
	;
		error(
		"table_gen__create_new_det_goal: unsupported evaluation model")
	),
	... lots of code ...

> 	GoalEx = pragma_c_code(will_not_call_mercury, PredId, ProcId,
> 			[TableVar], [yes("TableVar" - TableVarMode)], 
> 			[TableVarType], ordinary( 
> "	{
> 		static Word Table = 0;
> 		TableVar = (Word)&Table;
> 	}
> ", 

I suggest s/Table/table/, to conform to our C coding guidelines.

Actually these names should have a prefix to avoid
name clashes.  The prefix should probably be `MC_'.
(MR_ for names in the runtime, ML_ for names in the library,
and MC_ for names generated by the compiler.)

So I suggest

	s/Table/MR_table/
	s/TableVar/MC_TableVar/

> gen_lookup_call_for_type(TypeCat, Type, TableVar, ArgVar, Module, VarTypes0,
> 		VarTypes, VarSet0, VarSet, NextTableVar, Goal) :-
> 	(
> 		TypeCat = enum_type
> 	->
> 		(
> 			type_to_type_id(Type, TypeId, _)
> 		->
> 			module_info_types(Module, TypeDefnTable),
> 			map__lookup(TypeDefnTable, TypeId, TypeDefn),
> 			hlds_data__get_type_defn_body(TypeDefn, TypeBody),
> 			(
> 				TypeBody = du_type(Ctors, _, yes, no)
> 			->
> 				list__length(Ctors, EnumRange)	
> 			;
> 				error(
>     "gen_lookup_call_for_type: unsupported type in tabled predicate/function")
> 			),

"unsupported" is misleading here; I think you mean "impossible".
Probably the message here should be

     "gen_lookup_call_for_type: enum type is not du_type?")

> gen_restore_call_for_type(TypeCat, _Type, TableVar, Var, OffsetVar, Module, 
> 		Goal) :-
> 	(
> 		(
> 			TypeCat = pred_type
> 		;
> 			TypeCat = enum_type
> 		;
> 			TypeCat = polymorphic_type
> 		;
> 			TypeCat = user_type
> 		)

That condition is duplicate several times;
you should factor out the common code into a subroutine.

> generate_call(PredName, Args, Detism, Feature, InstMap, Module, Goal) :-
> 	list__length(Args, Arity),
> 	module_info_get_predicate_table(Module, PredTable),
> 	(
> 		predicate_table_search_pred_m_n_a(PredTable,
> 			unqualified("mercury_builtin"), PredName, Arity, 
> 			[PredId0])

You should use `mercury_private_builtin_module/1' from modules.m
rather than hard-coding "mercury_builtin".
...
> 	Call = call(PredId, ProcId, Args, not_builtin, no, qualified(
> 		unqualified("mercury_builtin"), PredName)), 

Likewise here.

> :- pred get_table_var_type(type).
> :- mode get_table_var_type(out) is det.
> 
> get_table_var_type(Type) :-
> 	construct_type(qualified(unqualified("mercury_builtin"), 
> 		"c_pointer") - 0, [], Type).	

Ditto.

>                     case TYPELAYOUT_UNIV_VALUE:
> 		    {
> 			Table = (Word**) MR_TABLE_TYPE_INFO(Table,
> 				data_value[UNIV_OFFSET_FOR_TYPEINFO]);
> 			Table = (Word**) MR_TABLE_ANY(Table,
> 				data_value[UNIV_OFFSET_FOR_TYPEINFO],
> 				data_value[UNIV_OFFSET_FOR_DATA]);
>                         break;
> 		    }
>                     case TYPELAYOUT_PREDICATE_VALUE:
> 		    {
> 		       	Word args = data_value[0];
> 
> 			Table = (Word **) MR_TABLE_WORD(Table, args);
> 			Table = (Word **) MR_TABLE_WORD(Table, data_value[1]);
> 			
> 			for (i = 0; i < args; i++) {
> 			    Table = (Word **) MR_TABLE_ANY(Table, 
> 				(Word *) type_info[i + 
> 				    TYPEINFO_OFFSET_FOR_PRED_ARGS],
> 				data_value[i+2]);
> 			}
> 		    }

The strange layout of the curly braces here is due to inconsistent
use of spaces and tables.  Please fix this.

> 			Table = (Word**) MR_TABLE_TAG(Table, data_tag);
> 			Table = (Word**) MR_TABLE_ENUM(Table, functors, 
> 					(Word)data_value);

s/(Word)/(Word) /

> static Word *
> make_type_info(Word *term_type_info, Word *arg_pseudo_type_info,
> 	bool *allocated) 

As I said last time around:

 | But actually, aren't those routines exactly the same as the ones
 | of the same name somewhere else?  If so, you should make them
 | `extern' rather than `static' and just define them in only one place.

And indeed, it appears that make_type_info() here is exactly the
same as in runtime/mercury_deep_copy.c.

If so, you should export the version from mercury_deep_copy.c
and use that, rather than duplicating the code.
(It might make sense to move the function from mercury_deep_copy.c
to mercury_type_info.c.)

> New File: runtime/mercury_table_any.h
> ===================================================================
> #ifndef _MERCURY_TABLE_ANY_H
> #define _MERCURY_TABLE_ANY_H
> 
> /*
> ** This function will lookup or insert any type of value into a 
> ** table. It uses the provided type_info to extract the necessary
> ** info to do this.
> */
> Word ** MR_table_type(Word *type_info, Word data_value, 
>     Word ** Table);

What's the semantics of the return value?

> #define ELEMENT(Table, Key) ((Word**)&(Table[Key]))

You should use an extra set of parentheses:

	#define ELEMENT(Table, Key) ((Word**)&((Table)[Key]))
					       ^     ^

Otherwise something like

	Element(ptr + offset, key);

will parse incorrectly.


> /*
> **  MR_int_index_lookup_or_add() : This function maintains a simple indexed 
> **	table of size Range.  
> */
> Word ** 
> MR_int_index_lookup_or_add(Word ** T, Integer Key, 
>         Integer Range)

s/T/t/
s/Key/key/
s/Range/range/

I guess the semantics of T(able), Key and Range are clear from the names,
but what's the semantics of the return value?

It would be good to use a typedef instead of `Word **'.

> /* Amount the table is allowed to fill. Must be less than 0.9 if you want
>    even poor lookup times */
> #define MAX_EL_SIZE_RATIO 0.95

I don't quite understand the comment here.

If <0.9 is required for good performance, why is the value 0.95?

> /*
>  *  Prime numbers which are close to powers of 2.  Used for choosing
>  *  the next size for a hash table.
>  */

You should use

	/*
	** ... comments here ...
	** ...
	*/

instead of

	/*
	 *  ... comments here ...
	 *  ...
	 */

> /*
>  *  Return the next prime number greater than the number received.
>  *  If no such prime number can be found, compute an approximate one.
>  */

Ditto.

> /* Insert key and Data into a new hash table using the given hash.
>  * this function does not have to do compares as the given key 
>  * is definitely not in the table. 
>  */

Ditto.

> /* Look to see if the given integer key is in the given table. If it
> ** is return the address of the data pointer associated with the key.
> ** If it is not; create a new element for the key in the table and
> ** return the address of its data pointer
> **/

Ditto.

> /* Look to see if the given float key is in the given table. If it
> ** is return the address of the data pointer associated with the key.
> ** If it is not create a new element for the key in the table and
> ** return the address of its data pointer
> **/

Ditto.

> /* Look to see if the given string key is in the given table. If it
> ** is return the address of the data pointer associated with the key.
> ** If it is not create a new element for the key in the table and
> ** return the address of its data pointer
> **/

Ditto.

> New File: runtime/mercury_table_int_float_string.h
...
> /* Look to see if the given integer key is in the given table. If it
> ** is return the address of the data pointer associated with the key.
> ** If it is not; create a new element for the key in the table and
> ** return the address of its data pointer
> **/

Ditto.

Also please finish sentences with a full stop.

> /* Look to see if the given float key is in the given table. If it
> ** is return the address of the data pointer associated with the key.
> ** If it is not create a new element for the key in the table and
> ** return the address of its data pointer
> **/

Ditto.

> 
> /* Look to see if the given string key is in the given table. If it
> ** is return the address of the data pointer associated with the key.
> ** If it is not create a new element for the key in the table and
> ** return the address of its data pointer
> **/

Ditto.

> New File: runtime/mercury_table_type_info.c
...
> typedef struct _tree_node {
> 	Word * key;
> 	Word value;
> 	struct _tree_node * right;
> 	struct _tree_node * left;
> } TreeNode;

s/_tree_node/TreeNode_struct/g

> New File: runtime/mercury_tabling.h
...
> #ifndef _MERCURY_TABLING_H
> #define _MERCURY_TABLING_H

s/_MERCURY_TABLING_H/MERCURY_TABLING_H/g

According to the ANSI/ISO C standard,
names starting with _[A-Z] are reserved for use 
by the C implementation.

> #define MR_TABLE_ARRAY(Table, Array)					\
> 	(Word**)0;fatal_error("Tabling of arrays not yet supported")

You shoudl write that as
 	(fatal_error("Tabling of arrays not yet supported"), (Word**)0)

This will ensure that fatal_error() gets called before the dummy
value (Word**)0 is used.

Can't use use the MR_TABLE_ANY macro in this case?

> #ifdef CONSERVATIVE_GC
> 
> #define MR_TABLE_SAVE_ANSWER(Offset, AnswerBlock, Value, TypeInfo)	\
> 	do {								\
> 		(*((Word**)AnswerBlock))[Offset] = Value;		\
> 	} while(0)
> 
> #else /* not CONSERVATIVE_GC */
> 
> #define MR_TABLE_SAVE_ANSWER(Offset, AnswerBlock, Value, TypeInfo)	\
> 	do {								\
> 		(*((Word**)AnswerBlock))[Offset] = 			\
> 			deep_copy(Value, &TypeInfo, NULL, NULL);	\
> 		restore_transient_registers();		  		\
> 	} while(0)

Where's the corresponding call to save_transient_registers()?

> #define table_allocate(Size)                                            \
> 	0;fatal_error("tabling only supported in conservative gc grades")
> #define table_reallocate(Pointer, Size)					\
> 	0;fatal_error("tabling only supported in conservative gc grades")

These should be changed in a manner similar to that described for
the other call to fatal_error() above.

> static void table_printf(const char*, ...);
> static void table_printf(const char *A, ...)
> {

Why the duplicate declarations here?

Also, s/A/a/

Or better, s/A/format/

OK, that's the end of my review for this round.  The number of issues
uncovered in this round means that we will need another round.

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