Une grille façon STL

Version imprimable

1 pièce(s) jointe(s)

Bonjour à tous.

Je me suis lancé il y a peu dans la réalisation d'un programme jouet.

Il s'agit d'un interpréteur C++ de langages étranges (dits ésotériques).
Je m'intéresse aux langages dont les instructions sont codées par des caractères.
Le célèbre brainf**k est un exemple, mais il y en a plein d'autres, tel que Path ou LNUSP.

Dans de nombreux cas, le pointeur d'instruction se déplace linéairement, mais peut tourner sur certaines instructions:
$---\
    |
    |
Partant du $, le code pointeur rebondit sur le slash, comme la lumière sur un miroir.

Voici un code source possible (quoi qu'inutile...)
$  !/     !\   #
    ,      .
    \ ++++ /
Pour exécuter le script, je crée une matrice de caractères, et je la parcoure.

Le problème, c'est qu'en général, la densité du code est très basse, et qu'il ne sert pas à rien de stoquer les instructions vides

J'ai pensé à créer un graphe d'instructions.

Le problème est devenu subitement beaucoup plus complexe quand j'ai décidé de rendre l'interpréteur générique en créant des fichiers de langages. (voir la pièce jointe)

Certains languages ont une grille à une dimension, d'autres à 3 ou 4.
Certains ont des opérateurs de rotation à 45 degrés.
$---q
     \
      \
D'autres proposent des "pas de cotés", qui déplacent le pointeur d'une case sur le côté, sans changer son déplacement.
$---v
    ----
J'ai essayé d'adapter mon graphe, mais je ne vois pas comment permettre tout cela.

En gros, j'ai besoin d'un itérateur ayant pour fonctionnalité un vecteur de déplacement, une position, le "case suivante" et le "avance jusqu'a la prochaine instruction"

Le tout dans une classe que j'imagine être templatée par le nombre de dimension de la grille.

Quelqu'un a-t'il une proposition?

Voici mon (nouveau) début de code.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 template<typename VALUE, int DIMENSION> class grid{ public: typedef std::array<int, DIMENSION> position_type; typedef VALUE value_type; private: class Slot{ typedef std::array<int, DIMENSION> position_type; position_type position; public: Slot(const position_type& place):position(place){} bool operator<(const Slot& other){ for(int i=0;i!=DIMENSION;++i){ if(position[i]!=other.position[i]) return position[i]<other.position[i]; } return false; } }; typedef std::map<Slot, VALUE> inner_type; inner_type cells; public: grid(); bool put(const position_type& slot, const value_type& value){ return false; } };
PS: voici deux sites pour les curieux sur les langages:
le magique 99 bottles of beer qui propose de nombreuses versions de l'affichage d'une comptine.
liste sur esolangs.org qui liste des langages souvent plus délirants les uns que les autres.

20/07/2012, 18h24
Obsidian
Hello,

Citation:

Envoyé par leternel

Le problème, c'est qu'en général, la densité du code est très basse, et qu'il ne sert pas à rien de stoquer les instructions vides

Si tu veux rentabiliser tes matrices creuses, je te conseille le whitespace. :-)

Citation:

Le problème est devenu subitement beaucoup plus complexe quand j'ai décidé de rendre l'interpréteur générique en créant des fichiers de langages. (voir la pièce jointe)

Bon, je ne sais pas quel degré de sérieux apporter à ta requête mais dans tous les cas, il faut que tu fasses les choses dans l'ordre, l'une après l'autre. Jette déjà un œil, si ce n'est déjà fait, à la théorie des langages pour voir comment écrire des parsers et des compilateurs génériques. Même avec les langages classiques à une seule dimension, il y a déjà de quoi faire et c'est quelque chose qui est très utilisé en informatique.

Ensuite, je ne vois pas beaucoup l'intérêt d'ajouter des dimensions au code comme tu le fait, pour deux raisons principales :
- Il s'agit toujours, dans les faits, de passer d'une instruction à une autre, et pas d'exécuter deux fils en parallèle. Ça revient donc à faire des gotos déguisés, ce qui est mis en évidence par ton graphe ;
- Une grille a plusieurs dimensions va forcément être creuse pour la bonne raison qu'il serait extrêmement long de la remplir. Avec trois dimensions, il faut n³ fois le temps qu'il te faudrait pour en remplir une seule, soit par exemple un milliard d'instructions là où tu en aurais mis seulement mille ailleurs.
Par contre, je te conseille également de te pencher sur les automates à pile si ce n'est pas déjà fait également : il s'agit d'un automate d'états fini ordinaire mais dont le diagramme des transitions dépend de l'élément au sommet d'une pile que tu remplis ou vide au fur et à mesure que tu parcours cet automate. Ça ressemble donc à un « automate à étages » et c'est assez proche des notions qui semblent flatter tes sens.
23/07/2012, 11h02
ternel
J'ai déjà quelques connaissances en théorie des langages, mes cours ne sont pas trop loin... Je vais réfléchir aux automates à piles, je n'y avais pas pensé.

Le problème auquel je me confronte est un défi personnel plus qu'autre chose.

La réalisation de l'interpréteur en tant que tel n'est pas un problème majeur. Il s'agit d'avoir deux itérateurs bien fichus (pointeur d'instruction et pointeur mémoire) et une liste d'opérateur, puis de répéter "ip.suivant(); ip.eval(mémoire);" jusqu'à terminaison du programme

Le parseur est plus complexe dans mon cas, puisque j'ai des discriminations importantes selon les langages.

D'où l'idée d'une classe de langage pour paramétrer le parseur créé.

J'obtiendrais ainsi les classes suivantes:
- mémoire
- mémoire::iterateur
- langage
- operateur
- des implémentations d'operateurs (plus ou moins parametrables)
- programme
- programme<?>
- programme<?>::iterateur
Parmi les subtilités apparaissant avec les grilles d'instructions (comme dans PATH), il y a les possibilités de parcourir des séquences d'instructions dans les deux sens ou de voir plusieurs séquences partagent une ou plusieurs instructions.
exemple de partage
```
1  \/\/\/|
2  aaaaaa\
3  bbbbbb/
   \/\/\/
```
en entrant en 1 vers la droite, on a la séquence abba abba abba abba abba abba, en ressortant en 1 vers la gauche
tandis qu'en commencant en 2 vers la droite on réalise aaaaaa bbbbbb en sortant en 3 vers la gauche.

Cela dit, une grille creuse peut aussi servir dans d'autres contexte, tel que des jeux de plateaux.