add return
[msc-thesis1617.git] / results.mtask.tex
1 The \glspl{Task} suitable for a client are called \glspl{mTask} and are written
2 in the aforementioned \gls{mTask}-\gls{EDSL}. Some functionality of the
3 original \gls{mTask}-\gls{EDSL} will not be used in this system. Conversely,
4 some functionality needed was not available in the existing \gls{EDSL}. Due to
5 the nature of class based shallow embedding this obstacle is very easy to
6 solve. A type --- housing the \gls{EDSL} --- does not have to implement all the
7 available classes. Moreover, classes can be added at will without interfering
8 with the existing views.
9
10 \section{\gls{Task} Semantics}
11 The current \gls{mTask} engine for devices does not support \glspl{Task} in the
12 sense that the \gls{C}-view does. \Glspl{Task} used with the \gls{C}-view are a
13 main program that executes code and launches \glspl{Task}. It was also possible
14 to just have a main program. The current \gls{mTask}-system only supports main
15 programs. Sending a \gls{Task} always goes together with choosing a scheduling
16 strategy. This strategy can be one of the following three strategies as
17 reflected in the \CI{MTTask} message type.
18
19 \begin{itemize}
20 \item\CI{OneShot}
21
22 \CI{OneShot} takes no parameters and means that the \gls{Task} will run
23 once and will then be removed automatically. This type of scheduling
24 could be useful, for example, in retrieving sensor information on
25 request of a user.
26 \item\CI{OnInterval}
27
28 \CI{OnInterval} has as a parameter the number of milliseconds to wait
29 in between executions. \Glspl{Task} running with this scheduling method
30 are executed at predetermined intervals.
31 \item\CI{OnInterrupt}
32
33 The last scheduling method is running \glspl{Task} on a specific
34 interrupt. None of the current client implementations support this.
35 However, registering interrupts on, for example the \gls{Arduino} is
36 very straightforward. Interrupt scheduling is useful for \glspl{Task}
37 that have to react on a certain type of hardware event such as the
38 press of a button.
39 \end{itemize}
40
41 \section{\gls{SDS} semantics}
42 \Glspl{SDS} on a client are available on the server as well as regular
43 \gls{SDS}. However, the same freedom is not given on the \glspl{SDS} that
44 reside on the client. Not all types are suitable to be located on a client.
45 Moreover, \glspl{SDS} behave a little different on an \gls{mTask} device
46 compared to the \gls{iTasks} system. In an \gls{iTasks} system, when the \gls{SDS}
47 is updated, a broadcast to everyone in the system watching is made to notify
48 them of the update. \glspl{SDS} can update very often and the
49 update might not be the final value it will get. This results in a lot of
50 expensive unneeded bandwidth usage. Therefore a device must publish the
51 \gls{SDS} explicitly to save bandwidth.
52
53 To add this functionality, the \CI{sds} class could be extended. However, this
54 would result in having to update all existing views that use the \CI{sds}
55 class. Therefore, an extra class is added that contains the extra
56 functionality. The existing views can choose to implement it in the future but
57 are not obliged to. The publication function has the following signature:
58 \begin{lstlisting}[caption={The \texttt{sdspub} class}]
59 class sdspub v where
60 pub :: (v t Upd) -> v t Expr | type t
61 \end{lstlisting}
62
63 \section{Bytecode compilation view}\label{sec:compiler}
64 The \glspl{mTask} are sent to the device in bytecode and are saved in the
65 memory of the device. To compile the \gls{EDSL} code to bytecode, a view is
66 added to the \gls{mTask}-system encapsulated in the type \CI{ByteCode}. As
67 shown in Listing~\ref{lst:bcview}, the \CI{ByteCode} view is a boxed \gls{RWST}
68 that writes bytecode instructions (\CI{BC}) while carrying around a
69 \CI{BCState}. The state is kept between compilations and is unique to a device.
70 The state contains fresh variable names and a register of \glspl{SDS} used.
71
72 Types implementing the \gls{mTask} classes must have two free type variables.
73 Therefore the \gls{RWST} is wrapped with a constructor and two phantom type
74 variables are added. This means that the programmer has to unbox the
75 \CI{ByteCode} object to be able to make use of the \gls{RWST} functionality
76 such as return values. Tailor made access functions are used to achieve this
77 with ease. The fresh variable stream in a compiler using a \gls{RWST} is often
78 put into the \emph{Reader} part of the monad. However, not all code is compiled
79 immediately and later on the fresh variable stream cannot contain variables
80 that were used before. Therefore this information is put in the state which is
81 kept between compilations.
82
83 Not all types are suitable for usage in bytecode compiled programs. Every value
84 used in the bytecode view must fit in the \CI{BCValue} type which restricts
85 the content. Most notably, the type must be bytecode encodable. A \CI{BCValue}
86 must be encodable and decodable without losing type or value information. At
87 the moment a simple encoding scheme is used that uses single byte prefixes to
88 detect the type of the value. The devices know these prefixes and can apply the
89 same detection if necessary.
90
91 \begin{lstlisting}[label={lst:bcview},caption={Bytecode view}]
92 :: ByteCode a p = BC (RWS () [BC] BCState ())
93 :: BCValue = E.e: BCValue e & mTaskType, TC e
94 :: BCShare =
95 { sdsi :: Int
96 , sdsval :: BCValue
97 }
98 :: BCState =
99 { freshl :: Int
100 , freshs :: Int
101 , sdss :: [BCShare]
102 }
103
104 class toByteCode a :: a -> String
105 class fromByteCode a :: String -> a
106 class mTaskType a | toByteCode, fromByteCode, iTask, TC a
107
108 instance toByteCode Int, ... , UserLED, BCValue
109 instance fromByteCode Int, ... , UserLED, BCValue
110
111 instance arith ByteCode
112 ...
113 instance serial ByteCode
114 \end{lstlisting}
115
116 \subsection{Instruction Set}
117 The instruction set is given in Listing~\ref{bc:instr}. The instruction set is
118 kept large, but under $255$, to get the highest expressively while keeping all
119 instruction one byte.
120
121 The interpreter running in the client is a stack machine. The virtual
122 instruction \CI{BCLab} is added to allow for an easy implementation of jumping.
123 However, this is not a real instruction and the labels are resolved to actual
124 program memory addresses in the final step of compilation to save instructions
125 and avoid label lookups at runtime.
126
127 \begin{lstlisting}[label={bc:instr},%
128 caption={Bytecode instruction set}]
129 :: BC = BCNop
130 | BCLab Int | BCPush BCValue | BCPop
131 //SDS functions
132 | BCSdsStore BCShare | BCSdsFetch BCShare | BCSdsPublish BCShare
133 //Unary ops
134 | BCNot
135 //Binary Int ops
136 | BCAdd | BCSub | BCMul
137 | BCDiv
138 //Binary Bool ops
139 | BCAnd | BCOr
140 //Binary ops
141 | BCEq | BCNeq | BCLes | BCGre
142 | BCLeq | BCGeq
143 //Conditionals and jumping
144 | BCJmp Int | BCJmpT Int | BCJmpF Int
145 //UserLED
146 | BCLedOn | BCLedOff
147 //Pins
148 | BCAnalogRead Pin | BCAnalogWrite Pin | BCDigitalRead Pin | BCDigitalWrite Pin
149 //Return
150 | BCReturn
151 \end{lstlisting}
152
153 All single byte instructions are converted automatically using the generic
154 function \CI{consIndex} which returns the index of the constructor. The index
155 of the constructor is the byte value for all instructions. The last step of the
156 compilation is transforming the list of bytecode instructions to actual bytes.
157
158 \subsection{Helper functions}
159 The \CI{ByteCode} type is just a boxed \gls{RWST} and that gives us access to
160 the whole range of \gls{RWST} functions. However, to apply a function the type
161 must be unboxed. After application the type must be boxed again. To achieve
162 this, several helper functions have been created. They are listed in
163 Listing~\ref{lst:helpers}. The \CI{op} and \CI{op2} function is crafted to make
164 operators that pop one or two values off the stack respectively. The \CI{tell`}
165 is a wrapper around the \gls{RWST} function \CI{tell} that appends the argument
166 to the \emph{Writer} value.
167
168 \begin{lstlisting}[label={lst:helpers},caption={Some helper functions}]
169 op2 :: (ByteCode a p1) (ByteCode a p2) BC -> ByteCode b Expr
170 op2 (BC x) (BC y) bc = BC (x >>| y >>| tell [bc])
171
172 op :: (ByteCode a p) BC -> ByteCode b c
173 op (BC x) bc = BC (x >>| tell [bc])
174
175 tell` :: [BC] -> (ByteCode a p)
176 tell` x = BC (tell x)
177
178 unBC :: (ByteCode a p) -> RWS () [BC] BCState ()
179 unBC (BC x) = x
180 \end{lstlisting}
181
182 \subsection{Arithmetics \& Peripherals}
183 Almost all of the code from the simple classes use exclusively helper
184 functions. Listing~\ref{lst:arithview} shows some implementations. The classes
185 \CI{boolExpr} and the classes for the peripherals are implemented using the
186 same strategy.
187
188 \begin{lstlisting}[label={lst:arithview},caption={%
189 Bytecode view implementation for arithmetic and peripheral classes}]
190 instance arith ByteCode where
191 lit x = tell` [BCPush (BCValue x)]
192 (+.) x y = op2 x y BCDiv
193 ...
194
195 instance userLed ByteCode where
196 ledOn l = op l BCLedOn
197 ledOff l = op l BCLedOff
198 \end{lstlisting}
199
200 \subsection{Control Flow}
201 Implementing the sequence operator is very straightforward in the bytecode
202 view. The function just sequences the two \glspl{RWST}. The \emph{If} statement
203 requires some detailed explanation since labels come into play. The
204 implementation speaks for itself in Listing~\ref{lst:controlflow}. First, all
205 the labels are gathered and then they are placed in the correct order in the
206 bytecode sequence. It can happen that multiple labels appear consecutively in
207 the code. This is not a problem since the labels are resolved to real addresses
208 later on anyway.
209
210 \begin{lstlisting}[label={lst:controlflow},%
211 caption={Bytecode view for \texttt{arith}}]
212 freshlabel = get >>= \st=:{freshl}->put {st & freshl=freshl+1} >>| pure freshl
213
214 instance If ByteCode Stmt Stmt Stmt where If b t e = BCIfStmt b t e
215 instance If ByteCode e Stmt Stmt where If b t e = BCIfStmt b t e
216 instance If ByteCode Stmt e Stmt where If b t e = BCIfStmt b t e
217 instance If ByteCode x y Stmt where If b t e = BCIfStmt b t e
218 instance IF ByteCode where
219 IF b t e = BCIfStmt b t e
220 (?) b t = BCIfStmt b t (tell` [])
221 BCIfStmt (BC b) (BC t) (BC e) = BC (
222 freshlabel >>= \else->freshlabel >>= \endif->
223 b >>| tell [BCJmpF else] >>|
224 t >>| tell [BCJmp endif, BCLab else] >>|
225 e >>| tell [BCLab endif]
226 )
227
228 instance noOp ByteCode where
229 noOp = tell` [BCNop]
230 \end{lstlisting}
231
232 The semantics for the \glspl{mTask} bytecode view are different than the
233 semantics for the \gls{C} view. \glspl{Task} in the \gls{C} view can start new
234 \gls{Task} or themselves to continue, while in the bytecode view, \gls{Task}
235 run idefinitly, one-shot or on interrupt. To allow interval and interrupt
236 \glspl{Task} to terminate, a return instruction is added. This class was not
237 available in the original system and is thus added. It just writes a single
238 instruction so that the interpreter knows to stop execution.
239 Listing~\ref{lst:return} shows the classes and implementation for the return
240 expression.
241
242 \begin{lstlisting}[label={lst:return},%
243 caption={Bytecode view for the return instruction}]
244 class retrn v where
245 retrn :: v () Expr
246
247 instance retrn ByteCode where
248 retrn = tell` [BCReturn]
249 \end{lstlisting}
250
251 \subsection{Shared Data Sources \& Assignment}
252 Shared data sources must be acquired from the state and constructing one
253 involves multiple steps. First, a fresh identifier is grabbed from the state.
254 Then a \CI{BCShare} record is created with that identifier. A \CI{BCSdsFetch}
255 instruction is written and the body is generated to finally add the \gls{SDS}
256 to the actual state with the value obtained from the function. The exact
257 implementation is shown in Listing~\ref{lst:shareview}.
258
259 \begin{lstlisting}[label={lst:shareview},%
260 caption={Bytecode view for \texttt{arith}}]
261 freshshare = get >>= \st=:{freshs}->put {st & freshs=freshs+1} >>| pure freshs
262
263 instance sds ByteCode where
264 sds f = {main = BC (freshshare
265 >>= \sdsi->pure {BCShare|sdsi=sdsi,sdsval=BCValue 0}
266 >>= \sds->pure (f (tell` [BCSdsFetch sds]))
267 >>= \(v In bdy)->modify (addSDS sds v)
268 >>| unBC (unMain bdy))
269 }
270 instance sdspub ByteCode where
271 pub (BC x) = BC (censor (\[BCSdsFetch s]->[BCSdsPublish s]) x)
272
273 addSDS sds v s = {s & sdss=[{sds & sdsval=BCValue v}:s.sdss]}
274 \end{lstlisting}
275
276 All assignable types compile to a \gls{RWST} that writes one fetch instruction.
277 For example, using a \gls{SDS} always results in an expression of the form
278 \CI{sds \x=4 In ...}. The actual \CI{x} is the \gls{RWST} that always writes
279 one \CI{BCSdsFetch} instruction with the correct \gls{SDS} embedded. Assigning
280 to an analog pin will result in the \gls{RWST} containing the \CI{BCAnalogRead}
281 instruction. When the assignable is not a read from but assigned to, the
282 instruction will be rewritten as a store instruction. Resulting in an
283 \CI{BCSdsStore} or \CI{BCAnalogWrite} instruction respectively. The
284 implementation for this is given in Listing~\ref{lst:assignmentview}.
285
286 \begin{lstlisting}[label={lst:assignmentview},%
287 caption={Bytecode view implementation for assignment.}]
288 instance assign ByteCode where
289 (=.) (BC v) (BC e) = BC (e >>| censor makeStore v)
290
291 makeStore [BCSdsFetch i] = [BCSdsStore i]
292 makeStore [BCDigitalRead i] = [BCDigitalWrite i]
293 makeStore [...] = [...]
294 \end{lstlisting}
295
296 \subsection{Actual Compilation}
297 All the previous functions are tied together with the \CI{toMessages} function.
298 This function compiles the bytecode and transforms the \gls{Task} in a message.
299 The \glspl{SDS} that were not already sent to the device are also added as
300 messages to be sent to the device. This functionality is listed in
301 Listing~\ref{lst:compilation}. The compilation process consists of two steps.
302 First, the \gls{RWST} is executed. Then, the \emph{Jump} statements that
303 jump to labels are transformed to jump to program memory addresses. The
304 translation of labels is possible in one sweep because no labels are reused.
305 Reusing labels would not give a speed improvement since the labels are removed
306 anyway in the end.
307
308 \begin{lstlisting}[label={lst:compilation},%
309 caption={Actual compilation.}]
310 bclength :: BC -> Int
311 bclength (BCPush s) = 1 + size (toByteCode s)
312 bclength ... = ...
313 bclength x = 1 + consNum{|*|} x
314
315 computeGotos :: [BC] Int -> ([BC], Map Int Int)
316 computeGotos [] _ = ([], newMap)
317 computeGotos [BCLab l:xs] i = appSnd ('DM'.put l i) (computeGotos xs i)
318 computeGotos [x:xs] i = appFst (\bc->[x:bc]) (computeGotos xs (i + bclength x))
319
320 toRealByteCode :: (ByteCode a b) BCState -> (String, BCState)
321 toRealByteCode x s
322 # (s, bc) = runBC x s
323 # (bc, gtmap) = computeGotos bc 1
324 = (concat (map (toString o toByteVal) (map (implGotos gtmap) bc)), s)
325
326 toMessages :: MTaskInterval (Main (ByteCode a b)) BCState -> ([MTaskMSGSend], BCState)
327 toMessages interval x oldstate
328 # (bc, newstate) = toRealByteCode (unMain x) oldstate
329 # newsdss = difference newstate.sdss oldstate.sdss
330 = ([MTSds sdsi e\\{sdsi,sdsval=e}<-newsdss] ++ [MTTask interval bc], newstate)
331 \end{lstlisting}
332
333 \section{Examples}
334 The heating example given previously in Listing~\ref{lst:exmtask} would be
335 compiled to the following code. The left column indicates the
336 position in the program memory.
337
338 \begin{lstlisting}[caption={Thermostat bytecode},language=c]
339 1-2 : BCAnalogRead (Analog A0)
340 3-6 : BCPush (Int 50)
341 7 : BCGre
342 8-9 : BCJmpF 17 //Jump to else
343 10-12: BCPush (Bool 1)
344 13-14: BCDigitalWrite (Digital D0)
345 15-16: BCJmp 21 //Jump to end of if
346 17-19: BCPush (Bool 0) //Else label
347 20 : BCDigitalWrite (Digital D0)
348 \end{lstlisting}
349 \todo{More elaborate example}