Le langage Scheme
Huitième partie

Par :
Guilhem de Wailly (gdw@erian-concept.com)

et :
Fernand Boéri (boeri@unice.fr)

Résumé
Voici le huitième article d'une série destinée à présenter le langage Scheme.
Cet article termine la présentation général de Scheme. Dans les articles précédents, nous avons vu les principaux aspects du langage. Les éléments présentés sont conformes à la norme R4RS du MIT, et portables sur la plupart des environnements de programmation.
Pour clore cette présentation générale, nous avons présenté le mois dernier la programmation d'un simulateur de circuits électronique logique. Ce mois-ci, nous terminons la programmation du simulateur.
Introduction
Cet article termine la présentation du simulateur de circuit électronique numérique.
Nous indiquons aux lecteurs que les articles précédents sont disponibles sur le WEB. Ils sont regroupés et constituent le tutorial d'OpenScheme 1.3, à l'adresse :
http://www.erian-concept.com/osm/doc/tutorial.pdf
Dans l'article précédent, nous avons commencé la programmation en Scheme d'un simulateur de circuit électroniques logiques. 
Le programme que nous présentons ici est issu du livre Structure et Interprétation des programmes informatiques de Abelson et Susman, véritable bible de Scheme, dont les références sont données en annexe, et du projet PSOM de l'unité de recherche SPORTS du Laboratoire I3S de l'Université de Nice-Sophia Antipolis. Cependant, les programmes présentés ici sont originaux et conçus spécialement pour Linux Magazine et ses lecteurs.
Dans l'article précédent, nous avons décrit la logique, base de l'étude en profondeur des ordinateurs. Nous y avons vu que l'étude d'un schéma logique commence généralement par sa table de vérité, qui permet de définir pour chaque combinaison de valeurs en entrée, les valeurs en sortie correspondante.
Mais le schéma peut être décrit de manière plus concise par son équation logique. La logique utilise trois opérateurs de base que sont le ET, le OU et le NON logique. Le comportement de tout schéma logique peut être décrit avec une combinaison de ces opérateurs primitifs.
Une fois la table de vérité ou l'équation logique obtenue, il est possible de dessiner le schéma logique électronique correspondant, qui peut aboutir à la réalisation d'une carte électronique.  Signalons que les méthodes actuelles réalisent les systèmes numériques avec des outils des synthèse basés sur des langages de description du matériel, comme VHDL, par exemple.
Dans le précédent article, nous avons décrit les connexions en Scheme. Elles permettent de relier les entrées et les sorties des composants dans le simulateur. Une connexion est un vecteur Scheme à trois positions : la première contient un symbole permettant de reconnaître l'objet, le second est la valeur initiale dans la connexion et le troisième est une liste de procédures à invoquer lorsque la valeur de la connexion est modifiée.
Nous avons défini les fonctions suivantes :
·	(connexion:créer [init]) : crée une nouvelle connexion. Le paramètre init est optionel et il est la valeur initiale de la connexion. Par défaut, la valeur initiale est nulle. Nous rappelons que la syntaxe utilisé ici permet de représenter comment utiliser la fonction. Les crochets indiquent que l'argument est facultatif.
·	(connexion:lire connexion) : retourne la valeur de la connexion.
·	(connexion:brancher! connexion action) : ajoute une procédure à la liste de procédures à invoquer lorsque la valeur de la connexion change.
·	(connexion:changer! connexion valeur) : modifie la valeur de la connexion.
Nous allons maintenant nous attacher à l'agenda, véritable centre névralgique du simulateur.
Simulateur : 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.

