Voici le septième article d'une série destinée à présenter le langage Scheme.
Dans les articles précédents, nous avons vu les principaux aspects du langage. Nous allons utiliser ce mois-ci nos connaissances pour programmer un simulateur de circuits logiques. Nous commençons par définir les éléments de base de la logique, science des microprocesseurs. Puis nous commencerons la définition des fonctions Scheme permettant de réaliser le simulateur.
Introduction
Notre introduction au langage Scheme est maintenant terminée. Les lecteurs connaissent pratiquement tous les aspects du langage, dans sa norme R4RS. Les éléments présentés dans cette série d'articles sont portables sur toutes les implémentations conformes à cette norme.
Nous indiquons aux lecteurs que les articles précédents sont disponibles sur le WEB. Ils sont regroupés pour former le brouillon du tutorial d'OpenScheme 1.3, à l'adresse :
http://www.erian-concept.com/osm/doc/tutorial.pdf
La norme R5RS est parue il y a peu. Cette nouvelle définition du langage spécifie quelques fonctionnalités supplémentaires, dont un langage de macro extrêmement puissant, qui permet d'ajouter de nouvelles formes spéciales à Scheme, comme la forme while, repeat, etc. Avec ce langage de définition de macro, Scheme devient définitivement l'un des langages le plus puissant dans ses possibilités d'extension.
Nous préparons environnement Scheme qui sera distribué prochainement sur le CD ROM de Linux Magazine et sur le WEB afin de permettre d'utiliser ces macro. La description des macro fera l'objet d'un prochain article.
Pour le moment, nous allons utiliser nos connaissances pour fabriquer un programme en Scheme de simulation de circuits logiques. Conforme à la norme R4RS, ce programme de simulation sera utilisable sur tous les environnements Scheme.
Bien que le projet soit ambitieux, la réalisation aura moins de 200 lignes de code !
Un schéma logique comporte des portes logiques élémentaires, comme les portes AND (et), OR (ou), NOT (non) ou NAND (non-et). Il est possible d'assembler ces portes afin de construire des éléments plus complexes.
Notre programme de simulation ne sera graphique. La description du schéma et l'affichage des résultats à l'aide des sondes seront effectués en mode texte. La modularité de la conception permettrait d'ajouter assez facilement une interface graphique à ce moteur élémentaire.
De plus, nous ne nous préoccuperons pas ici des portes sensibles aux fronts d'horloges.
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.
Mais avant de commencer la programmation, un peu de logique !
Logique numérique
Introduction
La logique numérique est à la base de l'informatique, notamment matérielle. C'est elle qui permet de décrire un schéma électronique logique et d'étudier son comportement. La logique est liée à l'algèbre de Boole (d'où le nom booléen) qui permet de définir un schéma logique à l'aide d'équations.
L'algèbre de Boole comporte trois opérateurs, le ET, le OU et le NON. L'écriture des équations reprend les symboles de l'arithmétique pour le ET (multiplication) et pour le OU (addition) et ajoute un symbole pour le NON (barre horizontale au-dessus de l'expression à inverser). L'algèbre de Boole définit aussi des règles de simplification ou réarrangements des expressions, qui permettent de réduire le nombre de portes (et donc de transistors).
Il serait possible de concevoir un programme en Scheme de simplification automatique des équations. En effet, Scheme est particulièrement à l'aise pour manipuler des expressions symboliques.
Lorsque que l'on possède une équation logique, il est possible de fabriquer le circuit électronique correspondant assez simplement. Sur les schémas complexes, des problèmes de dissipation de chaleur, de temporisation, de parasites interviennent, rendant la réalisation moins immédiate qu'avec des schémas simples.
Tout commence avec le transistor qui est un composant électronique qui agit comme un interrupteur piloté par une entrée de commande. En assemblant des transistors, on construit des composants plus gros remplissant une fonction logique. Les composants de base sont les portes logiques comme le AND. Puis en assemblant des portes logiques, on définit des foncions de plus en plus complexes, comme un additionneur à un bit, puis un additionneur à n-bits, etc. Les microprocesseurs sont décrits à l'aide de fonctions logiques.
L'une des particularités de la logique est de permettre une grande réutilisation des composants afin de construire des composants plus complexes et de toujours permettre la définition de la fonction réalisée sous la forme d'une équation.
Portes logiques élémentaires
A l'aide des transistors, il est possible de concevoir des éléments plus complexes que sont les portes logiques. Une porte logique réalise une fonction logique particulière.
Schéma du ET
Voici par exemple la représentation d'une porte AND :
Fig 1 : Représentation d'une porte AND.
Table de vérité
Le comportement de cette porte est entièrement spécifié par sa table de vérité, qui met en relation toutes les valeurs possibles des entrées et la valeur de sortie résultante. Rappelons que les valeurs sont binaires, c'est à dire qu'elles valent 0 ou 1. La table de vérité de la porte AND est :
| a | b | s |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Tab 1 : Table de vérité d'une porte AND.
Cette table de vérité montre les correspondances entre les valeurs binaires en entrée et les valeurs binaires en sortie. Ainsi, la valeur en sortie est 1 lorsque les deux entrées sont à 1 et seulement dans ce cas.
Algèbre de Boole
On peut aussi définir le comportement d'une porte à l'aide d'une équation logique. Une équation logique utilise trois opérateurs, le ET, le OU et le NON. Le ET est noté comme la multiplication, le OU est noté comme l'addition et le NON est noté avec une barre au-dessus de l'expression à inverser :
| Expression | Equation |
| a ET b | a.b |
| a OU b | a+b |
| NON a |
|
Tab 2 : Opérateur de l'algèbre de Boole.
Pour manipuler les équations logiques, l'algèbre de Boole définit des règles de simplification. Leur description sort du cadre de cet article sur le langage Scheme ! Le lecteur le souhaitant pourra se référer au livre Architecture de l'Ordinateur de A. Tanenbaum, qui est la bible des architectures matérielles, et dont l'exposé part du transistor pour aboutir aux machines parallèles.
La simplification ou le réarrangement d'une expression logique a toujours pour but l'optimisation du schéma logique et donc de la carte électronique ou du circuit correspondant.
Dans notre cas, l'équation de la porte AND est très simple, puisque l'opérateur ET existe dans l'algèbre :
s = a . b
Le NON
Les autres portes logiques standards sont les portes NOT (inverseur), OR (ou), NAND (non-et), NOR (non-ou).Voici leur représentation et leur table de vérité :
Fig 2 : Représentation d'une porte NOT.
a s
| a | s |
| 0 | 1 |
| 1 | 0 |
Tab 3 : Table de vérité d'une porte NOT.
L'équation logique de la porte NOT est aussi très simple, car l'opérateur NON existe dans l'algèbre :
s=a
Le OU
La porte OR est donc un inverseur : sa sortie est toujours l'inverse de son entrée.
Fig 3 : Représentation d'une porte OR.
| a | b | s |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Tab 4 : Table de vérité d'une porte OR.
La porte OR est un ou logique entre les valeurs en entrée. Son équation est :
s = a + b
Le NON-ET et le NON-OU
Le lecteur pourra lui-même déterminer les tables de vérité des antres portes NAND et NOR, en sachant qu'il suffit de placer un inverseur à la sortie des portes, respectivement, AND et OR pour obtenir la valeur de leur sortie. L'équation logique du NAND est :
s = a.b
Création d'une fonction logique
Nous allons utiliser les portes élémentaires pour fabriquer une porte plus complexe. Nous partons de la table de vérité de la fonction logique à réaliser, puis nous obtenons son équation et enfin son schéma logique.
Table de vérité
Il existe une fonction logique appelée ou-exclusif et notée XOR dont voici la table de vérité :
| a | b | s |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Tab 5 : Table de vérité d'une porte XOR.
Cette table de vérité est le point de départ de la définition de la porte. Elle spécifie entièrement le comportement et permet de déduire son équation logique. Avec l'équation, il est possible d'étudier la porte, de la simplifier, de transformer la manière de la construire en vérifiant que le comportement reste inchangé.
Equation logique
Pour obtenir l'équation logique d'une porte XOR, nous regardons dans la table les lignes où la sortie vaut 1 : ce sont les deux lignes du milieu. Nous écrivons alors l'équation de la sortie directement en fonction des entrées :
s=
a . b + a.b
Nous avons donc : s vaut 1 lorsque l'inverse de a vaut 1 ET b vaut 1, OU a vaut 1 ET l'inverse de b vaut 1.
Lorsque ces conditions ne sont pas rencontrées, s vaut 0.
Dire que l'inverse de a vaut 1 revient à dire que a vaut 0. Cela nous conduit à une nouvelle formulation : s vaut 1 lorsque a vaut 0 ET b vaut 1, OU a vaut 1 ET b vaut 0.
L'équation est donc la simple traduction de ce que l'on lit sur la table. L'algèbre de Boole nous permettrait de la simplifier, le cas échéant.
Réalisation
Pour réaliser le schéma électrique correspondant à la fonction XOR, nous lisons simplement son équation :
Fig 4 : Construction d'une porte XOR.
Nous voyons que la construction de nouvelles fonctions logiques n'est pas très compliquée. La simplification est parfois plus ardue.
Cahier des charges
Maintenant que nous avons décrit brièvement le sujet, quel est le cahier des charges ?
Il nous faut construire un programme en Scheme qui permette de :
- Définir des portes élémentaires. Ces portes sont décrites par leur comportement, que l'on programmera à la main. Il n'y pas de limite quant à la fonctionnalité de ces portes primitives : il sera possible de décrire une porte logique élémentaire, comme un microprocesseur.
- Construire de nouvelles portes à l'aide de portes plus élémentaires. Cela permet la réutilisation des composants déjà définis. Ces composants sont construits de manière modulaire.
- Réaliser une architecture, en connectant des portes élémentaires et des connexions. La réalisation de l'architecture sera effectuée par des appels de fonctions. L'élément clef est la connexion qui relie une sortie à une ou plusieurs entrées. Une connexion pourra transporter une valeur binaire ou se comporter comme un bus.
- Placer des sondes pour afficher les différentes valeurs des signaux. Les sondes affichent les différentes valeurs qui circulent sur une connexion.
- Simuler l'architecture. La simulation se termine automatiquement lorsque plus aucune valeur n'est modifiée dans le schéma et qu'il atteint un état stable.
De manière à rester simple, le programme ne sera pas graphique, mais purement textuel. Une interface graphique pourrait être construite au-dessus de notre premier modèle.
Exemple d'utilisation
Nous commençons maintenant la réalisation du simulateur. Le simulateur comprend plusieurs parties, dont la définition de l'agenda, les connexions, les portes élémentaires et le moteur de simulation.
L'agenda est une structure qui enregistre les évènements qui restent à exécuter. Il sera décrit dans le prochain article. Les évènements sont des couples formés par une date et une procédure. L'agenda est une liste d'événements ordonnée par les dates.
Les connexions sont des structures de données qui relient les portes entre elles, et qui ont la capacité de propager des valeurs. Les connexions sont responsables de la propagation des valeurs entre les portes.
Les portes élémentaires sont décrites à l'aide de leur comportement programmé en Scheme, par opposition aux portes composées dont seule la structure est décrite.
Lorsque l'outil sera terminé, nous pourrons écrire :
(define agenda (agenda:créer))
Cette instruction crée l'agenda, qui permet de stocker les évènements restants.
La prochaine étape consiste en la création des connexions qui correspondent aux fils du schéma électrique :
(define a (connexion:créer))
(define b (connexion:créer))
(define s (connexion:créer))
Pour le moment, les connexions ne sont pas reliées à des portes. Les portes sont créées en les reliant à des connexions :
(porte:and agenda a b s)
Cette instruction crée une poste ET dont les deux entrées sont reliées aux connexions a et b, et dont la sortie est reliée à la connexion s.
(porte:sonde agenda "s" s)
Cette instruction relie la sortie s à une sonde qui va permettre de visualiser les valeurs circulant sur la connexion.
Le schéma obtenu par cette série d'instruction est :
Fig 5 : Schéma simple : porte ET et Sonde.
Pour simuler de schéma, nous allons placer explicitement des valeurs sur les entrées et nous allons examiner à l'aide de la sonde l'effet sur la sortie :
(connexion:changer! a 1)
(agenda:simuler agenda)
La fonction agenda: simuler lance le simulateur. Dans ce cas, la modification effectuée sur l'entrée a n'a généré aucun événement sur la sortie, et la sonde n'a détecté aucune modification sur la sortie s. Modifions maintenant l'entrée b :
(connexion:changer! b 1)
(agenda:simuler agenda)
Cette fois-ci, la modification de l'entrée b entraîne la modification de la sortie s, que la sonde détecte en affichant :
SONDE(0) s : 1
La sonde affiche l'instant entre parenthèses, ici 0.
Avec ce simulateur, il est possible de réaliser un système instable, c'est à dire qui provoque une infinité de changements sur les sorties.
Un moyen simple de réaliser un système instable est de connecter la sortie d'un inverseur à son entrée. De cette manière, quelle que soit la valeur initiale de la sortie, elle est toujours inversée, ce qui conduit le système à osciller. Le schéma du système instable est le suivant :
Fig 6 : Système instable.
La programmation de ce schéma est :
; création des connexions
(define a (connexion:créer))
; création de l'agenda
(define agenda (agenda:créer))
; connexion des portes
(porte:not agenda a a)
; sonde
(porte:sonde agenda "a" a)
; simulation
(connexion:changer! a 1)
(agenda:simuler agenda)
; la valeur de sortie de s change
SONDE(0) s : 0
SONDE(1) s : 1
SONDE(2) s : 2
SONDE(3) s : 3
...
La sonde détecte une infinité de changements sur la sortie, et la simulation ne s'arrête jamais. Ce système instable peut servir à générer des horloges pour des systèmes plus complexes.
Simulateur : les connexions
Dans cet article, nous ne décrirons que les connexions. Il nous restera à décrire l'agenda, le moteur du simulateur, et les portes primitives.
Une connexion est un vecteur Scheme à trois éléments :
- Un symbole permettant d'identifier ce vecteur comme étant une connexion. C'est une manière simplifiée de contrôler le type des arguments.
- La valeur courante de la connexion. Par défaut, cette valeur est initialisée à zéro, mais elle peut être initialisée à une autre valeur. Les valeurs circulant sur les connexions sont à priori binaires, c'est à dire qu'elles valent 0 ou 1. Mais rien n'empêche de placer sur les connexions d'autres types de valeurs, ce qui transformerait notre simulateur en environnement DataFlow.
- Une liste d'actions à exécuter lorsque la valeur de la connexion est modifiée. Ces actions sont des procédures Scheme sans arguments. La propriété de Scheme de définir des procédures attachées à un environnement est utilisée très naturellement ici. Cette caractéristique, très simple d'utilisation, donne toute sa puissance au langage.
La fonction Scheme créant une connexion est ;
; création d'une connexion
(define (connexion:créer . init)
(vector 'connexion
(if (null? init) 0 (car init))
'()))
On remarque que la fonction est à nombre d'arguments variable : Elle peut être appliquée à zéro, un ou plus arguments. Le paramètre init contient la liste des arguments supplémentaires, ou la liste vide, le cas échéant. Dans notre cas, seul le premier argument sera utilisé pour modifier, le cas échéant, la valeur initiale de la connexion.
Le premier élément du vecteur est le symbole connexion qui nous permettra d'effectuer des tests sur la validité de l'objet. De plus, à l'affichage d'un objet connexion, le nom connexion permettra de le différencier des autres objets.
Le second élément du vecteur est la valeur initiale de la connexion, initialisé à zéro ou par l'argument optionnel.
Le troisième élément du vecteur est la liste des actions attachées à la connexion, initialement vide.
Nous allons maintenant définir les fonctions permettant de manipuler une connexion. La première d'entre elles est la fonction de lecture de la valeur courante de la connexion :
; lecture de la valeur courante
(define (connexion:lire connexion)
(vector-ref connexion 1))
La valeur d'une connexion est simplement la deuxième valeur du vecteur.
On remarque qu'aucun test n'est effectué quant à la nature de l'objet passé en argument. Il serait possible de vérifier qu'il s'agit bien d'un vecteur et que son premier élément est le symbole connexion.
La fonction suivante permet d'ajouter une action à la liste des actions enregistrées dans la connexion :
; ajout d'une action
(define (connexion:brancher! connexion
action)
(vector-set! connexion
2
(cons action
(vector-ref connexion
2))))
Enfin, la dernière fonction permet de modifier la valeur courante. Si la nouvelle valeur est différente de la valeur courante, toutes les actions sont activées. Sinon, rien ne ce passe :
; modifier la valeur courante
(define (connexion:changer! connexion
valeur)
(if (not (eq? (vector-ref connexion 1)
valeur))
(begin
(vector-set! connexion 1 valeur)
(for-each (lambda (action)
(action))
(vector-ref connexion 2)))))
La fonction ne présente pas de difficultés. Si la nouvelle valeur est différente de la valeur courante de la connexion, la valeur de la connexion est modifiée et toutes les procédures de la liste des actions sont activées, sans arguments.
Nous verrons dans le prochain article que les actions sont responsables de la propagation des valeurs le long des connexions en activant des fonctions de calcul attachées aux portes.