2.66        SETL

Linguaggio didattico per la teoria degli insiemi

SETL (SET Language) è stato sviluppato da Jacob T. Schwartz negli anni 1969-70 presso il Courant Institute. In seguito Gary Levin sviluppò ISETL (Interactive SET Language), per un utilizzo interattivo in ambienti Unix, DOS, e Macintosh alla Clarkson University. La versione per Windows, ISETLW, è dovuta a John Kirchmeyer del Mount Union College con l’aiuto di Jamie Wylie nel 1995, nel 2001 è disponibile la versione 3, sempre ad opera di John Kirchmeyer.

SETL è un linguaggio di programmazione indirizzato alla teoria degli insiemi, infatti oltre ai tipi elementari di dato, stringhe di caratteri, numeri interi illimitati, numeri reali, booleani, prevede:

·         tuple, liste di oggetti qualsivoglia, le tuple sono racchiuse da [],

·         set, insiemi di oggetti qualsivoglia ma non duplicati, gli insiemi sono racchiusi fra {},

·         map, insiemi di 2-tuple, con il primo componente funzionante come una chiave.

Una variabile non inizializzata ha il tipo di dato OM (omega).

Per l’utilizzo degli insiemi sono disponibili:

·         operazioni di unione, intersezione e differenza tramite gli operatori + o union, * o inter e – rispettivamente.

·         Costruttori (formers), peraltro utilizzati anche per le tuple e per le istruzioni di iterazione.

·         Funzioni di test: in, notin e subset.

·         Funzioni di estrazione e quantificazione: take ... from, choose, arb, forall ed exist.

·         Costruzione tramite condizione introdotta dai simboli, equivalenti, : o |, col significato di "tale che".

primo := func(n);

    ins := {p | p in {n} |(forall indx in {2.. p div 2}| p mod indx /= 0)};

    if #ins = 1 then

          return "primo"

    else

          return "non primo";

      end if;

end func;

numeri := {};   $ insieme vuoto

for indx in [3..50] do

    numeri := numeri union {[primo(indx),indx]};   $ insieme mappa

end for;

>     numeri{"primo"};

{17, 13, 3, 5, 11, 7, 23, 19, 31, 29, 43, 47, 37, 41};

>     arb(numeri);      $ estrazione di un elenco arbitrario 

["non primo", 38];

I selettori sono uno strumento efficace per trattare stringhe, tuple ed insiemi, hanno la forma n..m, dove n o m possono mancare:

>     stringa := "lafleur";

>     stringa(..3); $ left 3

"laf";

>     stringa(#stringa-2..); $ right 3 

"eur";

E’ possibile scrivere ed utilizzare librerie di moduli, la versione per Windows è fornita con funzioni per grafica vettoriale.

SETL ha aspetti funzionali, la definizione di un insieme, produce l’insieme:

>     {[a,b,c] : a,b,c in [1..20] | a < b and a**2 + b**2 =c**2};


{[3, 4, 5], [5, 12, 13], [6, 8, 10], [8, 15, 17], [12, 16, 20], [9, 12, 15]};

L’esempio che segue è una simulazione dell’evoluzione di una popolazione, rappresentata da numeri fra 0 e 255, tramite un’algoritmo genetico (embrionale). Gli individui con un particolare gene, per semplicità è il bit che rende il numero dispari, soccombono in maggior misura degli altri.

$ ISETLW ISETL for Windows Version 3.0 Beta 0

$ genpop generate n different peoples

genpop := func(x,n);

  while #x < n do

      x := x + {random({0..255})};

  end while;

  return x

end;

$ newpop generate a new individual, from two individual (mf is twople of eightple)

newpop := func(mf);

  new := 0;

  for bit in {1..8} do

      new := new + mf(arb([1,2]))(bit) * 2 **(bit-1)

  end for;

  return new

end;

 

$ extpop extract n peoples

extpop := func(x,n);

  extract := {};

  while #extract < n do

      extract := extract + {arb(x)};

  end while;

  return extract

end;

$ tobit transform number in bits

tobit := func(n);

      bits := [0,0,0,0,0,0,0,0];

      for i in [1..8] do

            bits(i) := n mod 2;

            n := n div 2;

      end;

      return bits;

end;

genetica := func();

print "Genetic Algorithm Simulation";

randomize(arb({1..100}));

sost := 0.2;      $ % of sostitution people

sostodd := 0.6;   $ % of sostitution odd people

npop := 100;      $ population number

$ generation of initial population

pop := {};

pop := genpop(pop,npop);

writeln "generation odd people even people restored";

for indx in [1..15] do

      $ extract a subset of discarded population

      oddelim := extpop({op |op in pop | op mod 2 /= 0},floor(npop*sost*sostodd));

      evenelim := extpop({op |op in pop | op mod 2 = 0},floor(npop*sost*(1-sostodd)));

      pop := pop-oddelim-evenelim;

      for cnt in [1..npop-#pop] do       $ regenerate peoples

            pop := pop + {newpop([tobit(arb(pop)),tobit(arb(pop))])};

      end;

      writeln indx,#{op |op in pop | op mod 2 /= 0}, #{op |op in pop | op mod 2 = 0},npop - #pop;

      $writeln "restore",npop - #pop," peoples";

      pop := genpop(pop,npop);           $ restore total polpulation (mutation)

      $write "even people:", #{op |op in pop | op mod 2 = 0};

      $writeln " odd people:",#{op |op in pop | op mod 2 /= 0};

end;

end; 

genetica();

 

"Genetic Algorithm Simulation";

generation odd people even people restored

         1        45        43        12

         2        43        46        11

         3        41        51         8

         4        37        52        11

         5        34        54        12

         6        35        55        10

         7        36        52        12

         8        34        55        11

         9        32        59         9

        10        29        59        12

        11        23        65        12

        12        20        68        12

        13        18        70        12

        14        21        66        13

        15        19        70        11