User-Defined Types

Since Magma V2.19, types may be defined by users within packages. This facility allows the user to declare new type names and create objects with such types and then supply some basic primitives and intrinsic functions for such objects.

The new types are known as user-defined types. The way these are typically used is that after declaring such a type T, the user supplies package intrinsics to: (1) create objects of type T and set relevant attributes to define the objects; (2) perform some basic primitives which are common to all objects in Magma; (3) perform non-trivial computations on objects of type T.

Declaring User-Defined Types

The following declarations are used to declare user-defined types. They may only be placed in package files, i.e., files that are included either by using Attach or a spec file (see above). Declarations may appear in any package file and at any place within the file at the top level (not in a function, etc.). In particular, it is not required that the declaration of a type appears before package code which refers to the type (as long as the type is declared before running the code). Examples below will illustrate how the basic declarations are used.

declare type T;

Declare the given type name T (without quotes) to be a user-defined type.

declare type T: P₁, ..., P_n;

Declare the given type name T (without quotes) to be a user-defined type, and also declare T to inherit from the user types P₁, ..., P_n (which must be declared separately). As a result, ISA(T, P_i) will be true for each i and when intrinsic signatures are scanned at a function call, an object of type T will match an argument of a signature with type P_i for any i.

NB: currently one may not inherit from existing Magma internal types or virtual types (categories). It is hoped that this restriction will be removed in the future.

declare type T[E];

Declare the given type names T and E (both without quotes) to be user-defined types. This form also specifies that E is the element type corresponding to T; i.e., if an object x has an element of type T for its parent, then x must have type E. This relationship is needed for the construction of sets and sequences which have objects of type T as a universe. The type E may also be declared separately, but this is not necessary.

declare type T[E]: P₁, ..., P_n;

This is a combination of the previous kinds two declarations: T and E are declared as user-defined types while E is also declared to be the element type of T, and T is declared to inherit from user-defined types P₁, ..., P_n.

Creating an Object

New(T) : Type -> T

Create an empty object of type T, where T is a user-defined type. Typically, after setting X to the result of this function, the user should set attributes in X to define relevant properties of the object which are characteristic of objects of type T.

Clone(X) : Any -> Any

Given an object X having (user-defined) type T, return a copy C of X with type T and with all assigned attributes copied from X. This allows one to modify the attributes of the new object C without affecting the attributes of X.

Special Intrinsics Provided by the User

Let T be a user-defined type. Besides the declaration of T, the following special intrinsics are mostly required to be defined for type T (the requirements are specified for each kind of intrinsic). These intrinsics allow the internal Magma functions to perform some fundamental operations on objects of type T. Note that the special intrinsics need not be in one file or in the same file as the declaration.

intrinsic Print(X::T)
{Print X}
    // Code: Print X with no new line, via printf
end intrinsic;

intrinsic Print(X::T, L::MonStgElt)
{Print X at level L}
    // Code: Print X at level L with no new line, via printf
end intrinsic;

Exactly one of these intrinsics must be provided by the user for type T. Each is a procedure rather than a function (i.e., nothing is returned), and should contain one or more print statements. The procedure is called automatically by Magma whenever the object X of type T is to be printed. A new line should not occur at the end of the last (or only) line of printing: one should use printf (see examples below).

When the second form of the intrinsic is provided, it allows X to be printed differently depending on the print level L, which is a string equal to one of "Default", "Minimal", "Maximal", "Magma".

Note: Print is used by Magma in error-handling tracebacks, being called with the "Minimal" parameter if available. In particular, Print in this form should be kept rather uncomplicated, notably avoiding the usage of (failing) try/catch constructions, as these will cause a crash from recursive errors being detected.

intrinsic Parent(X::T) -> .
{Parent of X}
    // Code: Return the parent of X
end intrinsic;

