Micro Systèmes n°51 mars 1985
Micro Systèmes n°51 mars 1985
  • Prix facial : 24 F

  • Parution : n°51 de mars 1985

  • Périodicité : mensuel

  • Editeur : Société Parisienne d'Edition

  • Format : (203 x 271) mm

  • Nombre de pages : 246

  • Taille du fichier PDF : 212 Mo

  • Dans ce numéro : dossier sur le programme Esprit.

  • Prix de vente (PDF) : gratuit

Dans ce numéro...
< Pages précédentes
Pages : 182 - 183  |  Aller à la page   OK
Pages suivantes >
182 183
Opérateurs A gauche I f I 1 + 1 Etats• OK 1 # 1 Impossible A droite En bas A gauche En haut # I # I # I 1 II 1 + 1 iii + 1 + 1 Impossible OK Impossible Impossible• It./.. Impossible Impossible OK\A droite En bas A gauche En haut I I# I 11# I I# I 1 Impossible Impossible Impossible 1 +11 Impossible Impossible Cul-de-sec.• sortie Fig. 4. — Un espace d'états est obtenu par application successive de tous les opérateurs à partir de la situation initiale. Lors de son exécution, le programme parcourt tous ces états, et effectue un « retour en arrière » lorsqu'il aboutit à un cul-de-sac. toujours des labyrinthes ?) , en définissant un système de base d'exploration combinatoire. Il suffira alors d'y ajouter les fonctions caractéristiques du domaine. De ce fait, le même système de base, la partie généralement la plus difficile à concevoir, pourra être utilisé dans des situations différentes. Trois fonctions suffisent à en décrire le noyau  : EXPLO- RER, ESSAIETOUS et EX- PLOREETAT. Il faut ensuite leur adjoindre une pléiade de fonctions annexes et dépendantes du contexte  : SI-SUCCES, et SI-ECHEC, qui déterminent 182 — MICRO-SYSTEMES si l'on atteint l'état final (le problème résolu) ou si l'on aboutit à une impasse ; dans l'un ou l'autre cas, il faudra activer les fonctions FAIRE- SUCCES et FAIRE-ECHEC qui précisent ce qui doit être effectué dans de telles situations. DEJA-VU et VU gèrent la « mémoire » du système pour lui éviter de boucler indéfiniment ; la fonction GENERER est responsable des transitions  : elle retourne la liste des états, issus d'une configuration donnée, en lui appliquant toutes les transformations valides dont la conformité est testée préalablement à l'aide de APPLICA- BLE ?. Enfin, INITIALISER prépare le système et génère la liste des états découlant de la situation initiale. Les deux fonctions ESSAIE- TOUS et EXPLOREETAT s'appellent mutuellement  : la première applique la seconde à tous les éléments d'une liste passée en argument. EXPLO- REETAT détermine si l'état passé en argument est un état final, et si non, applique ES- SAIETOUS à toutes les situations qui en résultent. Il s'agit donc d'un mécanisme récursif. Au cours de chaque appel, les états déjà parcourus sont mémorisés, et LES FONCT La réalisation de programmes performants oblige parfois le programmeur à se confronter à des problèmes d'implantation afin d'optimiser au mieux temps de calcul et espace mémoire. -Le développement de logiciels en Lisp n'échappe pas à cette règle, et il faut parfois recourir à des fonctions difficiles à manipuler, parce qu'elles transforment la structure physique des listes. Deux d'entre elles sont fondamentales, car toutes les autres peuvent se définir à partir de celles-là  : RPLACA et RPLACD. La première prend en argument un doublet (c'est-à-dire le constituant d'une liste) et une expression, et remplace le CAR (c'est-à-dire la tête) de la liste par la valeur de l'expression, alors que la seconde en modifie le CDR : ? (setq listel'(a b c d)) = (a b c d) ? (rplaca listel'x) = (x b c d) ? listel = (x b c d) ? (rplacd listel'(y u i)) = (x y u i) ? listel = (x y u i) Ces transformations sont définitives. Il ne faut pas confondre le comportement de ces fonctions avec l'usage de CAR, CDR et CONS qui n'implique aucun effet secondaire. ? (setq liste2'(a b c d)) = (a b c d) ? (cons'x (cdr liste2)) = (x b c d) ? liste2 = (a b c d) La figure A montre l'effet de ces fonctions sur la structure physique des listes  : elles agissent directement sur les pointeurs qui relient entre eux les doublets en formant des listes. Leur emploi doit être effectué avec circonspection  : de nombreux effets pervers peuvent provenir d'une utilisation mal contrôlée. Du fait de cette modification interne qu'elles imposent, toutes les variables Mars 1985
ARTEFACT ONS DE MANIPULATION ET LES TABLEAUX a) Avant  : Liste 1 —.1> A (Rplaca Liste 1'X) > NIL D ; les fonctions de manipulations de listes indicées (denthcdr (il) (cond ((pull 1) ()) ((= i 0) I) (t (nthcdr (1- i) (cdr I))))) (denth (i l) (car (nthcdr t 1))) Après  : Liste 1 -111> blAvant  : Liste 2 Après  : Liste 1—er Liste 2 X Y (Rplacol Liste 1 Liste 2) Fig. A. — Les opérations de manipulation physique (rplaca (a) etrplacd (b)) modifient la structure des listes, en travaillant directement sur les pointeurs qui relient les doublets entre eux. qui partagent ces listes se trouvent modifiées : ? (setq listel'(a b c d)) = (a b c d) ? (setq liste2 (cdr listel)) = (b c d) ? (rplaca liste2'x) = (x c d) ? liste2 = (x c d) ? listel = (a x c d) Dans certains cas, elles permettent de créer des structures de données bizarres qui n'existent pas en Lisp pur  : les listes circulaires. Ces drôles d'expressions ne peuvent facilement être imprimées  : du fait de leur nature, leur visualisation par les fonctions classiques d'impression (PRINT) ne s'arrête jamais (les points signalent que l'impression continue indéfiniment, sauf si la fonction PRINT limite la 1 D NIL NIL taille des listes qu'elle édite) : ? (setq listel'(a)) = a ? (rplacd listel listel) = (aaaaaaaaa... ? (setq liste2'(a b c)) = (rplaca liste2 liste2) ? (((((((((((... b c) b c) b c) b c)... Dans d'autres occasions, c'est justement leur effet pervers qui est recherché pour limiter le nombre de manipulations  : en particulier pour implémenter des tableaux. La structure de donnée fondamentale de Lisp est la liste. Il est pourtant parfois utile de représenter des informations sous forme de tableaux. La plupart des versions disposent de la possibilité de traiter des vecteurs ou des matrices (tableaux de dimensions 1 et 2) à la manière de Pascal, Basic ou Fortran, avec cependant une (de setnth (ilv) (let ((lst (nthcdr i I))) (if l(rplacalst v)) v)) (de makelist (n v) (if () n 0) (cons v (makelist (1- n v))))) Fig. B. — II est possible de se créer facilement des structures de données qui n'existent pas dans le langage de base (bien que la majorité des versions de Lisp supportent ces extensions), telles que les vecteurs, ou tableaux à une dimension. différence essentielle  : chaque case peut être remplie par un nombre, un symbole, une liste, voire un tableau. Mais même sans disposer de ces structures de manière prédéfinie, il est toujours possible de les construire à l'aide de listes, en manipulant directement leur structure. Dans un premier temps, il faut créer des fonctions qui peuvent traiter des vecteurs  : NTHCDR, NTH, SETNTH et MAKELIST (fig. B). Les deux premières ramènent une liste, ou le CAR de la liste, à partir de son indice (compté à partir de 0) ; la troisième sert à affecter une valeur à la case d'indice 1, tandis que la dernière construit un vecteur comme une liste de n doublets initialisés à une valeur par défaut : ? (setq listel (makelist 5 0)) = (00000) ? (setnth 2 listel (+3 2)) = (00500) ? (setnth 4 listel'(a b)) = (0050 (a b)) ? (nthcdr 2 listel) = (50 (a b)) ? (nth 4 listel) = (a b) ? listel = (0050 (a b)) Créer des tableaux à deux dimensions devient ainsi très facile, puisqu'il suffit d'ajouter les trois fonctions TREF, TSET et MAKETABLE : ? (de tref (tab i j) (nth j (nth i tab))) = tref ? (de tset (tab i j) (setnth j (nth i tab) y)) = tset ? (de maketable (i j el) (makelist i (makelist j el))) = maketable et pour visualiser : ? (de printab (tab) (mapcar'print tab) t) = printab On peut ensuite traiter ces structures comme on le ferait dans des langages classiques : ? (setq tabl'((a b c d) (e f g h) (i j k 1))) = ((a b c d) (e f g h) (i j kl)) ? (printab tabl) (abcd) (efgh) (i j kl) =t ? (tset tabl12'(123)) = (123) ? (printab tabl) (abcd) (e f (123) h) (i j kl) =t ? (tget tabl0 0) = a ? (tget tabl2 3) = 1 Mars 1985 MICRO-SYSTEMES — 183



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