Pointeurs de fonction, fermetures et Lambda

Je viens juste d'apprendre les pointeurs de fonction et, alors que je lisais le chapitre K&R sur le sujet, la première chose qui m'a frappé a été: "Hé, c'est un peu comme une fermeture." Je savais que cette hypothèse est fondamentalement erronée et après une recherche en ligne, je n'ai trouvé aucune analyse de cette comparaison.

Alors, pourquoi les pointeurs de fonction de style C sont-ils fondamentalement différents des fermetures ou des lambdas? Pour autant que je sache, cela a à voir avec le fait que le pointeur de fonction pointe toujours vers une fonction définie (nommée) par opposition à la pratique de définir la fonction de manière anonyme.

Pourquoi le passage d'une fonction à une fonction est-il considéré comme plus puissant dans le second cas, où elle n'est pas nommée, que dans le premier où c'est juste une fonction normale et quotidienne qui est transmise?

Veuillez me dire comment et pourquoi j'ai tort de comparer les deux de si près.

Merci.

Un lambda (ou fermeture ) encapsule à la fois le pointeur de fonction et les variables. C'est pourquoi, en C #, vous pouvez faire:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

J'y ai utilisé un délégué anonyme comme fermeture (sa syntaxe est un peu plus claire et plus proche de C que l'équivalent lambda), qui a capturé lessThan (une variable de pile) dans la fermeture. Lorsque la fermeture est évaluée, lessThan (dont le cadre de pile a peut-être été détruit) continuera à être référencé. Si je change moins que, alors je change la comparaison:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

lessThanTest(99); // returns true
lessThan = 10;
lessThanTest(99); // returns false

En C, ce serait illégal:

BOOL (*lessThanTest)(int);
int lessThan = 100;

lessThanTest = &LessThan;

BOOL LessThan(int i) {
   return i < lessThan; // compile error - lessThan is not in scope
}

bien que je puisse définir un pointeur de fonction qui prend 2 arguments:

int lessThan = 100;
BOOL (*lessThanTest)(int, int);

lessThanTest = &LessThan;
lessThanTest(99, lessThan); // returns true
lessThan = 10;
lessThanTest(100, lessThan); // returns false

BOOL LessThan(int i, int lessThan) {
   return i < lessThan;
}

Mais, maintenant, je dois passer les 2 arguments lorsque je l'évalue. Si je souhaitais passer ce pointeur de fonction à une autre fonction où lessThan n'était pas dans la portée, je devrais soit le maintenir manuellement en vie en le passant à chaque fonction de la chaîne, soit en le promouvant dans un global.

Bien que la plupart des langages traditionnels qui prennent en charge les fermetures utilisent des fonctions anonymes, cela n'est pas obligatoire. Vous pouvez avoir des fermetures sans fonctions anonymes et des fonctions anonymes sans fermetures.

Résumé: une fermeture est une combinaison de pointeur de fonction + variables capturées.

En tant que personne ayant écrit des compilateurs pour les langues avec et sans fermetures «réelles», je ne suis respectueusement pas d'accord avec certaines des réponses ci-dessus. Une fermeture Lisp, Scheme, ML ou Haskell ne crée pas de nouvelle fonction dynamiquement . Au lieu de cela, il réutilise une fonction existante mais le fait avec de nouvelles variables libres . La collection de variables libres est souvent appelée l' environnement , du moins par les théoriciens du langage de programmation.

Une fermeture est juste un agrégat contenant une fonction et un environnement. Dans le compilateur Standard ML du New Jersey, nous en avons représenté un comme un enregistrement; un champ contenait un pointeur vers le code et les autres champs contenaient les valeurs des variables libres. Le compilateur a créé une nouvelle fermeture (pas une fonction) dynamiquement en allouant un nouvel enregistrement contenant un pointeur vers le même code, mais avec des valeurs différentes pour les variables libres.

Vous pouvez simuler tout cela en C, mais c'est une douleur dans le cul. Deux techniques sont populaires:

1. Passez un pointeur vers la fonction (le code) et un pointeur séparé vers les variables libres, de sorte que la fermeture soit divisée en deux variables C.