This intrinsic is only needed when T is an element type, so objects of type T have parents. It should be a user-provided package function, which takes an object X of type T (user-defined), and returns the parent of X, assuming it has one. In such a case, typically the attribute Parent will be defined for X and so X`Parent should simply be returned.

intrinsic 'in'(e::., X::T) -> BoolElt
{Return whether e is in X}
    // Code: Return whether e is in X
end intrinsic;

This intrinsic is only needed when objects of type T (user-defined) have elements, and should be a user-provided package function, which takes any object e and an object X of type T (user-defined), and returns whether e is an element of X.

intrinsic IsCoercible(X::T, y::.) -> BoolElt, .
{Return whether y is coercible into X and the result if so}
    // Code: do tests on the type of y to see whether coercible

    // On failure, do:
    //    return false, "Illegal coercion"; // Or more particular message

    // Assumed coercible now; set x to result of coercion into X
    return true, x;
end intrinsic;

Assuming that objects of type T (user-defined) have elements (and so coercion into such objects makes sense), this must be a user-provided package function, which takes an object X of type T (user-defined) and an object Y of any type. If Y is coercible into X, the function should return true and the result of the coercion (whose parent should be X). Otherwise, the function should return false and a string giving the reason for failure. If this package intrinsic is provided, then the coercion operation X!y will also automatically work for an object X of type T (i.e., the internal coercion code in Magma will automatically call this function).

intrinsic SubConstructor(X::T, t::.) -> T
{Return the substructure of X generated by elements of the tuple t}
    // This corresponds to the constructor call sub<X | r1, r2, ..., rn>
    // t is ALWAYS a tuple of the form <r1, r2, ..., rn>
    // Code: do tests on the elements in t to see whether valid and then
    //       set S to the substructure of T generated by r1, r2, ..., rn
    // Use standard require statements for error checking
    // Possibly use "t := Flat(t);" to make it easy to loop over t if
    //     any of the ri are sequences
    return S;
end intrinsic;

Assuming that objects of type T (user-defined) have elements, this must be a user-provided package function, which takes an object X of type T (user-defined) and a tuple t. The user call sub<X | r1, r2, ..., rn> (where X has type T) will cause this intrinsic to be called with X and the tuple t=< r1, ... ,rn >. The function should create the substructure S of X generated by r1, ... ,rn and return S alone (the inclusion map from X to S is automatically handled by Magma via coercion).

intrinsic Hash(X::T) -> RngIntElt
{Return a hash value for the object x (should be between 0 and 2^31-1)}
   // Code: determine a hash value for the given object
   // NOTE: Objects X and Y of type T for which X eq Y is true
   //       MUST have the same hash value
   return hash;
end intrinsic;

Providing this intrinsic can greatly speed the checking of equality of objects of type T, and in particular if you wish to work with sets of reasonable cardinality (more than 1000 elements) it should be made available. The requirement is that if X and Y are equal, then their hashes should be the same, regardless of their internal representation.

Examples

Some basic examples illustrating the general use of user-defined types are given here. Non-trivial examples can also be found in much of the standard Magma package code (one can search for "declare type" in the package .m files to see several typical uses).

declare type MyRat;

declare attributes MyRat: Numer, Denom;

intrinsic MyRational(n::RngIntElt, d::RngIntElt) -> MyRat
{Create n/d}

    require d ne 0: "Denominator must be non-zero";
    r := New(MyRat);
    r`Numer := n;
    r`Denom := d;
    return r;
end intrinsic;

intrinsic Print(r::MyRat)
{Print r}

    n := r`Numer;
    d := r`Denom;
    g := GCD(n, d);
    if d lt 0 then g := -g; end if;
    printf "%o/%o", n div g, d div g; // NOTE: no newline!
end intrinsic;

intrinsic '+'(r::MyRat, s::MyRat) -> MyRat
{Return r + s}

    rn := r`Numer;
    rd := r`Denom;
    sn := s`Numer;
    sd := s`Denom;
    return MyRational(rn*sd + sn*rd, rd*sd);
end intrinsic;

intrinsic '*'(r::MyRat, s::MyRat) -> MyRat
{Return r * s}

    rn := r`Numer;
    rd := r`Denom;
    sn := s`Numer;
    sd := s`Denom;
    return MyRational(rn*sn, rd*sd);
end intrinsic;

> Attach("myrat.m");
> r := MyRational(3, -9);
> r;
-1/3
> s := MyRational(4, 7); 
> s;
> r+s;
5/21
> r*s;
-4/21

/* Declare types and attributes */


// Note that we declare DirProdElt as element type of DirProd:
declare type DirProd[DirProdElt];
declare attributes DirProd: Rings;
declare attributes DirProdElt: Elements, Parent;


/* Special intrinsics for DirProd */


intrinsic DirectProduct(Rings::Tup) -> DirProd
{Create the direct product of given rings (a tuple)}

    require forall{R: R in Rings | ISA(Type(R), Rng)}:
        "Tuple entries are not all rings";
    D := New(DirProd);
    D`Rings := Rings;
    return D;
