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