[mercury-users] Uniqueness modes etc

[Dr Mark H Phillips]

Thanks for your helpful response!

On Mon, 2003-12-29 at 08:44, Fergus Henderson wrote:
> On 24-Dec-2003, Dr Mark H Phillips <mark at austrics.com.au> wrote:
> >   :- pred r(int, int, int, int).
> >   :- mode r(di, uo, in, out) is det.
> 	r(X, Y, N, Fn) :- ....
[snip]
> 	X = X_0,
> 	Y = X_0,
> 	Q = (pred(N::in, Fn::out) is det :- r(X, Y, N, Fn))
> 
> > Now presumably q could be "applied" to several different n, producing
> > in turn several different fn.  Now r is referentially transparent,
> > but because q has uniqueness modifying behaviour hidden away inside
> > the "currying", q acts as if it is referentially opaque.  Ie, on each
> > application, x_0 may be modified, potentially giving rise to different
> > q behaviour down the track.
> 
> Indeed, if code like this was allowed, that would be a problem.

But would it really be a problem?  This is what I am not sure about.  It
seems very similar to what DCG does.  If I am understanding DCG
correctly, what it does is to hide a thread of state variables from the
user.  If the compiler were to accept:

  Q = (pred(N::in, Fn::out) is det :- r(X_0, X_0, N, Fn))

it would be interpreted as: "each time Q is evaluated, feed in
uniqueness variable X_0 which dies, then create a new uniqueness
variable which we will also call X_0 (okay because the old X_0 is 
dead), ready for feeding in next time Q is evaluated".

In this way a sequence of uniqueness state variables are destroyed
and created, but this sequence is hidden from the user, much like
what DCG does.  So if we allow DCG, why not this?

Are there theoretical problems that allowing Q would introduce, that
DCG does not introduce? 

> > And what is the best way of thinking about these issues?  Ie,
> > this kind of behaviour can be quite useful -- certainly in C++ it can
> > be -- is it a problem or is it theoretically fine?  Or should I be
> > modelling this kind of thing differently.
> 
> If you _want_ this kind of behaviour, then I think the right way of modelling
> it in Mercury would probably be to use a "mutvar" -- see the "store" module
> in the Mercury standard library.  Feel free to ask if you have any questions
> about this approach.

Thanks for the suggestion!  I've done a google search and read a few
things which have given me a rough idea of the concept (I think!).

So using this approach I think what I would be doing is something
like this:

  :- pred r(mutvar(int, S), int, int, S, S)
  :- mode r(in, in, out, di, uo) is det.
  r(X, N, Fn) --> ....
  X_0 ....
  Q = (pred(N::in, Fn::out, ::di, ::uo) --> r(X_0, N, Fn))

(I might have got some of the syntax a bit wrong.)

In this way I could then pass Q to some other procedure which
has no knowledge of X_0.  All the procedure knows is that it
can use Q to pass in an N and get out an Fn, and that behind
the scenes (via DCG on a list of store variables) there are
state changes happening, hence there is no guarantee that
passing in the same N twice will give the same Fn each time.

This approach seems good.  For example it would allow me to 
write a generic, yet efficient, procedure which essentially 
takes a sequence of integer permutations as input and 
computes the result of applying these permutations to 0 a 
certain number of times (10 times for example).

Let me explain what I mean.  Q is effectively a changing
function taking an int to an int.  If each of these functions is
one-to-one and onto (each representing a shuffling of the 
integers) then each is a permutation on the set of integers.
My procedure starts with 0 and applies Q to get the result
of applying the first permutation.  It then takes this result
and applies Q to it, effectively applying the second
permutation.  It repeats this operation 10 times and returns
the final result.

Because I "pass in" the sequence of integer permutations via
a mechanism of uniqueness based mutation, there is the potential
for this sequence to be generated in a very efficient fashion.
In addition, because I am currying the mutvar, I am hiding the
details of the mutation from my procedure, hence ensuring that
my procedure is generic --- ie will work equally well with any
sequence of integer permutations passed in this way.

However, this approach has its limitations (I think).  It is
okay if my procedure only applies the first 10 permutations
generated, but what if I want it to apply the first M 
permutations where M is an input variable?  If I understand
the DCG mechanism correctly, this won't work.  (Perhaps
I am wrong about this??)

This is why I suspect my original idea (of currying a 
di uo pair, feeding the uo back in as di) would actually be 
a better solution.  My concern is that perhaps allowing this
would lead to theoretical limitations??  But perhaps these
could be overcome by introducing into the language a notion
of "mutating pred" and only allowing currying of di uo pairs
inside these special procedures.  This way, any theoretical
limitations introduced would not infect the whole language.
It would also indicate to the user to be wary when using
mutating preds because there are potentially hidden state
changes happening (much like how the use of DCG indicates
the same thing to a user).

Anyway, that's all for now.  Thanks for your help.  I 
would gratefully accept further thoughts or suggestions.

Cheers,

Mark.


--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------