
\chapter{Interpreter for the message-driven code}
\label{chap:compiler}

According to the algorithm presented in the \hyperref[chap:scheduler]{Scheduler chapter} and
parallel message-driven program schema (figure \ref{fig:parallel_schema}) in the
\hyperref[chap:scheduler]{Motivation chapter}, it is evident that list of the affected global
variables by message processing is needed by the scheduler to operate.

In this chapter, the programming language is proposed whose syntax, and semantics is created
explicitly to \textit{semantically restrict} all valid programs to the message-driven programming
paradigm. These restrictions aim to allow static analysis of the program code which automatically
generates \textit{read/written variables extraction function}. This function, based on the message,
determines global variables that will be read or altered during program execution on the given message.

\section{Programming language proposal}

Following sections contain the syntax and the semantics of the programming language, which will be
used in the experiments presented in this diploma thesis \cite{syntaxSemantics}. This language is more
high-level than simple assembly, so it is not that hard to write programs in it. However, it is still
quite low-level, so it is trivial to implement, and it is simple to analyze statically.

\subsection{Main concept and philosophy}

First of all, the proposed programming language has to be \textit{Turing complete}. Main needed feature
for \textit{Turing completeness} is some form of the looping \cite{turingCompleteness}. For this purpose,
recursive calls, and therefore function declaring, will be possible in the proposed programming language.

Secondly, static analysis, which is needed to extract altered global variables, has to be possible. This is
a reason why some low-level features have to be excluded, e.g., dynamic controlling of the program flow.
Therefore, no dynamic address jumps, which are possible in the assembler languages, will be possible.

It is also desirable to increase the potential number of variables that will be identifiable in the programs.
To achieve this the special built-in type is present in the programming language - \textit{object type}.
This type allows the creation of the nested structures and has built-in syntactic support in the programming language:
\begin{figure}[H]
  \begin{lstlisting}
  global.obj.subObj.subSubObj.field = 10
  \end{lstlisting}
  \caption{Syntactic support for the object type}
  \label{fig:object_creation}
\end{figure}
This is syntactically valid statement, which creates three objects, \textit{obj, subObj} and \textit{subSubObj},
and assign integer value to the field named \textit{field} of the object \textit{subSubObj}. Thanks to the fact
that this is the only syntax for creating objects, it is possible that nested fields can also be identified as
separate variables that are passed to the scheduler.

There are only two predefined top-level objects scoping all variables that make the syntax clear and explicit:
\begin{enumerate}
  \item \textit{global} - the object that represents global program state which is preserved across processing
  of multiple messages. The static analyzer analyzes access to this object and creates function, which returns
  list of \textit{paths} (e.g. \textit{obj.subObj.subSubObj.field}) that are \textit{read or altered} by
  processing of specific message.

  \item \textit{local} - the object that is specific to each function call. Every function call creates new
  \textit{local} object for the function and assigns arguments to the object's fields. Other fields can be
  created during function execution.
\end{enumerate}

Every message is processed by the \textit{main} function which is defined by the programmer. This function has
only one argument of the \textit{object type} - actual message to be processed. The return value of this function
is also of the \textit{object type} and contains information about the action that should be done by the runtime
system, e.g., logging, HTTP request sending or writing to the file. This function can produce side-effects
in terms of global variable assignments. This function can call other, potentially recursive, functions that can
also have side-effects.

\subsection{Syntax and semantics}

\subsubsection*{\textbf{Function declaration}}

To allow code reusing and recursive calls declaring named functions is possible with the following syntax:

\begin{figure}[H]
  \begin{lstlisting}
  def func(arg1, arg2)
    {Assignment statements / Control-flow statements}
  end
  \end{lstlisting}
  \caption{Schema of the function declaration}
\end{figure}

This declaration creates function named \textit{func} which takes two arguments. These arguments can be
accessed by the \textit{local.arg1} and \textit{local.arg2}names. Every function has a return value, so it
is not explicitly stated in the declaration. No types are declared for the function, however, each value has
its type in the language. These types are checked dynamically during execution when built-in functions are called.