Fig 6 : 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 :
> (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 cet article, 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 :
> (define agenda (agenda:créer))
=> #unspecified
> agenda
=> #(agenda () ())
Pour l'instant, l'agenda est vide de toute action. Ajoutons une action :
> (agenda:ajouter! agenda 1 'p1)
=> #unspécified
> 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 :
> (agenda:ajouter! agenda 1 'p2)
=> #unspécified
> 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 :
> (agenda:ajouter! agenda 3 'p3)
=> #unspécified
> 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.
Simulateur : Portes primitives
Les portes primitives on la particularité d'utiliser du code en Scheme pour établir la relation entre les entrées et les sorties. A l'inverse, les portes assemblée sont construites en fabriquant un module reliant de manière interne des portes et des connexions.
La porte la plus simple que nous puissions définir réalise la fonction NON : si son entrée vaut 1, elle place sur sa sortie la valeur 0, et vice et versa.
Le constructeur de l'inverseur peut être définit par :
(define (porte:not agenda entrée sortie)
 ; procédure interne de calcul
(define (action:not)
 (let ([valeur (connexion:lire entrée)])
   (agenda:retarder agenda
                    1
                    (lambda ()
                      (connexion:changer! 
                       sortie
                       (if (zero? valeur)
                           1
                           0))))))
(connexion:brancher! entrée action:not))
C'est une procédure dont les paramètres sont un agenda, une connexion en entrée et une connexion en sortie.
On définit alors une fonction de calcul interne : Cette procédure lit la valeur sur la connexion en entrée, et place avec un retard unitaire, la valeur inverse sur la sortie, à l'aide d'une procédure lambda. Le constructeur associe alors cette fonction de calcul interne à la connexion en entrée.
Toute la dynamique du calcul sera activée par les connexions en entrée et en sortie, qui vont activer la procédure interne de calcul, ce qui a pour effet de modifier la valeur de la connexion en sortie.
La seconde porte primitive que nous définissons et la porte ET à deux entrées et une sortie :
(define (porte:and agenda entrée-1
                         entrée-2
                         sortie)
(define (action:and)
 (let ([v-1 (connexion:lire entrée-1)]
       [v-2 (connexion:lire entrée-2)])
   (agenda:retarder agenda
                    2
                    (lambda ()
                     (connexion:changer! 
                      sortie
                      (if (or (zero? v-1)
                              (zero? v-2))
                          0
                          1))))))
(connexion:brancher! entrée-1 action:and)
(connexion:brancher! entrée-2 action:and))
Ce constructeur à la même structure que le constructeur du NON mis à part le fait qu'il doive prendre en compte les deux entrées. 
La porte est identique à la porte ET mis à part que le test est :
(define (porte:or agenda entrée-1
                        entrée-2
                        sortie)
(define (action:or)
 (let ...
                      (if (and (zero? v-1)
                               (zero? v-2))
                          0
                          1))))))
 ...
(connexion:brancher! entrée-1 action:or)
(connexion:brancher! entrée-2 action:or))
La dernière porte primitive définie est la sonde. Branchée à une connexion, elle permet d'afficher les différentes valeurs circulant sur cette connexion :
(define (porte:sonde agenda nom connexion)
(define (action:sonde)
 (display (agenda:aujourd-hui agenda))
 (display #\space)
 (display nom)
 (display ": ")
 (display (connexion:lire connexion))
 (newline))
(connexion:brancher! connexion
                     action:sonde))
Le constructeur a comme paramètres un agenda, un nom qui servira à identifier la sonde et une connexion. De la même manière que pour les autres portes primitives, on associe une procédure à la connexion donnée en argument.
Simulateur : portes assemblée
Dans cette section, nous montrons comment assembler des portes pour en définir une autre, plus complexe. Nous reprenons l'exemple de la porte XOR présentée dans l'article précédent. Rappelons que le schéma logique de la porte XOR est :

Fig 4 : Construction d'une porte XOR.
Nous définissons le constructeur de cette porte par :
(define (porte:xor agenda
                  entrée-1
                  entrée-2
                  sortie)
 (let ([c-A (connexion:créer)]
       [c-B (connexion:créer)]
       [c-C (connexion:créer)]
       [c-D (connexion:créer)])
   (porte:not agenda entrée-1 c-A)
   (porte:not agenda entrée-2 c-B)
   (porte:and agenda c-A entrée-2 c-C)
   (porte:and agenda c-B entrée-1 c-D)
   (porte:or  agenda c-C c-D sortie)))
Cette fois-ci, il n'existe pas de procédure de calcul. A la place, nous avons des connexions internes que nous relions à des portes internes, sans savoir d'ailleurs, si elles sont primitives ou pas. 
La porte XOR réalisée prend en compte les retards introduits par les portes qui la composent. Si nous constations que la porte introduit des retards trop importants, il faudrait la réaliser comme une porte primitive, avec une fonction de calcul.
Nous avons maintenant une méthode universelle pour construire des portes aussi complexes que nous le souhaitons.
Conclusion
La principale limitation de ce simulateur est de ne pas permettre de prendre en compte les portes logiques sensibles aux fronts. Cette prise en compte ne nécessite pas de grosses modifications.
Il serait possible d'adjoindre une interface graphique à ce moteur. Cela pourrait être fait à l'aide d'OpenScheme et de sa toute nouvelle librairie graphique orientée objet.
Le projet présenté montre l'intérêt d'une simulation logicielles d'un système matériel. Un projet plus ambitieux, développé eu Laboratoire I3S, à Sophia-Antipolis, dans l'opération SPORTS, permet de concevoir, de modéliser, de simuler et d'évaluer les performances de systèmes matériels constitués de processeurs de traitement numérique du signal (DSP), de processeur RISC, ou de leur association. Ce projet repose sur une modélisation orientée objet.
Le simulateur présenté ici peut servir dans d'autres domaines que la logique électronique : il peut en fait être utilisé pour modéliser tous les flux, quelle qu'en soit la nature.
En fait, le simulateur ne se préoccupe pas des données transportées sur les connexions et il en ignore totalement la nature. Seules les portes primitives sont attachées aux objets transportés. Dans notre exemple, les données sont des 0 et de 1.
Cette méthode de conception est connue en informatique sous le nom de graphe ou langage dataflow, c'est à dire à `` flots de données ''. L'un des langages dataflow le plus connu est Lucid qui fut l'un des premiers. Certains connaissent aussi l'environnement Ptolemey développé par EA. Lee et DG. Messerschmitt. Nous renvoyons les lecteurs à la bibliographie donnée en annexe.
Les auteurs

Guilhem de Wailly, directeur de la société Erian Concept : support, formations, configurations, administration, développements Linux.
http://www.erian-concept.com

Fernand Boéri, Professeur à l'Université de Nice - Sophia-Antipolis, membre de l'unité SPORTS du laboratoire I3S, spécialiste en modélisation, évaluation de performances et architectures parallèles.
http://www.i3s.unice.fr
Références
Logique
¨	Architecture de l'ordinateur 
Andrew Tanenbaum
Inter Edition
Dataflow
¨	Synchronous dataflow 
EA Lee et DG Messerschmitt
Proceding of the IEEE, 75(9) :1235-1245, Septembre 1987
¨	Lucid, the dataflow Programming Language 
EWW Wadge et EA Ashcroft
Academic Press,1985
Scheme
¨	Structure et Interprétation des programmes informatiques
H. Abelson, GJ. Sussman
InterEdition
¨	The Scheme Programming Languages - Ansi Scheme 
R. Kent Dybvig
Prentice Hall
¨	Les langages Lisps -  Christian Queinnec
InterEdition
¨	Programmer avec Scheme - J. Chazarin
Thomson Publishing
¨	Revised4 Report on the Algorithmic Language Scheme
W. Clinger, J. Rees
ftp://ftp.nj.nec.com/pub/kelsey
Environnements Scheme
¨	Scm - A. Jaffer
http://www-swiss.ai.mit.edu/~jaffer/SCM.html
La référence des interprètes Scheme. Très petit, rapide, pour beaucoup de plates-formes, extensible.
¨	PCScheme - Texas Instrument
ftp://cui.unige.ch/public/pcs/pcscheme.exe
Un très bon environnement de programmation Scheme pour DOS, avec éditeur intégré.
¨	OpenScheme - Erian Concept
http://www.erian-concept/osm
Environnement professionnel de programmation Scheme comprenant un interprète, un compilateur et un débogueur symbolique. 
Existe en version libre et commerciale, pour Windows et Linux.