mtaskext.bytecode.tex

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