\subsubsection*{\textbf{Literal and field name statements}}

Constant literals are the only way how to create new values in the programming language:
\begin{figure}[H]
  \begin{lstlisting}
  42
  100.0
  true
  false
  'c'
  "string"
  \end{lstlisting}
  \caption{Examples of the constant literals}
\end{figure}
These literals can be used in more complex statements of the programming language.
Exact usage is shown in the following sections.

Despite creating new values, there is also another way how to reference values in
the programming language - \textit{field names}:
\begin{figure}[H]
  \begin{lstlisting}
  local.x
  local.x.y
  local.x.y.y
  global.x
  global.x.y
  global.x.y.y
  \end{lstlisting}
  \caption{Examples of the field names}
\end{figure}

Nested structure of the field names is a very important feature of the programming language. It
allows creating the nested structures that are essential for many algorithms. These structures are
possible because each value under fields with the name starting with \textit{local.x.} are contained
in the \textit{local.x} object, i.e., all these values are copied when the object \textit{local.x} is copied.

\subsubsection*{\textbf{Assignment statements}}

Assignments are a driving mechanism of the program computation. There are three types of the assignments:
\begin{enumerate}
  \item \textit{The constant assignment} which allows assignment of any valid constant
  literal to specific global or local field:
  \begin{figure}[H]
    \begin{lstlisting}
     {Field name} = {Constant literal}
    \end{lstlisting}
    \caption{Schema of the constant assignment statement}
    \label{fig:assign_constant}
  \end{figure}

  \item \textit{The copy assignment} which copies the value of any global or local field
  to another global or local field:
  \begin{figure}[H]
    \begin{lstlisting}
    {Field name} = {Field name}
    \end{lstlisting}
    \caption{Schema of the copy assignment statement}
    \label{fig:assign_copy}
  \end{figure}

  \item \textit{The function call assignment} which calls the function and copies its
  result to the specified global or local field:
  \begin{figure}[H]
    \begin{lstlisting}
    {Field name} = func({Constant literal / Field name},
                        {Constant literal / Field name})
    \end{lstlisting}
    \caption{Schema of the function call assignment statement}
    \label{fig:assign_call}
  \end{figure}
  This statement calls a function named \textit{func} with two arguments and copies its result
  into the \textit{\{Field name\}} field.
\end{enumerate}

\subsubsection*{\textbf{Control-flow statements}}

Controlling the execution flow of the program is the essential requirement for each programming
language. Without controlling execution flow, each program run will be almost the same even on
different input data, and that is not enough for most of the algorithms.

For controlling execution flow, two types of statements are usable:
\begin{enumerate}
  \item \textit{The condition statement} which branches the execution based on field's
  boolean value:
  \begin{figure}[H]
    \begin{lstlisting}
    if {Field name}
      {Assignment statements / Control-flow statements}
    else
      {Assignment statements / Control-flow statements}
    end
    \end{lstlisting}
    \caption{Schema of the condition statement}
    \label{fig:condition}
  \end{figure}
  This statement checks value of the \textit{\{Field name\}} field. If it is \textit{true} first set of
  statements is executed, if it \textit{false} second set of statements is executed. Any other value leads
  to a program termination with an error. After execution of the appropriate set of statements after the
  condition is executed.

  \item \textit{The return statement} which stops the execution of the current function and returns
  the value to the caller:
  \begin{figure}[H]
    \begin{lstlisting}
    return {Field name / Constant literal}
    \end{lstlisting}
    \caption{Schema of the return statement}
    \label{fig:return}
  \end{figure}
  If the function doesn't have \textit{return} statement or its execution doesn't reach any, special value
  \textit{null} is returned. This value is discussed in the section below.
\end{enumerate}

\subsection{Built-in data types}

