\section{Semantics}
The current \gls{mTask} engine for devices does not support \glspl{Task} in the
-sense that the \gls{C}-view it does. \Glspl{Task} used with the \gls{C}-view
-are a main program that runs some \gls{Task}. \glspl{Task} in the new system
-are \CI{Main} objects with a program inside that does not contain \glspl{Task}
-but are a \gls{Task} as a whole. Sending a \gls{Task} always goes together with
+sense that the \gls{C}-view does. \Glspl{Task} used with the \gls{C}-view are a
+main program that runs some \glspl{Task}. \glspl{Task} in the new system are
+\CI{Main} objects with a program inside that does not contain \glspl{Task} but
+are a \gls{Task} as a whole. Sending a \gls{Task} always goes together with
choosing a scheduling strategy. This strategy can be one of the following three
strategies as reflected in the \CI{MTTask}.
\CI{OneShot} takes no parameters and means that the \gls{Task} will run
once and will then be removed automatically. This type of scheduling
- could be usefull to for example retrieving sensor information on
+ could be useful, for example, in retrieving sensor information on
request of a user.
\item\CI{OnInterval}
\CI{OnInterval} has as a parameter the number of milliseconds to wait
in between executions. \Glspl{Task} running with this scheduling method
- are executed every fixed interval.
+ are executed at predetermined intervals.
\item\CI{OnInterrupt}
The last scheduling method is running \glspl{Task} on a specific
- interrupt. None of the current implementation implement this. However,
- registering interrupts on for example the \gls{Arduino} is very
- straightforward. Interrupt scheduling is usefull for \glspl{Task} that
- have to react on a certain type of hardware event such as the press of
- a button.
+ interrupt. None of the current client implementations support this.
+ However, registering interrupts on, for example the \gls{Arduino} is
+ very straightforward. Interrupt scheduling is useful for \glspl{Task}
+ that have to react on a certain type of hardware event such as the
+ press of a button.
\end{itemize}
\subsection{\glspl{SDS}}
\section{Bytecode compilation}\label{sec:compiler}
The \glspl{mTask} are sent to the device in bytecode and are saved in the
memory of the device. To compile the \gls{EDSL} code to bytecode, a view is
-added to the \gls{mTask}-system called \CI{ByteCode}. As shown in
-Listing~\ref{lst:bcview}, the \CI{ByteCode} view is a boxed \gls{RWST} that
-writes bytecode instructions (\CI{BC}) while carrying around a \CI{BCState}.
-The state is kept between devices and contains fresh variable names and a
-register of shares used.
+added to the \gls{mTask}-system encapsulated in the type \CI{ByteCode}. As
+shown in Listing~\ref{lst:bcview}, the \CI{ByteCode} view is a boxed \gls{RWST}
+that writes bytecode instructions (\CI{BC}) while carrying around a
+\CI{BCState}. The state is kept between compilations and is unique to a device.
+The state contains fresh variable names and a register of \glspl{SDS} used.
Types implementing the \gls{mTask} classes must have two free type variables.
Therefore the \gls{RWST} is wrapped with a constructor and two phantom type
variables are added. This means that the programmer has to unbox the
\CI{ByteCode} object to be able to use return values for the monad. Tailor made
access functions are used to achieve this with ease. The fresh variable stream
-in a compiler using an \gls{RWST} is often put in to the \emph{Reader} part of
+in a compiler using a \gls{RWST} is often put into the \emph{Reader} part of
the monad. However, not all code is compiled immediately and later on the fresh
-variable stream can not contain variables that were used before. Therefore this
+variable stream cannot contain variables that were used before. Therefore this
information is put in the state which is kept between compilations.
Not all types are suitable for usage in bytecode compiled programs. Every value
, sdsval :: BCValue
}
:: BCState =
- { freshl :: [Int]
- , freshs :: [Int]
+ { freshl :: Int
+ , freshs :: Int
, sdss :: [BCShare]
}
program size.
The interpreter is a
-stack machine. Therefore the it needs instructions like \emph{Push} and
+stack machine. Therefore it needs instructions like \emph{Push} and
\emph{Pop}. The virtual instruction \CI{BCLab} is added to allow for an easy
implementation. However, this is not a real instruction and the labels are
resolved to actual addresses in the final step of compilation to save
| BCReturn
\end{lstlisting}
-All instructions are can be converted semi-automatically using the generic
-function \CI{consIndex\{*\}} that gives the index of the constructor. This
-constructor index is the actual byte value for the instruction. The
-\CI{BCValue} type contains existentially quantified types and therefore must
-have a given implementation for all generic functions.
+All instructions can be converted semi-automatically using the generic function
+\CI{consIndex\{*\}} that gives the index of the constructor. This constructor
+index is the actual byte value for the instruction. The \CI{BCValue} type
+contains existentially quantified types and therefore must have a given
+implementation for all generic functions.
\subsection{Helper functions}
The \CI{ByteCode} type is just a boxed \gls{RWST} and that gives us access to
the whole range of \gls{RWST} functions. However, to apply a function the type
must be unboxed. After application the type must be boxed again. To achieve
-this some helper functions have been created. They are listed in
+this, several helper functions have been created. They are listed in
Listing~\ref{lst:helpers}. The \CI{op} and \CI{op2} function is crafted to make
operators that pop one or two values off the stack respectively. The \CI{tell`}
is a wrapper around the \gls{RWST} function \CI{tell} that appends the argument
\subsection{Control Flow}
Sequence is very straightforward in the bytecode view. The function just
sequences the two \glspl{RWST}. The \emph{If} statement requires some detailed
-explanation since labels come in to play. The implementation speaks for itself
-in Listing~\ref{lst:controlflow}. First all the labels are gathered and then
+explanation since labels come into play. The implementation speaks for itself
+in Listing~\ref{lst:controlflow}. First, all the labels are gathered and then
they are placed in the correct order in the bytecode sequence. It can happen
that multiple labels appear consecutively in the code. This is not a problem
-since the labels are resolved to real addresses later on anyways.
+since the labels are resolved to real addresses later on anyway.
\begin{lstlisting}[label={lst:controlflow},%
caption={Bytecode view for \texttt{arith}}]
-freshlabel = get >>= \st=:{freshl=[fr:frs]}->put {st & freshl=frs} >>| pure fr
+freshlabel = get >>= \st=:{freshl}->put {st & freshl=freshl+1} >>| pure freshl
instance If ByteCode Stmt Stmt Stmt where If b t e = BCIfStmt b t e
instance If ByteCode e Stmt Stmt where If b t e = BCIfStmt b t e
\subsection{Shared Data Sources \& Assignment}
Shared data sources must be acquired from the state and constructing one
-happens via multiple steps. First a fresh identifier is grabbed from the state.
+involves multiple steps. First, a fresh identifier is grabbed from the state.
Then a \CI{BCShare} record is created with that identifier. A \CI{BCSdsFetch}
-instruction is written and the body is generated to finally add the share to
+instruction is written and the body is generated to finally add the \gls{SDS} to
the actual state with the value obtained from the function. The exact
implementation is shown in Listing~\ref{lst:shareview}.
\begin{lstlisting}[label={lst:shareview},%
caption={Bytecode view for \texttt{arith}}]
-freshshare = get >>= \st=:{freshl=[fr:frs]}->put {st & freshl=frs} >>| pure fr
+freshshare = get >>= \st=:{freshs}->put {st & freshs=freshs+1} >>| pure freshs
instance sds ByteCode where
sds f = {main = BC (freshshare
addSDS sds v s = {s & sdss=[{sds & sdsval=BCValue v}:s.sdss]}
\end{lstlisting}
-All assignable types compile to an \gls{RWST} that writes one instruction. For
-example, using an \gls{SDS} always results in an expression of the form
+All assignable types compile to a \gls{RWST} that writes one instruction. For
+example, using a \gls{SDS} always results in an expression of the form
\CI{sds \x=4 In ...}. The actual \CI{x} is the \gls{RWST} that always writes
one \CI{BCSdsFetch} instruction with the correct \gls{SDS} embedded. When the
call of the \CI{x} is not a read but an assignment, the instruction will be
The \glspl{SDS} that were not already sent to the device are also placed in
messages to be sent to the device. This functionality is listed in
Listing~\ref{lst:compilation}. The compilation process consists of two steps.
-First the \gls{RWST} is executed, secondly the \emph{Jump} statements that jump
-to labels are transformed to jump to addresses. The translation of labels is
-possible in one sweep because no labels are reused. Reusing labels would not
-give a speed improvement since the labels are removed anyways in the end.
+First, the \gls{RWST} is executed. Then the \emph{Jump} statements that
+jump to labels are transformed to jump to addresses. The translation of labels
+is possible in one sweep because no labels are reused. Reusing labels would not
+give a speed improvement since the labels are removed anyway in the end.
\begin{lstlisting}[label={lst:compilation},%
caption={Actual compilation.}]
20 : BCDigitalWrite (Digital D0)
\end{lstlisting}
-\todo{add more elaborate example?}
+\section{Interpreter}
+The client contains an interpreter to execute a \gls{Task}'s bytecode.
+
+First some preparatory work is done. The stack will be initialized and the
+program counter and stack pointer are set to zero and the bottom respectively.
+Then the interpreter executes one step at the time while the program counter is
+smaller than the program length. The code for this is listed in
+Listing~\ref{lst:interpr}. One execution step is basically a big switch
+statement going over all possible bytecode instructions. Some instructions are
+detailed upon in the listing. The \CI{BCPush} instruction is a little more
+complicated in real life because some decoding will take place as not all
+\CI{BCValue}'s are of the same length.
+
+\begin{lstlisting}[language=C,label={lst:interpr},%
+ caption={Rough code outline for interpretation}]
+#define f16(p) program[pc]*265+program[pc+1]
+
+void run_task(struct task *t){
+ uint8_t *program = t->bc;
+ int plen = t->tasklength;
+ int pc = 0;
+ int sp = 0;
+ while(pc < plen){
+ switch(program[pc++]){
+ case BCNOP:
+ break;
+ case BCPUSH:
+ stack[sp++] = pc++ //Simplified
+ break;
+ case BCPOP:
+ sp--;
+ break;
+ case BCSDSSTORE:
+ sds_store(f16(pc), stack[--sp]);
+ pc+=2;
+ break;
+ // ...
+ case BCADD: trace("add");
+ stack[sp-2] = stack[sp-2] + stack[sp-1];
+ sp -= 1;
+ break;
+ // ...
+ case BCJMPT: trace("jmpt to %d", program[pc]);
+ pc = stack[--sp] ? program[pc]-1 : pc+1;
+ break;
+}
+\end{lstlisting}
repositories / msc-thesis1617.git / blobdiff