[mercury-users] Collections of closures [polymorphic insts]

[Ralph Becket]

I've been doing some thinking about the
business of polymorphic insts which are
needed if we're to avoid the dodgy hacks
we've been discussing in this thread (many
thanks to Fergus et al. for the solution,
btw.)  These thoughts are only slightly
more advanced than those of the "it occurred
to me in the shower that..." variety, but 
it would be good to do some brainstorming,
even if all we end up with is a better
understanding of the problem.

It occurs to me that mode/inst info. is
required for three things:
1. working out which procedure to call;
2. determinism checking; and
3. uniqueness checking.

At any point in the execution of a program,
each variable in scope is either free or
bound to some value.  For the sake of
argument let us assume that these values are
ground members of some type (e.g. int, string,
list(bool) etc.) [I don't want to worry about
bound(...) restrictions and partially
instantiated structures for now.]

The two most common argument modes are

:- mode in :: ground -> ground.
:- mode out :: free -> ground.

These are sufficient to describe the vast
majority of modes that we're interested in.
The compiler uses mode information to decide
whether a particular varible is going to be
free or bound to a (ground) value at each
point in the computation.

A problem arises with higher order values.
Higher order values have their own insts
which are special forms of the ground inst.

Consider

:- func app(func(T1) = T2, T1) = T2.
:- mode app(func(in) = out, in) = out.

app(F, X) = F(X).

The first argument to app/2 needs a fancy
inst because the compiler has to be able to
check that the body of app/2 calls it in the
correct mode.  A similar argument applies to
functions that return other functions.

So we definitely need higher order insts.  The
key problem lies with functions that return
other functions (perhaps without knowing it).

For example, if Fns is a list of 
func(int::in) = int::out is det
procedures and we have

:- func nth(list(T), int) = T.
:- mode nth(in, in) = out is det.

nth([], _) = error("...").
nth([H|T], N) = ( if N = 0 then H else nth(T, N-1) ).

then, assuming Fns is long enough, after

F = nth(Fns, 3)

we have an object of *type* `func(int) = int' in F,
but unfortunately F is in inst ground, not
func(in) = out is det.  So we can't apply F to
anything because mode analysis will tell us that it
can't verify that we will be applying F correctly
and hence will forbid any such activity.  [Note that
we can pass Fns as an `in' argument since func insts
are special cases of the ground inst, as mentioned
above.]

Since the library writer can't anticipate every
higher order object that might be passed as an
argument (e.g. inserting functions into lists, trees,
maps etc.) we end up with libraries that really don't
work very well with higher order code.

Hence we need polymorphic insts and modes.

Now it seems to me that we can have polymorphic insts
in much the same was as we can have polymorphically
typed arguments provided we accept that there are only
a limited number of things one can do with such
arguments.

As far as I can see, if variable X is in inst I, where
I is polymorphic (i.e. unknown) then all I can do with
X is
(a) copy it (provided I isn't known to be unique), and
(b) pass it as an argument to something expecting its
argument to have inst I, and
(c) return it, and
(d) that's it.
I can't even test X for equality with some other Y since
the test for equality may be structural and I don't know
that X *has* any structure yet.

But this is fine.

Consider the following mode for nth/2 above (I'm supplying
the parametric modes in/1 and out/1 just for reference and
the list_skel/1 inst):

:- mode in(I) :: I -> I.
:- mode out(I) :: free -> I.

:- inst list_skel(I) = bound([] ; [I | list_skel(I)]).

:- mode nth(in(list_skel(I)), int) = out(I) is det.

The code for nth/2 doesn't do anything with the members of
the list argument other than ignore them or return them. So
the polymorphic inst rules are satisfied.  What's more,
after

F = nth(Fns, 3)

we can show that F has inst `func(in) = out is det' which
we can do something sensible with.

We can also show higher order stuff in action:

:- func app(func(T1) = T2, T1) = T2.
:- mode app(in(func(I1) = I2), in(I1)) = out(I2) is det.

F = app(nth(Fns), 3)

obtaining the same result.

The only problemette I can think of with this scheme is
what do you do when you copy a free variable?  One
possibility is that you end up with an alias of that
variable, but I've half convinced myself that you
should really get a new free variable instead.

Anyway, I look forward to hearing what people think.

Cheers,

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