Primeros pasos con `GAP`

gap es un entorno de cálculo algebraico discreto. Tiene un núcleo implementado en c y dispone aparte de librerías escritas en su propio lenguaje de programación.

Este lenguaje es de tipo procedural, por lo que aquellas personas que han programado en pascal, c, maple, … no tienen problemas en adaptarse. En la página oficial de gap se puede encontrar abundante información concerniente a instalación en distintas plataformas, tutoriales, manuales, paquetes.

Los paquetes pasan por un proceso de arbitraje similar al de las revistas científicas. Primero son depositados (y accesibles al público en la página oficial) y si se aceptan pasan a ser parte de la distribución. Aún así muchos instaladores incluyen los paquetes depositados.

gap ha sido mantenido a lo largo de su historia por varias universidades, y se nutre de las contribuciones que hacen los usuarios en forma de paquetes para fines más específicos.

La línea de comandos

gap es un lenguaje interpretado (aunque tiene un compilador). Se pueden hacer operaciones directamente en la línea de comandos o bien se pueden leer ficheros con guiones escritos con un editor de textos.

Normalmente se invoca usando el comando gap, aunque dependiendo del sistema operativo pueden haber distintas alternativas. Una vez iniciado el intérprete aparece una línea de comandos con el siguiente aspecto.

gap>

Para la edición de las entradas que queramos evaluar se pueden utilizar las flechas junto con las teclas de inicio y fin. Además existe la posibilidad de usar combinaciones de teclas similares a las de empleadas en un shell de unix (ctr-[b,f,p,n,a,e]). El tabulador sirve para completar comandos a partir del texto que hayamos introducido en ese momento. Así teclear Gcd+TAB da como resultado:

gap> Gcd
    Gcd
    GcdCoeffs
    GcdInt
    GcdOp
    GcdRepresentation
    GcdRepresentationOp
    Gcdex

Para salir de la línea de comandos podemos usar el comando quit;, o bien pulsar ctr-d.

El final de línea no se indica con el retorno de carro, sino con ; (para evaluar, se pulsa enter). Esto permite escribir sentencias de varias líneas.

gap> 1+
> 2;
3

En jupyter para evaluar hay que pulsar mayúscula+enter.

1+
2;

La sesión de trabajo se puede almacenar en un fichero para su posterior edición usando el comando LogTo. Con LogTo("pruebas/log"); guardamos en el fichero log en la carpeta pruebas. Con LogTo(); interrumpimos la grabación.

Podemos leer una secuencia de comandos (guión) con la orden Read (en este ejemplo uno.g contiene sólamente a:=1;).

Read("pruebas/uno.g");

a;

Nótese que las barras son de la forma /, incluso en windows.

A la ayuda se accede usando el signo de cierre de interrogación. Por ejmeplo, ?LogTo muestra ayuda sobre dicho comando.

Las operaciones de suma y producto dependen de los argumentos que les acompañen. Así pueden representar suma de enteros, o de matrices, o de subespacios vectoriales… El producto puede significar incluso la composición de dos permutaciones, y el elevado (^) la imagen de un punto por una permutación.

[1,2,3]+[1,2];

[ 2, 4, 3 ]

(1,2)*(2,5);

(1,5,2)

1^(1,2,3);

Los símbolos =, <, >, <=, > = y <> sirven para denotar igualdad, ser mayor, menor, menor o igual, mayor o igual y distinto, respectivamente.

2=1+1;

true

[1,2]<[3];

true

[1,2]>[1,3];

false

1<>1;

false

Identificadores

Si vamos a utilizar un objeto varias veces, podemos por comodidad asignarle un nombre.

a:=2^10;

Si queremos inhibir la salida, escribimos un punto y coma extra al final de la asignación.

b:=a;;

Podemos visualizar las variables definidas hasta el momento de la siguiente forma.

NamesUserGVars();

Error, Variable: 'NamesUserGVars' must have a value
not in any function at stream:1

Las variables en gap no tienen tipo, las características del objeto al que se refieren se guardan en el propio objeto. De hecho, podemos reutilizar una misma variable para denotar distintos tipos de datos.