Language provides few built-in data types, their usage is implicit and no special declaration
is needed to specify usage of concrete type. Values of these types are created only by constant
literals. Exception is the \textit{object type} which allows on-demand creation by the syntax introduced
in the \hyperref[fig:object_creation]{Figure \ref{fig:object_creation}}.

\begin{table}[H]
  \begin{tabular}{| C{2cm} | C{3cm} | C{3cm} | C{3cm} |}
    \hline
    \textbf{Name} & \textbf{Possible values} & \textbf{Default value} & \textbf{Literal examples} \\ \hline

    Object & List of variables & null & null \\ \hline

    Boolean & true, false & false & true, false \\ \hline

    Integer & from \( -2^{63} - 1 \) to \( 2^{63} - 1 \) & 0 & -1, -2, 1, 2 \\ \hline

    Float & approx. from \( -1.7 \cdot 10^{-308} \) to \( 1.7 \cdot 10^{308} \) & 0.0 & -1.5, -10.0, 1.5, 10 \\ \hline

    Char & arbitrary unicode character & U+0000 & 'c', '0' \\ \hline

    String & sequence of \textit{Char} values & "" & "Hello", "World" \\ \hline
  \end{tabular}
  \caption{Built-in data types}
\end{table}

\subsection{Built-in functions}

In addition to built-in data types, many built-in functions, which operate on values of these types, are provided.
These functions can be divided into several groups.

First of all, there are functions for an equality checking. These can operate on any given built-in type except
the \textit{object type}.

\begin{table}[H]
  \begin{tabular}{| C{3.5cm} | C{8cm} |}
    \hline
    \textbf{Signature} & \textbf{Description} \\ \hline

    \_eq(val1, val2) &
    Returns \textit{\textbf{true}} if both values have the same type and value, \textit{\textbf{false}} otherwise. \\ \hline

    \_neq(val1, val2) &
    Returns \textit{\textbf{true}} if both values doesn't have the same type or their values differ, \textit{\textbf{false}} otherwise. \\ \hline

  \end{tabular}
  \caption{Built-in functions for an equality checking}
\end{table}

For scalar types, i.e., integer, floating-point and char types, value comparing is also possible.
These comparing functions are defined only for arguments of the same scalar type. All other types
of arguments lead to program termination with an error.

\begin{table}[H]
  \begin{tabular}{| C{3.5cm} | C{8cm} |}
    \hline
    \textbf{Signature} & \textbf{Description} \\ \hline

    \_lt(val1, val2) &
    Returns \textit{\textbf{true}} if \textit{val1} is lower than \textit{val2}, \textit{\textbf{false}} otherwise. \\ \hline

    \_gt(val1, val2) &
    Returns \textit{\textbf{true}} if \textit{val1} is greater than \textit{val2}, \textit{\textbf{false}} otherwise. \\ \hline

    \_leqt(val1, val2) &
    Returns \textit{\textbf{true}} if \textit{val1} is lower or equal than \textit{val2}, \textit{\textbf{false}} otherwise. \\ \hline

    \_geqt(val1, val2) &
    Returns \textit{\textbf{true}} if \textit{val1} is greater or equal than \textit{val2}, \textit{\textbf{false}} otherwise. \\ \hline

  \end{tabular}
  \caption{Built-in functions for scalar types comparing}
\end{table}

For the integer type, special modulo function is provided. This function can be called only with both
arguments set to integer values. Using any other argument types leads to a program execution error.

\begin{table}[H]
  \begin{tabular}{| C{3.5cm} | C{8cm} |}
    \hline
    \textbf{Signature} & \textbf{Description} \\ \hline

    \_mod(val1, val2) & Returns value of \textit{\textbf{val1 \% val2}}. \\ \hline

  \end{tabular}
  \caption{Built-in functions for the integer type}
\end{table}

Numeric types can be used in basic arithmetic functions. These functions can operate only if both
arguments are of the integer type, or both are of the floating-point type. Any other types terminate
a program execution with an error.

