All solutions

These predicates create a list of all the solutions of a goal.

1. findall/3

findall(Template, Goal, Instances) is true iff Instances unifies with the list of values to which a variable X not occurring in Template or Goal would be instantiated by successive re-executions of call(Goal), X=Template. after systematic replacement of all variables in X by new variables.

Templates and modes for the predicate are as follows:

findall(?term, +callable_term, ?list)

1.1 Example tests

Let's start with some simple tests verifying success of failure of single goals.

alice.tuprolog.SimpleGoalFixture
goalsuccess()
findall(X, (X=2; X=1), [1, 2]). false

Now let's run some tests verifying the unification for some of the variables in goals.

First of all, let's start an appropriate fixture containing an engine.

fit.ActionFixture
start alice.tuprolog.EngineFixture

Then, ask the engine to solve a query, and check variable bindings.

fit.ActionFixture
enter query findall(X, (X=1; X=2), S).
check hasSolution true
enter variable S
check binding [1, 2]
enter query findall(X+Y, (X=1), S).
check hasSolution true
enter variable S
check binding [1 + _] expected
['+'(1,_27959626)] actual
enter query findall(X, fail, L).
check hasSolution true
enter variable L
check binding []
enter query findall(X, (X=1; X=1), S).
check hasSolution true
enter variable S
check binding [1, 1]
enter query findall(X, (X=1; X=2), [X, Y]).
check hasSolution true
enter variable X
check binding 1
enter variable Y
check binding 2

The remaining tests cover the cases when an error or exception is thrown by the engine while solving a query.

alice.tuprolog.PrologActionFixture
enter query findall(X, Goal, S).
check hasSolution false
check exception instantiation_error
enter query findall(X, 4, S).
check hasSolution false
check exception type_error(callable, 4)

2. bagof/3

bagof/3 assembles as a list the solutions of a goal for each different instantiation of the free variables in that goal. The elements of each list are in order of solution, but the order in which each list is found is undefined.

Note that bagof/3 is re-executable.

Templates and modes for the predicate are as follows:

bagof(?term, +callable_term, ?list)

2.1 Example tests

Let's start with some simple tests verifying success of failure of single goals.

alice.tuprolog.SimpleGoalFixture
goalsuccess()
bagof(X, fail, S). false

Let's run some tests verifying the unification for some of the variables in goals.

First of all, let's start an appropriate fixture containing an engine.

fit.ActionFixture
start alice.tuprolog.EngineFixture

Then, ask the engine to solve a query, and check variable bindings.

