[m-rev.] for review: improvements to relation.m

[Mark Brown]

On 05-Sep-2007, Julien Fischer <juliensf at csse.unimelb.edu.au> wrote:
>
> On Wed, 5 Sep 2007, Mark Brown wrote:
>
>> Estimated hours taken: 2
>> Branches: main
>>
>> Improvements to the relation module.
>>
>> library/relation.m:
>> 	Change the type relation_key/0 to relation_key/1.  The argument is
>> 	a phantom type which provides some extra type safety.
>>
>> 	Document this module using more consistent terminology.  In
>> 	particular, for relation(T) an "element" refers to a value of
>> 	type T, a "key" is of type relation_key(T), and an "edge" is an
>> 	ordered pair of keys.
>>
>> 	s/remove/delete/g, for consistency with other library modules.
>>
>> 	Export a version of relation.reduced which also returns the map
>> 	from relation keys to clique keys.  (This is needed by G12.)
>>
>> 	Change the stability of this module to "medium", on the grounds
>> 	that it's been used reasonably widely now.
>>
>> library/svrelation.m:
>> compiler/dependency_graph.m:
>> compiler/hlds_module.m:
>> compiler/modules.m:
>> compiler/prog_event.m:
>> compiler/stratify.m:
>> profiler/propagate.m:
>> 	Update to make use of the new types.
>>
>
> I wonder if this might not be an opportunity to swap the argument
> orderings in relation.m around so they match those in svrelation.m.
> (We could then delete svrelation.m.)

I thought about that, but decided it was too backwards incompatible, even
for a module that probably isn't used much and was "low" stability.

I also considered changing "key" to "vertex", "element" to "value", and
changing the module name to directed_graph or dgraph (I prefer the latter).
Then we could just leave relation.m and svrelation.m in for a release,
and then remove them.

Perhaps I should do this instead?

>
> ...
>
>> @@ -612,17 +644,17 @@
>>     % Add the arcs to the composition.
>>     list.foldl(add_compose_arcs(KeyMap1, KeyMap2), KeyAL, !Compose).
>>
>> -:- pred find_new_rel_keys(pair(relation_key_set)::in,
>> -    relation_key_set::in, relation_key_set::out,
>> -    relation_key_set::in, relation_key_set::out) is det.
>> +:- pred find_new_rel_keys(pair(relation_key_set(T))::in,
>> +    relation_key_set(T)::in, relation_key_set(T)::out,
>> +    relation_key_set(T)::in, relation_key_set(T)::out) is det.
>>
>> find_new_rel_keys(R1Keys - R2Keys,
>>         R1NeededKeys0, R1NeededKeys1, R2NeededKeys0, R2NeededKeys1) :-
>>     R1NeededKeys1 = sparse_bitset.union(R1NeededKeys0, R1Keys),
>>     R2NeededKeys1 = sparse_bitset.union(R2NeededKeys0, R2Keys).
>>
>> -:- pred add_compose_arcs(key_map::in, key_map::in, 
>> pair(relation_key_set)::in,
>> -    relation(T)::in, relation(T)::out) is det.
>> +:- pred add_compose_arcs(key_map(T)::in, key_map(T)::in,
>> +    pair(relation_key_set(T))::in, relation(T)::in, relation(T)::out) is 
>> det.
>>
>> add_compose_arcs(KeyMap1, KeyMap2, R1Keys - R2Keys, !Compose) :-
>>     relation.add_cartesian_product(
>> @@ -630,8 +662,8 @@
>>         map_key_set(KeyMap2, R2Keys),
>>         !Compose).
>
> I suggest renaming that so that it refers to edges rather than arcs.

Ok.

>
> ...
>
>>     % Provided that we never encounter a node that we've visited before
>> @@ -738,8 +770,8 @@
>>     relation.components_2(Rel, DomList, set.init, SetofBitsets),
>>     Set = set.map(to_set, SetofBitsets).
>>
>> -:- pred relation.components_2(relation(T)::in, list(relation_key)::in,
>> -    set(relation_key_set)::in, set(relation_key_set)::out) is det.
>> +:- pred relation.components_2(relation(T)::in, list(relation_key(T))::in,
>> +    set(relation_key_set(T))::in, set(relation_key_set(T))::out) is det.
>>
>> relation.components_2(_Rel, [], !Comp).
>> relation.components_2(Rel, [X | Xs], !Comp) :-
>> @@ -747,13 +779,13 @@
>>     queue.list_to_queue([X], Q0),
>>     relation.reachable_from(Rel, Q0, Set0, Component),
>>     set.insert(!.Comp, Component, !:Comp),
>> -    list_to_set(Xs, XsSet `with_type` relation_key_set),
>> +    list_to_set(Xs, XsSet `with_type` relation_key_set(T)),
>
> You may as well replace `with_type` with `:` there.

Done.

>
> The rest of that looks fine.

I'll await comments on the new module proposal before committing.

Cheers,
Mark.

diff -u library/relation.m library/relation.m
--- library/relation.m	4 Sep 2007 15:45:10 -0000
+++ library/relation.m	4 Sep 2007 17:41:37 -0000
@@ -641,8 +641,8 @@
     sparse_bitset.foldl2(copy_element(R2), R2NeededKeys, !Compose,
         map.init, KeyMap2),
 
-    % Add the arcs to the composition.
-    list.foldl(add_compose_arcs(KeyMap1, KeyMap2), KeyAL, !Compose).
+    % Add the edges to the composition.
+    list.foldl(add_compose_edges(KeyMap1, KeyMap2), KeyAL, !Compose).
 
 :- pred find_new_rel_keys(pair(relation_key_set(T))::in,
     relation_key_set(T)::in, relation_key_set(T)::out,
@@ -653,10 +653,10 @@
     R1NeededKeys1 = sparse_bitset.union(R1NeededKeys0, R1Keys),
     R2NeededKeys1 = sparse_bitset.union(R2NeededKeys0, R2Keys).
 
-:- pred add_compose_arcs(key_map(T)::in, key_map(T)::in,
+:- pred add_compose_edges(key_map(T)::in, key_map(T)::in,
     pair(relation_key_set(T))::in, relation(T)::in, relation(T)::out) is det.
 
-add_compose_arcs(KeyMap1, KeyMap2, R1Keys - R2Keys, !Compose) :-
+add_compose_edges(KeyMap1, KeyMap2, R1Keys - R2Keys, !Compose) :-
     relation.add_cartesian_product(
         map_key_set(KeyMap1, R1Keys),
         map_key_set(KeyMap2, R2Keys),
@@ -779,7 +779,7 @@
     queue.list_to_queue([X], Q0),
     relation.reachable_from(Rel, Q0, Set0, Component),
     set.insert(!.Comp, Component, !:Comp),
-    list_to_set(Xs, XsSet `with_type` relation_key_set(T)),
+    list_to_set(Xs, XsSet : relation_key_set(T)),
     difference(XsSet, Component, Xs1Set),
     to_sorted_list(Xs1Set, Xs1),
     relation.components_2(Rel, Xs1, !Comp).
@@ -1012,7 +1012,7 @@
     % RTC of any element in a clique is the same as the RTC of any other
     % element in that clique. So we visit each clique in reverse topological
     % sorted order, compute the RTC for each element in the clique and then
-    % add the appropriate arcs.
+    % add the appropriate edges.
     %
     relation.dfs(Rel, Dfs),
     init(Visit),
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------