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

diff --git a/results.mtask.tex b/results.mtask.tex
index 18c5a06..9580dec 100644
--- a/results.mtask.tex
+++ b/results.mtask.tex
@@ -1,67 +1,197 @@
-\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}]
+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}
+\todo{semantics}
+
+\section{Bytecode compilation}
+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.
+
+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.
+
+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
+	}
+:: 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{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
+
+\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. 
+
+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.
+
+\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 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.
+
+\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
+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 a Expr
+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}
+
+\subsection{Control Flow}
+\begin{lstlisting}[label={lst:controlflow},%
+	caption={Bytecode view for \texttt{arith}}]
+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
+happens via 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. The exact implementation is shown in
+Listing~\ref{lst:shareview}.
+
+\begin{lstlisting}[label={lst:shareview},%
+	caption={Bytecode view for \texttt{arith}}]
+instance sds ByteCode where
+	sds f = {main = BC (freshs
+				>>= \sdsi->pure {BCShare | sdsi=sdsi,sdsval=BCValue 0}
+				>>= \sds->pure (f (tell` [BCSdsFetch sds]))
+				>>= \(v In bdy)->modify (addSDS sds v)
+				>>| unBC (unMain bdy))}
+	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
+\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}
+\todo{hulp functies voor compileren}