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. _______________________________________________ Axiom-developer mailing list Axiom-developer@nongnu.org http://lists.nongnu.org/mailman/listinfo/axiom-developer
