introduction.tex
6.24 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
\section{Introduction}
All programmers must deal with uncertainty about runtime environments. For
example, the most appropriate algorithm for a given task may depend on inputs
that are unknown when the function is written, and its performance may depend
on device-specific features that are impossible for the developer to
anticipate. In other cases, real-world testing may be required to choose
between several approaches, which has led to the popularity of split testing.
Uncertainty is especially problematic for mobile app programmers. Specific
device features, such as accurate GPS location, may or may not be available.
Networks come and go and their properties change: from fast and free Wifi
links to slower metered mobile data connections. Energy may be plentiful or
scarce, depending on the device's battery capacity and the user's energy
consumption and charging patterns. These constantly fluctuating exogenous
conditions make writing effective mobile apps particularly challenging.
Today programmers are forced to anticipate these changing conditions at
development time and implement the required adaptation themselves.
Figure~\ref{fig-example-if} shows an example of an Android app attempting to
adapt to the device's battery level by establishing regular- and low-battery
code paths, with the latter attempting to save energy, possibly by utilizing
a slower but more energy-efficient algorithm, computing an approximate
result, or deferring the computation.
Unfortunately, this approach has several serious weaknesses. The most
important is perhaps the least obvious: it is unclear that the different code
paths achieve the desired result. There may be no differences between the
alternatives (neither conserves energy), the alternative designed to conserve
energy may actually consume more due to bugs or incorrect assumptions, or the
result may also depend on some other factor not considered by the programmer,
such as the type of network the device is currently using.
In addition, adaptive programming frequently requires arbitrary decision
thresholds chosen before deployment. Even if the two code paths shown in
Figure~\ref{fig-example-if} achieve the desired result, it is unclear what
the threshold for choosing a path should be, whether a single threshold
will work for all users, and whether the threshold should depend on
other factors such as how frequently the app is used.
\begin{figure}[t]
\begin{minted}[fontsize=\footnotesize]{java}
if (plugged == false && batteryLevel < 10) {
// Attempt to save energy
} else {
// Don't attempt to save energy
}
\end{minted}
\vspace*{-0.2in}
\caption{\small\textbf{Typical Error-Prone Energy Adaptation.} The threshold is
arbitrary and the attempt to conserve energy may succeed only at certain times,
only for certain users, only on certain devices, or never.}
\label{fig-example-if}
\vspace*{-0.2in}
\end{figure}
Finally, the current approach to adaptation fails to support post-deployment
testing. While it is possible to enable flexibility, runtime adaptation, and
split testing using the languages typically used to program mobile systems,
these common tasks require writing large amounts of error-prone boilerplate
code, including APIs to adjust values at runtime and code to retrieve
settings from remote servers.
The root of the problem is that \textbf{today's languages force programmers to
be certain at a moment when they cannot be}: at development time. While this
problem is endemic to existing programming languages, when developing mobile
apps it is magnified by the amount of variation developers must confront. Our
solution is simple: (1) provide developers with a way to express
\textit{structured uncertainty}, and (2) use the resulting flexibility to
enable a large array of downstream tools for resolving uncertainty by
choosing from the alternatives provided by the developer.
\begin{figure}[t]
\begin{minted}[fontsize=\footnotesize]{java}
maybe {
// Attempt to save energy
} or {
// Don't attempt to save energy
}
\end{minted}
\vspace*{-0.1in}
\caption{\small\textbf{Example \texttt{maybe} Statement.} The programmer provides
multiple equivalent alternatives. The system determines how to choose between
them at runtime.}
\label{fig-example-maybe}
\vspace*{-0.1in}
\end{figure}
In this paper, we present a novel a language construct for expressing
structured uncertainty: the \texttt{maybe} statement. Unlike previous
approaches to adaptation that relied on language support, \texttt{maybe} does
not attempt to encourage the programmer to provide more information about
their app to allow the compiler to improve performance or guarantee
correctness. Rather, \texttt{maybe} allows the programmer to express and
structure uncertainty by providing two or more different
\textit{alternatives} implementing multiple approaches to runtime adaptation,
possibly by making the same energy-performance or energy-accuracy tradeoffs
described previously. Conceptually, \texttt{maybe} extends the process of
compilation and optimization to include post-deployment testing while also
enabling flexible adaptation that may produce per-user, per-device, or
temporally-varying solutions.
Figure~\ref{fig-example-maybe} shows how our earlier example can be easily
rewritten to use a \texttt{maybe} statement. Unlike the previous example
\texttt{maybe} does not rely on the developer to implement a decision process
or correctly anticipate the effects of each alternative. Instead, the
\texttt{maybe} system makes runtime choices about which alternative to use by
measuring the tradeoffs produced by each alternative and (in this case)
activating an energy-saving alternative when appropriate. All the developer
has to do is provide alternatives when they are unsure what to do; the
\texttt{maybe} system does the rest.
The rest of our paper is structured as follows. We begin by providing a more
complete description of the \texttt{maybe} statement in
Section~\ref{sec-maybe}. Section~\ref{sec-certainty} describes several
techniques for transforming development-time uncertainty into runtime
certainty. We continue by describing several example use cases in
Section~\ref{sec-usage}, discussing the implications of the \texttt{maybe}
statement in Section~\ref{sec-discussion}, and presenting related work in
Section~\ref{sec-related}. We conclude in Section~\ref{sec-conclusion}.