Перейти к главе: Начало 1 2 3 4 A B C Bib Ind
 [Начало книги]  [Содержание]   [Предыдущая глава]   [Следующая глава] 

2 Язык программирования GAP
 2.1 Символы и категории слов в GAP
 2.2 Ключевые слова
 2.3 Идентификаторы
 2.4 Выражения
 2.5 Обращения к функциям
 2.6 Сравнение выражений
 2.7 Арифметические операторы
 2.8 Присваивания
 2.9 Вызов процедуры
 2.10 Команда IF
 2.11 Цикл WHILE
 2.12 Цикл REPEAT
 2.13 Цикл FOR
 2.14 Функции
 2.15 Команда RETURN

2 Язык программирования GAP

2.1 Символы и категории слов в GAP

GAP воспринимает следующие символы: цифры, буквы (верхний и нижний регистры), пробел, символы табуляции и новой строки, а также специальные символы:


"     `     (     )     *     +     ,     _     #
.     /     :     ;     <     =     >     ~     &
[     \     ]     ^     _     {     }     ! 

Составленные из символов слова относятся к следующим категориям:

Следует заметить, что пробелы могут быть использованы для повышения удобочитаемости текста, так как любая последовательность пробелов воспринимается GAP как один пробел. Таким образом, команда


if i<0 then a:=-i;else a:=i;fi; 

может быть записана следующим образом:


if i < 0  then # если i отрицательное 
    a := -i; 
else           # иначе 
    a := i; 
fi;

2.2 Ключевые слова

Ключевыми словами GAP являются следующие слова:


and         do         elif      else       end        fi
for        function    if        in         local      mod
not        od          or        repeat     return     then
until      while       quit      QUIT       break      rec 
continue

2.3 Идентификаторы

Идентификаторы состоят из букв, цифр, символов подчеркивания _, и должны содержать не менее одной буквы или символа подчеркивания _. При этом регистр является существенным. Примеры идентификаторов:


a                  foo              LongIdentifier
hello              Hello            HELLO 
x100               100x             _100 
underscores_case   MixedCase 

2.4 Выражения

Примерами выражений являются: переменные, обращения к функциям, целые числа, перестановки, строки, функции, списки, записи. С помощью операторов из них могут быть составлены более сложные выражения. Операторы разбиты на три класса:

Пример 1:


gap>2*2;; #два знака ";" подавляют вывод на экран 
gap>2*2+9=Fibonacci(7) and Fibonacci(13) in Prime;
true 

Следует различать глобальные и локальные переменные, различия которых можно видеть из следующего примера: Пример 2:


g := 0;        # глобальная переменная g 
x := function ( a, b, c ) 
   local   y; 
   g := c;     # c - аргумент функции x 
   y := function ( y ) 
       local  d, e, f; 
       d := y; # y - аргумент функции y 
       e := b; # b - аргумент функции x 
       f := g; # g - глобальная переменная g 
       return d + e + f; 
   end; 
   return y(a); # y-локальная переменная функции x
end; 

2.5 Обращения к функциям

Формат:


function-var() 
function-var( arg-expr {, arg-expr} ) 

Пример 1:


gap> Fibonacci( 11 ); # обращение к функции "Fibonacci" с аргументом 11
89

Пример 2: обращение к операции RightCosets, в котором второй аргумент определяется обращением к другой функции


gap> RightCosets( G, Intersection( U, V ) );

2.6 Сравнение выражений

Формат:


left-expr = right-expr 
left-expr <> right-expr
left-expr < right-expr 
left-expr > right-expr 
left-expr <= right-expr 
left-expr >= right-expr 

Операторы = и <> проверяют соответственно равенство и неравенство, возвращая true или false. Заметьте, что с их помощью можно сравнивать любые объекты, т.е. при использовании = и <> никогда не будет получено сообщение об ошибке. Для каждого типа объектов определение равенства может отличаться и описано в соответствующем разделе справочного руководства. Объекты, относящиеся к различным семействам (families) всегда различны, т.е. = приведет к false, и <> - к true. Кроме того, в некоторых случаях для них может быть определено отношение "меньше". Операторы сравнения имеют больший приоритет по сравнению с логическими операторами, но меньший по сравнению с арифметическими. Например, a*b = c and d интерпретируется как ((a*b)=c) and d). Еще один пример (сравнение, левая часть которого является выражением ):


gap> 2 * 2 + 9 = Fibonacci(7); 
true 

2.7 Арифметические операторы

Формат:


+ right-expr 
- right-expr 
left-expr + right-expr 
left-expr - right-expr 
left-expr * right-expr 
left-expr / right-expr 
left-expr mod right-expr 
left-expr ^ right-expr 

Значение, как правило, зависит от типа операндов. mod определен только для целых и рациональных чисел. Для элемента группы ^ означает возведение в степень, если правый операнд - целое число, а если он - элемент группы, то сопряжение с его помощью. Приоритет операторов (по убыванию):

Пример:


-2 ^ -2 * 3 + 1 

означает


(-(2 ^ (-2)) * 3) + 1 

