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

[Fergus Henderson]

On 09-Mar-1998, Oliver Hutchison <ohutch at students.cs.mu.oz.au> wrote:
> Index: library/mercury_builtin.m
> ===================================================================
> RCS file: /home/staff/zs/imp/mercury/library/mercury_builtin.m,v
> retrieving revision 1.93
> diff -u -r1.93 mercury_builtin.m
> --- mercury_builtin.m	1998/02/25 00:11:53	1.93
> +++ mercury_builtin.m	1998/03/02 03:17:08
> @@ -899,6 +899,729 @@
>  ").
>  
>  
> +:- interface.
> +:- import_module char.

It might be better to use `character' here in mercury_builtin.m
rather than doing `import_module char' in the interface.
Otherwise we'll have to read in char.int3 for every compilation
(plus the int3 files for any modules imported in the interface
of char.m, transitively).  It just seems better for the
interface to `mercury_builtin' to be completely self-contained.

> +:- type table.
> +
> +
> +:- impure pred get_table(table).
> +:- mode get_table(out) is det.
> +
> +
> +:- semipure pred table_working_on_ans(table).
> +:- mode table_working_on_ans(in) is semidet.
> +
> +:- impure pred table_mark_as_working(table).
> +:- mode table_mark_as_working(in) is det.
> +
> +:- impure pred table_loopcheck_error is erroneous.
> +
> +
> +:- impure pred table_lookup_insert_int(table, int, table).
> +:- mode table_lookup_insert_int(in, in, out) is det.
> +
> +:- impure pred table_lookup_insert_char(table, char, table).
> +:- mode table_lookup_insert_char(in, in, out) is det.
> +
> +:- impure pred table_lookup_insert_string(table, string, table).
> +:- mode table_lookup_insert_string(in, in, out) is det.
> +
> +:- impure pred table_lookup_insert_float(table, float, table).
> +:- mode table_lookup_insert_float(in, in, out) is det.
> +
> +:- impure pred table_lookup_insert_enum(table, int, T, table).
> +:- mode table_lookup_insert_enum(in, in, in, out) is det.
> +
> +:- impure pred table_lookup_insert_user(table, T, table).
> +:- mode table_lookup_insert_user(in, in, out) is det.
> +
> +:- impure pred table_lookup_insert_poly(table, T, table).
> +:- mode table_lookup_insert_poly(in, in, out) is det.
> +
> +
> +:- semipure pred table_have_ans(table).
> +:- mode table_have_ans(in) is semidet. 
> +
> +:- semipure pred table_has_failed(table).
> +:- mode table_has_failed(in) is semidet.
> +
> +
> +:- impure pred table_create_ans_block(table, int, table).
> +:- mode table_create_ans_block(in, in, out) is det.
> +
> +:- impure pred table_save_int_ans(table, int, int).
> +:- mode table_save_int_ans(in, in, in) is det.
> +
> +:- impure pred table_save_char_ans(table, int, char).
> +:- mode table_save_char_ans(in, in, in) is det.
> +
> +:- impure pred table_save_string_ans(table, int, string).
> +:- mode table_save_string_ans(in, in, in) is det.
> +
> +:- impure pred table_save_float_ans(table, int, float).
> +:- mode table_save_float_ans(in, in, in) is det.
> +
> +:- impure pred table_save_any_ans(table, int, T).
> +:- mode table_save_any_ans(in, in, in) is det.
> +
> +:- impure pred table_save_failure(table).
> +:- mode table_save_failure(in) is det.
> +
> +
> +:- semipure pred table_restore_int_ans(table, int, int).
> +:- mode table_restore_int_ans(in, in, out) is det.
> +
> +:- semipure pred table_restore_char_ans(table, int, char).
> +:- mode table_restore_char_ans(in, in, out) is det.
> +
> +:- semipure pred table_restore_string_ans(table, int, string).
> +:- mode table_restore_string_ans(in, in, out) is det.
> +
> +:- semipure pred table_restore_float_ans(table, int, float).
> +:- mode table_restore_float_ans(in, in, out) is det.
> +
> +:- semipure pred table_restore_any_ans(table, int, T).
> +:- mode table_restore_any_ans(in, in, out) is det.

All these predicates should be documented.

> +:- implementation.
> +
> +:- type table == c_pointer.
> +
> +:- pragma c_header_code("
> +
> +#define ML_WORKING_ON_ANS 1
> +#define ML_FAILED 2

What about

	#define ML_FOUND_ANSWER 0

?

Some documentation about what these numbers are used for might be useful.

Would it be better to use an enum rather than #define?

> +:- pragma c_code(get_table(T::out), "
> +	T = 0;
> +").

Some documentation is needed here.
What does this magic number `0' mean here?

