[m-dev.] Term representation and `any' insts - HAL

[Fergus Henderson]

On 23-Mar-1999, Warwick Harvey <wharvey at cs.monash.edu.au> wrote:
> Hi folks,
> 
> As many of you are aware, we are making heavy use of `any' insts for 
> "solver" variables when compiling HAL to Mercury.  With the alias tracking 
> code as of a month or so ago, it appears we can get Mercury to accept a 
> variable's transition from `any' to `ground' (say) --- many thanks to those 
> involved in the alias code.  This is mainly needed for situations where the 
> HAL compiler knows more about a variable's instantiation than the Mercury 
> compiler can --- it allows us to do instantiation coercions, for instance.
> 
> However, there is a further problem, for the situation where a variable goes 
> from `any' to `bound(...)' (nothing to do with analysis this time).  This 
> mainly relates to variables using the Herbrand solver, when we know the 
> top-level functor has become bound.  The problem really stems from our 
> representation of Herbrand variables --- we reserve a (primary) tag in the 
> discriminated union, which means that the representation of a `free' 
> variable is different (in the top-level word) from that of a bound variable. 
>  This means a variable's representation can change when going from `any' to 
> `bound(...)' or `ground'.  Unfortunately (for us), when it comes to code 
> generation, Mercury seems to assume that `any' and `ground' are the same 
> representation.

Basically yes: Mercury assumes that an `any' inst which at runtime
happens to be ground will be represented in the same way as as a
`ground' inst.

> That is, if one passes a variable to a predicate which 
> changes it from `any' to `bound(...)', Mercury assumes the representation 
> hasn't changed, and continues to use the `any' copy of the variable 
> (basically, it does not return the new representation from the predicate).
> 
> Now, we could work around this in our own code generation by introducing a 
> new argument whenever the instantiation of a variable changes like this, but 
> doing this seems annoying and error-prone.  :-)  So instead, I was wondering 
> whether it might be better/easier to solve it at the Mercury end.
>
> So basically, I'm looking for comments on any or all of the following:
> 
> - Is the assumption that the representation doesn't change for any -> bound 
> a reasonable one?

The presumption was that cases like this would be handled in the same
way that Prolog handles them, by using a level of indirection,
and thus passing a pointer in rather than passing a value in and a value out.

Is there any particular reason why you don't want to use that technique?

I don't see how your proposed technique could work, in general,
since there might be other copies of the `any' inst around.
Consider the following code:

	:- pred p(herbrand, io__state, io__state).
	:- mode p(in(any), di, uo) is cc_multi.
	p(X) -->
		{ id(X, Y, Z) },
		{ bind(Y) },
		dump(Z).

	:- pred id(T, T, T).
	:- mode id(in(any), out(any), out(any)).
	id(X, X, X).

	:- pred bind(herbrand).
	:- mode bind(any -> ground).

	:- pred dump(herbrand, io__state, io__state).
	:- mode dump(any -> any, di, uo) is cc_multi.

With your scheme, how would the call to bind(Y) bind the value of the
aliased variable Z, as is needed for the subsequent call to dump(Z)?

> On a somewhat related topic, it would be useful for us if there were an 
> instantiation `bound/0', which basically means the top-level functor is 
> bound, but its arguments are `any' (i.e. it tailors itself to the type 
> similarly to `ground', but only applies to the top level of the type tree).  
> Currently we just generate an instantiation for each type separately, but of 
> course this doesn't work for polymorphic predicates.  That hasn't been a 
> problem yet, but it could be in the future.  This seems like a much bigger 
> change than the one above, and hence seems less likely that I will do 
> anything about it, but I thought it might be worth at least thinking about 
> while doing the above.

That would be straight-forward, but extremely tedious, to implement.

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