X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;f=results.mtask.tex;h=c6adefb744f7d71e9b2dd47c6591be82751bc3b3;hb=36d2564cca6ffab6506198f13545e5d02cf2b5cc;hp=888b0d67a9a60ae2b5793abde8e0ef5bbd2a248f;hpb=5fef9ca5f782e58aca5c019c71db675e16138b4d;p=msc-thesis1617.git diff --git a/results.mtask.tex b/results.mtask.tex index 888b0d6..c6adefb 100644 --- a/results.mtask.tex +++ b/results.mtask.tex @@ -1,13 +1,13 @@ -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} +The \glspl{Task} suitable for a client are called \gls{mTask}-\gls{Task} 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 +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{\gls{Task} 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 executes code and launches \glspl{Task}. It was also possible @@ -25,49 +25,52 @@ reflected in the \CI{MTTask} message type. 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. + \CI{OnInterval} has the number of milliseconds to wait in between + executions as a parameter. \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. + interrupt. Unfortunatly, due to time constraints and focus, none of the + current client implementations support this. 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}} +\section{\gls{SDS} semantics} \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. +\glspl{SDS}. However, the same freedom is not given for \glspl{SDS} that +reside on the client. Not all types are suitable to be located on a client, +simply because it needs to be serializable and representable on clients. +Moreover, \glspl{SDS} behave a little different in an \gls{mTask} device +compared to in the \gls{iTasks} system. In an \gls{iTasks} system, when the +\gls{SDS} is updated, a broadcast to all watching \glspl{Task} in the system +is made to notify them of the update. \glspl{SDS} can update often and the +update might not be the final value it will get. Implementing the same +functionality on the \gls{mTask} client would result 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: +functionality. Programmers can choose to implement it for existing views 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 encapsulated in the type \CI{ByteCode}. As +\section{Bytecode compilation view}\label{sec:compiler} +The \gls{mTask}-\glspl{Task} 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 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. +that writes bytecode instructions (\CI{BC}, Subsection~\ref{sec:instruction}) +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} that are 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 @@ -113,11 +116,10 @@ instance arith ByteCode instance serial ByteCode \end{lstlisting} -\section{Implementation} -\subsection{Instruction Set} +\subsection{Instruction Set}\label{sec:instruction} The instruction set is given in Listing~\ref{bc:instr}. The instruction set is -kept large, but under $255$, to get the highest expressively while keeping all -instruction one byte. +kept large, but under $255$, to get as much expressieve power as possible while +keeping all instruction within one byte. 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. @@ -151,20 +153,21 @@ and avoid label lookups at runtime. | BCReturn \end{lstlisting} -All single byte instructions are 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 +All single byte instructions are converted automatically using a generic +function which returns the index of the constructor. The index of the +constructor is the byte value for all instructions. Added to this single byte +value are the encoded parameters of the instruction. 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, 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. +Since the \CI{ByteCode} type is just a boxed \gls{RWST}, access to the whole +range of \gls{RWST} functions is available. However, to use this, the type must +be unboxed. After application the type must be boxed again. To achieve this, +several helper functions have been created. They are given in +Listing~\ref{lst:helpers}. The \CI{op} and \CI{op2} functions is hand-crafted +to make operators that pop one or two values off the stack respectively. The +\CI{tell`} function 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 @@ -181,10 +184,10 @@ 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 using the -same strategy. +Almost all of the code from the simple classes exclusively use helper +functions. Listing~\ref{lst:arithview} shows some implementations. The +\CI{boolExpr} class 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}] @@ -200,16 +203,15 @@ instance userLed ByteCode where \subsection{Control Flow} 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. +view. The function just sequences the two \glspl{RWST}. The +implementation for the \emph{If} statement speaks for itself in +Listing~\ref{lst:controlflow}. First, all the labels are gathered after which +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}}] + caption={Bytecode view for \texttt{arith} class}] 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 @@ -225,14 +227,34 @@ BCIfStmt (BC b) (BC t) (BC e) = BC ( t >>| tell [BCJmp endif, BCLab else] >>| e >>| tell [BCLab endif] ) + instance noOp ByteCode where noOp = tell` [BCNop] \end{lstlisting} +The semantics for the \gls{mTask}-\glspl{Task} bytecode view are different from +the semantics of the \gls{C} view. \glspl{Task} in the \gls{C} view can start +new \glspl{Task} or even start themselves to continue, while in the bytecode +view, \glspl{Task} run indefinitly, one-shot or on interrupt. To allow interval +and interrupt \glspl{Task} to terminate, a return instruction is added. This +class was not available in the original system and is thus added. It just +writes a single instruction so that the interpreter knows to stop execution. +Listing~\ref{lst:return} shows the classes and implementation for the return +expression. + +\begin{lstlisting}[label={lst:return},% + caption={Bytecode view for the return instruction}] +class retrn v where + retrn :: v () Expr + +instance retrn ByteCode where + retrn = tell` [BCReturn] +\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} +Fresh \gls{SDS} are generated using 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}. @@ -254,15 +276,16 @@ instance sdspub ByteCode where 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 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. 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}. +All assignable types compile to a \gls{RWST} which writes the specific fetch +instruction(s). For example, using an \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 correctly embedded +\gls{SDS}. Assigning to an analog pin will result in the \gls{RWST} containing +the \CI{BCAnalogRead} instruction. When the operation on the assignable is not +a read operation from but an assign operation, the instruction(s) will be +rewritten accordingly. This results in a \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.}] @@ -274,17 +297,17 @@ makeStore [BCDigitalRead i] = [BCDigitalWrite i] makeStore [...] = [...] \end{lstlisting} -\section{Actual Compilation} +\subsection{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. +This function compiles the bytecode and transforms the \gls{Task} to a message. 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 +messages to be sent to the device. This functionality is shown 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 program memory addresses. The -translation of labels is possible in one sweep because no labels are reused. +translation of labels is possible in one sweep because fresh labels are reused. Reusing labels would not give a speed improvement since the labels are removed -anyway in the end. +in the end. \begin{lstlisting}[label={lst:compilation},% caption={Actual compilation.}] @@ -311,8 +334,8 @@ toMessages interval x oldstate = ([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 +\section{Examples} +The thermostat 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. @@ -327,51 +350,4 @@ position in the program memory. 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. - -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} +\todo{More elaborate example}