2. Passez un pointeur vers une structure, où la structure contient les valeurs des variables libres et également un pointeur vers le code.

La technique n ° 1 est idéale lorsque vous essayez de simuler une sorte de polymorphisme en C et que vous ne voulez pas révéler le type d'environnement - vous utilisez un pointeur void * pour représenter l'environnement. Pour des exemples, regardez les interfaces et implémentations C de Dave Hanson . La technique n ° 2, qui ressemble plus étroitement à ce qui se passe dans les compilateurs de code natif pour les langages fonctionnels, ressemble également à une autre technique familière ... les objets C ++ avec des fonctions membres virtuelles. Les implémentations sont presque identiques.

Cette observation a conduit à un sage de Henry Baker:

Les gens dans le monde d'Algol / Fortran se sont plaints pendant des années de ne pas comprendre ce que les fermetures de fonctions d'utilisation possibles auraient dans la programmation efficace de l'avenir. Puis la révolution de la «programmation orientée objet» s'est produite, et maintenant tout le monde programme en utilisant des fermetures de fonction, sauf qu'ils refusent toujours de les appeler ainsi.

En C, vous ne pouvez pas définir la fonction en ligne, vous ne pouvez donc pas vraiment créer une fermeture. Tout ce que vous faites est de transmettre une référence à une méthode prédéfinie. Dans les langages qui prennent en charge les méthodes / fermetures anonymes, la définition des méthodes est beaucoup plus flexible.

Dans les termes les plus simples, les pointeurs de fonction n'ont aucune portée qui leur est associée (sauf si vous comptez la portée globale), tandis que les fermetures incluent la portée de la méthode qui les définit. Avec lambdas, vous pouvez écrire une méthode qui écrit une méthode. Les fermetures vous permettent de lier "certains arguments à une fonction et d'obtenir une fonction d'arité inférieure en conséquence". (tiré du commentaire de Thomas). Vous ne pouvez pas faire cela en C.

EDIT: Ajout d'un exemple (je vais utiliser la syntaxe Actionscript-ish car c'est ce que je pense en ce moment):

Supposons que vous ayez une méthode qui prend une autre méthode comme argument, mais qui ne fournit pas un moyen de passer des paramètres à cette méthode lorsqu'elle est appelée? Comme, par exemple, une méthode qui provoque un délai avant d'exécuter la méthode que vous lui avez transmise (exemple stupide, mais je veux rester simple).

function runLater(f:Function):Void {
  sleep(100);
  f();
}

Supposons maintenant que vous souhaitiez utiliser runLater () pour retarder le traitement d'un objet:

function objectProcessor(o:Object):Void {
  /* Do something cool with the object! */
}

function process(o:Object):Void {
  runLater(function() { objectProcessor(o); });
}

La fonction que vous passez à process () n'est plus une fonction définie de manière statique. Il est généré dynamiquement et peut inclure des références à des variables qui étaient dans la portée lorsque la méthode a été définie. Ainsi, il peut accéder à 'o' et 'objectProcessor', même si ceux-ci ne sont pas dans la portée globale.

J'espère que cela a du sens.

Fermeture = logique + environnement.

Par exemple, considérez cette méthode C # 3:

public Person FindPerson(IEnumerable<Person> people, string name)
{
    return people.Where(person => person.Name == name);
}

