\input{subfilepreamble}
-\setcounter{chapter}{5}
+\setcounter{chapter}{4}
\begin{document}
\input{subfileprefix}
\subsection{Execution}
The second phase consists of performing 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 be executed, the \gls{RTS} selects all tasks that can be scheduled, see \cref{sec:scheduling} for more details.
-A task is stored below the stack and its complete state is a \gls{CLEAN} record contain most importantly the task id, a pointer to the task tree in the heap (null if not initialised yet), the current task value, the configuration of \glspl{SDS}, the configuration of peripherals, the byte code and some scheduling information.
+Execution of a task is always an interplay between the interpreter and the \emph{rewriter}.
If a task is not initialized 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 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.
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.
\caption{Memory layout}\label{fig:memory_layout}
\end{figure}
+A task is stored below the stack and its complete state is a \gls{CLEAN} record contain most importantly the task id, a pointer to the task tree in the heap (null if not initialised yet), the current task value, the configuration of \glspl{SDS}, the configuration of peripherals, the byte code and some scheduling information.
+
In memory, task data grows from the bottom up and the 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.
+Values in the interpreter are always stored on the stack.
+Compound data types are stored unboxed and flattened.
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.
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.
-\todo{plaa\-tje van me\-mo\-ry hier}
+\todo{plaa\-tje van me\-mo\-ry hier uitbreiden}
\section{Compiler}
\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.
+The instruction set is a fairly standard stack machine instruction set extended with special \gls{TOP} instructions for creating task tree nodes.
+All instructions are housed in a \gls{CLEAN} \gls{ADT} and serialised to the byte representation using a generic function.
+Type synonyms (\cref{lst:type_synonyms}) are used to provide insight on the arguments of the instructions.
+Labels are always two bytes long, all other arguments are one byte long.
-\begin{lstClean}[caption={The type housing the instruction set.},label={lst:instruction_type}]
+\begin{lstClean}[caption={Type synonyms for instructions arguments.},label={lst:type_synonyms}]
:: ArgWidth :== UInt8 :: ReturnWidth :== UInt8
:: Depth :== UInt8 :: Num :== UInt8
:: SdsId :== UInt8 :: JumpLabel =: JL UInt16
+\end{lstClean}
+
+\Cref{lst:instruction_type} shows an excerpt of the \gls{CLEAN} type that represents the instruction set.
+For example, shorthand instructions are omitted for brevity.
+Detailed semantics for the instructions are given in \cref{chp:bytecode_instruction_set}.
+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.
-//** Datatype housing all instructions
+\begin{lstClean}[caption={The type housing the instruction set.},label={lst:instruction_type}]
:: BCInstr
- //Return instructions
//Jumps
= BCJumpF JumpLabel | BCJump JumpLabel | BCLabel JumpLabel | BCJumpSR ArgWidth JumpLabel
| BCReturn ReturnWidth ArgWidth | BCTailcall ArgWidth ArgWidth JumpLabel
| 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
| BCAddI | BCSubI | ...
...
-//** Datatype housing all task types
:: BCTaskType
- = BCStableNode ArgWidth | ArgWidth
+ = BCStableNode ArgWidth | BCUnstableNode ArgWidth
// Pin io
| BCReadD | BCWriteD | BCReadA | BCWriteA | BCPinMode
// Interrupts
// Repeat
| BCRepeat
// Delay
- | BCDelay | BCDelayUntil //* Only for internal use
+ | BCDelay | BCDelayUntil
// Parallel
| BCTAnd | BCTOr
//Step
\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});
+context (see \cref{ssec:step});
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};
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.
+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.
rtrn m = m >>| tell` [BCMkTask (bcstable m)]
\end{lstClean}
-\subsection{Step combinator}\label{ssec:step}
+\subsection{Sequential combinator}\label{ssec:step}
The \cleaninline{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.
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.
-Lifted SDSs are compiled in a very similar way.\todo{deze \P{} moet naar integration?}
-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 \cleaninline{a} from the \cleaninline{Shared a} to a \cleaninline{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.
+Lifted SDSs are compiled in a very similar way \cref{sec:liftsds}.
% VimTeX: SynIgnore on
\begin{lstClean}[caption={Backend implementation for the SDS classes.},label={lst:comp_sds}]
\end{lstClean}
% VimTeX: SynIgnore off
-\section{C code generation}\label{sec:ccodegen}
+\section{\texorpdfstring{\Gls{C}}{C} code generation}\label{sec:ccodegen}
All communication between the \gls{ITASK} server and the \gls{MTASK} server is type-parametrised.
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 generic programming library or compiler support that includes a lot of metadata in the record and constructor nodes.
-
\section{Conclusion}
-\todo[inline]{conclusion}
+%\todo[inline]{conclusion}
\input{subfilepostamble}
\end{document}
repositories / phd-thesis.git / blobdiff