[mercury-users] partially instantiated data structures

[Fergus Henderson]

Peter Schachte <schachte at cs.mu.OZ.AU> wrote:
> Fergus Henderson wrote:
> > (In fact the Mercury solution in such cases is quite likely just as
> > efficient as the Prolog solution, despite the copying, because of the
> > efficiency advantages of Mercury's compile-time mode analysis.
> 
> I don't think that's a very meaningful comparison.  If you're saying
> that "well, Prolog may be a bit faster here, but Mercury is so much
> faster everywhere else that it wins overall," then I certainly agree,

No, I meant that even for code using this technique, Mercury is quite
likely just as fast, possibly faster.  I was basically comparing the
costs of copying with the costs of dynamic moding.  There are other
differences between Mercury and Prolog that affect efficiency, of course,
such as the availability of static type and determinism information,
but static modes are the most important one as far as efficiency is concerned.

> but that doesn't mean Mercury couldn't use a variant of the Prolog
> implementation strategy and do even better

With the current Mercury implementation, you could use something quite
analagous to the Prolog technique: you could use `any' insts (dynamic moding)
and the `var' type defined in extras/trailed_update/var.m for such cases.
However, I suspect that the overhead of dynamic moding and the `var' type
would be at least as high as the overhead of copying.
(I'm just guesstimating here, I haven't done any actual measurements.)

The overhead could be reduced by having the compiler reserve separate tags
for uninstantiated variables, say with some annotation on type definitions,
rather than using the `var' type.  But even then I suspect the cost of
dynamic moding would still be similar to the cost of copying.

We do hope to eventually support statically moded partially instantiated
data structures in Mercury.  That would be significantly more efficient
than either of these two approaches (the copying solution or the solution
using dynamic moding).

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