Une fonction pure mémorisée est-elle considérée comme pure?

47

Disons que fn(x)c’est une fonction pure qui fait quelque chose de coûteux, telle que renvoyer une liste des facteurs premiers de x.

Et disons que nous faisons une version mémoisée de la même fonction appelée memoizedFn(x). Il renvoie toujours le même résultat pour une entrée donnée, mais conserve un cache privé des résultats précédents pour améliorer les performances.

Formellement parlant, est memoizedFn(x)considéré comme pur?

Ou existe-t-il un autre nom ou terme qualificatif utilisé pour désigner une telle fonction dans les discussions sur la PF? (c.-à-d. une fonction avec des effets secondaires qui peuvent affecter la complexité de calcul des appels suivants, mais qui peuvent ne pas affecter les valeurs de retour.)

callum
la source
24
Peut-être que ce n'est pas pur pour les puristes, mais "assez pur" pour les gens pragmatiques ;-)
Doc Brown
2
@DocBrown Je suis d'accord, je me demandais simplement s'il existait un terme plus formel pour «assez pur»
callum
13
L'exécution d'une fonction pure modifiera probablement le cache d'instructions du processeur, les prédicteurs de branche, etc. Mais c'est probablement "assez pur" pour les puristes également - ou vous pouvez oublier les fonctions pures.
Gnasher729
10
@callum Non, il n'y a pas de définition formelle de "assez pur". Lorsque vous discutez de la pureté et de l'équivalence sémantique de deux appels "référentiellement transparents", vous devez toujours indiquer exactement la sémantique que vous allez appliquer. A un niveau de détail d'implémentation bas, il sera toujours défaillant et aura des effets de mémoire ou des timings différents. C'est pourquoi vous devez être pragmatique: quel niveau de détail est utile pour raisonner sur votre code?
Bergi
3
Ensuite, dans un souci de pragmatisme, je dirais que la pureté dépend du fait que vous considériez ou non que le temps de calcul fait partie des résultats. funcx(){sleep(cached_time--); return 0;}renvoie le même val à chaque fois, mais se comportera différemment
Mars

Réponses:

41

Oui. La version mémoisée d'une fonction pure est également une fonction pure.

