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