> < ^ From:

> < ^ Subject:

Subject: On the programming language `GAP'

Dear GAP-forum,

being an enthusiastic GAP user and programmer, I have

collected two suggestions on improving the GAP

language itself. Although I appreciate the idea of

`lean' languages, as for example GAP is, it seems

to me that GAP might benefit from these additions.

Especially ZF-comprehensions turned out to be so useful in

other languages I used before (Gofer, Haskell) that

I would be very glad to have it in GAP, too. In case these

ideas fit the general design considerations and

development strategy of the GAP-project I would

like to do actual implementation work on it.

Best regards,

Sebastian Egner.

1. ZF-comprehensions for lists and sets. ----------------------------------------

A Zermelo-Fraenkel-comprehension (ZF-c.) is a compact notation to

denote a collection (list or set) of objects. It resembles the

standard mathematical notation for comprehensions. An examples is

[ x^2 | for x in [100, 99 .. 1], IsPrime(x) ],

the list of squares of the primes not exceeding 100 in decending order.

Which could be written in GAP for example as

List(Filtered([100, 99 .. 1], IsPrime), x -> x^2)

or explicitly (not working as printed; name the function) as

( function () local result, x; result := []; for x in [100, 99 .. 1] do if IsPrime(x) then Add(result, x^2); fi; od; return result; end )()

Another example containing two generators ('for') yielding a set is

{ [n, r] | for n in [1..10], for r in PrimeResidues(n) },

the set of all pairs [n, r] being relative prime where 1 <= n <= 10.

This might be written in GAP as

Union(List([1..10], n -> List(PrimeResidues(n), r -> [n, r]))).

or explicitly (not working, too) as

( function () local result, n, r; result := Set([]); for n in [1..10] do for r in PrimeResidues(n) do AddSet(result, [n, r]); od; od; return result; end )()

The general ingrediences of a ZF-comprehension are

* iterators to loop formal variables (`x', `n', `r') over

structured homogeneous collections of objects (`[100, 99 .. 1]',

`[1..10]', `PrimeResidues(n)'),

* predicates to filter objects (`IsPrime(x)'), and

* collectors to form the resulting homogeneous collection

(`[ .. ]' and `{ .. }').

ZF-comprehensions do not add expressive power to the

GAP-language since they can always be replaced by expressions

in List(), Filtered(), Concatenation(), and Union().

However, they are very intuitive to read and write,

especially on the interactive input line. The implementation

has to be done in the underlying C-kernel since ZF-comprehensions

introduce a syntactic structures and set up a binding context

for the formal variables being used within the comprehension.

The syntactic expressions do not interfere with any other

existing structure, so old GAP-programs remain correct.

2. User-supplied iterators to run over structured objects ---------------------------------------------------------

The `for'-statement of GAP v3.x does only run over lists.

This implies that every time you iterate over the elements

of a structured object (like a group) the list of its

elements is formed before the iteration starts at all.

There is a particularly elegant way to extend the semantics

of the `for'-statement to run over structured objects:

The structured object obj has two additional fields in

its operations record to hold functions to do the iteration.

Namely an iterator record is produced by iter := newIterator(obj)

before the iteration begins. This record holds at least

the field iter.isEmpty containing a boolean value to indicate

if there is still an element to enumerate. While this flag

is false stepIterator(iter) modifies the iterator record

and sets iter.element to the current element.

The `for'-statement is augmented to recognize the case of

obj being no list but a record with an operations

field in which the two functions are available. In other words

obj := rec(

..special data of the object..

operations := rec(

newIterator := function (obj) .. return iter; end, # custom-made

stepIterator := function (iter) .. return; end, # dito.

..more operations for the object..

)

);

so the iteration

for x in obj do

..statements..

od;

is unrolled to mean something like

local iter;

iter := obj.operations.newIterator(obj);

while not iter.isEmpty do

obj.operations.stepIterator(iter);

x := iter.element;

..statements..

od;

This feature can be implemented in the GAP-language itself

but it will be most useful if the C-kernel is modified to

augment the `for'-statement --- especially in conjunction

with ZF-comprehensions. Namely `for' needs to set up a local

variable to hold the iterator. (Which must *not* be stored

in obj.) Note that the modification of the GAP-language is

limited to the `for'-statement, does not interfere with

the existing semantics of `for', and the feature does not

rely on peculiarities of any particular GAP-domain.

> < [top]