[mercury-users] partially instantiated data structures

[Warwick Harvey]

Fergus wrote:
> 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.
[...]

Well, we can actually try this, right now.  If somebody wants to write some 
Mercury code that does something like this by copying, I'm happy to adapt it 
(assuming it's not *too* big!) to fill the fields in dynamically, feed it 
into HAL, and we'll see what we get.

There are things one could put into the example to make the HAL version 
perform badly (as well as things that are just not implemented yet --- e.g. 
please steer clear of requiring unbound variables to be put in a polymorphic 
data structure), but it'd give us a starting point.

For those who don't know, HAL is a constraint logic programming language 
which is compiled to Mercury.  We've introduced several new grade components 
to add extra features we want in the Mercury run-time.  One of these is to 
reserve a tag (as Fergus mentioned as a possibility in his mail) for use in 
implementing "true" Herbrand variables (i.e. aliasing, putting unbound vars 
in data structures, etc.).  We use a Parma binding scheme so that once a 
data structure is ground it looks just like a Mercury data structure (modulo 
the reserved tag).  The results so far for the Herbrand solver are quite 
promising, with Prolog-like speed when no type/mode/determinism is given (we 
hope to improve this when we get proper indexing happening for non-Mercury 
modes) and Mercury-like speed when full Mercury type/mode/determinism is 
given.

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