Re: a unified caching system for avoiding recomputation

--===============1027019986==
Content-Type: multipart/alternative; boundary=14dae9cfcdb84dfdab04c52e2f0f

--14dae9cfcdb84dfdab04c52e2f0f
Content-Type: text/plain; charset=ISO-8859-1

I am not sure if you want more examples, but:

Spreadsheets often carefully avoid recomputation (a.k.a. caching or
memoization)
Gosper's HashLife is an example of clever memoization
Blelloch, Acar and Harper have a couple papers called "Selective
Memoization" and "Adaptive Functional Programming" about memoization and
incremental recomputation that seem (to my idiot eyes) to offer a
programming language theory-based approach to control of memoization (you
can memoize everything and some programming languages do but it's not
usually practical.)

Soar has a form of memoization called chunking that is a little bit
"lifted". Rather than a function computing an output from an input, and
then storing an input/output pair, there's a backtracing step and the thing
that is memoized is a rule that has variables in it - it may be able to
apply to sufficiently similar inputs, a form of explanation-based
generalization. I think it's also a bit like just-in-time compilation.

Just-in-time compilation is an example of selective memoization - the
compiled code (as you mention) is the output of a computation, and keeping
an executable around is a cache. However, you don't necessarily want to do
the compilation step; the heuristics around just-in-time computation are
about how to decide when it would be worthwhile to start a cache.

Johnicholas

--14dae9cfcdb84dfdab04c52e2f0f
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

I am not sure if you want more examples, but:<br><br>Spreadsheets often car=
efully avoid recomputation (a.k.a. caching or memoization)<br>Gosper&#39;s =
HashLife is an example of clever memoization<br>Blelloch, Acar and Harper h=
ave a couple papers called &quot;Selective Memoization&quot; and &quot;Adap=
tive Functional Programming&quot; about memoization and incremental recompu=
tation that seem (to my idiot eyes) to offer a programming language theory-=
based approach to control of memoization (you can memoize everything and so=
me programming languages do but it&#39;s not usually practical.)<br>
<br>Soar has a form of memoization called chunking that is a little bit &qu=
ot;lifted&quot;. Rather than a function computing an output from an input, =
and then storing an input/output pair, there&#39;s a backtracing step and t=
he thing that is memoized is a rule that has variables in it - it may be ab=
le to apply to sufficiently similar inputs, a form of explanation-based gen=
eralization. I think it&#39;s also a bit like just-in-time compilation.<br>
<br>Just-in-time compilation is an example of selective memoization - the c=
ompiled code (as you mention) is the output of a computation, and keeping a=
n executable around is a cache. However, you don&#39;t necessarily want to =
do the compilation step; the heuristics around just-in-time computation are=
 about how to decide when it would be worthwhile to start a cache.<br>
<br>Johnicholas<br>

--14dae9cfcdb84dfdab04c52e2f0f--

--===============1027019986==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

-- 
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
--===============1027019986==--