4.1 Basic Search Engines

All these engines take a script as input and return a list of its solutions.

base.one

{Search.base.one +ScriptP ?Xs}

returns a singleton list containing the first solution of the script +ScriptP (a unary procedure) obtained by depth-first search. If no solution exists, nil is returned.

As an example,

{Search.base.one proc {$ X}
                    choice  
                       choice X=ape [] X=bear end  
                    [] X=cat  
                    end 
                 end}

returns the list [ape].

base.all

{Search.base.all +ScriptP ?Xs}

returns the list of all solutions of the script +ScriptP (a unary procedure) obtained by depth-first serach. As an example,

{Search.base.all proc {$ X}
                    choice  
                       choice X=ape [] X=bear end  
                    [] X=cat  
                    end 
                 end}

returns the list [ape bear cat].

Search.base.best

{Search.base.best +ScriptP +OrderP ?Xs}

returns a singleton list containing the best solution with respect to the order +OrderP (a binary procedure) of the script +ScriptP (a unary procedure) obtained by branch and bound search. If no solution does exist, nil is returned.

The branch and bound strategy works as follows. When a solution is found, all the remaining alternatives are constrained to be better with respect to the order +OrderP. The binary procedure +OrderP is applied with its first argument being the previous solution, and its second argument the root variable of a space for one of the remaining alternatives.

For instance, the following script constrains its root variable to a pair of integers, such that a certain equation holds between its components.

proc {Script Root}
   X={FD.int 1#10} Y={FD.int 1#10}
in 
   Y =: 10 - X - 2*Y
   Root = X#Y
   {FD.distribute split Root}
end

With the order

proc {MaxSum Old New}
   Old.1 + Old.2 <: New.1 + New.2
end

we can search for a solution with maximal sum of X and Y by

{SearchBest Script MaxSum}

This returns the singleton list [7#1].

Similarly, we can search for the solution with the maximal product, by using the order:

proc {MaxProduct Old New}
   Old.1 * Old.2 <: New.1 * New.2
end

in:

{SearchBest Script MaxProduct}

This returns the singleton list [4#2].