Re: [Axiom-developer] Lazy re-evaluation (was: More AxiomUI)

[William Sit]

Bill:

This is Part III. History, and Lazy Re-evaluation

> >> Should this be a front-end browser function or a back-end Axiom
> >> function. For example a function in Axiom might be able to return
> >> the list of input history numbers of those commands that need to
> >> be re-executed.
> >
> > This is unreasonable. The purpose to edit earlier input lines may
> > also rearrange the order of execution of the lines. Only the user
> > knows what order of execution is needed for his/her purpose.
> 
> I disagree. Given Axiom's history of the commands that have already
> been executed and a list of the modifications to the input lines
> (contents of the browser page), it is quite possible to determine
> the minimum number and order of (re-)execution and/or execution of
> new commands that is required to compute a consistent state.
> 

First, as I pointed out previously, Axiom's history command does not
discriminate between syntax-valid and syntax-invalid commands, nor does it know
whether some commands as just for "testing the water" purposes. The user must,
after saving the input lines, editing the file. Axiom can be modified to remove
the syntax-invalid lines, but it still has no way to know the intention of the
user.

What you have in mind is not for a browser interactive session. Rather, if the
action involved is 

(1) read an input file and run it
(2) after seeing the results and not satisfied, use an external editor     to
modify the input file
(3) read the edited input file and run it

This is the full "roll back" model. This setting separates the issue of LRE from
browser-editing issues (I think these are separate and independent issues; Maple
confuses the two, see Part II). This does not forbid editing done within the
same browser, as long as it is a separately spawned process (much like editing
Wiki pages now). Then I would agree that Axiom may be able to detect the
difference and perform lazy-re-evaluation.

In your example, say the first input file (labels not part of the input) is:

(1) a:=1
(2) b:=a
(3) a:=2
(4) c:=a+b

where $c$ gets the value 3, and the edited file is

(1') a:=1
(2') b:=a+1
(3') a:=2
(4') c:=a+b

where $c$ gets the value 4. In running the edited input file, if
lazy-re-evaluation (LRE) is applied, one has to decide whether the (1') is
re-executed. This depends on whether Axiom cached the rhs of (1). Now at the
time (1) is run, is there any reason for Axiom to cache the rhs of (1)? I would
say no. (Note, caching the rhs of (1) is not the same as bounding $a$ to the rhs
of (1); in bounding, there is no way to get to the rhs of (1) again without
re-evaluation. Referencing $a$ is not an option because $a$ may have been
rebound by the time (1') is executed.)

Assuming that, then there has to be a switch to instruct Axiom to cache or not
to cache rhs. Let's continue and assume that the rhs of (1) is cached and say
(1') is done by LRE, that is, $a$ is rebound to 1, without re-evaluating the rhs
of (1). The rhs of (2') is now recompiled and evaluated, binding $b$ to the
value 2.
(3') is also done by LRE. Now it gets interesting. (4') is the same as (4). So
accordingly, one may be tempted to use LRE, that is, used the cached value of
the rhs of (4), which is 3. But that is clearly wrong. So the LRE algorithm must
not just cache the value of rhs, but also track dependencies and the states. It
must determine that the $a$ on the rhs of (4') is the same as the $a$ of (4),
which means that a *history* of $a$ be maintained, not just the current state.
That is, it must know from (3) and (3') that the two $a$ at different times have
the same value. Similarly, it must know that the two $b$ in (4) and (4') have
different values. 


This is a very simple example. In more complicated situations, the value of $b$
may have been rebound as side-effects (as in (2) and (2') having the form
d:=f(a,b)). Not only must the LRE algorithm detect these situations, it must
also maintain other commands the user made in between the two reads, which could
also have modified some of the varibles explicitly appearing in the input files.
There is obviously trade off between this overhead on recomputations.
Experts in LRE probably have all this figured out, but to a casual user, who
most likely would not understand this behind the scene actions, the displayed
results may be very baffling and confusing (Maple is such an example already,
and we have seen lots of examples in Axiom due to lack of understanding of
types).

As far as users are concerned, most need not know the details of implementation
or how the results are arrived at, as long as they are what are expected. I
think this is a very important design principle for user interfaces.

In developing a final input file that may be used again and again with minor
changes to embedded parameters, the user wants an environment that each time the
input file is run, whether this is from a fresh session or during the middle of
one, the results should be identical to one from a fresh session. The easiest
way to assure this is to include ")clear all" at the beginning of the file,
which would defeat most of the advantages or efficiency gains by LRE.

William