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

[Warwick Harvey]

Fergus wrote:
> On 23-Mar-1999, Warwick Harvey <wharvey at cs.monash.edu.au> wrote:
> > 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?

We'd like to avoid the level of indirection if we know something is ground 
(so you only pay when you need it).  In particular, we (originally) wanted 
to be able to pass a (now) ground data structure to a Mercury library 
predicate, and have it work.  This seems perhaps a little less useful now, 
since we're going to want to add new modes to many of the (Mercury) library 
predicates, which means we may end up building our own library anyway...  
But I digress.

Anyway, we're using a Parma binding scheme, which means any references to a 
variable embedded in some data structure are updated when the variable is 
bound.  We could do this for "standalone" copies of the variable too, except 
that we don't really want to add to the Parma chain every time Mercury 
copies the variable.  So we only add it when constructing new terms, etc.  
The "standalone" copies are (currently) intended to be handled properly by 
their modes: if the compiler thinks it's `any', it gets extra checks; if the 
compiler thinks it's bound, it skips the checks.  Then if we just make sure 
the variable is dereferenced and possibly updated any time there's a 
transition from `any' to `bound', it should all work.  :-)

> 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)?

Since `dump/3' takes something of inst `any', it is obliged to dereference 
it somehow (probably by checking that it is in a suitable state) before 
printing it.

If `dump/3' took something of inst `ground' and Mercury's alias analysis was 
smart enough to realise that `Z' was in fact ground, then I suspect the HAL 
compiler would have already rejected the program during mode analysis, 
unless it too was smart enough to realise this, in which case it would make 
sure `Z' was dereferenced before passing it to `dump'.

[ Is this where you point out a fatal flaw in this scheme?  ;-]

> > 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).  
> 
> That would be straight-forward, but extremely tedious, to implement.

OK, thanks for the info.

Warwick