At times, the reduction requires the evaluation of expressions, using the interpreter.
During every rewrite step, a task value is produced.
On the device, the \gls{RTS} may have multiple tasks at the same time active.
-By interleavig the rewrite steps, parallel operation is achieved.
+By interleaving the rewrite steps, parallel operation is achieved.
The design, architecture and implementation of the \gls{RTS} is shown in \cref{sec:compiler_rts}.
\begin{figure}
After compilation, several post-processing steps are applied to make the code suitable for the microprocessor.
First, in all tail call \cleaninline{BCReturn} instructions are replaced by \cleaninline{BCTailCall} instructions to optimise the tail calls.
Furthermore, all byte code is concatenated, resulting in one big program.
-Many instructions have commonly used arguments so shorthands are introduced to reduce the program size.
+Many instructions have commonly used arguments, so shorthands are introduced to reduce the program size.
For example, the \cleaninline{BCArg} instruction is often called with argument \numrange{0}{2} and can be replaced by the \numrange[parse-numbers=false]{\cleaninline{BCArg0}}{\cleaninline{BCArg2}} shorthands.
Furthermore, redundant instructions such as pop directly after push are removed as well in order not to burden the code generation with these intricacies.
-Finally the labels are resolved to represent actual program addresses instead of the freshly generated identifiers.
+Finally, the labels are resolved to represent actual program addresses instead of the freshly generated identifiers.
After the byte code is ready, the lowered \glspl{SDS} are resolved to provide an initial value for them.
-The byte code, \gls{SDS} specification and perpipheral specifications are the result of the process, ready to be sent to the device.
+The byte code, \gls{SDS} specification and peripheral specifications are the result of the process, ready to be sent to the device.
\subsection{Instruction set}
The instruction set is a fairly standard stack machine instruction set extended with special \gls{TOP} instructions for creating task tree nodes.
Translating $\mathcal{E}$ to \gls{CLEAN} code is very straightforward, it basically means writing the instructions to the writer monad.
Almost always, the type of the interpretation is not used, i.e.\ it is a phantom type.
To still have the functions return the correct type, the \cleaninline{tell`}\footnote{\cleaninline{tell` :: [BCInstr] -> BCInterpret a}} helper is used.
-This function is similar to the writer monad's \cleaninline{tell} function but is casted to the correct type.
+This function is similar to the writer monad's \cleaninline{tell} function but is cast to the correct type.
\Cref{lst:imp_arith} shows the implementation for the arithmetic and conditional expressions.
Note that $r$, the context, is not an explicit argument here but stored in the state.
\end{align*}
A function call starts by pushing the stack and frame pointer, and making space for the program counter (\cref{lst:funcall_pushptrs}) followed by evaluating the arguments in reverse order (\cref{lst:funcall_args}).
-On executing \cleaninline{BCJumpSR}, the program counter is set and the interpreter jumps to the function (\cref{lst:funcall_jumpsr}).
+On executing \cleaninline{BCJumpSR}, the program counter is set, and the interpreter jumps to the function (\cref{lst:funcall_jumpsr}).
When the function returns, the return value overwrites the old pointers and the arguments.
This occurs right after a \cleaninline{BCReturn} (\cref{lst:funcall_ret}).
-Putting the arguments on top of pointers and not reserving space for the return value uses little space and facilitates tail call optimization.
+Putting the arguments on top of pointers and not reserving space for the return value uses little space and facilitates tail call optimisation.
\begin{figure}
\begin{subfigure}{.24\linewidth}
\end{figure}
Calling a function and referencing function arguments are an extension to $\mathcal{E}$ as shown below.
-Arguments may be at different places on the stack at different times (see \cref{ssec:step}) and therefore the exact location always is be determined from the context using \cleaninline{findarg}\footnote{\cleaninline{findarg [l`:r] l = if (l == l`) 0 (1 + findarg r l)}}.
+Arguments may be at different places on the stack at different times (see \cref{ssec:step}) and therefore the exact location is always is determined from the context using \cleaninline{findarg}\footnote{\cleaninline{findarg [l`:r] l = if (l == l`) 0 (1 + findarg r l)}}.
Compiling argument $a_{f^i}$, the $i$th argument in function $f$, consists of traversing all positions in the current context.
Arguments wider than one stack cell are fetched in reverse to reconstruct the original order.
Furthermore, it is a lazy node in the task tree: the right-hand side may yield a new task tree after several rewrite steps, i.e.\ it is allowed to create infinite task trees using step combinators.
The function is generated using the $\mathcal{S}$ scheme that requires two arguments: the context $r$ and the width of the left-hand side so that it can determine the position of the stability which is added as an argument to the function.
The resulting function is basically a list of if-then-else constructions to check all predicates one by one.
-Some optimization is possible here but has currently not been implemented.
+Some optimisation is possible here but has currently not been implemented.
\begin{align*}
\cschemeE{t_1\text{\cleaninline{>>*.}}t_2}{r} & =
First the context is evaluated.
The context contains arguments from functions and steps that need to be preserved after rewriting.
The evaluated context is combined with the left-hand side task value by means of a \cleaninline{.&&.} combinator to store it in the task tree so that it is available after a rewrite.
-This means that the task tree is be transformed as seen in \cref{lst:context_tree}.
+This means that the task tree is transformed as seen in \cref{lst:context_tree}.
\begin{figure}
\begin{subfigure}{.5\textwidth}
While there is no code generated in the definition, the byte code compiler is storing all \gls{SDS} data in the \cleaninline{bcs_sdses} field in the compilation state.
Regular \glspl{SDS} are stored as \cleaninline{Right String255} values.
-The \glspl{SDS} are typed as functions in the host language so an argument for this function must be created that represents the \gls{SDS} on evaluation.
+The \glspl{SDS} are typed as functions in the host language, so an argument for this function must be created that represents the \gls{SDS} on evaluation.
For this, an \cleaninline{BCInterpret} is created that emits this identifier.
When passing it to the function, the initial value of the \gls{SDS} is returned.
In the case of a local \gls{SDS}, this initial value is stored as a byte code encoded value in the state and the compiler continues with the rest of the program.
Then, using \cleaninline{addSdsIfNotExist}, the identifier for this particular \gls{SDS} is either retrieved from the compiler state or generated freshly.
This identifier is then used to provide a reference to the \cleaninline{def} definition to evaluate the main expression.
Compiling \cleaninline{getSds} is a matter of executing the \cleaninline{BCInterpret} representing the \gls{SDS}, which yields the identifier that can be embedded in the instruction.
-Setting the \gls{SDS} is similar: the identifier is retrieved and the value is written to put in a task tree so that the resulting task can remember the value it has written.
+Setting the \gls{SDS} is similar: the identifier is retrieved, and the value is written to put in a task tree so that the resulting task can remember the value it has written.
% VimTeX: SynIgnore on
-\begin{lstClean}[caption={Backend implementation for the SDS classes.},label={lst:comp_sds}]
+\begin{lstClean}[caption={Backend implementation for the \gls{SDS} classes.},label={lst:comp_sds}]
:: Sds a = Sds Int
instance sds BCInterpret where
sds def = {main =
The exact communication method is a customisable device-specific option baked into the \gls{RTS}.
The interface is kept deliberately simple and consists of two layers: a link interface and a communication interface.
Besides opening, closing and cleaning up, the link interface has three functions that are shown in \cref{lst:link_interface}.
-Consequently, implementing this link interface is very simple but it is still possible to implement more advanced link features such as buffering.
+Consequently, implementing this link interface is very simple, but it is still possible to implement more advanced link features such as buffering.
There are implementations for this interface for serial or \gls{WIFI} connections using \gls{ARDUINO}, and \gls{TCP} connections for Linux.
\begin{lstArduino}[caption={Link interface of the \gls{MTASK} \gls{RTS}.},label={lst:link_interface}]
\begin{description}
\item[SpecRequest]
- is a message instructing the device to send its specification and it is received immediately after connecting.
+ is a message instructing the device to send its specification.
+ It is received immediately after connecting.
The \gls{RTS} responds with a \texttt{Spec} answer containing the specification.
\item[TaskPrep]
tells the device a task is on its way.
Especially on faster connections, it may be the case that the communication buffers overflow because a big message is sent while the \gls{RTS} is busy executing tasks.
This message allows the \gls{RTS} to postpone execution for a while, until the larger task has been received.
- The server sends the task only after the device acknowledged the preparation by by sending a \texttt{TaskPrepAck} message.
+ The server sends the task only after the device acknowledged the preparation by sending a \texttt{TaskPrepAck} message.
\item[Task]
contains a new task, its peripheral configuration, the \glspl{SDS}, and the byte code.
The new task is immediately copied to the task storage but is only initialised during the next phase.
Stable tasks, and unreachable task tree nodes are removed.
If a task is to be removed, tasks with higher memory addresses are moved down.
-For task trees---stored in the heap---the \gls{RTS} already marks tasks and task trees as trash during rewriting so the heap can be compacted in a single pass.
-This is possible because there is no sharing or cycles in task trees and nodes contain pointers pointers to their parent.
+For task trees---stored in the heap---the \gls{RTS} already marks tasks and task trees as trash during rewriting, so the heap can be compacted in a single pass.
+This is possible because there is no sharing or cycles in task trees and nodes contain pointers to their parent.
\section{C code generation}\label{sec:ccodegen}
From the structural representation of the type, a \gls{CLEAN} parser and printer is constructed using generic programming.
Furthermore, a \ccpp{} parser and printer is generated for use on the \gls{MTASK} device.
The technique for generating the \ccpp{} parser and printer is very similar to template metaprogramming and requires a rich generic programming library or compiler support that includes a lot of metadata in the record and constructor nodes.
-Using generic programming in the \gls{MTASK} system, both serialisation and deserialisation on the microcontroller and and the server is automatically generated.
+Using generic programming in the \gls{MTASK} system, both serialisation and deserialisation on the microcontroller and the server is automatically generated.
\subsection{Server}
On the server, off-the-shelve generic programming techniques are used to make the serialisation and deserialisation functions (see \cref{lst:ser_deser_server}).
Serialisation is a simple conversion from a value of the type to a string.
-Deserialisation is a little bit different in order to support streaming\footnotemark.
+Deserialisation is a bit different in order to support streaming\footnotemark.
\footnotetext{%
Here the \cleaninline{*!} variant of the generic interface is chosen that has less uniqueness constraints for the compiler-generated adaptors \citep{alimarine_generic_2005,hinze_derivable_2001}.%
}
The \gls{RTS} first evaluates the main expression in the interpreter.
The result of this evaluation, a run time representation of the task, is a task tree.
This task tree is rewritten according to small-step reduction rules until a stable value is observed.
-Rewriting multiple tasks at the same time is achieved by interleaving the rewrite steps, resulting in seamingly parallel execution of the tasks.
+Rewriting multiple tasks at the same time is achieved by interleaving the rewrite steps, resulting in seemingly parallel execution of the tasks.
All communication, including the serialisation and deserialisation, between the server and the \gls{RTS} is automated.
From the structural representation of the types, printers and parsers are generated for the server and the client.
repositories / phd-thesis.git / blobdiff