\begin{table}[H]
  \begin{tabular}{| C{3.5cm} | C{8cm} |}
    \hline
    \textbf{Signature} & \textbf{Description} \\ \hline

    \_add(val1, val2) & Returns value of \textit{\textbf{val1 + val2}}. \\ \hline

    \_sub(val1, val2) & Returns value of \textit{\textbf{val1 - val2}}. \\ \hline

    \_mul(val1, val2) & Returns value of \textit{\textbf{val1 * val2}}. \\ \hline

    \_div(val1, val2) & Returns value of \textit{\textbf{val1 / val2}}. \\ \hline

  \end{tabular}
  \caption{Built-in functions for integer and floating-point arithmetic}
\end{table}

For integer and boolean types, it is possible to define boolean logic functions. On booleans
their behavior is apparent. On integers, they compute the result in the bit by bit manner.
If these functions are used on any other type, a program is terminated with an error.

\begin{table}[H]
  \begin{tabular}{| C{3.5cm} | C{8cm} |}
    \hline
    \textbf{Signature} & \textbf{Description} \\ \hline

    \_and(val1, val2) &
    Performs \textbf{and} boolean operation between the \textit{val1} and \textit{val2} and returns the result. \\ \hline

    \_or(val1, val2) &
    Performs \textbf{or} boolean operation between the \textit{val1} and \textit{val2} and returns the result. \\ \hline

    \_xor(val1, val2) &
    Performs \textbf{exclusive-or} boolean operation between the \textit{val1} and \textit{val2} and returns the result. \\ \hline

    \_neg(val) &
    Flips each bit in the \textit{val} and returns the result. \\ \hline

  \end{tabular}
  \caption{Built-in functions for a boolean logic}
\end{table}

String type is unique and needs some functions for manipulation. Executing these functions on
non-string type terminates a program execution with an error.

\begin{table}[H]
  \begin{tabular}{ | C{3.5cm} | C{8cm} |}
    \hline
    \textbf{Signature} & \textbf{Description} \\ \hline

    \_len(str) &
    Returns length of the string \textit{str} as an integer value. \\ \hline

    \_ch(str, index) &
    Returns character of the string \textit{str} at position \textit{index} as a char value \\ \hline

    \_con(str1, str2) &
    Returns concatenation of two strings. \\ \hline

  \end{tabular}
  \caption{Built-in functions for a string manipulation}
\end{table}

In addition to all these functions, some more are provided for value conversions and computation simulations.

\begin{table}[H]
  \begin{tabular}{| C{3cm} | C{3.5cm} | C{5cm} |}
    \hline
    \textbf{Signature} & \textbf{Possible arguments types} & \textbf{Description} \\ \hline

    \_integer(val) & Integer, Float, Boolean, Char &
    Returns \textit{integer} representation of the given value. \\ \hline

    \_float(val) & Float, Integer &
    Returns \textit{float} representation of the given integer value. \\ \hline

    \_sleep(duration, val) & Integer and Any &
    Returns \textit{val} and simulates computation taking \textit{duration} milliseconds. \\ \hline

  \end{tabular}
  \caption{Built-in utility functions and functions for conversions}
\end{table}

\section{Static analysis of the program code}

Static program analysis is a process which is very often used in software verification tools \cite{verification}
to catch many potential errors before a program is even executed. Some forms of the static program analysis are
also used in compilers to optimize code execution \cite{compilerConstruction}, e.g., death code elimination.

Even though it is not apparent, optimization of the code execution is also the final aim of static analysis
described in this diploma thesis. It is not evident because the static analysis is used to create extra code
that will be used by the specified scheduler to parallelize a program execution.

Several steps have to be done by the analyzer to create this \textit{guide code} for the scheduler. These steps
are described in the following sections, and there are possible only because the semantics of the programming
language was carefully chosen, as was shown in the previous thesis parts.

