TD/TP n°2 : Function, argument, binding and trapeze

On donnera quelques compléments sur les notions de bases, ainsi que sur les arguments de fonctions. On expliquera comment gérer une fonction comme argument d'une autre fonction, avec un exemple d'application à la méthode des trapèzes. On finira sur les notions de liaisons statiques et dynamiques.

1. Quelques compléments de les notions de base de Lisp

1.1 Compléments sur la fonction let (cf. 2.3 du TD/TP n°1) :
La fonction let* est semblable à la fonction let à la différence qu'elle permet de faire des initialisations de variables dépendantes des précédentes, comme cela sera vérifié dans l'exercice suivant :

Exercice 1 :
Evaluer les expressions suivantes et en comprendre la valeur de retour
> (setq a 4)
> (let   ((a 3) (b (+ a  4))) (list a b))
> (let* ((a 3) (b (+ a  4))) (list a b))
1.2 Bloc d'instructions
La fonction progn permet de définir une séquence d'instructions qui seront évaluées. La valeur retournée est celle de la dernière expression (cf. cours).

Exercice 2 :
Ecrire un programme qui associe successivement des valeurs que vous choisirez arbitrairement, à 4 variables et en retourne la moyenne.

1.3 Prédicats complémentaires Exercice 3 :
Faire deux constructions renvoyant des valeurs différentes avec chacun des prédicats précédents.

2. Quelques compléments sur les arguments des fonctions

