update presentation, the body is there

[msc-thesis1617.git] / mtaskext.bytecode.tex

diff --git a/mtaskext.bytecode.tex b/mtaskext.bytecode.tex
index 833d964..e0da38a 100644 (file)
--- a/mtaskext.bytecode.tex
+++ b/mtaskext.bytecode.tex
@@ -24,9 +24,12 @@ 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
 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.
+same detection if necessary. Note that \CI{BCValue} uses existentially
+quantified type variables and therefore it is not possible to derive class
+instances such as \CI{iTasks}. Tailor-made instances for these functions have
+been made.

 
 

-\begin{lstlisting}[label={lst:bcview},caption={Bytecode view}]
+\begin{lstlisting}[language=Clean,label={lst:bcview},caption={Bytecode view}]

 :: ByteCode a p = BC (RWS () [BC] BCState ())
 :: BCValue = E.e: BCValue e & mTaskType, TC e
 :: BCShare =
 :: ByteCode a p = BC (RWS () [BC] BCState ())
 :: BCValue = E.e: BCValue e & mTaskType, TC e
 :: BCShare =


@@ -63,7 +66,7 @@ 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.
 
 program memory addresses in the final step of compilation to save instructions
 and avoid label lookups at runtime.
 

-\begin{lstlisting}[label={bc:instr},%
+\begin{lstlisting}[language=Clean,label={bc:instr},%

        caption={Bytecode instruction set}]
 :: BC = BCNop
        | BCLab Int          | BCPush BCValue     | BCPop
        caption={Bytecode instruction set}]
 :: BC = BCNop
        | BCLab Int          | BCPush BCValue     | BCPop


@@ -105,7 +108,7 @@ 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.
 
 \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}]
+\begin{lstlisting}[language=Clean,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])
 
 op2 :: (ByteCode a p1) (ByteCode a p2) BC -> ByteCode b Expr
 op2 (BC x) (BC y) bc = BC (x >>| y >>| tell [bc])
 


@@ -125,11 +128,11 @@ functions. Listing~\ref{lst:arithview} shows some implementations. The
 \CI{boolExpr} class and the classes for the peripherals are implemented using
 the same strategy.
 
 \CI{boolExpr} class and the classes for the peripherals are implemented using
 the same strategy.
 

-\begin{lstlisting}[label={lst:arithview},caption={%
+\begin{lstlisting}[language=Clean,label={lst:arithview},caption={%

        Bytecode view implementation for arithmetic and peripheral classes}]
 instance arith ByteCode where
        lit x = tell` [BCPush (BCValue x)]
        Bytecode view implementation for arithmetic and peripheral classes}]
 instance arith ByteCode where
        lit x = tell` [BCPush (BCValue x)]

-       (+.) x y = op2 x y BCDiv
+       (+.) x y = op2 x y BCAdd

        ...
 
 instance userLed ByteCode where
        ...
 
 instance userLed ByteCode where


@@ -137,7 +140,7 @@ instance userLed ByteCode where
        ledOff l = op l BCLedOff
 \end{lstlisting}
 
        ledOff l = op l BCLedOff
 \end{lstlisting}
 

-\subsection{Control Flow}
+\subsection{Control Flow}\label{ssec:control}

 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
 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


@@ -146,17 +149,14 @@ 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.
 
 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
+\begin{lstlisting}[language=Clean,label={lst:controlflow},%
+       caption={Bytecode view for the \texttt{IF} class}]
+freshlabel = get >>= \st=:{freshl}->put {st & freshl=freshl+1} >>| tell 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` [])
 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] >>|
 BCIfStmt (BC b) (BC t) (BC e) = BC (
        freshlabel >>= \else->freshlabel >>= \endif->
        b >>| tell [BCJmpF else] >>|


@@ -165,11 +165,11 @@ BCIfStmt (BC b) (BC t) (BC e) = BC (
        )
 
 instance noOp ByteCode where
        )
 
 instance noOp ByteCode where

-       noOp = tell` [BCNop]
+       noOp = BC (pure ())

 \end{lstlisting}
 
 \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
+The scheduling in the \gls{mTask}-\glspl{Task} bytecode view is different from
+the scheduling in 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 indefinitely, one-shot or on interrupt. To allow
 interval and interrupt \glspl{Task} to terminate, a return instruction is
 new \glspl{Task} or even start themselves to continue, while in the bytecode
 view, \glspl{Task} run indefinitely, one-shot or on interrupt. To allow
 interval and interrupt \glspl{Task} to terminate, a return instruction is


@@ -178,7 +178,7 @@ 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.
 
 execution.  Listing~\ref{lst:return} shows the classes and implementation for
 the return expression.
 

-\begin{lstlisting}[label={lst:return},%
+\begin{lstlisting}[language=Clean,label={lst:return},%

        caption={Bytecode view for the return instruction}]
 class retrn v where
   retrn :: v () Expr
        caption={Bytecode view for the return instruction}]
 class retrn v where
   retrn :: v () Expr


@@ -197,7 +197,7 @@ implementation is shown in Listing~\ref{lst:shareview}. The implementation for
 the \CI{namedsds} class is exactly the same other than that it stores the given
 name in the \CI{BCShare} structure as well.
 
 the \CI{namedsds} class is exactly the same other than that it stores the given
 name in the \CI{BCShare} structure as well.
 

-\begin{lstlisting}[label={lst:shareview},%
+\begin{lstlisting}[language=Clean,label={lst:shareview},%

        caption={Bytecode view for \texttt{arith}}]
 freshshare = get >>= \st=:{freshs}->put {st & freshs=freshs+1} >>| pure freshs
 
        caption={Bytecode view for \texttt{arith}}]
 freshshare = get >>= \st=:{freshs}->put {st & freshs=freshs+1} >>| pure freshs
 


@@ -215,17 +215,17 @@ addSDS sds v s = {s & sdss=[{sds & sdsval=BCValue v}:s.sdss]}
 \end{lstlisting}
 
 All assignable types compile to an \gls{RWST} which writes the specific fetch
 \end{lstlisting}
 
 All assignable types compile to an \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
+instruction(s). For example, using an \gls{SDS} always results in % chktex 36
+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
 \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}.
+instruction(s) will be rewritten accordingly. This results in a %chktex 36
+\CI{BCSdsStore} or \CI{BCAnalogWrite} instruction respectively. The
+implementation for this is given in Listing~\ref{lst:assignmentview}.

 
 

-\begin{lstlisting}[label={lst:assignmentview},%
+\begin{lstlisting}[language=Clean,label={lst:assignmentview},%

        caption={Bytecode view implementation for assignment.}]
 instance assign ByteCode where
        (=.) (BC v) (BC e) = BC (e >>| censor makeStore v)
        caption={Bytecode view implementation for assignment.}]
 instance assign ByteCode where
        (=.) (BC v) (BC e) = BC (e >>| censor makeStore v)


@@ -243,11 +243,21 @@ 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
 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},%
