Questions for using Lisp language to built the computer algebra systems.

On 9/18/07, mrkmhrsh at yahoo.co.jp <mrkmhrsh at yahoo.co.jp> wrote:
>
> I think the most drawback of the computer algebra system built on the Lisp
> system is that since the Lisp system makes so much pointer references
> to make access to the lisp cells it is slow on the pipelined and cached
> systems.


Well, first of all, as Bruno points out, there are other data structures
available in Common Lisp.  And there are certainly some applications of
Maxima which run into performance problems.

It would certainly be possible to implement expression trees using a more
packed representation, especially since Maxima essentially never modifies
trees in place and rarely uses circular list structures (internally, it uses
them in the compar module). This would have advantages (less space, better
pipeline and cache performance in many cases) and disadvantages (no shared
substructures and more copying).  In fact, it would even be possible to do
this using existing Lisp primitives (cons, car, cdr) as long as you're
willing to give up eq-identity of objects (which would break some code, but
actually not a lot), rplaca/d, and circular structures.

(Even the cdr-coding could reduce the pointer references, tagged pointer
> access
> means every reference of pointer can causes the branch or the pipeline jam
> to make the computation slow.


Yes, it would be perfectly possible to implement a cdr-coding system without
modifying the source code at all.  In fact, that's what the Lisp machine
did. It's an interesting empirical question to see whether with current
architectures the overhead of a cdr-coding system would be recouped in
better cache coherence and pipelining. I don't know if the experiment has
been performed -- the original motivation for cdr-coding was not
performance, but mostly memory conservation, because RAM was very expensive
at the time. You might want to write a Lisp system using cdr-coding to see.

You could also imagine a CAS built from scratch using a different underlying
representation.  For example, the rational function package (CRE) could use
vectors in a very natural way.  But that is a particular representation that
is only convenient for some kinds of calculations.  The old Schoonship
system (written in assembler), if I'm not mistaken, used a very packed
representation, which was excellent for problems which fit naturally into
that representation, but not in general.

Do you think writing generic computer algebra system like Maxima using for
> example Fortran9x or Java is too difficult ?


It's only a "small matter of programming".  Rewriting Maxima in Java but
keeping the cons-cell structure would be quite easy, but what would be the
point?  Anything else would be a lot of work, because the current code is
very concrete.  Writing it in Fortran 9x sounds like an exercise in
masochism.

Another drawback is that there are so many Lisp dialects.


Yes, this causes some problems in keeping Maxima working in various Common
Lisps, but rarely impacts the core symbolic functionality.  Mostly it's
about I/O, CFFI, etc.

Common Lisp system as the language contains too many functions defined
> and against the kind of ideas of the "reduced instruction sets" system.


So what?

> I think it might be better that for the maxima to define the minimum
> required set of lisp functions, and then other functions can be defined
> using lisp.


There are many Lisp implementations that do exactly that.

How do you think lisp is so essential or not? (I might be wrong.)


It's certainly not essential in any deep way, but I don't see any compelling
reason to abandon it for Maxima given the existing code base.

            -s

PS Bruno puts Java in the same performance class as Python, which is grossly
unfair.  Good dynamic/JIT implementations of Java can run as fast as C++ in
many cases, sometimes faster, surprisingly enough.