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

[Page, Bill]

William,

I am sorry that this is a rather long email, but I think this is
an important subject that has not yet been properly dealt with
in any computer algebra system.

> Bill Page wrote:
>> ... both Tim Daly and William Sit assure me that the old Axiom
>> Hypertex browser already implements this kind of dependency
>> tracking. That is apparently the purpose of the \free{} and
>> \bound{} attributes embedded the Axiom commands contained in
>> the hypertex pages.
>> 
>> I would prefer to call this something like "lazy re-evaluation".
>> 
>> I think it is notable that neither Maple nor Mathematica have
>> lazy re-evaluation in their standard worksheet interfaces.

On Wednesday, June 22, 2005 10:20 AM William Sit wrote:

> I am not sure what you meant by "lazy re-evaluation" here (or it
> could be my ignorance about the concept).

"Lazy re-evaluation" is a concept that has been discussed in the
context of discrete event simulation, parallel computation and
transaction processing roll-back in databases systems. See for
example:

An Efficient Implementation of Lazy Re-evaluation
Avinash C. Palaniswamy, Sandeep Aji, and Philip A.
http://portal.acm.org/citation.cfm?id=306961

"Lazy Reevaluation is a technique designed to reduce unnecessary
re-compilation after processing a rollback event. That is, if an
event e causes rollback and the processing does not alter the
process state, then the process can jump over the events that it
has already processed."

Also related to "mostly functional" programming:

Worlds in Collision: A Mostly Functional Model of Concurrency
Control and Recovery

http://home.pipeline.com/~hbaker1/TreeShadow.html

"We therefore advocate a style of programming called "mostly
functional programming". Unlike purely functional programming,
which attempts to completely finesse  the issue of state, we
realize that state is an essential part of the "real world"
and must be dealt with. For example, synchronization of two
processes requires at least one bit of state--which process
arrived first--and so state cannot be avoided in a parallel
system which performs any communication. Since state is a
"necessary evil", we seek to control it by making it accessible
and utilize state-accessing and state-changing operations as
sparingly as possible."

> Mathematica has two modes of assignments: SetDelayed (:=) for
> functions and Set (=) for immediate evaluation and so does
> Axiom: macro (==) and assign (:=). Both SetDelayed and macro can
> be used to define *any* identifier, not necessarily a function
> (just think of it as function without arguments although there
> may be a minor difference: "x == ..." instead of "x() == ...").
> Each time an identifier defined using SetDelayed or macro is
> referenced, it is recomputed in Set or assignment (and in SetDelayed
> or macro when these are computed), and this occurs recursively
> until all identifiers at the "leaves" are resolved with Set or
> assigned values. The SetDelayed or macro defined identifiers have
> no "values" associated and the values are computed on demand.

In Maple this is written as

  x := '....';

The use of quotes prevents evaluation so that x literally represents
the expression enclosed in quotes instead of it's "value".

> Do you consider this delayed computation lazy re-evaluation? [I put
> "values" in quotation because the word value can have different
> meanings at different levels; at a functional level, the SetDelayed
> or macro defined identifiers of course have associated "values".]

No what you describe is usually just called "delayed evaluation". It is a
type of lazy *evaluation*, not lazy *re-evaluation*.

http://en.wikipedia.org/wiki/Lazy_evaluation

"Delayed evaluation is used particularly in functional languages. When
using delayed evaluation, an expression is not evaluated as soon as it
gets bound to a variable, but when the evaluator is forced to produce
the expression's value."

Lazy evaluation in functional programming languages usually means
something more than just delayed evaluation. For reasons of
efficiency it also involves "updating" or caching of values. As
far as I know, Axiom does not do this when evaluating the ==
construct but in might apply in the case of Axiom's iterator
expressions. I don't know about Mathematica but I do know that in
the case of Maple it is possible to associate this kind of caching
with function evaluation.

http://computing-dictionary.thefreedictionary.com/lazy%20evaluation

"lazy evaluation - An evaluation strategy combining normal order
evaluation with updating. Under normal order evaluation (outermost or
call-by-name evaluation) an expression is evaluated only when its value
is needed in order for the program to return (the next part of) its
result. Updating means that if an expression's value is needed more
than once (i.e. it is shared), the result of the first evaluation is
remembered and subsequent requests for it will return the remembered
value immediately without further evaluation. This is often implemented
by graph reduction. An unevaluated expression is represented as a
closure - a data structure containing all the information required to
evaluate the expression."