La pureté de cette fonction ne concerne que l'effet que les paramètres d'entrée sur la valeur de retour de la fonction (transmettre la même entrée doit toujours produire la même sortie) et tous les effets secondaires pertinents pour les états globaux (par exemple, le texte envoyé au terminal, à l'interface utilisateur ou au réseau). . Le temps de calcul et les utilisations de mémoire supplémentaires sont sans importance pour la pureté de la fonction.

Les caches d'une fonction pure sont quasiment invisibles pour le programme; un langage de programmation fonctionnel est autorisé à optimiser automatiquement une fonction pure en une version mémoisée de la fonction s'il peut déterminer que cela sera bénéfique. En pratique, déterminer automatiquement quand la mémorisation est bénéfique est en réalité un problème assez difficile, mais une telle optimisation serait valide.

Lie Ryan
la source
19

Wikipedia définit une "fonction pure" en tant que fonction ayant les propriétés suivantes:

  • Sa valeur de retour est la même pour les mêmes arguments (pas de variation avec des variables statiques locales, des variables non locales, des arguments de référence modifiables ou des flux d'entrée provenant de périphériques d'E / S).

  • Son évaluation n'a aucun effet secondaire (pas de mutation de variables statiques locales, de variables non locales, d'arguments de référence modifiables ni de flux d'E / S).

En effet, une fonction pure retourne la même sortie à partir de la même entrée et n’affecte rien d’autre en dehors de la fonction. Pour des raisons de pureté, la façon dont la fonction calcule sa valeur de retour n'a pas d'importance, tant qu'elle renvoie la même sortie avec la même entrée.

Des langages fonctionnellement purs comme Haskell utilisent régulièrement la mémorisation pour accélérer une fonction en mettant en cache les résultats précédemment calculés.

Robert Harvey
la source
16
Il se peut que je manque quelque chose, mais comment allez-vous garder la cache sans effets secondaires?
val
1
En le gardant à l'intérieur de la fonction.
Robert Harvey
4
"pas de mutation de variable statique locale" semble également exclure les variables locales persistantes entre les appels.
Val
3
Cela ne répond pas réellement à la question, même si vous semblez impliquer que oui, c'est pur.
Mars
6
@val Tu as raison: cette condition doit être un peu assouplie. La mémoisation purement fonctionnelle à laquelle il fait référence ne présente aucune mutation visible de données statiques. Ce qui se passe, c'est que le résultat est ensuite calculé et mémoisé la première fois que la fonction est appelée et renvoie la même valeur à chaque appel. Beaucoup de langages ont un idiome pour cela: une static constvariable locale en C ++ (mais pas le C), ou une structure de données évaluée paresseusement en Haskell. Une autre condition est nécessaire: l’initialisation doit être thread-safe.
Davislor
7

Oui, les fonctions pures mémoisées sont communément appelées pures. Ceci est particulièrement courant dans des langues telles que Haskell, dans lesquelles des résultats immuables mémorisés, évalués paresseux et immuables sont intégrés.

Il y a une mise en garde importante: la fonction de mémorisation doit être adaptée aux threads, sinon vous risquez d'obtenir une condition de concurrence critique lorsque deux threads tentent de l'appeler.

Voici un exemple d'informaticien utilisant le terme «purement fonctionnel»: ce billet de blog de Conal Elliott sur la mémoisation automatique:

Peut-être étonnamment, la mémorisation peut être implémentée simplement et purement fonctionnelle dans un langage fonctionnel paresseux.

Il existe de nombreux exemples dans la littérature évaluée par des pairs, et ce depuis des décennies. Par exemple, cet article de 1995, "Utilisation de la mémorisation automatique en tant qu'outil d'ingénierie logicielle dans des systèmes d'intelligence artificielle du monde réel", utilise un langage très similaire dans la section 5.2 pour décrire ce que nous appellerions aujourd'hui une fonction pure:

La mémorisation ne fonctionne que pour les vraies fonctions, pas les procédures. Autrement dit, si le résultat d'une fonction n'est pas spécifié de manière complète et déterministe par ses paramètres d'entrée, l'utilisation de la mémorisation donnera des résultats incorrects. Le nombre de fonctions pouvant être mémorisées avec succès sera augmenté en encourageant l’utilisation d’un style de programmation fonctionnel dans l’ensemble du système.

Certaines langues impératives ont un idiome similaire. Par exemple, une static constvariable en C ++ n'est initialisée qu'une fois, avant que sa valeur ne soit utilisée, et ne mute jamais.

Davislor
la source
3

Cela dépend de la façon dont vous le faites.

Habituellement, les gens veulent mémoriser en transformant un dictionnaire de cache. Cela présente tous les problèmes associés aux mutations impures, tels que le souci de la concurrence, l’inquiétude de voir le cache devenir trop volumineux, etc.

Cependant, vous pouvez mémoriser sans mutation impure de la mémoire. Un exemple est dans cette réponse , où je dépiste les valeurs mémoisées en externe au moyen d’un lengthsargument.

Dans le lien fourni par Robert Harvey , l'évaluation paresseuse est utilisée pour éviter les effets secondaires.

Une autre technique parfois utilisée consiste à marquer explicitement la mémorisation en tant qu'effet secondaire impur dans le contexte d'un IOtype, comme avec la fonction memoize de cats-effect .

Ce dernier point fait apparaître que parfois l'objectif consiste simplement à encapsuler la mutation plutôt que de l'éliminer. La plupart des programmeurs fonctionnels considèrent qu'il est "assez pur" pour rendre l'impureté explicite et encapsulée.

Si vous voulez un terme qui le différencie d'une fonction vraiment pure, je pense qu'il suffit de dire "mémo avec un dictionnaire mutable". Cela permet aux gens de savoir comment l'utiliser en toute sécurité.

Karl Bielefeldt
la source
Je ne pense pas que la solution la plus pure puisse résoudre les problèmes ci-dessus: pendant que vous perdez tout souci de concurrence, vous perdez également toute chance pour deux appels lancés simultanément comme collatz(100)et collatz(200)de coopérer. Et IIUIC, le problème avec le cache devenant trop grand reste (bien que Haskell puisse avoir quelques astuces intéressantes pour cela?).
Maaartinus
Note: IOest pur. Toutes les méthodes impures sur IOet les chats sont nommés unsafe. Async.memoizeest également pur, nous n’avons donc pas à nous contenter de "assez pur" :)
Samuel
2

Habituellement, une fonction qui renvoie une liste n'est pas pure du tout car elle nécessite une allocation de stockage et peut donc échouer (par exemple en lançant une exception qui n'est pas pure). Un langage comportant des types de valeur et pouvant représenter une liste en tant que type de valeur de taille limitée peut ne pas avoir ce problème. Pour cette raison, votre exemple n'est probablement pas pur.

En général, si la mémorisation peut être effectuée de manière à éviter les incidents (par exemple, en ayant un stockage alloué de manière statique pour les résultats mémorisés et une synchronisation interne pour en contrôler l'accès si le langage admet des threads), il est raisonnable d'envisager une telle fonction. pur.

R ..
la source
0

Vous pouvez implémenter la mémorisation sans effets secondaires en utilisant la monade d'état .

[Monade d'état] est fondamentalement une fonction S => (S, A), où S est le type qui représente votre état et A le résultat que la fonction produit - Cats State .

Dans votre cas, l'état serait la valeur mémoisée ou rien (c'est-à-dire Haskell Maybeou Scala Option[A]). Si la valeur mémo est présente, elle est renvoyée sous la forme A, sinon, elle Aest calculée et renvoyée à la fois comme état de transition et résultat.

Samuel
la source