Programmation génétique
Génération itérative de code
Machines de Turing
Automate à pile
Automate fini
Bascules
Segments de code
Autres exemples

Cet exemple provient de la section 10.2 (Symbolic Regression with Constant Creation) du livre Genetic Programming: on the programming of computers by means of natural selection de John R. Koza, ISBN 978-0-262-11170-6.

La courbe à découvrir est :

2.718x² + 3.1416x

Le fichier sym-reg-test-cases.dat contient 20 valeurs aléatoires de x entre -1 et 1. La seconde colonne contient l'ordonnée de la courbe. Le programme utilisé est gp-example.astl. Y voir les commentaires pour le rouler sur votre ordinateur.

Sur Windows, la solution trouvée à la génération 44 est :

x * (x + (-0.2162846767 - x + 0.7376628925 + (pdiv(x, 0.9688711203) + (pdiv(x, 0.8065126499) - (-0.03921628468 - x + (x + 0.01388592181)) + (-0.4843592639 + 0.9697866756) * x + 0.7376628925) + -0.03921628468 * x + 0.4240546892)) + (x + x * -0.8399609363) * x * (x - x) * pdiv(x, pdiv(0.9697866756, 0.9688711203) + x * (x - 0.9697866756 * (x + x * x - x * x))) + 0.4240546892) + x

Expression qui est équivalente à :

2.71825x² + 3.13248x

Sur Linux la convergence est plus rapide. Sur Mac OS, deux essais supplémentaires avec des arguments différents à srand m'ont été nécessaires. Une solution a été trouvée avec 1979 comme seed au lieu de 42.

La fonction make_trans_func utilisée dans les exemples ci-dessous élimine les énoncés répétitifs.

Sans elle dans l'exemple d'automate à pile, le code aurait l'air de :

# Transitions (non automodifiant)
make_trans = function(init_state, input_symbol, popped_symbol, new_state, 
   pushed_symbol)
{
   transition = names("init_state", "input_symbol", "popped_symbol", 
      "new_state", "pushed_symbol")
   transition.init_state = init_state
   transition.input_symbol = input_symbol
   transition.popped_symbol = popped_symbol
   transition.new_state = new_state
   transition.pushed_symbol = pushed_symbol
   transition
}

Machine de Turing #1. Requière gen-trans-func.astl et run_machine.astl.

Proche des transitions, les deux symboles (x / y) sont:

• x : le symbole sous la tête
• y : l'action accomplie

L'action peut être :

• R : déplacer la tête vers la droite
• L : déplacer la tête vers la gauche
• autre: le symbole à écrire

L'espace vide est représenté par Delta.

---

Machine de Turing #2. Requière gen-trans-func.astl et run_machine.astl.

Un automate à pile. Requière gen-trans-func.astl.

Au dessus des transitions, les trois symboles (x, y; z) sont :

• x: le symbole lu
• y: le symbole dépilé
• z: le symbole empilé

La séquence vide est représentée par lambda.

Un automate fini déterministe.

Le code suivant démontre une de trois façons de définir une fonction qui affiche deux résultats alternativement.

# premiere facon
# definition de la fonction:
a = function()
{
   print(1)
   if (value(a.childset[1].childset[0].childset[1].childset[0]) == 1)
   {
      a.childset[1].childset[0] = `print(2)'
   } 
   else
   {
      a.childset[1].childset[0] = `print(1)'
   }
   {}   
}
# appels a la fonction
a()
a()

Dans la première façon:

• a.childset[0] donnerait une référence à la liste de paramètre de la fonction "a". La structure de l'arbre d'une définition de fonction est illustrée ici.
• a.childset[1] donne une référence à la liste d'énoncés de la fonction "a".
• a.childset[1].childset[0] donne une référence au premier énoncé de la liste précédente.
• a.childset[1].childset[0].childset[0] donnerait une référence au noeud nom de l'appel à "print". La structure de l'arbre d'appel est illustrée ici.
• a.childset[1].childset[0].childset[1] donne une référence à la liste d'arguments de l'appel à "print".
• a.childset[1].childset[0].childset[1].childset[0] donne une référence au premier élément de la liste précédente, ie au premier argument de l'appel à "print".

Les commentaires d'une ligne doivent commencer avec # et nous terminons la liste d'énoncés du corps de "a" par {} pour éviter l'affichage de la valeur de l'assignation dans le "else".

