[m-dev.] EDCG inferrence

[Fergus Henderson]

On 14-Feb-2000, Peter Nicholas MALKIN <pnmalk at students.cs.mu.oz.au> wrote:
> However I have a slight problem with integrating hidden argument inferrence,
> with the type inferrence system. The problems stems from the same reason that
> I cannot implement the translation at the same time as purity for efficiency.
> The problem is that the way in which the type checking mechanism traverses
> the hlds data is not compatable with the way required for EDCGs.
> 
> i.e. Disjunctions and if-then-elses are traversed in the same way as
> conjunctions. For EDCGs each disjunct must be traversed separately and the
> results combined and similarly for if-then-elses.
> 
> I cannot see a feasable way around this except for writing it separately.

Well, you could save and restore the information that
you need for EDCG inference, similarly to the way that
mode analysis saves and restores the instmap.

E.g. instead of

	process(if_then_else(Cond, Then, Else)) -->
		process(Cond),
		process(Then),
		process(Else).

you would have

	process(if_then_else(Cond, Then, Else)) -->
		% save initial edcg_info state
		get_edcg_info(State0),

		% process the cond & the `then' branch
		process(Cond),
		process(Then),

		% save edcg_info state after the `then' branch
		% and restore initial edcg_info state
		get_edcg_info(StateAfterThen),
		set_edcg_info(State0),

		% process the `else' branch
		process(Else),

		% get edcg_info state after then `else' branch and
		% merge it with the state saved after then `then' branch
		get_edcg_info(StateAfterElse),
		{ merge_edcg_info(StateAfterThen, StateAfterElse, State) },
		set_edcg_info(State).

Hmm... that doesn't quite work, because type inference
is doing a breadth-first search over a set of different
type assignments, and the edcg_info may be different
for each different type assignment.

However, I think you can solve that problem by keeping the state
that you need to save as a part of the type_assign.  In particular,
you can keep in each type_assign a _stack_ of edcg_infos, and then use
"dup", "swap", and "merge" operations on the stack:

	process(if_then_else(_Vars, Cond, Then, Else, _SM)) -->
		% save initial edcg_info state
		for_each_type_assign(edcg_info_stack_dup),

		% process the cond & the `then' branch
		process(Cond),
		process(Then),

		% save edcg_info state after the `then' branch
		% and restore initial edcg_info state
		for_each_type_assign(edcg_info_stack_swap),

		% process the `else' branch
		process(Else),

		% get edcg_info state after then `else' branch and
		% merge it with the state saved after then `then' branch
		for_each_type_assign(edcg_info_stack_merge).

Here the `for_each_type_assign' operation would just
map over each type_assign in the type_assign_set,

	:- type type_info ---> type_info(
		/* ... */
    		type_assign_set :: list(type_assign)
	).
	:- type type_assign ---> type_assign(
		/* ... */
    		edcg_info_stack :: stack(edcg_info)
	).

	:- pred for_each_type_assign(func(type_assign) = type_assign,
    		type_info, type_info).
	:- mode for_each_type_assign(in, in, out) is det.
	for_each_type_assign(F, TI,
		TI^type_assign_set := list__map(F, TI^type_assign_set)).

while the stack operations would be quite straight-forward:

	:- func edcg_info_stack_dup(type_assign) = type_assign.
	:- func edcg_info_stack_swap(type_assign) = type_assign.
	:- func edcg_info_stack_merge(type_assign) = type_assign.
	edcg_info_stack_dup(TA) =
		TA^edcg_info_stack := dup(TA^edcg_info_stack).
	edcg_info_stack_swap(TA) =
		TA^edcg_info_stack := swap(TA^edcg_info_stack).
	edcg_info_stack_merge(TA) =
		TA^edcg_info_stack := merge(TA^edcg_info_stack).

	% duplicate the top element on the stack
	:- func dup(stack(T)) = stack(T).
	dup(Stack) = stack__push(Stack, stack__top_det(Stack)).

	% swap the top two elements on the stack
	:- func swap(stack(T)) = stack(T).
	swap(Stack0) = stack__push(stack__push(Stack2, X), Y) :-
		stack__pop_det(Stack0, X, Stack1),
		stack__pop_det(Stack1, Y, Stack2).

	% merge the top two elements on the stack
	% using merge_edcg_info
	:- func merge(stack(edcg_info)) = stack(edcg_info).
	merge(Stack0) = Stack :-
		stack__pop_det(Stack0, X, Stack1),
		stack__pop_det(Stack1, Y, Stack2),
		Stack = stack__push(Stack2, merge_edcg_info(X, Y)).

	:- func merge_edcg_info(edcg_info, edcg_info) = edcg_info.
	merge_edcg_info(_, _) = _ :-
		...

Is that clear?

-- 
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.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------