|
Summer of Code: Axiom Projects
Information on Google's Summer of Code project is available
here
- I. DOCUMENTATION
Axiom is documented with 4 books which are under development,
a tutorial, a programmer's guide, a reference volume, and a
developer's guide.
- work on the reference volume of the book
The reference volume is intended to provide complete lookup
coverage of the Axiom system. There are over 11,000 functions
within Axiom which require standardized documentation.
This project would involve visiting each algebra file (approx
300 files) to make a complete listing of all of the function
signatures and their type information. Ideally this should be
automated as the information is available. The output should be
a set of Latex files which will contain boiler-plate documentation.
The Latex output should be able to produce an index for the
reference volume.
- literate documentation
Axiom consists of literate programs. Each lisp, C, Makefile, etc is
written by combining Latex and source code into a Latex document.
At build time the source code and technical paper are extracted from
these documents automatically.
There are several thousand files in Axiom each of which needs to be
understood and properly documented. Choose an algorithm (such as
the greatest common divisor) or an area (such as p-adic numbers) and
provide the required documentation for the algorithms.
- language translation
Axiom is a worldwide project. It is used in multiple countries
and runs on platforms like Red Flag Linux (Chinese). We have
some introductory documentation in French but we need people
who can translate the book into any non-english language.
This requires that you be fluent in both languages. The result
should be a set of latex documents that are a complete translation
of the original material
- Television/DVD presentation
We need to design and script an effective introduction to Axiom
for new users. The most effective way to do this (at least from the
new user's point of view) would be a DVD/TV kind of presentation.
Rather than just a dry presentation of fact we would need to script
a light, fast-moving presentation similar to the courses by
Cerebellum on General Chemistry.
This would require background in areas like video editing, script writing,
production, direction, etc. and would be ideal for a liberal arts person
who wanted to explore educational activities. For an online example view
go-opensource. If done carefully
it could be coordinated with MIT.
MIT's Open Courseware Site has their Mathematics online and some courses,
notably Gilbert Strang's Linear Algebra (18.06) has a complete
video lecture online.
- II. USER INTERFACE
- [AxiomTK]? work on the windows version of the browser and graphics
Axiom can output its equations in many formats such as FORTRAN
or TeX. We need to develop a jsMath output format for browsers.
(see http://www.math.union.edu/~dpvc/jsMath/examples/Henrici.html)
We need to develop a MathML output format for browsers.
Axiom has a browser and a graphics component. Both of these
user interface components are written in C using X11 and are
hard to port to Windows. We're experimenting with methods of
creating a platform independent method of implementing these
components.
Common Lisps can communicate with TK which provides a platform
independent way of displaying graphics. We need to work out the
lisp code necessary to read browser pages and render them as TK
pages
Mathematica has a free reader program which is designed to
show their notebooks. The format for the reader is standard ascii.
We could develop an Axiom output format that would allow us to
create notebooks from Axiom taking advantage of the features of
the Mathematics notebook.
- work on the wiki version of the browser and graphics
An alternative project is to use a browser as the standard front
end to both the Axiom browser and the graphics. We need to
work out the wiki code to use the browser pages directly in
the wiki.
The task is to figure out how to get the wiki to accept the browser
page syntax and how to inline graphics in wiki pages.
- III. SYSTEM BUILDING and TESTING
- develop regression testing
Axiom has several hundred test cases that are run during the
build of the system. Each of these test cases generate output.
Create a systematic way of using this test suite for systematic
regression testing and implement it.
The result should be integrated into the Axiom Makefile machinery.
- develop test cases
Axiom has about 1100 "domains" which include about 11,000
functions. We need to systematically create and organize a
domain-by-domain set of reference test cases with
explanations, boundary cases, etc.
Develop an automated generate-and-test program. Axiom allows
you to select domains and use these to build up types. A systematic
way of constructing types and elements of the types is needed.
Input could be from the databases which contain signature information
for all types and functions. Additionally it would be useful if the
test program parsed the expressions and kept all of the generated
tests in a tree so we could decide issues like coverage. The tree
should be searchable for both function and domain information. There is already software that is very close:
AldorUnit?.
As an example, it is used for testing with ALLPROSE.
- test graphics code
The Graphics component on Axiom has not been systematically
tested. Use the handbook of curves and surfaces to
comprehensively test the graphics routines.
The result should be a set of input files which recreate
all of the graphics in the CRC handbook and a set of bug
reports that document failure cases.
An alternative result is to modify the graphics code to
handle the failure cases. This would require learning the
details of C, X11, and the graphics code.
- IV. NEW FEATURES
- drag-and-drop
Axiom uses Knuth's idea of literate programs as the basic file
format for all of its code. There is a project called Doyen
which needs to be able to drag-and-drop a literate program onto
a running Axiom system and have that code and documentation
automatically added to the system.
Given a literate program that includes axiom algebra code and
some text figure out how to "drag and drop" the paper onto axiom.
that is, figure out how to get the code in the right place, the
makefile to accept the code, the paper in the right place and
integrated into the documentation
The result should be a working demonstration.
- dvi organization
As part of the build process Axiom generates hundreds of dvi
files (output from Latex) that represent the documentation
associated with every source file. Currently these are minimally
organized by directory. The task is to work out an automated way
of organizing these files. One possibility is to organize the
algebra file documentation according to the algebra lattice.
The output should be a program that can be run to create the
proper organization, likely as a Latex file.
- booklet mechanism
Pamphlets use random names in code chunks. Develop a full URL
syntax and create a booklet mechanism. That is, one should be
able to define a chunk as:
<<file:///something>>
and have something inserted inline or ::
<<http:///something>>
and have something inserted inline.
The result should be a rewrite of the booklet command.
- semantic markups
In the future Axiom is intended to allow searches of the
computational literates (such as math papers) based on concepts.
In order to do this we need to develop latex macros for marking
"concepts" in latex files. This will allow the author to mark
up literate programs and math papers and create a concept index,
similar to the word index mechanism latex now uses.
The result should be a latex.sty style file.
- flash integration
Axiom does not know how to dynamically create flash files.
The flash file format is open source.
The task is to develop an interface that will allow algebra
programs to generate flash animation output. An example is to
compute and animate the surface wave of water struck by a
round pebble dropped from a given height.
- V. MATHEMATICAL WORK
- Field Theory Module (a la
FeynCalc)
- Literate Program to implement "Primes is in P" algorithm
Axiom has permission to use the paper "Primes is in P" as
example documentation. This paper is widely known. It has
the theory, a proof of the theory, an algorithm and a proof
of the algorithm. However it lacks an implementation in Axiom.
Implement the algorithm as a literate program (we already have
the paper as a pamphlet file) and integrate it into both the
Axiom documentation and the Axiom sources.
- Symbolic Summation algorithm
There is an algorithm for computing Symbolic Sums but
it is not currently implemented in Axiom. Study this
algorithm and implement it.
The result should be a literate program that can do
symbolic summation in Axiom complete with a test suite.
- CATS, a Computer Algebra Test Suite
There are many different computer algebra systems and they
all develop their own ad-hoc test suites. These suites have
no organizational structure nor any verified results.
The National Institute of Standards and Technologies (NIST)
has a categorization of numerical mathematical algorithms.
A similar categorization does not exist for symbolic math.
The task would involve creating a taxonomy of symbolic
math that provides reference problems with verified results
as well as an implementation for these cases using Axiom.
Note that the taxonomy should not be Axiom specific.
The result would be a taxonomy, the reference cases, the
Axiom cases, and the Makefile machinery to automate testing.
There should also be bug reports filed for failure cases.
- Magnus integration
Magnus is an open source implementation of infinite group
theory algorithms.
These need to be extracted, documented, and implemented
in Axiom
The first result would be the category/domain hierarchy
to support infinite group theory.
The second and continuing result would be the implementation
of the algorithms as literate programs.
- Expand Axiom's set of linear algebra algorithm's to
include symbolic LU decomposition and other missing
common operations.
- Extend the functionality of Axiom's non-commutative
polynomial domains (XPOLY) to permit substitions and
rule-based pattern matching.
- Implement a new Axiom mathematical category of directed graphs
to serve as the foundation for several other projects ranging
from the domain of categories (in the sense of category theory)
to more pedesteran concerns such as data structures operations
on graphs (based on graph theory) and integration of tools for
the efficient display of large graphs (of particular interest
to future maintenance and development of complex dependency
structure of the Axiom library itself).
- Graph the algebra lattice
Axiom has a large type lattice that needs to be documented.
One of the key tools for understanding the dependent relations
would be a graph of the lattice. The current graph would include
about 1100 nodes and, so far, has resisted efforts to construct
a graph.
The result would be a graph, likely using a dynamic visualization
tool since printing it would not be useful.
- Simulation integration
There is a bridge simulation game called Pontefex (now called
Bridge Builder, I believe) by
ChronicLogic?. Bridges are constructed from beams. Beams can be modeled
by two matrices, one at each end. Forces can be vectors and can be
applied and resolved into forces of compression or tension, twisting
or bending. All of these can be written using Axiom. So the idea is to
combine the Bridge Builder program with Axiom in order to be able to
model the forces on a bridge and try to accurately predict where the
bridge will fail prior to running the simulation.
This would combine Axiom with a commercial product to better illustrate
the power available. It would require contacting the company, negotiating
the deal, and leading a project to integrate the two pieces of software in
effective ways. Overall, a very big, long term project.
- V. RESEARCH PROBLEMS
Reading Soiffer's PhD? thesis (The Design of a User Interface for
Computer Algebra Systems) raises an interesting research question.
Assume you're given a standard page size (8 1/2 x 11, A4, display size)
and you have an equation to format in some understandable way
how can you format the equation to fit on one page.
The underlying "assumption" is that equations longer than one page are
unreadable and useless.
There are a variety of techniques:
- line breaks when the equation hits the edge
- common subexpression elimination when it can occur
R = (x+y) (z+(xy)) ==>
let M = (x+y)
R = M * (z+M)
so that you can "name" common subexpressions and lift them
- function reification
"name" a subexpression that requires a parameter,
lift it out, and substitute a parameterized term.
in a tree or DAG representation this is node-naming
- term reification
"name" a term, lift it out, and substitute
in a tree or DAG representation this is node-naming
- term summarization
replacing a (reordered) subset of the terms by a summation
- eliding leading, trailing, or middle terms
term + term + ... + term
- linearizing terms
terms, such as fractions, can be rewritten in linear form to
save lines
- constant naming
long constants replaced by short names:
R = 3.77612876767 * foo ==>
let M = 3.77612876767
R = M * foo
- pattern naming
turn 2D template structures (powers/ratios/matricies/polys) into
"named" template structures and substitute
+- -+ +- -+
| 1 2 | | 5 6 |
| | * | |
| 3 4 | | 7 8 |
+- -+ +- -+
turns into
A = Matrix((1 2) (3 4))
B = Matrix((5 6) (7 8))
MatrixProduct(A,B)
- operator names for all template structures and linear versions
- "outer structure" recognition
is it fundamentally a matrix? a polynomial? an integral?
the layout techniques could differ based on the outer structure
- "inner structure" eliding
clip out "heavy" element in a matrix so it does not cause
wide columns
- depth, width, height maximums as parameters
Ultimately it seems this boils down to a question of embedding a
tree or a DAG into a planar graph. or perhaps this is an extension
of the TeX layout algorithm with each weights assigned to the boxes?
compute the weight (area?) of a node in the tree or DAG and do some
sort of weight-reduction?
Summer of Code: Axiom Mentors
The following are possible mentors for some of the above projects. Interested students should contact
Tim Daly and identify the project you want to work on. Potential mentors please insert your info in alphabetical order (by last name).
- Tim Daly, lead Axiom developer, Carnegie Mellon University
- Bill Page, Axiom developer, Kingston, Ontario, Canada
- William Sit, Professor of Mathematics, City College of New York
Google's Summer of Code requires a
Mentoring Organization
I think the [Axiom Foundation]? would be ideal for this purpose.
Let's try to get the [Axiom Foundation]? added to the list at
http://code.google.com/summerofcode.html
Some additional possible projects and some additional information
about the above projects is available on the Axiom OldWishList page.
Although I am sure that we have enough projects listed above
to keep an army of students busy for several years, I think
creating this list is a very useful exercise in and of itself.
Maybe another category would be a good idea. Something like:
- VI. AXIOM-RELATED PROJECTS
- Complete the (re-)integration of the
Aldor compiler
into the open source version of Axiom.
Aldor (previously known as the AXIOMXL library compiler)
is a stand alone compiler that is compatible with the
AXIOM SPAD programming language. Aldor can be used to
write new algorthms and more efficient versions of existing
library code.
- Extensions to MathAction - the Axiom Wiki
- Extend the interface to Axiom to permit display of Axiom
graphics on MathAction
Axiom graphics requires the X-windows environment. This
can be done on the server using the virtual framebuffer
driver Xfbdev and the xvfb-run script. See:
http://packages.debian.org/unstable/x11/xvfb
http://www.t2-project.org/packages/xorg-server.html
To process graphic commands from a wiki page Axiom must be
started with xvfb-run with graphics enabled:
xvfb-run axiom -gr -noht -noclef
the Axiom command, e.g.:
viewport1 := draw(sin x, x=-%pi..%pi)
needs to be able to communicate with the graphics processor
in the X-windows environment to create the graphic image.
Additional Axiom commands can write this to a postscript file
and display in on the web page. E.g.:
write(viewport1, "graphic1", "postscript")
\begin{latex}
\psfig {graphic1.VIEW/axiom2D.ps}
\end{latex}
- Add web interfaces to other open source mathematical
In addition to Axiom, MathAction already has interfaces
to several other packages including Reduce
and GraphViz.
Interfaces to other open source mathematical packages
such as listed on the RosettaStone page could help to
build a stronger community among mathematical software
developers. This in turn would lead to improvements in
Axiom and all related packages.
Linux Fund may be another source of funds
for work on axiom.
|