\documentclass{article}
\usepackage{alltt,wrapfig,bar,graphicx}  % Written by David Carlisle and Sebastian Rahtz
\input{tricks.sty}
\begin{document}
\subsection{Reasoning about Early Life cycle Artifacts}

TAR2 works by summarizing a log of model behavior. Prior to a design being implemented,
 how can such a log
be generated?
In this first example, a simple qualitative simulator is used to generate behavior
from an early life cycle design.
%Such networks have the following features:
%\bi
%\item
%{\em Units} are defined according to  constraints between their {\em input/output} variables;
%\item
%{\em Units} are connected in a network where the output of some units
%are the input to others.
%\item
%Something {\em flows} around the network and {\em conservation laws} apply
%(e.g. in-flow has to equal out-flow).
%\item
%Sometimes, the network is built from a component libraries. Hence, it may contain repeated structures.
%\ei
%
%\noindent
%Such a network could represent many situations including
%\bi
%\item
%Water flowing in pipes in an industrial
%plant; 
%\item
%Customers moving through a web site while being directed towards services that potentially 
%interest them;
%\item
%The electrical circuit shown in \fig{cirtt}.
%\ei

Early in the design life cycle, the  general structure of the
solution may be known, but the details may yet to be determined.
That is,  even if precise quantitative values are unknown,
the {\em qualitative} features of the solution may be defined.
For example, in \fig{cirtt}, 
the network topology of the product (an electric circuit, in this case) is be defined
and the 
general nature of the network constraints are known.
However, suppose that
all that is currently known about the 
numerics is their sign: 
$\{+,-,0\}$ 
representing {\em positive}, {\em negative}, and {\em zero}
quantities (respectively).
\begin{figure}[!h]
\begin{center}
\includegraphics[width=3.5in]{../tim/cirt.pdf}
\end{center}
\caption{A qualitative network: $Sw_i$, $B_i$ denote switches and bulbs.
The network repeats the structure three times with labels
$\{A,B,C\}$. Between each repetition are 
connectors that {\em open} or {\em close}  switches depending on
whether or not some bulb is glowing or dark.
}
\label{fig:cirtt}
\end{figure}


Despite these unknowns, we still may
want to assess different
options.
For example, in hardware/software co-design
it is useful to  know what  problems can be solved by software and what problems need additional hardware.
Suppose the goal of the 
circuit (involving bulbs, switches, openers, and closers) in \fig{cirtt} is to illuminate some region.
One way to ensure that all the bulbs burn brightly is to add surge protectors to protect
the filaments. However, this adds to the cost of the circuit
so an engineering team reviewing the qualitative network of \fig{cirtt}
might ask ``how much can we increase the illumination just using default settings 
{\em without} adding expensive surge protectors?''.

In nondeterministic systems like \fig{cirtt}, 
the outputs are not fully determined by the inputs.
The following table explains why.
In qualitative arithmetic,
some additions are deterministic such as adding two positive quantity
always yields a positive quantity.
However,  some additions are not such as 
adding a {\em positive} and a {\em negative} which can produce either a positive or negative result.  We 
identify this indeterminism with the name  $Any$. 
\begin{center} \begin{minipage} {.8\linewidth} \begin{alltt}\footnotesize
sum(+,+,+).   sum(+,0,+). sum(+,-,Any).
sum(0,+,+).   sum(0,0,0). sum(0,-,-).
sum(-,+,Any). sum(-,0,-). sum(-,-,-).
\end{alltt} \end{minipage} \end{center}
Our thesis is that TAR2 can generate simple descriptions from seemingly complex
problems. 
The nondeterminacy in 
\fig{cirtt} generates a very large space options which TAR2 can succinctly
summarize.
To understand the enormity of the design space,
some more information is required about 
bulbs and switches.
For example, the first line of the following table
says that a blown bulb is always dark, and has zero amps; however, we do not know about the
voltage across it.
Also, the last line 
({\tt switch(on,0,Any)}) comments that 
if a switch is on, there is zero voltage drop
across that switch, but we do not know about the amperage.
\begin{center} \begin{minipage} {.9\linewidth} \begin{alltt}\footnotesize
%bulb(Mode,Light,Volts,Amps)
 bulb(blown,dark,  Any, 0).
 bulb(ok,   light, +,   +).
 bulb(ok,   light, -,   -).
 bulb(ok,   dark,  0,   0).

