L'agenda

L'agenda est une liste dont les éléments sont ordonnés par le temps. Il s'agit ici d'un temps logique, incrémenté à chaque étape de la simulation, comme le montre la figure 11.1.

Figure 11.1: Agenda : c'est une liste de listes.

L'agenda contient une liste de procédures pi ordonnées par les dates : en Scheme, c'est une liste de liste comme :

Osm> (list '(1 p1) '(2 p2) '(3 p3 p4) '(4 p5))
  => ((1 p1) (2 p2) (3 p3 p4) (4 p5))

où les pi sont des procédures Scheme. Ces procédures sont invoquées lorsque le temps sera venu d'exécuter toutes les actions du temps présent. Le temps présent est la date du premier élément de la liste, dans l'exemple, 1.

Au cours de la simulation, certaines portes vont programmer une action sur leur connexion de sortie avec au minimum un retard unitaire. D'autres portes, plus complexes, ne pourront mettre à jour leur sortie qu'avec des retards plus importants.

La fonction de création de l'agenda est très simple :

; création d'un agenda
(define (agenda:créer)
  (vector 'agenda '() '()))

Le premier champ du vecteur Scheme est occupé par le symbole agenda, ce qui permet d'identifier ce vecteur comme un agenda, à des fins de contrôle.

Le second champ de ce vecteur est une liste vide qui recevra les actions sensibles à un front montant ou descendant. Dans cette présentation, nous ne nous en occuperons pas.

Le troisième champ est la liste des actions enregistrées. Initialement, cette liste est vide. Elle sera alimentée au cours de la simulation. La liste des actions est composée par des listes dont le premier élément est la date et dont les éléments suivant sont des procédures à invoquer le moment voulu.

La première fonction liée à l'agenda permet d'ajouter une action programmée à une date future. La difficulté de cette fonction est qu'elle doit insérer l'action en maintenant l'ordre des actions dans le temps. Nous avons :

(define (agenda:ajouter! agenda date action)
 (let loop ([actions (vector-ref agenda 2)]
            [précédent #f])
   (if (null? actions)
    ; agenda vide ou date postérieure
    (let ([dernier (cons (list date action)
                         '())])
      (if précédent
       ; ajout à la fin
       (set-cdr! précédent dernier)
       ; création du premier élément
       (vector-set! agenda 2 dernier)))
    (cond [(> date (car (car actions)))
           ; ajouter après
           (loop (cdr actions) actions)]
          [(= date (car (car actions)))
            ; ajouter ici
           (set-cdr!
            (car actions)
            (cons action
                  (cdr (car actions))))]
          [else
           ; ajouter avant
           (let ([nouveau (cons (list date
                                     action)
                                 actions)])
           (if précédent
            ; insertion
            (set-cdr! précédent nouveau)
            ; création
            (vector-set! agenda
                         2 nouveau)))]))))

La fonction est basée sur l'itération loop dont les variables sont la liste des actions contenant chacune une date et des procédures, et liste des actions précédentes.

Le premier cas se produit lorsque la liste de cellules est vide. Ce peut être parce que l'agenda est vide ou parce que la date à ajouter est postérieure à toutes les actions déjà enregistrées. Dans ce cas, s'il existe une cellule précédente, la nouvelle cellule est ajoutée à sa suite, sinon, la cellule devient la première action de l'agenda.

Si l'action doit être insérée avant les autres actions, elle est placée en premier, devenant ainsi le premier élément de la liste des actions, soit avant une action précédente, auquel cas le lien de cette dernière doit être mis à jour.

Essayons :

Osm> (define agenda (agenda:créer))
  => #unspecified

Osm> agenda
  => #(agenda () ())

Pour l'instant, l'agenda est vide de toute action. Ajoutons une action :

Osm> (agenda:ajouter! agenda 1 'p1)
  => #unspécified

Osm> agenda
  => #(agenda () ((1 p1)))

Cette fois-ci, nous constatons que le couple date-action (1 p1) a été ajouté. Remarquons que nous avons utilisé le symbole p1 pour l'action, au lieu d'une fonction, ceci pour raccourcir l'exemple ; plus bas, nous utiliserons de vraies procédures. Ajoutons maintenant une autre procédure, à la même date :

Osm> (agenda:ajouter! agenda 1 'p2)
  => #unspécified

Osm> agenda
  => #(agenda () ((1 p2 p1)))

Dans ce cas, la procédure p2 a été ajoutée à la liste des procédures à exécuter en date 1. Ajoutons maintenant une procédure p3 à une date postérieure :

Osm> (agenda:ajouter! agenda 3 'p3)
  => #unspécified

Osm> agenda
  => #(agenda () ((1 p2 p1)(3 p3)))

La liste est donc maintenue toujours triée par ordre de date. Les fonctions suivantes sont beaucoup plus simples. La première d'entre elles donne simplement la date du jour :

(define (agenda:aujourd-hui agenda)
  (if (null? (vector-ref agenda 2))
      1
      (car (car (vector-ref agenda 2)))))

Si l'agenda est vide, la date du jour est la date initiale 1, sinon, elle est la valeur de la date de la première cellule.

La seconde fonction utilitaire permet de savoir si la fin du monde est atteinte :

(define (agenda:fin-du-monde? agenda)
  (if (vector-ref agenda 2) #f #t))

Le simulateur est alimenté en actions par les connexions. Lorsque le système atteint un état stable et que plus aucun changement n'est enregistré, la simulation s'arrête.

La fonction suivante permet d'ajouter une procédure à exécuter avec un certain retard par rapport à la date courante dans l'agenda :

(define (agenda:retarder agenda
                         retard
                         action)
  (agenda:ajouter! agenda 
                   (+ (agenda:aujourd-hui
                       agenda)
                      retard)
                   action))

Cette fonction est une simple réécriture de la fonction agenda:ajouter!.

La fonction qui suit permet d'exécuter toutes les actions de la date courante. Si au moins une action a été exécutée, elle retourne #t, sinon elle retourne #f :

(define (agenda:aujourd-hui-tout-faire
         agenda)
  (for-each (lambda (action)
              (action))
            (cdr (car (vector-ref agenda
                                  2)))))

Cette fonction utilise simplement la forme for-each sur la liste des procédures de la première liste d'actions. Notons que nous évitons de tester si l'agenda est vide ou pas, car le test sera fait avant d'appeler cette fonction.

Enfin, cette dernière fonction utilitaire permet de changer de date courante pour passer à la date suivante :

(define (agenda:demain! agenda)
  (vector-set! agenda
               2
               (cdr (vector-ref agenda 2))))

Cela est fait simplement en affectant à la liste des actions de l'agenda, la queue de cette liste. Le mécanisme de gestion de la mémoire de Scheme se chargera de récupérer en temps voulu la mémoire utilisée, sans que nous ayons explicitement à le faire.

La dernière fonction présentée est le cœur du simulateur. Il s'écrit simplement avec :

(define (agenda:simuler agenda)
 (if (not (agenda:fin-du-monde? agenda))
  (begin
   (agenda:aujourd-hui-tout-faire agenda)
   (agenda:demain! agenda)
   (agenda:simuler agenda))))

Il s'agit là d'une superbe fonction à récursion terminale. Son premier travaille consiste à savoir si la fin de la simulation est atteinte. Si ce n'est pas le cas, on exécute toutes les actions de la date courante, puis on change de jour, et on recommence.

Le simulateur est terminé. Il ne nous reste plus qu'à définire les portes primitives, puis nous pourrons les assembler à l'infini.