[mercury-users] support for Prolog variables

[Fergus Henderson]

On 08-Sep-1998, Peter Schachte <pets at cs.mu.OZ.AU> wrote:
> On Tue, Sep 08, 1998 at 05:06:43AM +1000, Fergus Henderson wrote:
> 
> > Prolog-style variables aren't very useful most of the time.
> > They can make programs harder to understand, they make static
> > checking difficult, and they can be very costly efficiency-wise.
> > So we certainly don't want them to be the default.
> > 
> > However, occaisionally you do want to do some constraint solving on
> > Herbrand terms.  We do want to have a solution for those relatively
> > rare occaisions, and that is what the `var' module is for.
> 
> I don't want to pick nits, and this is a philosophical issue, but I
> find it interesting that you look at this issue this way.  To me,
> you're always doing constraint solving on Herbrand terms (or other
> data structures).

Yes, I agree with this...

> Most of these constraints can be solved in a
> straightforward linear sort of way, but some can't.  Currently,
> Mercury can handle the former sort (modulo aliasing problems), but not
> the latter.

I'd talk about "statically moded" rather than "linear", and
"prior to 0.7.2" rather than "currently" (since 0.7.2 added
support for `any' insts), but apart from those minor differences,
I'm still in agreement...

> The var module and any inst are a way to handle the
> latter sort, but unfortunately this solution requires using different
> types.

I'd say the unfortunate thing is that dynamic moding requires
a less efficient representation.

It's reasonable to see the use of a different type as a disadvantage,
but I think this is less of a disadvantage than the disadvantages
that you get if you use a single type and different representations
(see below).

> The nicer solution (to my tastes) would be to allow both sorts
> of constraints over the same types (though not necessarily the same
> representations), using the most efficient method in each case.  This,
> I believe, is what HAL is trying to do.

The trouble with this is that the implementation has to either use the less
efficient representations everywhere, or do implicit conversions between
different representations. 

If the compiler does implicit conversion between different representations,
then you run into some difficulties.  Such implicit conversions can be very
costly, because they may require copying a whole data structure (e.g.
converting a `list(var(int))' to a `list(int)'); this is bad not only
because it makes things slow but also because implicit insertion of O(n)
operations makes it very difficult for users to predict performance of
their programs.  So this approach does not seem very attractive.

Using the less efficient representations everywhere is not very
attractive for a general-purpose programming language, since it means
you pay a significant efficiency penalty even in code that doesn't use
constraints at all.  If constraint solving is your main application
area, as is the case for HAL, then this is a reasonable choice.  But
for Mercury, I don't think constraint solving code will be frequent
enough to make this trade-off worthwhile.

Mercury programmers can still write constraint solving code, of course;
the distinction between types such as `int' and `var(int)' just means
that they need to be explicit about when representation changes occur.

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