-Some functionality of the original \gls{mTask}-\gls{EDSL} will not be used in
-this extension \gls{EDSL}. Conversely, some functionality needed was not
-available in the existing \gls{EDSL}. Due to the nature of class based shallow
-embedding this obstacle is very easy to solve. A type housing the \gls{EDSL}
-does not have to implement all the available classes. Moreover, classes can be
-added at will without interfering with the existing views.
+The \glspl{Task} suitable for a client are called \glspl{mTask} and are written
+in the aforementioned \gls{mTask}-\gls{EDSL}. Some functionality of the
+original \gls{mTask}-\gls{EDSL} will not be used in this system. Conversely,
+some functionality needed was not available in the existing \gls{EDSL}. Due to
+the nature of class based shallow embedding this obstacle is very easy to
+solve. A type --- housing the \gls{EDSL} --- does not have to implement all the
+available classes. Moreover, classes can be added at will without interfering
+with the existing views.
\section{Semantics}
-\todo{semantics}
+The current \gls{mTask} engine for devices does not support \glspl{Task} in the
+sense that the \gls{C}-view does. \Glspl{Task} used with the \gls{C}-view are a
+main program that executes code and launches \glspl{Task}. It was also possible
+to just have a main program. The current \gls{mTask}-system only supports main
+programs. 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} message type.
-\section{Bytecode compilation}
+\begin{itemize}
+ \item\CI{OneShot}
+
+ \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 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 at predetermined intervals.
+ \item\CI{OnInterrupt}
+
+ The last scheduling method is running \glspl{Task} on a specific
+ 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}}
+\Glspl{SDS} on a client are available on the server as well as regular
+\gls{SDS}. However, the same freedom is not given on the \glspl{SDS} that
+reside on the client. Not all types are suitable to be located on a client.
+Moreover, \glspl{SDS} behave a little different on an \gls{mTask} device
+compared to the \gls{iTasks} system. In an \gls{iTasks} system, when the \gls{SDS}
+is updated, a broadcast to everyone in the system watching is made to notify
+them of the update. \glspl{SDS} can update very often and the
+update might not be the final value it will get. This results in a lot of
+expensive unneeded bandwidth usage. Therefore a device must publish the
+\gls{SDS} explicitly to save bandwidth.
+
+To add this functionality, the \CI{sds} class could be extended. However, this
+would result in having to update all existing views that use the \CI{sds}
+class. Therefore, an extra class is added that contains the extra
+functionality. The existing views can choose to implement it in the future but
+are not obliged to. The publication function has the following signature:
+\begin{lstlisting}[caption={The \texttt{sdspub} class}]
+class sdspub v where
+ pub :: (v t Upd) -> v t Expr | type t
+\end{lstlisting}
+
+\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
-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
-information is put in the state which is kept between compilations.
+\CI{ByteCode} object to be able to make use of the \gls{RWST} functionality
+such as return values. Tailor made access functions are used to achieve this
+with ease. The fresh variable stream 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 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
used in the bytecode view must fit in the \CI{BCValue} type which restricts
-the content. Most notably, the type must be bytecode encodable. A \CI{BCValue}
+the content. Most notably, the type must be bytecode encodable. A \CI{BCValue}
must be encodable and decodable without losing type or value information. At
-the moment a simple encoding scheme is used that uses a single byte prefixes to
-detect which type the value is. The devices know of these prefixes and act
-accordingly.
+the moment a simple encoding scheme is used that uses single byte prefixes to
+detect the type of the value. The devices know these prefixes and can apply the
+same detection if necessary.
\begin{lstlisting}[label={lst:bcview},caption={Bytecode view}]
:: ByteCode a p = BC (RWS () [BC] BCState ())
, sdsval :: BCValue
}
:: BCState =
- { freshl :: [Int]
- , freshs :: [Int]
+ { freshl :: Int
+ , freshs :: Int
, sdss :: [BCShare]
}
\section{Implementation}
\subsection{Instruction Set}
The instruction set is given in Listing~\ref{bc:instr}. The instruction set is
-kept large, but under $255$, to get the highest expressivity for the lowest
-program size.
+kept large, but under $255$, to get the highest expressively while keeping all
+instruction one byte.
-The interpreter is a
-stack machine. Therefore the 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
-instructions.
+The interpreter running in the client is a stack machine. The virtual
+instruction \CI{BCLab} is added to allow for an easy implementation of jumping.
+However, this is not a real instruction and the labels are resolved to actual
+program memory addresses in the final step of compilation to save instructions
+and avoid label lookups at runtime.
\begin{lstlisting}[label={bc:instr},%
caption={Bytecode instruction set}]
| 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 single byte instructions can be converted automatically using the generic
+function \CI{consIndex} which returns the index of the constructor. The index
+of the constructor is the byte value for all instructions. The last step of the
+compilation is transforming the list of bytecode instructions to actual bytes.
\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
op2 :: (ByteCode a p1) (ByteCode a p2) BC -> ByteCode b Expr
op2 (BC x) (BC y) bc = BC (x >>| y >>| tell [bc])
-op :: (ByteCode a p) BC -> ByteCode a Expr
+op :: (ByteCode a p) BC -> ByteCode b c
op (BC x) bc = BC (x >>| tell [bc])
tell` :: [BC] -> (ByteCode a p)
\subsection{Arithmetics \& Peripherals}
Almost all of the code from the simple classes use exclusively helper
functions. Listing~\ref{lst:arithview} shows some implementations. The classes
-\CI{boolExpr} and the classes for the peripherals are implemented in the same
-fashion.
+\CI{boolExpr} and the classes for the peripherals are implemented using the
+same strategy.
\begin{lstlisting}[label={lst:arithview},caption={%
Bytecode view implementation for arithmetic and peripheral classes}]
\end{lstlisting}
\subsection{Control Flow}
+Implementing the sequence operator 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 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 anyway.
+
\begin{lstlisting}[label={lst:controlflow},%
caption={Bytecode view for \texttt{arith}}]
+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
+instance If ByteCode Stmt e Stmt where If b t e = BCIfStmt b t e
+instance If ByteCode x y Stmt where If b t e = BCIfStmt b t e
+instance IF ByteCode where
+ IF b t e = BCIfStmt b t e
+ (?) b t = BCIfStmt b t (tell` [])
+BCIfStmt (BC b) (BC t) (BC e) = BC (
+ freshlabel >>= \else->freshlabel >>= \endif->
+ b >>| tell [BCJmpF else] >>|
+ t >>| tell [BCJmp endif, BCLab else] >>|
+ e >>| tell [BCLab endif]
+ )
instance noOp ByteCode where
noOp = tell` [BCNop]
\end{lstlisting}
\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
-the actual state with the value obtained from the function. The exact
+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=:{freshs}->put {st & freshs=freshs+1} >>| pure freshs
+
instance sds ByteCode where
- sds f = {main = BC (freshs
- >>= \sdsi->pure {BCShare | sdsi=sdsi,sdsval=BCValue 0}
+ sds f = {main = BC (freshshare
+ >>= \sdsi->pure {BCShare|sdsi=sdsi,sdsval=BCValue 0}
>>= \sds->pure (f (tell` [BCSdsFetch sds]))
>>= \(v In bdy)->modify (addSDS sds v)
>>| unBC (unMain bdy))
}
+instance sdspub ByteCode where
pub (BC x) = BC (censor (\[BCSdsFetch s]->[BCSdsPublish s]) x)
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 fetch 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
-rewritten as a \CI{BCSdsStore}. The implementation for this is given in
-Listing~\ref{lst:assignmentview}.
+one \CI{BCSdsFetch} instruction with the correct \gls{SDS} embedded. Assigning
+to an analog pin will result in the \gls{RWST} containing the \CI{BCAnalogRead}
+instruction. When the assignable is not a read from but assigned to, the
+instruction will be rewritten as a store instruction. Resulting in an
+\CI{BCSdsStore} or \CI{BCAnalogWrite} instruction respectively. The
+implementation for this is given in Listing~\ref{lst:assignmentview}.
\begin{lstlisting}[label={lst:assignmentview},%
caption={Bytecode view implementation for assignment.}]
\end{lstlisting}
\section{Actual Compilation}
-\todo{hulp functies voor compileren}
+All the previous functions are tied together with the \CI{toMessages} function.
+This function compiles the bytecode and transforms the \gls{Task} in a message.
+The \glspl{SDS} that were not already sent to the device are also added as
+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. Then, the \emph{Jump} statements that
+jump to labels are transformed to jump to program memory 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.}]
+bclength :: BC -> Int
+bclength (BCPush s) = 1 + size (toByteCode s)
+bclength ... = ...
+bclength x = 1 + consNum{|*|} x
+
+computeGotos :: [BC] Int -> ([BC], Map Int Int)
+computeGotos [] _ = ([], newMap)
+computeGotos [BCLab l:xs] i = appSnd ('DM'.put l i) (computeGotos xs i)
+computeGotos [x:xs] i = appFst (\bc->[x:bc]) (computeGotos xs (i + bclength x))
+
+toRealByteCode :: (ByteCode a b) BCState -> (String, BCState)
+toRealByteCode x s
+# (s, bc) = runBC x s
+# (bc, gtmap) = computeGotos bc 1
+= (concat (map (toString o toByteVal) (map (implGotos gtmap) bc)), s)
+
+toMessages :: MTaskInterval (Main (ByteCode a b)) BCState -> ([MTaskMSGSend], BCState)
+toMessages interval x oldstate
+# (bc, newstate) = toRealByteCode (unMain x) oldstate
+# newsdss = difference newstate.sdss oldstate.sdss
+= ([MTSds sdsi e\\{sdsi,sdsval=e}<-newsdss] ++ [MTTask interval bc], newstate)
+\end{lstlisting}
+
+\section{Example}
+The heating example given previously in Listing~\ref{lst:exmtask} would be
+compiled to the following code. The left column indicates the
+position in the program memory.
+
+\begin{lstlisting}[caption={Thermostat bytecode},language=c]
+ 1-2 : BCAnalogRead (Analog A0)
+ 3-6 : BCPush (Int 50)
+ 7 : BCGre
+ 8-9 : BCJmpF 17 //Jump to else
+10-12: BCPush (Bool 1)
+13-14: BCDigitalWrite (Digital D0)
+15-16: BCJmp 21 //Jump to end of if
+17-19: BCPush (Bool 0) //Else label
+20 : BCDigitalWrite (Digital D0)
+\end{lstlisting}
+
+\section{Interpreter}
+The client contains an interpreter to execute a \gls{Task}'s bytecode.
+
+Before execution 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