Execution model
| Program execution |
|---|
| General concepts |
| Types of code |
| Compilation strategies |
| Notable runtimes |
|
| Notable compilers & toolchains |
|
A programming language consists of a grammar/syntax plus an execution model. The execution model specifies the behavior of elements of the language. By applying the execution model, one can derive the behavior of a program that was written in terms of that programming language. For example, when a programmer "reads" code, in their mind, they walk through what each line of code does. In effect they simulate the behavior inside their mind. What the programmer is doing is applying the execution model to the code, which results in the behavior of the code.
Each and every programming language has an execution model, which determines the manner in which the units of work (that are indicated by program syntax) are scheduled for execution. Detailed examples of the specification of execution models of a few popular languages include those of Python,[1] the execution model of the Unified Parallel C (UPC) programming language, [2] a discussion of various classes of execution model such as for imperative versus functional languages,[3] and an article discussing execution models for real-time embedded languages.[4]
Details of an execution model
Operational Semantics is one method of specifying a language's execution model. The observed behavior of a running program must match the behavior derived from the operational semantics (which define the execution model of the language).
An execution model covers things such as what is an indivisible unit of work, and what are the constraints on the order in which those units of work may take place. For example, the addition operation is an indivisible unit of work in many languages, and in sequential languages such units of work are constrained to take place one after the other.
To illustrate this, consider the C programming language, as described in the book by Kernighan and Richie.[5] C has a concept called a statement. The language specification defines a statement as a chunk of syntax that is terminated by a ";". The language spec then says that "execution of the program proceeds one statement after the other, in sequence". Those words: "execution of the program proceeds one statement after the other, in sequence" are one piece of the execution model of C! Those words tells us that statements are indivisible units of work and that they proceed in the same order as their syntactic appearance in the code (except when a control statement such as IF or FOR modifies the order). By stating that "execution of the program proceeds one statement after the other, in sequence", the programming model has stated constraints on the order of performing units of work.
The C language actually has an additional level to its execution model, which is the order of precedence. Order of precedence states the rules for the order of operations within a single statement. The order of precedence can be viewed as stating the constraints on performing the units of work that are within a single statement. So, ";" and "IF" and "WHILE" cover constraints on the order of statements, while order of precedence covers constraints on work within a statement. Hence, these parts of the C language specification are also part of the execution model of the C language.
Execution models can also exist independently from programming languages, examples of which would be the POSIX Threads library, and Hadoop's Map-Reduce programming model. The implementation of an execution model can be via compiler, or interpreter, and often includes a runtime system.
An implementation of an execution model controls the order in which work takes place during execution. This order may be chosen ahead of time, in some situations, or it can be dynamically determined as the execution proceeds. Most execution models allow varying degrees of both. For example, the C language fixes the order of work within a statement and it fixes the order of all statements, except ones that involve an IF statement or a form of loop statement. Hence, most of the order of execution may be chosen statically, before execution begins, but a small portion must be chosen dynamically, as execution proceeds.
The static choices are most often implemented inside a compiler, in which case the order of work is represented by the order in which instructions are placed into the executable binary. The dynamic choices would then be implemented inside the language's runtime system. The runtime system may be a library, which is called by instructions inserted by the compiler, or the runtime system may be embedded into the executable directly, such as by inserting branch instructions, which make dynamic choices about which work to perform next.
However, an interpreter may also be constructed for any language, in which case all decisions on order of execution are dynamic. An interpreter can be viewed as being part translator, and part execution model implementation.
Assembly language execution model versus implementation by micro-architectures
Assembly languages also have execution models, the same as any other language. Such an execution model is implemented by a CPU micro-architecture. For example, both a 5 stage in-order pipeline and a large out of order CPU implement the same assembly language execution model. The execution model is the definition of the behavior, so all implementations, whether in-order or out-of-order or interpreted or JIT'd etc.. must all give the exact same result, and that result is defined by the execution model.
Parallel Execution Models
In the modern age, parallel programming is an increasingly important topic. Parallel execution models tend to be complex because multiple timelines are simulated, and the points in time at which activities in one timeline are ordered relative to activities in another timeline. For example, the C++11 standard includes sizeable wording that deals with the parallel execution model of the language.
See also
References
- ^ "Python Documentation: Execution Model".
- ^ "UPC Language Features".
- ^ Cardoso, J.M.P.; Diniz, P.C. (2011). "Programming Languages and Execution Models". Springer US. ISBN 9780387096711.
- ^
PELLIZZONI, R.; BETTI, E.; BAK, S.; YAO, G.; CRISWELL, J.; CACCAMO, M.; KEGLEY, R (2011). "A Predictable Execution Model for COTS-based Embedded Systems" (PDF). Real-Time and Embedded Technology and Applications Symposium. IEEE.
{{cite web}}: Unknown parameter|last-author-amp=ignored (|name-list-style=suggested) (help) - ^ Kernighan, Brian W.; Dennis M. Ritchie (February 1978). The C Programming Language (1st ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 0-13-110163-3.