Obligement - L'Amiga au maximum

Vendredi 19 avril 2019 - 00:29  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Accueil
 · A Propos
 · Articles
 · Galeries
 · Glossaire
 · Liens
 · Liste jeux Amiga
 · Quizz
 · Téléchargements
 · Trucs et astuces


Articles

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Articles divers

 · Articles in english
 · Articles en d'autres langues


Twitter

Suivez-nous sur Twitter




Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Logiciels
 · Jeux
 · Scène démo
 · Divers


Jeux Amiga

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Trucs et astuces

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Glossaire

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


Contact

David Brunet

Courriel

 


Programmation : Lisp - Les huit reines
(Article écrit par Patrick Chaze et extrait d'Amiga News Tech - septembre 1991)


Le but de cet article n'est pas de vous faire un cours sur Lisp, mais plutôt de vous inciter à le découvrir par vous-mêmes, au travers d'AMXLisp, un interpréteur Lisp accessible à toutes les bourses, et par voie de conséquence, d'accéder à un autre style de programmation. AMXLisp n'est autre que la version pour Amiga du très célèbre produit du domaine public XLisp existant sur de nombreux systèmes. Cette version a été écrite en C par David Betz pour ce qui concerne la partie interpréteur, l'interface Amiga étant dûe à François Rouaix.

Rappel historique

Pour commencer, un rappel sur ce langage assez peu répandu sur Amiga. Il s'agit d'un des plus anciens langages de programmation. Ses premières implémentations ont vu le jour à la fin des années 1960, quelques années seulement après Fortran. Lisp a été conçu par John Mc Carthy pour le traitement d'expressions symboliques (par opposition au traitement numérique). Il a été utilisé dès son origine pour écrire des programmes de calcul symbolique différentiel et intégrale, de logique mathématique et dans le cadre de la programmation de jeux. C'est de plus un langage interactif avec un environnement intégré. Ceci a pour conséquence que du cycle classique de développement édition texte -> compilation -> édition de lien -> chargement -> exécution des langages compilés habituels, nous passons au cycle réduit lecture d'une expression -> évaluation (cycle propre à l'interprétation).

Ces vertus alliées à la simplicité de la syntaxe de Lisp, offrent la possibilité de programmer immédiatement un problème sans passer par des stades de déclarations de variables ou de types et finalement, le fait que Lisp soit basé sur la récursivité, en fait un excellent langage d'apprentissage et d'enseignement de la programmation.

Initiation

Comme certaines mauvaises langues le prétendent, Lisp n'est pas l'acronyme de "List of Insipid and Stupid Parenthesis" mais plus simplement de LISt Programming. Ainsi que l'indique ce nom, Lisp traite essentiellement des listes. Une liste est quelque chose qui commence par une parenthèse ouvrante "(" et se termine par une parenthèse fermante ")", par exemple : (A N T 25).

Une liste est composée d'atomes qui peuvent êtres des entiers, des caractères ou des chaînes. Pour manipuler ces listes, on utilise un certain nombre de fonctions parmi lesquelles on peut citer les fonctions de base suivantes : "car", "cdr" et "cons" qui permettent respectivement d'extraire le premier élément d'une liste, d'obtenir la liste privée de son premier élément, et de construire une nouvelle liste. La notation utilisée pour les appels de fonctions est la notation préfixée, c'est-à-dire la fonction suivie de ses arguments. En d'autres termes, le premier élément d'une liste sera interprété comme une fonction, sauf indication contraire de votre part. Le symbole "'" (apostrophe) permet d'éviter l'évaluation de l'expression qui le suit, qu'il s'agisse d'une liste ou bien d'un atome. Exemple :

Lisp

Il existe un grand nombre d'autres fonctions standard, telle que celle permettant la concaténation de deux listes :

(append '(A N T) '(25))

Ou encore celle permettant la définition d'autres fonctions :

(defun (<listes des paramètres>) <corps de la fonction>)

Lisp comprend également tout une batterie de fonctions de contrôle parmi lesquelles l'on retrouve "if" et "cond" :

(if <condition> action1 action2)

Si la condition est vraie, alors on effectuera l'action1, sinon l'action2. Une condition est vraie si son évaluation rend une autre valeur que NIL (symbole du faux en Lisp, par opposition à T (True)).