The algorithms described in the following sections are based on ideas often used in \textit{formal verification}
techniques \cite{verification} as well as in \textit{compiler optimization} methods \cite{compilerConstruction}.
The algorithms' creation was mainly influenced by the following techniques:
\begin{enumerate}
  \item \textit{Symbolic execution} which is often used in formal verification \cite{symbolicExecution}.
  \item \textit{Shape analysis} which is used primarily in formal verification \cite{shapeAnalysis}.
  \item \textit{Abstract interpretation} which is used in formal verification and compiler optimization \cite{abstraction}.
\end{enumerate}

\subsection*{\textbf{Detection of recursive functions}}

Recursive functions are essential for many algorithms. However, a static analysis of such functions is,
in general case, impossible. To avoid executing analyzer on recursive functions, it is needed to detect
whether the function is recursive or not.

This detection can be done by a \textit{cycle detection} algorithm \cite{graphTheory} in the directed graph
that is created according to the following description:
\begin{enumerate}
  \item Add a vertex for each declared function.

  \item Create a directed edge from the vertex of the function \textbf{f} to the vertex of the function \textbf{g}
  for each \textit{function call assignment} of the function \textbf{g} in the function \textbf{f}.
\end{enumerate}
Any declared function is recursive only if there exists a cycle starting in the function's vertex.

This static analysis is possible only because all function calls are semantically restricted to be static,
i.e., no jumps to the computed program addresses are possible, as it is possible in the low-level assembler
languages.

When dealing with the complexity of this algorithm, let the \( n \) to denote the count of declared
functions in the program. If so, the created graph will have exactly \( n \) vertices and at most
\( n^2 \) edges. The simple \textit{depth-first search} algorithm, with the time complexity \( O(|V| + |E|) \),
can perform the cycle detection. Therefore, the worst-case time and space complexity of this static
analysis is \( O(n^2) \) \cite{complexity}.

\subsection*{\textbf{Creating list of read and written global fields}}

Each declared function (recursive or not) can potentially read or alter some global variables. Static
analysis of the source code can create a list of these variables for each function.

The whole list of the variables can be obtained using \textit{breath-first search} or
\textit{depth-first search} algorithm \cite{graphTheory} in the directed graph that has three
different types of vertices and is created by the following process:
\begin{enumerate}
  \item Add a \textit{function vertex} for each declared function.

  \item Add a \textit{global read vertex} for each field name, starting with the \textit{global.} string,
  that appears in the source code as a condition argument or as a function argument.

  \item Add a \textit{global write vertex} for each field name, starting with the \textit{global.} string,
  that appears in the source code in the left side of an assignment statement.

  \item Create directed edge from the \textit{function vertex} of the function \textbf{f} to the
  \textit{function vertex} of the function \textbf{g} for each \textit{function call assignment}
  of the function \textbf{g} in the function \textbf{f}.

  \item Create directed edge from the \textit{function vertex} of the function \textbf{f} to the
  \textit{global read vertex} of the global variable \textbf{v} if the variable \textbf{v} is used
  as a \textit{condition argument} or as a \textit{function call argument} in the source code of the
  function \textbf{f}.

  \item Create directed edge from the \textit{function vertex} of the function \textbf{f} to the
  \textit{global write vertex} of the global variable \textbf{v} if a variable \textbf{v} is used
  as a \textit{left-side} of any assignment in the source code of the function \textbf{f}.
\end{enumerate}
List of read global fields for any declared function \textbf{f} contains fields whose \textit{global read vertex}
is reachable from the \textit{function vertex} of the \textbf{f}.
List of write global fields for any declared function \textbf{f} contains fields whose \textit{global write vertex}
is reachable from the \textit{function vertex} of the \textbf{f}.

This static analysis would be impossible to perform if the semantics of the assignment statements
would define assignment by reference. However, all assignment statements, as well as function call
arguments passing, perform copying of the values. Therefore, all global fields assignments are static.

