Thomas Linder Puls: Suspending predicates (initial)

2024-01-04T13:03:12Z

Suspending predicates (initial)

New page

{{languageReferenceNavbar|Suspending Predicates}}

{{Template:NonReleased}}

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 ===

{{Example|
We want to have a loop that reads messages from a <vp>webSocket</vp> 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:
<vip>
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
}).
</vip>
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:
<vip>
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.
</vip>
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 <vp>suspending</vp> which is added to a predicate declaration and/or predicate domain.

<vip>
domains
webSocket_asyncOp = (webSocket WebSocket) suspending.
class predicates
echoLoop_async : (webSocket WebSocket) suspending.
tryCalculate : () -> integer Result determ suspending.
</vip>

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 <vp>nondeterm</vp>/<vp>multi</vp> 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 <vp>future::submit</vp> or <vp>future::submit_unit</vp>. These routines submits the suspending predicate to an <vp>executionContext</vp> and returns a <vp>future</vp> 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.

{{Example|Here we submit the <vp>echoLoop_async</vp> predicate from above and wait for the completion:
<vip>
...
Future = future::submit_unit({ :- echoLoop_async(WebSocket) }),
_ = Future:get(),
...
</vip>}}

=== 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:
<vip>
clauses
p_susp() :-
q_susp().
r_susp().
</vip>

In this scenario, the code will initially call <vp>q_susp</vp>, and only after <vp>q_susp</vp> has finished will <vp>r_susp</vp> be called. During this seemingly sequential execution, the execution may suspend multiple times, but <vp>r_susp</vp> won't be invoked until <vp>q_susp</vp> 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.

{{Example|For example, consider this code:
<vip>
clauses
combinePages_susp() = Combined :-
Page1 = fetch_susp("https://....."),
Page2 = fetch_susp("https://....."),
Combined = combine(Page1, Page2).
</vip>
In this code, the fetching of <vp>Page2</vp> won't commence until the fetching of <vp>Page1</vp> has completed.
}}

To handle such cases, you can <vp>submit</vp> a suspending call to the 'background' and obtain a <vp>future</vp> that can be <vp>await</vp>ed.

