results.mtask.tex

   1 Some functionality of the original \gls{mTask}-\gls{EDSL} will not be used in
   2 this extension \gls{EDSL}. Conversely, some functionality needed was not
   3 available in the existing \gls{EDSL}. Due to the nature of class based shallow
   4 embedding this obstacle is very easy to solve. A type housing the \gls{EDSL}
   5 does not have to implement all the available classes. Moreover, classes can be
   6 added at will without interfering with the existing views.
   7
   8 \section{Semantics}
   9 \subsection{\glspl{mTask}}
  10 The current \gls{mTask} engine for devices does not support \glspl{Task} in the
  11 sense that the \gls{C}-view it does. \glspl{Task} in the new system are are
  12 \CI{Main} objects with a program inside. A \gls{Task} runs periodically, on
  13 interrupt or one-shot.
  14 \todo{elaborate}
  15
  16 \subsection{\glspl{SDS}}
  17 \glspl{SDS} behave a little bit differently on an \gls{mTask} device than in
  18 the \gls{iTasks} system. In an \gls{iTasks} system, when the \gls{SDS} is
  19 updated, a broadcast to everyone in the system watching is made to notify them
  20 of an update. \glspl{SDS} on the device can update very often and the update
  21 might not be the final value it will get. Therefore a device must publish the
  22 \gls{SDS} explicitly to save bandwidth. This means that an extra function is
  23 added to the \CI{sds} class that adds the \CI{pub} function.
  24 \todo{elaborate}
  25
  26 \section{Bytecode compilation}\label{sec:compiler}
  27 The \glspl{mTask} are sent to the device in bytecode and are saved in the
  28 memory of the device. To compile the \gls{EDSL} code to bytecode, a view is
  29 added to the \gls{mTask}-system called \CI{ByteCode}. As shown in
  30 Listing~\ref{lst:bcview}, the \CI{ByteCode} view is a boxed \gls{RWST} that
  31 writes bytecode instructions (\CI{BC}) while carrying around a \CI{BCState}.
  32 The state is kept between devices and contains fresh variable names and a
  33 register of shares used.
  34
  35 Types implementing the \gls{mTask} classes must have two free type variables.
  36 Therefore the \gls{RWST} is wrapped with a constructor and two phantom type
  37 variables are added. This means that the programmer has to unbox the
  38 \CI{ByteCode} object to be able to use return values for the monad. Tailor made
  39 access functions are used to achieve this with ease. The fresh variable stream
  40 in a compiler using an \gls{RWST} is often put in to the \emph{Reader} part of
  41 the monad. However, not all code is compiled immediately and later on the fresh
  42 variable stream can not contain variables that were used before. Therefore this
  43 information is put in the state which is kept between compilations.
  44
  45 Not all types are suitable for usage in bytecode compiled programs. Every value
  46 used in the bytecode view must fit in the \CI{BCValue} type which restricts
  47 the content. Most notably, the type must be bytecode encodable.  A \CI{BCValue}
  48 must be encodable and decodable without losing type or value information. At
  49 the moment a simple encoding scheme is used that uses a single byte prefixes to
  50 detect which type the value is. The devices know of these prefixes and act
  51 accordingly.
  52
  53 \begin{lstlisting}[label={lst:bcview},caption={Bytecode view}]
  54 :: ByteCode a p = BC (RWS () [BC] BCState ())
  55 :: BCValue = E.e: BCValue e & mTaskType, TC e
  56 :: BCShare =
  57         { sdsi :: Int
  58         , sdsval :: BCValue
  59         }
  60 :: BCState =
  61         { freshl :: [Int]
  62         , freshs :: [Int]
  63         , sdss :: [BCShare]
  64         }
  65
  66 class toByteCode a :: a -> String
  67 class fromByteCode a :: String -> a
  68 class mTaskType a | toByteCode, fromByteCode, iTask, TC a
  69
  70 instance toByteCode Int, ... , UserLED, BCValue
  71 instance fromByteCode Int, ... , UserLED, BCValue
  72
  73 instance arith ByteCode
  74 ...
  75 instance serial ByteCode
  76 \end{lstlisting}
  77
  78 \section{Implementation}
  79 \subsection{Instruction Set}
  80 The instruction set is given in Listing~\ref{bc:instr}. The instruction set is
  81 kept large, but under $255$, to get the highest expressivity for the lowest
  82 program size.
  83
  84 The interpreter is a
  85 stack machine. Therefore the it needs instructions like \emph{Push} and
  86 \emph{Pop}. The virtual instruction \CI{BCLab} is added to allow for an easy
  87 implementation. However, this is not a real instruction and the labels are
  88 resolved to actual addresses in the final step of compilation to save
  89 instructions.
  90
  91 \begin{lstlisting}[label={bc:instr},%
  92         caption={Bytecode instruction set}]
  93 :: BC = BCNop
  94         | BCLab Int          | BCPush BCValue     | BCPop
  95         //SDS functions
  96         | BCSdsStore BCShare | BCSdsFetch BCShare | BCSdsPublish BCShare
  97         //Unary ops
  98         | BCNot
  99         //Binary Int ops
 100         | BCAdd              | BCSub              | BCMul
 101         | BCDiv
 102         //Binary Bool ops
 103         | BCAnd              | BCOr
 104         //Binary ops
 105         | BCEq               | BCNeq              | BCLes             | BCGre
 106         | BCLeq              | BCGeq
 107         //Conditionals and jumping
 108         | BCJmp Int          | BCJmpT Int         | BCJmpF Int
 109         //UserLED
 110         | BCLedOn            | BCLedOff
 111         //Pins
 112         | BCAnalogRead Pin   | BCAnalogWrite Pin  | BCDigitalRead Pin | BCDigitalWrite Pin
 113         //Return
 114         | BCReturn
 115 \end{lstlisting}
 116
 117 All instructions are can be converted semi-automatically using the generic
 118 function \CI{consIndex\{*\}} that gives the index of the constructor. This
 119 constructor index is the actual byte value for the instruction. The
 120 \CI{BCValue} type contains existentially quantified types and therefore must
 121 have a given implementation for all generic functions.
 122
 123 \subsection{Helper functions}
 124 The \CI{ByteCode} type is just a boxed \gls{RWST} and that gives us access to
 125 the whole range of \gls{RWST} functions. However, to apply a function the type
 126 must be unboxed. After application the type must be boxed again. To achieve
 127 this some helper functions have been created. They are listed in
 128 Listing~\ref{lst:helpers}. The \CI{op} and \CI{op2} function is crafted to make
 129 operators that pop one or two values off the stack respectively. The \CI{tell`}
 130 is a wrapper around the \gls{RWST} function \CI{tell} that appends the argument
 131 to the \emph{Writer} value.
 132
 133 \begin{lstlisting}[label={lst:helpers},caption={Some helper functions}]
 134 op2 :: (ByteCode a p1) (ByteCode a p2) BC -> ByteCode b Expr
 135 op2 (BC x) (BC y) bc = BC (x >>| y >>| tell [bc])
 136
 137 op :: (ByteCode a p) BC -> ByteCode b c
 138 op (BC x) bc = BC (x >>| tell [bc])
 139
 140 tell` :: [BC] -> (ByteCode a p)
 141 tell` x = BC (tell x)
 142
 143 unBC :: (ByteCode a p) -> RWS () [BC] BCState ()
 144 unBC (BC x) = x
 145 \end{lstlisting}
 146
 147 \subsection{Arithmetics \& Peripherals}
 148 Almost all of the code from the simple classes use exclusively helper
 149 functions. Listing~\ref{lst:arithview} shows some implementations. The classes
 150 \CI{boolExpr} and the classes for the peripherals are implemented in the same
 151 fashion.
 152
 153 \begin{lstlisting}[label={lst:arithview},caption={%
 154         Bytecode view implementation for arithmetic and peripheral classes}]
 155 instance arith ByteCode where
 156         lit x = tell` [BCPush (BCValue x)]
 157         (+.) x y = op2 x y BCDiv
 158         ...
 159
 160 instance userLed ByteCode where
 161         ledOn  l = op l BCLedOn
 162         ledOff l = op l BCLedOff
 163 \end{lstlisting}
 164
 165 \subsection{Control Flow}
 166 Sequence is very straightforward in the bytecode view. The function just
 167 sequences the two \glspl{RWST}. The \emph{If} statement requires some detailed
 168 explanation since labels come in to play. The implementation speaks for itself
 169 in Listing~\ref{lst:controlflow}. First all the labels are gathered and then
 170 they are placed in the correct order in the bytecode sequence. It can happen
 171 that multiple labels appear consecutively in the code. This is not a problem
 172 since the labels are resolved to real addresses later on anyways.
 173
 174 \begin{lstlisting}[label={lst:controlflow},%
 175         caption={Bytecode view for \texttt{arith}}]
 176 freshlabel = get >>= \st=:{freshl=[fr:frs]}->put {st & freshl=frs} >>| pure fr
 177
 178 instance If ByteCode Stmt Stmt Stmt where If b t e = BCIfStmt b t e
 179 instance If ByteCode e Stmt Stmt    where If b t e = BCIfStmt b t e
 180 instance If ByteCode Stmt e Stmt    where If b t e = BCIfStmt b t e
 181 instance If ByteCode x y Stmt       where If b t e = BCIfStmt b t e
 182 instance IF ByteCode where
 183         IF b t e = BCIfStmt b t e
 184         (?) b t = BCIfStmt b t (tell` [])
 185 BCIfStmt (BC b) (BC t) (BC e) = BC (
 186         freshlabel >>= \else->freshlabel >>= \endif->
 187         b >>| tell [BCJmpF else] >>|
 188         t >>| tell [BCJmp endif, BCLab else] >>|
 189         e >>| tell [BCLab endif]
 190         )
 191 instance noOp ByteCode where
 192         noOp = tell` [BCNop]
 193 \end{lstlisting}
 194
 195 \subsection{Shared Data Sources \& Assignment}
 196 Shared data sources must be acquired from the state and constructing one
 197 happens via multiple steps. First a fresh identifier is grabbed from the state.
 198 Then a \CI{BCShare} record is created with that identifier. A \CI{BCSdsFetch}
 199 instruction is written and the body is generated to finally add the share to
 200 the actual state with the value obtained from the function. The exact
 201 implementation is shown in Listing~\ref{lst:shareview}.
 202
 203 \begin{lstlisting}[label={lst:shareview},%
 204         caption={Bytecode view for \texttt{arith}}]
 205 freshshare = get >>= \st=:{freshl=[fr:frs]}->put {st & freshl=frs} >>| pure fr
 206
 207 instance sds ByteCode where
 208         sds f = {main = BC (freshshare
 209                         >>= \sdsi->pure {BCShare | sdsi=sdsi,sdsval=BCValue 0}
 210                         >>= \sds->pure (f (tell` [BCSdsFetch sds]))
 211                         >>= \(v In bdy)->modify (addSDS sds v)
 212                         >>| unBC (unMain bdy))
 213                 }
 214         pub (BC x) = BC (censor (\[BCSdsFetch s]->[BCSdsPublish s]) x)
 215
 216 addSDS sds v s = {s & sdss=[{sds & sdsval=BCValue v}:s.sdss]}
 217 \end{lstlisting}
 218
 219 All assignable types compile to an \gls{RWST} that writes one instruction. For
 220 example, using an \gls{SDS} always results in an expression of the form
 221 \CI{sds \x=4 In ...}. The actual \CI{x} is the \gls{RWST} that always writes
 222 one \CI{BCSdsFetch} instruction with the correct \gls{SDS} embedded. When the
 223 call of the \CI{x} is not a read but an assignment,  the instruction will be
 224 rewritten as a \CI{BCSdsStore}. The implementation for this is given in
 225 Listing~\ref{lst:assignmentview}.
 226
 227 \begin{lstlisting}[label={lst:assignmentview},%
 228         caption={Bytecode view implementation for assignment.}]
 229 instance assign ByteCode where
 230         (=.) (BC v) (BC e) = BC (e >>| censor makeStore v)
 231
 232 makeStore [BCSdsFetch i]    = [BCSdsStore i]
 233 makeStore [BCDigitalRead i] = [BCDigitalWrite i]
 234 makeStore [...]             = [...]
 235 \end{lstlisting}
 236
 237 \section{Actual Compilation}
 238 All the previous functions are tied together with the \CI{toMessages} function.
 239 This function compiles the bytecode and transforms the \gls{Task} in a message.
 240 The \glspl{SDS} that were not already sent to the device are also placed in
 241 messages to be sent to the device. This functionality is listed in
 242 Listing~\ref{lst:compilation}. The compilation process consists of two steps.
 243 First the \gls{RWST} is executed, secondly the \emph{Jump} statements that jump
 244 to labels are transformed to jump to addresses. The translation of labels is
 245 possible in one sweep because no labels are reused. Reusing labels would not
 246 give a speed improvement since the labels are removed anyways in the end.
 247
 248 \begin{lstlisting}[label={lst:compilation},%
 249         caption={Actual compilation.}]
 250 bclength :: BC -> Int
 251 bclength (BCPush s) = 1 + size (toByteCode s)
 252 bclength ... = ...
 253 bclength x = 1 + consNum{|*|} x
 254
 255 computeGotos :: [BC] Int -> ([BC], Map Int Int)
 256 computeGotos [] _ = ([], newMap)
 257 computeGotos [BCLab l:xs] i = appSnd ('DM'.put l i) (computeGotos xs i)
 258 computeGotos [x:xs] i = appFst (\bc->[x:bc]) (computeGotos xs (i + bclength x))
 259
 260 toRealByteCode :: (ByteCode a b) BCState -> (String, BCState)
 261 toRealByteCode x s
 262 # (s, bc) = runBC x s
 263 # (bc, gtmap) = computeGotos bc 1
 264 = (concat (map (toString o toByteVal) (map (implGotos gtmap) bc)), s)
 265
 266 toMessages :: MTaskInterval (Main (ByteCode a b)) BCState -> ([MTaskMSGSend], BCState)
 267 toMessages interval x oldstate
 268 # (bc, newstate) = toRealByteCode (unMain x) oldstate
 269 # newsdss = difference newstate.sdss oldstate.sdss
 270 = ([MTSds sdsi e\\{sdsi,sdsval=e}<-newsdss] ++ [MTTask interval bc], newstate)
 271 \end{lstlisting}
 272
 273 \section{Example}
 274 The heating example given previously in Listing~\ref{lst:exmtask} would be
 275 compiled to the following code. The left column indicates the
 276 position in the program memory.
 277
 278 \begin{lstlisting}[caption={Thermostat bytecode},language=c]
 279  1-2 : BCAnalogRead (Analog A0)
 280  3-6 : BCPush (Int 50)
 281  7   : BCGre
 282  8-9 : BCJmpF 17                   //Jump to else
 283 10-12: BCPush (Bool 1)
 284 13-14: BCDigitalWrite (Digital D0)
 285 15-16: BCJmp 21                    //Jump to end of if
 286 17-19: BCPush (Bool 0)             //Else label
 287 20   : BCDigitalWrite (Digital D0)
 288 \end{lstlisting}
 289
 290 \todo{add more elaborate example?}