Pourquoi concevoir un langage avec des types anonymes uniques?

C'est quelque chose qui m'a toujours dérangé en tant que fonctionnalité des expressions lambda C ++: le type d'une expression lambda C ++ est unique et anonyme, je ne peux tout simplement pas l'écrire. Même si je crée deux lambdas dont la syntaxe est exactement la même, les types résultants sont définis pour être distincts. La conséquence est que a) les lambdas ne peuvent être passées qu'aux fonctions de modèle qui permettent au moment de la compilation, le type indescriptible d'être passé avec l'objet, et b) que les lambdas ne sont utiles qu'une fois qu'ils sont effacés via std::function<>.

Ok, mais c'est juste la façon dont C ++ le fait, j'étais prêt à l'écrire comme une simple fonctionnalité ennuyeuse de ce langage. Cependant, je viens d'apprendre que Rust fait apparemment la même chose: chaque fonction Rust ou lambda a un type unique et anonyme. Et maintenant je me demande: pourquoi?

Donc, ma question est la suivante:
quel est l'avantage, du point de vue d'un concepteur de langage, d'introduire le concept d'un type unique et anonyme dans une langue?

De nombreuses normes (en particulier C ++) adoptent une approche consistant à minimiser ce qu'elles demandent aux compilateurs. Franchement, ils en demandent déjà assez! S'ils n'ont pas à spécifier quelque chose pour que cela fonctionne, ils ont tendance à laisser l'implémentation définie.

Si les lambdas n'étaient pas anonymes, il faudrait les définir. Cela aurait à dire beaucoup sur la façon dont les variables sont capturées. Prenons le cas d'un lambda [=](){...}. Le type devrait spécifier les types réellement capturés par le lambda, ce qui pourrait être non trivial à déterminer. De plus, que se passe-t-il si le compilateur optimise avec succès une variable? Considérer:

static const int i = 5;
auto f = [i]() { return i; }

Un compilateur optimisant pourrait facilement reconnaître que la seule valeur possible de iqui pourrait être capturée est 5 et le remplacer par auto f = []() { return 5; }. Cependant, si le type n'est pas anonyme, cela pourrait changer le type ou forcer le compilateur à moins optimiser, en stockant imême s'il n'en avait pas réellement besoin. C'est tout un sac de complexité et de nuance qui n'est tout simplement pas nécessaire pour ce que les lambdas étaient censés faire.

Et, dans le cas où vous auriez réellement besoin d'un type non anonyme, vous pouvez toujours construire vous-même la classe de fermeture et travailler avec un foncteur plutôt qu'une fonction lambda. Ainsi, ils peuvent faire en sorte que les lambdas gèrent le cas de 99% et vous laissent coder votre propre solution dans le 1%.

