Introduction à brainfuck

Aujourd'hui, un petit post détente et amusement : on va découvrir le brainfuck.

Brainfuck, c'est quoi ?

C'est un Turing-tarpit, un langage Turing-complet minimaliste. Son intérêt et de présenter 8 opérateurs ('<','>','+','-','.','.','[',']') et aucune opérande, et de pouvoir implémenter n'importe quel algorithme (pourvu que la taille de la mémoire soit infinie).

Mode de fonctionnement

La machine Brainfuck est constituée de 5 élements :

• Un pointeur, ou tête de lecture, qui peut lire et écrire des données, et se déplacer de manière séquentielle


• Une bande de mémoire, qui peut contenir des valeurs entières


• Un lecteur de programme, qui ne peut être contrôlé que par lui-même


• Un gestionnaire d'entrées (clavier)


• Un moyen de sortie (écran/imprimante)

  

Les opérateurs agissent sur la tête de lecture, à l'exception de [ et ] qui agissent sur le lecteur de programme.

• + incrémente la valeur dans l'élement sous la tête de lecture


• - la décrémente


• < décale la tête de lecture vers la gauche


• > vers la droite


• , demande l'entrée d'une valeur et la stocke là où la tête de lecture se trouve


• . imprime la valeur contenue sous la tête de lecture