> +:- pragma c_code(table_working_on_ans(T::in), "
> +	TABLE_PROFILE_CALL(WorkingOnAns);

Where is `WorkingOnAns' defined?
I think that the capitalization of that name must not fit
our coding guidelines.

> +	if (*((Word*) T) == ML_WORKING_ON_ANS) {
> +		SUCCESS_INDICATOR = 1;
> +	} else {
> +		SUCCESS_INDICATOR = 0;
> +	}

You can just do

	SUCCESS_INDICATOR = (*((Word*) T) == ML_WORKING_ON_ANS);

But how do you know that the value passed will be a pointer?

> +:- pragma c_code(table_loopcheck_error, "
> +	exit(-1);
> +").

Wouldn't it be better to call error/1, to (a) print out an error message and
(b) get a stack trace?

> +:- interface.
> +
> +:- impure pred table_setup(table, table).
> +:- mode table_setup(in, out) is det.
> +
> +:- semipure pred table_return_all_ans(table, table).
> +:- mode table_return_all_ans(in, out) is nondet.
> +
> +:- impure pred table_get_ans_table(table, table).
> +:- mode table_get_ans_table(in, out) is det.
> +
> +
> +:- semipure pred table_have_all_ans(table).
> +:- mode table_have_all_ans(in) is semidet.
> +
> +:- semipure pred table_have_some_ans(table).
> +:- mode table_have_some_ans(in) is semidet.
> +
> +:- semipure pred table_new_ans(table).
> +:- mode table_new_ans(in) is semidet.
> +
> +
> +:- impure pred table_mark_have_some_ans(table).
> +:- mode table_mark_have_some_ans(in) is det.
> +
> +:- impure pred table_mark_have_all_ans(table).
> +:- mode table_mark_have_all_ans(in) is failure.
> +
> +:- impure pred table_mark_as_returned(table).
> +:- mode table_mark_as_returned(in) is det.
> +
> +
> +:- impure pred table_suspend(table, table).
> +:- mode table_suspend(in, out) is nondet.
> +
> +:- impure pred table_resume(table).
> +:- mode table_resume(in) is failure.
> +
> +
> +:- impure pred table_new_ans_slot(table, table).
> +:- mode table_new_ans_slot(in, out) is det.

Documentation needed here...

> +:- implementation.
> +
> +:- pragma c_header_code("
> +
> +typedef struct {
> +	Word AnsNum;
> +	Word Ans;
> +} AnswerListNode;

Field names should be lower-case: 

	typedef struct {
		Word ans_num;
		Word ans;
	} AnswerListNode;

The same comment applies in many places in this file.

> +#define ML_HAVE_NO_ANS 0
> +#define ML_HAVE_ALL_ANS 1
> +#define ML_HAVE_SOME_ANS 2

It would probably be better to use an `enum'.

> +#define ML_ANS_USED 1

Documentation needed here.

> +#ifdef MR_TABLE_DEBUG
> +void dump_table(NondetTable *);
> +#else
> +#define dump_table(A)
> +#endif

Please indent #ifdef'd code by two spaces:

	#ifdef MR_TABLE_DEBUG
	  void dump_table(NondetTable *);
	#else
	  #define dump_table(A)
	#endif

> +:- pragma c_code(table_setup(T0::in, T::out), "
> +	/* Init the table if this is the first time me see it */

Your `pragma c_code' fragments should explicitly specify
`will_not_call_mercury'.  This is particularly important
for the ones that call list_cons() or list_empty()...
(See the "memory management" section of the "c interface"
section of the "pragmas" chapter of the Mercury Language Reference Manual.)

> +table_return_all_ans(T, A) :-
> +	semipure table_return_all_ans_list(T, AList),
> +	list__member(Node, AList),
> +	semipure table_return_all_ans2(Node, A).

s/ans2/ans_2/g

> +Integer ML_resumption_SP = -1;
> +Word ML_resumption_stack_size = 256;	/* Half the inital size of 
> +						the stack */

s/inital/initial/

> +Define_entry(mercury__table_resume_1_0);
> +
> +	dump_table(NON_TABLE(r1));
> +	
> +	if (list_is_empty(NON_TABLE(r1)->AnswerList) ||
> +		list_is_empty(NON_TABLE(r1)->SuspendList))
> +	{
> +		SUCCESS_INDICATOR = 0;

s/0/FALSE/

> +		proceed();
> +	}
> +
> +	ML_RESUME_PUSH();
> +
> +	ML_RESUME_VAR->Table = NON_TABLE(r1);
> +	ML_RESUME_VAR->NonStackBlockSize = (Word) MR_maxfr -
> +		(Word) ML_RESUME_VAR->Table->NonStackBottom;
> +	ML_RESUME_VAR->DetStackBlockSize = (Word) MR_sp - 
> +		(Word )ML_RESUME_VAR->Table->DetStackBottom;

s/ )/) /