For the complexity analysis of this algorithm, let the \( n \) to denote the number of statements
in the program plus the number of declared functions in the program. Therefore, number of vertices
in the created graph can be bounded by the O(n), and number of edges by the \( O(n^2) \). The simple
\textit{depth-first search} algorithm, with the time complexity \( O(|V| + |E|) \), can test reachability
in the graph. Consequently, the final worst-case time complexity of the algorithm is \( O(m \cdot n^2) \)
where the \( m \) denotes the number of declared functions. The worst-case space complexity is \( O(n^2) \) \cite{complexity}.

\subsection*{\textbf{Creating boolean expression for each global variable read and write}}

Each global variable read and write can be located in the branch of zero or more conditions. These branches
can also be nested in each other. For the scheduler, it is necessary to extract all possible conditions that
lead to reading or writing of any given global variable.

The boolean expressions represent such conditions. However, they might be undetermined if they depend on the
global variable itself, and not only on the incoming message. Such dependency is undesirable because using
global variables during scheduling can lead to an inconsistent state of the system. Therefore, these
undetermined expressions have to conclude in the global variable being treated as always read or written.

All conditions in the proposed programming language consist of the testing particular variable which has to
be of the \textit{boolean type}. Value of such variable is created by a sequence of \textit{assignment statements}.
This sequence can be easily translated into the expression which has a tree structure. Expression trees of each
variable can be created by the following recursive process performed on the code of the program:
\begin{enumerate}
  \item On a \textit{constant assignment statement} (see figure~\ref{fig:assign_constant}) change the current expression for
  the target variable to the specific constant.

  \item On a \textit{copy assignment statement} (see figure~\ref{fig:assign_copy}) change the current expression for the
  target variable to the current expression of the source variable if it exists, or to the source variable
  read expression if source variable has no current expression.

  \item On a \textit{call assignment statement} (see figure~\ref{fig:assign_call}) action depends on the
  type of the function that is being called:
  \begin{enumerate}
    \item If it is a \textit{built-in function} change the current expression for the target variable
    to the \textit{function-call expression}, also replacing function's arguments with the corresponding
    expressions.

    \item If it is a \textit{non-recursive function} recursively run this process and change the current expression
    for the target variable to the expression returned by the function being called.

    \item If it is a \textit{recursive function} which \textbf{does not} read or write any global variable change
    the current expression for the target variable to the \textit{function-call expression}, also replacing
    function's arguments with the corresponding expressions.

    \item If it is a \textit{recursive function} which \textbf{does} read or write some global variables change
    the current expression for the target variable to the special \textit{undetermined expression}.
  \end{enumerate}

  \item On a \textit{condition statement} (see figure~\ref{fig:condition}) the process has to be split
  to determine expressions for \textit{then} and \textit{else} branch independently. Then, to merge the
  split, each changed expression is replaced by the special \textit{if expression} which consists of the
  three expressions:
  \begin{enumerate}
    \item \textit{The condition expression} - expression of the variable that was in the former condition.
    \item \textit{The 'then' expression} - expression that belongs to the variable in the \textit{then} branch.
    \item \textit{The 'else' expression} - expression that belongs to the variable in the \textit{else} branch.
  \end{enumerate}

  \item On a \textit{return statement} (see figure~\ref{fig:return}) set the current expression for the
  current function's return to the current expression of the returned variable or to the constant
  expression of the returned constant. However, return statement is special because it can alter
  execution flow of the program. Therefore, return expression has to be guarded by the condition
  expression of the return's location in the code. Also, if function has multiple return statements
  these have to be merged by another condition expression.
\end{enumerate}

This process creates trees that have leaves with \textit{constants}, with \textit{variables reads}, or
with \textit{undetermined expressions}. If leaf contains the \textit{global variable read} or the
\textit{undetermined expression}, whole expression tree has to be considered as \textit{undetermined} -
such expressions are considered to be always \textit{true} by the scheduler.

