introduction.tex
6.33 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
132
\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
outcome may depend on other factors not considered by the programmer, such as
the type of network the device is currently using.
In addition, attempts at pre-deployment adaptation frequently produce
arbitrary decision thresholds. Even if the two code paths in
Figure~\ref{fig-example-if} achieve the desired result, it is unclear what
battery level threshold should trigger the energy-saving path, 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) {
// Try to save energy
} else {
// Don't try 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 currently used to program mobile systems,
these tasks require writing large amounts of error-prone boilerplate code
that retrieves settings from remote servers and adjusts values at runtime.
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 {
// Try to save energy (Alternative 1)
} or {
// Don't to save energy (Alternative 2)
}
\end{minted}
\vspace*{-0.2in}
\caption{\small\textbf{Example \texttt{maybe} Statement.} The programmer
provides multiple alternatives. The system determines how to choose between
them.}
\label{fig-example-maybe}
\vspace*{-0.2in}
\end{figure}
\sloppypar{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 encourage programmers 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.
Together, multiple alternatives can produce 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 time-varying decisions.}
Figure~\ref{fig-example-maybe} shows how our earlier example can be easily
rewritten using a \texttt{maybe} statement. Unlike the previous example,
\texttt{maybe} does not rely on the developer to implement a decision process
or correctly predict 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. When they are
unsure what to do, all developers have to do is provide alternatives; the
\texttt{maybe} system does the rest. \texttt{maybe} allows developers to
respond to uncertainty with flexibility, which is used to enable
testing-driven adaptation.
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}.