(d'après le Traité de programmation en Common Lisp de R. Strandh et I. Durand)

2.1 Arguments optionnels

Une fonction peut posséder des arguments optionnels qui se trouvent toujours après les arguments requis. Ces arguments sont précédés de &optional. Lors de l'appel de la fonction, s'ils ne sont pas donnés, ils prennent la valeur nil.
> (defun f (a b &optional c d) (list a b c d))
> (f 1 2)
(1 2 NIL NIL)
> (f 1 2 3)
(1 2 3 NIL)
> (f 1 2 3 4)
(1 2 3 4)
Il est possible de préciser une valeur par défaut d'un argument optionel. On remplace son symbole par une liste de 2 éléments : son symbole et  sa valeur par défaut qui lui sera attribuée si l'argument n'est pas fourni à l'appel de la fonction.
> (defun f (a b &optional (c 1) (d 1)) (list a b c d))
> (f 'a 'b 'c)
(a b c 1)
Exercice 4 :
Trouvez une solution à l'exercice 13 de la feuille de TD/TP n°1 (recherche de nombres triangulaires) qui n'utilise qu'une seule fonction avec un argument optionnel.

2.2 Arguments restes
A la fin des arguments, il est possible d'ajouter un unique paramètre précédé par le symbole &rest. Dans ce cas, la fonction peut être appelée avec un nombre d'arguments supérieurs ou égal aux nombres d'arguments requis et facultatifs. Les arguments supplémentaires constituent alors une liste qui correspond à la valeur de l'argument reste.
> (defun f (a b &optional (c 1) (d 1) &rest e) (list a b c d e))
> (f 1 2 3 4)
(1 2 3 4 NIL)
> (f 1 2 3 4 5 6 7)
(1 2 3 4 (5 6 7))
2.3 Arguments mot-clés

Certains arguments peuvent être du type mot-clé. Dans la construction de la fonction, ils apparaissent après le symbole &key, qui se trouve en fin de la liste d'arguments, après &optional et &rest. Pour invoquer une fonction avec un argument mot-clé, il faut passer 2 arguments : le symbole du paramètre utilisé dans la construction de la fonction, en le faisant précédé de ":" et la valeur à associer à cet argument. Si l'argument n'est pas évoqué lors de l'appel de la fonction, il prend la valeur nil ou encore une valeur par défaut qui suit le nom du paramètre dans la construction de la fonction (cf. l'exemple suivant).
> (defun f (a b &key c d) (list a b c d))
>(f 1 2 :d 5)
(1 2 NIL 5)
> (defun f (a b &key (c '(a b)) d) (list a b c d))
> (f 1 2 :d 1)
(1 2 (a b) 1)
> (f 1 2 :c 3)
(1 2 3 NIL)
2.4 Fonctions locales

Les opérateurs flet et labels permettent de définir des fonctions locales à une expression donnée, comme le fait let pour établir des liaisons locales (cf. 2.3 du TD/TP n°1). Pour plus de précisions, on pourra consulter la page Définitions de fonctions locales du Traité de programmation en Common Lisp de R. Strandh et I. Durand.

2.5 Passer une fonction en argument et l'appeler

Comme cela a été vu en cours, la notion d'environnement est essentielle pour le système d'évaluation de l'interpréteur Lisp. L'environnement décrit les liaisons déjà définies et manipule ainsi un espace de noms de variables :
        Env = {(var1-val1), (var2-val2), ...}
En fait, le Common Lisp manipule 2 espaces de noms différents : l'espace des noms de variables et l'espace des noms de fonctions.

Il est essentiel de pouvoir utiliser des fonctions pour paramètrer le comportement d'autres fonctions. Rappelez-vous comment était conçue la bibliothèque graphique Java (UP) que vous avez utilisez au premier semestre en analyse numérique : la fonction à tracer est passée en paramètre à l'objet qui en gère l'affichage. Pour ce faire, en Java, on doit utiliser un processus assez complexe : définir une interface pour récupérer une méthode de calcul d'une fonction, puis définir une classe spécifique ou encore une classe interne pour représenter chaque fonction à tracer.

L'approche plus synthétique du Lisp va permettre de faire transiter des fonctions comme simple argument d'autres fonctions. En Scheme, il ne vous reste plus qu'à utiliser directement le nom de l'argument comme une fonction. Vous trouverez dans le livre  Structure and interpretation of computer programs de Harold Abelson, Gerald Jay and Julie Sussman, au chapitre 1.3 Formulating Abstractions with Higher-Order Procedures , une illustration de cette construction en Scheme.

En Common Lisp, le processus est légèrement moins direct à cause des différents espaces de noms, pour les variables d'une part et les fonctions de l'autre. Il est nécessaire de "traverser" ces espaces de noms.

Pour passer de l'espace des noms de fonctions à celui des noms de variables, on utilise l'opérateur function : (function f). Cet opérateur accepte un  seul argument, le nom de la fonction. La valeur de l'expression est la fonction. Pour simplifier l'utilisation de cette opérateur, la construction suivante est synonyme : #' f. Pour invoquer la fonction dans une construction, on peut alors utiliser :
- apply qui possède 2 arguments, la fonction appelée par #' et la liste des arguments ;
- funcall où les arguments de la fonction appelée, suivent directement la nom de la fonction.

Exercice 5 :
Evaluer les expressions suivantes et en comprendre la valeur de retour
> (defun carre (x) (* x x))
> (function carre)
> #' carre
> (apply #' carre '(2))
> (funcall #' carre 2)
Lorsqu'une fonction f a été transmise en argument dans le corps d'une autre fonction g, son nom se trouve alors lié dans l'espace des noms de variables. On ne peut pas alors, contrairement à Scheme, utiliser directement son  nom comme on manipulerait un nom de fonctions. Il faut passer de l'espace des noms de variables à l'espace des noms de fonctions. Pour cela, il suffit de faire précédé le nom de la fonction par funcall qui assure cette transition entre les espaces de noms (cf. exemple suivant).
> (defun doublef (f x) (* 2 (funcall f x)))
> (doublef #'carre 3)
> (doublef 'carre 3)
Exercice 6 : méthode des trapèzes
On veut ecrire une fonction qui calcule I : l'intégrale d'une fonction réelle f sur un intervalle réel [a, b], en utilisant la méthode des trapèzes (vu en cours d'analyse numérique du 1er semestre).

Dans cette méthode on subdivise l'intervalle [a,b] en n sous-intervalles, de même largeur h = (b-a)/n. On note xi= a+i*h.

Par linéarité de l'intégrale, on  sait que I correspond à la somme des intégrales de f sur chaque sous-intervalle de [a,b]. Soit [x0, x1] un de ces sous-intervalles, on approche l'intégrale de f sur cet intervalle par l'aire du trapèze reliant les points (x0, 0), (xO, f(x0)), (x1, f(x1)) et (x1,0). Cette aire vaut h*(f(x0)+f(x1))/2.

L'intégrale I s'obtient donc en sommant ces n aires : h* ((f(a)+f(b))/2 + f(x1) + f(x2) + ... + f(x{n-1})).

Ecrire une fonction int_trap qui calcule l'intégrale d'une fonction f arbitraire, sur l'intervalle [a, b] en utilisant n subdivisions.

3 Liaisons statiques ou dynamiques : special

Les liaisons variable-valeur sont définis dans l'environnement. Il existe deux types de liaisons : les liaisons lexicales et les liaisons dynamiques (cf. cours).

Une liaison lexicale correspond à une variable dont la portée est limitée au texte (ou portion de code) où elle est définie.

Une laison dynamique correspond à une variable dont la portée n'est pas limitée à la portion de code où elle est définie, mais elle s'étend à l'environnement d'exécution : on peut notamment y accéder dans les sous-fonctions.

En Common Lisp, par défaut toute liaison de variable est lexicale. On peut rendre une laison dynamique en utilisant la construction :
(declare (special nom_variable)).

Exercice 7 :
Evaluer les constructions suivantes et en comprendre les affichages des résultats.
> (defun francs_en_euros (x) (acces_x)  (/ x 6.55957))
> (defun acces_x () (print x)))
> (francs_en_euros 100)
> (defun francs_en_euros2 (x) (declare (special x)) (acces_x) (/ x 6.55957))
> (francs_en_euros2 100)
Exercice 8 :
Reprendre l'exemple donné en cours :
> (defun foo (x) (list x y))
> (defun bar (y) (foo 1991))
> (setq y 0)
> (list (bar 100) (foo 3))
Evaluer ces constructions, puis proposer les modifications qui permettent d'obtenir les résultats donnés dans le cours, dans le cas d'une liaison dynamique.