nondet C code

[Fergus Henderson]

Zoltan, have you still got a copy of your proposal for nondet C code?
I have saved a copy of my alternative proposal, but I can't find your
original mail.

P.S.  Here's how Eclipse does it.

     _________________________________________________________________

                          Nondeterministic Externals
                                       
   The previous sections covered the creation of deterministic external
   predicates. The nondeterministic predicates can of course use the same
   macros as the deterministic ones, however their functionality is
   larger in that they are sensitive to the backtracking process.
   
   A non deterministic Prolog procedure has potentially more than one
   solution. When it is first called, a solution is found if possible,
   and execution proceeds. If a subsequent goal fails, backtracking
   occurs, and an attempt is made to find another solution to the call of
   the procedure. To make this action possible in the procedural language
   C, ECLiPSe provides a macro which will take note of the values to be
   given to the arguments of an external procedure if an attempt is made
   to resatisfy it. This macro is Remember().
   
   To illustrate its use, consider the next example, it shows a C
   implementation of the Prolog predicate member/2. As opposed to the
   well-known Prolog definition this one does not work backwards, i.e. it
   will not construct lists when called with the second argument
   uninstantiated:
   
int
p_member(velt, telt, vlist, tlist)
value velt, vlist;
type telt, tlist;
{
        pword *p;

        /* we require a list or nil */
        Check_List(tlist);
        /* if the list is empty, we fail */
        if(IsNil(tlist))
        {
                Cut_External;
                Fail;
        }
        /* the tail of the list */
        p = vlist.ptr + 1;
        /* must be dereferenced! */
        Dereference(p);
        /*
        * on backtracking we will get the tail of the list
        * instead of the list itself
        */
        Remember(2, p->val, p->tag);
        /*
        * and we behave as the unification
        * of the element and the head
        */
        Return_Unify_Pw(velt, telt,
                vlist.ptr->val, vlist.ptr->tag);
}

   To link this C function to a Prolog predicate use b_external/2 as
   follows:
   
b_external(member/2, p_member)

   In a Prolog program the call
   
member(X, List)

   will succeed if X is a member of the list List. This is clearly
   resatisfiable - for example in the call
   
member(X, [1, 2, 3, 4])

   where X is an uninstantiated variable, X will first be instantiated to
   1, and on resatisfaction of the goal it will successively be
   instantiated to 2, 3, and 4 before it finally fails. A solution to the
   call
   
member(X, List)

   is found when X is unified with the head of List by the
   Return_Unify_Pw() statement in the last line of the function. When an
   attempt is made to resatisfy the above clause, X must be instantiated
   to another element of List. This will be done if the procedure is
   called again with a new instantiation of its arguments, namely that
   when the second argument has the value of the tail of the list which
   it was given on the previous call.
   
   The use of the macro Remember() makes this new instantiation of the
   procedure's arguments possible. In an external procedure, the call of
   the macro
   
Remember(n, val, tag);

   has the effect that if an attempt is made to resatisfy the procedure,
   the value given in argument n of the Prolog procedure will be the
   Prolog term represented by the value val and the tag tag. The type of
   val must be value and the type of tag must be type.
   
   Thus in the above example, it is required that the procedure be called
   with the second argument instantiated to the tail of the list which
   was its previous value. So a pointer is taken to the tail by the
   assignment of the pointer p in the fourth statement, and the call
   
Remember(2, p->val, p->tag);

   informs ECLiPSe that to resatisfy the goal a call of the Prolog
   procedure must be made again, with the second argument instantiated to
   the object pointed to by p.
   
   Note the use of the Dereference macro in the previous   example. p is
   the tail of the list and so to access its value, it must be
   dereferenced, even though it will become   predicate argument in the
   next invocation of p_member - only the terms which are arguments of
   the normal (not after backtracking) invocation are dereferenced by the
   system.
   
   A nondeterministic external predicate is resatisfiable until it
   explicitly cuts all following alternatives using the macro
   Cut_External, i.e.   if it uses Return_Unify and this unification
   fails or if it uses the macro Fail, it will be called immediately
   again with the newly remembered value, if any. If it is known that the
   current solution is the last one, the macro Succeed_Last can be used
   for a deterministic exit   from this external predicate, i.e. the
   predicate succeeds and is no longer resatisfiable.
   
   To perform the backtracking operation, some information must be stored
   between one attempt at satisfaction of the goal and an attempt to
   resatisfy it. By this mechanism, the backtracking of Prolog can be
   imitated by the facilities in C. It is not always possible (and seldom
   desirable) to map directly from the definition of the procedure in
   Prolog to an implementation in C. Some ingenuity may be required. A
   very simple example is the procedure p/1 defined in Prolog as
   
p(a).
p(b).
p(c).

   This is implemented as a C external by defining the Prolog code
   
p(X) :- p(X, 1).

   The C external is then written for the procedure p/2, whose auxiliary
   second argument serves to count its invocations.
   
int
p_p2(v1, t1, v2, t2)
value v1, v2;
type  t1, t2;
{
        char        *result;
        pword       new;

        /* first check the arguments */
        Check_Integer(t2);
        Check_Output_Atom(t1);
        /* take note of new resatisfaction */
        Make_Integer(&new, v2.nint + 1);
        Remember(2, new.val, new.tag);
        /* get the string that corresponds to the value of v2 */
        switch(v2.nint)
        {
                case 1:
                        result = "a";
                        break;
                case 2:
                        result = "b";
                        break;
                case 3:
                        result = "c";
                        break;
                default:
                        Fail;
        }
        Return_Unify_Atom(v1, t1, Did(result, 0));
}
     _________________________________________________________________
-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.