# [m-rev.] diff: Make the recursion patterns analysis more robust.

Paul Bone pbone at csse.unimelb.edu.au
Fri Oct 8 23:49:29 AEDT 2010

```Make the recursion patterns analysis more robust.

Handle semidet and committed choice disjunctions in the recursion patterns
analysis.

deep_profiler/recursion_patterns.m:
As above.

deep_profiler/measurement_units.m:
Add a new function, not_probability that returns the probability that a
certain probability will not occur.

Index: deep_profiler/measurement_units.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/measurement_units.m,v
retrieving revision 1.7
diff -u -p -b -r1.7 measurement_units.m
--- deep_profiler/measurement_units.m	26 Aug 2010 06:29:27 -0000	1.7
+++ deep_profiler/measurement_units.m	8 Oct 2010 12:46:26 -0000
@@ -137,6 +137,9 @@
:- func or(probability, probability) = probability.
:- func and(probability, probability) = probability.

+    % The probability of the given probability not occuring.
+:- func not_probability(probability) = probability.
+
%-----------------------------------------------------------------------------%
%
% Code for formatting numbers.
@@ -306,6 +309,8 @@ or(A, B) = A + B.
% Combine conjoint probabilities with multiplication.
and(A, B) = A * B.

+not_probability(X) = 1.0 - X.
+
%-----------------------------------------------------------------------------%
%
% Code for formatting numbers.
Index: deep_profiler/recursion_patterns.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/recursion_patterns.m,v
retrieving revision 1.5
diff -u -p -b -r1.5 recursion_patterns.m
--- deep_profiler/recursion_patterns.m	7 Oct 2010 02:38:10 -0000	1.5
+++ deep_profiler/recursion_patterns.m	8 Oct 2010 12:46:26 -0000
@@ -276,8 +276,7 @@ single_rec_average_recursion_cost(BaseCo
).

:- type recursion_error
-    --->    re_unhandled_determinism(detism_rep)
-    ;       re_unhandled_disjunction.
+    --->    re_unhandled_determinism(detism_rep).

% goal_recursion_data(RecursiveCallees, Goal, GoalPath,
%   init_recursion_data, RecursionData)
@@ -306,8 +305,8 @@ goal_recursion_data(ThisClique, CallSite
Conjs, !:RecursionData)
;
GoalExpr = disj_rep(Disjs),
-            disj_recursion_data(ThisClique, CallSiteMap, GoalPath, 1, Disjs,
-                !:RecursionData)
+            disj_recursion_data(ThisClique, CallSiteMap, GoalPath, 1, certain,
+                Disjs, !:RecursionData)
;
GoalExpr = switch_rep(_, _, Cases),
switch_recursion_data(ThisClique, CallSiteMap, GoalPath, 1, Cases,
@@ -370,18 +369,8 @@ conj_recursion_data(ThisClique, CallSite
;
ConjRecursionData = recursion_data(_, _, _),
-        (
-            get_coverage_before_and_after(Conj ^ goal_annotation, Before, After)
-        ->
-            ( After > Before ->
-                % Nondet code can overflow this probability.
-                ConjSuccessProb = certain
-            ;
-                ConjSuccessProb = probable(float(After) / float(Before))
-            )
-        ;
-            error(this_file ++ "expected complete coverage information")
-        ),
+        success_probability_from_coverage(Conj ^ goal_annotation,
+            ConjSuccessProb),
SuccessProb = and(SuccessProb0, ConjSuccessProb),
conj_recursion_data(ThisClique, CallSiteMap, GoalPath, ConjNum + 1,
SuccessProb, Conjs, ConjsRecursionData),
@@ -391,11 +380,52 @@ conj_recursion_data(ThisClique, CallSite

:- pred disj_recursion_data(clique_ptr::in,
map(goal_path, cost_and_callees)::in, goal_path::in, int::in,
-    list(goal_rep(coverage_info))::in, recursion_data::out) is det.
+    probability::in, list(goal_rep(coverage_info))::in, recursion_data::out)
+    is det.
+
+disj_recursion_data(_, _, _, _, _, [], simple_recursion_data(0.0, 0)).
+disj_recursion_data(ThisClique, CallSiteMap, GoalPath, DisjNum, FailureProb0,
+        [Disj | Disjs], RecursionData) :-
+    % Handle only semidet and committed-choice disjunctions, once a goal
+    % succeeds it cannot be re-entered.
+    goal_recursion_data(ThisClique, CallSiteMap,
+        DisjRecursionData),
+    (
+        % If the first disjunct was never tried then no other disjuncts will
+        % ever be tried.
+    ;
+        DisjRecursionData = recursion_data(_, _, _),
+        % Handle this just like a semidet conjunction, except that we go to the
+        % next disjunct if it _fails_.
+        success_probability_from_coverage(Disj ^ goal_annotation,
+            ConjSuccessProb),
+        ConjFailureProb = not_probability(ConjSuccessProb),
+        FailureProb = and(FailureProb0, ConjFailureProb),
+        disj_recursion_data(ThisClique, CallSiteMap, GoalPath, DisjNum + 1,
+            FailureProb, Disjs, DisjsRecursionData),
+        merge_recursion_data_sequence(DisjRecursionData, DisjsRecursionData,
+            RecursionData)
+    ).

-disj_recursion_data(_, _, _, _, _, !:RecursionData) :-
-    !:RecursionData = simple_recursion_data(0.0, 0),
+:- pred success_probability_from_coverage(coverage_info::in, probability::out)
+    is det.
+
+success_probability_from_coverage(Coverage, SuccessProb) :-
+    (
+        get_coverage_before_and_after(Coverage, Before, After)
+    ->
+        ( After > Before ->
+            % Nondet code can overflow this probability.
+            SuccessProb = certain
+        ;
+            SuccessProb = probable(float(After) / float(Before))
+        )
+    ;
+        error(this_file ++ "expected complete coverage information")
+    ).

:- pred ite_recursion_data(clique_ptr::in,
map(goal_path, cost_and_callees)::in, goal_path::in,
@@ -700,8 +730,6 @@ simple_recursion_data(Cost, Calls) =

error_to_string(re_unhandled_determinism(Detism)) =
format("%s code is not handled", [s(string(Detism))]).
-error_to_string(re_unhandled_disjunction) =
-    "Disjunctions are not currently handled".

%----------------------------------------------------------------------------%

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20101008/dddb33bc/attachment.sig>
```