Les fonctionnelles

La forme lambda : rappel et utilisation

(lambda (<p1> <p2> ... <pn>) <e>)

• Nommage de $\lambda$-expressions : (define f (lambda (x y) (+ (* 10 x) y)))
• Application de $\lambda$-expressions : mise en position fonctionnelle, stratégie applicative (par valeur)
• Passage de $\lambda$-expressions en paramètres : juxtaposition
• $\lambda$-expressions en retour de fonction : imbrication

Juxtaposition

On appelle rédex un terme de la forme $(\lambda x.u) v$. On définit alors la bêta-réduction :

$$(\lambda x.u) v \rightarrow u[x:=v]$$

• Soit le terme $(\lambda x.xy)(\lambda x.ux)$ : on a la suite de réductions suivante : $(\lambda x.xy)(\lambda x.ux) \rightarrow (xy)[x:=\lambda x.ux] = (\lambda x.ux)y \rightarrow (ux)[x:=y] = uy$

• Soit $(\lambda f.f0)(\lambda x.(* 2 x))$ : on a la suite de réductions suivante : $(f0)[f:=\lambda x.(* 2 x)] = (\lambda x .(* 2 x)) 0 \rightarrow (* 2 x)[x:=0] = (* 2 0) \rightarrow 0$

• En Scheme, pour ((lambda (f) (f 0)) (lambda (x) (* 2 x))), on a la suite de réductions suivante :

  ((lambda (x) (* 2 x)) 0) ; -> (* 2 0) -> 0

Imbrication

• Soit $(\lambda x.\lambda y.xy)f$ : on a $(\lambda y.xy)[x:=f] = \lambda y.fy$
• Soit $((\lambda x.\lambda y.xy)f)z$ : on a $((\lambda y.xy)[x:=f])z = (\lambda y.fy) z \rightarrow (fy)[y:=z] = fz$

Itération : la forme map

La forme map prend une fonction f et $n$ listes en arguments ($n>0$), où $n$ est l'arité de la fonction f. Soient l1 = (a1 a2 ... ak) et l2 = (b1 b2 ... bk) :

• cas d'une fonction unaire : (map f l1) renvoie ((f a1) (f a2) ... (f ak)) ;
• cas d'une fonction $n$-aire : (map f l1 l2 ...) renvoie ((f a1 b1 ...) (f a2 b2 ...) ... (f ak bk ...)).

Forme andmap

Cette forme a la même signature que la forme map. Elle applique la fonction aux éléments de la liste dans l'ordre. Elle s'arrête et renvoie #f au premier résultat faux ; sinon, le résultat est celui de la dernière application (pas de mise en liste).

Forme ormap

Comme la forme andmap, mais elle renvoie le premier résultat vrai (différent de #f), et #f si aucun résultat n'est vrai.

Itérations générales : formes foldl et foldr

Comme la forme map, les formes fold appliquent une fonction aux éléments d'une ou plusieurs listes. Alors que map rassemble les résultats obtenus dans une liste, les formes fold les combinent d'une façon déterminée par leur paramètre fonctionnel f. Elles appliquent f aux éléments des listes de gauche à droite (foldl) ou de droite à gauche (foldr). L'argument init est utilisé pour terminer la combinaison récursive du résultat.

Application : la forme apply

Cette fonction réalise l'application d'une fonction à une liste d'arguments. Ce mécanisme est utile pour l'écriture de fonctions à nombre d'arguments variable.

(apply <f> <l>) = (<f> <e1> <e2> ... <en>)

avec <l> = (<e1> <e2> ... <en>).

Fonctions en retour de fonctions

Curryfication

La fonction curry curryfie son argument. Soit une fonction $f : A \times B \rightarrow C$ ; la curryfication lui associe la fonction $f^c : A \rightarrow (B \rightarrow C)$, qui a pour résultat une fonction allant de $B$ dans $C$ et telle que $\forall x \in A, \forall y \in B, f(x,y) = (f^c(x))(y)$.

Notion de fermeture

• L'environnement lexical d'une fonction est l'environnement dans lequel elle est définie
• Une fermeture est la représentation d'une fonction sous forme d'un couple associant l'environnement lexical et le code de la fonction
• En Scheme, les fonctions sont représentées par des fermetures pour conserver leur environnement de définition contenant des références éventuelles (ce n'est pas le cas, par exemple, d'Emacs Lisp en portée dynamique)
• Les fermetures peuvent être utilisées pour représenter des états, par modification de l'environnement