Арифметические операторы имеют наивысший приоритет по сравнению с операторами сравнения и логическими операторами.

2.8 Присваивания

Командами в GAP называются: присваивания, вызовы процедур, структуры if, while, repeat, for, а также команда return. Все команды заканчиваются точкой с запятой ";". Присваивания имеют формат


var := expr; 

Пример:


gap> data:= rec( numbers:= [ 1, 2, 3 ] );
rec( numbers := [ 1, 2, 3 ] )
gap> data.string:= "string";; data;
rec( numbers := [ 1, 2, 3 ], string := "string" )
gap> data.numbers[2]:= 4;; data;
rec( numbers := [ 1, 4, 3 ], string := "string" )

2.9 Вызов процедуры

Формат:


procedure-var(); 
procedure-var( arg-expr {, arg-expr} ); 

Различие между процедурами и функциями введено для удобства, GAP же их не различает. Функция возвращает значение, но не производит побочных эффектов. Процедура не возвращает никакого значения, но производит какое-либо действие (например, процедуры Print, Append, Sort).

2.10 Команда IF

Формат:


if bool-expr1 then statements1 
  { elif bool-expr2 then statements2 } 
  [ else statements3 ] 
fi; 

При этом частей elif может быть произвольное количество или ни одной. Часть else также может отсутствовать. Пример 1: в командах


if expr1 then 
   if expr2 then stats1 
   else stats2 fi; 
fi; 

else относится ко второму if, тогда как в командах


if expr1 then 
   if expr2 then stats1 fi; 
else stats2 
fi; 

else относится к первому if. Пример 2:


gap> i := 10;; 
gap> if 0 < i  then 
>        s := 1; 
>    elif i < 0  then 
>        s := -1; 
>    else 
>        s := 0; 
>    fi; 
gap> s; # знак i
1

2.11 Цикл WHILE

Формат:


while bool-expr do statements od; 

Последовательность команд statements выполняется, пока истинно условие bool-expr. При этом сначала проверяется условие, а затем, если оно истинно, выполняются команды. Если уже при первом обращении условие ложно, то последовательность команд statements не выполнится ни разу. Пример:


gap> i := 0;;  s := 0;; 
gap> while s <= 200  do 
>        i := i + 1;  s := s + i^2; 
>    od; 
gap> s; 
204 

2.12 Цикл REPEAT

Формат:


repeat statements until bool-expr; 

Последовательность команд statements выполняется до тех пор, пока не будет выполняться условие bool-expr. При этом сначала выполняются команды, а затем проверяется условие. Таким образом, при любом начальном значении условия набор команд statements выполнится, по крайней мере, один раз. Пример (вычисление наименьшей суммы квадратов первых n последовательных натуральных чисел, превышающей 200):


gap> i := 0;;  s := 0;; 
gap> repeat 
>        i := i + 1;  s := s + i^2; 
>    until s > 200; 
gap> s; 
204 

2.13 Цикл FOR

Форматы:


for simple-var in list-expr do statements od;
for variable in iterator do statements od; 
for variable in object do statements od;

В первом варианте последовательность команд statements выполняется для каждого элемента из списка list-expr. Цикл for эквивалентен циклу while:


loop-list := list; 
loop-index:= 1; 
while loop-index <= Length(loop-list) do 
  variable := loop-list[loop-index]; 
  ... 
  statements 
  ... 
  loop-index := loop-index+1; 
od; 

Список list часто является последовательностью. Команда


for variable in [from..to] do statements od; 

соответствует распространенной в других языках команде


for variable from from to to do statements od; 

Пример:


gap> s := 0;; 
gap> for i  in [1..100]  do 
>        s := s + i; 
> od; 
gap> s; 
5050 

В следующем примере изменение списка приводит к выполнению команд для новых его элементов:


gap> l := [ 1, 2, 3, 4, 5, 6 ];; 
gap> for i  in l  do 
>        Print( i, " " ); 
>        if i mod 2 = 0 then Add( l, 3*i/2 ); fi;
> od;  Print( "\n" ); 
1 2 3 4 5 6 3 6 9 9 
gap> l; 
[ 1, 2, 3, 4, 5, 6, 3, 6, 9, 9 ] 

А в следующем - не приводит:


gap> l := [ 1, 2, 3, 4, 5, 6 ];; 
gap> for i  in l  do 
>        Print( i, " " ); 
>        l := []; 
> od;  Print( "\n" ); 
1 2 3 4 5 6 
gap> l; 
[  ] 

Теперь рассмотрим оставшиеся два варианта цикла FOR:


for variable in iterator do statements od; 
for variable in object do statements od;