L'expression lambda encapsule non seulement la logique («comparer le nom») mais aussi l'environnement, y compris le paramètre (c'est-à-dire la variable locale) «nom».

Pour en savoir plus, consultez mon article sur les fermetures qui vous guide à travers C # 1, 2 et 3, montrant comment les fermetures facilitent les choses.

En C, les pointeurs de fonction peuvent être passés en tant qu'arguments aux fonctions et renvoyés en tant que valeurs des fonctions, mais les fonctions n'existent qu'au niveau supérieur: vous ne pouvez pas imbriquer les définitions de fonction les unes dans les autres. Pensez à ce qu'il faudrait pour que C prenne en charge les fonctions imbriquées qui peuvent accéder aux variables de la fonction externe, tout en étant capable d'envoyer des pointeurs de fonction de haut en bas dans la pile d'appels. (Pour suivre cette explication, vous devez connaître les bases de l'implémentation des appels de fonction en C et dans la plupart des langages similaires: parcourez l' entrée de la pile d'appels sur Wikipedia.)

Quel type d'objet est un pointeur vers une fonction imbriquée? Ce ne peut pas être simplement l'adresse du code, car si vous l'appelez, comment accède-t-il aux variables de la fonction externe? (Rappelez-vous qu'en raison de la récursivité, il peut y avoir plusieurs appels différents de la fonction externe active en même temps.) C'est ce qu'on appelle le problème funarg , et il y a deux sous-problèmes: le problème funargs descendant et le problème funargs ascendant.

Le problème des funargs vers le bas, c'est-à-dire l'envoi d'un pointeur de fonction "vers le bas de la pile" comme argument à une fonction que vous appelez, n'est en fait pas incompatible avec C, et GCC supporte les fonctions imbriquées comme funargs vers le bas. Dans GCC, lorsque vous créez un pointeur vers une fonction imbriquée, vous obtenez vraiment un pointeur vers un trampoline , un morceau de code construit dynamiquement qui configure le pointeur de lien statique , puis appelle la fonction réelle, qui utilise le pointeur de lien statique pour accéder les variables de la fonction externe.

Le problème des funargs ascendants est plus difficile. GCC ne vous empêche pas de laisser un pointeur de trampoline exister une fois que la fonction externe n'est plus active (n'a pas d'enregistrement sur la pile d'appels), puis le pointeur de lien statique pourrait pointer vers des déchets. Les enregistrements d'activation ne peuvent plus être alloués sur une pile. La solution habituelle est de les allouer sur le tas, et de laisser un objet fonction représentant une fonction imbriquée pointer simplement vers l'enregistrement d'activation de la fonction externe. Un tel objet s'appelle une fermeture . Ensuite, le langage devra généralement prendre en charge le garbage collection afin que les enregistrements puissent être libérés une fois qu'il n'y a plus de pointeurs pointant vers eux.

Les lambdas ( fonctions anonymes ) sont vraiment un problème distinct, mais généralement un langage qui vous permet de définir des fonctions anonymes à la volée vous permettra également de les renvoyer en tant que valeurs de fonction, de sorte qu'elles finissent par être des fermetures.

Un lambda est une fonction anonyme définie dynamiquement . Vous ne pouvez tout simplement pas faire cela en C ... quant aux fermetures (ou à la convination des deux), l'exemple typique de lisp ressemblerait à quelque chose du genre:

(defun get-counter (n-start +-number)
     "Returns a function that returns a number incremented
      by +-number every time it is called"
    (lambda () (setf n-start (+ +-number n-start))))

En termes C, vous pourriez dire que l'environnement lexical (la pile) de get-counterest capturé par la fonction anonyme et modifié en interne comme le montre l'exemple suivant:

[1]> (defun get-counter (n-start +-number)
         "Returns a function that returns a number incremented
          by +-number every time it is called"
        (lambda () (setf n-start (+ +-number n-start))))
GET-COUNTER
[2]> (defvar x (get-counter 2 3))
X
[3]> (funcall x)
5
[4]> (funcall x)
8
[5]> (funcall x)
11
[6]> (funcall x)
14
[7]> (funcall x)
17
[8]> (funcall x)
20
[9]> 

Les fermetures impliquent qu'une variable à partir du point de définition de la fonction est liée à la logique de la fonction, comme la possibilité de déclarer un mini-objet à la volée.

Un problème important avec C et les fermetures est que les variables allouées sur la pile seront détruites en quittant la portée actuelle, peu importe si une fermeture les pointait. Cela conduirait au genre de bogues que les gens obtiennent lorsqu'ils renvoient négligemment des pointeurs vers des variables locales. Les fermetures impliquent fondamentalement que toutes les variables pertinentes sont soit des éléments ref-countés, soit des éléments récupérés sur un tas.

Je ne suis pas à l'aise d'assimiler lambda à la fermeture parce que je ne suis pas sûr que les lambdas dans toutes les langues soient des fermetures, parfois je pense que les lambdas viennent d'être des fonctions anonymes définies localement sans liaison de variables (Python pré 2.1?).