fit.ActionFixture
enter query bagof(X, (X=1; X=2), S). Free variable set: {}
check hasSolution true
enter variable S
check binding [1, 2]
enter query bagof(X, (X=1; X=2), X). Free variable set: {}
check hasSolution true
enter variable X
check binding [1, 2]
enter query bagof(X, (X=Y; X=Z), S). Free variable set: {Y, Z}
check hasSolution true
enter variable S
check binding [Y, Z] expected
[_24807938,_33208902] actual
enter query bagof(1, (Y=1; Y=2), L). Free variable set: {Y}
check hasSolution true
enter variable L
check binding [1]
enter variable Y
check binding 1
check hasAnotherSolution true
enter variable L
check binding [1]
enter variable Y
check binding 2
enter query bagof(f(X, Y), (X=a; Y=b), L). Free variable set: {}
check hasSolution true
enter variable L
check binding [f(a, _), f(_, b)] expected
[f(a,_19642336),f(_20248218,b)] actual
enter query bagof(X, Y^((X=1, Y=1) ; (X=2, Y=2)), S). Free variable set: {}
check hasSolution true
enter variable S
check binding [1, 2]
enter query bagof(X, Y^((X=1; Y=1) ; (X=2, Y=2)), S). Free variable set: {}
check hasSolution true
enter variable S
check binding [1, _, 2] expected
[1,_24585668,2] actual
enter query bagof(X, (Y^(X=1; Y=2) ; X=3), S). Free variable set: {Y}
check hasSolution true
enter variable S
check binding [3]
enter variable Y
check binding _ expected
Y actual
enter query bagof(X, (X=Y; X=Z; Y=1), S). Free variable set: {Y, Z}
check hasSolution true
enter variable S
check binding [Y, Z] expected
[_22522451,_7295144,_1603604] actual
check hasAnotherSolution true expected
false actual
enter variable S
check binding [_]
alice.tuprolog.NoSolutionException
at alice.tuprolog.SolveInfo.getVarValue(SolveInfo.java:171)
at alice.tuprolog.EngineFixture.binding(EngineFixture.java:92)
at sun.reflect.GeneratedMethodAccessor21.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at fit.TypeAdapter.invoke(Unknown Source)
at fit.TypeAdapter.get(Unknown Source)
at fit.Fixture.check(Unknown Source)
at fit.ActionFixture.check(Unknown Source)
at sun.reflect.GeneratedMethodAccessor14.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at fit.ActionFixture.doCells(Unknown Source)
at fit.Fixture.doRow(Unknown Source)
at fit.Fixture.doRows(Unknown Source)
at fit.Fixture.doTable(Unknown Source)
at fit.Fixture.interpretFollowingTables(Unknown Source)
at fit.Fixture.interpretTables(Unknown Source)
at fit.Fixture.doTables(Unknown Source)
at fit.FileRunner.process(Unknown Source)
at fit.FileRunner.run(Unknown Source)
at fit.FileRunner.main(Unknown Source)
enter variable Y
check binding 1
alice.tuprolog.NoSolutionException
at alice.tuprolog.SolveInfo.getVarValue(SolveInfo.java:171)
at alice.tuprolog.EngineFixture.binding(EngineFixture.java:92)
at sun.reflect.GeneratedMethodAccessor21.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at fit.TypeAdapter.invoke(Unknown Source)
at fit.TypeAdapter.get(Unknown Source)
at fit.Fixture.check(Unknown Source)
at fit.ActionFixture.check(Unknown Source)
at sun.reflect.GeneratedMethodAccessor14.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at fit.ActionFixture.doCells(Unknown Source)
at fit.Fixture.doRow(Unknown Source)
at fit.Fixture.doRows(Unknown Source)
at fit.Fixture.doTable(Unknown Source)
at fit.Fixture.interpretFollowingTables(Unknown Source)
at fit.Fixture.interpretTables(Unknown Source)
at fit.Fixture.doTables(Unknown Source)
at fit.FileRunner.process(Unknown Source)
at fit.FileRunner.run(Unknown Source)
at fit.FileRunner.main(Unknown Source)

Let's now use a real theory to exercise the predicate on.

fit.ActionFixture
enter theory a(1, f(_)).
a(2, f(_)).
enter query bagof(X, a(X, Y), L). Free variable set: {Y}
check hasSolution true
enter variable L
check binding [1, 2]
enter variable Y
check binding f(_) expected
f(_22725577) actual
enter theory b(1, 1).
b(1, 1).
b(1, 2).
b(2, 1).
b(2, 2).
b(2, 2).
enter query bagof(X, b(X, Y), L). Free variable set: {Y}
check hasSolution true
enter variable L
check binding [1, 1, 2]
enter variable Y
check binding 1
check hasAnotherSolution true
enter variable L
check binding [1, 2, 2]
enter variable Y
check binding 2

The remaining tests cover the cases when an error or exception is thrown by the engine while solving a query.

alice.tuprolog.PrologActionFixture
enter query bagof(X, Y^Z, L).
check hasSolution false
check exception instantiation_error
enter query bagof(X, 1, L).
check hasSolution false
check exception type_error(callable, 1)

3. setof/3

setof/3 assembles as a list the solutions of a goal for each different instantiation of the free variables in that goal. Each list is a sorted list, but the order in which each list is found is undefined.

Note that bagof/3 is re-executable.

Templates and modes for the predicate are as follows:

setof(?term, +callable_term, ?list)

3.1 Example tests

Let's start with some simple tests verifying success of failure of single goals.

alice.tuprolog.SimpleGoalFixture
goalsuccess()
setof(X, fail, S). false

Let's run some tests verifying the unification for some of the variables in goals.

First of all, let's start an appropriate fixture containing an engine.

fit.ActionFixture
start alice.tuprolog.EngineFixture

Then, ask the engine to solve a query, and check variable bindings.