a:=1;

a:=(1,2);

(1,2)

a:=[1,2];

[ 1, 2 ]

El identificador last se usa para hacer referencia a la última salida (también existen last2 y last3).

En gap se ha establecido el convenio de escribir las variables globales y las utilizadas en las librerías empezando con mayúsculas.

Las funciones también son objetos, y se pueden definir de varias formas. Podemos utilizar un procedimiento clásico.

f:=function(x)
    return x^2;
end;

function( x ) ... end

f(3);

Y también podemos usar notación estilo \(\lambda\)-cálculo.

g:=x->x^2;
g(3);

function( x ) ... end

Listas

Las listas en gap se escriben, como ya hemos visto en algunos ejemplos arriba como una secuencia de elementos delimitada por corchetes. Dichas secuencias no tienen por qué ser homogéneas. Al trabajar con listas tenemos que prestar atención a algunas funciones que son ‘destructivas’, a saber, modifican alguno de los argumentos que se les pasa. Esto se debe en parte a que cuando uno asigna un identificador a una lista, no lo hace al objeto como tal, si no a su posición en la memoria.

a:=[1,"a"];

[ 1, "a" ]

b:=a;

[ 1, "a" ]

b[2]:=3;

a;

[ 1, 3 ]

Como hemos visto en este ejemplo lista[n] accede al n-ésimo elemento de la lista (empezando por 1; en otros lenguajes la primera posición es la correspondiente al índice 0).

Podemos usar el comando ShallowCopy para hacer una copia de una lista, creando un objeto nuevo.

a:=[1,"a"];

[ 1, "a" ]

b:=ShallowCopy(a);

[ 1, "a" ]

b[2]:=3;

b;

[ 1, 3 ]

a;

[ 1, "a" ]

Hay multitud de formas para definir y modificar listas, ponemos unos ejemplos a continuación.

a:=[1,"a"];

[ 1, "a" ]

Para añadirle a a los elementos de otra lista, podemos usar Append:

Append(a,[2,3]);

a;

[ 1, "a", 2, 3 ]

Si lo que queremos es añadir un elemento al final, usamos Add.

Add(a,5);

a;

[ 1, "a", 2, 3, 5 ]

Concatenation devuelve una lista nueva a partir de dos dadas, concatenándolas y sin modificarlas.

Concatenation(a,[8,9]);

[ 1, "a", 2, 3, 5, 8, 9 ]

a;

[ 1, "a", 2, 3, 5 ]

Filtered lo podemos usar para filtrar los elementos de una lista que cumplan una condición.

l:=Filtered([1..100],IsPrime);

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]

También podemos aplicar una función a todos los elementos de una lista.

List(l,x->x^2);

[ 4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409 ]

A veces es conveniente usar conjuntos en vez de listas, pues sus elementos se ordenan (si son comparables entre sí) y la pertenencia de un elemento es más rápida de resolver.

a:=[1,2,1,2];

[ 1, 2, 1, 2 ]

Set(a);

[ 1, 2 ]

a;

[ 1, 2, 1, 2 ]

3 in a;

false

Hay ciertos comandos que dan como salida un conjunto.

a:=[1,2];

[ 1, 2 ]

b:=[2,3];

[ 2, 3 ]

u:=Union(a,b);

[ 1, 2, 3 ]

IsSet(u);

true

Intersection(a,b);

[ 2 ]

Rangos

El uso de .. se puede usar de varias formas, y captura la idea de rango.

l:=[1..20];

[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ]

l{[3,5..9]};

[ 3, 5, 7, 9 ]

lc:=List(l,x->x^2);

[ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400 ]

lc{[20,19..10]};

[ 400, 361, 324, 289, 256, 225, 196, 169, 144, 121, 100 ]

Registros

En gap podemos crear registros con campos personalizados utilizando rec.

r:=rec(a:=1,b:="2");

rec( a := 1, b := "2" )

Podemos añadir nuevos campos, o modificar los existentes, simplemente asignándoles un valor.

