pl_search::Pred Class Reference

Base class for Prolog-like predicates. More...

#include <pred.hpp>

Inheritance diagram for pl_search::Pred:

Collaboration diagram for pl_search::Pred:

Public Member Functions
	Pred (Trail *trail)
	Default constructor.
PredPtr	get_continuation ()
	Gets the continuation of the predicate.
virtual void	set_continuation (PredPtr cont)
	Sets the continuation of the predicate.
PredPtr	last_pred ()
	Follows the continuation chain to the last predicate.
virtual void	call_init ()
	Initialize call.
virtual bool	call ()
bool	call_continuation ()
	Calls the continuation of the predicate - first call_init and then call.
virtual	~Pred ()=default
	Virtual destructor for proper cleanup.
virtual std::string	get_name ()
	For debugging.

Protected Attributes
PredPtr	continuation
	The continuation of the predicate.
Trail *	trail
	Pointer to the trail for managing variable bindings.

Detailed Description

Base class for Prolog-like predicates.

The Pred class provides an interface for Prolog-like predicates. It uses a continuation-passing style to manage the flow of execution. Derived classes implement specific predicate behaviors. Predicates are used to program backtrack search in a Prolog-like style. Execution of the search is initiated by calling the call() method of the first predicate in a chain of predicates. Non-determinism is typically implemented using one or more ChoicePred predicates which are used to make choices. The DisjPred meta-predicate can also be used to implement non-determinism by providing alternatives to be tried in order. It's possible for the user to implement non-deterministic predicates themselves but a combination of ChoicePred predicates and DisjPred predicates is usually sufficient.

The key method is call() which is called to execute the predicate. Any system defined and user defined call() method is required to satisfy the following contract for each choice point in the execution of the predicate:

• If the execution for this choice succeeds "locally" then the call() method must call the continuation of the predicate by calling call_continuation().
• If the execution fails either locally or due to a failure in the continuation then the call() method should try the next choice point (if any).
• If the execution fails and there are no more choice points then the call() method should return false.
• For non-deterministic predicates, whenever failure occurs the call() method must unbind any variables that were bound during the execution of the predicate.

For a typical search program the only user-defined predicate will be the last predicate in the chain of predicates. This will typically be a predicate that simply prints or saves solution(s) found by the search. If only the first solution is required then the predicate should simply returns true and if all solutions are required then the predicate should return false triggering backtracking. In either case, if this is the only use of this predicate then the continuation will be nullptr and so it's not necessary to call call_continuation() in this case.

For managing unbound variables, the Trail class is used to keep track of variable bindings. Whenever a variable is bound, it should be trailed using the trail_var() method of the Trail class (which typically happens when two terms are unified). When backtracking occurs, the unbind_to() method of the Trail class should be called to reset variables to their previous values. Typically in the call() method of a predicate, the current size of the trail is saved at the start of the method and then whenever the predicate fails, the trail is reset to that size to unbind any variables that were bound during the execution of the predicate.

Locally failure typically occurs when a choice is made by binding one or more variables but then a unify fails or some constraint is violated.

The ChoicePred::call() method is an example of a predicate that implements this contract. It saves the trail size at the start of the method and then whenever a choice fails, it resets the trail to that size to unbind any variables that were bound during the execution of the predicate. Note that whenever make_choice() succeeds (the predicate succeeds locally) call_continuation() is called.

This means that a program written as a chained collection of predicates will be executed in a depth-first manner with backtracking whenever a predicate fails. The program will therefore explore the search tree in a depth-first manner and either stop when the first solution is found or explore the entire search tree.

Warning: A given instance of a predicate should not be used in multiple contexts as its continuation will be set for one context and then used in another context. This can be avoided by creating a new instance of the predicate for each context in which it is used.

Warning: When writing a predicate that is intended to be used in a conjunction that is preceeded by a non-deterministic predicate care must be taken with what code should be in the constructor and what code should be at the beginning of call(). Code in the constructor is only executed once at creation time while code at the beginning of call is, of course, executed each time call() is executed. Given that the state is typically dependent on any choices made in a preceeding non-deterministic predicate then any code that is dependent on earlier choices should be placed in the call_init method.

Note: As mentioned in the trail.hpp comments, user programs that do repeated searches should call unbind_to(0) to reset all variables back to their initial values before starting the next search. This is important to ensure that variables are in a consistent state before starting a new search.

Constructor & Destructor Documentation

Pred()

pl_search::Pred::Pred ( Trail *  trail )

inline

Default constructor.

Parameters

trail

Pointer to the trail for managing variable bindings.

~Pred()

virtual pl_search::Pred::~Pred ( )

virtualdefault

Virtual destructor for proper cleanup.

Member Function Documentation

call()

virtual bool pl_search::Pred::call ( )

inlinevirtual

Reimplemented in pl_search::FailPred, pl_search::ChoicePred, pl_search::DisjPred, pl_search::Once, pl_search::NotNot, pl_search::IfThenElse, and pl_search::Loop.

call_continuation()

bool pl_search::Pred::call_continuation ( )

inline

Calls the continuation of the predicate - first call_init and then call.

Returns

True if the continuation is called successfully, false otherwise.

nullptr is treated as a successful call to the continuation (an always true predicate) and is used to signify the end of a chain of predicates.

call_init()

virtual void pl_search::Pred::call_init ( )

inlinevirtual

Initialize call.

This method gives the programmer the opportunity to do some initialization when this predicate is (re)called (not when the predicate is created). This is typically required when implementing non-deterministic predicates as the complete set of choices needs to be re-enabled (see VarChoicePred for example). This is also important when this predicate is preceeded by a non-deterministic predicate in the call chain. Making a different choice in the non-deterministic predicate might require some recomputation. LoopBodyFactory typically requires similar considerations but call_init is not required for the generated predicate as it will not be recalled. The way the system is implemented guarantees that call_init will be called before call for each predicate except the first in the call chain and those generated by LoopBodyFactory. call_continuation calls it before the call and the meta-predicates call it directly.

Reimplemented in pl_search::VarChoicePred.

get_continuation()

PredPtr pl_search::Pred::get_continuation ( )

inline

Gets the continuation of the predicate.

Returns

A shared pointer to the continuation predicate.

get_name()

virtual std::string pl_search::Pred::get_name ( )

inlinevirtual

For debugging.

last_pred()

PredPtr pl_search::Pred::last_pred

(

)

Follows the continuation chain to the last predicate.

Returns

A shared pointer to the last predicate in the continuation chain.

set_continuation()

virtual void pl_search::Pred::set_continuation ( PredPtr  cont )

inlinevirtual

Sets the continuation of the predicate.

Parameters

cont	A shared pointer to the continuation predicate.

Reimplemented in pl_search::FailPred, pl_search::DisjPred, and pl_search::IfThenElse.

Member Data Documentation

continuation

PredPtr pl_search::Pred::continuation

protected

The continuation of the predicate.

trail

Trail* pl_search::Pred::trail

protected

Pointer to the trail for managing variable bindings.

---

The documentation for this class was generated from the following files:

• include/pl_search/pred.hpp
• src/pred.cpp