RE: [Axiom-developer] letting my mud settle

[C Y]

--- Bill Page <address@hidden> wrote:

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

Cool!  I'll take a look.

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

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

Heh :-).  OK, I'll stop worrying then.

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

Ah, OK.  So as long as we preserve a copy of this original version with
which to compile future versions, we are in the clear.

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

OK.  I'll try to do some reading.

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

I think I just don't properly understand compiler technology, so I'll
hush up until I know enough to talk intelligently.

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

Sorry!  I don't mean to cause a rehash.  I'll go back and look over the
older discussions.
 
> > > 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?

Not a bad question to ask, actually, but I suppose the answer is so
much trouble and the problem so unlikely as to not be worth worrying
about.

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

Ah.  And even more minor if we aren't going to need to keep
bootstrapping.

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

Hmm.  I take it at some point we should either demonstrate that or
generate a binary using enough cycles so things iterate to steady
state?

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

Got it.

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

If you don't understand all the implications I'm most likely sunk, at
least for a while :-).

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

I think that's what I might be doing.

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

Ah :-).

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

OK.

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

That's the kind of thing it would be nice to have a formal proof of
:-).  Oh, well.  As long as it works.  It sounds a little like running
LaTeX on a document multiple times to get to the final form.

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

I think so.  I'll need to peruse the bootstrapping info.

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

I might have a few, but I'll try and do my homework first.  I would
suggest that both axiom specific bootstrapping information and any
relevant background material be incorporated into the books, as well as
(perhaps) instructions on how to proceed in the (very unlikely!) case
of having to compile Axiom without a working Axiom binary.

Cheers, and thanks for taking the time to answer an essentially
redundant question.

CY


                
__________________________________ 
Yahoo! FareChase: Search multiple travel sites in one click.
http://farechase.yahoo.com