Is it possible to create something like call_with_time_limit (+Time, :Goal) https://www.swi-prolog.org/pldoc/doc_for?object=call_with_time_limit/2 which instead of killing the Goal after Time seconds “forks” it – ie runs the goal concurrently in the background – while continuing on with the program?
Nice thought. It will be pretty hard though. There is a semantic issue as to what it means for the remainder of the program to continue if Goal shares variables with its environment. Disregarding that, you would need to be able to capture the partially evaluated state and migrate it to another thread.
With some restrictions, this might be possible using delimited continuations. I.e., run the goal under reset/3 and make the timeout signal call shift/1. Now if reset/3 returns with a continuation you can restart that in another thread. If reset/3 returns normally, there was no timeout.
The only reason why this fails is that the timeout is handled using an interrupt handler that is executed inside an embedded C environment and shift/1 doesn’t find the matching reset/3 as that is in another environment. This isn’t easy to fix as this would imply capturing the C continuation in addition to the Prolog one. It might work if we could somehow relay this to use the constraint wakeup mechanism which executes delayed goals in the normal Prolog context. In general that is not really what you want as both failure and non-determinism of such a goal affect the execution of the program in which the goal is injected. Currently only exceptions raised by an interrupt handler are propagated.
For short, I think it is doable but not for timeouts that happen in foreign functions such as waiting for I/O.
On the other hand, if the goal takes a significant amount of time you can run it directly in a thread. Creating and joining a thread takes (depending on OS and hardware) about 30us:
t(N) :-
( N > 0
-> thread_create(true, Id),
thread_join(Id),
N2 is N - 1,
t(N2)
; true
).
?- time(t(100 000)).
% 600,002 inferences, 1.858 CPU in 2.917 seconds (64% CPU, 322851 Lips)
Ubuntu 19.04, Intel i7-5557U CPU (2 cores, 4 threads)
1 Like
Many thanks for that prompt reply @Jan. It’s definitely put me on the right track. I’ve never programmed with threads before, so it’s fairly enlightening (and bewildering) for me.
thread_get_message/3 https://www.swi-prolog.org/pldoc/doc_for?object=thread_get_message/3 has a timeout option which I think is what I want.
My initial attempt looks something like this:
%% best_answer_within_timelimit(+Time, :Goal)
best_answer_within_timelimit(Time, mygoal(Input, Output)) :-
thread_create(aux_predicate(Time, mygoal(Input, Output)), Id),
thread_join(Id).
aux_predicate(Time, mygoal(Input, Output)) :-
setup_call_cleanup(
message_queue_create(Queue),
( mygoal(Input, Output),
thread_send_message(Queue, Output),
( thread_get_message(Queue, Output, [timeout(Time)])
-> format('Proceed with solution ~w~n', [Output])
; format('Quickly make a guess for time being~n')
)
),
message_queue_destroy(Queue)
).
That seems to work ok provided I don’t try to return Output from the auxiliary predicate, which results in an undefined variable in the calling predicate best_answer_within_timelimit.
This is a bit strange. I’d expect the initial thread to wait for a message from the created thread. As is, you do a send and then a get message from the same queue in the same thread, so that always succeeds!?
An example how to get results from executing something in a thread is here. This is a different task, injecting a goal into another thread to get information about the status of this thread.
1 Like
Ok, my shakey understanding of threads and message queues has advanced to the point where I can get this to work intermittently:
%% best_answer_within_timelimit(+Time, :Goal) is det
best_answer_within_timelimit(Time, mygoal(Input, Output)) :-
thread_create(aux_predicate(mygoal(Input, Output)), Id),
( catch(thread_get_message(Id, Output, [timeout(Time)]),
Error,
true)
-> ( var(Error)
-> format('Proceed with solution ~w~n', [Output])
; format('Oops: ~w~n', [Error]),
plan_b(Input, Output)
)
; plan_b(Input, Output)
),
thread_join(Id, true).
aux_predicate(mygoal(Input, Output)) :-
thread_self(Id),
mygoal(Input, Output),
thread_send_message(Id, Output).
Now what happens is if I start with a freshly fired up swipl command line and consulted file, it works. But if I run it again, I get:
Oops: error(existence_error(message_queue,<thread>(10,0x562b36e052c0)),context(system:thread_get_message/3,_10782))
Or without the formatted error message handed by catch/3
ERROR: /home/roblaing/src/tests/chess.plt:116:
test thread1: received error: thread_get_message/2: message_queue `<thread>(9,0x562b36e1aac0)' does not exist
The main thread is listening on the queue of the thread it created. That is to some extend possible, but rather dubious. Such is aux_predicate/1 which sends a message to itself. Normally, the main thread either passes its identity to the thread it creates such that this thread knows where to report to or it creates a dedicated queue for this purpose that it passes on. So, you get something like this:
main :-
thread_self(Me),
thread_create(child(Me, Task), Id).
thread_get_message(Reply),
....
child(Master, Task) :-
run Task
thread_send_message(Master, Result).
There are lots of variations possible 
Which one is best depends on many factors such as the possibility of one of the threads failing and what should then happen to the other, whether you care where the answer comes from or more in general which conversations between threads may be going on in the process.
1 Like
Many thanks for the prompt reply as always @Jan. Capturing the parent thread Id (which I’ve called Consumer because I read threads with message queues fall under the producer-consumer pattern) and sending that as an argument to the “producer” aux_predicate seems to have fixed the intermittent error problem. Hopefully this gets the basics on track. I’ll try write a tutorial once I’ve got it figured out. As you can see, I’m very much a novice at this stuff.
%% best_answer_within_timelimit(+Time, :Goal) is det
best_answer_within_timelimit(Time, mygoal(Input, Output)) :-
thread_self(Consumer),
thread_create(aux_predicate(Consumer, Input), Id),
( catch(thread_get_message(Consumer, Output, [timeout(Time)]),
Error,
true)
-> ( var(Error)
-> format('Proceed with solution ~w~n', [Output])
; format('Oops: ~w~n', [Error]),
plan_b(Input, Output)
)
; plan_b(Input, Output)
),
thread_join(Id, true).
aux_predicate(Producer, Input) :-
mygoal(Input, Output),
thread_send_message(Producer, Output).