results.mtask.tex

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