When there exists the expression for each defined variable at each point in the code, it
is easy to determine when are specific global variables read or written. It can be done
by traversing the graph that is created by the following procedure. The procedure is performed
on the code which is obtained by \textit{inlining} each \textit{non-recursive} \textit{side-effect}
function call:
\begin{enumerate}
  \item Add a \textit{root vertex} which holds an \textit{always true} expression.

  \item Add a \textit{condition vertex} for each condition that appears in the \textit{inlined program code}.
  This vertex contains the expression determine by the previously described process.

  \item Add a \textit{global read vertex} for each global variable that is read by any of the statements.

  \item Add a \textit{global write vertex} for each global variable that is assigned by any of the assignment statements.

  \item Create a \textit{then directed edge} and a \textit{else directed edge} from each \textbf{top-level}
  \textit{condition vertex} into the \textit{root vertex}.

  \item Create a \textit{then directed edge} from each \textbf{not-top-level} \textit{condition vertex} \textbf{v} into the
  \textit{condition vertex} of the condition which contains the condition \textbf{v} in its \textit{then branch}.

  \item Create an \textit{else directed edge} from each \textbf{not-top-level} \textit{condition vertex} \textbf{v} into the
  \textit{condition vertex} of the condition which contains the condition \textbf{v} in its \textit{else branch}.

  \item Create a \textit{then directed edge} from each \textit{global read or write vertex} \textbf{v}
  into the \textit{condition vertex} of the condition which contains operation of the \textbf{v} directly in its \textit{then branch}.

  \item Create an \textit{else directed edge} from each \textit{global read or write vertex} \textbf{v}
  into the \textit{condition vertex} of the condition which contains operation of the \textbf{v} directly in its \textit{else branch}.
\end{enumerate}
The boolean expression for any given \textit{read or write vertex} \textbf{v} can be obtained
by finding the path from the \textbf{v} to the \textit{root vertex}. The final boolean expression
has to satisfy each condition expression or its negation, depending on the type of the incoming edge of the
condition vertex:
\begin{enumerate}
  \item Incoming edge is \textit{then edge} - the condition expression has to be satisfied.
  \item Incoming edge is \textit{else edge} - negation of the condition expression has to be satisfied.
\end{enumerate}

With this process multiple boolean expressions are created for each \textit{global variable read}
and multiple boolean expressions are created for each \textit{global variable write}.
If all these boolean expressions evaluate to \textit{false} it is guaranteed that message
processing will not read or write given variable. This means that all global variables are
implicitly locked by the scheduler, there are unlocked only if all their boolean expressions
evaluate to \textit{false}.

To analyze the complexity of the algorithm, let the \( n \) to denote the number of statements in the program.
Therefore, the number of vertices of the graph is bounded by the \( O(n) \), and number of edges by the \( O(n^2) \).
Finding the path between two vertices can be performed by the simple \textit{depth-first search} algorithm.
Hence, the total time complexity of the algorithm is \( O(m \cdot n^2) \) where the \( m \) denotes the number
of global variables identified in the program code. The worst-case space complexity is \( O(n^2) \) \cite{complexity}.

\section{Compiling from a high-level OOP programming language}

The programming language presented in this diploma thesis is low-level, and does not contain many features
that are expected in user-friendly languages. This is intentional because it was designed to make the
implementation of the interpreter and static analyzer as simple as possible. However, this approach made the usage
of the language very impractical for the programmer. Although, it is still usable as a target of a compilation
from another, more high-level language.

It is even possible to create a compiler for an object-oriented programming language (OOP). There is, however,
one limitation that has to be overcome to allow polymorphism feature found in the OOP languages \cite{oop}. This limitation
is the lack of dynamic jumps. Polymorphism is often implemented by some virtual function table which holds in-memory
addresses of the functions. These addresses are used by the function call to execute right instructions based on
the polymorphic object type \cite{polymorphism}.

In general case, programs consist of several separately compiled modules. This separation of compilation makes it
impossible to overcome the mentioned limitation. However, if whole program code is compiled together, these polymorphic
calls can be transformed into the conditions which statically check the type of the object and make a static function call
\cite{polymorphism}.
