gsl-design.texi

GNU Scientific Library,C语言开发的数值方面的函数库

@strong{One language only (C)}

Advantages: simpler, compiler available and quite universal.

@node Interface to other languages, What routines are implemented, Language for implementation, Design
@section Interface to other languages

Wrapper packages are supplied as "extra" packages; not as part of the
"core". They are maintained separately by independent contributors.

Use standard tools to make wrappers: swig, g-wrap

@node What routines are implemented, What routines are not implemented, Interface to other languages, Design
@section What routines are implemented

Anything which is in any of the existing libraries.  Obviously it makes
sense to prioritize and write code for the most important areas first.

@c @itemize @bullet
@c @item Random number generators

@c Includes both random number generators and routines to give various
@c interesting distributions.

@c @item Statistics

@c @item Special Functions

@c What I (jt) envision for this section is a collection of routines for
@c reliable and accurate (but not necessarily fast or efficient) estimation
@c of values for special functions, explicitly using Taylor series, asymptotic 
@c expansions, continued fraction expansions, etc.  As well as these routines,
@c fast approximations will also be provided, primarily based on Chebyschev
@c polynomials and ratios of polynomials.  In this vision, the approximations
@c will be the "standard" routines for the users, and the exact (so-called)
@c routines will be used for verification of the approximations.  It may also
@c be useful to provide various identity-checking routines as part of the
@c verification suite.

@c @item Curve fitting

@c polynomial, special functions, spline

@c @item Ordinary differential equations

@c @item Partial differential equations

@c @item Fourier Analysis

@c @item Wavelets

@c @item Matrix operations: linear equations

@c @item Matrix operations: eigenvalues and spectral analysis

@c @item Matrix operations: any others?

@c @item Direct integration

@c @item Monte carlo methods

@c @item Simulated annealing

@c @item Genetic algorithms

@c We need to think about what kinds of algorithms are basic generally
@c useful numerical algorithms, and which ones are special purpose
@c research projects.  We should concentrate on supplying the former.

@c @item Cellular automata

@c @end itemize

@node What routines are not implemented, Design of  Numerical Libraries, What routines are implemented, Design
@section What routines are not implemented

@itemize @bullet
@item anything which already exists as a high-quality GPL'ed package.

@item anything which is too big
 -- i.e. an application in its own right rather than a subroutine

For example, partial differential equation solvers are often huge and
very specialized applications (since there are so many types of PDEs,
types of solution, types of grid, etc).  This sort of thing should
remain separate.  It is better to point people to the good applications
which exist.

@item anything which is independent and useful separately.

Arguably functions for manipulating date and time, or financial
functions might be included in a "scientific" library.  However, these
sorts of modules could equally well be used independently in other
programs, so it makes sense for them to be separate libraries.
@end itemize

@node  Design of  Numerical Libraries, Code Reuse, What routines are not implemented, Design
@section  Design of  Numerical Libraries

In writing a numerical library there is a unavoidable conflict between
completeness and simplicity.  Completeness refers to the ability to
perform operations on different objects so that the group is
"closed". In mathematics objects can be combined and operated on in an
infinite number of ways.  For example, I can take the derivative of a
scalar field with respect to a vector and the derivative of a vector
field wrt a scalar (along a path).

There is a definite tendency to unconsciously try to reproduce all these
possibilities in a numerical library, by adding new features one by
one. After all, it is always easy enough to support just one more
feature.... so why not?

Looking at the big picture, no-one would start out by saying "I want to
be able to represent every possible mathematical object and operation
using C structs" -- this is a strategy which is doomed to fail.  There
is a limited amount of complexity which can be represented in a
programming language like C.  Attempts to reproduce the complexity of
mathematics within such a language would just lead to a morass of
unmaintainable code.  However, it's easy to go down that road if you
don't think about it ahead of time.

It is better to choose simplicity over completeness.  In designing new
parts of the library keep modules independent where possible. If
interdependencies between modules are introduced be sure about where you
are going to draw the line.

@node Code Reuse, Standards and conventions, Design of  Numerical Libraries, Design
@section Code Reuse

It is useful if people can grab a single source file and include it in
their own programs without needing the whole library.  Try to allow
standalone files like this whenever it is reasonable.  Obviously the
user might need to define a few macros, such as GSL_ERROR, to compile
the file but that is ok.  Examples where this can be done: grabbing a
single random number generator.

