Suivez-nous sur X
|
|
|
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,
ALL
|
|
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
|
|
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
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
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 :
Il existe un grand nombre d'autres fonctions standard, telle que celle permettant la concaténation de deux
listes :
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 :
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 :
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 :
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.
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 :
Il suffit de modifier la fonction "place_reines" en y insérant une variable globale qui permet de stocker
l'ensemble des solutions :
...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 :
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.
|