{{Example|Here's an example based on the previous clause:
<vip>
clauses
combinePages_susp() = Combined :-
Page1Future = future::submit( { = fetch_susp("https://.....") }),
Page2 = fetch_susp("https://....."),
Page1 = Page1Future:await(),
Combined = combine(Page1, Page2).
</vip>
The first fetch is submitted to the background, and we obtain a <vp>future</vp> for it. We do not create a <vp>future</vp> 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 <vp>Page2</vp> has finished, we <vp>await</vp> the completion of the fetch of <vp>Page1</vp>. 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 <vp>await</vp> that specific operation, which means we may need to wait on several other operations to complete before detecting the exception.
* We won't <vp>cancel</vp> the other operations even though their results won't be used.

To resolve these issues, we can employ a <vp>waitSet</vp>, which is a set of <vp>future</vp>s to wait for. The <vp>waitSet</vp> itself is also a <vp>future</vp> that completes when either all the <vp>future</vp>s in the set have completed successfully or when one of them has completed with an exception (whichever occurs first). If an exception occurs, the <vp>waitSet</vp> will <vp>cancel</vp> all the remaining non-completed futures and complete itself with the same exception.

{{Example|Here's an example using a <vp>waitSet</vp>:
<vip>
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).
</vip>
It's worth noting that the actual waiting occurs in <vp>WaitSet:await_unit()</vp>. If one of the operations completes with an exception, that exception will become evident at that line of code.}}

=== Execution and cancellation contexts ===

When suspending predicates as 'submitted for execution' they will be submitted to execution in an <vp>executionContext</vp>.

An <vp>executionContext</vp> 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 <vp>executionContext</vp>s 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 <vp>executionContext</vp> and the <vp>cancellation</vp> 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., <vp>future</vp>'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:

* <vp><name>_susp</vp> indicates that the predicate is suspending. Predicates that does not end in <vp>_susp</vp> 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 <vp>procedure</vp>s.

A predicate is translated into one that takes an extra continuation argument, where a <vp>continuation_</vp> is an (object) predicate with no arguments.
<vip>
domains
continuation_ = ().
</vip>

The continuation represents what happens after this predicate has done whatever it is supposed to do, i.e. how the computation ''continues'' afterwards.

{{Example|The predicate
<vip>
class predicates
task_susp : () suspending.
</vip>
is translated into a predicate <vp>task_susp_</vp> that takes a continuation as argument instead of returning:
<vip>
class predicates
task_susp_ : (continuation_ Cont_).
</vip>
}}

For every suspending predicate we create a heap-frame class. Where a <vp>heapframe_</vp> is an object with a single predicate <vp>go_</vp>:

<vip>
interface heapframe_
predicates
go_ : ().
end interface heapframe_
</vip>

Such a class will have a constructor that receives the continuation (and any original arguments) as arguments.

{{Example|For the predicate above we will create a class like this:
<vip>
class task_susp_frm_ : heapframe_
constructors
new : (continuation_ Cont_).
end class task_susp_frm_
</vip>
}}

Now let us consider the translation of clauses.

{{Example|We will consider this clause
<vip>
clauses
task_susp() :-
openChannel(),
fetch1_susp(),
fetch2_susp(),
closeChannel().
</vip>
The code will "open a channel" by calling a non-suspending predicate <vp>openChannel</vp>, then it will call the suspending predicate <vp>fetch1_susp</vp>, 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 <vp>go_</vp> on that predicate.

{{Example|The clause will look like this
<vip>
clauses
task_susp_(Cont_) :-
F = task_susp_frm_::new(Cont_),
F:go_().
</vip>
Notice that the call to <vp>go_</vp> is a final call so the stack frame for <vp>task_susp_</vp> is replaced by the stack frame for <vp>go_</vp>. Leaving only one frame on the stack.
}}

The original code of the clause will be moved to the <vp>go_</vp> predicate and a number of <vp>continuation_</vp> 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).

{{Example|For the clause above the class will look like this:
<vip>
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_
</vip>
The overall <vp>continuation_</vp> is stored in a fact variable, it will be invoked when the entire clause has run to the end.
The <vp>go_</vp> clause first call the non-suspending predicate <vp>openChannel</vp> and then it calls the suspending predicate <vp>fetch1_susp</vp> or rather the translation of this predicate <vp>fetch1_susp_</vp>. This predicate is called with the <vp>continuation_</vp> predicate <vp>cont1_</vp>.
<vp>cont1_</vp> represents what happens after the call to <vp>fetch1_susp_</vp> has finished, which is calling <vp>fetch2_susp_</vp> (the translation of <vp>fetch2_susp</vp>) with <vp>cont2_</vp> as argument.
<vp>cont2_</vp> represents what happens after the call to <vp>fetch2_susp_</vp> has finished, which is calling <vp>closeChannel</vp>. And since the entire clause is then finished, we end <vp>cont2_</vp> with calling <vp>cont_</vp>, because it represents what happens after this clause.
}}

Notice that the calls to non-suspending predicates (like <vp>openChannel</vp>) 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:

{{Example|Consider this clause
<vip>
clauses
pred_susp() :-
if test() then
sub_susp()
else
ordinary()
end if,
<common code>.
</vip>
<vp><common code></vp> is the continuation of both branches in the <vp>if-then-else</vp>. But the call to <vp>sub_susp</vp> 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.

{{Example|Consider this as a kind of "schematic middle step":
<vip>
clauses
pred_susp() :-
if test() then
sub_susp(),
contX_()
else
ordinary(),
contX_()
end if.

predicates
contX_ : continuation_.
clauses
contX_() :-
<common code>.
</vip>
Given this transformation there is no longer code to execute after the <vp>if-then-else</vp>.
}}

==== 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 <vp>bTop_</vp> 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 <vp>bTop_</vp> 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' (<vp>!</vp>) involves resetting the <vp>bTop_</vp> 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 (<vp>nondeterm</vp/<vp>multi</vp>) 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 <vp>nondeterm</vp>/<vp>multi</vp> 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:

{{Example|The code for this will look something like this:
<vip>
try
<run suspending code>
catch TraceId do
suspendingExceptionHandling(TraceId)
end try
</vip>
Where <vp>suspendingExceptionHandling</vp> will find the heap allocated trappoint chain and delegate the exception handling to it.}}

==== Parameters & Variables ====

Now let's consider how to deal with parameters, etc.

In Visual Prolog (i.e., for the <vp>prolog</vp> 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.

{{Example|Several of the predicates here would more naturally be functions, but to maintain focus we will make them into predicates with output variables ourselves. We have also simplified the clause by only having one fetch, this will simplify the example without loosing any essence.
<vip>
class predicates
task_susp : (string Server, string Result [out]) suspending.
clauses
task_susp(Server, Result) :-
openChannel(Server, Channel),
fetch_susp(Channel, Result),
closeChannel(Channel).
</vip>
}}

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.

{{Example|
<vip>
class predicates
task_susp_ : (contination_ Cont_, string Server, pointerTo{string} ResultPtr_).
</vip>
}}

Again, we create a heapframe class with a constructor that receives all the arguments of the translated predicate.

{{Example|The class looks like this
<vip>
class task_susp_frm_ : heapframe_
constructors
new : (continuation_ Cont_, string Server, pointerTo{string} ResultPtr_).
end class task_susp_frm_
</vip>
}}

And the original clause is translated into one that creates a heapframe object and invoke <vp>go_</vp> as a final call.

{{Example|The clause will look like this
<vip>
clauses
task_susp_(Cont_, Server, ResultPtr_) :-
F = task_susp_frm_::new(Cont_, Server, ResultPtr_),
F:go_().
</vip>
}}

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 <vp>go_</vp> predicate and <vp>continuation_</vp> predicates.

{{Example|The code will look like this:
<vip>
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_
</vip>
}}

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., <vp>ChannelPtr</vp> in the call to <vp>openChannel</vp>).
* 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).

[[Category:Language|{{PAGENAME}}]]

← Older revision		Revision as of 14:58, 16 April 2024
Line 480:		Line 480:
	* Input parameters and variables are represented as facts with their original type. In some places the address of such facts are needed (e.g., <vp>ChannelPtr</vp> in the call to <vp>openChannel</vp>).		* Input parameters and variables are represented as facts with their original type. In some places the address of such facts are needed (e.g., <vp>ChannelPtr</vp> in the call to <vp>openChannel</vp>).
	* 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).		* 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).

	~~[[Category:Language\|{{PAGENAME}}]]~~

← Older revision		Revision as of 14:01, 11 January 2024
Line 1:		Line 1:
	{{languageReferenceNavbar\|Suspending Predicates}}		{{languageReferenceNavbar\|Suspending Predicates}}

	~~{{Template:NonReleased}}~~

	The purpose of '''suspending''' predicates is to support asynchronous programming, parallelism, coroutines, etc.		The purpose of '''suspending''' predicates is to support asynchronous programming, parallelism, coroutines, etc.

Language Reference/Suspending Predicates - Revision history

Thomas Linder Puls: Category

Thomas Linder Puls: Released

Thomas Linder Puls: Suspending predicates (initial)