Dans cet article, je vais vous parler d'une des options de curry et de l'application partielle des fonctions en C ++ qui est mon préféré. Je vais également montrer ma propre implémentation pilote de cette chose et expliquer le point de curry sans formule mathématique complexe, ce qui est vraiment simple pour vous. Nous verrons également ce qui se trouve sous le capot de la bibliothèque kari.hpp que nous utiliserons pour les fonctions de curry. Quoi qu'il en soit, il y a beaucoup de choses fascinantes à l'intérieur, alors bienvenue!
Currying
Alors, qu'est-ce que le curry? Je suppose que c'est l'un de ces mots que vous entendez tout le temps des programmeurs Haskell (après la monade , bien sûr). Essentiellement, la définition du terme est assez simple, donc les lecteurs qui ont déjà écrit sur des langages de type ML ou Haskell , ou qui savent ce que cela signifie ailleurs, se sentent libres de sauter cette section.
Currying - est la technique de transformation d'une fonction qui prend N arguments en une fonction, qui prend un seul argument et retourne la fonction de l'argument suivant, et elle continue jusqu'à ce que nous retournions la fonction du dernier argument, qui va représenter le résultat global. Je pense que cela aide si je vous montre des exemples:
int sum2(int lhs, int rhs) { return lhs + rhs; }
Nous avons ici une fonction d'addition binaire. Et si nous voulons en faire une fonction à variable unique? C'est en fait très simple:
auto curried_sum2(int lhs) { return [=](int rhs) { return sum2(lhs, rhs); }; }
Non, qu'avons-nous fait? Nous avons pris une valeur basée sur un seul argument appelé lambda qui à son tour prend le deuxième argument et effectue l'ajout lui-même. En conséquence, nous pouvons appliquer la fonction curried_sum2 à nos arguments un par un:
Et c'est en fait tout l'intérêt de l'opération de curry. Bien sûr, il est possible de le faire avec des fonctions de n'importe quelle arité - cela fonctionnera absolument de la même manière. Nous retournerons une fonction curry de N-1 arguments chaque fois que nous prenons la valeur d'un autre argument:
auto sum3(int v1, int v2, int v3) { return v1 + v2 + v3; } auto curried_sum3(int v1) { return [=](int v2){ return [=](int v3){ return sum3(v1, v2, v3); }; }; }
Application partielle
Application partielle - est un moyen d'appeler des fonctions de N arguments lorsqu'ils ne prennent qu'une partie des arguments et renvoient une autre fonction des arguments restants.
À cet égard, il convient de noter que dans des langues comme Haskell, ce processus fonctionne automatiquement, derrière le dos d'un programmeur. Ce que nous essayons de faire ici est de l'exécuter explicitement, sum3 à- sum3 d'appeler notre fonction sum3 comme ceci: sum3(38,3)(1) ou peut-être comme ceci: sum3(38)(3,1) . En plus de cela, si une fonction renvoie une autre fonction qui a été curry, elle peut également être appelée en utilisant la liste des arguments de la première fonction. Voyons l'exemple:
int boo(int v1, int v2) { return v1 + v2; } auto foo(int v1, int v2) { return kari::curry(boo, v1 + v2); }
En fait, nous avons un peu d'avance sur nous-mêmes, montrant un exemple d'utilisation de kari.hpp , alors oui, c'est le cas.
Fixer les objectifs
Avant d'écrire quelque chose, il est nécessaire (ou souhaitable) de comprendre ce que nous voulons avoir à la fin. Et nous voulons avoir la possibilité de curry et d'appliquer partiellement toute fonction qui peut être appelée en C ++. Quels sont:
- lambdas (y compris les génériques)
- objets fonction (foncteurs)
- fonctions de toute arité (y compris les modèles)
- fonctions variadiques
- méthodes d'une classe
Les fonctions variadiques peuvent être curry en spécifiant un nombre exact d'arguments que nous voulons curry. Une interaction standard avec std :: bind et ses résultats sont également souhaitables. Et bien sûr, nous avons besoin d'une opportunité pour appliquer des fonctions à variables multiples et appeler des fonctions imbriquées de sorte qu'il semble que nous ayons travaillé avec une fonction curry.
Et nous ne devons pas non plus oublier les performances. Nous devons minimiser les coûts de calcul des wrappers, le transfert des arguments et leur stockage. Cela signifie que nous devons déplacer au lieu de copier, stocker uniquement ce dont nous avons vraiment besoin et renvoyer (avec une suppression supplémentaire) les données aussi rapidement que possible.
Auteur, vous essayez à nouveau d'inventer std::bind one!
Oui et non. std::bind est sans aucun doute un outil puissant et éprouvé, et je n'ai pas l'intention d'écrire son meurtrier ou son alternative. Oui, il peut être utilisé pour le curry et une application partielle explicite (en spécifiant exactement quels arguments nous appliquons, où et combien). Mais c'est sûr que ce n'est pas l'approche la plus pratique, sans mentionner qu'elle n'est pas toujours applicable car nous devons connaître l'arité de la fonction et écrire des liaisons spécifiques en fonction de cela. Par exemple:
int foo(int v1, int v2, int v3, int v4) { return v1 + v2 + v3 + v4; }
API
namespace kari { template < typename F, typename... Args > constexpr decltype(auto) curry(F&& f, Args&&... args) const; template < typename F, typename... Args > constexpr decltype(auto) curryV(F&& f, Args&&... args) const; template < std::size_t N, typename F, typename... Args > constexpr decltype(auto) curryN(F&& f, Args&&... args) const; template < typename F > struct is_curried; template < typename F > constexpr bool is_curried_v = is_curried<F>::value; template < std::size_t N, typename F, typename... Args > struct curry_t { template < typename... As > constexpr decltype(auto) operator()(As&&... as) const; }; }
kari::curry(F&& f, Args&&... args)
Renvoie un objet fonction de type curry_t (une fonction curry) avec des arguments optionnels args appliqués ou avec le résultat de l'application des arguments à la fonction donnée f (si la fonction est nulle ou si les arguments transférés étaient suffisants pour l'appeler).
Si le paramètre f contient la fonction déjà curry, il renvoie sa copie avec les arguments args appliqués.
kari::curryV(F&& f, Args&&... args)
Permet de curryer des fonctions avec un nombre variable d'arguments. Après cela, ces fonctions peuvent être appelées à l'aide de l'opérateur () sans arguments. Par exemple:
auto c0 = kari::curryV(std::printf, "%d + %d = %d"); auto c1 = c0(37, 5); auto c2 = c1(42); c2();
Si le paramètre f contient une fonction qui a déjà été curry, il renvoie sa copie avec un type d'application modifié pour un nombre variable d'arguments avec les arguments args appliqués.
kari::curryN(F&& f, Args&&... args)
Permet de curry des fonctions avec un nombre variable d'arguments en spécifiant un nombre exact N d'arguments que nous voulons appliquer (sauf ceux donnés en args ). Par exemple:
char buffer[256] = {'\0'}; auto c = kari::curryN<3>(std::snprintf, buffer, 256, "%d + %d = %d"); c(37, 5, 42); std::cout << buffer << std::endl;
Si le paramètre f contient une fonction déjà curry, il renvoie sa copie avec le type d'application modifié pour N arguments avec les arguments args appliqués.
kari::is_curried<F>, kari::is_curried_v<F>
Quelques structures auxiliaires pour vérifier si une fonction a déjà été curry. Par exemple:
const auto l = [](int v1, int v2){ return v1 + v2; }; const auto c = curry(l);
kari::curry_t::operator()(As&&... as)
L'opérateur permettant une application complète ou partielle d'une fonction au curry. Renvoie la fonction curry des arguments restants de la fonction initiale F , ou la valeur de cette fonction obtenue par son application sur l'arriéré des anciens arguments et des nouveaux arguments as . Par exemple:
int foo(int v1, int v2, int v3, int v4) { return v1 + v2 + v3 + v4; } auto c0 = kari::curry(foo); auto c1 = c0(15, 20);
Si vous appelez une fonction curry sans argument en utilisant curryV ou curryN , elle sera appelée s'il y a suffisamment d'arguments. Sinon, il renverra une fonction partiellement appliquée. Par exemple:
auto c0 = kari::curryV(std::printf, "%d + %d = %d"); auto c1 = c0(37, 5); auto c2 = c1(42);
Détails de mise en œuvre
En vous donnant des détails sur l'implémentation, je vais utiliser C ++ 17 afin de garder le texte de l'article court et d'éviter les explications inutiles et empilées SFINAE , ainsi que des exemples d'implémentations que j'ai dû ajouter dans le C ++ 14 standard. Tout cela, vous pouvez le trouver dans le référentiel du projet, où vous pouvez également l'ajouter à vos favoris :)
make_curry(F&& f, std::tuple<Args...>&& args)
Une fonction auxiliaire qui crée un objet fonction curry_t ou applique la fonction f donnée aux arguments args .
template < std::size_t N, typename F, typename... Args > constexpr auto make_curry(F&& f, std::tuple<Args...>&& args) { if constexpr ( N == 0 && std::is_invocable_v<F, Args...> ) { return std::apply(std::forward<F>(f), std::move(args)); } else { return curry_t< N, std::decay_t<F>, Args... >(std::forward<F>(f), std::move(args)); } } template < std::size_t N, typename F > constexpr decltype(auto) make_curry(F&& f) { return make_curry<N>(std::forward<F>(f), std::make_tuple()); }
Maintenant, il y a deux choses intéressantes à propos de cette fonction:
- nous l'appliquons aux arguments uniquement s'il est appelable pour ces arguments et que le compteur d'application
N est à zéro - si la fonction n'est pas appelable, nous considérons cet appel comme une application partielle et créons un objet fonction
curry_t contenant la fonction et les arguments
struct curry_t
L'objet fonction censé stocker le backlog d'arguments et la fonction que nous appellerons lors de son application finale. Cet objet est ce que nous allons appeler et appliquer partiellement.
template < std::size_t N, typename F, typename... Args > struct curry_t { template < typename U > constexpr curry_t(U&& u, std::tuple<Args...>&& args) : f_(std::forward<U>(u)) , args_(std::move(args)) {} private: F f_; std::tuple<Args...> args_; };
Il y a un certain nombre de raisons pour lesquelles nous stockons l'arriéré d'arguments args_ dans std :: tuple :
1) les situations avec std :: ref sont gérées automatiquement pour stocker les références quand nous en avons besoin, par défaut en fonction de la valeur
2) application pratique d'une fonction en fonction de ses arguments ( std :: apply )
3) il est prêt à l'emploi, vous n'avez donc pas à l'écrire à partir de zéro :)
Nous avons également stocké l'objet que nous appelons et la fonction f_ par sa valeur, et soyez prudent lorsque vous choisissez le type lors de la création d'un (je vais développer ce problème ci-dessous), ou lorsque vous le déplacez ou le copiez en utilisant la référence universelle dans le constructeur.
Un paramètre de modèle N agit comme un compteur d'application pour les fonctions variadiques.
curry_t::operator()(const As&...)
Et, bien sûr, la chose qui fait que tout fonctionne - l'opérateur qui appelle l'objet fonction.
template < std::size_t N, typename F, typename... Args > struct curry_t {
L'opérateur appelant a quatre fonctions surchargées.
Une fonction sans paramètres permettant de commencer à appliquer la fonction variadique (créée par curryV ou curryN ). Ici, nous décrémentons le compteur d'application jusqu'à zéro, indiquant clairement que la fonction est prête à être appliquée, puis nous donnons tout ce qui est nécessaire pour que la fonction make_curry .
Fonction d'un seul argument qui décrémente le compteur d'applications de 1 (s'il n'est pas à zéro) et place notre nouvel argument a dans l'arriéré des arguments args_ et transfère tout cela à make_curry .
Une fonction variadique qui est en fait une astuce pour l'application partielle de divers arguments. Ce qu'il fait, c'est de les appliquer récursivement, une par une. Maintenant, il y a deux raisons pour lesquelles ils ne peuvent pas être appliqués en une seule fois:
- le compteur d'applications peut descendre à zéro avant qu'il n'y ait plus d'arguments
- la fonction
f_ peut être appelée plus tôt et retourner une autre fonction curry, donc tous les arguments suivants lui seront destinés
La dernière fonction sert de pont entre l'appel de curry_t utilisant lvalue et l'appel de fonctions en utilisant rvalue .
Les balises des fonctions qualifiées ref rendent l'ensemble du processus presque magique. Pour faire court, avec leur aide, nous apprenons qu'un objet a été appelé en utilisant la référence rvalue et nous pouvons simplement déplacer les arguments au lieu de les copier dans la fonction d'appel make_curry . Sinon, nous devrons copier les arguments afin d'avoir encore la possibilité d'appeler à nouveau cette fonction, en nous assurant que les arguments sont toujours là.
Bonus
Avant de conclure, je voudrais vous montrer quelques exemples du sucre syntaxique qu'ils ont dans kari.hpp qui peut être qualifié de bonus.
Sections opérateur
Les programmeurs qui ont déjà travaillé avec Haskell doivent être familiers avec les sections opérateurs permettant de donner une brève description des opérateurs appliqués. Par exemple, la structure (*2) , génère une fonction à argument unique, renvoyant le résultat de la multiplication de cet argument par 2. Donc, ce que je voulais c'était d'essayer d'écrire quelque chose comme ça en C ++. Aussitôt dit, aussitôt fait!
using namespace kari::underscore; std::vector<int> v{1,2,3,4,5}; std::accumulate(v.begin(), v.end(), 0, _+_);
Composition des fonctions
Et bien sûr, je ne serais pas un wacko complet si je n'avais pas essayé d'écrire une composition de fonction . En tant qu'opérateur de composition, j'ai choisi l' operator * comme le plus proche (par son apparence) de tous les symboles disponibles pour le signe de composition en mathématiques. Je l'ai également utilisé pour appliquer la fonction résultante à un argument. Voilà donc ce que j'ai:
using namespace kari::underscore;
- la composition des fonctions
(*2) et (+2) est appliquée à 4 . (4 + 2) * 2 = 12 - la fonction
(*2) est appliquée à 4 , puis nous appliquons (+2) au résultat. (4 * 2 + 2) = 10
De la même manière, vous pouvez créer des compositions assez complexes dans un style sans point , mais gardez à l'esprit que seuls les programmeurs Haskell les comprendront :)
Conclusion
Je pense qu'il était assez clair auparavant qu'il n'était pas nécessaire d'utiliser ces techniques dans de vrais projets. Mais je dois quand même le mentionner. Après tout, mon objectif était de faire mes preuves et de vérifier la nouvelle norme C ++. Serais-je capable de faire ça? Et serait C ++? Eh bien, je suppose que vous venez de voir que nous avons tous les deux fait ça. Et je suis vraiment reconnaissant à tous les gars qui ont lu le tout.