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