Deduplicator a souligné dans ses commentaires que je n'abordais pas autant l'unicité que l'anonymat. Je suis moins certain des avantages de l'unicité, mais il convient de noter que le comportement des éléments suivants est clair si les types sont uniques (l'action sera instanciée deux fois).

int counter()
{
    static int count = 0;
    return count++;
}

template <typename FuncT>
void action(const FuncT& func)
{
    static int ct = counter();
    func(ct);
}

...
for (int i = 0; i < 5; i++)
    action([](int j) { std::cout << j << std::endl; });

for (int i = 0; i < 5; i++)
    action([](int j) { std::cout << j << std::endl; });

Si les types n'étaient pas uniques, nous aurions à spécifier quel comportement devrait se produire dans ce cas. Cela pourrait être délicat. Certaines des questions qui ont été soulevées au sujet de l'anonymat soulèvent également leur vilaine tête dans cette affaire pour un caractère unique.

Les lambdas ne sont pas seulement des fonctions, ils sont une fonction et un état . Par conséquent, C ++ et Rust les implémentent comme un objet avec un opérateur d'appel ( operator()en C ++, les 3 Fn*traits de Rust).

Fondamentalement, [a] { return a + 1; }dans desugars C ++ à quelque chose comme

struct __SomeName {
    int a;

    int operator()() {
        return a + 1;
    }
};

puis en utilisant une instance __SomeNameoù le lambda est utilisé.

Pendant que vous || a + 1êtes à Rust, dans Rust, vous aurez quelque chose comme

{
    struct __SomeName {
        a: i32,
    }

    impl FnOnce<()> for __SomeName {
        type Output = i32;
        
        extern "rust-call" fn call_once(self, args: ()) -> Self::Output {
            self.a + 1
        }
    }

    // And FnMut and Fn when necessary

    __SomeName { a }
}

Cela signifie que la plupart des lambdas doivent avoir des types différents .

Maintenant, il y a plusieurs façons de le faire:

• Avec les types anonymes, c'est ce que les deux langues implémentent. Une autre conséquence de cela est que tous les lambdas doivent avoir un type différent. Mais pour les concepteurs de langage, cela présente un avantage évident: les Lambdas peuvent être simplement décrites en utilisant d'autres parties plus simples déjà existantes du langage. Ce ne sont que du sucre de syntaxe autour de parties déjà existantes du langage.
• Avec une syntaxe spéciale pour nommer les types lambda: Ceci n'est cependant pas nécessaire car les lambdas peuvent déjà être utilisés avec des modèles en C ++ ou avec des génériques et les Fn*traits dans Rust. Aucun des deux langages ne vous oblige à effacer les lambdas pour les utiliser (avec std::functionen C ++ ou Box<Fn*>en Rust).

Notez également que les deux langages conviennent que les lambdas triviaux qui ne capturent pas le contexte peuvent être convertis en pointeurs de fonction.

Décrire les fonctionnalités complexes d'un langage à l'aide de fonctionnalités plus simples est assez courant. Par exemple, C ++ et Rust ont tous deux des boucles range-for, et ils les décrivent tous deux comme du sucre de syntaxe pour d'autres fonctionnalités.

C ++ définit

for (auto&& [first,second] : mymap) {
    // use first and second
}

comme étant équivalent à

{

    init-statement
    auto && __range = range_expression ;
    auto __begin = begin_expr ;
    auto __end = end_expr ;
    for ( ; __begin != __end; ++__begin) {

        range_declaration = *__begin;
        loop_statement

    }

} 

et Rust définit

for <pat> in <head> { <body> }

comme étant équivalent à

let result = match ::std::iter::IntoIterator::into_iter(<head>) {
    mut iter => {
        loop {
            let <pat> = match ::std::iter::Iterator::next(&mut iter) {
                ::std::option::Option::Some(val) => val,
                ::std::option::Option::None => break
            };
            SemiExpr(<body>);
        }
    }
};

qui, bien qu'ils semblent plus compliqués pour un humain, sont à la fois plus simples pour un concepteur de langage ou un compilateur.

(Ajout à la réponse de Caleth, mais trop long pour tenir dans un commentaire.)

L'expression lambda n'est que du sucre syntaxique pour une structure anonyme (un type Voldemort, car vous ne pouvez pas dire son nom).

Vous pouvez voir la similitude entre une structure anonyme et l'anonymat d'un lambda dans cet extrait de code:

#include <iostream>
#include <typeinfo>

using std::cout;

int main() {
    struct { int x; } foo{5};
    struct { int x; } bar{6};
    cout << foo.x << " " << bar.x << "\n";
    cout << typeid(foo).name() << "\n";
    cout << typeid(bar).name() << "\n";
    auto baz = [x = 7]() mutable -> int& { return x; };
    auto quux = [x = 8]() mutable -> int& { return x; };
    cout << baz() << " " << quux() << "\n";
    cout << typeid(baz).name() << "\n";
    cout << typeid(quux).name() << "\n";
}

Si cela n'est toujours pas satisfaisant pour un lambda, cela devrait également être insatisfaisant pour une structure anonyme.

Certains langages permettent une sorte de typage canard qui est un peu plus flexible, et même si C ++ a des modèles qui n'aident pas vraiment à créer un objet à partir d'un modèle qui a un champ membre qui peut remplacer un lambda directement plutôt que d'utiliser un std::functionwrapper.

Pourquoi concevoir un langage avec des types anonymes uniques ?

Parce qu'il y a des cas où les noms ne sont ni pertinents ni utiles ni même contre-productifs. Dans ce cas, la capacité d'abstraire leur existence est utile car elle réduit la pollution des noms et résout l'un des deux problèmes difficiles de l'informatique (comment nommer les choses). Pour la même raison, les objets temporaires sont utiles.

lambda

L'unicité n'est pas une chose lambda spéciale, ni même une chose spéciale pour les types anonymes. Cela s'applique également aux types nommés dans le langage. Pensez à suivre:

struct A {
    void operator()(){};
};

struct B {
    void operator()(){};
};

void foo(A);

Notez que je ne peux pas passer Bdans foo, même si les classes sont identiques. Cette même propriété s'applique aux types sans nom.

lambdas ne peut être passé qu'aux fonctions de modèle qui permettent au moment de la compilation, un type indescriptible d'être passé avec l'objet ... effacé via std :: function <>.

Il existe une troisième option pour un sous-ensemble de lambdas: les lambdas non capturants peuvent être convertis en pointeurs de fonction.

Notez que si les limitations d'un type anonyme sont un problème pour un cas d'utilisation, alors la solution est simple: un type nommé peut être utilisé à la place. Les lambdas ne font rien qui ne puisse pas être fait avec une classe nommée.

La réponse acceptée par Cort Ammon est bonne, mais je pense qu'il y a un autre point important à faire sur l'implémentation.

Supposons que j'ai deux unités de traduction différentes, "one.cpp" et "two.cpp".

// one.cpp
struct A { int operator()(int x) const { return x+1; } };
auto b = [](int x) { return x+1; };
using A1 = A;
using B1 = decltype(b);

extern void foo(A1);
extern void foo(B1);

Les deux surcharges fooutilisent le même identifiant ( foo) mais ont des noms mutilés différents. (Dans l'ABI Itanium utilisé sur les systèmes POSIX-ish, les noms mutilés sont _Z3foo1Aet, dans ce cas particulier,. _Z3fooN1bMUliE_E)

// two.cpp
struct A { int operator()(int x) const { return x + 1; } };
auto b = [](int x) { return x + 1; };
using A2 = A;
using B2 = decltype(b);

void foo(A2) {}
void foo(B2) {}

Le compilateur C ++ doit s'assurer que le nom mutilé de void foo(A1)dans "two.cpp" est le même que le nom mutilé de extern void foo(A2)"one.cpp", afin que nous puissions lier les deux fichiers objets ensemble. C'est la signification physique de deux types étant "du même type": il s'agit essentiellement de compatibilité ABI entre des fichiers objets compilés séparément.

Le compilateur C ++ n'est pas obligé de s'assurer que B1et B2sont «du même type». (En fait, il est nécessaire de s'assurer qu'ils sont de types différents; mais ce n'est pas aussi important pour le moment.)

Quel mécanisme physique le compilateur utilise-t-il pour s'assurer que A1et A2sont "du même type"?

Il fouille simplement dans les typedefs, puis examine le nom complet du type. C'est un type de classe nommé A. (Eh bien, ::Apuisque c'est dans l'espace de noms global.) Donc c'est le même type dans les deux cas. C'est facile à comprendre. Plus important encore, il est facile à mettre en œuvre . Pour voir si deux types de classes sont du même type, prenez leurs noms et effectuez un strcmp. Pour transformer un type de classe en nom mutilé d'une fonction, vous écrivez le nombre de caractères dans son nom, suivi de ces caractères.

Ainsi, les types nommés sont faciles à modifier.

Quel mécanisme physique le compilateur pourrait -il utiliser pour s'assurer que B1et B2sont «du même type», dans un monde hypothétique où C ++ exigeait qu'ils soient du même type?

Eh bien, il ne pouvait pas utiliser le nom du type, parce que le type n'a pas avoir un nom.

Peut-être qu'il pourrait en quelque sorte encoder le texte du corps du lambda. Mais ce serait un peu gênant, car en fait le bdans "one.cpp" est subtilement différent du bdans "two.cpp": "one.cpp" a x+1et "two.cpp" a x + 1. Nous devrions donc trouver une règle qui dit soit que cette différence d'espace n'a pas d' importance, soit qu'elle le fait (ce qui en fait des types différents après tout), ou que peut - être que c'est le cas (peut-être que la validité du programme est définie par l'implémentation , ou peut-être que c'est "mal formé aucun diagnostic requis"). En tous cas,A

Le moyen le plus simple de sortir de la difficulté est simplement de dire que chaque expression lambda produit des valeurs d'un type unique. Ensuite, deux types lambda définis dans des unités de traduction différentes ne sont certainement pas du même type . Dans une seule unité de traduction, nous pouvons "nommer" les types lambda en comptant simplement à partir du début du code source:

auto a = [](){};  // a has type $_0
auto b = [](){};  // b has type $_1
auto f(int x) {
    return [x](int y) { return x+y; };  // f(1) and f(2) both have type $_2
} 
auto g(float x) {
    return [x](int y) { return x+y; };  // g(1) and g(2) both have type $_3
} 

Bien sûr, ces noms n'ont de sens que dans cette unité de traduction. Ce TU $_0est toujours d'un type différent de certains autres TU $_0, même si ce TU struct Aest toujours du même type que certains autres TU struct A.

Soit dit en passant, notez que notre idée «encoder le texte du lambda» avait un autre problème subtil: les lambdas $_2et se $_3composent exactement du même texte , mais ils ne devraient clairement pas être considérés comme du même type!

À propos, C ++ nécessite que le compilateur sache comment modifier le texte d'une expression C ++ arbitraire , comme dans

template<class T> void foo(decltype(T())) {}
template void foo<int>(int);  // _Z3fooIiEvDTcvT__EE, not _Z3fooIiEvT_

Mais C ++ n'exige pas (encore) que le compilateur sache comment modifier une instruction C ++ arbitraire . decltype([](){ ...arbitrary statements... })est encore mal formé même en C ++ 20.

Notez également qu'il est facile de donner un alias local à un type sans nom en utilisant typedef/ using. J'ai le sentiment que votre question a peut-être surgi en essayant de faire quelque chose qui pourrait être résolu de cette manière.

auto f(int x) {
    return [x](int y) { return x+y; };
}

// Give the type an alias, so I can refer to it within this translation unit
using AdderLambda = decltype(f(0));

int of_one(AdderLambda g) { return g(1); }

int main() {
    auto f1 = f(1);
    assert(of_one(f1) == 2);
    auto f42 = f(42);
    assert(of_one(f42) == 43);
}

MODIFIE POUR AJOUTER: En lisant certains de vos commentaires sur d'autres réponses, il semble que vous vous demandez pourquoi

int add1(int x) { return x + 1; }
int add2(int x) { return x + 2; }
static_assert(std::is_same_v<decltype(add1), decltype(add2)>);
auto add3 = [](int x) { return x + 3; };
auto add4 = [](int x) { return x + 4; };
static_assert(not std::is_same_v<decltype(add3), decltype(add4)>);

C'est parce que les lambdas sans captures sont constructibles par défaut. (En C ++ uniquement à partir de C ++ 20, mais cela a toujours été conceptuellement vrai.)

template<class T>
int default_construct_and_call(int x) {
    T t;
    return t(x);
}

assert(default_construct_and_call<decltype(add3)>(42) == 45);
assert(default_construct_and_call<decltype(add4)>(42) == 46);

Si vous avez essayé default_construct_and_call<decltype(&add1)>, ce tserait un pointeur de fonction initialisé par défaut et vous auriez probablement une erreur de segmentation. Ce n'est pas utile.

Les lambdas C ++ ont besoin de types distincts pour des opérations distinctes, car C ++ se lie statiquement. Ils ne peuvent être construits que par copie / déplacement, vous n'avez donc généralement pas besoin de nommer leur type. Mais c'est en quelque sorte un détail de mise en œuvre.

Je ne sais pas si les lambdas C # ont un type, car ce sont des "expressions de fonction anonymes", et elles sont immédiatement converties en un type de délégué compatible ou un type d'arborescence d'expression. Si c'est le cas, c'est probablement un type imprononçable.

C ++ a également des structures anonymes, où chaque définition mène à un type unique. Ici, le nom n'est pas imprononçable, il n'existe tout simplement pas en ce qui concerne la norme.

C # a des types de données anonymes , qu'il interdit soigneusement de s'échapper de la portée dans laquelle ils sont définis. L'implémentation leur donne également un nom unique et imprononçable.

Avoir un type anonyme signale au programmeur qu'il ne doit pas fouiller dans leur implémentation.

De côté:

Vous pouvez donner un nom au type d'un lambda.

auto foo = []{}; 
using Foo_t = decltype(foo);

Si vous n'avez aucune capture, vous pouvez utiliser un type de pointeur de fonction

void (*pfoo)() = foo;

Pourquoi utiliser des types anonymes?

Pour les types générés automatiquement par le compilateur, le choix est soit (1) d'honorer la demande d'un utilisateur pour le nom du type, soit (2) de laisser le compilateur en choisir un seul.

1. Dans le premier cas, l'utilisateur est censé fournir explicitement un nom chaque fois qu'une telle construction apparaît (C ++ / Rust: chaque fois qu'un lambda est défini; Rust: chaque fois qu'une fonction est définie). Il s'agit d'un détail fastidieux que l'utilisateur doit fournir à chaque fois, et dans la majorité des cas, le nom n'est plus jamais mentionné. Il est donc logique de laisser le compilateur trouver un nom automatiquement et d'utiliser des fonctionnalités existantes telles que l' decltypeinférence de type ou pour référencer le type aux quelques endroits où il est nécessaire.

2. Dans ce dernier cas, le compilateur doit choisir un nom unique pour le type, qui serait probablement un nom obscur et illisible tel que __namespace1_module1_func1_AnonymousFunction042. Le concepteur de langage pourrait spécifier précisément comment ce nom est construit dans des détails glorieux et délicats, mais cela expose inutilement un détail d'implémentation à l'utilisateur sur lequel aucun utilisateur sensé ne pourrait se fier, car le nom est sans aucun doute fragile face à des refactors même mineurs. Cela contraint également inutilement l'évolution du langage: les ajouts futurs de fonctionnalités peuvent entraîner une modification de l'algorithme de génération de nom existant, entraînant des problèmes de compatibilité descendante. Ainsi, il est logique d'omettre simplement ce détail et d'affirmer que le type généré automatiquement n'est pas exprimable par l'utilisateur.

Pourquoi utiliser des types uniques (distincts)?

Si une valeur a un type unique, un compilateur d'optimisation peut suivre un type unique sur tous ses sites d'utilisation avec une fidélité garantie. En corollaire, l'utilisateur peut alors être certain des endroits où la provenance de cette valeur particulière est pleinement connue du compilateur.

À titre d'exemple, au moment où le compilateur voit:

let f: __UniqueFunc042 = || { ... };  // definition of __UniqueFunc042 (assume it has a nontrivial closure)

/* ... intervening code */

let g: __UniqueFunc042 = /* some expression */;
g();

le compilateur a une confiance totale qui gdoit nécessairement provenir de f, sans même connaître la provenance de g. Cela permettrait gde dévirtualiser l'appel. L'utilisateur le saurait également, car l'utilisateur a pris grand soin de préserver le type unique de fflux de données qui a conduit à g.

Nécessairement, cela limite ce que l'utilisateur peut faire f. L'utilisateur n'est pas libre d'écrire:

let q = if some_condition { f } else { || {} };  // ERROR: type mismatch

car cela conduirait à l'unification (illégale) de deux types distincts.

Pour contourner ce problème, l'utilisateur peut effectuer une conversion ascendante __UniqueFunc042vers le type non unique &dyn Fn(),

let f2 = &f as &dyn Fn();  // upcast
let q2 = if some_condition { f2 } else { &|| {} };  // OK

Le compromis fait par ce type d'effacement est que les utilisations de &dyn Fn()compliquent le raisonnement du compilateur. Donné:

let g2: &dyn Fn() = /*expression */;

le compilateur doit examiner minutieusement le /*expression */pour déterminer s'il g2provient de fou d'une autre fonction (s), et les conditions dans lesquelles cette provenance tient. Dans de nombreuses circonstances, le compilateur peut abandonner: peut-être que l'humain pourrait dire que g2cela vient vraiment de fdans toutes les situations, mais le chemin de fà g2était trop compliqué pour que le compilateur puisse le déchiffrer, résultant en un appel virtuel à g2avec des performances pessimistes.

Cela devient plus évident lorsque ces objets sont livrés à des fonctions génériques (modèle):

fn h<F: Fn()>(f: F);

Si on appelle h(f)where f: __UniqueFunc042, alors hest spécialisé sur une instance unique:

h::<__UniqueFunc042>(f);

Cela permet au compilateur de générer du code spécialisé pour h, adapté à l'argument particulier de f, et l'envoi vers fest très probablement statique, sinon intégré.

Dans le scénario opposé, où l'on appelle h(f)avec f2: &Fn(), le hest instancié comme

h::<&Fn()>(f);

qui est partagée entre toutes les fonctions de type &Fn(). De l'intérieur h, le compilateur en sait très peu sur une fonction opaque de type &Fn()et ne pourrait donc appeler de manière conservatrice fqu'avec une distribution virtuelle. Pour distribuer de manière statique, le compilateur devrait intégrer l'appel à h::<&Fn()>(f)sur son site d'appel, ce qui n'est pas garanti s'il hest trop complexe.

Premièrement, les lambda sans capture sont convertibles en pointeur de fonction. Donc, ils fournissent une forme de généricité.

Maintenant, pourquoi les lambdas avec capture ne sont pas convertibles en pointeur? Étant donné que la fonction doit accéder à l'état du lambda, cet état doit apparaître comme un argument de fonction.

Pour éviter les conflits de noms avec le code utilisateur.

Même deux lambdas avec la même implémentation auront des types différents. Ce qui est bien car je peux aussi avoir différents types d'objets même si leur disposition de mémoire est égale.