fit.ActionFixture
enter query setof(X, (X=1; X=2), S). Free variable set: {}
check hasSolution true
enter variable S
check binding [1, 2]
enter query bagof(X, (X=1; X=2), X). Free variable set: {}
check hasSolution true
enter variable X
check binding [1, 2]
enter query setof(X, (X=2; X=1), S). Free variable set: {}
check hasSolution true
enter variable S
check binding [1, 2]
enter query setof(X, (X=2; X=2), S). Free variable set: {}
check hasSolution true
enter variable S
check binding [2]
enter query setof(X, (X=Y; X=Z), S). Free variable set: {Y, Z}
check hasSolution true
enter variable S
check binding [Y, Z] expected
[_19432672,_19647819] actual
Depending on the implementation, the binding could also be [Z, Y]
enter query setof(1, (Y=2; Y=1), L). Free variable set: {Y}
check hasSolution true The order of solutions is undefined
enter variable L
check binding [1]
enter variable Y
check binding 1 expected
2 actual
check hasAnotherSolution true The order of solutions is undefined
enter variable L
check binding [1]
enter variable Y
check binding 2 expected
1 actual
enter query setof(f(X, Y), (X=a; Y=b), L). Free variable set: {}
check hasSolution true
enter variable L
check binding [f(_, b), f(a, _)] expected
[f(_19397138,b),f(a,_26396889)] actual
enter query setof(X, Y^((X=1, Y=1) ; (X=2, Y=2)), S). Free variable set: {}
check hasSolution true
enter variable S
check binding [1, 2]
enter query setof(X, Y^((X=1; Y=1) ; (X=2, Y=2)), S). Free variable set: {}
check hasSolution true
enter variable S
check binding [_, 1, 2] expected
[_3022623,1,2] actual
enter query setof(X, (Y^(X=1; Y=2) ; X=3), S). Free variable set: {Y}
check hasSolution true
enter variable S
check binding [3]
enter variable Y
check binding _ expected
Y actual
enter query setof(X, (X=Y; X=Z; Y=1), S). Free variable set: {Y, Z}
check hasSolution true
enter variable S
check binding [Y, Z] expected
[_1243630,_30844270,_17235092] actual
Depending on the implementation, the binding could also be [Z, Y]
check hasAnotherSolution true expected
false actual
enter variable S
check binding [_]
alice.tuprolog.NoSolutionException
at alice.tuprolog.SolveInfo.getVarValue(SolveInfo.java:171)
at alice.tuprolog.EngineFixture.binding(EngineFixture.java:92)
at sun.reflect.GeneratedMethodAccessor21.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at fit.TypeAdapter.invoke(Unknown Source)
at fit.TypeAdapter.get(Unknown Source)
at fit.Fixture.check(Unknown Source)
at fit.ActionFixture.check(Unknown Source)
at sun.reflect.GeneratedMethodAccessor14.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at fit.ActionFixture.doCells(Unknown Source)
at fit.Fixture.doRow(Unknown Source)
at fit.Fixture.doRows(Unknown Source)
at fit.Fixture.doTable(Unknown Source)
at fit.Fixture.interpretFollowingTables(Unknown Source)
at fit.Fixture.interpretTables(Unknown Source)
at fit.Fixture.doTables(Unknown Source)
at fit.FileRunner.process(Unknown Source)
at fit.FileRunner.run(Unknown Source)
at fit.FileRunner.main(Unknown Source)
enter variable Y
check binding 1
alice.tuprolog.NoSolutionException
at alice.tuprolog.SolveInfo.getVarValue(SolveInfo.java:171)
at alice.tuprolog.EngineFixture.binding(EngineFixture.java:92)
at sun.reflect.GeneratedMethodAccessor21.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at fit.TypeAdapter.invoke(Unknown Source)
at fit.TypeAdapter.get(Unknown Source)
at fit.Fixture.check(Unknown Source)
at fit.ActionFixture.check(Unknown Source)
at sun.reflect.GeneratedMethodAccessor14.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at fit.ActionFixture.doCells(Unknown Source)
at fit.Fixture.doRow(Unknown Source)
at fit.Fixture.doRows(Unknown Source)
at fit.Fixture.doTable(Unknown Source)
at fit.Fixture.interpretFollowingTables(Unknown Source)
at fit.Fixture.interpretTables(Unknown Source)
at fit.Fixture.doTables(Unknown Source)
at fit.FileRunner.process(Unknown Source)
at fit.FileRunner.run(Unknown Source)
at fit.FileRunner.main(Unknown Source)

