Function Execution

Abstract Computational Model

The sequential computational model for function execution can be seen as one possible sequential implementation of a concurrent computational model. We can obtain such a concurrent computational model by abstracting from the details of how a function is scheduled for execution.

Abstract Function Call

In abstraction, from the caller's viewpoint the call of the function can be seen as the sending of arguments to the function and the receiving of the return value. Together with similar abstractions on the functions side we get the following scheme.
  1. Caller sends arguments to function.
    1. Function receives arguments.
    2. Function executes its body.
    3. Function sends return value to caller.
  2. Caller receives return value and continues execution.
This scheme does not allow for recursive function calls. It also assumes there is a function present for receiving the arguments, but the function first has to come into existence.

Function Instance Controller

In order to solve the shortcomings of the scheme above, a mechanism is needed that creates an instance of the function when it is called, corresponding to the setup of an environment for the function in the sequential computational model. Such a mechanism also has to take care of the return values from these instances and the destruction of the instances after execution. Below we show a scheme in which this mechanism is called the controller.
  1. Caller sends function-name and arguments to controller.
    1. Controller receives function-name and arguments.
    2. Controller creates an instance of the function.
    3. Controller sends arguments to function.
      1. Function receives arguments.
      2. Function executes its body.
      3. Function sends return value to controller.
    4. Controller receives return value.
    5. Controller disposes the instance of the function.
    6. Controller sends return value to caller.
  2. Caller receives return value and continues execution.
The abstract viewpoints for the caller and the function are still there, but now the controller acts as intermediate.

In this scheme, the controller operates in concurrency with the sequential instruction execution. This makes it possible to separate the concerns of the communication between the two and their internal operation.

Scheduling of Functions

In the scheme above we can relax the constraints that a function has to wait for the value returned by the called function and that the controller immediately has to take action on a call of a function. Execution of instructions might as well continue until a certain point where the return value is needed. The controller may wait with creating an instance of a function until some criterion is met, such as the availability of resources, the moment the return value is needed, etc. This is typically the concept of a scheduler.

The tasks of a scheduler consists of receiving function call requests, controlling function execution, and sending return values back. Controlling function execution consists of the following steps.

  1. Scheduler sets up an environment and makes the arguments available in the environment.
  2. The function is executed in the environment.
  3. The environment is taken down.
There may be more than one function waiting for execution and they are not necessarilly executed in the order in which they are called. To deliver the right return values it is necessary to identify the calls and the instances. This can be done by providing instances of functions with identifiers that have to be send along with the messages.

Concurrent Execution

With the scheme presented above concurrent execution of function instances is possible. Since it is not necessary to wait for the return value of a function, other instructions can be executed concurrently with the execution of the function. At the same time other function calls can be executed as well, resulting in massive concurrent execution of functions. For parallel execution to happen, more than one sequential instruction executor has to be available. The scheduler has to use these sequential instruction executors as resources for execution of functions.