+translation of labels to program addresses is straightforward. The function
+consumes the instructions one by one while incrementing the address counter
+with the length of the instruction. The generic function \CI{consNum} is used
+which gives the arity of the constructor. However, when it encounters a
+\CI{BCLab} instruction, the counter is not increased because the label will not
+result in an actual instruction. The label is removed and the position of the
+label is stored in the resulting map. When all labels are removed, the jump
+instructions are transformed using the \CI{implGotos} function that looks up
+the correct program address in the map resulting from the aforementioned
+function. This step is followed by comparing the old compiler state to the new
+one to find new instantiated \glspl{SDS}. The compilation concludes with
+converting the bytecode and \glspl{SDS} to actual messages ready to send to the
+client.
+
+\begin{lstlisting}[language=Clean,label={lst:compilation},%

        caption={Actual compilation.}]
 bclength :: BC -> Int
 bclength (BCPush s) = 1 + size (toByteCode s)
        caption={Actual compilation.}]
 bclength :: BC -> Int
 bclength (BCPush s) = 1 + size (toByteCode s)


@@ -256,8 +266,12 @@ bclength x = 1 + consNum{|*|} x
 
 computeGotos :: [BC] Int -> ([BC], Map Int Int)
 computeGotos [] _ = ([], newMap)
 
 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))
+computeGotos [BCLab l:xs] i
+# (bc, i) = computeGotos xs i
+= (bc, put l i)
+computeGotos [x:xs] i
+# (bc, i) = computeGotos xs (i + bclength x)
+= ([x:bc], i)

 
 toRealByteCode :: (ByteCode a b) BCState -> (String, BCState)
 toRealByteCode x s
 
 toRealByteCode :: (ByteCode a b) BCState -> (String, BCState)
 toRealByteCode x s


@@ -265,6 +279,11 @@ toRealByteCode x s
 # (bc, gtmap) = computeGotos bc 1
 = (concat (map (toString o toByteVal) (map (implGotos gtmap) bc)), s)
 
 # (bc, gtmap) = computeGotos bc 1
 = (concat (map (toString o toByteVal) (map (implGotos gtmap) bc)), s)
 

+implGotos map (BCJmp t) = BCJmp $ fromJust   (get t map)
+implGotos map (BCJmpT t) = BCJmpT $ fromJust (get t map)
+implGotos map (BCJmpF t) = BCJmpF $ fromJust (get t map)
+implGotos _ i = i
+

 toMessages :: MTaskInterval (Main (ByteCode a b)) BCState -> ([MTaskMSGSend], BCState)
 toMessages interval x oldstate
 # (bc, newstate) = toRealByteCode (unMain x) oldstate
 toMessages :: MTaskInterval (Main (ByteCode a b)) BCState -> ([MTaskMSGSend], BCState)
 toMessages interval x oldstate
 # (bc, newstate) = toRealByteCode (unMain x) oldstate