RE: [Axiom-developer] letting my mud settle

[Bill Page]

On November 8, 2005 4:55 PM C Y wrote:
> 
> Personally, I would be happier with a system that can be 
> bootstrapped. 

I started writing a long explanation about bootstrapping
and all that, but thanks to the magic of Wikipedia I don't
have to bother, I can just point:

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

and you can instantly find out all kinds of things like the
importance of Robert Heinlein to the concept. :)

More specific to this discussion is:

http://en.wikipedia.org/wiki/Bootstrapping_%28compilers%29

The design of bootstrapping compilers has a long and
venerable history and Axiom happens to be one of these
types of systems.

> 
> > I think that William Sit is right that having accomplished
> > this bootstrap, it seems unnecessary to continue to distribute
> > Axiom in this way. It is now quite possible to return to the
> > way Axiom used to be distributed as binary code plus source
> > code. Building open source Axiom would then require a running
> > version of open source Axiom in exactly the same way that
> > building gcc from source code requires a running gcc.
> 
> What about a platform that has no running Axiom binary?  gcc,
> IIRC, solves this by a rather convoluted process called cross
> compilation?

No. Cross compilation is a simple and common operation.

This is essentially the situation that Tim was in when he
first received the Axiom source code for the open source
distribution and cross compilation was the method by which
he solved that problem. He used Axiom (actually just parts
of Axiom) running on another system to generate the lisp
code that he then copied to the open source distribution so
that those algebra modules that needed to be present before
the rest of the library could be compiled, could first be
compiled from the lisp code. Of course it wasn't quite that
simple - some hand coded changes to the machine generated
lisp code was necessary because the target lisp environment
was not the same as the lisp on the host machine.
 
> It would be nice not to have to worry about such issues
> for Axiom - why not keep the design goal of building Axiom
> using only a working ANSI Lisp?

Because that means having to maintain two versions - a lisp
version and a spad version of quite a few Axiom library
modules. And if changes are made to any of the spad code in
one of these modules, the lisp code must be re-generated.
All of this is well described in Tim's documentation.

If we could return to the original way of building Axiom,
then this error-prone process is not required.

> 
> > Since this thread is at least partly devoted to "airing
> > dirty laundry", I should mention that in retrospect I think
> > the specific way in which Axiom algebra was bootstrapped
> > from source, i.e. by including machine generated lisp code
> > from Spad compiler output directly in the pamphlet files was
> > probably not the best idea.
> 
> Well, a cleaner solution would be nice, but hopefully rewriting
> the source in Lisp would allow us to unknot this situation.

No. I think you must not understand what I said above. The
Lisp code is part of the bootstrap. It does not in anyway
"unknot" the situation.

> 
> > At the time Tim made this decision I was not really part of
> > the project and even if I had been I would not have understood
> > then that there was a better way. But now it is clear to me
> > that the cyclic dependencies in Axiom's library code are a
> > result of the fairly extensive use of mutual recursion, i.e.
> > source modules that naturally recursively depend on each other.
> 
> This bothers me in principle.  Why is this necessary?  I for
> one would prefer to change this situation, if it can be changed.
> Chicken-egg situations are seldom desirable.

Sigh. I feel like we have already been around this circle
several times... :) Well, I suppose it might be considered a
rather difficult concept, so it doesn't hurt to try to say it
all again another way ... see below. I hope you don't mind that
this email is a rather long as a result.

> 
> > This may not have been especially obvious even to the original 
> > Axiom developers since Axiom had always previously been built
> > from an existing running version of Axiom and the algebra code
> > was written over a fairly long period of time.
> 
> I worry about a case in the future in which the Axiom code
> might have to be built without any working binaries of Axiom -
> what happens then? We've already seen the pain this situation
> caused once.
> 

Axiom is open source, like gcc and gcl. So you might as well be
saying: what happens if we want to build Axiom and we have no C
compiler or lisp system?

Actually, I don't think it could have been that painful - just
a lot of tedious work. But I should let Tim speak to that. I
know that determining which modules to use in the bootstrap
was not easy because that means essentially having to do a
topological sort of the dependencies among the 1,300 modules
and finding the cycles. Tim used a simple but tedious process
to do this that probably did not result in an optimal (smallest)
set of bootstrap modules. But that is a minor detail.

