Le langage Scheme - 8e partie

Voici le huitième article d'une série destinée à présenter le langage Scheme.

Cet article termine la présentation générale 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 électroniques logiques. Ce mois-ci, nous terminons la programmation du simulateur.

Introduction

Cet article termine la présentation du simulateur de circuits électroniques numériques.

Nous indiquons aux lecteurs que les articles précédents sont disponibles sur le Web. Ils sont regroupés et constituent le didactitiel 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 circuits é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 correspondantes.

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 de 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ée 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.

L'agenda : c'est une liste de liste

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

> (list '(1 p₁) '(2 p₂) '(3 p₃ p₄) '(4 p₅))

=> ((1 p₁) (2 p₂) (3 p₃ p₄) (4 p₅))

où les p_i sont des procédures Scheme. Ces procédures sont invoquées lorsque le temps est 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 suivants 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 la 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 'p₂)

=> #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 prend 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 queue de cette liste à la liste des actions de l'agenda. 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 travail 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éfinir les portes primitives, puis nous pourrons les assembler à l'infini.

Simulateur : Portes primitives

Les portes primitives ont 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ées 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 versa.

Le constructeur de l'inverseur peut être défini 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 est 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 a 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 sauf 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ées

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 :

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 logicielle d'un système matériel. Un projet plus ambitieux, développé au Laboratoire I3S, à Sophia-Antipolis, dans le cadre de 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 processeurs 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 des 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 ». Un des langages dataflow le plus connu est Lucid qui fut l'un des premiers. Certains connaissent aussi l'environnement Ptolemey développé par E.A. Lee et D.G. Messerschmitt. Nous renvoyons les lecteurs à la bibliographie donnée en annexe.