axiom-developer
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [Axiom-developer] RE: algebra Makefiles with explicit dependencies,


From: Bill Page
Subject: RE: [Axiom-developer] RE: algebra Makefiles with explicit dependencies, bootstrap, fixed-points etc.
Date: Sun, 9 Jan 2005 16:05:53 -0500

Steve,

On Sunday, January 09, 2005 1:22 AM you wrote:
> 
> On Sat, Jan 08, 2005 at 10:21:34PM -0500, Bill Page wrote:
> > I am not sure I understand what you mean by a `compilation
> > model' in the case of a language like Axiom. Could you suggest
> > some relevant references?
> 
> I don't have any references, unfortunately. The thought I have
> in mind is really no more than an axiom specific `make'. In
> allowing the compiler do the bookkeeping, we could automagicly
> resolve dependencies and have a trusted logic to achieve the
> `fixed point' state. I used the term `compilation model' since,
> however the process proceeds, we need a tight definition of what
> actions the compiler will perform, how it finds source files,
> etc. We might only need enough logic in the compiler itself to
> produce appropriate error messages which could be captured and
> parsed by the interpreter or some other process. 

When you said "compilation model" what came to my mind is
something analogous to but much more general than, say the
solution of a set of linear equations by an algorithm like
Gaussian elimination. I.e. the compiler would have to recognize
the specific form of the recursion and transform it to an
equivalent problem with an easily computed solution.

I do not know of any such general "automagic" that would apply
to a language as general as Axiom. Dealing with mutual recursion
is much more complicated than just resolving dependencies.

But as a "brute force" method I think that the kind of iteration
that I implemented to find the current problem can also serve
(for now at least) as it's general solution. Thankfully computer
hardware is now so far advanced that compiling Axiom no longer
takes a week and the prospect of having to re-compile the Axiom
algebra two or three times in order to find the fixed point is
not such a heavy prospect. The current fixedPoint script does
this in about 6 hours on my 2.4 GHz. 512Mb. machine.

If have been thinking if it would be worthwhile to try to take
advantage of a complete set of dependencies in order minimize
the work needed during each iteration. Right now I simply blow
away all the generated code at each iteration and rebuild
everything. Strictly this is probably not necessary. Instead
one might attempt to find only the strongly connected components
in the dependency graph and use them to form a conventional
dependency lattice. Iteration is strictly only necessary within
each component.

I haven't done a formal analysis (Does anyone have a suitable
implementation an efficient graph algorithm that could find
the strongly connected components of a graph of about 1,500
nodes and an average degree of about 10 - 15 arcs?) but my
impression is that the Axiom algebra code is already so inter-
connected that this procedure might not yield much advantage.
Furthermore, it is necessary that the dependency graph itself
be determined dynamically. This is possible, but it would
further complicate each iteration.

Therefore as I originally explained to Tim, I think the best
approach would be to provide "bootstrap" lisp code for *all*
of the Axiom spad files. Then during the build, the initial
bootstrap version of Axiom would be built directly from only
the bootstrap lisp files. Since this involves only lisp
compilation, it would considerably faster than compiling the
spad code. Then the first iteration of the build would be to
simply compile all of the spad files as we do now. If all of
the generated lisp code matches the bootstrap lisp code, then
we are done. If not, then we need to update the cached lisp
code and repeat the iteration until convergence is reached.
In this case there is no need to worry about dependencies at
all.

As I have said previously however, I do not think that it would
be easy to prove that this brute force iteration method will
necessarily find a fixed point, let alone a least fixed point.
If the Axiom language contained only functional constructs then
perhaps this might be formally possible. I think it would make
a great programming language research topic. But in practice,
I do not think that the lack of proof of convergence of the
simple iteration procedure is likely to cause any problem.
After all, Axiom has existed as a viable programming environment
for quite some time apparently without even recognizing that
there was a (potential) problem.

> 
> No matter how I think of the problem of dependencies in terms
> of a `build' procedure, I'm always compelled to regard it as
> a language issue. We are currently defining mutually recursive
> structures in a language which, strictly speaking, does not
> support them!

Yes, that is quite interesting isn't it? I wonder if this has
been recognized before by previous Axiom developers? It seems
that Axiom has always been on the leading edge of programming
language development - so much so that sometimes I think the
developers did not even know how advanced they were. Axiom had
the basis of a object-oriented design even before the concept
had a name.

I think it would be a good idea right now to formally recognize
that Axiom's algebra is specified in a mutually recursive manner
and even to encourage it's further use. I think Tim's example
of the coding of `one?' function is a particular good example
as to why this is a good idea from the point of view of the
Axiom language. It does seem quite unsatisfactory to me to be
forced to specify such a basic equality in terms of lisp
primitives.

> 
> > Here are some references on mutual recursion that seem
> > quite relevant to me;
> 
> Thank you very much for pointing these out! I will look them
> over this weekend.
> 
> I regard axiom as a particular implementation of a general
> philosophy on how to do computational math. Trying to work
> towards a new compiler/language, I think, has some great
> benefits. It would be great fun :) It motivates one to study
> the existing implementation, which in turn motivates maintenance
> and improvement of the existing system. And of course there is
> all the benefits to the scientific community (despite the
> apparent lack of funding for such work, I don't consider the
> area of CAS design a solved problem! :).
> 

I agree enthusiastically and I sincerely hope that we can somehow
attract the interest of other CAS developers, the current Aldor,
Haskel and Ocaml developers in this issue.

Regards,
Bill Page.





reply via email to

[Prev in Thread] Current Thread [Next in Thread]