The following examples assume that member/2 is defined with the following clauses:

member(X, [X | _]).
member(X, [_ | L]) :- member(X, L).

Let's start with some simple tests verifying success of failure of single goals.

alice.tuprolog.SimpleGoalFixture
goalsuccess()
setof(X, (exists(U,V)^member(X, [V, U, f(U), f(V)])), [a, b, f(b), f(a)]). false expected
true actual

Let's run some tests verifying the unification for some of the variables in goals.

First of all, let's start an appropriate fixture containing an engine.

fit.ActionFixture
start alice.tuprolog.EngineFixture

Then, ask the engine to solve a query, and check variable bindings.

fit.ActionFixture
enter query setof(X, member(X, [f(U,b), f(V,c)]), L). Free variable set: {U, V}
check hasSolution true
enter variable L
check binding [f(U,b), f(V,c)] expected
[f(_29345020,b),f(_18724539,c)] actual
Depending on the implementation, the binding could also be [f(V,c), f(U,b)]
enter query setof(X, member(X, [f(U,b), f(V,c)]), [f(a,c), f(a,b)]). Free variable set: {U, V}
check hasSolution false Depending on the implementation, the query could also succeed unifying both U and V with a
enter query setof(X, member(X, [f(b,U), f(c,V)]), [f(b,a), f(c,a)]). Free variable set: {U, V}
check hasSolution true
enter variable U
check binding a expected
U actual
enter variable V
check binding a expected
V actual
enter query setof(X, member(X, [V, U, f(U), f(V)]), [a, b, f(a), f(b)]). Free variable set: {U, V}
check hasSolution true
enter variable U
check binding b expected
U actual
Depending on the implementation, the binding could also be a
enter variable V
check binding a expected
V actual
Depending on the implementation, the binding could also be b

Let's now use a real theory to exercise the predicate on.

fit.ActionFixture
enter theory a(1, f(_)).
a(2, f(_)).
enter query setof(X, a(X, Y), L). Free variable set: {Y}
check hasSolution true
enter variable L
check binding [1, 2]
enter variable Y
check binding f(_) expected
f(_21893435) actual
enter theory b(1, 1).
b(1, 1).
b(1, 2).
b(2, 1).
b(2, 2).
b(2, 2).
enter query setof(X, b(X, Y), L). Free variable set: {Y}
check hasSolution true
enter variable L
check binding [1, 2]
enter variable Y
check binding 1
check hasAnotherSolution true
enter variable L
check binding [1, 2]
enter variable Y
check binding 2
enter query setof(X-Xs, Y^setof(Y, b(X, Y), Xs), L). Free variable set: {}
check hasSolution true
enter variable L
check binding [1-[1, 2], 2-[1,2]]
enter query setof(X-Xs, setof(Y, b(X, Y), Xs), L). Free variable set: {Y}
check hasSolution true
enter variable L
check binding [1-[1, 2], 2-[1, 2]]
enter variable Y
check binding _ expected
Y actual
enter theory d(1, 1).
d(1, 2).
d(1, 1).
d(2, 2).
d(2, 1).
d(2, 2).
enter query setof(X-Xs, bagof(Y, d(X, Y), Xs), L). Free variable set: {Y}
check hasSolution true
enter variable L
check binding [1-[1, 2, 1], 2-[2, 1, 2]]
enter variable Y
check binding _ expected
Y actual

Note that there are no tests covering the cases when an error or exception is thrown by the engine while solving a query, despite setof/3 being known for throwing three different types of exceptions.

Run the tests!


The results of the tests for All solutions are as follows:

fit.Summary
counts 81 right, 25 wrong, 4 ignored, 4 exceptions
input file D:\Silvia\Merge_Tesi\Tesi\test\allSolutions.html
input update Tue Dec 23 03:02:00 CET 2008
output file D:\Silvia\Merge_Tesi\Tesi\test\report_Montanari\allSolutions.html
run date Wed Sep 28 12:50:02 CEST 2011
run elapsed time 0:00.76