12.4.1.1 Non-deterministic Foreign Predicates

By default foreign predicates are deterministic. Using the PL_FA_NONDETERMINISTIC attribute (see PL_register_foreign()) it is possible to register a predicate as a non-deterministic predicate. Writing non-deterministic foreign predicates is slightly more complicated as the foreign function needs context information for generating the next solution. Note that the same foreign function should be prepared to be simultaneously active in more than one goal. Suppose the natural_number_below_n/2 is a non-deterministic foreign predicate, backtracking over all natural numbers lower than the first argument. Now consider the following predicate:

quotient_below_n(Q, N) :-
        natural_number_below_n(N, N1),
        natural_number_below_n(N, N2),
        Q =:= N1 / N2, !.

In this predicate the function natural_number_below_n/2 simultaneously generates solutions for both its invocations.

Non-deterministic foreign functions should be prepared to handle three different calls from Prolog:

• Initial call (PL_FIRST_CALL)
  Prolog has just created a frame for the foreign function and asks it to produce the first answer.
• Redo call (PL_REDO)
  The previous invocation of the foreign function associated with the current goal indicated it was possible to backtrack. The foreign function should produce the next solution.
• Terminate call (PL_PRUNED)
  The choice point left by the foreign function has been destroyed by a cut. The foreign function is given the opportunity to clean the environment.

Both the context information and the type of call is provided by an argument of type control_t appended to the argument list for deterministic foreign functions. The macro PL_foreign_control() extracts the type of call from the control argument. The foreign function can pass a context handle using the PL_retry*() macros and extract the handle from the extra argument using the PL_foreign_context*() macro.

(return) foreign_t PL_retry(intptr_t value)

The foreign function succeeds while leaving a choice point. On backtracking over this goal the foreign function will be called again, but the control argument now indicates it is a‘Redo' call and the macro PL_foreign_context() returns the handle passed via PL_retry(). This handle is a signed value two bits smaller than a pointer, i.e., 30 or 62 bits (two bits are used for status indication). Defined as return _PL_retry(n). See also PL_succeed().

(return) foreign_t PL_retry_address(void *)

As PL_retry(), but ensures an address as returned by malloc() is correctly recovered by PL_foreign_context_address(). Defined as return _PL_retry_address(n). See also PL_succeed().

int PL_foreign_control(control_t)

Extracts the type of call from the control argument. The return values are described above. Note that the function should be prepared to handle the PL_PRUNED case and should be aware that the other arguments are not valid in this case.

intptr_t PL_foreign_context(control_t)

Extracts the context from the context argument. If the call type is PL_FIRST_CALL the context value is 0L. Otherwise it is the value returned by the last PL_retry() associated with this goal (both if the call type is PL_REDO or PL_PRUNED).

void * PL_foreign_context_address(control_t)

Extracts an address as passed in by PL_retry_address().

predicate_t PL_foreign_context_predicate(control_t)

Fetch the Prolog predicate that is executing this function. Note that if the predicate is imported, the returned predicate refers to the final definition rather than the imported predicate; i.e., the module reported by PL_predicate_info() is the module in which the predicate is defined rather than the module where it was called. See also PL_predicate_info().

Note: If a non-deterministic foreign function returns using PL_succeed() or PL_fail(), Prolog assumes the foreign function has cleaned its environment. No call with control argument PL_PRUNED will follow.

The code of figure 5 shows a skeleton for a non-deterministic foreign predicate definition.

typedef struct                  /* define a context structure */
{ ...
} context;

foreign_t
my_function(term_t a0, term_t a1, control_t handle)
{ struct context * ctxt;

  switch( PL_foreign_control(handle) )
  { case PL_FIRST_CALL:
        if ( !(ctxt = malloc(sizeof *ctxt)) )
          return PL_resource_error("memory");
        <initialize ctxt>
        break;
    case PL_REDO:
        ctxt = PL_foreign_context_address(handle);
        break;
    case PL_PRUNED:
        ctxt = PL_foreign_context_address(handle);
        ...
        free(ctxt);
        return TRUE;
  }

  <find first/next solution from ctxt>
  ...
  // We fail */
  if ( <no_solution> )
  { free(ctx);
    return FALSE;
  }
  // We succeed without a choice point */
  if ( <last_solution> )
  { free(ctx);
    return TRUE;
  }
  // We succeed with a choice point */
  PL_retry_address(ctxt);
}