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 a Expr
 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 \begin{lstlisting}[label={lst:controlflow},%
 152         caption={Bytecode view for \texttt{arith}}]
 153 instance noOp ByteCode where
 154         noOp = tell` [BCNop]
 155 \end{lstlisting}
 156
 157 \subsection{Shared Data Sources \& Assignment}
 158 Shared data sources must be acquired from the state and constructing one
 159 happens via multiple steps. First a fresh identifier is grabbed from the state.
 160 Then a \CI{BCShare} record is created with that identifier. A \CI{BCSdsFetch}
 161 instruction is written and the body is generated to finally add the share to
 162 the actual state with the value obtained from the function. The exact
 163 implementation is shown in Listing~\ref{lst:shareview}.
 164
 165 \begin{lstlisting}[label={lst:shareview},%
 166         caption={Bytecode view for \texttt{arith}}]
 167 instance sds ByteCode where
 168         sds f = {main = BC (freshs
 169                         >>= \sdsi->pure {BCShare | sdsi=sdsi,sdsval=BCValue 0}
 170                         >>= \sds->pure (f (tell` [BCSdsFetch sds]))
 171                         >>= \(v In bdy)->modify (addSDS sds v)
 172                         >>| unBC (unMain bdy))
 173                 }
 174         pub (BC x) = BC (censor (\[BCSdsFetch s]->[BCSdsPublish s]) x)
 175
 176 addSDS sds v s = {s & sdss=[{sds & sdsval=BCValue v}:s.sdss]}
 177 \end{lstlisting}
 178
 179 All assignable types compile to an \gls{RWST} that writes one instruction. For
 180 example, using an \gls{SDS} always results in an expression of the form
 181 \CI{sds \x=4 In ...}. The actual \CI{x} is the \gls{RWST} that always writes
 182 one \CI{BCSdsFetch} instruction with the correct \gls{SDS} embedded. When the
 183 call of the \CI{x} is not a read but an assignment,  the instruction will be
 184 rewritten as a \CI{BCSdsStore}. The implementation for this is given in
 185 Listing~\ref{lst:assignmentview}.
 186
 187 \begin{lstlisting}[label={lst:assignmentview},%
 188         caption={Bytecode view implementation for assignment.}]
 189 instance assign ByteCode where
 190         (=.) (BC v) (BC e) = BC (e >>| censor makeStore v)
 191
 192 makeStore [BCSdsFetch i]    = [BCSdsStore i]
 193 makeStore [BCDigitalRead i] = [BCDigitalWrite i]
 194 makeStore [...]             = [...]
 195 \end{lstlisting}
 196
 197 \section{Actual Compilation}
 198 \todo{hulp functies voor compileren}