[m-dev.] Associating information with HLDS goals.

Paul Bone pbone at csse.unimelb.edu.au
Thu Dec 27 10:23:04 AEDT 2007

On 27/12/2007, at 4:17 AM, Julien Fischer wrote:

> On Wed, 26 Dec 2007, Paul Bone wrote:
>> I've found that I'd like to associate some extra information with  
>> HLDS goals. This information is only needed locally in  
>> deep_profining.m.  This information describes weather a particular  
>> goal is trivial, and if a port count is available at some point  
>> within or before that goal such that after runtime it can be  
>> determined how often execution reaches the end of that goal.
>> I'm writing a code transformation that works backwards through  
>> HLDS goal structures, and from inside to out.  That is, if it  
>> considers a conjunction, first it will consider the conjunction as  
>> a whole, then each conjunct in reverse order.  This is because  
>> information from goals after the current goal is used in the  
>> decision of whether a coverage point should be inserted after the  
>> current goal.
>> However useful information can also be determined from goals  
>> before the current goal, I believe the easiest way to handle this  
>> is to walk over the HLDS first, in normal order and generate some  
>> information and associate it with each goal.  Then a second pass  
>> in reverse can gather information that can be gathered when  
>> walking over the HLDS in reverse order, it will also apply the  
>> transformation.
>> I could use a map to map each goal to the information associated  
>> with it as found by the first pass, and look up this map for each  
>> goal in the second pass.  I believe this would run in O(N log N)  
>> time.  Using an N-ary tree - A tree where each node may have any  
>> number of sub-trees - I believe I can turn this into linear time.   
>> However it's quite messy, because I have to check that the nary  
>> tree has the same number of branches as there are sub goals of any  
>> goal and throw an exception otherwise in order to keep my code  
>> deterministic.
>> What I would really like is a structure that mimics the hlds_goal  
>> and hlds_goal_expr structures, where the hlds_goal function symbol  
>> takes an extra argument of arbitrary type T.  This would be useful  
>> for me, and will make my code more simple.  I believe this will  
>> likely also be useful for others.  But I'm wondering if this is  
>> the best option of if other similar problems have been solved  
>> differently, or in which module I should add this data structure.
>> Any Advice?
> I suggest extending the hlds_goal_extra_info structure to hold the
> extra information, as we do for the CTGC and RBMM systems.  Adding new
> data structures that mimic the hlds_goal and hlds_goal_expr structures
> would just be a maintainance headache - I don't think that is worth
> doing unless there are particularly good reasons for doing so.

Thanks Julian.

This sounds like the best option.  I'd really like a polymorphic type  
that could be used to associate arbitrary information with a goal, if  
it weren't for the maintenance issue I could have my cake and eat it  


mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au

More information about the developers mailing list