> The above delayed evaluation (which is automatically evaluated when
> needed) only occurs *after* the SetDelayed or macro definitions have
> been executed earlier (known the Axiom's run time system). This is
> different from the hyperdoc browser, which may have only *read in*
> the input file, but *not yet* run any assignment (delayed or otherwise).
> This is like in Mathematica when the you read in a Notebook, commands
> are not executed (unless marked as initialisation cells and the
> system set to automatically run these on loading). Now if a user
> *skipped* some assignments (delayed or otherwise) that, say, defines
> x, y, and *jumped* to an assignment for z that involves x, y, normally
> in the Axiom interpreter, the x, y would be treated as undefined symbols
> and perhaps cause either a syntax error or a wrong evaluation. In
> hyperdoc, the system will know whether x and y are free or bound
> (because these are declared in the input file when it is built for
> hyperdoc from regular input file), it knows to search for their
> definitions and execute those assignments.

I don't see any difference in principle between a 'bound' variable
in hyperdoc and a delayed evaluation in Axiom. In both case the
definitions are "read-in" but not yet acted upon. It's just that
this is occurring at a different level in the system. There is a
difference however in the case where the command in Axiom is not a
delayed evaluation. In effect in this case the value of a variable
is being updated ("cached" i.e. stored) and should not have to be
evaluated again.

> So the hyperdoc action, as I understand it, is unrelated to
> "lazy re-evaluation" of the first paragraph.

That is correct. 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

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 ... :).

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

>  [spreadsheet interface discussion snipped]

> ...
>> 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.

> However, as you probably know, you can use:
>
> )history )write filename.input
>
> to capture the input lines (if you have ")history on") and edit
> it. However, the resulting .input file captures all input lines,
> including all the ones that did not work due to typos or syntax,
> etc, and so needs to be cleaned.

That is equivalent to the brute force method that is necessary
now with Maple. It is possible to do much better than this!

> What is desirable in the interpreter interface, is the ability to
> edit previous input lines in a 2D way. Mathematica allows it and
> makes it very easy to do quick exploratory computations during the
> development phrase.

2-d editing might be possible if we can use mathML. In that case
it is possible to select displayed 2-d sub-expressions, modify them
with a few keystrokes (e.g. by typing the corresponding linear 1-d
sub-expression). But in general wysiwyg equation editing is often
awkward at best. And input of commands actually involves more
semantics than what is normally explicit in the 2-d display. Both
Maple and Mathematica have invested a great deal of effort in a user
interface that (in principle) allows this. But even after all this
effort, I really don't like to use it. I am too used to the "old" way
of doing it, I guess - using a separate linear 1-d "input syntax"
to type the commands.

> The final order of execution can be done with cut and paste right
> there on screen in the FrontEnd and there is no need to save the
> history into a file first (because the interface *is* the editor
> as well). Maybe an emacs or TeXmacs interface can do that?

The information in the history file is necessary if we want to
perform lazy re-evaluation as I described above.

>> These could be mapped to corresponding output areas in the
>> browser.
>
> A browser (web browser) is not a text editor (yet). In fact, it
> is probably undesirable to make a browser into an editor.

I disagree. Have you tried Kai's AxiomUI demo yet?

> As nice as Wiki is, one still have to edit the source text, rather
> than the rendered text.

That is true, but in most cases I would argue that this is *more
efficient* then 2-d editing of the commands whose output generated
some rendered mathematics.

> In Mathematica, this would be like requiring editing the Notebook
> file in text mode (which one *can* do, even on a cell-by-cell basis).
> I can't imagine editing XML in text mode (I have tolerated editing
> html, including those generated by MS Word or including Chinese, but
> I think direct editing XML is not for me).

It is not expected that an AxiomUI user would edit XML markup. It
is also likely that we can avoid almost all HTML except in the
case of some complex page structures.

> ...
>>> [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.

> 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?"

> (Think about all the "automated" choices MS Word provides --
> I spend more time undoing them than actual writing).

MS Word is a rotten example. I agree that we don't want that!

> I decide by correctly using == and := and recalling inputs.
> 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".

> I would love to have Mathematica FrontEnd working for Axiom
> (the best of both worlds). There are many many features of the
> FrontEnd that are great and unparallelled (to name just a
> few besides those already mentioned: all Notebooks are ASCII,
> include editable input and output, graphics, incorporated style
> sheets, independent of platform or operating systems, can be
> converted into html, tex, etc; the entire Mathematica documentation
> available, with live editable examples, and programmable using
> FrontEnd commands).

Don't get me wrong: I think there are some very good things about
both the Mathematica and Maple user interfaces. But user preferences
for particular worksheet interfaces is a very subjective thing.
Because of the high learning curves it is often dictated largely
by one's individual experience and emotions like product loyalty
(or the opposite of loyalty ;) which are often generated by intense
intellectual investment. Disagreements on user interface design
probably generates just as much or more "heat" then opinions
about programming languages.

Regards,
Bill Page.