sweep

[msc-thesis1617.git] / results.mtask.tex

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{\gls{Task} 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.

\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}

\section{\gls{SDS} semantics}
\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 view}\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 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 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}
must be encodable and decodable without losing type or value information. At
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 ())
:: BCValue = E.e: BCValue e & mTaskType, TC e
:: BCShare =
        { sdsi :: Int
        , sdsval :: BCValue
        }
:: BCState = 
        { freshl :: Int
        , freshs :: Int
        , sdss :: [BCShare]
        }

class toByteCode a :: a -> String
class fromByteCode a :: String -> a
class mTaskType a | toByteCode, fromByteCode, iTask, TC a

instance toByteCode Int, ... , UserLED, BCValue
instance fromByteCode Int, ... , UserLED, BCValue

instance arith ByteCode
...
instance serial ByteCode
\end{lstlisting}

\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 expressively while keeping all
instruction one byte. 

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}]
:: BC = BCNop
        | BCLab Int          | BCPush BCValue     | BCPop
        //SDS functions
        | BCSdsStore BCShare | BCSdsFetch BCShare | BCSdsPublish BCShare
        //Unary ops
        | BCNot
        //Binary Int ops
        | BCAdd              | BCSub              | BCMul
        | BCDiv
        //Binary Bool ops
        | BCAnd              | BCOr
        //Binary ops
        | BCEq               | BCNeq              | BCLes             | BCGre
        | BCLeq              | BCGeq
        //Conditionals and jumping
        | BCJmp Int          | BCJmpT Int         | BCJmpF Int
        //UserLED
        | BCLedOn            | BCLedOff
        //Pins
        | BCAnalogRead Pin   | BCAnalogWrite Pin  | BCDigitalRead Pin | BCDigitalWrite Pin
        //Return
        | BCReturn
\end{lstlisting}

All single byte instructions are 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, 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
to the \emph{Writer} value.

\begin{lstlisting}[label={lst:helpers},caption={Some helper functions}]
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 b c
op (BC x) bc = BC (x >>| tell [bc])

tell` :: [BC] -> (ByteCode a p)
tell` x = BC (tell x)

unBC :: (ByteCode a p) -> RWS () [BC] BCState ()
unBC (BC x) = x
\end{lstlisting}

\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 using the
same strategy.

\begin{lstlisting}[label={lst:arithview},caption={%
        Bytecode view implementation for arithmetic and peripheral classes}]
instance arith ByteCode where
        lit x = tell` [BCPush (BCValue x)]
        (+.) x y = op2 x y BCDiv
        ...

instance userLed ByteCode where
        ledOn  l = op l BCLedOn
        ledOff l = op l BCLedOff
\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}

\todo{Add return instruction}

\subsection{Shared Data Sources \& Assignment}
Shared data sources must be acquired from the state and constructing one
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 \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 (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 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. 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.}]
instance assign ByteCode where
        (=.) (BC v) (BC e) = BC (e >>| censor makeStore v)

makeStore [BCSdsFetch i]    = [BCSdsStore i]
makeStore [BCDigitalRead i] = [BCDigitalWrite i]
makeStore [...]             = [...]
\end{lstlisting}

\subsection{Actual Compilation}
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{Examples}
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}
\todo{More elaborate example}