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 : 150 - 151  |  Aller à la page   OK
Pages suivantes >
150 151
De même, il est possible de déterminer si un nombre est plus grand ou plus petit qu'un autre : ? (< 2 3) =t ? (< 3 2) =() ? (> 2 3) =() ? (> 3 2) =t Pour vérifier l'égalité struc- turelle de deux listes, on em- ploie la fonction EQUAL. Par exemple : ? (equal'(a (a b))'(a (a b))) =t ? (equal'(a b c)'(a b)) =() ? (equal'(a b)'(a c)) =() Elle peut aussi servir à com- parer des atomes entre eux : ? (equal'a'a) =t ? (equal'a'b) =() Sélection et récursivité Les structures de contrôle Lisp ressemblent beaucoup à celles des autres langages de programmation. Elles se décomposent en deux catégories : les structures de sélection et les structures de répétition. Il existe deux opérations de sélection en Lisp : IF et COND. La première correspond au IF... THEN... ELSE que l'on rencontre dans tous les langages de programmation, à la différence près qu'il s'agit ici d'un IF fonctionnel. Expliquons-nous. La plupart des langages de programmation, comme Basic, Pascal ou C sont dits impératifs. Programmer consiste à décrire les étapes du calcul à l'aide d'instructions qui effectuent des opérations sur des structures de données. En revanche, dans les langages fonctionnels tels que Lisp, la notion d'instruction n'existe pratiquement pas. Tout le traitement s'effectue par l'intermédiaire de fonctions dont le rôle principal n'est pas tant de modifier la valeur d'une variable que de produire un résultat. Il en est de même pour les opérations de sélection. A la différence de Basic ou de Pascal, IF n'est pas une instruction mais une fonction qui retourne une valeur. Par exemple, dans les langages impératifs, la réalisation d'un test qui donne le signe d'un nombre s'exprime de la manière suivante : if X < 0 then signe = -1 else signe = 1 alors qu'en Lisp il est possible d'écrire (if (< x 0) -1 1) sans devoir faire appel à une variable SIGNE supplémen- taire. De la même manière, on pourra définir une fonction MAX qui retourne le plus grand de deux nombres de la manière suivante : ? (de max (x y) max (if (> x y) x y)) ? (max 2 3) = 3 ? (max 10 4) = 10 La structure du IF est donc la suivante : (IF ) Le résultat de la partie est retournée si la condition est vraie, celui de la partie dans le cas contraire. La primitive COND est une sorte de IF généralisé, qui prend la forme suivante : (cond ( ) ( ) (..) (t )) Les tests sont examinés en séquence. Si l'un d'entre eux est satisfait (c'est-à-dire s'il retourne une valeur non nulle, donc vraie) la partie action correspondante est évaluée, et la forme COND retournera ce résultat. Le dernier test est donné sous la forme d'un atome T, dont la valeur est toujours vraie. Il s'agit de l'alternative qui est évaluée si aucune autre condition n'est vérifiée. Cette forme est équivalente à une suite de IF emboîtés : (if (if )) La fonction TYPE, présentée figure 2, détermine le type d'une expression Lisp, et retourne les symboles NOMBRE, ATOME ou LISTE selon la nature de l'argument. Elle utilise la primitive COND pour tester d'abord si la valeur est un nombre, puis s'il s'agit d'un atome ; (de type (x) (cond ((numberp x) ((atom x) (t'liste)))'nombre)'atome) Fig. 2. - La fonction TYPE détermine le type d'une valeur, et renvoie l'un des symboles NOMBRE, ATOME ou LISTE, selon la nature de son argument. enfin, si aucun des deux premiers tests n'a été satisfait, la fonction suppose que l'on est en présence d'une liste. ? (type 3) = nombre ? (type'lundi) = atome ? (type'(2 3)) = liste Tous les programmes incorporent des boucles de calcul. La répétition des tâches est à la base de l'informatique. En Lisp, ces opérations de répétitions peuvent être effectuées de plusieurs manières. La plus pure de ces techniques consiste à utiliser la récursivité du langage. Une fonction récursive est une fonction qui s'appelle ellemême. La célèbre fonction factorielle, qui se définit comme le produit des N premiers nombres entiers, est un exemple de fonction récursive : (de fac (n) (if (= n 1) 0 (* n (fac (- n 1))))) En langage ordinaire, cela revient à exprimer que la factorielle de 1 est 0, et que pour tous les autres nombres, la factorielle de N est égale au pro- (de member (x liste) (cond ((null liste)) ((equal (car liste) x) (t (member x (cdr liste))))) ? (member'a'(b d a c)) => niveau 1 : appel initial x = a liste = (b d a c) liste vide ? -> non a = b ? ->non => niveau 2 : appel récursif x = a liste = (d a c) liste vide ? -> non a = d ? ->non => niveau 3 : appel récursif x = a liste = (a c) liste vide ? -> non a = a ? -> oui alors retour niveau 3 : retour résultat = t <= niveau 2 : retour résultat = t <= niveau 1 : retour résultat = t t b) Fig. 3. - La fonction MEMBER teste la présence d'un élément X au sein d'une liste LISTE. Sa définition récursive est centrée autour d'une expression COND (a), c'est-à-dire une liste de paires « condition-action ». La trace de son exécution (b) montre les différents appels successifs de la fonction. 150 - MICRO-SYSTEMES Décembre 1984
Encadré B LA STRUCTURE INTERNE DES LISTES Les listes sont des structures de données dynamiques, car leur taille varie constamment au cours du fonctionnement des programmes. Depuis la réalisation des premiers interprètes du langage, vers le début des années 1960, des solutions ont été avancées pour les implanter efficacement. Toutes reposent sur la notion de cellule ou doublet. Elément minimum d'une liste, la cellule, représentée figure D, est composée de deux parties qui forment directement le CAR et le CDR de la liste. Celles-ci sont en fait des adresses mémoires qui pointent vers d'autres éléments Lisp : atomes ou cellules. Les listes sont ainsi constituées de cellules chaînées les unes aux autres comme le montre la figure E. Les fonctions CAR et CDR sont alors définies comme des simples accès indirects à la mémoire. Le CAR d'une cellule correspond au contenu de l'adresse de cette cellule, et son CDR au contenu de l'adresse suivante. Les expressions Lisp, et donc les fonctions, sont aussi représentées comme des listes, et font donc un grand usage des doublets. Par exemple, la figure F montre la représentation interne de l'expression Lisp : (cons (car a (append a b))) Les atomes ont généralement un espace propre et une représentation distincte de celle des doublets. Ceux-ci sont représentés sous la forme d'une structure fixe, sorte de « record » pour reprendre la terminologie Pascal, et composent la table des symboles. Dans la plupart des Lisp modernes, chaque symbole est constitué d'un certain nombre de champs qui contiennent les différentes valeurs de l'atome (fig. G) : CVAL contient la valeur de l'atome lorsqu'il est considéré comme une variable, FVAL sa valeur fonctionnelle, c'est-à-dire la définition de la fonction éventuellement attachée à cet atome, et PVAL, sa liste de propriété ; enfin PNAME contient une chaîne de caractère, le nom du symbole. Dans la construction des listes, ce n'est pas le nom externe du symbole qui est implanté dans le CAR ou le CDR des cellules, mais l'adresse de l'atome. Cette technique permet d'augmenter l'efficacité du langage. CAR CDR pointeur pointeur AA\A Fig. D. — La cellule est l'élément de base de la composition d'une liste. Elle se compose de deux adresses mémoire qui pointent vers d'autres cellules, ou des atomes. Fig. E — La structure interne d'une liste, telle que (a (a b) c) est constituée d'un ensemble de cellules qui sont chaînées les unes aux autres. 4 n NII A enn.- - ; """."""°eie CVAL FVAL 3 (Fonction (XY) (CONS (CAR X) (CARY ») P.LIST P.NAME (Profession MEDECIN Age 30 « TOTO » NIL 4 Fig. F. — Les expressions Lisp sont représentées elles aussi à l'aide de listes, c'est-à-dire sous la forme de n grappes » de cellules, qui seront analysées et évaluées par l'interpréteur. Fig. G.. — Un atome Lisp, ici TOTO, est formé de quatre champs principaux : la CVAL contient la valeur de l'atome en tant que variable ; la FVAL, supporte la définition éventuelle d'une fonction ; la P-LIST comprend la suite des paires « propriété-valeur » attachée au symbole ; enfin le P-NA ME est tout simplement le nom de l'atome, c'est-à-dire la chaîne de caractères qui est reconnue durant la phase de lecture, ou visualisée pen- 4 dant l'impression. duit de ce nombre par la factorielle de N-1. Au départ, la programmation récursive semble un peu complexe. Ces fonctions qui s'appellent elles-mêmes, comme une sorte de jeu de miroir, donnent le vertige. Elles paraissent ne reposer sur aucune base réelle, comme accrochées à un nuage. En fait, un examen attentif montre qu'il n'en est rien. Il existe toujours ce que l'on appelle un « point d'arrêt », une étape du calcul qui ne rappelle pas la fonction originale, et donc assure sa stabilité. Comme exemple de fonction récursive simple, nous allons définir une fonction qui imprime tous les éléments d'une liste passée en argument. ? (de printl (liste) = printl (print (car liste)) (if (null liste) (printl (cdr liste)))) ? (printl'(a (b c) d)) a (b c) d =t Son fonctionnement est le suivant. En premier lieu, elle imprime le premier élément de la liste. Ensuite, elle teste si la liste est vide à l'aide du prédicat NULL, qui retourne la valeur vraie dans le cas d'une liste vide. Dans l'affirmative, la fonction retourne la valeur T et s'arrête. Dans le cas contraire, elle se rappelle elle-même en passant en argument la liste privée de son premier élément. De nombreuses fonctions peuvent être définies sur ce schéma. En particulier, la fonction MEMBER, qui teste si un élément est présent à l'intérieur d'une liste, est décrite figure 3.a. Si la liste est vide, alors cela signifie que l'on n'a pas trouvé l'élément recherché, et le résultat est () ; au contraire, si le premier élément de la liste correspond, alors la fonction ramène T ; enfin, si cela ne marche pas, on continue à appliquer la fonction MEM- BER sur le reste de la liste. ? (member 3 = ? (member 4 =t'(2'(2 4 6 4 6 8)) 8)) ? (member'(a b)'(e (a b) e)) t La figure 3.b montre une représentation de ce qui se passe lors de l'évaluation de cette fonction. La fonction se rappelle elle-même jusqu'au point d'arrêt, caractérisé soit par la fin de la liste passée en argument, soit par l'égalité du pre- Décembre 1984 MICRO-SYSTEMES — 151



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