[mercury-users] New to mercury: structure reuse and efficiency

[Gregory D. Weber]

There are a few of points here that I don't understand.

Peter Schachte writes:
 > Gregory D. Weber wrote:
 > 
 > >There's an implied question here which I don't think has been answered:
 > >how _does_ he do what he wants to do here, which, I believe, is to
 > >make sure that H does not equal T before making the recursive call?
 > >
 > > > member([H|T], H).
 > > > 
 > > > member([H|T], X) :- not(X=H), member(T, X).
 > >  
 > >
 > I think the best answer to your question is:  you don't, the compiler 
 > does it for you.  This definition does what he wants:
 > 
 > member([H|T], H).
 Let's call this rule 1 ...

 > 
 > member([_|T], X) :- member(T, X).
... and this rule 2.

 > 
 > 
 > In fact, it's better than what he's asking for, because the compiler 
 > does it in a more flexible way than you could do it yourself.  The 
 > compiler is smart enough to notice a call member(L, X) where L and  X 
 > are both sure to be ground, and it forces the call to be deterministic 

[Ralph: s/deterministic/semi-deterministic/]

 > for you, 

Am I correct in thinking that you are assuming certain mode declarations,
such as

     :- mode list__member(in, in) is semidet.
     :- mode list__member(out, in) is nondet.

???

> so you don't try to see if the element is in the tail of the 
 > list when you've already seen that it matches the head.  

Why would I (= the member process?) already have seen that it matches the head?
In an earlier message, Ralph said the compiler would freely rearrange code,
but "already" implies that it orders rule 1 before rule 2.  Do we
really know this?  If we do, is it because, as a general principle,
the compiler will always arrange to try a base case rule before 
a recursive step rule?

> However, when X 
 > is unbound, then it will match every element of the list, so you don't 
 > want to commit yourself to the first match.  Consider this predicate to 
 > determine whether two lists have any elements in common:
 > 
 >     overlap(L1, L2) :- member(L1, X), member(L2, X).
 > 
 > Here the first call to member will have X unbound and the second will 
 > have it bound, so the first must not commit to the first match (because 
 > it may not be the first elment of L1 that appears on L2), but the second 
 > one can (because we don't care how many times an element of L1 appears 
 > on L2).  

Again, if the compiler is free to rearrange code, isn't it possible
it tries member(L2, X) first?

> But further, once we find an element in common, we can commit 
 > to that, because we don't care which elements are in common, just that 
 > at least one is.  The Mercury compiler will do all that for you without 
 > you having to say anything.

Except for the mode declarations?  :-)

 > 
 > -- 
 > Peter Schachte              640K should be enough for anyone!
 > schachte at cs.mu.OZ.AU            -- Bill Gates, 1981
 > www.cs.mu.oz.au/~schachte/ 
 > Phone: +61 3 8344 1338     
 > 
 > --------------------------------------------------------------------------
 > 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
 > --------------------------------------------------------------------------
 > 

-- 
Gregory D. Weber

Associate Professor of Computer Science, Indiana University East
2325 Chester Boulevard, Richmond, Indiana 47374-1289, U.S.A.
Telephone: (765) 973-8420         World-Wide Web http://mypage.iu.edu/~gdweber/

----
ASCII plain text is the document format that maximizes readability and 
minimizes hassle and hazard.  It is the format of the official documents
defining Internet protocols (http://www.rfc-editor.org/).


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