@node Standards and conventions, Background and Preparation, Code Reuse, Design
@section Standards and conventions

The people who kick off this project should set the coding standards and
conventions.  In order of precedence the  standards that we follow are,

@itemize @bullet
@item We follow the GNU Coding Standards.
@item We follow the conventions of the ANSI Standard C Library.
@item We follow the conventions of the GNU C Library.
@item We follow the conventions of the glib GTK support Library.
@end itemize

The references for these standards are the @cite{GNU Coding Standards}
document, Harbison and Steele @cite{C: A Reference Manual}, the
@cite{GNU C Library Manual} (version 2), and the Glib source code.

For mathematical formulas, always follow the conventions in Abramowitz &
Stegun, the @cite{Handbook of Mathematical Functions}, since it is the
definitive reference and also in the public domain.

If the project has a philosophy it is to "Think in C".  Since we are
working in C we should only do what is natural in C, rather than trying
to simulate features of other languages.  If there is something which is
unnatural in C and has to be simulated then we avoid using it. If this
means leaving something out of the library, or only offering a limited
version then so be it.  It is not worthwhile making the library
over-complicated.  There are numerical libraries in other languages, and
if people need the features of those languages it would be sensible for
them to use the corresponding libraries, rather than coercing a C
library into doing that job.  

It should be borne in mind at all time that C is a macro-assembler.  If
you are in doubt about something being too complicated ask yourself the
question "Would I try to write this in macro-assembler?" If the answer
is obviously "No" then do not try to include it in GSL. [BJG]

It will be useful to read the following paper,

