[mercury-users] yield and iterators [was: First solution in csharp without try/catch]

[Jeff Thompson]

On 1/8/2012 8:58 PM, Mark Brown wrote:
>> Is there another way (where the implementation doesn't use try/catch) to
>> make a semidet predicate which succeeds on the first solution of some code
>> block?
> In general you need a way to wind back the stack by an arbitrary number
> of frames for a commit, and in C# throwing an exception may well be the
> quickest way to achieve that.  In principle the compilation model could
> return a flag for each nondet call, but that would need to be tested after
> every call even if not actually required.

A way in C# is to use the "yield" and iterator features built into the 
language where the compiler adds this unwinding support.  Here is my 
example again where test succeeds if the condition succeeds once:

:- pred test is semidet.
test :- if multiPred(10, X), X > 15 then true else fail.

:- pred multiPred(int::in, int::out) is multi.
multiPred(M, X) :- X = 1 * M.
multiPred(M, X) :- X = 2 * M.

Here is the Mercury compiler C# output (simplified) for test which 
catches the runtime.Commit() exception thrown by test_0_p_0_3:

         private class Test_0_p_0_env_0
         {
             public bool succeeded;
             public int X_1;
         }
         public static bool test_0_p_0()
         {
             var env_ptr = new testYield.Test_0_p_0_env_0();
             try
             {
                 multiPred_2_p_0(10, testYield.test_0_p_0_3, env_ptr);
                 env_ptr.succeeded = false;
             }
             catch (runtime.Commit commit_variable)
             {
                 env_ptr.succeeded = true;
             }
             return env_ptr.succeeded;
         }
         public static void multiPred_2_p_0(int M_1, 
runtime.MethodPtr2_r0<int, object> cont, object cont_env_ptr)
         {
             cont(1 * M_1, cont_env_ptr);
             cont(2 * M_1, cont_env_ptr);
         }
         private static void test_0_p_0_3(int arg1, object env_ptr_arg)
         {
             var env_ptr = (testYield.Test_0_p_0_env_0)env_ptr_arg;

             env_ptr.X_1 = arg1;
             env_ptr.succeeded = (env_ptr.X_1 > 15);
             if (env_ptr.succeeded)
                 throw new runtime.Commit();
         }

Here is the code using "yield".  See embedded comments.

         public static bool test_0_p_0_yield()
         {
             var X_1 = new int[1];
             foreach (var l1 in multiPred_2_p_0(10, X_1))
             {
                 foreach (var l2 in test_0_p_0_3(X_1[0]))
                     return true;   // Commit. The compiler handles all 
the stack unwinding at this point.
             }
             return false;
         }
         public static IEnumerable<bool> multiPred_2_p_0(int M_1, int[] X_1)
         {
             X_1[0] = 1 * M_1;
             yield return false;
             X_1[0] = 2 * M_1;
             yield return false;   // Multiple yields for "multi" 
predicates.
         }
         private static IEnumerable<bool> test_0_p_0_3(int arg1)
         {
             if (arg1 > 15)
                 yield return true;      // This nested call doesn't 
need to know at this point that the outer loop will do a commit.
             // else if no yield, then this predicate "fails".
         }

Note also that with this approach it is not necessary for a predicate to 
create an env_ptr or to pass a continuation, since upon "yield" the 
control returns to the predicate.

Thanks,
- Jeff
--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------