Pointeurs de fonction, fermetures et Lambda

Question

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

Alors, pourquoi les indicateurs de fonction de style C sont-ils fondamentalement différents des fermetures ou des lambdas? Autant que je sache, cela a à voir avec le fait que le pointeur de fonction pointe toujours sur une fonction définie (nommée), par opposition à la pratique consistant à définir anonymement la fonction.

Pourquoi le passage d'une fonction à une fonction est-il considéré comme plus puissant dans le deuxième cas, où elle n'est pas nommée, que dans le premier cas où il s'agit simplement d'une fonction normale, quotidienne, qui est passée?

Dites-moi comment et pourquoi j'ai tort de comparer les deux de si près.

Merci.

Answer 1

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 peut avoir été détruit) continuera à être référencé. Si je modifie lessThan, je modifie 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, cela 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 transmettre ce pointeur de fonction à une autre fonction où lessThan n’était pas dans la portée, je devais soit le maintenir manuellement en vie, en le transmettant à chaque fonction de la chaîne, soit en en faisant la promotion au niveau global.

Bien que la plupart des langages courants prenant en charge les fermetures utilisent des fonctions anonymes, cela n’est pas obligatoire. Vous pouvez avoir des fermetures sans fonction anonyme et des fonctions anonymes sans fermeture.

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

Answer 2

En tant que personne ayant écrit des compilateurs pour les langues avec et sans 'véritables' fermetures, je suis en désaccord avec certaines des réponses ci-dessus. Une fermeture Lisp, Scheme, ML ou Haskell ne crée pas de nouvelle fonction de manière dynamique . Au lieu de cela, il réutilise une fonction existante , mais avec nouvelles variables libres . La collection de variables libres est souvent appelée environnement , du moins par les théoriciens du langage de programmation.

Une fermeture est simplement un agrégat contenant une fonction et un environnement. Dans le compilateur Standard ML du New Jersey, nous en avons représenté un sous forme d’enregistrement; un champ contenait un pointeur sur le code et les autres champs contenaient les valeurs des variables libres. Le compilateur a créé dynamiquement une nouvelle fermeture (non fonctionnelle) en attribuant un nouvel enregistrement contenant un pointeur sur le code identique , mais avec des valeurs différentes pour les variables libres.

Vous pouvez simuler tout cela en C, mais c’est pénible. Deux techniques sont populaires:

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

2. Passez un pointeur sur une structure, laquelle contient les valeurs des variables libres et un pointeur sur le code.

La technique n ° 1 est idéale lorsque vous essayez de simuler une sorte de polymorphisme en C et que vous ne souhaitez pas révéler le type de l'environnement - vous utilisez un pointeur vide * représenter l'environnement. Pour des exemples, consultez les Interfaces et mises en œuvre de Dave Hanson. La technique n ° 2, qui ressemble plus à 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 de membre virtuel. Les implémentations sont presque identiques.

Cette observation a conduit Henry Baker à se plaindre:

  

Les habitants du monde Algol / Fortran se sont plaints pendant des années de ne pas comprendre l’utilisation possible des fermetures de fonctions pour une programmation efficace de l’avenir. Ensuite, la révolution de la "programmation orientée objet" a eu lieu, et maintenant tout le monde programme à l'aide de fonctions de fermeture, sauf qu'il refuse toujours de les appeler ainsi.

Answer 3

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

