TD/TP n°1 : Welcome Lisp

1. Environnement de travail

1.1 Clisp

Dérivé des travaux sur le lamda-calcul, la première version de Lisp a été réalisée en 1958 par John Mc Carthy, au MIT (USA).
Developpé parallèlement à Fortran, langage spécialisé pour le calcul scientifique, le Lisp s'est vu orienté vers le domaine de l'intelligence artificielle.
De nombreux dialectes de la famille Lisp ont vu le jour. Parmi les plus importants ces dernières années, on trouve Scheme, très largement répendu en pédagogie et Common Lisp qui s'en inspire selon certains auteurs. Common Lisp fait l'objet d'une normalisation (G.L. Steele).

Clisp est une implantation de Common Lisp réalisée par Bruno Haible et Michael Stoll. C'est un produit professionnel qui inclut de nombreux outils (compilateur, programmation sockets, ...). Nous utiliserons qu'une partie réduite de ses fonctionnalités.

On utilise habituellement clisp en mode interactif, en tapant simplement la commande
clisp
Mais il est possible de rentrer dans ce mode interactif en intégrant un fichier d'ibstructions lisp
clips -i fichier.lisp
Sans l'option i, l'interpréteur exécute les instructions du fichier et rend la main, sans passer par le mode interactif.

1.2 Notion d'environnement interactif

- Interactivité
Fonctionnement de l'interpréteur = (print(eval(read))) ...
C'est à dire qu'il exécute une séquence de (saisie, évaluation, affichage).
Voilà un exemple de session :
> (+ 1 1)
2
> ( ) ; ici une liste vide
NIL
Notez la construction d'un commentaire précédé du symbole ;
Vous pouvez tester ces quelques lignes dans votre interpréteur ...
... Attention au blanc de séparations entre les noms de fonctions appelées et les arguments
... Attention à la construction d'expressions correctement paranthésées ... vous en aurez à manipuler !

Dans la suite de ce TD/TP, vous êtes encouragé à tester les exemples donnés et à faire vos propres expérimentations à partir de ceux-ci.
Vous avez aussi bien sûr, à répondre aux exercices qui vous seront proposés après quelques rappels ...

- Sortir de l'environnement :
On peut quitter l'interpréteur lisp en saisissant l'une des expressions suivantes : (quit), (exit) ou (bye)
> (quit)
bye.
- Stopper une évaluation :
L'utilisation des touches CTRL-D permet d'arrêter brutalement une évaluation en cours.
... si par exemple, l'évaluation a générée une boucle sans fin.

1.3 Utilisateur d'un éditeur, charger un fichier dans l'interpréteur

- Environnement de travail étendu : (Interpréteur, Editeur)
L'environnement interactif nécessite une grande attention pour la saisie de fonction assez longue.
Il devient alors efficace d'utiliser en parallèle votre éditeur favori pour saisir et corriger facilement vos constructions.
Il rest à savoir comment rapatrier vos travaux de l'éditeur dans l'interpréteur. Ci-après, deux solutions :

- Copie à la souris : Sélectionner à la souris, la bonne fonction à recopier depuis votre éditeur. Puis l'insérer, toujours avec la souris dans la fenre d'éditions.

- Une manière plus élégante est d'utilsez une fonction Lisp adhoc ... Elle existe et s'appelle load.
Une fois votre page de calcul sauvegardée, on pourra charger les focntions qu'il contient dans l'interpréteur avec
> (load "monFichier.lisp")
1.4 Aide, manuel

- Commandes d'édition
     - Le manuel de la librairie d'édition GNU d'édition utilisée par les concepteurs de Clisp.

- Documentation
     - page de manuel : http://clisp.cons.org/clisp.html
     - documentation  : http://clisp.cons.org/impnotes.html
     - Common Lisp Hyperspec : http://clisp.cons.org/clisp.html

1.5 Environnement intégré

- Emacs ... pour les amateurs ... non documenté ici (cf. Mr Google)

- Jabberwocky (en fin de séance pour les + avancés).
On pourra récupérer facilement cet IDE gratuit via internet ... chez Mr Google, questionnez "Jabberwocky" pour connaître l'origine de cette dénomination ... puis questionnez "Jabberwocky lisp" ... 

2. Quelques notions de base 

2.1 Fonction quote

La fonction quote interdit l'évaluation de son argument.

Exercice 1 :
Comment sont évaluées les constructions suivantes ... et comprendre le résultat de l'évaluation !
> (quote (+ 1 1))
> (quote (bonjour))
> (bonjour)
Notation abrégée de quote : '
> '(+ 1 1)
(+ 1 1)
2.2 Arithmétique et manipulation de nombres

