\begin{document}
\input{subfileprefix}
-
\chapter{Implementation}%
\label{chp:implementation}
\begin{chapterabstract}
It is threefold: first it shows the implementation of the byte code compiler for \gls{MTASK}'s \gls{TOP} language, then is details of the implementation of \gls{MTASK}'s \gls{TOP} engine that executes the \gls{MTASK} tasks on the microcontroller, and finally it shows how the integration of \gls{MTASK} tasks and \glspl{SDS} is implemented both on the server and on the device.
\end{chapterabstract}
-\section{Byte code compiler}
-IFL19 paper, bytecode instructieset~\cref{chp:bytecode_instruction_set}
+Microcontrollers usually have flash-based program memory which wears out fairly quick.
+For example, the atmega328p in the \gls{ARDUINO} UNO is rated for 10000 write cycles.
+While this sounds like a lot, if new tasks are sent to the device every minute or so, a lifetime of not even seven days is guaranteed.
+Hence, for dynamic applications, generating code at run-time for interpretation on the device is necessary.
+This byte code is then interpreted on MCUs with very little memory and processing power and thus save precious write cycles of the program memory.
+precious write cycles of the program memory.
+
+In order to provide the device with the tools to interpret the byte code, it is programmed with a \gls{RTS}, a customisable domain-specific \gls{OS} that takes care of the execution of tasks but also low-level mechanisms such as the communication, multi tasking, and memory management.
+Once the device is programmed with the \gls{MTASK} \gls{RTS}, it can continuously receive new tasks.
+
+\subsection{Instruction set}
+The instruction set is a fairly standard stack machine instruction set extended with special \gls{TOP} instructions.
+\Cref{lst:instruction_type} shows the \gls{CLEAN} type representing the instruction set of which \cref{tbl:instr_task} gives detailed semantics.
+Type synonyms are used to provide insight on the arguments of the instructions.
+One notable instruction is the \cleaninline{MkTask} instruction, it allocates and initialises a task tree node and pushes a pointer to it on the stack.
+
+\begin{lstClean}[caption={The type housing the instruction set.},label={lst:instruction_type}]
+:: ArgWidth :== UInt8 :: ReturnWidth :== UInt8
+:: Depth :== UInt8 :: Num :== UInt8
+:: SdsId :== UInt8 :: JumpLabel =: JL UInt16
+
+//** Datatype housing all instructions
+:: BCInstr
+ //Return instructions
+ //Jumps
+ = BCJumpF JumpLabel | BCJump JumpLabel | BCLabel JumpLabel | BCJumpSR ArgWidth JumpLabel
+ | BCReturn ReturnWidth ArgWidth | BCTailcall ArgWidth ArgWidth JumpLabel
+ //Arguments
+ | BCArgs ArgWidth ArgWidth
+ //Task node creation and refinement
+ | BCMkTask BCTaskType | BCTuneRateMs | BCTuneRateSec
+ //Task value ops
+ | BCIsStable | BCIsUnstable | BCIsNoValue | BCIsValue
+ //Stack ops
+ | BCPush String255 | BCPop Num | BCRot Depth Num | BCDup | BCPushPtrs
+ //Casting
+ | BCItoR | BCItoL | BCRtoI | ...
+ // arith
+ | BCAddI | BCSubI | ...
+ ...
+
+//** Datatype housing all task types
+:: BCTaskType
+ = BCStableNode ArgWidth | ArgWidth
+ // Pin io
+ | BCReadD | BCWriteD | BCReadA | BCWriteA | BCPinMode
+ // Interrupts
+ | BCInterrupt
+ // Repeat
+ | BCRepeat
+ // Delay
+ | BCDelay | BCDelayUntil //* Only for internal use
+ // Parallel
+ | BCTAnd | BCTOr
+ //Step
+ | BCStep ArgWidth JumpLabel
+ //Sds ops
+ | BCSdsGet SdsId | BCSdsSet SdsId | BCSdsUpd SdsId JumpLabel
+ // Rate limiter
+ | BCRateLimit
+ ////Peripherals
+ //DHT
+ | BCDHTTemp UInt8 | BCDHTHumid UInt8
+ ...
+\end{lstClean}
+
+\subsection{Compiler}
+The bytecode 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.
+The state monad accumulates the code, and stores the stateful data the compiler requires.
+\Cref{lst:compiler_state} shows the data type for the state, storing:
+function the compiler currently is in;
+code of the main expression;
+context (see \todo{insert ref to compilation rules step here});
+code for the functions;
+next fresh label;
+a list of all the used \glspl{SDS}, either local \glspl{SDS} containing the initial value (\cleaninline{Left}) or lifted \glspl{SDS} (see \cref{sec:liftsds}) containing a reference to the associated \gls{ITASK} \gls{SDS};
+and finally there is a list of peripherals used.
+
+\begin{lstClean}[label={lst:compiler_state},caption={\Gls{MTASK}'s byte code compiler type}]
+:: BCInterpret a :== StateT BCState (WriterT [BCInstr] Identity) a
+:: BCState =
+ { bcs_infun :: JumpLabel
+ , bcs_mainexpr :: [BCInstr]
+ , bcs_context :: [BCInstr]
+ , bcs_functions :: Map JumpLabel BCFunction
+ , bcs_freshlabel :: JumpLabel
+ , bcs_sdses :: [Either String255 MTLens]
+ , bcs_hardware :: [BCPeripheral]
+ }
+:: BCFunction =
+ { bcf_instructions :: [BCInstr]
+ , bcf_argwidth :: UInt8
+ , bcf_returnwidth :: UInt8
+ }
+\end{lstClean}
+
+Executing the compiler is done by providing an initial state.
+After compilation, several post-processing steps are applied to make the code suitable for the microprocessor.
+First, in all tail call \cleaninline{BCReturn}'s are replaced by \cleaninline{BCTailCall} to implement tail call elimination.
+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.
+For example, the \cleaninline{BCArg} instruction is often called with argument \qtyrange{0}{2} and can be replaced by the \cleaninline{BCArg0}--\cleaninline{BCArg2} shorthands.
+Furthermore, redundant instructions (e.g.\ 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 freshly generated identifiers.
+After the byte code is ready, the lifted \glspl{SDS} are resolved to provide an initial value for them.
+The result---byte code, \gls{SDS} specification and perpipheral specifications---are the result of the process, ready to be sent to the device.
+
+\section{Compilation rules}
+This section describes the compilation rules, the translation from abstract syntax to byte code.
+The compilation scheme consists of three schemes\slash{}functions.
+When something is surrounded by $\parallel$, e.g.\ $\parallel{}a_i\parallel{}$, it denotes the number of stack cells required to store it.
+
+Some schemes have a \emph{context} $r$ as an argument which contains information about the location of the arguments in scope.
+More information is given in the schemes requiring such arguments.
+
+\newcommand{\cschemeE}[2]{\mathcal{E}\llbracket#1\rrbracket~#2}
+\newcommand{\cschemeF}[1]{\mathcal{F}\llbracket#1\rrbracket}
+\newcommand{\cschemeS}[3]{\mathcal{S}\llbracket#1\rrbracket~#2~#3}
+\begin{table}
+ \centering
+ \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.\\
+ \bottomrule
+ \end{tabularx}
+\end{table}
+
+\subsection{Expressions}
+Almost all expression constructions are compiled using $\mathcal{E}$.
+The argument of $\mathcal{E}$ is the context (see \cref{ssec:functions}).
+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.
+
+\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};
+ \cschemeE{e_2}{r};
+ \text{\cleaninline{BCAdd}};\\
+ {} & \text{\emph{Similar for other binary operators}}\\
+ \cschemeE{\text{\cleaninline{Not}}~e}{r} & =
+ \cschemeE{e}{r};
+ \text{\cleaninline{BCNot}};\\
+ {} & \text{\emph{Similar for other unary operators}}\\
+ \cschemeE{\text{\cleaninline{If}}~e_1~e_2~e_3}{r} & =
+ \cschemeE{e_1}{r};
+ \text{\cleaninline{BCJmpF}}\enskip l_{else}; \mathbin{\phantom{=}} \cschemeE{e_2}{r}; \text{\cleaninline{BCJmp}}\enskip l_{endif};\\
+ {} & \mathbin{\phantom{=}} \text{\cleaninline{BCLabel}}\enskip l_{else}; \cschemeE{e_3}{r}; \mathbin{\phantom{=}} \text{\cleaninline{BCLabel}}\enskip l_{endif};\\
+ {} & \text{\emph{Where $l_{else}$ and $l_{endif}$ are fresh labels}}\\
+ \cschemeE{\text{\cleaninline{tupl}}~e_1~e_2}{r} & =
+ \cschemeE{e_1}{r};
+ \cschemeE{e_2}{r};\\
+ {} & \text{\emph{Similar for other unboxed compound data types}}\\
+ \cschemeE{\text{\cleaninline{first}}~e}{r} & =
+ \cschemeE{e}{r};
+ \text{\cleaninline{BCPop}}\enskip w;\\
+ {} & \text{\emph{Where $w$ is the width of the left value and}}\\
+ {} & \text{\emph{similar for other unboxed compound data types}}\\
+ \cschemeE{\text{\cleaninline{second}}\enskip e}{r} & =
+ \cschemeE{e}{r};
+ \text{\cleaninline{BCRot}}\enskip w_1\enskip (w_1+w_2);
+ \text{\cleaninline{BCPop}}\enskip w_2;\\
+ {} & \text{\emph{Where $w_1$ is the width of the left and, $w_2$ of the right value}}\\
+ {} & \text{\emph{similar for other unboxed compound data types}}\\
+\end{align*}
+
+Translating $\mathcal{E}$ to \gls{CLEAN} code is very straightforward, it basically means executing the 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` :: BCInterpret a}} helper is used.
+This function is similar to the writer monad's \cleaninline{tell} function but is casted 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 but stored in the state.
+
+\begin{lstClean}[caption={Interpretation implementation for the arithmetic and conditional classes.},label={lst:imp_arith}]
+instance expr BCInterpret where
+ lit t = tell` [BCPush (toByteCode{|*|} t)]
+ (+.) a b = a >>| b >>| tell` [BCAdd]
+ ...
+ If c t e = freshlabel >>= \elselabel->freshlabel >>= \endiflabel->
+ c >>| tell` [BCJumpF elselabel] >>|
+ t >>| tell` [BCJump endiflabel,BCLabel elselabel] >>|
+ e >>| tell` [BCLabel endiflabel]
+\end{lstClean}
+
+\subsection{Functions}
+Compiling functions occurs in $\mathcal{F}$, which generates bytecode for the complete program by iterating over the functions and ending with the main expression.
+When compiling the body of the function, the arguments of the function are added to the context so that the addresses can be determined when referencing arguments.
+The main expression is a special case of $\mathcal{F}$ since it neither has arguments nor something to continue.
+Therefore, it is just compiled using $\mathcal{E}$.
-\section{Run time system}
+\begin{align*}
+ \cschemeF{main=m} & =
+ \cschemeE{m}{[]};\\
+ \cschemeF{f~a_0 \ldots a_n = b~\text{\cleaninline{In}}~m} & =
+ \text{\cleaninline{BCLabel}}~f;\\
+ {} & \mathbin{\phantom{=}} \cschemeE{b}{[\langle f, i\rangle, i\in \{(\Sigma^n_{i=0}\parallel{}a_i\parallel{})..0\}]};\\
+ {} & \mathbin{\phantom{=}} \text{\cleaninline{BCReturn}}~\parallel{}b\parallel{}~n;\\
+ {} & \mathbin{\phantom{=}} \cschemeF{m};\\
+\end{align*}
+%
+%A function call starts by pushing the stack and frame pointer, and making space for the program counter (a) followed by evaluating the arguments in reverse order (b).
+%On executing \Cl{BCJumpSR}, the program counter is set and the interpreter jumps to the function (c).
+%When the function returns, the return value overwrites the old pointers and the arguments.
+%This occurs right after a \Cl{BCReturn} (d).
+%Putting the arguments on top of pointers and not reserving space for the return value uses little space and facilitates tail call optimization.
+%
+%\begin{figure}
+% \subfigure[\Cl{BCPushPtrs}]{\includegraphics[width=.24\linewidth]{memory1}}
+% \subfigure[Arguments]{\includegraphics[width=.24\linewidth]{memory2}}
+% \subfigure[\Cl{BCJumpSR}]{\includegraphics[width=.24\linewidth]{memory3}}
+% \subfigure[\Cl{BCReturn}]{\includegraphics[width=.24\linewidth]{memory4}}
+% \caption{The stack layout during function calls.}
+% \Description{A visual representation of the stack layout during a function call and a return.}
+%\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 Subsection~\ref{ssec:step}) and therefore the exact location always has to be determined from the context using \Cl{findarg}\footnote{%
+% \lstinline{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 preserve the order.
+%
+%\begin{compilationscheme}
+% \cschemeE{f(a_0, \ldots, a_n)}{r} & =
+% \text{\Cl{BCPushPtrs}};\\
+% {} & \mathbin{\phantom{=}} \cschemeE{a_n}{r}; \cschemeE{a_{\ldots}}{r}; \cschemeE{a_0}{r};\\
+% {} & \mathbin{\phantom{=}} \text{\Cl{BCJumpSR}}\enskip n\enskip f;\\
+% \cschemeE{a_{f^i}}{r} & =
+% \text{\Cl{BCArg} findarg}(r, f, i)\enskip \text{for all}\enskip i\in\{w\ldots v\};\\
+% {} & v = \Sigma^{i-1}_{j=0}\|a_{f^j}\|\\
+% {} & w = v + \|a_{f^i}\|\\
+%\end{compilationscheme}
+%
+%Translating the compilation schemes for functions to Clean is not as straightforward as other schemes due to the nature of shallow embedding.
+%The \Cl{fun} class has a single function with a single argument.
+%This argument is a Clean function that---when given a callable Clean function representing the mTask function---will produce \Cl{main} and a callable function.
+%To compile this, the argument must be called with a function representing a function call in mTask.
+%Listing~\ref{lst:fun_imp} shows the implementation for this as Clean code.
+%To uniquely identify the function, a fresh label is generated.
+%The function is then called with the \Cl{callFunction} helper function that generates the instructions that correspond to calling the function.
+%That is, it pushes the pointers, compiles the arguments, and writes the \Cl{JumpSR} instruction.
+%The resulting structure (\Cl{g In m}) contains a function representing the mTask function (\Cl{g}) and the \Cl{main} structure to continue with.
+%To get the actual function, \Cl{g} must be called with representations for the argument, i.e.\ using \Cl{findarg} for all arguments.
+%The arguments are added to the context and \Cl{liftFunction} is called with the label, the argument width and the compiler.
+%This function executes the compiler, decorates the instructions with a label and places them in the function dictionary together with the metadata such as the argument width.
+%After lifting the function, the context is cleared again and compilation continues with the rest of the program.
+%
+%\begin{lstlisting}[language=Clean,label={lst:fun_imp},caption={The backend implementation for functions.}]
+%instance fun (BCInterpret a) BCInterpret | type a where
+% fun def = {main=freshlabel >>= \funlabel->
+% let (g In m) = def \a->callFunction funlabel (byteWidth a) [a]
+% in addToCtx funlabel zero (argwidth def)
+% >>| liftFunction funlabel (argwidth def)
+% (g (findArgs funlabel zero (argwidth def))) Nothing
+% >>| clearCtx >>| m.main
+% }
+%
+%callFunction :: JumpLabel UInt8 [BCInterpret b] -> BCInterpret c | ...
+%liftFunction :: JumpLabel UInt8 (BCInterpret a) (Maybe UInt8) -> BCInterpret ()
+%\end{lstlisting}
+%
+%\subsection{Tasks}\label{ssec:scheme_tasks}
+%Task trees are created with the \Cl{BCMkTask} instruction that allocates a node and pushes it to the stack.
+%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 Subsection~\ref{ssec:step}).
+%
+%\begin{compilationscheme}
+% \cschemeE{\text{\Cl{rtrn}}\enskip e}{r} & =
+% \cschemeE{e}{r};
+% \text{\Cl{BCMkTask BCStable}}_{\|e\|};\\
+% \cschemeE{\text{\Cl{unstable}}\enskip e}{r} & =
+% \cschemeE{e}{r};
+% \text{\Cl{BCMkTask BCUnstable}}_{\|e\|};\\
+% \cschemeE{\text{\Cl{readA}}\enskip e}{r} & =
+% \cschemeE{e}{r};
+% \text{\Cl{BCMkTask BCReadA}};\\
+% \cschemeE{\text{\Cl{writeA}}\enskip e_1\enskip e_2}{r} & =
+% \cschemeE{e_1}{r};
+% \cschemeE{e_2}{r};
+% \text{\Cl{BCMkTask BCWriteA}};\\
+% \cschemeE{\text{\Cl{readD}}\enskip e}{r} & =
+% \cschemeE{e}{r};
+% \text{\Cl{BCMkTask BCReadD}};\\
+% \cschemeE{\text{\Cl{writeD}}\enskip e_1\enskip e_2}{r} & =
+% \cschemeE{e_1}{r};
+% \cschemeE{e_2}{r};
+% \text{\Cl{BCMkTask BCWriteD}};\\
+% \cschemeE{\text{\Cl{delay}}\enskip e}{r} & =
+% \cschemeE{e}{r};
+% \text{\Cl{BCMkTask BCDelay}};\\
+% \cschemeE{\text{\Cl{rpeat}}\enskip e}{r} & =
+% \cschemeE{e}{r};
+% \text{\Cl{BCMkTask BCRepeat}};\\
+% \cschemeE{e_1\text{\Cl{.||.}}e_2}{r} & =
+% \cschemeE{e_1}{r};
+% \cschemeE{e_2}{r};
+% \text{\Cl{BCMkTask BCOr}};\\
+% \cschemeE{e_1\text{\Cl{.&&.}}e_2}{r} & =
+% \cschemeE{e_1}{r};
+% \cschemeE{e_2}{r};
+% \text{\Cl{BCMkTask BCAnd}};\\
+%\end{compilationscheme}
+%
+%This simply translates to Clean code by writing the correct \Cl{BCMkTask} instruction as exemplified in Listing~\ref{lst:imp_ret}.
+%
+%\begin{lstlisting}[language=Clean,caption={The backend implementation for \Cl{rtrn}.},label={lst:imp_ret}]
+%instance rtrn BCInterpret where rtrn m = m >>| tell` [BCMkTask (bcstable m)]
+%\end{lstlisting}
+%
+%\subsection{Step combinator}\label{ssec:step}
+%The \Cl{step} construct is a special type of task because the task value of the left-hand side may change over time.
+%Therefore, the continuation tasks on the right-hand side are \emph{observing} this task value and acting upon it.
+%In the compilation scheme, all continuations are first converted to a single function that has two arguments: the stability of the task and its value.
+%This function either returns a pointer to a task tree or fails (denoted by $\bot$).
+%It is special because in the generated function, the task value of a task can actually be inspected.
+%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.
+%
+%\begin{compilationscheme}
+% \cschemeE{t_1\text{\Cl{>>*.}}t_2}{r} & =
+% \cschemeE{a_{f^i}}{r}, \langle f, i\rangle\in r;
+% \text{\Cl{BCMkTask}}\enskip \text{\Cl{BCStable}}_{\|r\|};\\
+% {} & \mathbin{\phantom{=}} \cschemeE{t_1}{r};\\
+% {} & \mathbin{\phantom{=}} \text{\Cl{BCMkTask}}\enskip \text{\Cl{BCAnd}};\\
+% {} & \mathbin{\phantom{=}} \text{\Cl{BCMkTask}}\\
+% {} & \mathbin{\phantom{=}} \enskip (\text{\Cl{BCStep}}\enskip (\cschemeS{t_2}{(r + [\langle l_s, i\rangle])}{\|t_1\|}));\\
+%%
+% \cschemeS{[]}{r}{w} & =
+% \text{\Cl{BCPush}}\enskip \bot;\\
+% \cschemeS{\text{\Cl{IfValue}}\enskip f\enskip t:cs}{r}{w} & =
+% \text{\Cl{BCArg}} (\|r\| + w);
+% \text{\Cl{BCIsNoValue}};\\
+% {} & \mathbin{\phantom{=}} \cschemeE{f}{r};
+% \text{\Cl{BCAnd}};\\
+% {} & \mathbin{\phantom{=}} \text{\Cl{BCJmpF}}\enskip l_1;\\
+% {} & \mathbin{\phantom{=}} \cschemeE{t}{r};
+% \text{\Cl{BCJmp}}\enskip l_2;\\
+% {} & \mathbin{\phantom{=}} \text{\Cl{BCLabel}}\enskip l_1;
+% \cschemeS{cs}{r}{w};\\
+% {} & \mathbin{\phantom{=}} \text{\Cl{BCLabel}}\enskip l_2;\\
+% {} & \text{\emph{Where $l_1$ and $l_2$ are fresh labels}}\\
+% {} & \text{\emph{Similar for \Cl{IfStable} and \Cl{IfUnstable}}}\\
+% \cschemeS{\text{\Cl{IfNoValue}}\enskip t:cs}{r}{w} & =
+% \text{\Cl{BCArg}} (\|r\|+w);
+% \text{\Cl{BCIsNoValue}};\\
+% {} & \mathbin{\phantom{=}} \text{\Cl{BCJmpF}}\enskip l_1;\\
+% {} & \mathbin{\phantom{=}} \cschemeE{t}{r};
+% \text{\Cl{BCJmp}}\enskip l_2;\\
+% {} & \mathbin{\phantom{=}} \text{\Cl{BCLabel}}\enskip l_1;
+% \cschemeS{cs}{r}{w};\\
+% {} & \mathbin{\phantom{=}} \text{\Cl{BCLabel}}\enskip l_2;\\
+% {} & \text{\emph{Where $l_1$ and $l_2$ are fresh labels}}\\
+% \cschemeS{\text{\Cl{Always}}\enskip f:cs}{r}{w} & =
+% \cschemeE{f}{r};\\
+%\end{compilationscheme}
+%
+%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 \Cl{.&&.} 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 follows:
+%
+%\begin{lstlisting}[language=Clean]
+%t1 >>= \v1->t2 >>= \v2->t3 >>= ...
+%//is transformed to
+%t1 >>= \v1->rtrn v1 .&&. t2 >>= \v2->rtrn (v1, v2) .&&. t3 >>= ...
+%\end{lstlisting}
+%
+%The translation to Clean is given in Listing~\ref{lst:imp_seq}.
+%
+%\begin{lstlisting}[language=Clean,caption={Backend implementation for the step class.},label={lst:imp_seq}]
+%instance step BCInterpret where
+% (>>*.) lhs cont
+% //Fetch a fresh label and fetch the context
+% = freshlabel >>= \funlab->gets (\s->s.bcs_context)
+% //Generate code for lhs
+% >>= \ctx->lhs
+% //Possibly add the context
+% >>| tell` (if (ctx =: []) []
+% //The context is just the arguments up till now in reverse
+% ( [BCArg (UInt8 i)\\i<-reverse (indexList ctx)]
+% ++ map BCMkTask (bcstable (UInt8 (length ctx)))
+% ++ [BCMkTask BCTAnd]
+% ))
+% //Increase the context
+% >>| addToCtx funlab zero lhswidth
+% //Lift the step function
+% >>| liftFunction funlab
+% //Width of the arguments is the width of the lhs plus the
+% //stability plus the context
+% (one + lhswidth + (UInt8 (length ctx)))
+% //Body label ctx width continuations
+% (contfun funlab (UInt8 (length ctx)))
+% //Return width (always 1, a task pointer)
+% (Just one)
+% >>| modify (\s->{s & bcs_context=ctx})
+% >>| tell` [BCMkTask $ instr rhswidth funlab]
+%
+%toContFun :: JumpLabel UInt8 -> BCInterpret a
+%toContFun steplabel contextwidth
+% = foldr tcf (tell` [BCPush fail]) cont
+%where
+% tcf (IfStable f t)
+% = If ((stability >>| tell` [BCIsStable]) &. f val)
+% (t val >>| tell` [])
+% ...
+% stability = tell` [BCArg $ lhswidth + contextwidth]
+% val = retrieveArgs steplabel zero lhswidth
+%\end{lstlisting}
+%
+%\subsection{Shared Data Sources}
+%The compilation scheme for SDS definitions is a trivial extension to $\mathcal{F}$ since there is no code generated as seen below.
+%
+%\begin{compilationscheme}
+% \cschemeF{\text{\Cl{sds}}\enskip x=i\enskip \text{\Cl{In}}\enskip m} & =
+% \cschemeF{m};\\
+% \cschemeF{\text{\Cl{liftsds}}\enskip x=i\enskip \text{\Cl{In}}\enskip m} & =
+% \cschemeF{m};\\
+%\end{compilationscheme}
+%
+%The SDS access tasks have a compilation scheme similar to other tasks (see~Subsection~\ref{ssec:scheme_tasks}).
+%The \Cl{getSds} task just pushes a task tree node with the SDS identifier embedded.
+%The \Cl{setSds} task evaluates the value, lifts that value to a task tree node and creates an SDS set node.
+%
+%\begin{compilationscheme}
+% \cschemeE{\text{\Cl{getSds}}\enskip s}{r} & =
+% \text{\Cl{BCMkTask}} (\text{\Cl{BCSdsGet}} s);\\
+% \cschemeE{\text{\Cl{setSds}}\enskip s\enskip e}{r} & =
+% \cschemeE{e}{r};
+% \text{\Cl{BCMkTask BCStable}}_{\|e\|};\\
+% {} & \mathbin{\phantom{=}} \text{\Cl{BCMkTask}} (\text{\Cl{BCSdsSet}} s);\\
+%\end{compilationscheme}
+%
+%While there is no code generated in the definition, the bytecode compiler is storing the SDS data in the \Cl{bcs_sdses} field in the compilation state.
+%The SDSs are typed as functions in the host language so an argument for this function must be created that represents the SDS on evaluation.
+%For this, an \Cl{BCInterpret} is created that emits this identifier.
+%When passing it to the function, the initial value of the SDS is returned.
+%This initial value is stored as a bytecode encoded value in the state and the compiler continues with the rest of the program.
+%
+%Compiling \Cl{getSds} is a matter of executing the \Cl{BCInterpret} representing the SDS, which yields the identifier that can be embedded in the instruction.
+%Setting the 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.
+%Lifted SDSs are compiled in a very similar way.
+%The only difference is that there is no initial value but an iTasks SDS when executing the Clean function.
+%A lens on this SDS converting \Cl{a} from the \Cl{Shared a} to a \Cl{String255}---a bytecode encoded version---is stored in the state.
+%The encoding and decoding itself is unsafe when used directly but the type system of the language and the abstractions make it safe.
+%Upon sending the mTask task to the device, the initial values of the lifted SDSs are fetched to complete the SDS specification.
+%
+%\begin{lstlisting}[language=Clean,caption={Backend implementation for the SDS classes.},label={lst:comp_sds}]
+%:: Sds a = Sds Int
+%instance sds BCInterpret where
+% sds def = {main = freshsds >>= \sdsi->
+% let sds = modify (\s->{s & bcs_sdses=put sdsi
+% (Left (toByteCode t)) s.bcs_sdses})
+% >>| pure (Sds sdsi)
+% (t In e) = def sds
+% in e.main}
+% getSds f = f >>= \(Sds i)-> tell` [BCMkTask (BCSdsGet (fromInt i))]
+% setSds f v = f >>= \(Sds i)->v >>| tell`
+% ( map BCMkTask (bcstable (byteWidth v))
+% ++ [BCMkTask (BCSdsSet (fromInt i))])\end{lstlisting}
+%
+%\section{Run time system}
+%
+%The RTS is designed to run on systems with as little as 2kB of RAM.
+%Aggressive memory management is therefore vital.
+%Not all firmwares for MCUs support heaps and---when they do---allocation often leaves holes when not used in a Last In First Out strategy.
+%Therefore the RTS uses a chunk of memory in the global data segment with its own memory manager tailored to the needs of mTask.
+%The size of this block can be changed in the configuration of the RTS if necessary.
+%On an Arduino {UNO} ---equipped with 2kB of RAM--- this size can be about 1500 bytes.
+%
+%In memory, task data grows from the bottom up and an interpreter stack is located directly on top of it growing in the same direction.
+%As a consequence, the stack moves when a new task is received.
+%This never happens within execution because communication is always processed before execution.
+%Values in the interpreter are always stored on the stack, even tuples.
+%Task trees grow from the top down as in a heap.
+%This approach allows for flexible ratios, i.e.\ many tasks and small trees or few tasks and big trees.
+%
+%The event loop of the RTS is executed repeatedly and consists of three distinct phases.
+%
+%%TODO evt subsubsections verwijderen
+%\subsubsection{Communication}
+%In the first phase, the communication channels are processed.
+%The messages announcing SDS updates are applied immediately, the initialization of new tasks is delayed until the next phase.
+%
+%\subsubsection{Execution}
+%The second phase consists of executing tasks.
+%The RTS executes all tasks in a round robin fashion.
+%If a task is not initialized yet, the bytecode of the main function is interpreted to produce the initial task tree.
+%The rewriting engine uses the interpreter when needed, e.g.\ to calculate the step continuations.
+%The rewriter and the interpreter use the same stack to store intermediate values.
+%Rewriting steps are small so that interleaving results in seemingly parallel execution.
+%In this phase new task tree nodes may be allocated.
+%Both rewriting and initialization are atomic operations in the sense that no processing on SDSs is done other than SDS operations from the task itself.
+%The host is notified if a task value is changed after a rewrite step.
+%
+%\subsubsection{Memory management}
+%The third and final phase is memory management.
+%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 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.
+%\subsection{Memory management}
+%\subsection{Interpreter}
+%\subsection{Rewrite engine}
+%\section{Task rewriting}\label{sec:rewrite}
+%Tasks are rewritten every event loop iteration and one rewrite cycle is generally very fast.
+%This results in seemingly parallel execution of the tasks because the rewrite steps are interleaved.
+%Rewriting is a destructive process that actually modifies the task tree nodes in memory and marks nodes that become garbage.
+%The task value is stored on the stack and therefore only available during rewriting.
+%
+%\subsection{Basic tasks}
+%The \Cl{rtrn} and \Cl{unstable} tasks always rewrite to themselves and have no side effects.
+%The GPIO interaction tasks do have side effects.
+%The \Cl{readA} and \Cl{readD} tasks will query the given pin every rewrite cycle and emit it as an unstable task value.
+%The \Cl{writeA} and \Cl{writeD} tasks write the given value to the given pin and immediately rewrite to a stable task of the written value.
+%
+%\subsection{Delay and repetition}
+%The \Cl{delay} task stabilizes once a certain amount of time has been passed by storing the finish time on initialization.
+%In every rewrite step it checks whether the current time is bigger than the finish time and if so, it rewrites to a \Cl{rtrn} task containing the number of milliseconds that it overshot the target.
+%The \Cl{rpeat} task combinator rewrites the argument until it becomes stable.
+%Rewriting is a destructive process and therefore the original task tree must be saved.
+%As a consequence, on installation, the argument is cloned and the task rewrites the clone.
+%
+%\subsection{Sequential combination}
+%First the left-hand side of the step task is rewritten.
+%The resulting value is passed to the continuation function.
+%If the continuation function returns a pointer to a task tree, the task tree rewrites to that task tree and marks the original left-hand side as trash.
+%If the function returns $\bot$, the step is kept unchanged.
+%The step itself never fields a value.
+%
+%\subsection{Parallel combination}\label{ssec:parallelExecution}
+%There are two parallel task combinators available.
+%A \Cl{.&&.} task only becomes stable when both sides are stable.
+%A \Cl{.||.} task becomes stable when one of the sides is stable.
+%The combinators first rewrite both sides and then merge the task values according to the semantics given in Listing~\ref{lst:parallel_combinators}.
+%
+%\begin{lstlisting}[language=Clean,caption={Task value semantics for the parallel combinators.},label={lst:parallel_combinators}]
+%(.&&.) :: (TaskValue a) (TaskValue b) -> TaskValue (a, b)
+%(.&&.) (Value lhs stab1) (Value rhs stab2) = Value (lhs, rhs) (stab1 && stab2)
+%(.&&.) _ _ = NoValue
+%
+%(.||.) :: (TaskValue a) (TaskValue a) -> TaskValue a
+%(.||.) lhs=:(Value _ True) _ = lhs
+%(.||.) (Value lhs _) rhs=:(Value _ True) = rhs
+%(.||.) NoValue rhs = rhs
+%(.||.) lhs _ = lhs\end{lstlisting}
+%
+%\subsection{Shared Data Source tasks}
+%The \Cl{BCSdsGet} node always rewrites to itself.
+%It will read the actual SDS embedded and emit the value as an unstable task value.
+%
+%Setting an SDS is a bit more involved because after writing, it emits the value written as a stable task value.
+%The \Cl{BCSdsSet} node contains the identifier for the SDS and a task tree that, when rewritten, emits the value to be set as a stable task value.
+%The naive approach would be to just rewrite the \Cl{BCSdsSet} to a node similar to the \Cl{BCSdsGet} but only with a stable value.
+%However, after writing the SDS, its value might have changed due to other tasks writing it, and then the \Cl{setSDS}'s stable value may change.
+%Therefore, the \Cl{BCSdsSet} node is rewritten to the argument task tree which always represents constant stable value.
+%In future rewrites, the constant value node emits the value that was originally written.
+%
+%The client only knows whether an SDS is a lifted SDS, not to which iTasks SDS it is connected.
+%If the SDS is modified on the device, it sends an update to the server.
+%
+%\section{Conclusion}
\input{subfilepostamble}
\end{document}
repositories / phd-thesis.git / blobdiff