En termes simples, les pointeurs de fonction ne sont associés à aucune étendue (à moins que vous ne comptiez l'étendue globale), tandis que les fermetures incluent l'étendue de la méthode qui les définit. Avec lambdas, vous pouvez écrire une méthode pour écrire une méthode. Les fermetures vous permettent de lier "certains arguments à une fonction et d'obtenir ainsi une fonction d'arité inférieure." (tiré du commentaire de Thomas). Vous ne pouvez pas faire ça en C.

EDIT: Ajouter un exemple (je vais utiliser la syntaxe Actionscript-ish car c'est ce qui me préoccupe actuellement):

Disons que vous avez une méthode qui prend une autre méthode comme argument, mais ne fournit pas un moyen de lui transmettre des paramètres quand elle est appelée? Par exemple, une méthode qui cause un délai avant de l'exécuter (exemple stupide, mais je veux que cela reste simple).

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

Supposons maintenant que vous souhaitiez que l'utilisateur runLater () retarde 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 transmettez à process () n'est plus une fonction définie de manière statique. Il est généré de manière dynamique et peut inclure des références à des variables qui étaient dans la portée lors de la définition de la méthode. Donc, 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.

Answer 4

Fermeture = logique + environnement.

Par exemple, considérons 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 ("compare le nom") mais également l’environnement, y compris le paramètre (variable locale) "nom".

Pour plus d'informations à ce sujet, consultez mon article sur les fermetures qui vous emmène C 1, 2 et 3 en montrant comment les fermetures facilitent les choses.

Answer 5

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

Quel type d'objet est un pointeur sur une fonction imbriquée? Il ne peut pas s'agir simplement de l'adresse du code, car si vous l'appelez, comment accède-t-il aux variables de la fonction externe? (N'oubliez pas qu'en raison de la récursivité, il peut y avoir plusieurs appels de la fonction externe actifs en même temps.) C'est ce qu'on appelle le problème de funarg et deux sous-problèmes: le problème de funargs à la baisse et le problème de funargs à la hausse.

Le problème de la difficulté descendante, c'est-à-dire l'envoi d'un pointeur de fonction "dans la pile" En tant qu'argument d'une fonction que vous appelez, elle n'est en fait pas incompatible avec C et GCC prend en charge les fonctions imbriquées sous forme de fonctions descendantes. Dans GCC, lorsque vous créez un pointeur sur une fonction imbriquée, vous obtenez réellement un pointeur sur un trampoline , un morceau de code construit de manière dynamique qui configure le pointeur de lien statique puis appelle la fonction réelle, qui utilise le pointeur de lien statique pour accéder aux variables de la fonction extérieure.

Le problème de la hausse des coûts 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 (il n'y a pas d'enregistrement sur la pile d'appels), le pointeur de lien statique pourrait alors pointer vers un garbage. Les enregistrements d'activation ne peuvent plus être alloués sur une pile. La solution habituelle consiste à les allouer sur le tas et à laisser un objet fonction représentant une fonction imbriquée simplement pointer sur l'enregistrement d'activation de la fonction externe. Un tel objet s'appelle une fermeture . Ensuite, la langue devra généralement prendre en charge la garbage collection afin que les enregistrements puissent être conservés. libéré une fois qu'il n'y a plus de pointeurs pointant vers eux.

Lambdas ( fonctions anonymes ) constituent en réalité un problème distinct, mais généralement un langage qui permet: si vous définissez des fonctions anonymes à la volée, vous pourrez également les renvoyer en tant que valeurs de fonction, afin qu’elles deviennent des fermetures.

Answer 6

Un lambda est une fonction anonyme, définie dynamiquement . Vous ne pouvez tout simplement pas faire cela en C ... en ce qui concerne les fermetures (ou la combinaison des deux), l’exemple typique de lisp ressemblerait à quelque chose comme:

(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 langage C, vous pouvez dire que l'environnement lexical (la pile) de get-counter est 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]> 

Answer 7

Les fermetures impliquent qu'une variable du point de vue de la définition de la fonction est liée à la logique de la fonction, comme pouvoir 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 à la sortie de la portée actuelle, que la fermeture les indique ou non. Cela conduirait au type de bugs que les gens rencontrent 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 comptés en références, soit des éléments collectés dans un déchet sur un tas.

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

Answer 8

Dans GCC, il est possible de simuler des fonctions lambda à l’aide de 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 tiré de la 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 élimine bien entendu la possibilité que votre application fonctionne avec d'autres compilateurs et est apparemment "non défini". comportement si YMMV.

Answer 9

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

Un exemple dans Common Lisp, où MAKE-ADDER renvoie 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 fonction DESCRIBE indique que les objets de fonction pour les deux fermetures sont identiques, mais que l'environnement est différent.

Common Lisp transforme les fonctions en objets à la fois pur et fonctionnels (ceux sans environnement) et on peut les appeler de la même manière, en utilisant FUNCALL .

Answer 10

La principale différence provient de l’absence de portée lexicale dans C.

Un pointeur de fonction est simplement un pointeur sur un bloc de code. Toute variable non pile qu'elle référence est globale, statique ou similaire.

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

Quelques fermetures peuvent partager certaines variables, de même que l'interface d'un objet (au sens de la POO). pour faire cela en C, vous devez associer une structure à une table de pointeurs de fonctions (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

Answer 11

La plupart des réponses indiquent que les fermetures nécessitent des pointeurs de fonction, éventuellement vers des fonctions anonymes, mais sous la forme Les marques marquées 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 variable $ count . Il n'est disponible que pour le sous-programme increment et persiste entre les appels.

Answer 12

En C, un pointeur de fonction est un pointeur qui invoquera 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 ils sont liés) et auxquels lambda fait généralement référence. une valeur qui est en fait une fonction non nommée. En C, une fonction n’est pas une valeur de première classe et ne peut donc pas être transmise. Vous devez donc lui passer un pointeur. Toutefois, dans les langages fonctionnels (comme Scheme), vous pouvez transmettre des fonctions de la même manière que vous transmettez une autre valeur