end intrinsic;


intrinsic Print(D::DirProd)
{Print D}

    Rings := D`Rings;
    printf "Direct product of %o", Rings; // NOTE: no newline!
end intrinsic;


function CreateElement(D, Elements)
    // Create DirProdElt with parent D and given Elements
    x := New(DirProdElt);
    x`Elements := Elements;
    x`Parent := D;
    return x;
end function;


intrinsic IsCoercible(D::DirProd, x::.) -> BoolElt, .
{Return whether x is coercible into D and the result if so}

    Rings := D`Rings;
    n := #Rings;
    if Type(x) eq DirProdElt then
        if x`Parent cmpeq D then
            return true, x;
        end if;
        x := x`Elements;
    end if;
    if Type(x) ne Tup then
        return false, "Coercion RHS must be a tuple";
    end if;
    if #x ne n then
        return false, "Wrong length of tuple for coercion";
    end if;
    Elements := <>;
    for i := 1 to n do
        l, t := IsCoercible(Rings[i], x[i]);
        if not l then
            return false, Sprintf("Tuple entry %o not coercible", i);
        end if;
        Append(~Elements, t);
    end for;

    y := CreateElement(D, Elements);
    return true, y;
end intrinsic;


/* Special intrinsics for DirProdElt */


intrinsic Print(x::DirProdElt)
{Print x}

    printf "%o", x`Elements; // NOTE: no newline!
end intrinsic;


intrinsic Parent(x::DirProdElt) -> DirProd
{Parent of x}

    return x`Parent;
end intrinsic;


intrinsic '+'(x::DirProdElt, y::DirProdElt) -> DirProdElt
{Return x + y}

    D := Parent(x);
    require D cmpeq Parent(y): "Incompatible arguments";

    Ex := x`Elements;
    Ey := y`Elements;
    return CreateElement(D, <Ex[i] + Ey[i]: i in [1 .. #Ex]>);
end intrinsic;


intrinsic '*'(x::DirProdElt, y::DirProdElt) -> DirProdElt
{Return x * y}

    D := Parent(x);
    require D cmpeq Parent(y): "Incompatible arguments";

    Ex := x`Elements;
    Ey := y`Elements;
    return CreateElement(D, <Ex[i] * Ey[i]: i in [1 .. #Ex]>);
end intrinsic;

> Attach("DirProd.m");
> Z := IntegerRing();
> Q := RationalField();
> F8<a> := GF(2^3);
> F9<b> := GF(3^2);
> D := DirectProduct(<Z, Q, F8, F9>);
> x := D!<1, 2/3, a, b>;
> y := D!<2, 3/4, a+1, b+1>;
> x;
<1, 2/3, a, b>
> Parent(x);
Direct product of <Integer Ring, Rational Field, Finite field of
size 2^3, Finite field of size 3^2>
> y;
<2, 3/4, a^3, b^2>
> x+y;
<3, 17/12, 1, b^3>
> x*y;
<2, 1/2, a^4, b^3>
> D!x;
<1, 2/3, a, b>
> S := [x, y]; S;
[
    <1, 2/3, a, b>,
    <2, 3/4, a^3, b^2>
]
> 
> &+S;
<3, 17/12, 1, b^3>