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

[William Sit]

Bill:

This is Part II. Re-evaluation (focusing on what needs to be recomputed) and bad
2D editing in Maple

> Re-evaluation is a little different. It involves a
> series of operations (transactions) which have already altered the
> state of the program, i.e. a series of updates. Like this:
> 
>   (1) -> a:=1
>   (2) -> b:=a
>   (3) -> a:=2
>   (4) -> c:=a+b
>   ...
> 
> At the end of this sequence of commands the state of Axiom is
> given by
> 
>   )display values
> 
>    Value of a: PositiveInteger:  2
>    Value of b: PositiveInteger:  1
>    Value of c: PositiveInteger:  2

My understanding (and I actually run this in Axiom and Maple -- assuming the
code is Axiom code; or Maple if semicolons are added at the end) is $c$ should
have value 3, not 2. That is, the state of the identifier $a$ has changed, but
not $b$ when $c$ is computed. Perhaps this is just a typo in your last line
above?

(1) -> )set mess autoload off
(1) -> a:=1

   (1)  1
                                                        Type: PositiveInteger
(2) -> b:=a

   (2)  1
                                                        Type: PositiveInteger
(3) -> a:=2

   (3)  2
                                                        Type: PositiveInteger
(4) -> c:=a+b

   (4)  3
                                                        Type: PositiveInteger
(5) -> )display values
   Value of %: PositiveInteger:  3
   Value of %e:  (none)
   Value of %i:  (none)
   Value of %infinity:  (none)
   Value of %minusInfinity:  (none)
   Value of %pi:  (none)
   Value of %plusInfinity:  (none)
   Value of SF:  (none)
   Value of a: PositiveInteger:  2
   Value of b: PositiveInteger:  1
   Value of c: PositiveInteger:  3

> Now think of these commands, (1), (2), ... as editable text embedded
> inside an Axiom "worksheet" e.g. displayed on a page of the new
> AxiomUI browser. The user decides that they want to change command
> (2) to read:
> 
>   (2) -> b:=a+1
> 
> The simplest thing (but not the most efficient thing) for us to do
> in this case is just to scrap the state of the whole calculate
> 
>   )clear values all
> 
> (i.e. roll-back) then re-do all four commands again.
> 
>   (5) -> a:=1
>   (6) -> b:=a+1
>   (7) -> a:=2
>   (8) -> c:=a+b
> 
> This is what one must do now for example in Maple. There is even a
> special button labeled !!! that performs the ')clear all' (reset;)
> and re-execution in one click. (and then wait ... :).

In Maple 9 (on a Mac OS X), when I go to the second line and modify it to 

   b:=a+1;

Maple returns the answer b:=2 (leaving the old answer 1 below it).

Maple does not support 2D editing that well. The "wait" can be interrupted by
clicking on a menu bar item. In any case, lines (3) and (4) are not
re-evaluated, but the displayed result suggests that (1) is re-evaluated. Worst,
if I now move the cursor to line (4) and re-execute this, the value of $c$ is 4,
which means that $b$ is not re-evaluated when $a$ has changed. The means that
the definition of an identifier in Maple is tied to its *position* in the input
sequence! In other words, editing a previous line is *different* from
re-entering it with the same edited command. Yuck!
 
> A lazy re-evaluation on the other hand would recognize that after
> changing command (2) the minimum number of commands that need to
> be re-executed so that the state of Axiom is consistent with the
> revised browser page is just these two:
> 
>   (5) b:=%%(1)+1
>   (6) c:=a+b