r.c:=rec(d:=1,e:=3);

rec( d := 1, e := 3 )

r;

rec( a := 1, b := "2", c := rec( d := 1, e := 3 ) )

r.a:=5;

r;

rec( a := 5, b := "2", c := rec( d := 1, e := 3 ) )

Para acceder al valor de un campo, utilizamos ..

r.c.d;

Podemos ver los campos definidos con RecNames.

RecNames(r);

[ "b", "a", "c" ]

O ver si un campo está asignado o no

IsBound(r.g);

false

Unbind(r.b);

r;

rec( a := 5, c := rec( d := 1, e := 3 ) )

Al igual que en listas, si queremos hacer una copia, es recomendable utilizar ShallowCopy.

rr:=ShallowCopy(r);

rec( a := 5, c := rec( d := 1, e := 3 ) )

rr.c.d:=4;

r;

rec( a := 5, c := rec( d := 4, e := 3 ) )

El problema aquí es que r contiene a su vez otro registro. Para evitar esto, utilizamos StructuralCopy.

rr:=StructuralCopy(r);

rec( a := 5, c := rec( d := 4, e := 3 ) )

rr.c.d:=1;

r;

rec( a := 5, c := rec( d := 4, e := 3 ) )

rr;

rec( a := 5, c := rec( d := 1, e := 3 ) )

Algunos ejemplos de programación

En gap se pueden utilizar comandos como for, while, repeat .. until para hacer bucles.

Veamos cómo definir el factorial de distintas formas, utilizando distintos estilos de implementación.

f:=function(x)
    local p, i; #variable local para el producto parcial y contador
    
    p:=1;
    for i in [1..x] do
        p:=p*i;
    od; #final de bucle
    
    return p; #salida
end;

function( x ) ... end

f(3);

De forma recursiva…

f:=function(x)

    if x=0 then
        return 1;
    fi;
    
    return x*f(x-1);
end;

function( x ) ... end

f(100);

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Usando funciones específicas de listas y \(\lambda\)-expresiones …

f:=x->Product([1..x]);

function( x ) ... end

f(150);

57133839564458545904789328652610540031895535786011264182548375833179829124845398393126574488675311145377107878746854204162666250198684504466355949195922066574942592095735778929325357290444962472405416790722118445437122269675520000000000000000000000000000000000000

Calculamos ahora el primer entero perfecto y los enteros perfectos entre 1 y 100000. Para ello usaremos First.

es_perfecto:=x->(Sum(DivisorsInt(x))=2*x);

function( x ) ... end

First([1..200],es_perfecto);

Filtered([1..1000],es_perfecto);

[ 6, 28, 496 ]

Veamos si todos los números entre 100 y 500 son perfectos, o si hay alguno.

ForAll([100..500], es_perfecto);

false

ForAny([100..500], es_perfecto);

true

Hacemos algo parecido con los pares de números amigos.

son_amigos:=function(x,y)
    local dx, dy; #divisores de x e y
    
    if x=y or IsPrime(x) then 
        return false;
    fi; #queremos buscar parejas distintas y que no sean primos
    dx:=List(DivisorsInt(x)); 
    Remove(dx);; #le quitamos x
    dy:=List(DivisorsInt(y));
    Remove(dy);; #le quitamos y
    return (Sum(dx)=y) and (x=Sum(dy));
end;

function( x, y ) ... end

Para ver qué números entre 1 y 50 tienen amigos, escribimos, por ejemplo, lo siguiente.

l:=Filtered([1..250],x->ForAny([1..500],y->son_amigos(x,y)));

[ 220 ]

List(l,x->[x,First([1..550],y->son_amigos(x,y))]);

[ [ 220, 284 ] ]

Si queremos buscar en una lista más grande, podemos usar iteradores.

l:=IteratorOfCartesianProduct([1..1500],[1..1500]);

<object>

for x in l do
if (x[1]<x[2]) and son_amigos(x[1],x[2]) then
    Print(x,"\n");
fi;
od;

[ 220, 284 ]
[ 1184, 1210 ]