general.hpp File Reference

Central docus-file regarding computer algebra. More...

Go to the source code of this file.

Detailed Description

Central docus-file regarding computer algebra.

General principles

The computer-algebra systems are taken as "programming languages with associated libraries". Thus the underlying languages are taken seriously(!), and they constitute two different abstraction levels:

  1. The "basic level" is the "Lisp level", that is, CLisp with Maxima:
    • The role model for all "data types" here is set theory.
      1. For example, a graph is a pair "[V,E]" of vertex-set V and a set E of 2-element subsets of the vertex-set.
      2. Faithful to the set-theoretic approach, a "vertex" can be anything.
      3. For a "general graph" we use a map from the set of edge-labels to the 1- or 2-element subsets.
      4. Similarly, a clause-set is a set of clauses, etc.
    • However, the fundamental objects now are lists:
      1. In set theory the fundamental object is a set, an unordered structure, since the mathematical world is eternal, objects are not created, but exist.
      2. Computation on the other hand fundamentally relies on order, so the most basic object is accordingly the list.
    • "Objects stand for themselves":
      1. As in set theory, a list can represent many things, and interpretations must be added to give it meaning.
      2. So for example "[{},{}]" can be
        • the graph with no vertices,
        • the hypergraph with no vertices and no hyperedges,
        • as well as the formal clause-set with no variables and no clauses.
      3. Objects are not adorned to fix their meaning.
    • The language is untyped, and this is (taken for this level(!)) "a feature, not a bug".
      1. No type checking of any kind is performed, but the algorithms are formulated as "pure generic algorithms" based on established conventions how to access the data.
      2. Thus the algorithms are open for more general applications than perhaps originally anticipated.
      3. For defining the concepts, and for error checking, predicates are provided which check whether objects are well-formed according to the notion of a "graph", a "clause-set" etc.; but these predicates are not used for programming.
    • "Flow with Lisp", that is, put things in a natural way into lists, and neither worry about efficiency nor about abstraction and concept-hierarchies.
    • No polymorphism is employed, but concrete representations (exploiting the generality of lists and terms) together with conversion functions.
      1. A central point here is that abstraction must come later.
      2. First we make concrete experiences with the real multiplicity of concrete types.
      3. Abstraction is then added at the Aldor and C++ level.
    • The intention of this level is that of quick and elegant programming, for prototyping and experimentation.
      1. It shall provide the specificational basis for the whole library.
      2. No simulations of programming concepts which where not anticipated with Lisp.
  2. The "extended level" is the "Aldor level", that is, Aldor with Axiom:
    • Aldor supports dependent types and concept hierarchies, and so here now abstraction is a central issue, with proper concept hierarchies and strict typing.
    • What still is abstracted away, compared to the "full level", are fine-grained algorithmic choices and especially considerations regarding memory management and construction/destruction of objects.
    • It seems that most development will happen at the basic level (the Maxima/Lisp level) or at the full level, while the Axiom/Aldor level is about planning, formulating and prototyping abstraction.
      1. For example, at the Maxima/Lisp level we develop a systematic and fine-grained, but non-abstract account of all graph- and hypergraph concepts, and a good selection on algorithms operating with these concepts.
      2. After seeing this picture (for the first time!), we look at common principles, common methods, common interfaces.
      3. That is, the multitude of concrete concepts is organised into a network of abstract concepts.
    • Currently we are in the phase of building up the basic level, and thus work at the Axiom/Aldor level is slow-going.
  3. The third level, the C++ level which is considered as the "full level", is no longer in the realm of computer algebra, and here in principal the full spectrum can be expressed, from hardware access to abstract concept hierarchies:
    1. Especially algorithms can be fully fine-tuned.
    2. And construction/destruction of objects can be fully controlled.
  4. So, especially for SAT algorithms the general plan is to
    1. first develop them at the simple Lisp-level,
    2. then to develop the fundamental abstractions at the Aldor-level,
    3. and finally to explore all possibilities at the C++ level.
    However, development can also start at the C++ level, and mimic these steps by first starting with the "C core part" of C++, and then adding abstraction and refinements.
  5. The usage of Sage is restricted to provide interfaces between the different systems.

The underlying mathematical concepts are the same for all three levels, but their realisations might differ considerably in the three levels.



Definition in file general.hpp.