• [ marque le début d'une boucle executée si la valeur sous la tête de lecture est différente de 0.


• ] marque la fin de la boucle : quand on le rencontre, on retourne au [ associé (Brainfuck maintient une pile d'associations en interne)
  

Tout ce qui n'est pas l'un de ces 8 caractères est considéré comme commentaire.

Exemples de programmes

Additionner deux valeurs. Ce programme lit deux valeurs, les additionne et affiche le résultat. Il détruit les deux variables d'entrée (i.e. les modifie)

,>,< on lit les 2 valeurs
[ debut de la boucle
->+<
]
>. on decale et on affiche

Faire le perroquet jusqu'à ce que l'on tape sur entrée (ASCII 10)

, on lit le premier caractère
=D[début de la boucle
|  , on lit le caractère
|  . on l'affiche
|  -----
|  ----- on lui soustrait 10
| ] fin de la boucle, on retourne au début (suivre la fleche)

Idées de programmes pour aller plus loin

• Un programme qui copie une variable dans la case mémoire d'à côté (sans détruire la source)


• Un programme qui affiche une chaîne de caractère déjà enregistrée (hint : elles se terminent par une valeur nulle)


• Un programme qui prend une chaîne de caractère en entrée, jusqu'à ce que l'on appuie sur Entrée, puis qui la lit à l'endroit, puis à l'envers.


• Un multiplicateur, destructeur ou non

Trier et filtrer selon des prédicats

La documentation MSDN est pour le moins sybilline sur comment utiliser le tri avec un prédicat (c'est à dire, en précisant le paramètre de tri dans l'argument). C'est un bon premier exemple pour utiliser les delegates (méthodes anonymes).

Premier cas de tri : trier une Liste générique à l'envers

Supposons par exemple que l'on veuille trier les élements d'une List<T> à l'envers. Ici, T implémentera IComparable, et aura donc la méthode public int CompareTo(T element), qui renvoie 0 si les deux élements sont égaux, -1 si l'élement element est plus grand que notre instance, et 1 sinon.

La méthode CompareTo est appelée par défaut. Toutefois, on veut trier à l'envers. La solution sale et à éviter est :
1/ Trier à l'endroit
2/ Inverser la liste

En effet, on peut faire autrement et de manière beaucoup plus jolie, en utilisant un delegate qui implémente (implicitement) IComparer.

A supposer que la liste soit nommée maListe, on fera :

maListe.Sort(delegate(T el1, T el2) { 
return - el1.CompareTo(el2); 
});

Deuxième cas de tri : trier des objets selon leurs champs

On peut aussi imaginer le cas d'une collection d'objets de classe MaLigne qui comportent chacun trois champs de type String, nommés s1, s2, s3.
Cette collection peut être la représentation logique d'un tableau à 3 colonnes, par exemple. On veut pouvoir trier en ordre ascendant la liste selon s1, s2, ou s3.
Pour ce faire, on va encore utiliser un delegate et le fait que les String soient comparables les unes avec les autres. A supposer que notre collection soit une List<MaLigne> de nom monTableau

// trier selon s1
monTableau.Sort(delegate(MaLigne el1, 
MaLigne el2)
{ 
return el1.s1.CompareTo(el2.s1); 
});
// trier selon s2
monTableau.Sort(delegate(MaLigne el1, 
MaLigne el2)
{ 
return el1.s2.CompareTo(el2.s2); 
});
// trier selon s3
monTableau.Sort(delegate(MaLigne el1,
MaLigne el2)
{ 
return el1.s3.CompareTo(el2.s3); 
});

Pour trier dans l'ordre inverse, il suffit de mettre un petit "-" juste après le return. Comme vous pouvez le voir, les facilités de tri sont très importantes en C#.

Filtrer une collection

La méthode préférée pour filtrer une collection est d'utiliser FindAll. FindAll prend un prédicat (une condition à vérifier) et retourne une liste chaînée (une List<T>) contenant les élements de la liste qui correspondent à ce prédicat. Le prédicat devra retourner cette fois un booléen selon que l'élement corresponde ou pas.

Un exemple : supposons que l'on ait une List<CompteEnBanque> comptesEnBanque. Un CompteEnBanque a, entre autres, un champ Solde, de type double (signé).
Pour obtenir la liste des comptes à découvert, on procède ainsi :

List<CompteEnBanque> aDecouvert = 
  comptesEnBanque.FindAll(delegate(CompteEnBanque c)
{ 
return c.Solde < 0; 
});

Quelques remarques

Vous remarquerez que les delegate anonymes n'ont pas de signature. On n'écrit pas int delegate(Foo f, Foo g){}.
On peut aussi trier et filtrer selon des méthodes définies et nommées. Je vous renvoie à la documentation MSDN pour des exemples.

Generics en C#

Il paraît que C# fait un tas de choses merveilleuses au niveau orienté-objet. Entre autres choses, il est capable de travailler avec des générics (le plus souvent des collections d'élements de type inconnu, plus ou moins précisé).

Utiliser les types génériques déjà fournis

C# propose déjà la plupart des collections génériques dont vous aurez besoin dans des programmes et algorithmes habituels.

List<T>

Ce type fournit une liste chaînée. T est une classe héritant d'Object (donc, n'importe quelle classe). Si T implémente ISortable, alors la List<t>sera triable.
Pour les méthodes, elles sont très explicites. Un exemple :

List<String> s = new List<String>(30);// ce constructeur initialise une liste à la contenance de 30 élements, par défaut
s.Add("toto"); // ajoute la chaîne toto, un objet sans référence autre que dans la liste, à s.
String st = "titi";
s.Add(st); // l'ajout se fait par référence, non pas par copie. Si on altère st, le contenu de la liste sera altéré
s.Add(1,"Ga"); // la chaîne Ga est ajoutée entre toto et titi
Console.WriteLine(s.Contains("Bu")); // affiche false
Console.WriteLine(s.Contains("Ga")); // affiche true
s.ExcessTrim() ;     // libère la mémoire non-utilisée par la liste.
                     // Penser à le faire une fois qu'elle est remplie,
                     // Il vaut mieux allouer en excès puis libérer la mémoire
                     // que devoir réallouer de la mémoire à chaque fois qu'on ajoute un élement
                     // (sauf contraintes particulières, du type systèmes embarqués)
Console.WriteLine(s.Count) ; // affiche 3
s.Clear(); //vide s
Console.WriteLine(s.Count) ; // affiche 0

Note : on peut aussi parcourir un dictionnaire avec foreach

foreach (T element in maListeGenerique)
{
    element.Squeeze();
}

Dictionary<T1,T2>

Ce type est le type Dictionnaire habituel : à une clé de type T1, on associe une valeur de type T2. Les clés de type T1 ne peuvent être dupliquées (i.e., deux clés ne peuvent être égales). Si on tente d'insérer deux élements avec la même clé, alors on une exception ArgumentException sera levée. A vous de la gérer dans vos programmes. Les méthodes sont encore une fois très explicites, je vous renvoie à la documentation MSDN pour quelques infos. On peut trier un Dictionary selon ses clés ou selon ses valeurs, pourvu que les clés ou les valeurs implément ISortable. Il suffira alors d'appeller monDictionnaire.Keys.Sort() ou monDictionnaire.Values.Sort() pour trier la collection (les joies de l'accès par référence).

Implémenter son propre type générique

Ici, on va supposer qu'on a besoin d'implémenter une pile (LIFO, donc, le dernier élement entré sera le premier à sortir) générique. Ne me demandez pas quel intérêt il y a à cela, à vous de le trouver ;-)

Pour ce faire, comme on ne cherche pas forcément la performance, on va simplement utiliser une liste en interne, que l'on va modifier. Notre pile pourra être énumérée, c'est à dire qu'on pourra la parcourir avec un foreach (qui poppera une valeur hors de la liste et la renverra).

namespace MesExperimentations{
  public class MaStack<T> : IEnumerable
  {
   private List<T> pListeInterne;
   public MaStack()
   {
    pListeInterne = new List<T>();
   }

   public MaStack(int capacity)
   {
    pListeInterne = new List<T>(capacity);
   }

   public T Pop()
   {
    T element = maListe[maListe.Count-1];
    maListe.RemoveAt(maListe.Count-1); // retire le dernier element de la liste
    return element;
   }

   public void Push(T element)
   {
    maListe.Insert(maListe.Count,element); // insère l'élement au bout de la liste
   }
   // ceci est la méthode à implémenter pour IEnumerable
   public IEnumerator<T> GetEnumerator()
   {
    int taille = maListe.Count;
    while (taille>=0)
    {
         taille --;
         yield return maListe[taille];
         // un raccourci de C# pour éviter une syntaxe plus lourde
         // le mot yield est un mot magique pour l'énumération.
         // il permet de faire des "return multiples" en un seul bloc de code,
         // sans devoir maintenir de variable globale
    }
   }
  }
}

Spécifier des contraintes sur T

Dans certains cas, faire une collection 100% générique n'est pas une bonne idée. Par exemple, on peut imaginer une liste qui se trie automatiquement à l'insertion. Donc, son type T devra implémenter ISortable. Je ne vais pas l'implémenter ici, je vous laisse le faire.

La première ligne de la classe sera :

public class ListeTriee<T> : List<T> where T: ISortable

Ici, la classe ListeTriee étend la classe List mais impose que le type T implémente l'interface ISortable (celle qui permet de trier).

Un dernier mot

Pour aller plus loin et plus en profondeur, comme toujours, rendez-vous sur MSDN library et faites des recherches sur Generics.