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 : 184 - 185  |  Aller à la page   OK
Pages suivantes >
184 185
Encadré 2 EINTERPRETE COTE PILE Pour certains, comprendre la manière dont Lisp fonctionne aide à concevoir la notion de récursivité. Son interprète est constitué essentiellement de trois parties  : la première gère l'espace mémoire, c'est-à-dire la structure des listes et des atomes, la seconde définit l'évaluateur, c'est-à-dire les deux fonctions EVAL et APPLY, et la troisième est composée de l'ensemble des primitives du langage. Comparé à sa puissance d'expression, l'évaluateur (dans sa forme de base et sans optimisation) n'est pas d'une très grande complexité, même s'il requiert un grand savoir-faire de la part des implémenteurs. On peut concevoir son organisation à travers une machine virtuelle à pile, c'est-à-dire un processeur fictif (qui peut ensuite être implémenté sur n'importe quel véritable ordinateur) comprenant un certain nombre de registres réservés à un usage particulier, et bien sûr une pile, dans laquelle seront mémorisées de nombreuses informations telles que les différentes adresses de retour des fonctions. Pour simplifier, on dira qu'il existe un registre (appelonsle RI) contenant la liste des expressions à évaluer, qui est sauvé sur la pile lors d'un appel à une fonction et restauré à sa valeur initiale après évaluation. Par exemple, si la fonction CARRE est définie ainsi : ? (de carre (x) (* xx)) = carre pour évaluer une expression de la forme (CARRE 4), l'interprète procède comme suit  : I° L'expression n'étant pas un atome, il suppose que CARRE est une fonction. 2° Il sauve sur la pile l'adresse de retour (comme cette expression est évaluée au niveau le plus haut, c'est l'adresse de la fonction TO- PLEVEL qui sera placée sur la pile) et l'ancienne valeur de la variable X (pour éviter de détruire le contenu qu'elle avait par effet de bord). 3° Il place la définition de CARRE — c'est-à-dire la suite des expressions qui la constituent, ici seulement (* X X) dans le registre R1, et place son argument (après l'avoir lui-même évalué) dans la variableX, puis il recommence les opérations. Après avoir constaté que * est une fonction prédéfinie, il appelle cette fonction, qui retourne la valeur 16. 4° Ce résultat est placé dans un registre spécial R2 qui contient la valeur de retour. 5° Puis l'ancienne valeur de X est dépilée et réaffectée à la variable, le registre RI subissant la même opération. De ce fait, le système évalue la suite de RI, c'està-dire la fonction TOPLE- VEL, qui affiche le résultat (la valeur de R2), 16. La pile joue donc un rôle essentiel dans le déroulement de l'évaluation, en conservant les valeurs des variables (ce qui permet de définir des variables locales) et les adresses de retour. C'est elle qui permet de conserver les différents appels d'une fonction lors d'une exécution récursive, et donc de mémoriser un chemin suivi lors d'une exploration dans un espace de recherche. récupérés lorsqu'une situation conduit à un échec. Si la solution du problème est trouvée, le système remonte brutalement, à cause du mécanisme d'échappement (voir encadré 3), jusqu'à la fonction EXPLORER. Il est possible d'utiliser un tel système pour de nombreuses applications. Plutôt que de rependre notre exemple de laby- 184 — MICRO-SYSTEMES rinthe, nous l'emploierons pour résoudre un petit problème de logique  : « lin dompteur d'un petit cirque ambulant doit faire traverser un fleuve à ses trois lions et à ses trois chiens. Malheureusement, son embarcation ne peut contenir que deux de ces animaux à la fois. De plus, il ne peut jamais laisser plus de lions, un petit système d'exploration combinatoire ; fonctions a definir ; (initialiser) ; (si-succes etat) ; (si-echec etat) ; (faire-succes etat) ; (faire-echec etat) ; (generer etat) ; (DejaVu etat) ; (vu etat) pour toutes applications initialisation  : renvoie la liste des etats initiaux que faire en cas de succes que faire en cas d'échec generer tous les etats suivants a-t-on deja vu cet etat considerer cet etat comme deja vu (de Explorer () (tag succes (EssaieTous (initialiser) 1) "c'est un echec")))))) (de EssaieTous (etats n) (mapc (lambda (z) (ExploreEtat z n)) etats) (if% traces (print "et ca remonte")))) (de ExploreEtat (etat n) (when (not (DejaVu etat)) (Vu etat) (if XtraceX (print "etat etat " niveau  : " n)) (cond ((si-succes etat) (exit succes (faire-succes etat))) ((si-echec etat) (faire-echec etat)) (t (EssaieTous (Generer etat) (1. n)))))) (setq% trace% t) ; application à la traversée des Lions et des Chiens ; description d'un etat (rgrv) (de RiveGauche (etat)(car etat)) (de RiveDroite (etat)(cadr etat)) ; la liste des transferts possibles (setq TransfertaPossibles'((Chien BAT (Chien Chien BAT) (Lion Lion BAT) (Chien Lion BAT) (Lion BAT))) ; la generation de tous les nouveaux etats (de Generer (etat) (Genererlst TransfertsPossibles (if (member'BAT (RiveGauche est))'RiveGauche'RiveDroite))) (de Genererlst (translist cote) (cond ((null translist) O) ((applicable ? (car translist) (funcall cote etat)) (cons (Transfert (car translist) cote etat) (genererlst (cdr translist) cote))) (t (genererlst (cdr translist)cote)))) ; l'opérateur TRANS est il applicable ? (de applicable ? (trans rive) (and (<= (nombre'Lion transKnombre "Lion rive)) (<= (nombre'Chien trans)(nombre'Chien rive)))) ; pour transférer effectivement les personnes de TRANS ; à partir de l'état ETAT et de la rive COTE (de transfert (tram cote etat) Fig. 5. - Le listing complet du programme d'exploration combinatoire appliqué à Mars 1985
(if (equal cote'RiveGauche) (list (supprime trans (RiveGauche etat)) (ajoute trans (RiveDroite etat))) (list (ajoute trans (RiveGauche etat)) (supprime trans (RiveDroite etat))))) ; tester quand il y a un succès (de si-sucres (etat)(null (RiveGauche etat))) (de faire-succes (etat) (print -reussi l) ; tester quand il y s un échec (de si-echec (etat) (or (and (> (nombre lion (RiveGauche eta0)(nombre (RiveGauche etat))) (> (nombre Chien (RiveGauche etat)) 0)) (and (> (nombre lion (RiveDroite etat))(nombre'Chien (RiveDroite etat))) (> (nombre'Chien (RiveDroite eut)) 0)))) (de faire-echec (etat) (print "*" Chiens manges ")) ; l'initialisation (de initialiser () (let ((EtatInit'((Lion Lion Lion Chien Chien Chien BAT)()))) (setq DejaVus O) (Vu &t'Unit) (Generer &t'and))), la gestion des états déjà explorés (de vu (etat) (let ((et (list (nombre'Lion (RiveGauche etat)) (nombre Chien (RiveGauche etat)) (nombre'BAT (RiveGAuche etat))))) (ifn (member et Dejavus) (newl DejaVus et)))) (de DejaVu (etat) (member (list (nombre'Lion(RiveGauche etat)) (nombre'Chien (RiveGauche etat)) (nombre'BAT (RiveGauche etat))) DejaVus)) ; les utilitaires ; pour connaitre le nombre de X dans LST (de nombre (zlst) (cond ((nullls00) ((equal z (car 131.))(1* (nombre x (cdr Ist)))) (t (nombre z (cdrlst))))) ; supprime tous les éléments du transfert TRANS de la rive LST (de supprime (translst) (mapc (lambda (z) (setqlst (supprl zlst))) trans) Ist)) (de supprl (vlst) (cond ((nullIst) O) ((equal (carlst) v) (cdrlst)) (t (cons (car Ist)(supprl v (cdrlst)))))), ajoute tous les éléments du transfert TRANS à la rive LST (de ajoute (translst)(append trans ! st)) l'exemple de la traversée des lions et des chiens. ARTEFACT ? (explorer) etat  : ((lion lion lion chien chien)(chien bat)) niveau  : 1 *" chiens manges etat  : ((lion lion lion chien)(chien chien bat)) niveau  : 1 ** chiens manges etat  : ((lion chien chien chien)(lion lion bat)) niveau  : 1 etat  : ((lion bat lion chien chien chien)(lion)) niveau  : 2 etat  : ((lion lion chien chien)(chien bat lion)) niveau  : 3 etat  : ((lion bat lion lion chien chien)(chien)) niveau  : 4 ** chiens manges et ca remonte etat  : ((lion lion chien)(chien chien bat lion)) niveau  : 3 chiens manges etat  : ((chien chien chien)(lion lion bat lion)) niveau 3 etat  : ((lion bat chien chien chien)(lion lion)) niveau 4 etat  : ((lion chien chien)(chien bat lion lion)) niveau  : 5 ** chiens manges etat  : ((lion chien)(chien chien bat lion lion)) niveau  : 5 etat  : ((chien bat lion chien)(chien lion lion)) niveau  : 6 — chiens manges etat  : ((lion lion bat lion chien)(chien chien)) niveau  : 6 chiens manges etat  : ((chien lion bat lion chien)(chien lion)) niveau  : 6 etat  : ((lion lion)(chien chien bat chien lion)) niveau  : 7 etat  : ((chien bat lion lion)(chien chien lion)) niveau  : 8 ** chiens manges etat  : ((lion bat lion lion)(chien chien chien)) niveau  : 8 etat  : ((lion)(lion lion bat chien chien chien)) niveau  : 9 etat  : ((chien bat lion)(lion lion chien chien)) niveau  : 10 etat  : (() (chien lion bat lion lion chien chien)) niveau  : 11 reussi reussi Fig. 6. - Le programme ‹< raisonne » en explorant toutes les situations possibles. Cette méthode doit être enrichie lorsque l'espace de recherche est trop grand  : « l'explosion combinatoire » qui en résulte fait croître le temps de calcul de manière exponentielle. que de chiens, pour éviter que les premiers ne dévorent les seconds. Comment le pauvre dompteur réussira-t-il à faire passer toute sa ménagerie ? » Pour résoudre ce casse-tête, nous utiliserons notre système d'exploration, après avoir défini toutes les fonctions annexes. Pour ce faire, nous serons amenés à faire des choix concernant la nature et la modélisation des états. Ces derniers sont associés aux positions respectives des animaux de part et d'autre du fleuve. Pour les représenter, une liste constituée elle-même de deux listes de symboles suffit. Par exemple, si deux lions, deux chiens et le dompteur (et son bateau) se trouvent sur la rive gauche et un lion avec un chien sur la rive droite, l'état en question est représenté ainsi  : ((Lion Lion Chien Chien BAT) (Lion Chien)) Faire passer un ou deux animaux d'une rive à l'autre constitue une transformation d'état. Par exemple, l'opérateur (Lion BAT) place le système dans le nouvel état  : ((Lion Chien Chien) (BAT Lion Lion Chien) qui conduit à un échec, les deux lions dévorant le chien sur la rive droite. Engendrer une nouvelle situation revient donc à transférer une partie des occupants d'une rive sur l'autre, compte tenu des opérateurs disponibles et des contraintes du jeu. Un certain nombre d'utilitaires deviennent indispensables, pour vérifier la validité des configurations, et réaliser effectivement le transfert d'une rive à l'autre. La figure 5 montre le listing du programme complet, qui comprend à la fois les fonctions générales, indépendantes de toute application, celles qui sont au contraire relatives à un domaine particulier, et enfin les fonctions utilitaires qui s'occupent des tâches d'ajout, de suppression et de tests de présence des animaux sur l'une ou l'autre des rives. De plus, les états déjà rencontrés au cours de Mars 1985 MICRO-SYSTEMES — 185



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