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