%num(Light, Glow).   %switch(State,Volts,Amps)
 num( light, 1).      switch(off,   Any,  0).
 num( dark,  0).      switch(on,    0,    Any).
\end{alltt} \end{minipage} \end{center}

\begin{figure}[!b]
{\scriptsize \begin{alltt}
  1  circuit(switch(Sw1,VSw1,C1),   bulb(B1,L1,VB1,C1),
  2          switch(Sw2,VSw2,C2),   bulb(B2,L2,VB2,C2),
  3          switch(Sw3,VSw3,CSw3), bulb(B3,L3,VB3,CB3),
  4          Glow) :-
  5      VSw3 = VB3,
  6      sum(VSw1, VB1, V1),   %  9 options
  7      sum(V1,VB3,+),        %  1 option
  8      sum(VSw2,VB2,VB3),    %  9 options
  9      switch(Sw1,VSw1,C1),  %  2 options
 10      bulb(B1,L1,VB1,C1),   %  4 options
 11      switch(Sw2,VSw2,C2),  %  2 options
 12      bulb(B2,L2,VB2,C2),   %  4 options
 13      switch(Sw3,VSw3,CSw3),%  2 options
 14      bulb(B3,L3,VB3,CB3),  %  4 options
 15      sum(CSw3,CB3,C3),     %  9 options
 16      sum(C2,C3,C1),        %  9 options
 17      num(L1,N1),
 18      num(L2,N2),
 19      num(L3,N3),
 20      Glow is N1+N2+N3.
\end{alltt}}
%%%% Jim -- in this Prolog, you use C to represent the amps.  Would A be better?

\caption{Conversation rules of \fig{cirtt}.}\label{fig:cirt}
\end{figure}
\begin{wrapfigure}{r}{1.8in}
{\footnotesize
\begin{center}
\begin{tabular}{c}
Untreated circuit \\
\begin{barenv} \setstyle{\sffamily} \setwidth{8}
\setnumberpos{none} \setstretch{1} \setyaxis{0}{45}{15}
\setxaxis{0}{9}{1}
\bar{0}{8}  %0
\bar{22}{8} %1
\bar{43}{8} %2
\bar{21}{8} %3
\bar{6}{8}  %4
 \bar{6}{8} %5
\bar{1}{8}  %6
\bar{0}{8}  %7
\bar{0}{8}  %8
\bar{0}{8}  %9
\end{barenv}
\end{tabular}
\end{center}}
\caption{Frequency count of number of bulbs glowing in the 35,228
solutions of {\tt circuits} of
\fig{cirtt}.}\label{fig:baseline}\label{fig:run1}
\end{wrapfigure}

\fig{cirtt} repeats three structures labeled $\{A,B,C\}$.
Within each structure,
certain conservation laws apply
about circuits in parallel and series.
These laws are represented in the Prolog of
\fig{cirt}; e.g.  line 9 says the two circuits in parallel have 
%%%% Jim -- is this what line 9 says?
the same voltage drop (so the sum of the voltages across switch
{\em SW2} and bulb {\em B2} is the same as the voltage across the
parallel bulb {\em B3}).
Each line of \fig{cirt} is labeled with the number of possibilities
it portends: i.e. $ 9*1*9*2*4*2*4*2*4*9*9 \approx 3,359,232$.  When  copied
three times in \fig{cirtt} these implies a space of up to
$(3,359,232)^3=10^{19}$ options. Many of these possibilities are ruled
out by inter-component constraints; nevertheless the constraints
of \fig{cirtt} can still succeed 35,228 times.