# deuxieme facon
a = function()
{
   print(1)
   # arglist, value call, operator==, if, stmtlist
   if (value(parent.parent.parent.parent.parent
      .childset[0].childset[1].childset[0]) == 1)
   {
      a.childset[1].childset[0] = `print(2)'
   }
   else
   {
      a.childset[1].childset[0] = `print(1)'
   }
   {}   
}
a()
a()

Dans la deuxième façon:

• parent donne une référence au noeud liste d'arguments de l'appel à "value".
• parent.parent donne une référence au noeud d'appel à "value".
• parent.parent.parent donne une référence au noeud de l'opérateur ==. Ce noeud est aussi le noeud condition de l'énoncé "if".
• parent.parent.parent.parent donne une référence au noeud "if".
• parent.parent.parent.parent.parent donne une référence au noeud liste d'énoncés de la fonction "a".
• Le .childset[0] additionnel donne une référence à au noeud d'appel à "print".
• Le .childset[1] additionnel donne une référence à la liste d'arguments de l'appel à "print".
• Le .childset[0] additionnel donne une référence au premier argument de l'appel à "print".

# troisieme facon
a = function()
{
   print(1)
   b = parent.parent.childset[0].childset[1].childset[0]
   if (value(b) == 1)
   {
      *b = `2'
   }
   else
   {
      *b = `1'
   }
   {}
}
a()
a()

Dans la troisième façon, nous utilisons l'opérateur unaire * avec l'intention d'avoir l'assignation faite au noeud référencé par la variable "b".

S'ils n'étaient pas à l'intérieur du corps d'une fonction le "else" ne pourrait pas être placé au début d'une nouvelle ligne. Placer un "else" au début d'une nouvelle ligne produirait une erreur de syntaxe.

---

Une fonction affichant alternativement trois résultats.

---

Une fonction générant des fonctions affichant alternativement n résultats.

Vous pouvez utiliser des segments de code comme points de départ pour des listes pointillées généalogiques.

> info(` "abc" ')
[node_type]     "code segment"
[nb_children]   1
>
> info(` "abc" '.childset[0])
[node_type]     "string"
[nb_children]   0
[value] "abc"
>
> info(` "abc" != "cba" '.childset[0])
[node_type]     "relational or logical operator"
[nb_children]   2
[operator]      "!="
>
> info(` function(x) x '.childset[0])
[node_type]     "function definition"
[nb_children]   2
[parameters][0] "x"

Quand vous assignez un segment de code à un noeud existant, vous n'avez pas à obtenir la racine du code en utilisant la forme `{code ici}'.childset[0]. Utiliser la fome `{code ici}' est suffisant.

Une fonction récursive.

---

Exemples de base

L'exemple de session suivant démontre l'usage des mots clé et l'usage de la fonction interne info qui donne le type du noeud duquel elle reçoit la référence et quelques utiles informations à propos du noeud. Les énoncés PCASTL sont après les symboles '>' et les sorties de l'interpréteur sont dans les lignes qui commencent par des espaces.

> a = parent
        0x4318e0
> info(a)
[node_type]     "mathematical operator"
[nb_children]   2
[operator]      =
>
> info(a.childset[0])
[node_type]     "variable"
[nb_children]   0
[name]  "a"
>
> info(a.childset[1])
[node_type]     "list"
[nb_children]   1
>
> info(a.childset[1].childset[0])
[node_type]     "parent reserved word"
[nb_children]   0
>
> a.childset[0].parent
        0x4318e0
> a.childset[1].parent
        0x4318e0

Après l'assignation d'une valeur à une variable, l'interpréteur retourne la valeur. L'adresse que nous voyons (0x330878) est dans ce cas l'adresse du noeud qui contient l'opérateur. Nous obtenons aussi une adresse quand nous définissons une fonction et quand nous déclarons un segment de code explicite. Le code que nous venons juste d'utiliser est illustré dans l'image ci-dessous.

Une liste pointillée généalogique est une liste de mots clé "parent" et "childset" séparés par des points. Le mot clé "parent" seul est une liste pointillée généalogique d'un item.

La session suivante utilise une liste pointillée généalogique de deux items.

> a = parent.childset[1]
        0x431560
> info(a)
[node_type]     "list"
[nb_children]   2
>
> info(a.childset[1])
[node_type]     "childset reserved word"
[nb_children]   1
>
> info(a.childset[1].childset[0])
[node_type]     "numerical constant"
[nb_children]   0
[value] 1

La structure du premier énoncé de l'exemple précédent est illustrée ci-dessous.

---

Le PCASTL sur Wikipedia (avec des exemples très de base).

 

retour au PCASTL