[mercury-users] append for list skeletons

[Peter Schachte]

> Mercury does not support free variable aliasing because it is
> so costly in terms of performance (this is one of the reasons why 
> Mercury is so much faster than Prolog).

There are many steps between Mercury's representation and Prolog's that
would allow at least some partially instantiated terms without loss of
efficiency, providing the compiler can determine *when and where* the
partially instantiated term would definitely become ground.

The simplest case would be to represent two aliased variables, say A and B,
where you know A will be the one that will ultimately be unified with a
ground term, as a pointer from A to B.  When you go to unify A, you simply
follow the pointer to update both A and B to point to the new term.  If more
than two variables may be aliased, they can be chained together, so binding
one enters a loop which follows the chain setting all variables to the same
term.  If you can't tell which of the aliased variables will be bound, you
can represent them as a circular list, and then bind them by following
around the list setting all elements to the new term until you get back
where you started.

All of these could be done without changing how other Mercury terms are
represented, and without changing the performance of other Mercury
operations.  Ie, this would cause no distributed fat (at least if restricted
to the det case).


> > Therefore the
> > naive/inefficient implementation of reverse
> > 
> > rev([], []).
> > rev([H|T], R) :-
> >     append(RT, [H], R), rev(T, RT).
> > 
> > will not be implementable for list skeletons?
> 
> That's correct.
> 
> Mercury requires quite a different programming style to Prolog, more
> in line with languages like ML.

In other words, Mercury is less like a constraint programming language, and
more like a functional language.  OTOH, there are parts of Mercury (eg
mode-driven reordering) where Mercury is more like a constraint language
than Prolog.

> Many of the cunning tricks you have
> to use in Prolog with partially instantiated structure (e.g. the 
> sort of difference structures you are describing here) are just 
> efficiency hacks; there are few places, in my opinion, where their 
> use doesn't make code less legible.

I think the definition of rev/2 above is very readable; more readable than
the non-naive one.  Or take this traditional Prolog definition of 
front(L, N, F) that constrains F to be the first N elements of L:

	front(L, N, F) :-
		length(F, N),
		append(F, _, L).

I think this is more readable and intuitive than the constructive version
you would write in Mercury.  The ability to specify a value by giving the
constraints it must satisfy is very powerful and intuitive to me.


-- 
Peter Schachte <schachte at cs.mu.OZ.AU>  Do, or do not. There is no 'try'.
http://www.cs.mu.oz.au/~schachte/      -- Yoda ('The Empire Strikes Back') 
Phone:  +61 3 8344 9166                
Fax:    +61 3 9348 1184                
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------