I'm interested in using Prolog to find a solution that maximises some atom of output. Say, for example, there are 10 predicates:
solution(1).
solution(2).
solution(3).
solution(4).
solution(5).
solution(6).
Finding the solution with the max argument, the usual way, would involve the predicate findall or setof. The problem with that approach is that it uses a lot of RAM. What I would be interested in instead is something like:
findmin(MinAtom, Solution, (predicate(MinAtom, Solution))).
This way, the graph search would not need to use a tonne of memory storing all execution paths, and could instead permute through each execution path, only retaining the running minimum solution along the way. Is there a native way of doing this?
I thought of a way to 'shimmy' this sort of behaviour into place, by first taking an arbitrary solution, then finding a solution that does better, and then continuing this process until no better solution is found, at which point the program halts. However, this approach involves some execution duplication while Prolog performs the graph search.
Anyone any insights on how to address this sort of problem in Prolog? It relates somewhat to integer linear programming, but does ILP in the graph search way instead.
I would also be amenable to hacky approaches, e.g. abusing the fail predicate.
Unless there is a subtlety in your question I am missing:
?- aggregate_all(min(X), solution(X), Min).
Min = 1.
?- aggregate_all(max(X), solution(X), Max).
Max = 6.
Unless you break it, this will run in constant memory. Please check the implementation, it is interesting. It shows how you can use Prolog as one of the more basic programming languages.
Is there a native way of doing this?
There is a probably non-portable (across Prolog implementations) way. In the case of SWI-Prolog, the basic idea can be seen in the source code of the library. For max():
aggregate_all(max(X), Goal, Max) :-
!,
State = state(X),
( call(Goal),
arg(1, State, M0),
M is max(M0,X),
nb_setarg(1, State, M),
fail
; arg(1, State, Max),
nonvar(Max)
).
The relevant non-portable predicate is nb_setarg/3. Another annoying limitation is that each "template" is hardcoded, I assume for efficiency. So while you can define your own aggregator, this will take you to back to bagof/findall land, with the current library implementation. You need to hardcode your own "loop" like the library does for the predefined aggregators.