\end{figure}
\section{Compiler}\label{sec:compiler_imp}
-The byte code compiler for \gls{MTASK} is designed to generate code that runs on resource-constrained edge devices.
-There is no heap avaliable for expressions, only for tasks
-\todo[inline]{Zou je hier niet een prargraafje schrijven over dat dit een beetje speciale compiler is. Alle type checks worden al door Clean gedaan. Dat is voordat deze compiler ooit uitgevoerd gaat worden. Bovendien kan het Clean programma de te compileren byte code dynamisch maken. Dat staat natuurlijk al eerder een keer, maar je make niet aannemen dat iedereen alles leest (en nu nog weet)}
-\todo[inline]{Dit gaat wel hard de diepte in. Zou je niet een kort stukje schrijven over hoe je bytecode machine er uit ziet?
- Heap: voor de huidige task tree die herschreven wordt.
- Function code: sequence of bytecode instructie.
- SDSs + Objects
- Stack om expressies te evelaueren en function calls te doen.
- Plaatje a la Figure 7.5.
-
- Om de code te maken heb je een intsantie van alle classen in mTask nodig voor BCInterpret a.
-
-Voor veel lezers zou het genoeg zijn om alleen dat te snappen, maak het ze eenvoudig.}
+The byte code compiler for \gls{MTASK} is an interpretation of the \gls{MTASK} language.
+In order to compile terms, instances for all \gls{MTASK} type classes are required for the \cleaninline{:: BCInterpret a} type.
+Terms in \gls{MTASK} are constructed and compiled at run time, but type checked at compile time in the host language \gls{CLEAN}.
+The compiled tasks are sent to the device for interpretation.
+The result of the compilation is the byte code and some metadata regarding the used peripherals and \glspl{SDS}.
+The compilation target is the interpreter of the \gls{MTASK} \gls{RTS}.
+In order to keep the hardware requirements down, all expressions are evaluated on a stack.
+Rewriting of tasks uses the same stack and also a heap.
+The heap usage is minimised by applying aggressive memory management.
+A detailed overview of the \gls{RTS} including the interpreter and rewriter is found in \cref{sec:compiler_rts}.
+
\subsection{Compiler infrastructure}
The byte code compiler interpretation for the \gls{MTASK} language is implemented as a monad stack containing a writer monad and a state monad.
The writer monad is used to generate code snippets locally without having to store them in the monadic values.
\begin{table}
\centering
- \caption{An overview of the compilation schemes.}
+ \caption{An overview of the compilation rules.}
\begin{tabularx}{\linewidth}{l X}
\toprule
Scheme & Description\\
\midrule
- $\cschemeE{e}{r}$ & Produces the value of expression $e$ given the context $r$ and pushes it on the stack.
- The result can be a basic value or a pointer to a task.\\
- $\cschemeF{e}$ & Generates the bytecode for functions.\\
- $\cschemeS{e}{r}{w} $ & Generates the function for the step continuation given the context $r$ and the width $w$ of the left-hand side task value.\\
+ $\cschemeE{e}{r}$ & Generates code for expressions given the context $r$\\
+ $\cschemeF{e}$ & Generates the code for functions.\\
+ $\cschemeS{e}{r}{w} $ & Generates the code for the step continuations given the context $r$ and the width $w$ of the left-hand side task value.\\
\bottomrule
\end{tabularx}
\end{table}
Values are always placed on the stack; tuples and other compound data types are unpacked.
Function calls, function arguments and tasks are also compiled using $\mathcal{E}$ but their compilations is explained later.
+\begingroup
+\allowdisplaybreaks%
\begin{align*}
\cschemeE{\text{\cleaninline{lit}}~e}{r} & = \text{\cleaninline{BCPush (bytecode e)}};\\
\cschemeE{e_1\mathbin{\text{\cleaninline{+.}}}e_2}{r} & = \cschemeE{e_1}{r};
{} & \text{\emph{Where $w_l$ is the width of the left and, $w_r$ of the right value}}\\
{} & \text{\emph{similar for other unboxed compound data types}}\\
\end{align*}
+\endgroup
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.
It pops arguments from the stack according to the given task type.
The following extension of $\mathcal{E}$ shows this compilation scheme (except for the step combinator, explained in \cref{ssec:step}).
+\begingroup
+\allowdisplaybreaks%
\begin{align*}
\cschemeE{\text{\cleaninline{rtrn}}~e}{r} & =
\cschemeE{e}{r};
\cschemeE{e_2}{r};
\text{\cleaninline{BCMkTask BCAnd}};\\
\end{align*}
+\endgroup%
-This translates to Clean code by writing the correct \cleaninline{BCMkTask} instruction as exemplified in \cref{lst:imp_ret}.
+This compilation scheme translates to Clean code by first writing the arguments and then the correct \cleaninline{BCMkTask} instruction.
+This is shown for the \cleaninline{.&&.} task in \cref{lst:imp_ret}.
\begin{lstClean}[caption={The byte code interpretation implementation for \cleaninline{rtrn}.},label={lst:imp_ret}]
-instance rtrn BCInterpret
-where
- rtrn m = m >>| tell` [BCMkTask (bcstable m)]
+instance .&&. BCInterpret where
+ (.&&.) l r = l >>| r >>| tell` [BCMkTask BCTAnd]
\end{lstClean}
\subsection{Sequential combinator}\label{ssec:step}
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 step.
This means that the task tree is transformed as seen in \cref{lst:context_tree}.
-In this figure, the expression \cleaninline{t1 >>=. \v1->t2 >>=. \v2->...} is shown\footnote{%
- \cleaninline{t >>=. e} is a shorthand combinator for \cleaninline{t >>* [OnStable (\_->true) e].}}.
+In this figure, the expression \cleaninline{t1 >>=. \\v1->t2 >>=. \\v2->...} is shown\footnote{%
+ \cleaninline{t >>=. e} is a shorthand combinator for \cleaninline{t >>* [OnStable (\\_->true) e].}}.
Then, the right-hand side list of continuations is converted to an expression using $\mathcal{S}$.
\begin{figure}
//Return width (always 1, a task pointer)
(Just one)
>>| modify (\s->{s & bcs_context=ctx})
- >>| tell` [BCMkTask (instr rhswidth funlab)]
-
+ >>| tell` [BCMkTask (instr rhswidth funlab)][+\pagebreak+]
toContFun :: JumpLabel UInt8 -> BCInterpret a
toContFun steplabel contextwidth
= foldr tcf (tell` [BCPush fail]) cont
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.
-
-\begin{align*}
- \cschemeF{\text{\cleaninline{sds}}~x=i~\text{\cleaninline{In}}~m} & =
- \cschemeF{m};\\
-\end{align*}
-
The \gls{SDS} access tasks have a compilation scheme similar to other tasks (see \cref{ssec:scheme_tasks}).
The \cleaninline{getSds} task just pushes a task tree node with the \gls{SDS} identifier embedded.
The \cleaninline{setSds} task evaluates the value, lifts that value to a task tree node and creates \pgls{SDS} set node.
\begin{align*}
+ \cschemeF{\text{\cleaninline{sds}}~x=i~\text{\cleaninline{In}}~m} & =
+ \cschemeF{m};\\
+ \\
\cschemeE{\text{\cleaninline{getSds}}~s}{r} & =
- \text{\cleaninline{BCMkTask}} (\text{\cleaninline{BCSdsGet}} s);\\
+ \text{\cleaninline{BCMkTask}}~(\text{\cleaninline{BCSdsGet}}~s);\\
\cschemeE{\text{\cleaninline{setSds}}~s~e}{r} & =
\cschemeE{e}{r};
\text{\cleaninline{BCMkTask BCStable}}_{\stacksize{e}};\\
- {} & \mathbin{\phantom{=}} \text{\cleaninline{BCMkTask}} (\text{\cleaninline{BCSdsSet}} s);\\
+ {} & \mathbin{\phantom{=}} \text{\cleaninline{BCMkTask}}~(\text{\cleaninline{BCSdsSet}}~s);\\
\end{align*}
\Cref{lst:comp_sds} shows the implementation of the \cleaninline{sds} type class.
This is done so that the \cleaninline{withDevice} task can write the received \gls{SDS} updates to the according \gls{SDS} while the \gls{SDS} is not in scope.
The \gls{ITASK} notification mechanism then takes care of the rest.
Such \pgls{SDS} is created by using the \cleaninline{mapReadWriteError} which, given a pair of read and write functions with error handling, produces \pgls{SDS} with the lens embedded.
-The read function transforms converts the typed value to a typeless serialised value.
+The read function transforms the typed value to a typeless serialised value.
The write function will, given a new serialised value and the old typed value, produce a new typed value.
-It tries to decode the serialised value, if that succeeds, it is written to the underlying \gls{SDS}, an error is thrown otherwise.
+It tries to decode the serialised value, if that succeeds, it is written to the underlying \gls{SDS}, otherwise, an error is thrown otherwise.
\Cref{lst:mtask_itasksds_lens} shows the implementation for this.
% VimTeX: SynIgnore on
The \gls{OS} is written in portable \ccpp{} and only contains a small device-specific portion.
In order to keep the abstraction level high and the hardware requirements low, much of the high-level functionality of the \gls{MTASK} language is implemented not in terms of lower-level constructs from \gls{MTASK} language but in terms of \ccpp{} code.
-Most microcontrollers software consists of a cyclic executive instead of an \gls{OS}, this one loop function is continuously executed and all work is performed there.
+Most microcontroller software consists of a cyclic executive instead of an \gls{OS}.
+This one loop function is continuously executed and all work is performed there.
In the \gls{RTS} of the \gls{MTASK} system, there is also such an event loop function.
It is a function with a relatively short execution time that gets called repeatedly.
The event loop consists of three distinct phases.
\subsection{Execution phase}
The second phase performs one execution step for all tasks that wish for it.
-Tasks are ordered in a priority queue ordered by the time a task needs to execute, the \gls{RTS} selects all tasks that can be scheduled, see \cref{sec:scheduling} for more details.
+Tasks are placed in a priority queue orderd by the time a task needs to execute.
+The \gls{RTS} selects all tasks that can be scheduled, see \cref{sec:scheduling} for more details.
Execution of a task is always an interplay between the interpreter and the rewriter.
The rewriter scans the current task tree and tries to rewrite it using small-step reduction.
Expressions in the tree are always strictly evaluated by the interpreter.
When a new task is received, the main expression is evaluated to produce a task tree.
A task tree is a tree structure in which each node represents a task combinator and the leaves are basic tasks.
If a task is not initialised yet, i.e.\ the pointer to the current task tree is still null, the byte code of the main function is interpreted.
-The main expression of \gls{MTASK} programs sent to the device fore execution always produces a task tree.
+The main expression of \gls{MTASK} programs sent to the device before execution always produces a task tree.
Execution of a task consists of continuously rewriting the task until its value is stable.
Rewriting is a destructive process, i.e.\ the rewriting is done in place.
Rewriting always starts at the top of the tree and traverses to the leaves, the basic tasks that do the actual work.
The first basic task encountered is the \cleaninline{delay} task, that yields no value until the time, \qty{500}{\ms} in this case, has passed.
When the \cleaninline{delay} task yielded a stable value after a number of rewrites, the task continues with the right-hand side of the \cleaninline{>>\|.} combinator by evaluating the expression (see \cref{fig:blink_tree2})\footnotemark.
-\footnotetext{\cleaninline{t1 >>\|. t2} is a shorthand for \cleaninline{t1 >>*. [IfStable id \_->t2]}.}
+\footnotetext{\cleaninline{t1 >>\|. t2} is a shorthand for \cleaninline{t1 >>*. [IfStable id \\_->t2]}.}
This combinator has a \cleaninline{writeD} task at the left-hand side that becomes stable after one rewrite step in which it writes the value to the given pin.
When \cleaninline{writeD} becomes stable, the written value is the task value that is observed by the right-hand side of the \cleaninline{>>=.} combinator.
-This will call the interpreter to evaluate the expression, now that the argument of the function is known.
+Then the interpreter is used again to evaluate the expression, now that the argument of the function is known.
The result of the call to the function is again a task tree, but now with different arguments to the tasks, e.g.\ the state in \cleaninline{writeD} is inversed.
\begin{figure}
\caption{Task tree after the delay passed}%
\label{fig:blink_tree2}
\end{subfigure}
- \caption{The task trees for a blink task in \cref{lst:blink_code} in \gls{MTASK}.}%
+ \caption{The task trees during reduction for a blink task in \gls{MTASK}.}%
\label{fig:blink_tree}
\end{figure}
\subsection{Client}
The \gls{RTS} of the \gls{MTASK} system runs on resource-constrained microcontrollers and is implemented in portable \ccpp{}.
In order to achieve more interoperation safety, the communication between the server and the client is automated, i.e.\ the serialisation and deserialisation code in the \gls{RTS} is generated.
-\todo[inline]{Dit naar voren halen naar 7.4.0?}
The technique used for this is very similar to the technique shown in \cref{chp:first-class_datatypes}.
However, instead of using template metaprogramming, a feature \gls{CLEAN} lacks, generic programming is used also as a two-stage rocket.
In contrast to many other generic programming systems, \gls{CLEAN} allows for access to much of the metadata of the compiler.
repositories / phd-thesis.git / blobdiff