X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;f=results.mtask.tex;h=20a51f1702c6d9ab8d065109e74517d343d0ab3a;hb=b8e0188d0d4b4f321259e036807b439c85753828;hp=c32f7acf318e05ad9d6a03f3404b136458d6b089;hpb=9662cccfffecb70d621318b5f3a35e46b6029f3c;p=msc-thesis1617.git diff --git a/results.mtask.tex b/results.mtask.tex index c32f7ac..20a51f1 100644 --- a/results.mtask.tex +++ b/results.mtask.tex @@ -1,54 +1,92 @@ -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. +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 system. 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} -\subsection{\glspl{mTask}} The current \gls{mTask} engine for devices does not support \glspl{Task} in the -sense that the \gls{C}-view it does. \glspl{Task} in the new system are are -\CI{Main} objects with a program inside. A \gls{Task} runs periodically, on -interrupt or one-shot. -\todo{elaborate} +sense that the \gls{C}-view does. \Glspl{Task} used with the \gls{C}-view are a +main program that executes code and launches \glspl{Task}. It was also possible +to just have a main program. The current \gls{mTask}-system only supports main +programs. 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} message type. + +\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} 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. This means that an extra function is -added to the \CI{sds} class that adds the \CI{pub} function. -\todo{elaborate} +\Glspl{SDS} on a client are available on the server as well as regular +\gls{SDS}. 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 different on an \gls{mTask} device +compared to 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 the update. \glspl{SDS} can update very often and the +update might not be the final value it will get. This results in a lot of +expensive unneeded bandwidth usage. 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 view is -added to the \gls{mTask}-system called \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 devices and contains fresh variable names and a -register of shares used. +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. 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 an \gls{RWST} is often put in to the \emph{Reader} part of -the monad. However, not all code is compiled immediately and later on the fresh -variable stream can not contain variables that were used before. Therefore this -information is put in the state which is kept between compilations. +\CI{ByteCode} object to be able to make use of the \gls{RWST} functionality +such as return values. 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} +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. +the moment a simple encoding scheme is used that uses single byte prefixes to +detect the type of the value. The devices know these prefixes and can apply the +same detection if necessary. \begin{lstlisting}[label={lst:bcview},caption={Bytecode view}] :: ByteCode a p = BC (RWS () [BC] BCState ()) @@ -58,8 +96,8 @@ accordingly. , sdsval :: BCValue } :: BCState = - { freshl :: [Int] - , freshs :: [Int] + { freshl :: Int + , freshs :: Int , sdss :: [BCShare] } @@ -78,15 +116,14 @@ instance serial 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. +kept large, but under $255$, to get the highest expressively while keeping all +instruction one byte. -The interpreter is a -stack machine. Therefore the 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. +The interpreter running in the client is a stack machine. The virtual +instruction \CI{BCLab} is added to allow for an easy implementation of jumping. +However, this is not a real instruction and the labels are resolved to actual +program memory addresses in the final step of compilation to save instructions +and avoid label lookups at runtime. \begin{lstlisting}[label={bc:instr},% caption={Bytecode instruction set}] @@ -114,17 +151,16 @@ instructions. | BCReturn \end{lstlisting} -All instructions are 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. +All single byte instructions can be converted automatically using the generic +function \CI{consIndex} which returns the index of the constructor. The index +of the constructor is the byte value for all instructions. The last step of the +compilation is transforming the list of bytecode instructions to actual bytes. \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 some helper functions have been created. They are listed in +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 @@ -147,8 +183,8 @@ unBC (BC x) = x \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. +\CI{boolExpr} and the classes for the peripherals are implemented using the +same strategy. \begin{lstlisting}[label={lst:arithview},caption={% Bytecode view implementation for arithmetic and peripheral classes}] @@ -163,17 +199,18 @@ instance userLed ByteCode where \end{lstlisting} \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 in to 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 anyways. +Implementing the sequence operator 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=[fr:frs]}->put {st & freshl=frs} >>| pure fr +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 @@ -194,35 +231,38 @@ instance noOp ByteCode where \subsection{Shared Data Sources \& Assignment} Shared data sources must be acquired from the state and constructing one -happens via multiple steps. First a fresh identifier is grabbed from the state. +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 share to -the actual state with the value obtained from the function. The exact +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=:{freshl=[fr:frs]}->put {st & freshl=frs} >>| pure fr +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} + >>= \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 an \gls{RWST} that writes one instruction. For -example, using an \gls{SDS} always results in an expression of the form +All assignable types compile to a \gls{RWST} that writes one fetch 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}. +one \CI{BCSdsFetch} instruction with the correct \gls{SDS} embedded. Assigning +to an analog pin will result in the \gls{RWST} containing the \CI{BCAnalogRead} +instruction. When the assignable is not a read from but assigned to, the +instruction will be rewritten as a store instruction. Resulting in an +\CI{BCSdsStore} or \CI{BCAnalogWrite} instruction respectively. The +implementation for this is given in Listing~\ref{lst:assignmentview}. \begin{lstlisting}[label={lst:assignmentview},% caption={Bytecode view implementation for assignment.}] @@ -237,13 +277,14 @@ makeStore [...] = [...] \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 +The \glspl{SDS} that were not already sent to the device are also added as 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, secondly 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 anyways in the end. +First, the \gls{RWST} is executed. Then, the \emph{Jump} statements that +jump to labels are transformed to jump to program memory 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.}] @@ -287,4 +328,50 @@ position in the program memory. 20 : BCDigitalWrite (Digital D0) \end{lstlisting} -\todo{add more elaborate example?} +\section{Interpreter} +The client contains an interpreter to execute a \gls{Task}'s bytecode. + +Before execution 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}