diff options
Diffstat (limited to 'assignment-13/ufpl.tex')
| -rw-r--r-- | assignment-13/ufpl.tex | 267 |
1 files changed, 267 insertions, 0 deletions
diff --git a/assignment-13/ufpl.tex b/assignment-13/ufpl.tex new file mode 100644 index 0000000..2129484 --- /dev/null +++ b/assignment-13/ufpl.tex @@ -0,0 +1,267 @@ +\documentclass[a4paper,twocolumn,english]{article} + +\title{$\mu$FPL\\[.4em] + \large{A small functional programming language for the Arduino}} +\author{Camil Staps} + +\usepackage[margin=25mm,bottom=35mm]{geometry} +\usepackage{graphicx} +\usepackage{subcaption} +\usepackage[hidelinks]{hyperref} +\usepackage{cleveref} +\usepackage{csquotes} +\usepackage{minted} +\setminted{fontsize=\small,tabsize=4,style=bw} + +\def\uFPL{$\mu$FPL} +\def\module#1{\texttt{\small#1}} +\def\clean#1{\texttt{\small#1}} + +\begin{document} + +\maketitle + +\section{Introduction} +\uFPL\ is a small functional programming language that compiles to Arduino C++. +It is implemented as a deeply embedded DSL in the programming language Clean.% + \footnote{I chose against a shallowly embedded DSL, + because the iTasks simulator is easier to make when there are concrete types to manipulate.} +Programs in \uFPL\ are lists of rewrite rules on shared data sources. +Rewrite rules can be set to trigger only when a share changes. +There are specialised instructions to deal with an LCD shield. +Buttons and timing are provided by way of predefined read-only shares. +Type safety is guaranteed using poor man's GADTs by John van Groningen. + +An example of a program in \uFPL\ is given in \cref{lst:score}. +It keeps scores of two players and displays it on the LCD. +There are four named rules (\texttt{a}, \texttt{b}, \texttt{r} and \texttt{print}) + that are executed in parallel by means of the \texttt{|||} operator. +The first two rules ensure that the scores of player A and player B are incremented when a button is pressed. +The third rule resets the scores when button 2 is pressed. +The fourth rule is triggered whenever either score changes, + and prints the score on the screen. + +\begin{listing*}[p] + \inputminted[firstline=13,lastline=32]{clean}{uFPL/Examples.icl} + \caption{An example \uFPL\ program to keep scores of two players.\label{lst:score}} +\end{listing*} + +\section{Implementation} + +\subsection{DSL} +The DSL types are provided in \module{uFPL}. +Expressions in our DSL are provided for literals, common operators for integers and booleans + and an \clean{EIf} constructor similar to Clean's \clean{if} (\cref{lst:exprs}). +Shorthands are provided for some constructors, especially those that require a bimap for type safety + (such as \clean{==.} for \clean{Expr}). +Expressions have a type \clean{t} and a phantom type \clean{rw} which is either \clean{RW} or \clean{RO}, + indicating whether an expression can be written or is read-only. +The only expression that can be written is an \clean{EShared}, + which is a shared data source (although there are read-only shares, such as buttons). + +\begin{listing*}[p] + \inputminted[firstline=53,lastline=74]{clean}{uFPL.dcl} + \caption{Expressions in our DSL.\label{lst:exprs}} +\end{listing*} + +A program consists of a collection of \clean{NamedRule}s, + a simple wrapper around the \clean{Rule} type (\cref{lst:rules}). +The last three constructors are only for the LCD shield. +The \clean{<\#} operator assigns a value to a shared data source. +With \clean{When} and \clean{>>>}, rules can be made conditional. +The first checks whether some condition holds, + while the second uses triggers that only fire when a share has changed value. +Rules can be chained with \clean{:.} and named rules with \clean{|||}. + +\begin{listing*}[p] + \inputminted[firstline=76,lastline=80]{clean}{uFPL.dcl} + \inputminted[firstline=84,lastline=93]{clean}{uFPL.dcl} + \caption{Rules in our DSL.\label{lst:rules}} +\end{listing*} + +The simplest trigger is \clean{Change}, which fires when a share has changed value. +The \clean{?=} trigger furthermore checks the new value. +Triggers can be composed with \clean{?\&} and \clean{?|}. + +Shares (\cref{lst:shares}) have a name, type, initial value and a function to represent values in C. +Like expressions, they have type variables for their type and whether they can be written or not. +The \clean{srw} field is discussed in \cref{sec:impl:sim}. +Normally, it should not be needed to define shares yourself. +Wrapper functions as \clean{rwInt :: String Int -> Expr Int RW} from \module{uFPL.Bootstrap} can be used for that, + similar to \clean{sharedStore} in iTasks. + +\begin{listing*}[p] + \inputminted[firstline=14,lastline=20]{clean}{uFPL.dcl} + \caption{Shares in our DSL.\label{lst:shares}} +\end{listing*} + +\subsection{Code generation} +A separate module, \module{uFPL.C}, provides types to represent simple (Arduino) C programs. +In \module{uFPL}, the \clean{gen} class takes care of generation to this C representation. + +Every named rule becomes a separate C function. +Every rule becomes a statement in a function. +The \clean{loop} function loops through all tasks and a special \clean{system} task, + which updates internal shares for buttons and timing. + +Shares are represented by structs and only accessed through specialised functions (\cref{lst:share-repr}) + holding their value (\clean{val}) and the number of tasks that has triggers for the share (\clean{subscriptions}). +There exists different structs for different types. +When the value is set, the member \clean{dirty} is set to the number of \clean{subscriptions}. +When a trigger on the share is checked, the \clean{dirty} number is decreased. +The trigger only fires when \clean{dirty} is positive. +Tasks are executed in a queue, + which guarantees that a task is always notified exactly once of a share change. + +\begin{listing*}[p] + \begin{minted}[gobble=2]{c} + struct bshare { + bool val; + unsigned char dirty; + unsigned char subscriptions; + }; + void bsubscribe(struct bshare *share) { + share->subscriptions++; + } + void bset(struct bshare *share, bool val) { + share->val = val; + share->dirty = share->subscriptions; + } + bool bdirty(struct bshare *share) { + if (share->dirty) { + share->dirty--; + return true; + } + return false; + } + \end{minted} + \caption{Representation of shares (here for booleans).\label{lst:share-repr}} +\end{listing*} + +The predefined shares for buttons and timing are always included in the generated code. +It would be possible to only include them when they are used, + but that would make generation of the \clean{system} function more complicated. +We rely on the C compiler to optimise unused shares. + +\subsection{Simulation} +\label{sec:impl:sim} +The \module{uFPL} module provides a view for running rules on some state, independently of iTasks. +An iTasks simulator is provided to interactively write programs in \uFPL. +The \module{uFPL.Sim} module provides shadow types similar to those in \module{uFPL}, + but with less type safety guarantees. +This is needed because we cannot build generic representations of types with existential quantifiers. + +We use a class \clean{lift :: t -> Task Dynamic} to lift shadow types to our DSL. +An example is given for addition in \cref{lst:lift}. +We have to explicitly test on all types (here \clean{Int} and \clean{Char}) + because type contexts in dynamic pattern matches are not supported yet. +In the iTask representation of the DSL, shares are identified with their name. +In a separate SDS these shares are defined. +The lift functionality looks up the right share in that SDS. +Whenever lifting fails (which is possible because the DSL is more restrictive), + an exception is thrown. + +\begin{listing*}[p] + \inputminted[gobble=1,firstline=101,lastline=104]{clean}{uFPL/Sim.icl} + \caption{Lifting shadow types to the DSL.\label{lst:lift}} +\end{listing*} + +Unlifting from the DSL to the iTasks domain is simpler and does not require dynamics or tasks (\clean{unlift :: t -> u}). +In the case of shares, we would want to define multiple instances of unlift, with the types + \clean{(UShared Int RW) -> IShared}, \clean{(UShared Int RO) -> IShared}, etc., + because the iTasks representation holds information about type and writability. +This yields a compiler error about multiply defined instances (which I think is a compiler bug). +To solve this, we use a dynamic representation of the value to check the type + and a small piece of ABC code to check whether the share is read-only or not (\cref{lst:unlift-shares}). +The latter was only possible by adding an extra field to the DSL shares that holds a value of the \clean{rw} type. + +\begin{listing*}[p] + \inputminted[firstline=167,lastline=196]{clean}{uFPL/Sim.icl} + \caption{Unlifting shares requires dynamics and ABC-code, due to a presumed compiler bug.\label{lst:unlift-shares}} +\end{listing*} + +The iTasks simulator allows the user to update a set of named rules and shares on the right. +Because rules are supposed to be independent, it is not possible to change the order of the list. +On the left, the state is shown: either \enquote{OK} or an exception when lifting to the DSL fails. +This provides the user with the same amount of type safety as provided by the compiler. +Example errors are shown in \cref{fig:itasks-errors}. + +\begin{figure*}[p] + \centering + \begin{subfigure}{.8\textwidth} + \centering + \includegraphics[width=\textwidth]{error-no-such-share} + \caption{Using a non-existent share.} + \end{subfigure} + + \begin{subfigure}{.8\textwidth} + \centering + \includegraphics[width=\textwidth]{error-share-type} + \caption{Assigning a value with other type to a share.} + \end{subfigure} + + \begin{subfigure}{.8\textwidth} + \centering + \includegraphics[width=\textwidth]{error-ro-share} + \caption{Assigning a value to a read-only share.} + \end{subfigure} + \caption{Errors thrown in the iTasks simulator.\label{fig:itasks-errors}} +\end{figure*} + +A number of actions is available to simulate the program. +It is not possible to update arbitrary shares, but for buttons and timing specialised actions are available (\cref{fig:itasks-score:simulation}). +The most basic action is \enquote{Step}, + which executes every named rule once. +Buttons can be toggled, which changes their value but does not execute any code. +Pressing a button means setting it to \clean{true}, doing a step and resetting it to \clean{false}.% + \footnote{The system does not take into account that only one button can be pressed at the same time due to the resistor ladder on the LCD shield.} +When a program uses timing, + actions exist for incrementing the value of \clean{millis} with \clean{100} or \clean{1000} (without stepping the program). +There also exists a fully automatic simulator + which increments the value of \clean{millis} by \clean{1000} and performs a step every second. +However, due to (presumed) limitations of the iTasks framework, + this uses a lot of CPU power and the state share sometimes misses an iteration. + +In the left bottom view, the states of the shares and the display ($16\times2$ is assumed) are shown. + +Finally, it is possible to generate code from within iTasks and save it to disk (\cref{fig:itasks-score:code-generation}). + +\begin{figure*}[p] + \begin{subfigure}{\textwidth} + \includegraphics[width=\textwidth]{scores} + \caption{Simulation.\label{fig:itasks-score:simulation}} + \end{subfigure} + \begin{subfigure}{\textwidth} + \includegraphics[width=\textwidth]{scores-generate} + \caption{Code generation.\label{fig:itasks-score:code-generation}} + \end{subfigure} + \caption{The scoring example program (\cref{lst:score}) in the iTasks simulator.\label{fig:itasks-scores}} +\end{figure*} + +\section{Discussion} +\uFPL\ is strongly typed. +Variables are type-checked, + but because \uFPL\ is a functional language the only variables are shares. +For type checking in the iTasks simulator we use tasks that lift shadow types to the DSL or throw exceptions. +The DSL has a straightforward syntax with shorthands whenever bimaps or other technicalities could be avoided. +It provides rudimentary task-oriented programming support using shared data sources + and a theoretically arbitrary number of tasks in parallel, + although sequencing, parameterised tasks and task control have not been implemented. + +\uFPL\ does not allow for control over pins, + but it would be straightforward to add this using more predefined shares. + +I chose for the subscription model of shares because it allows to suspend and start tasks. +However, this has not been implemented yet. +Therefore, the number of subscriptions to a share is currently only a constant value. + +Using a \clean{dirty} counter for shares requires that every task is executed equally often. +It would be possible to handle triggers with a bitmask where each bit indicates whether a task has seen the change. +This would allow for tasks starting other tasks. + +Currently, tasks cannot return a value; all generated functions have type \clean{void} and arity 0. +It would be very easy to implement this as a syntactic sugar where a new share would be introduced to handle the inter-task communication. +However, I did not do that because adding these changes to the iTasks simulator would be tedious, + and the proper way would be to generate functions with parameters and return types. + +\end{document} |