introduction.tex
5.51 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
\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; This has led to the popularity of so-called AB
or split testing.
Uncertainty is especially problematic for mobile app programmers:
Specific device features, such as
accurate location from GPS, may or may not be available. Networks come and go,
and their properties may change, from fast and free Wifi links to slower or
metered mobile data connections. Energy may be plentiful or nearly exhausted,
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.
The most typical approach to address this problem is to force the
programmer to 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---by utilizing a slower
but more energy-efficient algorithm, computing an approximation instead of an
exact result, or deferring the computation.
\sloppypar{ 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
connected to.}
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{\textbf{Typical Error-prone Energy Adaptation.} The threshold is
arbitrary and the attempt to conserve energy may not work sometimes, for some
users, or at all.}
\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 when it comes to the scope and effects of
exogenous runtime conditions, \textbf{today's languages force programmers
to be certain at a moment when they cannot be}, at compile time.
This weakness is only exacerbated by the amount of variation across different
mobile devices. Our solution is simple: (1) Provide developers with a
way to express structured uncertainty as sets of equivalent options,
and (2) Use this structure to enable a robust array of downstream tools for
resolving uncertainty by selecting among options 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.2in}
\caption{\textbf{Example Use of the \texttt{maybe} Statement.} }
\label{fig-example-maybe}
\vspace*{-0.2in}
\end{figure}
In this paper, we focus on the challenge of providing developers with
a language construct for expressing structured uncertainty: The
\texttt{maybe} statement. \texttt{maybe} statements allow programmers to
express sets of equivalent options for both data and control-flow.
Figure~\ref{fig-example-maybe} shows a simple case of a \texttt{maybe} case
statement applied to our earlier example. Instead of being forced to choose,
being forced to attempt to implement the decision process, or even required
to evaluate multiple options, the programmer is free to offer two or more
alternatives that are different but both correct, although one may be
preferable. At runtime only one will be used during any given execution, with
the system choosing the alternative that saves energy when it is appropriate
to do so. Note that the branch that a \texttt{maybe} statement takes
is not random; Rather, it tries to make the best choice and not just any choice.
How that choice is made is discussed in the remainder of our paper. 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 collapsing compile-time uncertainty into the required runtime
certainty. We continue by
briefly describing several example use cases in Section~\ref{sec-usage} and related work in Section~\ref{sec-related}.
We conclude in Section~\ref{sec-conclusion}.