Blame view

maybe.tex 3.74 KB
Geoffrey Challen authored
1
\section{\texttt{\large maybe} Statement Semantics}
Geoffrey Challen authored
2
3
\label{sec-maybe}
Geoffrey Challen authored
4
5
6
7
To begin we provide an overview of the \texttt{maybe} statement's semantics
describing how it allows developers to structure uncertainty. We refer to
each of the values or code paths a \texttt{maybe} statement can choose from
as an \textit{alternative}.
Geoffrey Challen authored
8
Geoffrey Challen authored
9
\begin{figure}[t]
Geoffrey Challen authored
10
11
\begin{minted}[fontsize=\footnotesize]{java}
// Setting variables
Geoffrey Challen authored
12
int retryInterval = maybe 1-16;
Jinghao Shi authored
13
String policy = maybe "auto", "quality", "perf";
Geoffrey Challen authored
14
Geoffrey Challen authored
15
// Function alternatives
Geoffrey Challen authored
16
@maybe
Oliver Kennedy authored
17
int myFunction(int a) { /* First alternative */ }
Geoffrey Challen authored
18
@maybe
Oliver Kennedy authored
19
int myFunction(int a) { /* Second alternative */ }
Geoffrey Challen authored
20
Oliver Kennedy authored
21
// Inlining evaluation code
Geoffrey Challen authored
22
maybe {
Oliver Kennedy authored
23
  ret = fastPowerHungryAlgorithm(input);
Geoffrey Challen authored
24
} or {
Oliver Kennedy authored
25
  ret = slowPowerEfficientAlgorithm(input);
Geoffrey Challen authored
26
} evaluate {
Jinghao Shi authored
27
28
  return { "repeat": false,
           "score" : nanoTime() + powerDrain() }
Geoffrey Challen authored
29
}
Oliver Kennedy authored
30
Geoffrey Challen authored
31
32
\end{minted}
Geoffrey Challen authored
33
\vspace*{-0.2in}
Geoffrey Challen authored
34
Geoffrey Challen authored
35
\caption{\small\textbf{More \texttt{maybe} Statements}}
Geoffrey Challen authored
36
Geoffrey Challen authored
37
38
\label{fig-maybeexamples}
Geoffrey Challen authored
39
\vspace*{-0.2in}
Geoffrey Challen authored
40
Geoffrey Challen authored
41
42
\end{figure}
Geoffrey Challen authored
43
44
\subsection{Setting Variables}
Geoffrey Challen authored
45
46
Variables can be used to represent uncertainty. Examples include an integer
storing how often a timer should trigger communication with a remote server,
Geoffrey Challen authored
47
or a string containing the name of a policy used to coordinate multiple code
Geoffrey Challen authored
48
49
50
blocks throughout 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''.
Geoffrey Challen authored
51
Geoffrey Challen authored
52
53
\subsection{Controlling Code Flow}
Geoffrey Challen authored
54
55
56
Code flow can also represent uncertainty. Examples include using multiple
algorithms to compute the same result or multiple code paths representing
different tradeoffs between performance, energy, and quality.
Geoffrey Challen authored
57
Figure~\ref{fig-example-maybe} shows the \texttt{maybe} statement in its
Geoffrey Challen authored
58
simplest form, controlling execution of multiple code blocks. If multiple
Oliver Kennedy authored
59
alternatives are specified, the system chooses one to execute; if only one
Oliver Kennedy authored
60
alternative is specified, the system chooses whether or not to execute it.
Geoffrey Challen authored
61
62
Single-alternative \texttt{maybe} statements can encapsulate or reorganize
logic that does not affect correctness, but may (or may not) produce some
Geoffrey Challen authored
63
desirable outcome.
Geoffrey Challen authored
64
65

Figure~\ref{fig-maybeexamples} shows several extensions of the \texttt{maybe}
Geoffrey Challen authored
66
67
68
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
Geoffrey Challen authored
69
70
signatures. \texttt{maybe} statements that require custom evaluation logic
can include an \texttt{evaluate} block as shown in the final example.
Geoffrey Challen authored
71
72
73
74
75
76
77
78
79
80
81
82
\texttt{evaluate} blocks provide app-specific \textit{a posteriori} logic to
evaluate the selected alternative. The \texttt{evaluate} block must return a
single JSON object with two components: (1) a positive integer
\texttt{score}, with smaller being better; (2) and a boolean \texttt{repeat}
indicating whether the system must use the same alternative next time. Hints
and custom evaluation logic can also be applied to other types of
\texttt{maybe} statements through annotations.

While it should be possible to nest \texttt{maybe} statements, it may require
compiler support to provide guarantees about how \texttt{maybe} decisions are
maintained across multiple code blocks. As we gain more experience with our
rewrite-based prototype, described next in Section~\ref{sec-certainty}, we
Geoffrey Challen authored
83
will revisit the question of nesting in future compiler-based \texttt{maybe}
Geoffrey Challen authored
84
systems.
Geoffrey Challen authored
85
Geoffrey Challen authored
86
87
88
89
90
As a final remark, note that structured uncertainty is not randomness.
Randomness weights multiple options statically---there is no right or wrong
decision. In contrast, the \texttt{maybe} statement indicates that during any
given execution one alternative may better than the others. The goal of the
system is to determine which one.