Re: Steps towards writing a computer algebra system

From: Julian V. Noble (jvn_at_virginia.edu)
Date: 01/18/05 

Date: Tue, 18 Jan 2005 18:38:56 -0500

Mike wrote:
>
> Hi
>
> I am a self-taught programmer and have always been fascinated with
> computer algebra systems (CAS) such as Mathematica. For a hobby I
> thought that I would like to have a crack at writing my own (very
> simple) CAS but I am rather lost on where to start.
>

Start by writing code to translate algebraic formulas to some useful
internal representation. I have written a fairly elaborate one in Forth
(translates a formula to Forth in usual Forthish RPN form) but there is
no reason you have to make Forth the parse language, or Forth the outpur
language, for that matter. Lisp, C, C++ or AWK would do fine for the parse
language, and assembler or pseudocode, or even a tree structure would be
fine for the target "language". I believe Kruse ("Data Structures and
Program Design") has a program for evaluating numerically an input formula.
That should serve as a guide to how to do it. Several of my Forth FORmula
TRANslators can be found at

   http://Galileo.phys.Virginia.EDU/classes/551.jvn.fall01/programs.htm

You will have to learn how to write finite state machines in whatever language
you choose, unless it has built-in pattern recognizing functions.

Once you can do this, think how to write out the rules for some algebraic
transformation, such as factoring out a common sub-expression, or solving
a linear or quadratic equation in closed form. Then write pseudocode to
translate the rules into an algorithm. At this point you will have
begun to understand what goes into a real CAS.

If you are interested in integer computations, learn how to do arithmetic
with integers of arbitrary length. See Knuth, e.g. for algorithms. You will
need to learn how to represent very large integers compactly. Knuth offers
some insight on this.

Good luck. 

-- 
Julian V. Noble
Professor Emeritus of Physics
jvn@lessspamformother.virginia.edu
    ^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/
   "As democracy is perfected, the office of president represents, more and
    more closely, the inner soul of the people. On some great and glorious
    day the plain folks of the land will reach their heart's desire at last
    and the White House will be adorned by a downright moron."
      --- H. L. Mencken (1880 - 1956)

Relevant Pages

  • Re: A different definition of MINUS, Part 3
    ... as providing a solution to a language implementation problem. ... but closed for the desired expressions of that language. ... I would assume that a computing model is to be ... algebra and a relational computing model is comparable to the ...
    (comp.databases.theory)
  • Re: A different definition of MINUS, Part 3
    ... There you go again attributing references to language implementation to me ... the algebra is not an essential ... While the name of the relvar no doubt has other significance in ...
    (comp.databases.theory)
  • Re: algebra equations for Reference and FD constraints
    ... are both programming language concepts and are not necessarily present depending on the language, eg., some languages don't need assignment. ... Whereas I would say that if one can't express a concept with either an algebra or calculus, then the concept is not a 'model' concept in the first place. ... I suspect Codd used the word 'update' only to give his ideas some familiar link to the sloppy terminology that was in wide play more than thirty years ago and seems to persist, eg., 'file updating'. ...
    (comp.databases.theory)
  • Re: A different definition of MINUS, Part 3
    ... as providing a solution to a language implementation problem. ... For example, if the language has a concept of 'relvar', I want to be able to substitute not the concept, but merely the name of the relvar in an algebraic equation. ... While the name of the relvar no doubt has other significance in a language implementation, its only significance in an algebra is to be a shorthand for some extension. ... This is the algebraic advantage - such language significance is stripped out of the language expressions, leaving only algebraic formulas and equations, removing the otherwise problem of having to make algebraic comparison of results and to deal with some extraneous language 'meaning' at the same time. ...
    (comp.databases.theory)
  • Re: Computer Algebra Algorithms lisp vs. C.
    ... >>in many CAS. ... in a non-standard language like maple language might not work ... Moreover, people using standard ... >>Unlike maple language which is only used by maple, ...
    (sci.math.symbolic)