Comme signalé plus haut, programmer en Lisp, c'est programmer de manière récursive. Pour comprendre cette notion, je vous propose l'exemple typique d'une fonction récursive, la fonction factorielle :

Lisp

AMXLisp

Après cette introduction au concept de Lisp, nous allons nous intéresser de manière plus approfondie à la version dont nous disposons sur Amiga. Vous devrez disposer des répertoires et fichiers suivants :
  • fd/ (fichiers *.fd)
  • include/ (bibliothèques standard de l'Amiga).
  • intetface_src/ (sources de l'interface Amiga).
  • lsp/ (sources de configuartion, plus des exemples).
  • src/ (sources d'AMXLisp).
  • amxlisp (exécutable, noyau de l'intetprêteur).
  • Et quelques autres...
Vous pourrez remarquer qu'à l'aide des fichiers includes, vous pourrez sans problème utiliser les bibliothèques internes de l'Amiga et donc faire à peu près autant de chose qu'avec un autre langage. Il ne vous restera plus qu'à lancer l'interpréteur en tapant sous CLI la commande : amxlisp.

Rien ne vaut la pratique

A titre d'exemple, et pour illustrer le style de programmation Lisp, je vous propose maintenant de construire un programme capable de résoudre le problème dit "des huit reines". Il s'agit de placer huit reines deux à deux non en prise sur un échiquier, c'est-à-dire de telle sorte qu'aucune reine ne soit sur la même ligne horizontale, verticale ou diagonale que l'autre.

Ce problème bien connu peut être résolu de manière simple en utilisant une méthode d'exploration d'arbre des possibilités, ce qui se prête très bien à une programmation récursive.

Vous pouvez taper les fonctions suivantes directemment sous l'interpréteur, mais plus sûrement dans un fichier que vous chargerez ensuite à l'aide de la fonction "load" (load "nom de fichier") ou bien, si vous possédez la disquette ANT25, chargez le fichier source reines.lsp.

Premièrement, nous allons écrire une fonction qui déterminera si deux reines sont en prise mutuelle. Aux échecs, une reine peut se déplacer le long de la colonne, de la ligne et des deux diagonales passant par sa position actuelle. On peut donc représenter sa position sur l'échiquier par le numéro de sa ligne et de sa colonne, d'où la fonction :

Lisp

Ensuite, on représente la configuration de plusieurs reines sur l'échiquier en utilisant une liste d'éléments, chacun d'eux étant lui-même une liste à deux composantes : la ligne et la colonne de la reine sur l'échiquier. Supposons maintenant que nous voulions disposer une reine. La fonction suivante nous indique si cette position (lig, col) est valide pour la nouvelle reine à placer :

Lisp

Après ces préliminaires, nous allons pouvoir écrire la fonction qui va parcourir l'échiquier pour nous fournir l'ensemble des solutions possibles. Notons au passage que cette fonction est capable de traiter le problème plus général qui consiste à placer N reines sur un échiquier de dimension NxN.

Lisp

La fonction "place_reine" nous donne les solutions sous la forme d'une liste de positions. Il serait plus sympathique de pouvoir les visualiser graphiquement, c'est ce que je vous propose de faire avec les fonctions suivantes :

Lisp

Il suffit de modifier la fonction "place_reines" en y insérant une variable globale qui permet de stocker l'ensemble des solutions :

Lisp

...puis de rajouter dans reine-ligne, après le (print (reverse echiquier)) l'appel à (setq *solutions* (append *solutions* (list (reverse echiquier)))).

Tout cela donnera, pour un échiquier de dimension, 4 :

Lisp

Pour ceux qui désireraient tester le problème initial des huit reines, je vous signale qu'il comporte 92 solutions.

Une dernière remarque sur ce type de problème : il est bien évident que certaines techniques permettraient de ne pas parcourir l'intégralité de l'espace de recherche pour aboutir à une solution. Je citerai à ce propos une technique issue de l'intelligence artificielle : la programmation par contraintes. En effet et comme son nom l'indique, elle permet, en propageant des contraintes liées à un choix (placement d'une reine par exemple), d'enlever de l'espace de recherche un certain nombre de possibilités qu'il ne sera pas utile d'explorer par la suite. J'aurai, j'espère, l'occasion de vous en parler lors d'un prochain article.

Lisp


[Retour en haut] / [Retour aux articles]