X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;f=results.mtask.tex;h=83cc7094edb2d7321ce1c871bb8ea864129ff334;hb=c91e99cb9e71060f461c03d1454ad5f31e9495a1;hp=8b0fb20ea551cc3b22c00efbe87392d13c2674cf;hpb=d11a7941da4024ec8ff9ef6afaebb6eb9d2c6ed4;p=msc-thesis1617.git diff --git a/results.mtask.tex b/results.mtask.tex index 8b0fb20..83cc709 100644 --- a/results.mtask.tex +++ b/results.mtask.tex @@ -1,28 +1,102 @@ -Some functionality of the original \gls{mTask}-\gls{EDSL} will not be used in -this extension \gls{EDSL}. Conversely, some functionality needed was not -available in the existing \gls{EDSL}. Due to the nature of class based shallow -embedding this obstacle is very easy to solve. A type housing the \gls{EDSL} -does not have to implement all the available classes. Moreover, classes can be -added at will without interfering with the existing views. - -\section{Bytecode compilation view} +The \glspl{Task} suitable for a client are called \glspl{mTask} and are written +in the aforementioned \gls{mTask}-\gls{EDSL}. Some functionality of the +original \gls{mTask}-\gls{EDSL} will not be used in this extension \gls{EDSL}. +Conversely, some functionality needed was not available in the existing +\gls{EDSL}. Due to the nature of class based shallow embedding this obstacle is +very easy to solve. A type --- housing the \gls{EDSL} --- does not have to +implement all the available classes. Moreover, classes can be added at will +without interfering with the existing views. + +\section{Semantics} +The current \gls{mTask} engine for devices does not support \glspl{Task} in the +sense that the \gls{C}-view does. \Glspl{Task} used with the \gls{C}-view are a +main program that runs some \glspl{Task}. \glspl{Task} in the new system are +\CI{Main} objects with a program inside that does not contain \glspl{Task} but +are a \gls{Task} as a whole. Sending a \gls{Task} always goes together with +choosing a scheduling strategy. This strategy can be one of the following three +strategies as reflected in the \CI{MTTask}. + +\begin{itemize} + \item\CI{OneShot} + + \CI{OneShot} takes no parameters and means that the \gls{Task} will run + once and will then be removed automatically. This type of scheduling + could be useful, for example, in retrieving sensor information on + request of a user. + \item\CI{OnInterval} + + \CI{OnInterval} has as a parameter the number of milliseconds to wait + in between executions. \Glspl{Task} running with this scheduling method + are executed at predetermined intervals. + \item\CI{OnInterrupt} + + The last scheduling method is running \glspl{Task} on a specific + interrupt. None of the current client implementations support this. + However, registering interrupts on, for example the \gls{Arduino} is + very straightforward. Interrupt scheduling is useful for \glspl{Task} + that have to react on a certain type of hardware event such as the + press of a button. +\end{itemize} + +\subsection{\glspl{SDS}} +\Glspl{SDS} on a client are available on the server as well. However, the same +freedom is not given on the \glspl{SDS} that reside on the client. Not all +types are suitable to be located on a client. Moreover, \glspl{SDS} behave a +little bit differently on an \gls{mTask} device than in the \gls{iTasks} +system. In an \gls{iTasks} system, when the \gls{SDS} is updated, a broadcast +to everyone in the system watching is made to notify them of an update. +\glspl{SDS} on the device can update very often and the update might not be the +final value it will get. Therefore a device must publish the \gls{SDS} +explicitly to save bandwidth. + +To add this functionality, the \CI{sds} class could be extended. However, this +would result in having to update all existing views that use the \CI{sds} +class. Therefore, an extra class is added that contains the extra +functionality. The existing views can choose to implement it in the future but +are not obliged to. The publication function has the following signature: +\begin{lstlisting}[caption={The \texttt{sdspub} class}] +class sdspub v where + pub :: (v t Upd) -> v t Expr | type t +\end{lstlisting} + +\section{Bytecode compilation}\label{sec:compiler} The \glspl{mTask} are sent to the device in bytecode and are saved in the -memory of the device. To compile the \gls{EDSL} code to bytecode a \gls{RWST} -is used. The \gls{RWST} is a state transformer stacked on a \emph{Reader} monad -and a \emph{Writer} monad. In this case the transformer part is not used. -However, this can be done to add for example better runtime error handling. +memory of the device. To compile the \gls{EDSL} code to bytecode, a view is +added to the \gls{mTask}-system encapsulated in the type \CI{ByteCode}. As +shown in Listing~\ref{lst:bcview}, the \CI{ByteCode} view is a boxed \gls{RWST} +that writes bytecode instructions (\CI{BC}) while carrying around a +\CI{BCState}. The state is kept between compilations and is unique to a device. +The state contains fresh variable names and a register of \glspl{SDS} used. -\begin{lstlisting}[language=Clean] +Types implementing the \gls{mTask} classes must have two free type variables. +Therefore the \gls{RWST} is wrapped with a constructor and two phantom type +variables are added. This means that the programmer has to unbox the +\CI{ByteCode} object to be able to use return values for the monad. Tailor made +access functions are used to achieve this with ease. The fresh variable stream +in a compiler using a \gls{RWST} is often put into the \emph{Reader} part of +the monad. However, not all code is compiled immediately and later on the fresh +variable stream cannot contain variables that were used before. Therefore this +information is put in the state which is kept between compilations. + +Not all types are suitable for usage in bytecode compiled programs. Every value +used in the bytecode view must fit in the \CI{BCValue} type which restricts +the content. Most notably, the type must be bytecode encodable. A \CI{BCValue} +must be encodable and decodable without losing type or value information. At +the moment a simple encoding scheme is used that uses a single byte prefixes to +detect which type the value is. The devices know of these prefixes and act +accordingly. + +\begin{lstlisting}[label={lst:bcview},caption={Bytecode view}] :: ByteCode a p = BC (RWS () [BC] BCState ()) :: BCValue = E.e: BCValue e & mTaskType, TC e -:: BCShare = { - sdsi :: Int, - sdsval :: BCValue +:: BCShare = + { sdsi :: Int + , sdsval :: BCValue } -:: BCState = { - freshl :: [Int], - freshs :: [Int], - sdss :: [BCShare] +:: BCState = + { freshl :: Int + , freshs :: Int + , sdss :: [BCShare] } class toByteCode a :: a -> String @@ -37,14 +111,263 @@ instance arith ByteCode instance serial ByteCode \end{lstlisting} -\section{Bytecode compilation view for \gls{mTask}} -Compilation to bytecode +\section{Implementation} +\subsection{Instruction Set} +The instruction set is given in Listing~\ref{bc:instr}. The instruction set is +kept large, but under $255$, to get the highest expressivity for the lowest +program size. -\subsection{Backend} -\todo{Aanpassingen -aan de mTask DSL} +The interpreter is a +stack machine. Therefore it needs instructions like \emph{Push} and +\emph{Pop}. The virtual instruction \CI{BCLab} is added to allow for an easy +implementation. However, this is not a real instruction and the labels are +resolved to actual addresses in the final step of compilation to save +instructions. -\section{Semantics} +\begin{lstlisting}[label={bc:instr},% + caption={Bytecode instruction set}] +:: BC = BCNop + | BCLab Int | BCPush BCValue | BCPop + //SDS functions + | BCSdsStore BCShare | BCSdsFetch BCShare | BCSdsPublish BCShare + //Unary ops + | BCNot + //Binary Int ops + | BCAdd | BCSub | BCMul + | BCDiv + //Binary Bool ops + | BCAnd | BCOr + //Binary ops + | BCEq | BCNeq | BCLes | BCGre + | BCLeq | BCGeq + //Conditionals and jumping + | BCJmp Int | BCJmpT Int | BCJmpF Int + //UserLED + | BCLedOn | BCLedOff + //Pins + | BCAnalogRead Pin | BCAnalogWrite Pin | BCDigitalRead Pin | BCDigitalWrite Pin + //Return + | BCReturn +\end{lstlisting} + +All instructions can be converted semi-automatically using the generic function +\CI{consIndex\{*\}} that gives the index of the constructor. This constructor +index is the actual byte value for the instruction. The \CI{BCValue} type +contains existentially quantified types and therefore must have a given +implementation for all generic functions. + +\subsection{Helper functions} +The \CI{ByteCode} type is just a boxed \gls{RWST} and that gives us access to +the whole range of \gls{RWST} functions. However, to apply a function the type +must be unboxed. After application the type must be boxed again. To achieve +this, several helper functions have been created. They are listed in +Listing~\ref{lst:helpers}. The \CI{op} and \CI{op2} function is crafted to make +operators that pop one or two values off the stack respectively. The \CI{tell`} +is a wrapper around the \gls{RWST} function \CI{tell} that appends the argument +to the \emph{Writer} value. + +\begin{lstlisting}[label={lst:helpers},caption={Some helper functions}] +op2 :: (ByteCode a p1) (ByteCode a p2) BC -> ByteCode b Expr +op2 (BC x) (BC y) bc = BC (x >>| y >>| tell [bc]) + +op :: (ByteCode a p) BC -> ByteCode b c +op (BC x) bc = BC (x >>| tell [bc]) + +tell` :: [BC] -> (ByteCode a p) +tell` x = BC (tell x) + +unBC :: (ByteCode a p) -> RWS () [BC] BCState () +unBC (BC x) = x +\end{lstlisting} + +\subsection{Arithmetics \& Peripherals} +Almost all of the code from the simple classes use exclusively helper +functions. Listing~\ref{lst:arithview} shows some implementations. The classes +\CI{boolExpr} and the classes for the peripherals are implemented in the same +fashion. + +\begin{lstlisting}[label={lst:arithview},caption={% + Bytecode view implementation for arithmetic and peripheral classes}] +instance arith ByteCode where + lit x = tell` [BCPush (BCValue x)] + (+.) x y = op2 x y BCDiv + ... + +instance userLed ByteCode where + ledOn l = op l BCLedOn + ledOff l = op l BCLedOff +\end{lstlisting} -\todo{Uitleggen wat het systeem precies doet} +\subsection{Control Flow} +Sequence is very straightforward in the bytecode view. The function just +sequences the two \glspl{RWST}. The \emph{If} statement requires some detailed +explanation since labels come into play. The implementation speaks for itself +in Listing~\ref{lst:controlflow}. First, all the labels are gathered and then +they are placed in the correct order in the bytecode sequence. It can happen +that multiple labels appear consecutively in the code. This is not a problem +since the labels are resolved to real addresses later on anyway. +\begin{lstlisting}[label={lst:controlflow},% + caption={Bytecode view for \texttt{arith}}] +freshlabel = get >>= \st=:{freshl}->put {st & freshl=freshl+1} >>| pure freshl + +instance If ByteCode Stmt Stmt Stmt where If b t e = BCIfStmt b t e +instance If ByteCode e Stmt Stmt where If b t e = BCIfStmt b t e +instance If ByteCode Stmt e Stmt where If b t e = BCIfStmt b t e +instance If ByteCode x y Stmt where If b t e = BCIfStmt b t e +instance IF ByteCode where + IF b t e = BCIfStmt b t e + (?) b t = BCIfStmt b t (tell` []) +BCIfStmt (BC b) (BC t) (BC e) = BC ( + freshlabel >>= \else->freshlabel >>= \endif-> + b >>| tell [BCJmpF else] >>| + t >>| tell [BCJmp endif, BCLab else] >>| + e >>| tell [BCLab endif] + ) +instance noOp ByteCode where + noOp = tell` [BCNop] +\end{lstlisting} + +\subsection{Shared Data Sources \& Assignment} +Shared data sources must be acquired from the state and constructing one +involves multiple steps. First, a fresh identifier is grabbed from the state. +Then a \CI{BCShare} record is created with that identifier. A \CI{BCSdsFetch} +instruction is written and the body is generated to finally add the \gls{SDS} to +the actual state with the value obtained from the function. The exact +implementation is shown in Listing~\ref{lst:shareview}. + +\begin{lstlisting}[label={lst:shareview},% + caption={Bytecode view for \texttt{arith}}] +freshshare = get >>= \st=:{freshs}->put {st & freshs=freshs+1} >>| pure freshs + +instance sds ByteCode where + sds f = {main = BC (freshshare + >>= \sdsi->pure {BCShare | sdsi=sdsi,sdsval=BCValue 0} + >>= \sds->pure (f (tell` [BCSdsFetch sds])) + >>= \(v In bdy)->modify (addSDS sds v) + >>| unBC (unMain bdy)) + } +instance sdspub ByteCode where + pub (BC x) = BC (censor (\[BCSdsFetch s]->[BCSdsPublish s]) x) + +addSDS sds v s = {s & sdss=[{sds & sdsval=BCValue v}:s.sdss]} +\end{lstlisting} + +All assignable types compile to a \gls{RWST} that writes one instruction. For +example, using a \gls{SDS} always results in an expression of the form +\CI{sds \x=4 In ...}. The actual \CI{x} is the \gls{RWST} that always writes +one \CI{BCSdsFetch} instruction with the correct \gls{SDS} embedded. When the +call of the \CI{x} is not a read but an assignment, the instruction will be +rewritten as a \CI{BCSdsStore}. The implementation for this is given in +Listing~\ref{lst:assignmentview}. + +\begin{lstlisting}[label={lst:assignmentview},% + caption={Bytecode view implementation for assignment.}] +instance assign ByteCode where + (=.) (BC v) (BC e) = BC (e >>| censor makeStore v) + +makeStore [BCSdsFetch i] = [BCSdsStore i] +makeStore [BCDigitalRead i] = [BCDigitalWrite i] +makeStore [...] = [...] +\end{lstlisting} + +\section{Actual Compilation} +All the previous functions are tied together with the \CI{toMessages} function. +This function compiles the bytecode and transforms the \gls{Task} in a message. +The \glspl{SDS} that were not already sent to the device are also placed in +messages to be sent to the device. This functionality is listed in +Listing~\ref{lst:compilation}. The compilation process consists of two steps. +First, the \gls{RWST} is executed. Then the \emph{Jump} statements that +jump to labels are transformed to jump to addresses. The translation of labels +is possible in one sweep because no labels are reused. Reusing labels would not +give a speed improvement since the labels are removed anyway in the end. + +\begin{lstlisting}[label={lst:compilation},% + caption={Actual compilation.}] +bclength :: BC -> Int +bclength (BCPush s) = 1 + size (toByteCode s) +bclength ... = ... +bclength x = 1 + consNum{|*|} x + +computeGotos :: [BC] Int -> ([BC], Map Int Int) +computeGotos [] _ = ([], newMap) +computeGotos [BCLab l:xs] i = appSnd ('DM'.put l i) (computeGotos xs i) +computeGotos [x:xs] i = appFst (\bc->[x:bc]) (computeGotos xs (i + bclength x)) + +toRealByteCode :: (ByteCode a b) BCState -> (String, BCState) +toRealByteCode x s +# (s, bc) = runBC x s +# (bc, gtmap) = computeGotos bc 1 += (concat (map (toString o toByteVal) (map (implGotos gtmap) bc)), s) + +toMessages :: MTaskInterval (Main (ByteCode a b)) BCState -> ([MTaskMSGSend], BCState) +toMessages interval x oldstate +# (bc, newstate) = toRealByteCode (unMain x) oldstate +# newsdss = difference newstate.sdss oldstate.sdss += ([MTSds sdsi e\\{sdsi,sdsval=e}<-newsdss] ++ [MTTask interval bc], newstate) +\end{lstlisting} + +\section{Example} +The heating example given previously in Listing~\ref{lst:exmtask} would be +compiled to the following code. The left column indicates the +position in the program memory. + +\begin{lstlisting}[caption={Thermostat bytecode},language=c] + 1-2 : BCAnalogRead (Analog A0) + 3-6 : BCPush (Int 50) + 7 : BCGre + 8-9 : BCJmpF 17 //Jump to else +10-12: BCPush (Bool 1) +13-14: BCDigitalWrite (Digital D0) +15-16: BCJmp 21 //Jump to end of if +17-19: BCPush (Bool 0) //Else label +20 : BCDigitalWrite (Digital D0) +\end{lstlisting} + +\section{Interpreter} +The client contains an interpreter to execute a \gls{Task}'s bytecode. + +First some preparatory work is done. The stack will be initialized and the +program counter and stack pointer are set to zero and the bottom respectively. +Then the interpreter executes one step at the time while the program counter is +smaller than the program length. The code for this is listed in +Listing~\ref{lst:interpr}. One execution step is basically a big switch +statement going over all possible bytecode instructions. Some instructions are +detailed upon in the listing. The \CI{BCPush} instruction is a little more +complicated in real life because some decoding will take place as not all +\CI{BCValue}'s are of the same length. + +\begin{lstlisting}[language=C,label={lst:interpr},% + caption={Rough code outline for interpretation}] +#define f16(p) program[pc]*265+program[pc+1] + +void run_task(struct task *t){ + uint8_t *program = t->bc; + int plen = t->tasklength; + int pc = 0; + int sp = 0; + while(pc < plen){ + switch(program[pc++]){ + case BCNOP: + break; + case BCPUSH: + stack[sp++] = pc++ //Simplified + break; + case BCPOP: + sp--; + break; + case BCSDSSTORE: + sds_store(f16(pc), stack[--sp]); + pc+=2; + break; + // ... + case BCADD: trace("add"); + stack[sp-2] = stack[sp-2] + stack[sp-1]; + sp -= 1; + break; + // ... + case BCJMPT: trace("jmpt to %d", program[pc]); + pc = stack[--sp] ? program[pc]-1 : pc+1; + break; +} +\end{lstlisting}