Goal Evaluation with Timeouts

Hello,

My question has two parts. In the first part, I would like to inquire about best logic-programming practices related to coding a specific portion of my program. In the second part, I have more direct programming-related questions.

Part I: My program evaluates goals with different strategies, and has the following blueprint.

% TimeOut is set to some value

program(Goal):-
attempt_strategy_1(Goal);
attempt_strategy_2(Goal);
...
attempt_strategy_n(Goal);

attempt_strategy_k(Goal):-
time_out(strategy_k(Goal), TimeOut, Result),
Result \== time_out.

From problem-domain knowledge, I know that there is almost always a strategy that will solve the problem in less than TimeOut milliseconds ; it’s just not possible to know apriori which one is going to be.

For this reason, I envelop the evaluation of strategies in a time_out/3 predicate as a way of saying “If strategy i is not able to solve the problem in Timeout milliseconds, then move to strategy i+1, and keep doing this because eventually one strategy will solve the problem within TimeOut milliseconds”.

This saves me a great amount of evaluation time as I do not have to exhaustively search all the space of a given strategy if I know that it should have found a solution by now – if it was the right strategy to pursue.

My question: Is there a better way of dealing with this other than using timeouts?

Part II: I overindulged in using timeouts to the point where I started using timeouts within timeouts. I noticed that for the following case:
p1(G):- time_out(p2(G), TimeOut1, Result1).
p2(G):- time_out(G, TimeOut2, Result2).

If TimeOut2 > TimeOut1, say TimeOut1=10000 and TimeOut2=50000, the evaluation of p2(G) will continue past TimeOut1=10000 and up to TimeOut2=50000 if a solution has not been found by then.

My Question: Is this expected, or am I doing something very wrong and convoluted?

Before posting this cry for help, I searched the topics in this forum looking for similar issues; and found that there is a more SWI-like predicate for timeouts namely call_with_time_limit/2.

My Question: Should I be using this latter instead for my timeouts?

Many thanks,
Amine.

I find your current idea to be quite intuitive and practical.

Off the top of my head I can think of only 4 additional ways to make this better.

  1. Make use of tabling if you are not already. (Note I have not used this personally but would do so if presented this problem).
  2. Make use of symbolic execution to calculate Big O, or do it by hand, then compare the Big O for each method.
  3. Use computation graph simplification if possible. See “Deep Learning” by Ian Goodfellow, Yoshua Bengio and Aaron Courville (WorldCat) (Chapter 6 PDF) (site) in section: 6.5.1 Computaional Graphs. Theano has Graph optimization
  4. If you are not after exact results but close enough then change closed world (Prolog) to open world (Neural Network), e.g. train a neural network and then use that. Also read the book as there are many other concepts in the book that might apply, e.g. Structured Probabilistic Models

I would use call_with_inference_limit/3 as it should be immune to CPU load changes AFAIK.


EDIT

The ideas listed above basically look at the algorithm as a computation graph and looks for ways to find the best algorithm using Big O, optimize the exiting algorithm, or reuse previously computed parts.

Another ideas is to look at the data for additional constraints that can be added. For example when parsing data as DCGs and looking at the input data with print_term/2 on slower running parts I can sometimes see a pattern in the data that lead to an added clause that speeds up the parsing. Most of the time the parsing with DCGs should be deterministic and the code that is not running as fast as desired is not running deterministic. By adding the additional clause(s) it becomes deterministic and thus much faster.

In other words an algorithm that is not the best may be one more constraints away from being the best algorithm, but if you don’t check you won’t known.

While I have not tried this with Prolog, it seems using a fuzzer would help with this concept.

First of all your second part. I reproduced this using

:- use_module(library(dialect/sicstus/timeout)).

test :-
    p1((repeat,fail)).

p1(G) :-
    time_out(p2(G), 100, Result1),
    writeln(1:Result1).

p2(G) :-
    time_out(G, 1000, Result2),
    writeln(2:Result2).

After which we get

103 ?- time(test).
2:time_out
1:success
% 2,611,875 inferences, 0.100 CPU in 0.100 seconds (100% CPU, 26145854 Lips)
true.

This is fairly easy to understand. Both schedule an alarm that throws a time_out exception. This will trigger after 0.1 sec in the inner loop, causing this to fail with Result2=time_out. Now the outer alarm scheduler is finished and the inner one got a timeout and killed its alarm. p1/1 now runs to completion (there are no active alarms). As p2/1 succeeds, p1/1 reports success and removes the activated, but still present alarm.

For short, the current implementation doesn’t nest well. A solution is to use a different exception, for example by including the frame reference in the exception. Just tested that. Works fine, so I’ll push that shortly.

As @EricGT says, the fact that this monitors wall time rather than CPU time might be killing, i.e., you may kill the correct strategy because wall time limit kills it although it didn’t use much CPU.

Back to your first question:

SWI’s native support for this is first_solution/3, which exploits multiple threads, using the answer of the first one to complete.

2 Likes

Related, an example using competitive-or parallelism that uses different algorithms to find the root of a function:

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/threads/functions

In this case, instead of using a timeout, the first algorithm that succeeds results in the termination of the other ones (hence the word “competitive”). Depending on the function, some algorithms converge quickly, some converge slowly, and others diverge. If you’re sure that a problem is always solvable using one of the algorithms, even if you don’t know which one, this may be a better solution than relying in possibly arbitrary timeouts.

Wow, I did not know about tabling; I have very entangled parts in my code to memorise proved goals and unprovable goals to speed up the search for goal. I will definitely look into this as it looks very clean and does things transparently without cluttering the code. Cheers!

Thanks a lot, I will be looking into more efficient ways that are based on concurrency.

Be aware that Jan has been adding/updating the tabling code over the last few months so if something doesn’t work as expected, don’t assume you made a mistake. At present it would be best to post it here so Jan can look it over and let you know if you found a bug in the SWI-Prolog tabling code or something. :smiley:

Does first_solution/3 create separate knowledge-base spaces for the different strategies during the concurrent evaluation?

I have asserts and retracts inside the strategies, and they are applied to the same predicates e.g.
strategy_1(Goal):-
% assert(some_info_about(X))
% Strategy 1 Stuff
% retract(some_info_about(X))

strategy_2(Goal):-
% assert(some_info_about(X))
% Strategy 2 Stuff
% retract(some_info_about(X))

So if they share the same knowledge base, data gets corrupted.

P.S. How do you format the code in your answers? I can only use the “</>” button that says “pre-formatted code” which gives me an output that does not even begin to look half as nice as yours.

Check the documentation of the thread_local/1 directive.

Thanks, I finally got it working :slight_smile:

1 Like