\subsubsection{Size of library components.}
\label{s:size}
We now consider how big library components might be.
If we want to achieve the strong reuse vision of ``programming by wiring
together large  components,'' this suggests that components ought to be
quite large compared to the wiring.  The following theorem sheds
light on the conditions when this is possible.

Let $S(n)$ denote the expected amount of code (in bits) saved
per use of the $n^\mathit{th}$ component.  We consider
the case when $\lambda(n) \sim \frac{1}{n \strlen{c(n)} f(n)}$,
where $\strlen{c(n)}$ is the codeword (identifier) length,
and $f(n)$ is a function $f \in o(n^\epsilon)$ for $\epsilon > 0$
that ensures convergence (cf. \refsec{s:newderiv}).
This coincides with a Zipf-style law as observed in practice
(\reffig{f:rates}).

\begin{thm}
\label{thm:size}
If a library achieves a compression factor of $\Hdomain > 0$ in an
honest problem domain, then 
$S(n) \sim \frac{1-\Hdomain}{\Hdomain} \cdot o(n^\epsilon)$
for any $\epsilon > 0$.
\end{thm}
\begin{proof}
Summing over all components, the total code saved is:
\begin{align}
\sum_{n=1}^\infty \underbrace{\bigl(\lambda(n) \Hdomain s + o(\Hdomain s)\bigr)}_{\text{expected \# uses}} ~~\cdot \underbrace{S(n)}_{\text{savings per use}} = \underbrace{(1-\Hdomain) s}_{\text{total savings}}
\end{align}
\noindent
Dividing through by $\Hdomain s$ and taking the limit as $s \rightarrow \infty$,
and substituting $\lambda(n) \sim \frac{1}{n \strlen{c(n)} f(n)}$,
\begin{align*}
\sum_{n=1}^\infty \frac{1}{n \strlen{c(n)} f(n)} S(n) = \frac{1-\Hdomain}{\Hdomain}
\end{align*}
Now if $S(n) \sim n^a$ for some constant $a > 0$ then the sum would diverge.  Therefore
$S(n)$ is not polynomial in $n$; in fact for the sum to converge we must
have $S(n) \prec f(n)$ which means $S(n)$ behaves asymptotically as
\begin{align*}
S(n) \sim \frac{1-\Hdomain}{\Hdomain} o(n^\epsilon)
\end{align*}
where $o(n^\epsilon)$ denotes some subpolynomial function.
\qed
\end{proof}

Note that if the components in the library are unique, then
$S(n) \geq \log n$ by pigeonhole.

\begin{figure*}
\begin{centering}
\includegraphics[scale=0.7]{save}

\end{centering}

\caption{Plot of $\frac{1-\Hdomain}{\Hdomain}$ versus $\Hdomain$, indicating
how much code is saved, proportionately, per component use.  When
$\Hdomain \rightarrow 1$ there is almost no reuse; $\Hdomain \rightarrow 0$
coincides with the ``strong reuse'' ideal of wiring together large
components.  In between is weak reuse, with moderate amounts of code
drawn from libraries.
}
\end{figure*}

\tinysection{Strong reuse?}
The interpretation of \refthm{thm:size} is fairly intuitive.  Roughly
it says the savings we can expect per component are linear
in the size of the component identifier.  Which is to say, we
should expect savings for the $n^\mathit{th}$ component to grow roughly 
as $\log^{+} n$.
This is consistent with findings in the
reuse literature that \emph{small} components are much more likely
to be reused.  
The important factor here is the multiplier $\frac{1-\Hdomain}{\Hdomain}$.
As $\Hdomain \rightarrow 0$, this multiplier becomes arbitrarily large.
This suggests that ``strong reuse'' (\refsec{s:intro}) corresponds
to the region $\Hdomain \rightarrow 0$.  
For example, if programs in a problem domain are thought to be solvable 
by wiring together components that are (say) $1000$ times bigger than the 
wiring itself, this suggests $\frac{1-\Hdomain}{\Hdomain} \approx 10^5$ or
$\Hdomain \approx 0.001$.  The key result is that whether one
is able to achieve strong reuse depends critically on the parameter 
$\Hdomain$ --- which measures how much diversity there is in the
problem domain.

