Pourquoi récursif de "laisser" faire de l'espace effcace?

Question

J'ai trouvé cette déclaration tout en étudiant Fonctionnel Réactif de Programmation, de "Branchement d'un Espace de Fuite avec une Flèche" par Hai Liu et Paul Hudak ( page 5) :

Suppose we wish to define a function that repeats its argument indefinitely:

    repeat x = x : repeat x

or, in lambdas:

    repeat = λx → x : repeat x

This requires O(n) space. But we can achieve O(1) space by writing instead:

    repeat = λx → let xs = x : xs
                  in xs

La différence ici, elle semble petite, mais extrêmement invite l'optimisation de l'espace. Pourquoi et comment ça se passe ? La meilleure proposition que j'ai faite est d'évaluer à la main:

    r = \x -> x: r x
    r 3

    -> 3: r 3 
    -> 3: 3: 3: ........
    -> [3,3,3,......]

Comme ci-dessus, nous aurons besoin de créer une infinité de nouvelles thunks de ces récursivité. Ensuite, j'essaie d'évaluer la seconde:

    r = \x -> let xs = x:xs in xs
    r 3

    -> let xs = 3:xs in xs
    -> xs, according to the definition above: 
    -> 3:xs, where xs = 3:xs
    -> 3:xs:xs, where xs = 3:xs

Dans la deuxième forme de l' xs s'affiche et peut être partagée entre tous les endroits qu'il se produise, donc je suppose que c'est pourquoi, nous ne pouvons exiger O(1) espaces plutôt que d' O(n). Mais je ne suis pas sûr de savoir si j'ai raison ou pas.

BTW: Le mot-clé "partagé" vient de la même document de la page 4:

Le problème ici est que le standard d'appel-par-besoin de règles d'évaluation sont incapables de reconnaître que la fonction:

f = λdt → integralC (1 + dt) (f dt) 

est le même que:

f = λdt → let x = integralC (1 + dt) x in x

L'ancienne définition de causes travailler à être répétée dans l'appel récursif pour f, alors que dans le second cas, le calcul est partagé.

Answer 1

Il est plus facile de comprendre avec des images:

• La première version

  repeat x = x : repeat x
  

  crée une chaîne de (:) constructeurs se terminant dans un thunk qui permettra de remplacer lui-même avec plus de constructeurs comme vous l'exigez. Ainsi, O(n) l'espace.

  

• La deuxième version

  repeat x = let xs = x : xs in xs
  

  utilise let "le nœud", la création d'un seul (:) constructeur qui se réfère à lui-même.

  

Answer 2

Dit simplement, les variables sont partagés, mais en fonction des applications ne le sont pas. Dans

repeat x = x : repeat x

c'est une coïncidence (à partir de la langue du point de vue) que le (co)appel récursif à répéter est avec le même argument. Donc, sans une optimisation supplémentaire (qui est appelé statique argument de transformation), la fonction sera appelée de nouveau et de nouveau.

Mais quand vous écrivez

repeat x = let xs = x : xs in xs

il n'y a pas récursive de la fonction des appels. Vous prenez un x, et de construire une valeur cyclique xs à l'utiliser. Tout partage est explicite.

Si vous souhaitez comprendre plus formellement, vous devez vous familiariser avec la sémantique de l'évaluation différée, comme Un Naturel de la Sémantique pour l'Évaluation différée.

Answer 3

Votre intuition xs communiqués est correct. À reformuler l'auteur de l'exemple en termes de répéter, au lieu de l'intégrale, lorsque vous écrivez:

repeat x = x : repeat x

la langue ne pas reconnaître que l' repeat x sur la droite est la même que la valeur produite par l'expression x : repeat x. Alors que si vous écrivez

repeat x = let xs = x : xs in xs

vous êtes explicitement la création d'une structure qui, lorsqu'il est évalué ressemble à ceci:

{hd: x, tl:|}
^          |
 \________/