Also, to get the difference between two pointers as a size in bytes,
it would be better to cast the pointers to `char *' rather than to Word.
Casting to Word might give incorrect results on segmented architectures.

> +	ML_RESUME_VAR->SuccIP = MR_succip;
> +	ML_RESUME_VAR->SP = MR_sp;
> +	ML_RESUME_VAR->CurFr = MR_curfr;
> +	ML_RESUME_VAR->MaxFr = MR_maxfr;
> +
> +	ML_RESUME_VAR->changed = 1;
> +	
> +	ML_RESUME_VAR->NonStackBlock = (Word *) table_allocate(
> +		ML_RESUME_VAR->NonStackBlockSize);
> +	table_copy_mem(ML_RESUME_VAR->NonStackBlock, 
> +		ML_RESUME_VAR->Table->NonStackBottom, 
> +		ML_RESUME_VAR->NonStackBlockSize);
> +	
> +	ML_RESUME_VAR->DetStackBlock = (Word *) table_allocate(
> +		ML_RESUME_VAR->DetStackBlockSize);
> +	table_copy_mem(ML_RESUME_VAR->DetStackBlock, 
> +		ML_RESUME_VAR->Table->DetStackBottom, 
> +		ML_RESUME_VAR->DetStackBlockSize);
> +		
> +Define_label(ChangeLoop);

Label names are basically global,
so this should probably be

	Define_label(mercury__table_resume_1_0_change_loop);

or something like that, to avoid name clashes.

> Index: runtime/mercury_string.h
> ===================================================================
> RCS file: /home/staff/zs/imp/mercury/runtime/mercury_string.h,v
> retrieving revision 1.8
> diff -u -r1.8 mercury_string.h
> --- mercury_string.h	1998/02/03 08:17:22	1.8
> +++ mercury_string.h	1998/02/17 02:20:12
> @@ -125,9 +125,9 @@
>  
>  #ifdef __GNUC__
>  #define hash_string(s)					\
> -	({ int hash;					\
> -	   do_hash_string(hash, s);			\
> -	   hash;					\
> +	({ int _hash;					\
> +	   do_hash_string(_hash, s);			\
> +	   _hash;					\
>  	})
>  #endif
...
>  #define HASH_STRING_FUNC_BODY				\
> -	   int hash;					\
> -	   do_hash_string(hash, s);			\
> -	   return hash;
> +	   int _hash;					\
> +	   do_hash_string(_hash, s);			\
> +	   return _hash;

Names starting with `_' are reserved for use by the C implementation
in certain contexts.

So I'd rather you change it to say `hash_string_result'
rather than `_hash'.

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