> > In theory the better way, instead of patching in the lisp
> > output of a previous version of Axiom, would have been (and
> > which still may be) to compile Spad "stub" files consisting
> > only of the initial code with all dependencies removed, for
> > those Spad files which had been specially selected to break
> > the dependency cycles - or for that matter, even compiling
> > all existing Spad files - first as "stubs' and then a second
> > time in their full source form.
> 
> If a "stub" file satisfies the dependency requirement, is there
> really a circular dependence in the first place?  Maybe I'm not
> understanding how that really works.

No, the "stub" does not really satisfy any dependencies, it is
really just a like an empty "place holder" the same way the lisp
bootstrap code is now. As the last steps of the build cycle (just
as is done now) these place holder modules are re-compiled directly
from the Spad code. In the current build process all of the
bootstrap modules are compiled twice - first as lisp routines
and finally as Spad routines. That completes one full cycle.
Usually that is all that is done. But as the analysis that I
referred to below shows this is not quite enough since some
to the dependencies do cycle back to affect code that has
already been compiled. However we believe (but have not proven!)
that this affects only some of the optimization that the Spad
compiler would have done and not that actual semantics of the
programs.

The idea of a Spad stub module is not my idea. I think it was
first mentioned by Peter Broadbery in

http://lists.nongnu.org/archive/html/axiom-developer/2005-01/msg00519.html

He wrote:

"Much of the circularity comes mainly from exported signatures -
It _may_ be possible to statically determine all the type signatures
from the .spad files, write out as a bootstrap definition, then
compile against these definitions."

That is what I meant by "stub".

>  
> > We have previously discussed this extensively as part of the
> > thread:
> > 
> > http://wiki.axiom-developer.org/17AlgebraBOOTSTRAPFixedPoint
> > http://wiki.axiom-developer.org/MutualRecursion
> > 
> > I think that recognizing this is important because it is
> > really a **feature** of the Spad language and the Axiom algebra
> > library in particular. It is not a *problem* as such, but rather
> > a challenge for the compiler developers. Aldor at least partially
> > addresses this through it's "extend" mechanism.
> 
> Circular dependence is a feature?  I'm afraid I'm not following,
> if I understand you correctly - how can this be an advantage?

Yes it is an advantage - quite a major one. Of all of the things
that I have studied while learning about Axiom, this is the one
things about which I am still most excited. I have to admit that
I do not fully understand all of the implications yet. But the
idea is really very simple.

Consider for example the problem of solving a system of linear
equations:

  1)  y = a1 x + b1

  2)  x = a2 y + b2

Each of these equations might make perfectly good sense in
it's own context. In the first case we assume x is known and
we just need to compute y. Or in the case of 2) we assume y
is known and we need to compute x. But taken together these
are circular!

Actually the formal relationship between solutions of equations
and mutual recursion is a very general one that is worked out
in some detail in a book called "Vicious Circles" by Barwise and
Moss, to which I have referred before on several occasions.
This kind of circularity can easily be confused with the
idea of "circular logic" which is a kind of logical fallacy.
But really it has more in common with the idea of "positive
feedback" in the context of automatic control systems in
engineering. The right kind of positive feedback can lead to
a stable solution (also called a fixed point).

So this is the lesson: Circularity is often a *good* thing,
because it allows us to specify what we want very simply and
clearly, but it implies the need for a *solution*.

One of the ways of trying to solve this circularity is just
to "break" it by starting with a good (lucky?) guess for x
in step 1). Then when we come to step 2) and actually calculate
x from the y that we calculated in step 1) we will find that
it is the same (or maybe almost the same). If it is not quite
the same, then we can trying feeding the answer from 2) back
into 1) and try again. This is exactly analogous to the situation
that we are in with respect to the Axiom algebra library.

It turns out that unlike the case of the circularity in a
system of linear equations where using a guess and simply
repeating the calculation will not work very well, in most
(maybe all?) cases of circularity in the Axiom library, this
process does seem to lead to the exact and stable solution
after going 3 times around the loop, i.e. re-compiling all
of the Axiom library code three times, each time feeding the
bootstrap that results from the final stage of each cycle,
back into the start of the next cycle.

Is this clear? Can you see what the implications of this
are and why I think it is both a *feature* (answer: because
it allows the Axiom library code to be written in a manner
that is simpler and more self-contained, module by module)
and also something about which we have to be rather careful
(answer: because this circularity implies the need for a
solution strategy)?

If not, then I am certainly willing to try to answer questions,
because I am convinced that understanding this is important
to the overall design of Axiom.

Regards,
Bill Page.