benign destructive update (was: add lazy evaluation to library)

[Fergus Henderson]

On 10-Mar-1999, Peter Schachte <schachte at cs.mu.OZ.AU> wrote:
> > :- pragma c_code(
> > 	update_closure(MercuryTerm::in, NewValue::in),
> > 	[will_not_call_mercury],
> > "{
> > 	/* strip off tag bits */
> > 	Word *ptr = (Word *) strip_tag(MercuryTerm);
> > 	/* destructively update value */
> > 	*ptr = NewValue;
> > }").
> 
> This is something, I would argue, that should be encapsulated in a
> module somewhere in the standard library.  As it is, there's no
> portable way to replace something with something equal, and it is
> something that will come up occasionally when you have a user-defined
> equality predicate for a type, and some values of that type are more
> efficient in some way than others.  Sure, it's a module with an impure
> interface, but it would be very useful in building efficient perfectly
> pure modules.

I agree.

Actually I copied the above code from the code for untrailed_setarg
in extras/trailed_update/var.m, and when I was doing so, I considered adding
setarg and untrailed_setarg to the standard library.  However, doing that
wouldn't work, because (1) there's no way to guarantee that things won't
be put in ROM, and (2) there's no way to guarantee that the representation
will use any indirection at all (consider no_tag types).
Another problem is that (3) a truly generic version of setarg requires
quite a bit of overhead, due to the costs of interpreting the RTTI
to find out the offset of the argument.

However, the functionality of update_closure is less general than that
of setarg, and this actually gives a hint on how we can solve these problems.
We can solve (1), (2), and (3) by defining a special type, called say
mutable(T), for which these guarantees do hold.  The type mutable(T) would be
implemented as a pointer to T, and there'd be operations to construct
a mutable(T) from a T, to destructively update a mutable(T), and to
dereference the pointer to get a T from a mutable(T).

Another alternative would be to have a `pragma mutable(<typename>/<arity>)';
then we could provide setarg, but only for types which have been declared
`pragma mutable'.  This approach could be a bit more efficient, because
the compiler might be able to use one level of indirection in cases where
using mutable(T) might require two.  However, it only solves (1) and (2),
not (3), and in addition, it's not statically type-safe.

Solving (3) would require using an even less safe version of setarg,
analagous to store__unsafe_new_arg_ref, and with the same kind of
restrictions.  See the following quote from the documentation in
library/store.m:

	%
	% Nasty performance hacks
	%
	% WARNING: use of these procedures is dangerous!
	% Use them only only as a last resort, only if performance
	% is critical, and only if profiling shows that using the
	% safe versions is a bottleneck.
	%
	% These procedures may vanish in some future version of Mercury.

		% `unsafe_arg_ref' is the same as `arg_ref',
		% and `unsafe_new_arg_ref' is the same as `new_arg_ref'
		% except that they doesn't check for errors,
		% and they don't work for `no_tag' types (types with
		% exactly one functor which has exactly one argument),
		% and they don't work for types with >4 functors.
		% If the argument number is out of range,
		% or if the argument reference has the wrong type,
		% or if the argument is a `no_tag' type,
		% then the behaviour is undefined, and probably harmful.

The magic number 4 in the "not >4 functors" restriction is particularly ugly
and implementation-dependent.

Given these disadvantages, I prefer the approach of using a new type
rather than `pragma mutable'.  Comments?

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