The automation of this is exactly what I was afraid of. In your (and Maple's)
interpretation of the user's changing (2) b:=a  to (6) b:=a+1, it is assumed
that a total "roll back" is what the user has in mind. It did not take into
account what the next computation the user wants to do after this change.   In
Maple, if the user follows (4) with

  (5)' b:= a + 1         %% newly entered (semicolon omitted)
 
  (6)' c:= a+b           %% re-entered

Then the value of $b$ is 3, and of $c$ is 5 because $a$ is bound to 2 (same for
both Axiom and Maple). Axiom does not have 2D editing, fine. In Maple, if the
user now goes to (4) and re-execute, it gives the value 5 (so it is not a "roll
back", which would give 4). Very confusing in Maple. I don't want Axiom to
imitate that.

In Mathematica (using Set (=)  for :=), when (2) is changed to $b$ = a+1, b gets
the value 3, reflecting that $a$ has changed. If the user wants to do a roll
back, then it is easy to select all the cells involved and do a shift-enter,
which would give the final $c$ to be 4. This is very consistent and intuitive.
The control is in the hands (er fingers) of the user, not Mathematica. If Axiom
is to have a 2D input-editing capability, and I think this should be a high
priority, then I much prefer it to imitate Mathematica.

What you have illustrated with (5) is only that in computing:

  (1) a:=1
  (2) b:=f(a)   %% f is any previously or explicitly defined function of a

then it would be efficient to evaluate this as

  (1) a:=1
  (2) b:= f(%%(1))

to avoid re-evaluation of the right hand side of (1). But in Axiom, := is
immediate assignment, $a$ already is bound to the value of the right hand side
(evaluated). There is not much difference in efficiency between b:=f(%%(1)) and
b:= f(a) at the time (2) is executed; in neither case is the rhs of (1)
re-evaluated. 

The situation would be different if (1) is a == 1 instead. Then detecting that
the left hand side of (1) has not changed would perhaps save time.

> 
> > ...
> >>> [clip nice example]
> >> Bob McElrath wrote:
> >>> A user interface could choose to highlight out[1] as needs-
> >>> recomputing, or just go ahead and do it. (spreadsheet-style)
> >>
> >> I think it would be pretty neat if the browser could do such
> >> highlighting and very useful if with one click you could ask
> >> Axiom to minimally recompute just those comands that need
> >> re-computing. This should be quite easy in principle using the
> >> kind of AJAX techniques that Kai mentioned elsewhere. The hardest
> >> part would be writing the Axiom code that dynamically computes
> >> the dependency tree.
> >
> > Am I missing something here? Can't one simply use == and := to
> > achieve the same thing already?
> 
> I think you are *definitely* missing something ... :). I don't
> see what == and := have to do with this.

Consider the example below:

(1) -> a:=1

   (1)  1
                                       Type: PositiveInteger
(2) -> b==a
                                       Type: Void
(3) -> a:=2

   (3)  2
                                       Type: PositiveInteger
(4) -> c==a+b
                                       Type: Void
(5) -> c
   Compiling body of rule b to compute value of type PositiveInteger
   Compiling body of rule c to compute value of type PositiveInteger

   (5)  4
                                       Type: PositiveInteger
(6) -> b==a+1
   Compiled code for b has been cleared.
   Compiled code for c has been cleared.
   1 old definition(s) deleted for function or rule b
                                       Type: Void
(7) -> c
   Compiling body of rule b to compute value of type PositiveInteger
   Compiling body of rule c to compute value of type PositiveInteger

   (7)  5
                                       Type: PositiveInteger

I think Axiom does not recompute the identifier $a$ each time. I do not need
select cells (lines) to make Axiom (re-)evaluate what needs to be re-evaluated
to get $c$. It knows because I declared $b$ to be recomputed each time. Note
that in (6),  the code for $c$ is already cleared (and so is the code for $b$).
Axiom *knows* dependency, much better than Maple. But $b$ is not compiled in
(6). This is certainly lazy. They were only recompiled when I force the
evaluation of $c$ (but $b$ was automatically recomputed). Actually, for real
efficiency, there is no need to recompile $c$, only relinking.

Too bad that in Axiom, the following would not work, although in principle, it
should, with some higher level values on the rhs of assignments:

dpol == ODPOL FRAC INT
w == makeVariable('w)$dpol
w.5

Both == have to be replaced by :=. I don't know if this is a bug or not,

dpol:=ODPOL FRAC INT
w == makeVariable('w)$dpol
w.5

Even though w is defined, the system could not find the function w because the
interpreter is looking for w in a library!

But the following works.

dpol := ODPOL FRAC INT
w() == makeVariable('w)$dpol
w().5

So there is some subtle difference between w and w() after all.

[comment on MS Word, snipped] 
[below quotation moved out of sequence]
 
> > What may be needed and would be extremely helpful in terms of
> > user experience, is again what Mathematica allows: 2D editing,
> > with multiple selection of cells, not necessarily adjacent,
> > and then one shift-enter does it.
> 
> "Selection of cells" is essentially what Bob and I were discussing
> above that you seemed to "miss".

If that is all I missed, no problem. I did address this! However, I think you
missed something :-) about == and :=. In using macros or delayed assignment, the
identifier is recomputed each time. May be not by LRE, but Bob did not use the
term LRE above. See Part II on RE and Part III on LRE.

By using ==, I did not imply that the system should not cache repeatedly used
values. In a recursive definition of the fibonacci sequence,

f(1)==1
f(2)==1
f(n | n>2) == f(n-1)+f(n-2)

it would be mightily inefficient if the values are not cached in
[f(n) for n in 1..100]

> 
> > As I commented above, it is *not* Axiom's job to decide for me
> > what needs recomputing and what does not.
> 
> I disagree. To paraphrase what Bob wrote several emails earlier:
> "Why should it be necessary for me to do something complex
> like figuring out an efficient re-calculation sequence when
> this is something that a computer can do very easily?"

In my case, because *I* want to be in the driver seat. Also by being forced to
do so, I understand my algorithm much better. The resulting sequence of
computations will be part of my final algorithm which, for better or worse,
represents my best effort. No matter how efficient this re-calculation is done
by the system, I want a repeatable computation; LRE is not repeatable because it
depends on a history of interaction. See Part III on Maple.

This is not the same issue as efficient implementation of recursion, where I
would *definitely* want the system to handle it.
 




William