X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;f=results.mtask.tex;h=c6adefb744f7d71e9b2dd47c6591be82751bc3b3;hb=36d2564cca6ffab6506198f13545e5d02cf2b5cc;hp=18c5a06304bc401fd8a115483553510a2a03ccbe;hpb=c1a2d537de7ff3d730d26658daa822b2f03ea110;p=msc-thesis1617.git

diff --git a/results.mtask.tex b/results.mtask.tex
index 18c5a06..c6adefb 100644
--- a/results.mtask.tex
+++ b/results.mtask.tex
@@ -1,67 +1,353 @@
-\section{mTask}
-\subsection{\gls{EDSL}}
-%The \gls{mTask}-\gls{EDSL} contains several classes that need to be implemented
-%by a type for it to be an \gls{mTask}. For numeric and boolean arithmetic the
-%classes \texttt{arith} and \texttt{boolExpr} are available and listed in a
-%shortened version in Listing~\ref{lst:arithbool}. All classes are to be
-%implemented by types of kind \texttt{*->*->*} a type \texttt{v t p},
-%respectively a view with a type and the role.
-%
-%\texttt{lit} lifts a constant to the \gls{mTask} domain. For a type to be a
-%valid \gls{mTask} type it needs to implement the \texttt{mTaskType} class. The
-%binary operators work as expected.
-
-\begin{lstlisting}[language=Clean,label={lst:arithbool},
-	caption={Basic classes for expressions}]
+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
+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 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. 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}
+
+\section{\gls{SDS} semantics}
+\Glspl{SDS} on a client are available on the server as well as regular
+\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. 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 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}, 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
+variables are added. This means that the programmer has to unbox the
+\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}
+must be encodable and decodable without losing type or value information. At
+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 ())
+:: BCValue = E.e: BCValue e & mTaskType, TC e
+:: BCShare =
+	{ sdsi :: Int
+	, sdsval :: BCValue
+	}
+:: BCState = 
+	{ freshl :: Int
+	, freshs :: Int
+	, sdss :: [BCShare]
+	}
+
+class toByteCode a :: a -> String
+class fromByteCode a :: String -> a
 class mTaskType a | toByteCode, fromByteCode, iTask, TC a
 
-class arith v where
-  lit :: t -> v t Expr | mTaskType t
-  (+.) infixl 6 :: (v t p) (v t q) -> v t Expr | type, +, zero t & isExpr p & isExpr q
-  ...
-class boolExpr v where
-  (&.) infixr 3 :: (v Bool p) (v Bool q) -> v Bool Expr | isExpr p & isExpr q
-  Not           :: (v Bool p) -> v Bool Expr | isExpr p
-  ...
-  (==.) infix 4 :: (v a p) (v a q) -> v Bool Expr | ==, toCode a & isExpr p & isExpr q
+instance toByteCode Int, ... , UserLED, BCValue
+instance fromByteCode Int, ... , UserLED, BCValue
+
+instance arith ByteCode
+...
+instance serial ByteCode
+\end{lstlisting}
+
+\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 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.
+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}]
+:: 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 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}
+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
+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 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}]
+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}
+
+\subsection{Control Flow}
+Implementing the sequence operator is very straightforward in the bytecode
+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} 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
+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}
+
+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}
+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}.
+
+\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} 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.}]
+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}
+
+\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} 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 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 fresh labels are reused.
+Reusing labels would not give a speed improvement since the labels are removed
+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{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.
+
+\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}
-%
-%
-%\subsection{Tasks}
-%
-%\subsection{Shares}
-%Shares can live on multiple clients at the same time. For every share created
-%for an \gls{mTask} a real \gls{SDS} is created that mirrors the value on the
-%client. All shares currently in use are stored in a system-wide \gls{SDS} in
-%such a way that the actual share can be retrieved at any moment. All shares
-%have a unique numeric identifier and an initial value.
-%
-%\begin{lstlisting}[language=Clean,label={lst:sharespec}, caption={\acrlong{SDS}}]
-%:: BCValue = E.e: BCValue e & mTaskType e
-%:: MTaskShareType = MTaskWithShare String | MTaskLens String
-%:: MTaskShare =
-%	{withTask :: [String]
-%	,withDevice :: [String]
-%	,identifier :: Int
-%	,realShare :: MTaskShareType
-%	,value :: BCValue
-%	}
-%
-%sdsStore :: Shared [MTaskShare]
-%\end{lstlisting}
-%\todo{Do something with the sharetype}
-%
-%\subsection{Communication}
-%%\todo{Handshake, device specification sending, spec.c}
-%%\todo{mTaskDevice class interface}
-%
-%\section{mTasks}
-%\subsection{\gls{EDSL}}
-%\todo{Show the classes}
-%
-%\subsection{Shares}
-%\todo{Show the types and why}
-%
-%Shares are used to store the values 
-%
-%Shares all have
+\todo{More elaborate example}