@itemize @asis
@item 
Kiem-Phong Vo, ``The Discipline and Method Architecture for Reusable
Libraries'', Software - Practice & Experience, v.30, pp.107-128, 2000.
@end itemize
@noindent
It is available from
@uref{http://www.research.att.com/sw/tools/sfio/dm-spe.ps} or the earlier
technical report Kiem-Phong Vo, "An Architecture for Reusable Libraries"
@uref{http://citeseer.nj.nec.com/48973.html}.

There are associated papers on Vmalloc, SFIO, and CDT which are also
relevant to the design of portable C libraries.

@itemize @asis
@item
Kiem-Phong Vo, ``Vmalloc: A General and Efficient Memory
Allocator''. Software Practice & Experience, 26:1--18, 1996.

@uref{http://www.research.att.com/sw/tools/vmalloc/vmalloc.ps}
@item
Kiem-Phong Vo. ``Cdt: A Container Data Type Library''. Soft. Prac. &
Exp., 27:1177--1197, 1997

@uref{http://www.research.att.com/sw/tools/cdt/cdt.ps}
@item
David G. Korn and Kiem-Phong Vo, ``Sfio: Safe/Fast String/File IO'',
Proceedings of the Summer '91 Usenix Conference, pp.  235-256, 1991.

@uref{http://citeseer.nj.nec.com/korn91sfio.html}
@end itemize

Source code should be indented according to the GNU Coding Standards,
with spaces not tabs. For example, by using the @code{indent} command:

@example
indent -gnu -nut *.c *.h
@end example
@noindent
The @code{-nut} option converts tabs into spaces.

@node Background and Preparation, Choice of Algorithms, Standards and conventions, Design
@section Background and Preparation

Before implementing something be sure to research the subject
thoroughly!  This will save a lot of time in the long-run.  The two most
important steps are,

@enumerate
@item
to determine whether there is already a free library (GPL or
GPL-compatible) which does the job.  If so, there is no need to
reimplement it.  Carry out a search on Netlib, GAMs, na-net,
sci.math.num-analysis and the web in general. This should also provide
you with a list of existing proprietary libraries which are relevant,
keep a note of these for future reference in step 2.

@item 
make a comparative survey of existing implementations in the
commercial/free libraries. Examine the typical APIs, methods of
communication between program and subroutine, and classify them so that
you are familiar with the key concepts or features that an
implementation may or may not have, depending on the relevant tradeoffs
chosen.  Be sure to review the documentation of existing libraries for
useful references.

@item
read up on the subject and determine the state-of-the-art.  Find the
latest review papers.  A search of the following journals should be
undertaken.

@itemize @asis
@item ACM Transactions on Mathematical Software
@item Numerische Mathematik
@item Journal of Computation and Applied Mathematics
@item Computer Physics Communications
@item SIAM Journal of Numerical Analysis
@item SIAM Journal of Scientific Computing
@end itemize
@end enumerate
@noindent
Keep in mind that GSL is not a research project.  Making a good
implementation is difficult enough, without also needing to invent new
algorithms.  We want to implement existing algorithms whenever
possible. Making minor improvements is ok, but don't let it be a
time-sink.

@node Choice of Algorithms, Documentation, Background and Preparation, Design
@section Choice of Algorithms

Whenever possible choose algorithms which scale well and always remember
to handle asymptotic cases.  This is particularly relevant for functions
with integer arguments.  It is tempting to implement these using the
simple @math{O(n)} algorithms used to define the functions, such as the
many recurrence relations found in Abramowitz and Stegun.  While such
methods might be acceptable for @math{n=O(10-100)} they will not be
satisfactory for a user who needs to compute the same function for
@math{n=1000000}.

Similarly, do not make the implicit assumption that multivariate data
has been scaled to have components of the same size or O(1).  Algorithms
should take care of any necessary scaling or balancing internally, and
use appropriate norms (e.g. |Dx| where D is a diagonal scaling matrix,
rather than |x|).

@node Documentation, Namespace, Choice of Algorithms, Design
@section Documentation
Documentation: the project leaders should give examples of how things
are to be documented.  High quality documentation is absolutely
mandatory, so documentation should introduce the topic, and give careful
reference for the provided functions. The priority is to provide
reference documentation for each function. It is not necessary to
provide tutorial documentation.

Use free software, such as GNU Plotutils, to produce the graphs in the
manual.

Some of the graphs have been made with gnuplot which is not truly free
(or GNU) software, and some have been made with proprietary
programs. These should be replaced with output from GNU plotutils.

When citing references be sure to use the standard, definitive and best
reference books in the field, rather than lesser known text-books or
introductory books which happen to be available (e.g. from undergraduate
studies).  For example, references concerning algorithms should be to
Knuth, references concerning statistics should be to Kendall & Stuart,
references concerning special functions should be to Abramowitz & Stegun
(Handbook of Mathematical Functions AMS-55), etc.

The standard references have a better chance of being available in an
accessible library for the user.  If they are not available and the user
decides to buy a copy in order to look up the reference then this also
gives them the best quality book which should also cover the largest
number of other references in the GSL Manual.  If many different books
were to be referenced this would be an expensive and inefficient use of
resources for a user who needs to look up the details of the algorithms.
Reference books also stay in print much longer than text books, which
are often out-of-print after a few years.

Similarly, cite original papers wherever possible.  Be sure to keep
copies of these for your own reference (e.g. when dealing with bug
reports) or to pass on to future maintainers.

If you need help in tracking down references, ask on the
@code{gsl-discuss} mailing list.  There is a group of volunteers with
access to good libraries who have offered to help GSL developers get
copies of papers.

[JT section: written by James Theiler

And we furthermore promise to try as hard as possible to document
the software: this will ideally involve discussion of why you might want
to use it, what precisely it does, how precisely to invoke it, 
how more-or-less it works, and where we learned about the algorithm,
and (unless we wrote it from scratch) where we got the code.
We do not plan to write this entire package from scratch, but to cannibalize
existing mathematical freeware, just as we expect our own software to
be cannibalized.]

@node Namespace, Header files, Documentation, Design
@section Namespace

Use @code{gsl_} as a prefix for all exported functions and variables.

Use @code{GSL_} as a prefix for all exported macros.

All exported header files should have a filename with the prefix @code{gsl_}.

All installed libraries should have a name like libgslhistogram.a

Any installed executables (utility programs etc) should have the prefix
@code{gsl-} (with a hyphen, not an underscore).

All function names, variables, etc should be in lower case.  Macros and
preprocessor variables should be in upper case.

@node Header files, Target system, Namespace, Design
@section Header files

Installed header files should be idempotent, i.e. surround them by the
preprocessor conditionals like the following,

@example
#ifndef __GSL_HISTOGRAM_H__
#define __GSL_HISTOGRAM_H__
...
#endif /* __GSL_HISTOGRAM_H__ */