Enter treatment learning. Instead of exploring tens of 
thousands of options, our contrast set learner just seeks the smallest {\em differences}
that distinguishes the lightest circuits from the darkest circuits.
This is simple to operationalize: in the 35,228 solutions,
each of the nine bulbs either glows or is dark. Hence, we can give the contrast
set learner 35,228 examples, each labeled with the class $1,2,3,{\ldots}9$.
\fig{run1} shows the distribution of those examples: usually, only two bulbs glow.

\begin{figure}[!b]
\begin{center}
{\footnotesize
\begin{tabular}{c|p{.3\linewidth}l|}\cline{2-3}
round 1 &
treatment 0: &if Sw2C=off then ... \\&&~\\
&(treatment learned \newline from 35,228 solutions)&
{\scriptsize
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
\setstretch{1} \setyaxis{0}{48}{15} \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{47}{8} %4
 \bar{48}{8} %5
\bar{3}{8} %6
\bar{2}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}}\\~&&\\\cline{2-3}
round 2 &
treatment 1: & when Sw2c=off then  \\
& & if Sw1C=on  then ...  \\&&~\\
&(treatment learned \newline from
3,264 solutions)&
{\scriptsize
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
\setstretch{1} \setyaxis{0}{48}{15} \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{41}{8} %4
 \bar{42}{8} %5
\bar{9}{8} %6
\bar{8}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}}\\ ~&&\\\cline{2-3}
round 3 & 
treatment 2: &when Sw2C=off   \\
&& and Sw1C=on then    \\
&& if  B3C=ok  then ...  \\&&~\\
&(treatment learned \newline from 648 solutions)&
{\scriptsize
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
\setstretch{1} \setyaxis{0}{32}{15} \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{18}{8} %4
 \bar{21}{8} %5
\bar{32}{8} %6
\bar{29}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}}\\ ~&&\\\cline{2-3}
\end{tabular}}
\end{center}
\caption{Treatments learned at round $i-1$ applied to round $i$.
}\label{fig:whatif3}
\end{figure}
\fig{whatif3} shows three rounds of treatment learning. Each round  
imposes the 
treatments learned at the previous round as additional constraints to the circuit.
Note that, in \fig{whatif3}:
\be
\item
The constraints added at each round reduce the indeterminacy by
an order of magnitude from 35,228 solutions to 3,264 to 648.
\item
As the behavior is constrained, the number of glowing lights increases.
\item
Performance can be improved by ensuring that bulbs are $ok$; i.e.
that they are not $blown$.  (We can do this by adding surge protectors, although this adds 
cost to the circuit.)
The first treatment that includes that a requirement that bulb has status $ok$ was in round 3
(with $B3C=ok$). That is, 
just by setting some defaults within the circuit 
($\{Sw2C=on,Sw1C=on\}$)
we can increase average
 illumination from two to five. (To see this,
compare \fig{run1} to  round 2 of \fig{whatif3}).
However, as shown in round 3 of \fig{whatif3},
we can boost average illumination to six
by adding just one surge protector to  bulb $B3C$. 
\ee
Note that a large problem space (35,228 options) can be controlled
by a small treatment 
($\{Sw2C=on, Sw1C=on, B3C=ok\}$).
Better yet, treatments can be learned early in the
life cycle
before precise information is available on
(say) the exact numeric specifications
of the components.

Many researchers have predicated their work on the truism that
catching errors during early software life cycle is very important.
For example, Menzies has previously argued
~\cite{me00q}:\begin{quote}  The case for more formality in
(early life cycle) is overwhelming. Many errors in software can be
traced back to errors in the requirements~\cite{reifer79}. Often,
the conception of a system is improved as a direct result of the
discovery of inadequacies in the current conception. The earlier
such inadequacies are found, the better, since   the cost of
removing errors at the earlier stage can be {\em orders of
magnitude cheaper} than the cost of removing errors in the final
system~\cite{schnieder98}.\end{quote} However, as we shall see in
the following study,  removing early life cycle errors for a
particular project was not nearly as important as selection of the
inspection methods

\end{document}
