Programmation fonctionelle

 

if 0 {Richard Suchenwirth 2007-03-31 - Tcl permet d'utiliser divers façons de programmation : impérative, fonctionnel, objét-orienté. Je pense que la façon fonctionelle est la plus intéressante, vu du coin mathématique.

Selon Wikipédia, "En informatique, une fonction est un ensemble d'instructions réalisant une certaine tâche. ... Une fonction prend zéro, un ou plusieurs paramètres et renvoie toujours un résultat." D'après cette définition, tous les commandes de Tcl sont fonctions.

"Une fonction en informatique se distingue principalement de la fonction mathématique par le fait qu'en plus de calculer un résultat à partir de paramètres, la fonction informatique peut avoir des effets de bord : par exemple afficher un message à l'écran, jouer un son, ou bien piloter une imprimante. .. Une fonction qui n'a pas d'effets de bord, et qui renvoie systématiquement la même valeur de retour pour les mêmes paramètres, est appelée fonction pure."

En autres mots, fonctions pures sont prédictibles, et réproducibles. Une fonction pure a zéro paramètres est equivalente à une constante. Exemples en Tcl: expr et plusieurs de ses opérateurs, linsert (qui renvoie une liste modifiée, mais ne change pas les valeurs de ses paramètres), llength, etc.

Fonctions impures sont, par exemple, le rand() de expr, ou gets, mais aussi set (car il produit un effect de bord, il change le valeur d'une variable), même chôse avec lappend, incr et beaucoup des autres.

C'était la vue exterieure. Dans le code d'une procedure, on peut aussi trouver parties pures ou impures - l'utilisation des variables, par exemple, qui ont un valeur à un temps, et un autre à autres temps, des sauts (Tcl n'a pas GOTO, mais il y a des sauts en "loops" comme for, foreach, while). L' alternative fonctionelle à l'iteration ("loop") est la récursion. Hélas, la profondite de récursion en Tcl est limité à 300..400 sur Windows, mais pour petits expérimets, ça suffirait.

Il est aussi possible de coder les fonctions en façon pure, en Tcl, et c'est que je veux démonstrer sur cette page. Elle est en fait un fichier Tcl, qu'on peut faire évaluer d'un interpréteur. Pour vérifier que les exemples suivants marchent bien, je commence avec un petit testeur:}

 proc e.g. {cmd -> expected} {
    if [catch {uplevel 1 $cmd} res] {puts $::errorInfo}
    if {$res ne $expected} {puts "$cmd -> $res, expected $expected"}
 }

if 0 {Alors, fonctions en Tcl. Nous les écrivons souvent comme procs:

 proc name params body

Une proc a trois parties : nom, liste des paramètres, "body" (corps de code). Le nom a rien à faire avec le reste - si seulement params et body sont le même, le nom peut être Toto, Satanas, ou quoi - elle faisait la même chose. Le nom est arbitraire. L'effét d'une fonction depend seulement de ses params et body, qu'on peut appeller un "lambda". On peut évaluer (appliquer) un lambda (en pratique, une liste de deux éléments, params et body) sans le nommer (en Tcl 8.5, apply est déjà contenu):}

 proc apply {lambda args} {
    foreach {params body} $lambda break
    if {[llength $params] != [llength $args]} {
        error "bad #args $args, expected $params"
    }
    foreach $params $args {}
    eval $body
 }
 e.g. {apply {{a b} {expr {$a+$b}}} 3 4} -> 7

# On peut mettre le lambda, un valeur pur, à une variable:

 set + {{a b} {expr {$a+$b}}}
 e.g. {apply ${+} 5 6} -> 11

if 0 { Évidemment, c'est moins joli que + 5 6 ou même expr 5+6, mais nous avons isolé le valeur d'une simple fonction, qui consiste de deux parts seulement: params et body. Il est aussi possible définir fonctions sauf params, avec le body seulement, si nous acceptons paramètres nommés comme nombres: $1 étaint le premier paramètre, $2 le deuxième, etc. J'appelle cette façon un "démi-lambda". Voilà comment l'appliquer: }

 proc dl'apply {dlambda args} {
    set i 0
    foreach a $args {set [incr i] $a}
    eval $dlambda
 }
 e.g. {dl'apply {expr {$1*$2}} 7 8} -> 56

if 0 {Fonctions maintenant étant valeurs, comme tous les autres (nombres, chaînes de caractères, listes), on peut les combiner pour recevoir des autres fonctions. Par exemple, le "fold" applique une fonction de deux paramètres successivement à une liste :}

 proc fold {f init liste} {
     foreach el $liste {set init [apply $f $init $el]}
     set init
 }
 e.g. {fold ${+} 0 {1 2 3 4}} -> 10

# On peut bien envelopper ça en un alias:

 interp alias {} sum {} fold ${+} 0
 e.g. {sum {2 3 4 5}} -> 14

if 0 {Autre exemple, la combinaison de fonctions. Si nous écrivons

 f [g $x]

nous applicons 'g' sur le paramètre 'x', et 'f' sur le résultat du premier. La fonction appliquée peut aussi être défini comme

 h = f o g

ou "o" est l'opérateur de combinaison de fonctions. Voyons si c'est possible en Tcl, composant le fonction comme chaîne :}

 proc o {f g} {return "x {apply {$f} \[apply {$g} \$x\]}"}

 set f {x {expr {$x*$x}}}
 set g {x {incr x}}
 e.g. {o $f $g} -> \
    {x {apply {x {expr {$x*$x}}} [apply {x {incr x}} $x]}}
 e.g. {apply [o $f $g] 5} -> 36
 e.g. {apply [o $g $f] 5} -> 26

if 0 {Évidemment, avec un petit ensemble de fonctions impures (apply, fold, o, ...) nous pouvons expérimenter très bien avec des purs lambdas :^)

map: Voilà une autre application classique de FP - appliquer une fonction sur tous éléments d'une liste: }

 proc map {f liste} {
    set res {}
    foreach el $liste {lappend res [apply $f $el]}
    set res
 }
 set double {x {expr {$x*2}}}
 e.g. {map $double {1 2 3 4 5}} -> {2 4 6 8 10}

# Également, on peut appliquer tous fonctions d'une liste à un paramètre:

 proc fmap {fs x} {
    set res {}
    foreach f $fs {lappend res [apply $f $x]}
    set res
 }
 e.g. {fmap [list $f $g] 7} -> {49 8}

if 0 {---- À suivre: filter, style Backus...


Voir aussi http://fr.wikipedia.org/wiki/Programmation_fonctionnelle }