Language Reference/Suspending Predicates
The purpose of suspending predicates is to support asynchronous programming, parallelism, coroutines, etc.
A suspending predicate can suspend its execution and resume it later when 'possible' or 'feasible'. In an asynchronous context, a suspending predicate suspends its execution when it is waiting for an asynchronous operation to complete, allowing other operations to proceed concurrently.
A key advantage of suspending predicates is that they do not block threads while in suspended state, thus enabling efficient utilization of resources. This feature makes them particularly useful in situations where multiple tasks are being executed concurrently.
Example
We want to have a loop that reads messages from a webSocket and echoes them back to the sender. Most of the time this loop would be waiting for some operation to complete; notably waiting for an incoming message. With synchronous code this would mean that a thread would be blocked most of its lifetime, consuming the resources of a thread which doesn't really do much.
Using asynchronous programming with promises/futures, the code could look like this:
class predicates echoLoop_async : (webSocket WebSocket) -> future{unit}. clauses echoLoop_async(WebSocket) = WebSocket:readMessage_async():thenDo( { (Message) = F :- if webSocket::close(Status, Reason) = Message then if 0 <> Status then stdio::writef("Closed:% %\n", Status, Reason) end if, F = future::newUnit() else F = WebSocket:writeMessage_async(Message):thenDo( { = echoLoop_async(WebSocket) % }) end if }).
Such code has several flaws, but here we will just notice that it is both difficult to write and read.
With suspending predicates, the code can be written like this:
class predicates echoLoop_async : (webSocket WebSocket) suspending. clauses echoLoop_async(WebSocket) :- Message = WebSocket:readMessage_async(), if webSocket::close(Status, Reason) = Message then if 0 <> Status then stdio::writef("Closed:% %\n", Status, Reason) end if else WebSocket:writeMessage_async(Message), echoLoop_async(WebSocket) end if.
It is clear that this code looks exactly like synchronous code, and is therefore just as easy to read and write. But while the code looks like synchronous code the execution is quite different as described below.
Language changes
The only new language entity is the keyword suspending which is added to a predicate declaration and/or predicate domain.
domains webSocket_asyncOp = (webSocket WebSocket) suspending. class predicates echoLoop_async : (webSocket WebSocket) suspending. tryCalculate : () -> integer Result determ suspending.
As mentioned earlier, a suspending predicate can pause its execution and resume it later when it's 'possible' or 'feasible.' The use of quotes highlights that the programming language itself doesn't specify the exact conditions for suspension or resumption. However, in certain contexts, the reasons become evident. For instance, when used for asynchronous operations, suspension occurs while waiting for those operations to finish, and execution resumes once they have completed.
Suspension
A suspending predicate has the ability to suspend its execution for various reasons, typically when waiting for an asynchronous operation to complete.
The key concern with suspension is understanding what happens when execution is paused. For instance, how does it differ from blocking in a synchronous operation? In essence, when a predicate suspends, the thread that was executing its code can be utilized for other tasks. Consequently, a suspended predicate does not 'tie up' a thread.
It's important to note that the execution of suspending predicates cannot be solely viewed in the context of a single thread performing a sequence of actions. Instead, a suspending predicate may consist of parts that are executed by different threads, and these threads may also perform other tasks in between executing the parts associated with a particular suspending predicate.
Submitting suspending predicates
Suspending predicates can seamlessly invoke other suspending predicates and non-suspending predicates. However, there are certain limitations on calling non-suspending nondeterm/multi predicates.
When you call a non-suspending predicate, its result is immediately available when the calling thread returns from the call. In contrast, calling a suspending predicate doesn't provide an immediate result because the predicate may suspend execution until an asynchronous operation is complete. Consequently, a non-suspending predicate cannot directly call a suspending one.
Instead, suspending predicates are submitted for execution within a designated execution context, typically using future::submit or future::submit_unit. These routines submits the suspending predicate to an executionContext and returns a future that completes with the result of the suspending predicate. As a result, when a suspending predicate is submitted for execution, the calling thread can continue to perform other tasks while the predicate is being processed.
...
Future = future::submit_unit({ :- echoLoop_async(WebSocket) }),
_ = Future:get(),
...Await
The semantics of a suspending predicate adhere to the same principles as a non-suspending predicate, with the added capability to suspend and later resume execution.
For instance, consider a clause like this:
clauses p_susp() :- q_susp(). r_susp().
In this scenario, the code will initially call q_susp, and only after q_susp has finished will r_susp be called. During this seemingly sequential execution, the execution may suspend multiple times, but r_susp won't be invoked until q_susp has completed.
However, in scenarios involving asynchronous operations, it can be advantageous to initiate multiple independent operations in parallel and then wait for their completion before proceeding with the utilization of their results.
clauses combinePages_susp() = Combined :- Page1 = fetch_susp("https://....."), Page2 = fetch_susp("https://....."), Combined = combine(Page1, Page2).
In this code, the fetching of Page2 won't commence until the fetching of Page1 has completed.
To handle such cases, you can submit a suspending call to the 'background' and obtain a future that can be awaited.
clauses combinePages_susp() = Combined :- Page1Future = future::submit( { = fetch_susp("https://.....") }), Page2 = fetch_susp("https://....."), Page1 = Page1Future:await(), Combined = combine(Page1, Page2).
The first fetch is submitted to the background, and we obtain a future for it. We do not create a future for the second fetch because we have to wait for all fetches to complete anyway, so the last one might just as well be handled in the direct way. After the fetch of Page2 has finished, we await the completion of the fetch of Page1. Then we combine the pages as before.
waitSet
Using the strategy outlined above, we would wait sequentially for the background operations to complete. However, this approach is suboptimal when one or more of the background operations completes with an exception. There are two key issues with this:
- We won't 'notice' the exception until we await that specific operation, which means we may need to wait on several other operations to complete before detecting the exception.
- We won't cancel the other operations even though their results won't be used.
To resolve these issues, we can employ a waitSet, which is a set of futures to wait for. The waitSet itself is also a future that completes when either all the futures in the set have completed successfully or when one of them has completed with an exception (whichever occurs first). If an exception occurs, the waitSet will cancel all the remaining non-completed futures and complete itself with the same exception.
clauses combinePages_susp() = Combined :- WaitSet = waitSet::new(), Page1Future = WaitSet:submit( { = fetch_susp("https://.....") }), Page2Future = WaitSet:submit( { = fetch_susp("https://.....") }), WaitSet:await_unit(), Page1 = Page1Future:await(), Page2 = Page2Future:await(), Combined = combine(Page1, Page2).
Execution and cancellation contexts
When suspending predicates as 'submitted for execution' they will be submitted to execution in an executionContext.
An executionContext provides the infrastructure needed to execute suspending code. Various types of execution contexts are available:
- Threadpools: These enable background processing and parallelism.
- A GUI thread: It executes the suspended parts during message handling steps.
- Regular threads: They enter waiting states to facilitate the resumption of suspended parts.
However, the use of executionContexts can give rise to certain challenges. GUI operations, for example, are typically constrained to a GUI context, while threadpools enable background processing and parallelism. This may necessitate context switching in specific situations (though the exact means for doing so may vary).
Additionally, suspending predicates also execute within a cancellation context.
Both the executionContext and the cancellation context of a suspending 'task' can be accessed through thread-local variables. It's important to note that most programmers need not directly manipulate these variables, as they are managed and utilized through library software (e.g., future's library).
Implementation
The implementation of suspending predicates is primarily designed to fulfill the specified semantics, and it is not necessary for programmers to fully understand the intricacies of the implementation. However, a brief description of the underlying implementation is provided for those interested.
Basically, suspending predicates are transformed into 'ordinary' code, and run as such.
The transformation has three major elements:
- Code Transformation: The code is converted into continuation-based code, where all 'returning' actions are replaced by calls to a continuation. Actual returning is employed when the execution suspends and terminates.
- Stack to Heap: Stack-frames are converted into heap-frames, which can persist in the heap while execution is suspended and can be resumed on any thread.
- Backtrack Points: Backtrack points and trap points for suspending predicates are stored in the heap rather than on the run stack.
A critical aspect of the translation scheme is that each time a suspending predicate is called, it is treated as a final call. Final calls are optimized to discard the current stack frame before making the call, ensuring that the new predicate's stack frame replaces the current one. This means that only one frame is left on the stack, even with nested calls.
When a predicate suspends, it returns from that call and leaves nothing on the stack.
To manage 'what happens next' when a predicate suspends and may return before completing its work, continuations are used. Continuations are predicates that represent 'what to continue with when the current operation is done'.
Continuation predicates are used to handle branching and join back to shared code. For instance, common code after conditional branches is placed into a separate continuation predicate, which is then called at the end of all branches.
This implementation scheme below is illustrative: the actual scheme may differ for various reasons (e.g., optimization). We will use the following naming conventions:
- <name>_susp indicates that the predicate is suspending. Predicates that does not end in _susp are non-suspending.
- Names ending with an underscore represent "translated" predicates and built-in/internal entities.
Let us at first disregard all data and only consider procedures.
A predicate is translated into one that takes an extra continuation argument, where a continuation_ is an (object) predicate with no arguments.
domains continuation_ = ().
The continuation represents what happens after this predicate has done whatever it is supposed to do, i.e. how the computation continues afterwards.
class predicates task_susp : () suspending.
is translated into a predicate task_susp_ that takes a continuation as argument instead of returning:
class predicates task_susp_ : (continuation_ Cont_).
For every suspending predicate we create a heap-frame class. Where a heapframe_ is an object with a single predicate go_:
interface heapframe_ predicates go_ : (). end interface heapframe_
Such a class will have a constructor that receives the continuation (and any original arguments) as arguments.
class task_susp_frm_ : heapframe_ constructors new : (continuation_ Cont_). end class task_susp_frm_
Now let us consider the translation of clauses.
clauses task_susp() :- openChannel(), fetch1_susp(), fetch2_susp(), closeChannel().
The code will "open a channel" by calling a non-suspending predicate openChannel, then it will call the suspending predicate fetch1_susp, and so forth.
The original clause will be transformed into one that takes a continuation as argument, and then constructs a heapframe object and finally invoke go_ on that predicate.
clauses task_susp_(Cont_) :- F = task_susp_frm_::new(Cont_), F:go_().
Notice that the call to go_ is a final call so the stack frame for task_susp_ is replaced by the stack frame for go_. Leaving only one frame on the stack.
The original code of the clause will be moved to the go_ predicate and a number of continuation_ predicates.
Each time we call a suspendable predicate we create a continuation predicate in the class and pass that as the continuation argument to the suspendable predicate (i.e. it's translation).
implement task_susp_frm_ facts cont_ : continuation_. clauses new(Cont_) :- cont_ := Cont_. clauses go() :- openChannel(), fetch1_susp_(cont1_). predicates cont1_ : continuation_. clauses cont1_() :- fetch2_susp_(cont2_). predicates cont2_ : continuation_. clauses cont2_() :- closeChannel(), cont_(). end implement task_susp_frm_
The overall continuation_ is stored in a fact variable, it will be invoked when the entire clause has run to the end. The go_ clause first call the non-suspending predicate openChannel and then it calls the suspending predicate fetch1_susp or rather the translation of this predicate fetch1_susp_. This predicate is called with the continuation_ predicate cont1_. cont1_ represents what happens after the call to fetch1_susp_ has finished, which is calling fetch2_susp_ (the translation of fetch2_susp) with cont2_ as argument. cont2_ represents what happens after the call to fetch2_susp_ has finished, which is calling closeChannel. And since the entire clause is then finished, we end cont2_ with calling cont_, because it represents what happens after this clause.
Notice that the calls to non-suspending predicates (like openChannel) is made in a completely normal way and that these predicates can create stack frames as they like. However all such calls have completed before we call another suspendable predicate. So at the time we call a suspendable predicate the stack only contains the frame of the current suspendable predicate and that frame will be replaced by the new frame because the call to the new suspendable predicate is made as a final call.
Also notice that execution cannot suspend inside a non-suspending predicate, so when suspension takes place there is only one stack frame on the stack, and when we return from that call the stack is completely vacated.
Branching which join back to shared code cause an additional need for continuation predicates as illustrated in this example:
clauses pred_susp() :- if test() then sub_susp() else ordinary() end if, <common code>.
<common code> is the continuation of both branches in the if-then-else. But the call to sub_susp is a final call. So we do not come back to <common code>.
Basically, such common code is put into a separate continuation predicate, which is then called in the end of all branches.
clauses pred_susp() :- if test() then sub_susp(), contX_() else ordinary(), contX_() end if. predicates contX_ : continuation_. clauses contX_() :- <common code>.
Given this transformation there is no longer code to execute after the if-then-else.
Backtracking & exception handling
Backtracking and exception handling are managed in a similar manner in Visual Prolog. In this discussion, we'll primarily focus on the handling of backtracking.
In Visual Prolog, each thread maintains a chain of backtrack points, and there exists a thread-global pointer known as bTop_ that points to the head of this chain. Each backtrack point carries essential information needed to transfer control back to the alternative branch (the failure alternative). When a failure occurs, the system removes the first backtrack point from the chain, adjusts the bTop_ pointer to point to the next backtrack point in the chain, and restores the state based on the information stored in the backtrack point.
The handling of 'cut' (!) involves resetting the bTop_ pointer to a specific value, which is stored in a variable at an earlier point in time. While we won't delve into the intricate details of this process, it's important to note that it involves operations that utilize variables within a clause. Despite the programmer not explicitly specifying the variable, the system manages it like any other variable.
However, when dealing with suspending predicates, two specific issues arise regarding the standard handling of backtracking:
- Backtrack Point Storage: Traditional backtrack points are stored in the stack, which conflicts with the need to entirely clear the stack in case of suspension.
- State Restoration: Non-deterministic (nondeterm</vp/<vp>multi) predicates maintain their state on the stack, allowing backtracking to reset to that specific stack state. However, in a suspending context, this approach is problematic since a suspending predicate may resume execution on a completely different stack.
To address the first issue, suspending predicates allocate backtrack points in the heap instead of storing them on the stack. This ensures that they can persist even when the stack is cleared due to suspension.
Regarding the second issue, a non-suspending backtrack point contains information about how to restore the stack and frame pointers. However, restoring the state in this manner doesn't make sense for suspending predicates because they may resume execution on a different stack. Instead, a suspending backtrack point restores the stack to the location where the suspending predicates have their stack frame. This stack frame remains in the same place throughout the execution of suspendable code, except when it suspends and is later resumed in a different location (note that backtracking doesn't occur while execution is suspended). Thus, during the execution of suspendable code on a particular thread and stack, a thread-global pointer is used to indicate where suspending backtrack points should restore to.
The second issue also affects the state of suspendable nondeterministic predicates themselves. Unlike non-suspending predicates, both suspending and non-suspending backtrack points in suspendable nondeterministic predicates store their state in the heap instead of on the stack. This avoids conflicts with suspension and ensures that state can be managed effectively.
In general, calling non-suspending nondeterm/multi predicates from suspending predicates is not allowed due to the challenges in restoring backtrack points on potentially different stacks. However, it may be possible to do so in cases where it can be guaranteed that all backtracking is completed before reaching a point where a suspending predicate is called. For example, a list comprehension does not leave any backtrack points, so if all calls inside the list comprehension are non-suspending, there is no issue with calling a non-suspending nondeterministic predicate within it.
While it may be difficult to figure out yourself whether those conditions are fulfilled, you don't need to worry the compiler will tell you if there is a problem.
As mentioned, exception handling is handled very similar to backtracking, but simpler in the sense that catch-points cannot be "left-behind" in the same way as backtrack points can. Trap-points are restored when backtracking back into the try section of a try-catch, but the problem that this cause relates to backtracking rather than to the trap-points themselves. Also, in this case the problem is for non-suspending nondeterm/multi predicates.
Windows will however not accept that trap-points are heap allocated. So in on "low level" all exceptions are trapped with completely normal exception trapping code, which then delegates the exception handling to the heap stored trap points:
try <run suspending code> catch TraceId do suspendingExceptionHandling(TraceId) end try
Parameters & Variables
Now let's consider how to deal with parameters, etc.
In Visual Prolog (i.e., for the prolog calling convention) all function return values are transformed into output arguments. So, in the final code there is only input and output arguments, but no return values. Output arguments are handled by passing a pointer to where the result must be stored. So, an output argument is actually a input pointer argument.
The general principle for dealing with parameters and variables from the original code is to store them as fact variables in the heapframe object rather than on the run-stack.
class predicates task_susp : (string Server, string Result [out]) suspending. clauses task_susp(Server, Result) :- openChannel(Server, Channel), fetch_susp(Channel, Result), closeChannel(Channel).
As before the predicate is translated into one with an additional continuation argument. Furthermore, all output arguments are converted to an input pointer argument instead.
class predicates task_susp_ : (contination_ Cont_, string Server, pointerTo{string} ResultPtr_).
Again, we create a heapframe class with a constructor that receives all the arguments of the translated predicate.
class task_susp_frm_ : heapframe_ constructors new : (continuation_ Cont_, string Server, pointerTo{string} ResultPtr_). end class task_susp_frm_
And the original clause is translated into one that creates a heapframe object and invoke go_ as a final call.
clauses task_susp_(Cont_, Server, ResultPtr_) :- F = task_susp_frm_::new(Cont_, Server, ResultPtr_), F:go_().
The heapframe class/object will contain fact variables corresponding to all parameters and variables (optimizations are not considered here). And like before we will place the actual code in the go_ predicate and continuation_ predicates.
implement task_susp_ facts cont_ : continuation_. channel_ : channel. resultPtr_ : ::pointerTo{::string}. server_ : ::string. clauses new(Cont_, Server, ResultPtr_) :- cont_ := Cont_, server_ := Server, resultPtr_ := ResultPtr_. clauses go_() :- fact_address_(channel_, ChannelPtr), openChannel(server_, ChannelPtr), fetch_susp(cont1_, channel_, resultPtr_). predicates cont1_ : continuation_. clauses cont1_() :- closeChannel(channel_), cont_(). end implement task_susp_
There are many details around the handling of the facts that represents parameters and variables. The main principles are:
- Input parameters and variables are represented as facts with their original type. In some places the address of such facts are needed (e.g., ChannelPtr in the call to openChannel).
- Output parameters (of the predicate itself) are received and stored as a pointerTo{...} fact. In some cases, it may be necessary to dereference the pointer (does not occur in this example).