X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;f=mtaskext.bytecode.tex;h=e0da38a041a59bcc18bc3664a14a73e0345a67e3;hb=2498dced580be1e7af31a662dadee26c4fd159ed;hp=111be6fd5bfc4f479c2365076c09736efb314cb2;hpb=6548a5ec9ce8e0df67fc4019625ab5238eb1bf71;p=msc-thesis1617.git diff --git a/mtaskext.bytecode.tex b/mtaskext.bytecode.tex index 111be6f..e0da38a 100644 --- a/mtaskext.bytecode.tex +++ b/mtaskext.bytecode.tex @@ -4,7 +4,7 @@ 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 +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. @@ -24,19 +24,23 @@ 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. +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 = - { sdsi :: Int - , sdsval :: BCValue + { sdsi :: Int + , sdsval :: BCValue + , sdsname :: String } :: BCState = { freshl :: Int , freshs :: Int - , sdss :: [BCShare] + , sdss :: [BCShare] } class toByteCode a :: a -> String @@ -62,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. -\begin{lstlisting}[label={bc:instr},% +\begin{lstlisting}[language=Clean,label={bc:instr},% caption={Bytecode instruction set}] :: BC = BCNop | BCLab Int | BCPush BCValue | BCPop @@ -104,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. -\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]) @@ -124,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. -\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)] - (+.) x y = op2 x y BCDiv + (+.) x y = op2 x y BCAdd ... instance userLed ByteCode where @@ -136,7 +140,7 @@ instance userLed ByteCode where 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 @@ -145,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. -\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` []) + BCIfStmt (BC b) (BC t) (BC e) = BC ( freshlabel >>= \else->freshlabel >>= \endif-> b >>| tell [BCJmpF else] >>| @@ -164,20 +165,20 @@ BCIfStmt (BC b) (BC t) (BC e) = BC ( ) instance noOp ByteCode where - noOp = tell` [BCNop] + noOp = BC (pure ()) \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 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},% +view, \glspl{Task} run indefinitely, 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}[language=Clean,label={lst:return},% caption={Bytecode view for the return instruction}] class retrn v where retrn :: v () Expr @@ -188,19 +189,21 @@ instance retrn ByteCode where \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 +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}. +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. -\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 instance sds ByteCode where sds f = {main = BC (freshshare - >>= \sdsi->pure {BCShare|sdsi=sdsi,sdsval=BCValue 0} + >>= \sdsi->pure {BCShare|sdsname="",sdsi=sdsi,sdsval=BCValue 0} >>= \sds->pure (f (tell` [BCSdsFetch sds])) >>= \(v In bdy)->modify (addSDS sds v) >>| unBC (unMain bdy)) @@ -211,18 +214,18 @@ 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} 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 +All assignable types compile to an \gls{RWST} which writes the specific fetch +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 +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) @@ -240,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 -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) @@ -253,8 +266,12 @@ 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)) +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 @@ -262,6 +279,11 @@ toRealByteCode x 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