Galois(ID:5629/gal006)

Symbolic maths 


sister language to Cayley

Language with explicit type declarations intended for batch processing


Related languages
Galois => CAYLEY   Co-development

References:
  • Cannon, John J. "A draft description of the group theory language Cayley" p66-84 view details Abstract: In this paper we outline a language belonging to the domain-specific class of algebraic programming languages. The problem domain we are concerned with is that of the theory of discrete groups and related structures. In 1971, Neübuser in Aachen and Cannon in Sydney, commenced the development of a general purpose group theory system called GROUP, the great majority of which is coded in ANSI Standard FORTRAN. For a discussion of the group theory algorithms planned for the system see Cannon [1]. Two driver languages are planned, Galois, a language with explicit type declarations intended for batch processing, and Cayley, a language where types are determined at run time and hence suitable both for batch processing and interactive computing. An interpreter for Cayley has been implemented at Sydney for the CDC6000 and CYBER series machines. The interpreter is coded in ANSI Standard FORTRAN and experience indicates that the entire system (some 50,000 lines of FORTRAN at present) can be implemented on a new machine with less than 2 months programming effort.
    Extract: Design Philosophy
    Design Philosophy
    It should perhaps be noted from the outset that the design of Cayley has been influenced by the existence of programs implementing some very powerful algorithms (e.g. nilpotent quotient, Todd-Coxeter) and the desire to synthesise these into a unified system so that a number of these algorithms may be brought to bear on a problem within a single run. Again group structure algorithms such as the subgroup lattice algorithm generate as their output an enormous amount of information, most of which is irrelevant to the problem at hand. Thus our language is required to process and extract information from large and complex data structures.

    Just as in ordinary programming languages, we wish to be able to program algorithms in a fairly natural way. There is the complication, however, that calculations may be performed in a number of different algebraic structures (e.g. groups, rings modules) and the precise specification of a structure (e.g. group of permutations of degree 6), need not be known until run time.

    We define type to mean a set of values. Besides traditional types such as integer and Boolean, Cayley contains several classes of types, the two most important of which are the class of algebraic structure types and the class of algebraic element types. Examples from the former class of types are
    permutation group of degree 6;
    group of 4×4 matrices over GF(9);
    finite field GF(26);
    ring of polynomials in x over field GF(2)
    modulo the polynomial x7-1;
    vector space of dimension 12 over GF(3).
    Examples of types from the class of algebraic element types are
    permutation of degree 6;
    4×4 matrix over GF(9);
    element of GF(26);
    polynomial over GF(2);
    12-dimensional vector with coefficients from GF(3).

    It can be seen that an algebraic structure type may consist of a single emement. There is a one-to-many correspondence between algebraic structure types and algebraic element types. In particular, it is necessary that an algebraic structure be defined before any of its elements.

    The kinds of algebraic structure currently permitted in Cayley are group, ring, field, vector space and module. An algebraic structure is represented in the machine as a set of attributes. These attributes not only serve to define the particular algebraic structure but also save most of the information that has been computed about the structure. Thus attributes of a group include type, elements, conjugacy classes, subgroup lattice etc. Note that generally only a subset of the attributes of a structure are defined during a computation within that structure.

    An important point to note concerning attributes is that their values need not belong to one of the standard Cayley types. An example of such an attribute is the subgroup lattice which is more than just a set of subgroups. Attributes corresponding to non-standard Cayley types are created by functions which can only return a value for the attribute. Once created, such an attribute may be printed or its constituents, corresponding to standard Cayley types, may be referred to in ordinary statements.

    Other important Cayley types are set, sequence and mapping. Because of the central role these concepts play in mathematics, any algebraic programming language without them would be seriously deficient. The elements of sets and sequences may be objects of any type. The domain and range of a mapping may be sets, sequences or algebraic structures. Special types associated with particular algebraic structures e.g. coset table with groups, are introduced as necessary. A typical Cayley program will involve one or more variables of algebraic structure type. Since the computation of certain information about such a structure e.g. conjugacy cl~sses, subgroups of a group, can be very expensive, it is saved (unless explicitly deleted by the user) as it will often be required further on in the computation. Thus as the computation proceeds more and more structural information is accumulated for each algebraic structure which is defined. Action routines are designed to check whether any of the saved information can be used to shorten their task.

    In this paper we give a summary of the principal constructs in Cayley. A more complete description may be found in [2]. The form of presentation adopted here is modeled loosely on Wirth's admirable description of Pascal [5].
          in Proceedings of the Third ACM symposium on Symbolic and algebraic computation, August 10-12, 1976, Yorktown Heights, New York, United States view details