http:^^www.cs.cornell.edu^info^people^tt^research^incremental-computation^derivation.html

来自「This data set contains WWW-pages collect」· HTML 代码 · 共 166 行

MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 24-Nov-96 21:33:34 GMT
Content-Type: text/html
Content-Length: 6703
Last-Modified: Wednesday, 06-Mar-96 16:34:02 GMT

<TITLE>Incremental Compuation: Deriving Incremental Programs</TITLE>

<H2>Deriving Incremental Programs</H2>

<P> <HR> <P>
<h3>Objectives</h3>
<OL>
<li> We are engaged in an ambitious effort to <i>derive</i> incremental
programs automatically (or semi-automatically) from
non-incremental programs written in standard programming languages.
This approach contrasts with our earlier approaches that aimed to
incrementally <i>evaluate</i> non-incremental programs.

<p> <LI> In essence, every program computes by fixed-point iteration,
expressed as recursive functions or loops.  This is why loop
optimizations are so important.  A loop body can be regarded as a
program <i>f</i> parameterized by an induction variable <i>x</i> that
is incremented on each iteration by a change operation <i>+</i>.
Efficient iterative computation relies on effective use of state,
i.e., computing the result of each iteration using stored results of
previous iterations.  This is why strength reduction and related
techniques are crucial for performance.

<p> <LI> Given a program <i>f</i> and an input change operation
<i>+</i>, a program <i>f'</i> that computes <i>f(x+y)</i> efficiently
by using the result of the previous computation of <i>f(x)</i> is
called an <i>incremental version</i> of <i>f</i> under <i>+</i>.
Sometimes, information other than the result of <i>f(x)</i> needs to
be maintained and used for efficient incremental computation of
<i>f(x+y)</i>.  We call a function that computes such information an
<i>extended version</i> of <i>f</i>.  Thus, the goal of computing
loops efficiently corresponds to constructing an extended version of a
program <i>f</i> and deriving an incremental version of the extended
version under an input change operation <i>+</i>.

<p> <li> In general, incremental computation aims to solve a problem
on a sequence of inputs that differ only slightly from one another,
making use of the previously computed output in computing a new
output, instead of computing the new output from scratch.  Incremental
computation is a fundamental issue relevant throughout computer
software, e.g., optimizing compilers, transformational program
development, and interactive systems.

</OL>

<P> <HR> <P>


<h3>Results</h3><P>

<!Comment: following is an ordered list >
<!Comment: each new item in the list starts with a 'LI' at the left margin >

<OL>

<li> Thus far, we have partitioned the problem of deriving incremental
programs into three subproblems:
<p>
<ul>

<li> <b>P1.</b> Exploiting the <i>result</i>, i.e., the return value,
of <i>f(x)</i>. 

<p>
<li> <b>P2.</b> Caching, maintaining, and exploiting <i>intermediate
results</i> of the computation <i>f(x)</i>.

<p>
<li> <b>P3.</b> Discovering, computing, maintaining, and exploiting
<i>auxiliary information</i> about <i>x</i>, i.e., information not
computed by  <i>f(x)</i>.

</ul>
<p>
We summarize here the essence of our methods:
<p>

<li><b>P1.</b> In <a
href="ftp://ftp.cs.cornell.edu/pub/yanhong/Inc-SCP95.ps.Z">
"Systematic Derivation of Incremental Programs"</a>,
we gave a systematic transformational approach for deriving an
incremental version <i>f'</i> of a program <i>f</i> under an input
change <i>+</i>.  The basic idea is to identify in the computation of
<i>f(x+y)</i> those subcomputations that are also performed in the
computation of <i>f(x)</i> and whose values can be retrieved from the
cached result <i>r</i> of <i>f(x)</i>.  The computation of
<i>f(x+y)</i> is symbolically transformed to avoid re-performing these
subcomputations by replacing them with corresponding retrievals.  This
efficient way of computing <i>f(x+y)</i> is captured in the definition
of <i>f'(x,y,r)</i>.

<p> <li><b>P2.</b> In 
<a href="ftp://ftp.cs.cornell.edu/pub/yanhong/Cir-PEPM95.ps.Z">
"Caching Intermediate Results for Program Improvement"</a>,
we gave a method, called <i>cache-and-prune</i>, for statically
transforming programs to cache all intermediate results useful for
incremental computation.  The basic idea is to (I) extend the program
<i>f</i> to a program <i>f-bar</i> that returns all intermediate
results, (II) incrementalize the program <i>f-bar</i> under <i>+</i>
to obtain an incremental version <i>f-bar'</i> of <i>f-bar</i> using
our method for P1, and (III) analyze the dependencies in
<i>f-bar'</i>, then prune the extended program <i>f-bar</i> to a
program <i>f-hat</i> that returns only the useful intermediate
results, and prune the program <i>f-bar'</i> to obtain a program
<i>f-hat'</i> that incrementally maintains only the useful
intermediate results.

<p><p> <li><b>P3.</b> In 
<a href="ftp://ftp.cs.cornell.edu/pub/yanhong/Dai-POPL96.ps.Z">
"Discovering Auxiliary Information for Incremental Computation"</a>,
we proposed a novel approach for finding auxiliary information.
Auxiliary information is, by definition, useful information about
<i>x</i> that is <i>not</i> computed by <i>f(x)</i>.  Where, then, can
one find it?  The key insight of our proposal is: <p> <ul>

<b>A.</b> Consider, as candidate auxiliary information for <i>f</i>, all
intermediate computations of an incremental version of <i>f</i> that
depend only on <i>x</i>; such an incremental version can be obtained
using some techniques we developed for solving P1 and
P2. (We use techniques developed for solving P1 and P2,
instead of just P1, so that the candidate auxiliary information
includes auxiliary information useful for efficiently maintaining
the intermediate results.)
</ul>
<p>
How can one discover which pieces of candidate auxiliary information
are useful and how they can be used?  We proposed:

<p>
<ul>

<b>B.</b> Extend <i>f</i> with all candidate auxiliary
information, then apply some techniques used in our methods for P1 and
P2 to obtain an extended version and an incremental extended version
that together compute, exploit, and maintain only useful intermediate
results and useful auxiliary information. 

</ul>

<p>
<li>Thus, on the one hand, one can regard the method for P3 as an
extension to methods for P1 and P2.  On the other hand, one can regard
methods for P1 and P2 (suitably revised for their different
applications here) as aids for solving P3.  The modular components
complement one another to form a comprehensive principled approach for
incremental computation and therefore also for efficient iterative
computation generally.  Although the entire approach seems complex,
each module or step is simple.

<p><li>
In <a href="ftp://ftp.cs.cornell.edu/pub/yanhong/Cachet-KBSE95.ps.Z">
"CACHET: An Interactive, Incremental-Attribution-Based Program
Transformation System For Deriving Incremental Programs"</a>
we describe our prototype implementation of these ideas.

</OL>

<P> <HR> <P>