blue / papers.hotmobile2015-maybe · Files

\section{\texttt{\large maybe} Statement Semantics}
\label{sec-maybe}

To begin, we provide a brief overview of the semantics of the \texttt{maybe}
statement, describing how it can express structured uncertainty in variable
values and runtime execution. We refer to each of the values a \texttt{maybe}
variable can take and each of the a paths a \texttt{maybe} code block can
execute as an \textit{alternative}.

Note that structured uncertainty is not randomness. The \texttt{maybe}
statement indicates that during any given execution one alternative may be
better than the others---even if the developer or system are not sure which
alternative to use.

\begin{figure}[t]
\begin{minted}[fontsize=\footnotesize]{java}
// Setting variables
int retryInterval = maybe 1-16;
String policy = maybe "auto", "quality", "perf";

// Function alternatives
@maybe
int myFunction(int a) { /* First alternative */ }

@maybe
int myFunction(int a) { /* Second alternative */ }

// Inlining evaluation code
maybe {
  ret = fastPowerHungryAlgorithm(input);
  choice = FAST;
} or {
  ret = slowPowerEfficientAlgorithm(input);
  choice = SLOW;
} analyze {
  return { "repeat": false,
           "score" : nanoTime() + powerDrain() }
}

// Cleanup may depend on which algorithm was used
if(choice == FAST){ cleanUpAfterFastAlg(ret); }
else              { cleanUpAfterSlowAlg(ret); }
\end{minted}

\vspace*{-0.2in}

\caption{\textbf{More Examples of \texttt{maybe} Statements.}}

\label{fig-maybeexamples}

\vspace*{-0.2in}

\end{figure}

\subsection{Setting Variables}

Variables can be used to represent uncertainty. Examples include an integer
storing how often a timer should trigger communication with a remote server,
or a string containing the name of a policy used to coordinate multiple code
blocks through the app. Figure~\ref{fig-maybeexamples} shows examples of an
integer that can take on values between 1 and 16, and a string that be set to
either ``auto'', ``quality'', or ``perf''.

\subsection{Controlling Code Flow}

Code flow can also represent uncertainty, and we expect this to be the most
common use of \texttt{maybe} statements. Examples include evaluating
multiple algorithms to compute the same result or code paths that represent
different energy-performance or energy-quality tradeoffs.
Figure~\ref{fig-example-maybe} shows the \texttt{maybe} statement in its
simplest form controlling execution of multiple code blocks. If multiple
alternatives are specified, the system chooses one to execute; if only one
alternative is specified, the system chooses whether or not to execute it.
Single-alternative \texttt{maybe} statements can encapsulate 
or reorganize logic that does not affect correctness, but may (or
may not) improve performance if executed.

Figure~\ref{fig-maybeexamples} shows several extensions of the \texttt{maybe}
statement providing syntactic sugar. \texttt{maybe} function annotations allow
uncertainty to be expressed at the function level, with the alternatives
consisting of multiple function definitions with identical signatures. Finally,
\texttt{maybe} blocks that require special performance evaluation logic can 
include that in the form of a \texttt{better} statement following the main 
\texttt{maybe}
block, as shown in the final example. \texttt{better} blocks provide 
application-specific logic that performs a post-mortem on the selected 
execution path.  The \texttt{better} block must return a
single JSON object that includes two components: A score, with smaller being
interpreted as better; and a boolean indicating whether the system should
use the same branch next time, or if it is free to try another. 
Note that hints and dedicated evaluation logic can also be
applied to variable and function-level \texttt{maybe} statements through
annotations.
We will return to post-mortem evaluation  
in Section~\ref{sec-certainty}.

\subsection{Programming With \texttt{\large maybe}}

We have yet to determine how well programmers will be able to use the new
\texttt{maybe} construct. At some level, \texttt{maybe} statements are
similar to the common \texttt{if-else} construct. At the bottom of the
statement, the programmer may not be sure which block was executed. Of
course, with \texttt{if-else} blocks it can be determined which block was
executed by examining the branch conditions. When working with the
\texttt{maybe} statement, the developer must set a variable inside each
\texttt{maybe} block if downstream code depends on which alternative was
chosen, as in Figure~\ref{fig-maybeexamples}.  Alternatively, programmers may 
use a \texttt{maybe} variable to select a policy, and employ the traditional
\texttt{if-else} construct to direct control flow based on the \texttt{maybe}
variable.

\subsection{When Not To Use \texttt{\large maybe}}
% 10/13 by OK: 
% We don't discuss dependencies between maybe statements anywhere else, so I'm
% killing the ref here.  It's still true that we're creating an exponential
% search space of possibilities; so the same text is getting re-purposed for
% that.
While \texttt{maybe} is a powerful programming tool, it is important that it
be used sparingly. In the case where no dependencies exist between the
alternatives expressed by separate \texttt{maybe} statements, each
\texttt{maybe} expands the overall configuration space exponentially and
makes the resulting process of determining the best alternative much more
complicated. Compile-time analysis may be required to ensure that downstream
optimization remains feasible.

The most important guideline for when \textit{not} to use \texttt{maybe}
usage is when a decision is not app-specific, and should instead be 
made by a library or  service. As an example, \texttt{maybe} should 
not be used to decide which networking interface to use to send a packet. 
To the degree that
one app shares the same objectives as others---say, to minimize latency---a
service should be performing adaptation on behalf of all apps using the
merged network interfaces, possibly through the use of its own internal
\texttt{maybe} statements.