Tables de distribution (dispatch tables)

Imaginons que vous programmez un jeu de rôle, un robot ou même simplement un CGI qui réagit de manière complètement différente en fonction des paramètres qu'il reçoit. La manière naïve de programmer son comportement est d'utiliser une longue suite d'instructions if ... elsif ... else.

Voici un exemple de code ainsi conçu :

    # la routine action() est appelée avec le nom de la commande
    # à exécuter et la liste de ses paramètres
    sub action {
        my ($cmd, @args) = @_;

        if( $cmd eq 'ouvrir' ) {
            ...
        }
        elsif( $cmd eq 'quitter' ) {
            print "Au revoir!\n";
            exit;
        }
        else {
            # commande inconnue
            print "Commande <$cmd> inconnue !\n";
        }
    }

Ce genre de programme pose plusieurs problèmes :

Maintenance et lisibilité du code
Pour ajouter une action, il faut aller l'insérer quelque part dans la liste des elsif. S'il y a vraiment beaucoup de cas à traiter, la taille de la routine action() va augmenter considérablement, en réduisant la lisibilité du code.

Même en utilisant des routines externes, on arrive quand même à un résultat fort peu lisible et très redondant :
```
    if   ( $cmd eq 'ouvrir' )   { ouvrir(@args) }
    elsif( $cmd eq 'fermer' )   { fermer(@args) }
    elsif( $cmd eq 'regarder' ) { regarder(@args) }
    ...
```
Gestion des alias
Ajouter un alias peut se faire en remplaçant le test $cmd eq 'commande' par une alternative ($cmd eq 'commande1' || $cmd eq 'commande2') ou même une reconnaissance de motif ($cmd =~ /^commande[12]$/).

Mais comment être certain qu'une regexp ajoutée au début de la liste des tests ne va pas cacher un test un peu plus loin, rendant inaccessible une autre fonction ?
Performance
Enfin, le nombre de tests à faire augmente proportionnellement au nombre de commandes, ce qui peut finir par dégrader les performances s'il y a beaucoup de commandes. Certes, on peut toujours déplacer les fonctions les plus utilisées au début, à condition de ne pas rater son copier/coller...

Il est souvent souhaitable de ne pas manipuler directement le code des fonctions, mais de se contenter de ne manipuler que des fonctions. C'est ce que permet la notion de callback (fonction de rappel) : une routine prend des références à d'autres routines en paramètre et se charge de les appeler avec les bons arguments. Voici un exemple simple :

    # action_chaines() prend en paramètre une chaîne de caractères
    # et une liste de fonctions à appliquer dessus, dans l'ordre.
    # Chaque fonction renvoie une version modifiée de la chaîne reçue.
    sub actions_chaine {
        my ( $str, @func ) = @_;

        $str = $_->($str) for @func;
        return $str;
    }

    # les actions sont appliquées dans l'ordre
    print actions_chaine( "abcdef",
        sub { scalar reverse shift },       # inverse la chaîne
        sub { my $s = shift; chop $s; $s }, # supprime le dernier caractère
        sub { "x-$_[0]" },                  # préfixe par "x-"
    );

Ce qui donne :

   x-fedcb

Il devient alors excessivement simple d'ajouter une action à la file, de manipuler différentes files d'actions de traitement ou de les combiner.

Mais revenons plutôt à notre jeu de rôle (ou programme interactif) pour voir comment utiliser cette notion de fonctions de rappel. Si on crée un hachage ayant pour clés le nom des actions et pour valeur une référence à la fonction correspondante, le code de la fonction action() devient très simple :

    # le hachage peut pointer vers des fonctions définies ailleurs
    # ou des fonctions anonymes
    %actions = (
        ouvrir  => \&ouvrir,
        quitter => sub { print "Au revoir!\n"; exit },
        ...
    );

    # la fonction action() se contente
    # de faire appel à la routine correspondante
    sub action {
        my ( $cmd, @args ) = @_;
        if( exists $actions{$cmd} ) {
            $actions{$cmd}->( @args );
        } else {
            die "L'action <$cmd> n'existe pas !";
        }
    }

On appelle cette structure une table de distribution (dispatch table en anglais). Ajouter une action revient alors à ajouter une clé dans le hachage. Des programmes suffisamment compliqués peuvent même le faire dynamiquement (au cours de leur exécution ou à partir d'un fichier de configuration).

Si on regarde les trois problèmes posés au début, on voit que ce système apporte une solution à chacun d'entre eux :

Maintenance et lisibilité du code
Le code de chaque action peut maintenant être isolé dans une fonction ou même dans un module ; il suffit de savoir pointer dessus :
```
    $action{toto} = \&MonModule::toto;
```
Gestion des alias
L'ajout d'un alias est tout à fait limpide :
```
    $action{partir} = $action{quitter};
```
Performance
Trouver la valeur associée à une clé dans un hachage de 1000 clés est beaucoup plus rapide que faire 1000 tests de comparaison entre chaînes.

Dans le cadre d'un autre type de programme, on peut très bien imaginer ajouter des fonctionnalités à notre robot, en lui donnant directement le code Perl correspondant aux actions :

    sub cree_action {
        my ($nom, $code) = @_;

        # construit une routine anonyme
        my $sub = eval "sub { $code }";
        if( $@ ) {
            # la compilation a raté, revoyez votre copie
            print "Impossible de compiler le code: $@\n";
            return;
        }
        else {
            # ajoute l'action à la liste des actions possibles
            # (remplace l'action $nom si elle existe)
            $actions{$nom} = $sub;
            print "Action $nom ajoutée\n";
        }
    }

(Inutile de préciser que ce genre de code constitue à lui seul un énorme trou de sécurité, selon les utilisateurs qui ont accès à votre robot.)

Les tables de dispatch permettent de manipuler une abstraction qui représente l'ensemble des fonctionnalités de notre programme. C'est un mode de fonctionnement extrêmement souple et efficace.

Pour conclure, voici comment ajouter à votre programme la possibilité de gérer des commandes abrégées, quand il n'y a aucune ambiguïté :

    sub action {
        my ( $cmd, @args ) = @_;

        # trouve la liste des commandes commençant par $cmd
        my @possibles = grep { /^$cmd/ } keys %actions;

        if( @possibles == 0 ) {
            # y en a pas
            print "L'action <$cmd> n'existe pas !";
        }
        elsif( @possibles > 1) {
            # y en a plusieurs, impossible de choisir
            print "Action <$cmd> ambigue : @possibles\n";
        }
        else {
            # on a trouvé la seule action possible
            $actions{$possibles[0]}->( @args );
        }
    }

Il suffit d'essayer d'ajouter cette fonctionnalité à la première version de notre routine action() pour se convaincre de l'élégance de ce concept de table de distribution.

(Philippe "BooK" Bruhat, Paris.pm & Lyon.pm - book@mongueurs.net)

Perles de Mongueurs (6)

Tables de distribution (dispatch tables)

Les nouvelles de la communauté Perl

OSCON 2004

À vous !