results.mtask.tex

   1 The \glspl{Task} suitable for a client are called \gls{mTask}-\gls{Task} and
   2 are written in the aforementioned \gls{mTask}-\gls{EDSL}. Some functionality of
   3 the original \gls{mTask}-\gls{EDSL} will not be used in this system.
   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 easy to solve. A type --- housing the \gls{EDSL} --- does not have to implement
   7 all the available classes. Moreover, classes can be added at will without
   8 interfering with the existing views.
   9
  10 \section{\gls{Task} 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 the number of milliseconds to wait in between
  29                 executions as a parameter. \Glspl{Task} running with this scheduling
  30                 method are executed at predetermined intervals.
  31         \item\CI{OnInterrupt}
  32
  33                 The last scheduling method is running \glspl{Task} on a specific
  34                 interrupt. Unfortunatly, due to time constraints and focus, none of the
  35                 current client implementations support this. Interrupt scheduling is
  36                 useful for \glspl{Task} that have to react on a certain type of
  37                 hardware event such as the press of a button.
  38 \end{itemize}
  39
  40 \section{\gls{SDS} semantics}
  41 \Gls{mTask}-\glspl{SDS} on a client are available on the server as in the form
  42 of regular \gls{iTasks}-\glspl{SDS}. However, the same freedom that an
  43 \gls{SDS} has in the \gls{iTasks}-system is not given for \glspl{SDS} that
  44 reside on the client. Not all types are suitable to be located on a client,
  45 simply because it needs to be representable on clients. Moreover, \glspl{SDS}
  46 behave a little different in an \gls{mTask} device compared to in the
  47 \gls{iTasks} system. In an \gls{iTasks} system, when the \gls{SDS} is updated,
  48 a broadcast to all watching \glspl{Task} in the system is made to notify them
  49 of the update. \glspl{SDS} can update often and the update might not be the
  50 final value it will get. Implementing the same functionality on the \gls{mTask}
  51 client would result in a lot of expensive unneeded bandwidth usage.  Therefore
  52 a device must publish the \gls{SDS} explicitly to save bandwidth.
  53
  54 To add this functionality, the \CI{sds} class could be extended. However, this
  55 would result in having to update all existing views that use the \CI{sds}
  56 class. Therefore, an extra class is added that contains the extra
  57 functionality. Programmers can choose to implement it for existing views in the
  58 future but are not obliged to. The publication function has the following
  59 signature:
  60 \begin{lstlisting}[caption={The \texttt{sdspub} class}]
  61 class sdspub v where
  62   pub :: (v t Upd) -> v t Expr | type t
  63 \end{lstlisting}
  64
  65 \section{Bytecode compilation view}\label{sec:compiler}
  66 The \gls{mTask}-\glspl{Task} are sent to the device in bytecode and are saved
  67 in the memory of the device. To compile the \gls{EDSL} code to bytecode, a view
  68 is added to the \gls{mTask}-system encapsulated in the type \CI{ByteCode}. As
  69 shown in Listing~\ref{lst:bcview}, the \CI{ByteCode} view is a boxed \gls{RWST}
  70 that writes bytecode instructions (\CI{BC}, Subsection~\ref{sec:instruction})
  71 while carrying around a \CI{BCState}. The state is kept between compilations
  72 and is unique to a device.  The state contains fresh variable names and a
  73 register of \glspl{SDS} that are used.
  74
  75 Types implementing the \gls{mTask} classes must have two free type variables.
  76 Therefore the \gls{RWST} is wrapped with a constructor and two phantom type
  77 variables are added. This means that the programmer has to unbox the
  78 \CI{ByteCode} object to be able to make use of the \gls{RWST} functionality
  79 such as return values. Tailor made access functions are used to achieve this
  80 with ease. The fresh variable stream in a compiler using a \gls{RWST} is often
  81 put into the \emph{Reader} part of the monad. However, not all code is compiled
  82 immediately and later on the fresh variable stream cannot contain variables
  83 that were used before. Therefore this information is put in the state which is
  84 kept between compilations.
  85
  86 Not all types are suitable for usage in bytecode compiled programs. Every value
  87 used in the bytecode view must fit in the \CI{BCValue} type which restricts
  88 the content. Most notably, the type must be bytecode encodable. A \CI{BCValue}
  89 must be encodable and decodable without losing type or value information. At
  90 the moment a simple encoding scheme is used that uses single byte prefixes to
  91 detect the type of the value. The devices know these prefixes and can apply the
  92 same detection if necessary.
  93
  94 \begin{lstlisting}[label={lst:bcview},caption={Bytecode view}]
  95 :: ByteCode a p = BC (RWS () [BC] BCState ())
  96 :: BCValue = E.e: BCValue e & mTaskType, TC e
  97 :: BCShare =
  98         { sdsi :: Int
  99         , sdsval :: BCValue
 100         }
 101 :: BCState =
 102         { freshl :: Int
 103         , freshs :: Int
 104         , sdss :: [BCShare]
 105         }
 106
 107 class toByteCode a :: a -> String
 108 class fromByteCode a :: String -> a
 109 class mTaskType a | toByteCode, fromByteCode, iTask, TC a
 110
 111 instance toByteCode Int, ... , UserLED, BCValue
 112 instance fromByteCode Int, ... , UserLED, BCValue
 113
 114 instance arith ByteCode
 115 ...
 116 instance serial ByteCode
 117 \end{lstlisting}
 118
 119 \subsection{Instruction Set}\label{sec:instruction}
 120 The instruction set is given in Listing~\ref{bc:instr}. The instruction set is
 121 kept large, but under $255$, to get as much expressive power as possible while
 122 keeping all instruction within one byte.
 123
 124 The interpreter running in the client is a stack machine. The virtual
 125 instruction \CI{BCLab} is added to allow for an easy implementation of jumping.
 126 However, this is not a real instruction and the labels are resolved to actual
 127 program memory addresses in the final step of compilation to save instructions
 128 and avoid label lookups at runtime.
 129
 130 \begin{lstlisting}[label={bc:instr},%
 131         caption={Bytecode instruction set}]
 132 :: BC = BCNop
 133         | BCLab Int          | BCPush BCValue     | BCPop
 134         //SDS functions
 135         | BCSdsStore BCShare | BCSdsFetch BCShare | BCSdsPublish BCShare
 136         //Unary ops
 137         | BCNot
 138         //Binary Int ops
 139         | BCAdd              | BCSub              | BCMul
 140         | BCDiv
 141         //Binary Bool ops
 142         | BCAnd              | BCOr
 143         //Binary ops
 144         | BCEq               | BCNeq              | BCLes             | BCGre
 145         | BCLeq              | BCGeq
 146         //Conditionals and jumping
 147         | BCJmp Int          | BCJmpT Int         | BCJmpF Int
 148         //UserLED
 149         | BCLedOn            | BCLedOff
 150         //Pins
 151         | BCAnalogRead Pin   | BCAnalogWrite Pin  | BCDigitalRead Pin | BCDigitalWrite Pin
 152         //Return
 153         | BCReturn
 154 \end{lstlisting}
 155
 156 All single byte instructions are converted automatically using a generic
 157 function which returns the index of the constructor. The index of the
 158 constructor is the byte value for all instructions. Added to this single byte
 159 value are the encoded parameters of the instruction. The last step of the
 160 compilation is transforming the list of bytecode instructions to actual bytes.
 161
 162 \subsection{Helper functions}
 163 Since the \CI{ByteCode} type is just a boxed \gls{RWST}, access to the whole
 164 range of \gls{RWST} functions is available. However, to use this, the type must
 165 be unboxed. After application the type must be boxed again. To achieve this,
 166 several helper functions have been created. They are given in
 167 Listing~\ref{lst:helpers}. The \CI{op} and \CI{op2} functions is hand-crafted
 168 to make operators that pop one or two values off the stack respectively. The
 169 \CI{tell`} function is a wrapper around the \gls{RWST} function \CI{tell} that
 170 appends the argument to the \emph{Writer} value.
 171
 172 \begin{lstlisting}[label={lst:helpers},caption={Some helper functions}]
 173 op2 :: (ByteCode a p1) (ByteCode a p2) BC -> ByteCode b Expr
 174 op2 (BC x) (BC y) bc = BC (x >>| y >>| tell [bc])
 175
 176 op :: (ByteCode a p) BC -> ByteCode b c
 177 op (BC x) bc = BC (x >>| tell [bc])
 178
 179 tell` :: [BC] -> (ByteCode a p)
 180 tell` x = BC (tell x)
 181
 182 unBC :: (ByteCode a p) -> RWS () [BC] BCState ()
 183 unBC (BC x) = x
 184 \end{lstlisting}
 185
 186 \subsection{Arithmetics \& Peripherals}
 187 Almost all of the code from the simple classes exclusively use helper
 188 functions. Listing~\ref{lst:arithview} shows some implementations. The
 189 \CI{boolExpr} class and the classes for the peripherals are implemented using
 190 the same strategy.
 191
 192 \begin{lstlisting}[label={lst:arithview},caption={%
 193         Bytecode view implementation for arithmetic and peripheral classes}]
 194 instance arith ByteCode where
 195         lit x = tell` [BCPush (BCValue x)]
 196         (+.) x y = op2 x y BCDiv
 197         ...
 198
 199 instance userLed ByteCode where
 200         ledOn  l = op l BCLedOn
 201         ledOff l = op l BCLedOff
 202 \end{lstlisting}
 203
 204 \subsection{Control Flow}
 205 Implementing the sequence operator is very straightforward in the bytecode
 206 view. The function just sequences the two \glspl{RWST}. The
 207 implementation for the \emph{If} statement speaks for itself in
 208 Listing~\ref{lst:controlflow}. First, all the labels are gathered after which
 209 they are placed in the correct order in the bytecode sequence. It can happen
 210 that multiple labels appear consecutively in the code. This is not a problem
 211 since the labels are resolved to real addresses later on anyway.
 212
 213 \begin{lstlisting}[label={lst:controlflow},%
 214         caption={Bytecode view for \texttt{arith} class}]
 215 freshlabel = get >>= \st=:{freshl}->put {st & freshl=freshl+1} >>| pure freshl
 216
 217 instance If ByteCode Stmt Stmt Stmt where If b t e = BCIfStmt b t e
 218 instance If ByteCode e Stmt Stmt    where If b t e = BCIfStmt b t e
 219 instance If ByteCode Stmt e Stmt    where If b t e = BCIfStmt b t e
 220 instance If ByteCode x y Stmt       where If b t e = BCIfStmt b t e
 221 instance IF ByteCode where
 222         IF b t e = BCIfStmt b t e
 223         (?) b t = BCIfStmt b t (tell` [])
 224 BCIfStmt (BC b) (BC t) (BC e) = BC (
 225         freshlabel >>= \else->freshlabel >>= \endif->
 226         b >>| tell [BCJmpF else] >>|
 227         t >>| tell [BCJmp endif, BCLab else] >>|
 228         e >>| tell [BCLab endif]
 229         )
 230
 231 instance noOp ByteCode where
 232         noOp = tell` [BCNop]
 233 \end{lstlisting}
 234
 235 The semantics for the \gls{mTask}-\glspl{Task} bytecode view are different from
 236 the semantics of the \gls{C} view. \glspl{Task} in the \gls{C} view can start
 237 new \glspl{Task} or even start themselves to continue, while in the bytecode
 238 view, \glspl{Task} run indefinitely, one-shot or on interrupt. To allow interval
 239 and interrupt \glspl{Task} to terminate, a return instruction is added. This
 240 class was not available in the original system and is thus added. It just
 241 writes a single instruction so that the interpreter knows to stop execution.
 242 Listing~\ref{lst:return} shows the classes and implementation for the return
 243 expression.
 244
 245 \begin{lstlisting}[label={lst:return},%
 246         caption={Bytecode view for the return instruction}]
 247 class retrn v where
 248   retrn :: v () Expr
 249
 250 instance retrn ByteCode where
 251         retrn = tell` [BCReturn]
 252 \end{lstlisting}
 253
 254 \subsection{Shared Data Sources \& Assignment}
 255 Fresh \gls{SDS} are generated using the state and constructing one involves
 256 multiple steps.  First, a fresh identifier is grabbed from the state.  Then a
 257 \CI{BCShare} record is created with that identifier. A \CI{BCSdsFetch}
 258 instruction is written and the body is generated to finally add the \gls{SDS}
 259 to the actual state with the value obtained from the function. The exact
 260 implementation is shown in Listing~\ref{lst:shareview}.
 261
 262 \begin{lstlisting}[label={lst:shareview},%
 263         caption={Bytecode view for \texttt{arith}}]
 264 freshshare = get >>= \st=:{freshs}->put {st & freshs=freshs+1} >>| pure freshs
 265
 266 instance sds ByteCode where
 267         sds f = {main = BC (freshshare
 268                         >>= \sdsi->pure {BCShare|sdsi=sdsi,sdsval=BCValue 0}
 269                         >>= \sds->pure (f (tell` [BCSdsFetch sds]))
 270                         >>= \(v In bdy)->modify (addSDS sds v)
 271                         >>| unBC (unMain bdy))
 272                 }
 273 instance sdspub ByteCode where
 274         pub (BC x) = BC (censor (\[BCSdsFetch s]->[BCSdsPublish s]) x)
 275
 276 addSDS sds v s = {s & sdss=[{sds & sdsval=BCValue v}:s.sdss]}
 277 \end{lstlisting}
 278
 279 All assignable types compile to a \gls{RWST} which writes the specific fetch
 280 instruction(s). For example, using an \gls{SDS} always results in an expression
 281 of the form \CI{sds \x=4 In ...}. The actual \CI{x} is the \gls{RWST} that
 282 always writes one \CI{BCSdsFetch} instruction with the correctly embedded
 283 \gls{SDS}.  Assigning to an analog pin will result in the \gls{RWST} containing
 284 the \CI{BCAnalogRead} instruction. When the operation on the assignable is not
 285 a read operation from but an assign operation, the instruction(s) will be
 286 rewritten accordingly. This results in a \CI{BCSdsStore} or \CI{BCAnalogWrite}
 287 instruction respectively. The implementation for this is given in
 288 Listing~\ref{lst:assignmentview}.
 289
 290 \begin{lstlisting}[label={lst:assignmentview},%
 291         caption={Bytecode view implementation for assignment.}]
 292 instance assign ByteCode where
 293         (=.) (BC v) (BC e) = BC (e >>| censor makeStore v)
 294
 295 makeStore [BCSdsFetch i]    = [BCSdsStore i]
 296 makeStore [BCDigitalRead i] = [BCDigitalWrite i]
 297 makeStore [...]             = [...]
 298 \end{lstlisting}
 299
 300 \subsection{Actual Compilation}
 301 All the previous functions are tied together with the \CI{toMessages} function.
 302 This function compiles the bytecode and transforms the \gls{Task} to a message.
 303 The \glspl{SDS} that were not already sent to the device are also added as
 304 messages to be sent to the device. This functionality is shown in
 305 Listing~\ref{lst:compilation}. The compilation process consists of two steps.
 306 First, the \gls{RWST} is executed. Then, the \emph{Jump} statements that
 307 jump to labels are transformed to jump to program memory addresses. The
 308 translation of labels is possible in one sweep because fresh labels are reused.
 309 Reusing labels would not give a speed improvement since the labels are removed
 310 in the end.
 311
 312 \begin{lstlisting}[label={lst:compilation},%
 313         caption={Actual compilation.}]
 314 bclength :: BC -> Int
 315 bclength (BCPush s) = 1 + size (toByteCode s)
 316 bclength ... = ...
 317 bclength x = 1 + consNum{|*|} x
 318
 319 computeGotos :: [BC] Int -> ([BC], Map Int Int)
 320 computeGotos [] _ = ([], newMap)
 321 computeGotos [BCLab l:xs] i = appSnd ('DM'.put l i) (computeGotos xs i)
 322 computeGotos [x:xs] i = appFst (\bc->[x:bc]) (computeGotos xs (i + bclength x))
 323
 324 toRealByteCode :: (ByteCode a b) BCState -> (String, BCState)
 325 toRealByteCode x s
 326 # (s, bc) = runBC x s
 327 # (bc, gtmap) = computeGotos bc 1
 328 = (concat (map (toString o toByteVal) (map (implGotos gtmap) bc)), s)
 329
 330 toMessages :: MTaskInterval (Main (ByteCode a b)) BCState -> ([MTaskMSGSend], BCState)
 331 toMessages interval x oldstate
 332 # (bc, newstate) = toRealByteCode (unMain x) oldstate
 333 # newsdss = difference newstate.sdss oldstate.sdss
 334 = ([MTSds sdsi e\\{sdsi,sdsval=e}<-newsdss] ++ [MTTask interval bc], newstate)
 335 \end{lstlisting}
 336
 337 \section{Examples}
 338 The thermostat example given previously in Listing~\ref{lst:exmtask} would be
 339 compiled to the following code. The left column indicates the
 340 position in the program memory.
 341
 342 \begin{lstlisting}[caption={Thermostat bytecode},language=c]
 343  1-2 : BCAnalogRead (Analog A0)
 344  3-6 : BCPush (Int 50)
 345  7   : BCGre
 346  8-9 : BCJmpF 17                   //Jump to else
 347 10-12: BCPush (Bool 1)
 348 13-14: BCDigitalWrite (Digital D0)
 349 15-16: BCJmp 21                    //Jump to end of if
 350 17-19: BCPush (Bool 0)             //Else label
 351 20   : BCDigitalWrite (Digital D0)
 352 \end{lstlisting}