Micro Systèmes n°48 décembre 1984
Micro Systèmes n°48 décembre 1984
  • Prix facial : 24 F

  • Parution : n°48 de décembre 1984

  • Périodicité : mensuel

  • Editeur : Société Parisienne d'Edition

  • Format : (203 x 271) mm

  • Nombre de pages : 246

  • Taille du fichier PDF : 187 Mo

  • Dans ce numéro : MSX... un nouveau standard ?

  • Prix de vente (PDF) : gratuit

Dans ce numéro...
< Pages précédentes
Pages : 152 - 153  |  Aller à la page   OK
Pages suivantes >
152 153
LA STRUCTURE D'ENSEMBLE EN QUELQUES FONCTIONS LISP Lisp est un langage idéal pour tester des idées de programmation. En particulier, il est très facile de se créer des structures de données sophistiquées. L'une de ces structures est bien connue en mathématiques puisqu'il s'agit de la notion d'ensemble. De portée très générale, un grand nombre de problèmes peuvent être résolus à l'aide de ces structures de données. Manipuler des ensembles ne présente aucune difficulté en Lisp, ce qui n'est pas le cas de la plupart des langages de programmation : leurs structures de données statiques (tableaux, record) s'accommodent mal du dynamisme nécessaire à l'implémentation des ensembles. Qu'est-ce qu'un ensemble ? Sans entrer dans les définitions mathématiques, un ensemble est donné comme une collection d'éléments, c'est-àdire une suite non ordonnée de « choses » uniques. Par exemple, b c d el est un ensemble alors que la b a c d} ne l'est pas, l'élément « a » étant répété. Les ensembles peuvent être combinés entre eux pour former d'autres ensembles, tester l'inclusion de l'un dans l'autre, ou vérifier l'appartenance d'un élément à un ensemble. Toutes ces opérations sont aisément définissables en Lisp, et les fonctions qui les implémentent sont présentées fi gure A. Chaque ensemble est considéré comme une liste d'atomes ou de listes, sans duplication d'éléments. Evidemment, ces ensembles doivent être donnés en extension, c'est-à-dire en énumérant explicitement la suite de leurs éléments. Seules quelques fonctions suffisent à manipuler des ensembles : UNIQUE, EN- SEMBLE ?, UNION, IN- TER, INCLUS et COMPA- RE, données ici, auxquelles il faut rajouter la primitive MEMBER présente dans tous les systèmes Lisp (et présentée dans le corps de l'article). (de unique (liste) (cond ((null liste) 0) ((member (car liste)(cdr liste)) (unique (cdr liste))) (t (cons (car liste)(unique (cdr liste)))))) (de union (11 12) (unique (append 11L2))) (de inter (11 12) (cond ((null 11) ()) ((member (car 11) 12) (cons (car 11)(inter (cdr 11) 12))) (t (inter (cdr 11) 12)))) (de inclus (11 12) (coud ((null 11) t) ((member (car 11) 12) (t ())) ) (inclus (cdr 11) 12)) (de ensemble ? (liste) (cond ((null liste) t) ((member (car liste)(cdr liste)) ()) (t (ensemble ? (cdr liste))))) (de compare (11 12) (cond ((null 11) t) ((member (car 11) 12) (t O)) ) (compare (cdr 11) 12)) Fig. A. — La structure d'ensemble peut être implémentée à l'aide de quelques fonctions. Les opérations qui peuvent lui être appliquées sont de deux ordres : tests (ENSEMBLE ?, MEMBER (présentée dans le corps de l'article), INCLUS et COMPARE) et manipulation (UNIQUE, UNION et INTER). — UNIQUE sert à éliminer les duplications éventuelles d'éléments, et donc à créer des ensembles à partir de listes quelconques. ? (unique'(a badead f)) = (beadf) ? (unique'(a b c d e)) = (a b c d e) — ENSEMBLE ? détermine si la liste passée en argument est bien un ensemble. ? (ensemble ?'(a ba dea d f)) =() ? (ensemble ?'(b e a d f)) =t En particulier, l'expression (ensemble ? (unique ? X)) retourne toujours T (c'est-à-dire vrai) quelle que soit la forme de la liste X (il faut néanmoins que X soit une liste). — UNION et INTER permettent de créer de nouveaux ensembles en fusionnant des ensembles déjà existants. A l'aide de la fonction UNION, il est possible de créer un en- semble qui contienne tous les éléments de chacun des ensembles de départ : ? (union'(2 4 6 8)'(1 3 5 7)) = (2 4 6 8 1 3 5 7) ? (union'(a b d e)'(a c e g)) =(bdaceg) INTER construit un ensemble qui ne contient que les éléments qui appartiennent à la fois aux deux ensembles de départ : ? (inter'(2 4 6 8)'(1 3 5 7) =() ? (inter'(a b d e)'(a c e g)) = (a e) — MEMBER permet de véri- fier qu'un élément appartient bien à un ensemble : ? (member'b'(a b d e)) =t ? (member'k'(a b de)) =() — INCLUS teste si tous les éléments d'un ensemble appartiennent à un autre ensemble, en d'autres termes si un ensemble est inclus dans un autre : ? (inclus'(a o u)'(a e i o u)) =t ? (inclus'(a ou y)'(a e i o u)) =() — COMPARE vérifie l'égalité de deux ensembles quels que soient leurs éléments. Il s'agit donc d'une fonction EQUAL généralisée aux ensembles. ? (compare'(e i u a o)'(a e i o u)) = t ? (compare'(a e i y o u)'(a e i o u)) = () Toutes ces fonctions sont formées selon le même schéma. Il s'agit dans tous les cas de définitions récursives, mise à part UNION qui met simplement bout à bout deux ensembles, puis supprime les éventuelles duplications d'éléments. Réalisées à l'aide d'une opération de sélection de type CON D, elles modèlent un parcours de liste, vérifiant au passage sur chacun des éléments une condition particulière. Le résultat est soit une valeur booléenne (vrai, exprimé part, ou faux par ()), soit un ensemble construit à l'aide de la primitive CONS. Elles sont toutes fondées 152 — MICRO-SYSTEMES Décembre 1984
NOM DE LA FONCTION Arguments : 1 ou 2 arguments TESTS CONSTRUCTIONS ADOPTEES Test d'arrêt le premier argument est vide ? Un résultat simple : T ou g Vérification d'une propriété sur le premier argument Un résultat simple : Tout) Condition par défaut si aucun des autres tests n'est vérifié On rappelle cette fonction en passant le CDR de l'un des arguments avec une construction éventuelle d'une liste Fig. B. — Toutes ces fonctions sont organisées autour d'un schéma général de récursion qui comprend deux tests (dont au moins l'un des deux est un est d'arrêt), et une opération par défaut (lorsque les tests ne sont pas vérifiés). ? (inter'(a b c)'(e ai c o)) => niveau 1 : appel initial 11 = (a b c) 12 (e ai c o) 11 vide ? —> non a membre de (e ai c o) —> oui => niveau 2 : appel récursif 11 = (b c) 12 = (e ai c o) 11 vide ? —> non b membre de (e ai co) —> non => niveau 3 : appel récursif 11= (c) 12= (e ai c o) 11 vide ? —> non c membre de (e ai c o) —> oui => niveau 4 : appel récursif 11 = () 12 = (e ai c o) 11 vide ? —> oui <= niveau 4 : retour résultat = O <= niveau 3 : (cons'c ()) retour résultat = (c) <= niveau 2 : retour résultat = (c) I <= niveau 1 : (cons'a'(c)) retour résultat = (a c) (a c) Fig C— La trace de l'exécution de la fonction INTER montre l'imbrication des niveaux de récursivité. et le resuitat qui est construit à l'aide de la primitive CONS au retour de certains appels. sur le modèle de la figure B. Cette figure visualise la trace d'exécution de INTER. Le traitement s'effectue en deux étapes. Au cours de la première, la fonction tente de trouver un point d'arrêt en descendant plusieurs niveaux de récursivité. Puis, elle revient au niveau général, remontant au passage une liste qu'elle construit à l'aide de la primitive CONS. Si l'on veut créer des ensembles d'ensembles, il faut redéfinir la fonction MEM- BER donnée dans le corps du texte, de manière à ce qu'elle puisse comparer des ensembles entre eux. Il suffit pour cela de remplacer EQUAL par COMPARE. Toutefois, il faut garder présent à l'esprit le paradoxe de Gôdel : l'ensemble de tous les ensembles se contient-il lui-même ? mier élément de la liste et de l'argumentX. Cette fonction est en réalité une primitive, disponible dans tous les systèmes Lisp, et écrite en langage machine pour plus d'efficacité. Mais cet exemple montre les capacités de Lisp à pouvoir définir, et donc à redéfinir par l'utilisateur s'il le désire, ses propres primitives. Il est même possible, et facile, de décrire un interpréteur Lisp en Lisp ! La valeur des variables Nous avons jusqu'à présent montré le fonctionnement du langage sans parler d'affectation ni de variables. En raison de son caractère fonctionnel, et de ses qualités récursives, il est possible d'écrire des programmes qui ne font presque jamais appel à des variables : toutes les informations sont passées en arguments des fonctions, et, après QUELQUES IMPLEMENTATIONS DE LISP Lisp est un langage disponible maintenant sur presque tous les ordinateurs. De nombreuses implantations ont vu le jour sur tous les « gros » : IBM, Vax, Univac, Multics et les autres. Deux versions françaises, qui n'ont rien à envier à leurs homologues américains, s'affrontent : Vlisp, développée à l'université de Vincennes par le pionnier de Lisp en France, Patrick Greusay, a été implanté sur un grand nombre d'ordinateurs : du Solar au Vax, en passant par différents PDP, et plus généralement tous les ordinateurs disposant du système d'exploitation Unix ; de son côté, Lelisp, conçu à l'INRIA à partir d'un modèle de Jérôme Chailloux, est bien adpaté à des applications industrielles, et fonctionne lui aussi sur la plupart des ordinateurs précités. Les micro-ordinateurs ne sont pas en reste : ils disposent désormais de très belles implémentations de Lisp. Passons rapidement sur deux versions de Lisp disponibles sur Apple : Plisp et Applisp, très décevantes toutes les deux. Tout juste peuvent-elles constituer une approche et une initiation au langage. Plus performant, MuLisp de Microsoft est disponible sur tous les ordinateurs disposant de CP/M, et fonctionne depuis peu sous MS-DOS (et donc sur l'IBM PC). Cette dernière, notamment, est une version rapide, et même s'il lui manque plusieurs caractéristiques des Lisp modernes (échappements, macro caractères, etc.) il représente un outil de travail efficace pour implanter rapidement de petits logiciels d'Intelligence Artificielle. Autre Lisp disponible sur l'IBM PC, le Golden Common Lisp. Ecrit à partir du dialecte Common Lisp, ce langage constitue une version réellement professionnelle. La France n'est pas en retard dans ce domaine, bien au contraire. Lelisp 80. certainement la meilleure implantation pour les micro-ordinateurs 8 bits, tourne sur plusieurs ordinateurs disposant de CP/M, dont l'Apple Il avec l'aide d'une carte Z- 80. Malheureusement, cette version n'a pas bénéficié d'un support commercial convenable. et la plupart des disquettes ont été diffusées grâce (!) au piratage. Pour en savoir plus et acquérir ce logiciel, adressez-vous à l'INRIA (té !. : 954.9C.2C,. où il a été développé. ou au CNDP (té !. : (t 329.2 1.64'i. qui en a acouis les droits de diffusion. Deux versions encore plus puissantes oe Lelisp seront disponible des la fin de l'année sur IBM PC (et sur tous les compatibles) et au début de l'année prochaine sur Macintosh. Commercialisées par la société ACT lnformâtique (tél. : (I) 633.72.60), il s'agit dans les deux cas de versions entièrement compatibles avec les versions de Lelisp fonctionnant sur les gros ordinateurs (tels que VAX par exemple). Un logiciel développé sur l'une de ces machines « tourne » immédiatement sur les autres, à la taille mémoire près. Décembre 1984 MICRO-SYSTEMES — 153



Autres parutions de ce magazine  voir tous les numéros


Liens vers cette page
Couverture seule :


Couverture avec texte parution au-dessus :


Couverture avec texte parution en dessous :


Micro Systèmes numéro 48 décembre 1984 Page 1Micro Systèmes numéro 48 décembre 1984 Page 2-3Micro Systèmes numéro 48 décembre 1984 Page 4-5Micro Systèmes numéro 48 décembre 1984 Page 6-7Micro Systèmes numéro 48 décembre 1984 Page 8-9Micro Systèmes numéro 48 décembre 1984 Page 10-11Micro Systèmes numéro 48 décembre 1984 Page 12-13Micro Systèmes numéro 48 décembre 1984 Page 14-15Micro Systèmes numéro 48 décembre 1984 Page 16-17Micro Systèmes numéro 48 décembre 1984 Page 18-19Micro Systèmes numéro 48 décembre 1984 Page 20-21Micro Systèmes numéro 48 décembre 1984 Page 22-23Micro Systèmes numéro 48 décembre 1984 Page 24-25Micro Systèmes numéro 48 décembre 1984 Page 26-27Micro Systèmes numéro 48 décembre 1984 Page 28-29Micro Systèmes numéro 48 décembre 1984 Page 30-31Micro Systèmes numéro 48 décembre 1984 Page 32-33Micro Systèmes numéro 48 décembre 1984 Page 34-35Micro Systèmes numéro 48 décembre 1984 Page 36-37Micro Systèmes numéro 48 décembre 1984 Page 38-39Micro Systèmes numéro 48 décembre 1984 Page 40-41Micro Systèmes numéro 48 décembre 1984 Page 42-43Micro Systèmes numéro 48 décembre 1984 Page 44-45Micro Systèmes numéro 48 décembre 1984 Page 46-47Micro Systèmes numéro 48 décembre 1984 Page 48-49Micro Systèmes numéro 48 décembre 1984 Page 50-51Micro Systèmes numéro 48 décembre 1984 Page 52-53Micro Systèmes numéro 48 décembre 1984 Page 54-55Micro Systèmes numéro 48 décembre 1984 Page 56-57Micro Systèmes numéro 48 décembre 1984 Page 58-59Micro Systèmes numéro 48 décembre 1984 Page 60-61Micro Systèmes numéro 48 décembre 1984 Page 62-63Micro Systèmes numéro 48 décembre 1984 Page 64-65Micro Systèmes numéro 48 décembre 1984 Page 66-67Micro Systèmes numéro 48 décembre 1984 Page 68-69Micro Systèmes numéro 48 décembre 1984 Page 70-71Micro Systèmes numéro 48 décembre 1984 Page 72-73Micro Systèmes numéro 48 décembre 1984 Page 74-75Micro Systèmes numéro 48 décembre 1984 Page 76-77Micro Systèmes numéro 48 décembre 1984 Page 78-79Micro Systèmes numéro 48 décembre 1984 Page 80-81Micro Systèmes numéro 48 décembre 1984 Page 82-83Micro Systèmes numéro 48 décembre 1984 Page 84-85Micro Systèmes numéro 48 décembre 1984 Page 86-87Micro Systèmes numéro 48 décembre 1984 Page 88-89Micro Systèmes numéro 48 décembre 1984 Page 90-91Micro Systèmes numéro 48 décembre 1984 Page 92-93Micro Systèmes numéro 48 décembre 1984 Page 94-95Micro Systèmes numéro 48 décembre 1984 Page 96-97Micro Systèmes numéro 48 décembre 1984 Page 98-99Micro Systèmes numéro 48 décembre 1984 Page 100-101Micro Systèmes numéro 48 décembre 1984 Page 102-103Micro Systèmes numéro 48 décembre 1984 Page 104-105Micro Systèmes numéro 48 décembre 1984 Page 106-107Micro Systèmes numéro 48 décembre 1984 Page 108-109Micro Systèmes numéro 48 décembre 1984 Page 110-111Micro Systèmes numéro 48 décembre 1984 Page 112-113Micro Systèmes numéro 48 décembre 1984 Page 114-115Micro Systèmes numéro 48 décembre 1984 Page 116-117Micro Systèmes numéro 48 décembre 1984 Page 118-119Micro Systèmes numéro 48 décembre 1984 Page 120-121Micro Systèmes numéro 48 décembre 1984 Page 122-123Micro Systèmes numéro 48 décembre 1984 Page 124-125Micro Systèmes numéro 48 décembre 1984 Page 126-127Micro Systèmes numéro 48 décembre 1984 Page 128-129Micro Systèmes numéro 48 décembre 1984 Page 130-131Micro Systèmes numéro 48 décembre 1984 Page 132-133Micro Systèmes numéro 48 décembre 1984 Page 134-135Micro Systèmes numéro 48 décembre 1984 Page 136-137Micro Systèmes numéro 48 décembre 1984 Page 138-139Micro Systèmes numéro 48 décembre 1984 Page 140-141Micro Systèmes numéro 48 décembre 1984 Page 142-143Micro Systèmes numéro 48 décembre 1984 Page 144-145Micro Systèmes numéro 48 décembre 1984 Page 146-147Micro Systèmes numéro 48 décembre 1984 Page 148-149Micro Systèmes numéro 48 décembre 1984 Page 150-151Micro Systèmes numéro 48 décembre 1984 Page 152-153Micro Systèmes numéro 48 décembre 1984 Page 154-155Micro Systèmes numéro 48 décembre 1984 Page 156-157Micro Systèmes numéro 48 décembre 1984 Page 158-159Micro Systèmes numéro 48 décembre 1984 Page 160-161Micro Systèmes numéro 48 décembre 1984 Page 162-163Micro Systèmes numéro 48 décembre 1984 Page 164-165Micro Systèmes numéro 48 décembre 1984 Page 166-167Micro Systèmes numéro 48 décembre 1984 Page 168-169Micro Systèmes numéro 48 décembre 1984 Page 170-171Micro Systèmes numéro 48 décembre 1984 Page 172-173Micro Systèmes numéro 48 décembre 1984 Page 174-175Micro Systèmes numéro 48 décembre 1984 Page 176-177Micro Systèmes numéro 48 décembre 1984 Page 178-179Micro Systèmes numéro 48 décembre 1984 Page 180-181Micro Systèmes numéro 48 décembre 1984 Page 182-183Micro Systèmes numéro 48 décembre 1984 Page 184-185Micro Systèmes numéro 48 décembre 1984 Page 186-187Micro Systèmes numéro 48 décembre 1984 Page 188-189Micro Systèmes numéro 48 décembre 1984 Page 190-191Micro Systèmes numéro 48 décembre 1984 Page 192-193Micro Systèmes numéro 48 décembre 1984 Page 194-195Micro Systèmes numéro 48 décembre 1984 Page 196-197Micro Systèmes numéro 48 décembre 1984 Page 198-199Micro Systèmes numéro 48 décembre 1984 Page 200-201Micro Systèmes numéro 48 décembre 1984 Page 202-203Micro Systèmes numéro 48 décembre 1984 Page 204-205Micro Systèmes numéro 48 décembre 1984 Page 206-207Micro Systèmes numéro 48 décembre 1984 Page 208-209Micro Systèmes numéro 48 décembre 1984 Page 210-211Micro Systèmes numéro 48 décembre 1984 Page 212-213Micro Systèmes numéro 48 décembre 1984 Page 214-215Micro Systèmes numéro 48 décembre 1984 Page 216-217Micro Systèmes numéro 48 décembre 1984 Page 218-219Micro Systèmes numéro 48 décembre 1984 Page 220-221Micro Systèmes numéro 48 décembre 1984 Page 222-223Micro Systèmes numéro 48 décembre 1984 Page 224-225Micro Systèmes numéro 48 décembre 1984 Page 226-227Micro Systèmes numéro 48 décembre 1984 Page 228-229Micro Systèmes numéro 48 décembre 1984 Page 230-231Micro Systèmes numéro 48 décembre 1984 Page 232-233Micro Systèmes numéro 48 décembre 1984 Page 234-235Micro Systèmes numéro 48 décembre 1984 Page 236-237Micro Systèmes numéro 48 décembre 1984 Page 238-239Micro Systèmes numéro 48 décembre 1984 Page 240-241Micro Systèmes numéro 48 décembre 1984 Page 242-243Micro Systèmes numéro 48 décembre 1984 Page 244-245Micro Systèmes numéro 48 décembre 1984 Page 246