Dans GCC, il est possible de simuler des fonctions lambda en utilisant la macro suivante:

#define lambda(l_ret_type, l_arguments, l_body)       \
({                                                    \
    l_ret_type l_anonymous_functions_name l_arguments \
    l_body                                            \
    &l_anonymous_functions_name;                      \
})

Exemple de source :

qsort (array, sizeof (array) / sizeof (array[0]), sizeof (array[0]),
     lambda (int, (const void *a, const void *b),
             {
               dump ();
               printf ("Comparison %d: %d and %d\n",
                       ++ comparison, *(const int *) a, *(const int *) b);
               return *(const int *) a - *(const int *) b;
             }));

L'utilisation de cette technique supprime bien sûr la possibilité que votre application travaille avec d'autres compilateurs et est apparemment un comportement "indéfini" donc YMMV.

La fermeture capture les variables libres dans un environnement . L'environnement existera toujours, même si le code environnant n'est peut-être plus actif.

Un exemple en Common Lisp, où MAKE-ADDERrenvoie une nouvelle fermeture.

CL-USER 53 > (defun make-adder (start delta) (lambda () (incf start delta)))
MAKE-ADDER

CL-USER 54 > (compile *)
MAKE-ADDER
NIL
NIL

Utilisation de la fonction ci-dessus:

CL-USER 55 > (let ((adder1 (make-adder 0 10))
                   (adder2 (make-adder 17 20)))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder1))
               (print (funcall adder1))
               (describe adder1)
               (describe adder2)
               (values))

10 
20 
30 
40 
37 
57 
77 
50 
60 
#<Closure 1 subfunction of MAKE-ADDER 4060001ED4> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(60 10)
#<Closure 1 subfunction of MAKE-ADDER 4060001EFC> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(77 20)

Notez que la DESCRIBEfonction montre que les objets de fonction pour les deux fermetures sont les mêmes, mais l' environnement est différent.

Common Lisp fait à la fois des fermetures et des objets de fonction pure (ceux sans environnement) à la fois des fonctions et on peut appeler les deux de la même manière, ici en utilisant FUNCALL.

La principale différence provient du manque de portée lexicale chez C.

Un pointeur de fonction est juste cela, un pointeur vers un bloc de code. Toute variable non-pile à laquelle elle fait référence est globale, statique ou similaire.

Une fermeture, OTOH, a son propre état sous la forme de «variables externes», ou «upvalues». ils peuvent être aussi privés ou partagés que vous le souhaitez, en utilisant une portée lexicale. Vous pouvez créer de nombreuses fermetures avec le même code de fonction, mais des instances de variables différentes.

Quelques fermetures peuvent partager certaines variables, et peuvent donc être l'interface d'un objet (au sens POO). pour faire cela en C, vous devez associer une structure à une table de pointeurs de fonction (c'est ce que fait C ++, avec une classe vtable).

en bref, une fermeture est un pointeur de fonction PLUS un état. c'est une construction de niveau supérieur

La plupart des réponses indiquent que les fermetures nécessitent des pointeurs de fonction, éventuellement vers des fonctions anonymes, mais comme Mark l'a écrit, des fermetures peuvent exister avec des fonctions nommées. Voici un exemple en Perl:

{
    my $count;
    sub increment { return $count++ }
}

La fermeture est l'environnement qui définit la $countvariable. Il n'est disponible que pour le incrementsous - programme et persiste entre les appels.

En C, un pointeur de fonction est un pointeur qui appellera une fonction lorsque vous la déréférencerez, une fermeture est une valeur qui contient la logique d'une fonction et l'environnement (les variables et les valeurs auxquelles elles sont liées) et un lambda fait généralement référence à une valeur qui est en fait une fonction sans nom. En C, une fonction n'est pas une valeur de première classe, elle ne peut donc pas être transmise, vous devez donc lui passer un pointeur à la place, mais dans les langages fonctionnels (comme Scheme), vous pouvez passer des fonctions de la même manière que vous transmettez toute autre valeur