pourquoi memoization n'est pas une fonctionnalité du langage?

Question

Je me demandais... pourquoi memoization n'est pas fourni nativement comme une fonctionnalité du langage par n'importe quelle langue-je connaître?

Edit: pour préciser, ce que je veux dire, c'est que la langue fournit un mot-clé pour spécifier une fonction donnée comme memoizable, pas que chaque fonction est automatiquement memoized "par défaut", à moins d'indication contraire. Par exemple, fortran fournit le mot-clé PUR pour spécifier une fonction spécifique en tant que tel. Je suppose que le compilateur peut tirer parti de cette information pour memoize l'appel, mais j'ignore ce qui se passe si vous déclarez PURE d'une fonction avec des effets secondaires.

Answer 1

Ce que VOUS voulez de memoization peut-être pas la même chose que ce que le compilateur memoization option serait de fournir.

Vous savez peut-être que c'est seulement rentable pour memoize le dernier 10 ou si les valeurs distinctes calculé, parce que vous savez comment cette fonction sera utilisée.

Vous savez peut-être qu'il n'a de sens que pour memoize 2 ou 3 valeurs, parce que vous ne serez jamais utiliser des valeurs plus vieux que ça. (Fibonacci de la Séquence qui vient à l'esprit.)

Vous pouvez générer un grand nombre de valeurs sur certaines pistes, et seulement quelques-uns sur les autres.

Vous voudrez peut-être "jeter" certains memoized valeurs et de recommencer. (Je memoized un générateur de nombre aléatoire de cette manière, afin que je puisse rejouer la séquence de nombres aléatoires qui construit une certaine structure, tandis que certains autres paramètres de la structure a été modifiée.)

Memoization comme une optimisation dépend de la recherche de la memoized valeur étant beaucoup moins cher que le recalcul de la valeur. Cela dépend de la commande de l'entrée des demandes. Ceci a des implications pour la memoization base de données: faut-il utiliser une pile, un tableau de toutes les valeurs d'entrée possibles (qui peuvent être de très grande taille), un seau de hachage, ou un b-arbre?

Le memoizing compilateur doit fournir soit un "one size fits all" memoization, ou qu'il peut apporter beaucoup de solutions de rechange possibles, et des paramètres pour contrôler les solutions de rechange. À un certain point, il devient plus facile pour tout le monde à demander à l'utilisateur de fournir son propre memoization.

Answer 2

Parce que les compilateurs ont pour émettre de la sémantique des programmes corrects. Vous ne pouvez pas memoize une fonction sans changer la sémantique du programme, sauf si elle est referentially transparent. Dans la plupart des langages de programmation de toutes les fonctions ne sont referentially transparent (pur langages de programmation fonctionnelle sont une exception) donc vous ne pouvez pas memoize tout. Mais alors, un mécanisme est nécessaire pour la détection de la transparence référentielle et c'est trop dur.

Answer 3

En Haskell, memoization est automatique pour (pur) de fonctions, vous avez défini un qui ne prennent pas d'arguments. Et l'exemple de Fibonacci dans ce Wiki est vraiment le plus simple démontrable exemple, je serais capable de penser à soit.

Haskell peut le faire parce que votre pur fonctions sont définies pour produire les mêmes résultats à chaque fois; bien sûr, monadique les fonctions qui en dépendent effets secondaires ne seront pas memoized.

Je ne suis pas sûr de ce que les limites supérieures sont, de toute évidence, il ne sera pas memoize plus que la mémoire disponible. Et je suis également pas sûr désinvolte si le memoization se produit au moment de la compilation (si les valeurs peuvent être déterminés au moment de la compilation), ou si il toujours se produit la première fois que la fonction est appelée.

Answer 4

Clojure est un memoize fonction (http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/memoize):

memoize
function

Usage: (memoize f)

Returns a memoized version of a referentially transparent function. The
memoized version of the function keeps a cache of the mapping from arguments
to results and, when calls with the same arguments are repeated often, has
higher performance at the expense of higher memory use.

Answer 5

Parce que vous ne devriez pas vous mettre en place quelque chose comme une fonctionnalité du langage quand il peut facilement être mis en œuvre dans le langage lui-même. Un memoization appartient dans une bibliothèque, ce qui est exactement là où la plupart des langues de la mettre.