Exercice 2 :
Comment sont évaluées les constructions suivantes ... et comprendre le résultat de l'évaluation !
> (+ 1 2)
> (+ 2 4 5 1)
> (* 2 3)
> (/ 2 3)
> pi
> (= (/ 5 2) 2.5)
> (/= 4 5)
> (< 3 5)
> (>= 2.5 (/ 5 2))
> (abs -5)
> (sqrt 10)
> (round 3.6)
> (cos pi)
> (cos pi/2)  ;réécrire correctement cette construction !
2.3 Liaison variable-valeur

La fonction setq permet d'établir une liaison entre une variable et une valeur. Ci-après, des exemples de votre cours :
> (setq a 12)
12
> (setq a '(12))
(12)
> (setq a "12")
"12"
La fonction setq est en fait équivalente à la fonction set avec la fonction quote sur son premier argument.

Exercice 3 :
Comment sont évaluées les constructions suivantes ... et comprendre le résultat de l'évaluation !
> (set 'a 'b)
> (set a '(c d)) ; a est évalué et a pour valeur b
> a
> b
La fonction let permet de definir l'évaluation d'une expression avec des variables locales. Dans l'exemple suivant on évalue a+b en ayant associé spécifiquement pour ce calcul a avec 3 et b avec 4 :
> (let ((a 3) (b 4)) (+ a b))
7

3. Construction de conditionnelles

3.1 Les booléens

Lisp propose
- deux booléens : les atomes T pour vrai et NIL pour faux.
- les fonctions booléennes classiques : and, or et not
- deux prédicats sur les atomes et les listes: (atom a) teste si a est un atome, (null l) teste si l est une liste vide

Exercice 4 :
Comment sont évaluées les constructions suivantes ... et comprendre le résultat de l'évaluation !
> (atom 1)
> (atom (atom 1))
> (atom '(a b))
> (null ( ))
> (null '(a b))
> (null (atom '(a b)))
3.2 L'égalité

- La fonction eq teste l'égalité de deux atomes

Exercice 5 :
Comment sont évaluées les constructions suivantes ... et comprendre le résultat de l'évaluation !
> (eq 'a 'a)
> (eq 'a 'b)
> 'eq '(a b) '(a b))

- La fonction equal test l'égalite de deux listes
> (equal '(a b) '(a b))
T
3.3 if

Une conditionnelle construite avec if prend la forme suivante : (if  exp_bool  eval_si_vrai  eval_si_faux).

Exercice 6 :
Comment sont évaluées les constructions suivantes ... et comprendre le résultat de l'évaluation !
> (if (eq 'a 'b) 1 2)
> (if (eq 'a 'a) 1 2)
A partir de la construction suivante (cf. cours)
> (if (typed a 'number) (sqrt a) "a n'est pas un nombre")
associer différentes valeurs à a pour pouvoir explorer les deux issues qualitativement différentes.

3.4 cond

Exercice 7 :
A partir de la construction donnée en cours
> (cond
            ((eq p 1) (list 'p '= 1))
            ((eq p 2) (list 'p '= 3))
            (t 50)
  )
associer différentes valeurs à a pour pouvoir explorer les deux issues qualitativement différentes.

4. Abstractions et fonctions

- Basé sur le lambda-calcul, Lisp utilise le symbole lambda pour créer des abstractions
> (lambda(x) (* x x))
#<CLOSURE :LAMBDA (X) (* X X)>
> ((lambda(x) (* x x)) 5)
25
Exercice 8 :
Créer une abstraction qui permet de calculer la norme euclidienne d'un point de coordonnées (x,y). L'appliquer à quelques points particulier.

- Le symbole defun permet de construire des fonctions
> (defun carre (x) (* x x))
CARRE
> (carre 5)
25
Exercice 9 :
Réécrire l'abstraction de l'exercice 8 sous forme de fonction
 
- Définir des variables locales à des fonctions
On peut pour cela utiliser let qui a été décrit précédemment
> (defun carrePi2(x)
                     (let ((pi2 9.86))
                          (* x x pi2)
                     )
   )

5. Exercices de récursion sur les nombres

Exercice 10 : Factorielle
Ecrire deux versions de la fonction factorielle. La première avec un if , la seconde avec un cond
Utilisez la fonction trace sur la fonction factorielle grâce à la construction
> (trace fact)
Relancer des calculs de factorielle pour comprendre ce que fait cette fonction.
Remarque : la fonction trace se désactive avec untrace
> (untrace fact)
Exercice 11 : Fibonacci
La suite de fibonacci est définie par
u(0) = u(1) = 1 et u(n) = u(n-1)+u(n-2)
Ecrire une fonction la réalisant. Utiliser trace pour suivre les appels récursifs de cette fonction.

Exercice 12 : Calcul d'une somme d'entiers
Ecrire une fonction somme calculant la somme de tous les entiers parcourant l'intervalle [n, p].

Exercice 13 : Nombres triangulaires
Un nombre x est appelé triangulaire si il existe un entier n tel que x corresponde à la somme de n premiers entiers. Ecrire une fonction qui permet de savoir si son argument est un nombre triangulaire.