Для этого необходимо сначала ввести некоторые понятия, характеризующие объекты, с которыми работает GAP. Каждый объект имеет свой тип. Тип объекта - это информация, которая используется для того, чтобы решить, применима ли к объекту данная операция, и, для выбора метода ее применения в случае положительного ответа. Например, тип двух объектов определяет, могут ли они быть умножены друг на друга, и если да, то каким способом. Аналогично, тип объекта определяет, может ли быть вычислен порядок (размер) этого объекта, и если да, то как. Тип объекта состоит из двух основных частей, характеризующих разные аспекты объекта, а именно из семейства, к которому он принадлежит, и из набора фильтров. Семейство определяет отношение данного объекта к другим объектам. Например, семейство образуют все подстановки. Другой пример семейства - семейство всех коллекций (collections), подстановок. Последнее семейство содержит множество всех групп подстановок в качестве подмножества. Третий пример - семейство всех рациональных функций с коэффициентами из некоторого семейства. Фильтр можно описать как последовательность true и false, характеризующую соответствующие параметры данного типа объектов (например, IsAbelian, IsPrime, IsGroup и т.п.). Хотя при выборе метода фильтры не различаются по их происхождению и применению, их можно классифицировать (с небольшими исключениями) на категории, представления, свойства, а также тестеры атрибутов. Набор элементов, лежащих в одном семействе, называется коллекцией. Примерами коллекций являются однородные списки, а также домены (domain) - так в GAP называются множества с дополнительной структурой, например, группа, класс сопряженных элементов, векторное пространство и т.д. Пусть теперь C - коллекция. Тогда итератор Iterator(C) позволяет организовать перебор всех элементов этой коллекции без повторений. В этом случае цикл FOR эквивалентен следующему циклу:


while not IsDoneIterator(iterator) do 
    variable := NextIterator(iterator) 
    statements 
od; 

Если же D - домен, то результат выполнения цикла вида


for variable in domain do 

должен быть таким же, как результат выполнения цикла вида


for variable in AsList(D) do

Если в цикле FOR объект object не является списком или итератором, то будет вычисляться Iterator(object). Если это вычисление будет успешным, то будет реализован перебор по итератору.


gap> g := Group((1,2,3,4,5),(1,2)(3,4)(5,6));
Group([ (1,2,3,4,5), (1,2)(3,4)(5,6) ])
gap> count := 0;; sumord := 0;;
gap> for x in g do
> count := count + 1; sumord := sumord + Order(x); od;
gap> count;
120
gap> sumord;
471

Такая конструкция использует намного меньше памяти, так как итератор может быть намного более компактным, чем список всех элементов. Из цикла FOR можно выйти до его выполнения, используя оператор break. Это особенно эффективно в комбинации с циклом по итератору, например, для поиска элемента с нужным свойством в некотором домене. Этот оператор может быть использован только внутри цикла.


gap> g := Group((1,2,3,4,5),(1,2)(3,4)(5,6));
Group([ (1,2,3,4,5), (1,2)(3,4)(5,6) ])
gap> for x in g do
> if Order(x) = 3 then
> break;
> fi; od;
gap> x;
(1,4,3)(2,6,5)

Оператор continue отменяет выполнение оставшейся части цикла и переходит сразу к выполнению следющей итерации. Этот оператор также может быть использован только внутри цикла.


gap> g := Group((1,2,3),(1,2));
Group([ (1,2,3), (1,2) ])
gap> for x in g do
> if Order(x) = 3 then
> continue;
> fi; Print(x,"\n"); od;
()
(2,3)
(1,3)
(1,2)

2.14 Функции

Формат:


function ( [ arg-ident {, arg-ident} ] ) 
           [ local loc-ident {, loc-ident} ; ] 
           statements 
           end 

Пример функции, которая определяет n-е число Фибоначчи:


gap> fib := function ( n ) 
>         local  f1,  f2,  f3,  i; 
>         f1 := 1;  f2 := 1; 
>         for i  in [3..n]  do 
>             f3 := f1 + f2; f1 := f2; f2 := f3; 
>         od; 
>         return f2; 
>     end;; 
gap> List( [1..10], fib ); 
[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ] 

Ту же функцию можно определить рекурсивно:


gap> fib := function ( n ) 
>         if n < 3  then 
>             return 1; 
>         else 
>             return fib(n-1) + fib(n-2); 
>         fi; 
>     end;; 
gap> List( [1..10], fib ); 
[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ] 

Заметим, что рекурсивная версия требует 2 fib(n) - 1 шагов для вычисления fib(n), тогда как итеративная требует только n-2 шага. Обе функции, однако, не являются оптимальными, так как библиотечная функция Fibonacci требует порядка log(n) шагов. Запись arg-ident -> expr является краткой записью для функции


function ( arg-ident ) return expr; end 

Здесь arg-ident - один идентификатор, т.е. таким образом нельзя задать функцию от нескольких переменных. Пример типичного использования такой записи:


gap> Sum( List( [1..100], x -> x^2 ) ); 
338350 

2.15 Команда RETURN

Формат:


return; 
return expr; 

Первая форма прерывает выполнение внутренней (при вызове одной функции из другой) функции и передает управление вызывающей функции, не возвращая при этом никакого значения. Вторая, кроме того, возвращает значение выражения expr.

 [Начало книги]  [Содержание]   [Предыдущая глава]   [Следующая глава] 
Перейти к главе: Начало 1 2 3 4 A B C Bib Ind

generated by GAPDoc2HTML