Comment la «déforestation» supprime-t-elle les «arbres» d'un programme?

Je pense comprendre comment la déforestation consomme et produit une liste en même temps (à partir d'une fonction de pliage et de dépliage - voir cette bonne réponse sur CodeReview ici ), mais quand je l'ai comparé avec l' entrée de wikipedia sur la technique dont il a parlé de `` supprimer arbres »d'un programme.

Je comprends comment un programme peut être analysé dans un arbre d'analyse syntaxique (est-ce vrai?), Mais quel est le sens de cette utilisation de la déforestation pour une sorte de simplification (est-ce?) Des programmes? Et comment pourrais-je le faire avec mon code?

Yatima2975 semble avoir couvert vos deux premières questions, je vais essayer de couvrir la troisième. Pour ce faire, je traiterai un cas d'une simplicité irréaliste, mais je suis sûr que vous pourrez imaginer quelque chose de plus réaliste.

Imaginez que vous vouliez calculer la profondeur de l' arbre binaire complet d'ordre . Le type d'arbres binaires (sans étiquette) est (dans la syntaxe Haskell):$n$

type Tree = Leaf | Node Tree Tree

Maintenant, l'arbre complet d'ordre est:$n$

full : Int -> Tree
full n | n == 0 = Leaf
full n = Node (full (n-1)) (full (n-1))

Et la profondeur d'un arbre est calculée par

depth : Tree -> Int
depth Leaf = 0
depth (Node t1 t2) = 1 + max (depth t1) (depth t2)

Vous pouvez maintenant voir que tout calcul de va d'abord construire l'arborescence complète d'ordre$\mathrm{depth}\ (\mathrm{full}\ n)$$n$$\mathrm{full}$$\mathrm{depth}$$\mathrm{depth}\ (\mathrm{full}\ n)$$\mathrm{full\_depth}$

full_depth : Int -> Int
full_depth n | n == 0 = 0
full_depth n = 1 + max (full_depth (n-1)) (full_depth (n-1))

Cela évite l'allocation de mémoire de l'arborescence complète et la nécessité d'effectuer une correspondance de modèle, ce qui améliore considérablement les performances. De plus, si vous ajoutez l'optimisation

max t t --> t

$\mathrm{full\_depth}$

Le seul compilateur grand public qui effectue la déforestation automatique est GHC, et si je me souviens bien, cela n'est effectué que lors de la composition de fonctions intégrées (pour des raisons techniques).

Tout d'abord, les listes sont une sorte d'arbres. Si nous représentons une liste sous forme de liste liée , il s'agit simplement d'un arbre dont chaque nœud a 1 ou 0 descendants.

Les arbres d'analyse ne sont qu'une utilisation des arbres comme structure de données. Les arbres ont de nombreuses applications en informatique, notamment le tri, la mise en œuvre de cartes, les tableaux associatifs, etc.

En général, la liste, les arbres, etc. sont des structures de données récursives: chaque nœud contient des informations et une autre instance de la même structure de données. Le pliage est une opération sur toutes ces structures qui transforme récursivement les nœuds en valeurs "ascendantes". Le dépliage est le processus inverse, il convertit les valeurs en nœuds "de haut en bas".

Pour une structure de données donnée, on peut construire mécaniquement leurs fonctions de pliage et de dépliage.

Par exemple, prenons des listes. (Je vais utiliser Haskell pour les exemples car il est tapé et sa syntaxe est très propre.) La liste est soit une fin, soit une valeur et une "queue".

data List a = Nil | Cons a (List a)

Imaginons maintenant que nous plions une liste. À chaque étape, nous avons le nœud actuel à plier et nous avons déjà plié ses sous-nœuds récursifs. Nous pouvons représenter cet état comme

data ListF a r = NilF | ConsF a r

où rest la valeur intermédiaire construite en repliant la sous-liste. Cela nous permet d'exprimer une fonction de pliage sur des listes:

foldList :: (ListF a r -> r) -> List a -> r
foldList f Nil            = f NilF
foldList f (Cons x xs)    = f (ConsF x (foldList f xs))

Nous convertissons Listen ListFrepliant récursivement sa sous-liste, puis utilisons une fonction définie sur ListF. Si vous y réfléchissez, ce n'est qu'une autre représentation de la norme foldr:

foldr :: (a -> r -> r) -> r -> List a -> r
foldr f z = foldList g
  where
    g NilF          = z
    g (ConsF x r)   = f x r

On peut construire unfoldListde la même manière:

unfoldList :: (r -> ListF a r) -> r -> List a
unfoldList f r = case f r of
                  NilF        -> Nil
                  ConsF x r'  -> Cons x (unfoldList f r')

Encore une fois, c'est juste une autre représentation de unfoldr:

unfoldr :: (r -> Maybe (a, r)) -> r -> [a]

(Notez que Maybe (a, r)c'est isomorphe à ListF a r.)

Et nous pouvons aussi construire une fonction de déforestation:

deforest :: (ListF a r -> r) -> (s -> ListF a s) -> s -> r
deforest f u s = f (map (deforest f u) (u s))
  where
    map h NilF        = NilF
    map h (ConsF x r) = ConsF x (h r)

Il supprime simplement l'intermédiaire Listet fusionne les fonctions de pliage et de dépliage.

La même procédure peut être appliquée à toute structure de données récursive. Par exemple, un arbre dont les nœuds peuvent avoir 0, 1, 2 ou descendants avec des valeurs sur des nœuds à 1 ou 0 branches:

data Tree a = Bin (Tree a) (Tree a) | Un a (Tree a) | Leaf a

data TreeF a r = BinF r r | UnF a r | LeafF a

treeFold :: (TreeF a r -> r) -> Tree a -> r
treeFold f (Leaf x)       = f (LeafF x)
treeFold f (Un x r)       = f (UnF x (treeFold f r))
treeFold f (Bin r1 r2)    = f (BinF (treeFold f r1) (treeFold f r2))

treeUnfold :: (r -> TreeF a r) -> r -> Tree a
treeUnfold f r = case f r of
                  LeafF x         -> Leaf x
                  UnF x r         -> Un x (treeUnfold f r)
                  BinF r1 r2      -> Bin (treeUnfold f r1) (treeUnfold f r2)

Bien sûr, nous pouvons créer deforestTreeaussi mécaniquement qu'auparavant.

(Habituellement, nous exprimons treeFoldplus facilement:

treeFold' :: (r -> r -> r) -> (a -> r -> r) -> (a -> r) -> Tree a -> r

)

Je vais laisser de côté les détails, j'espère que le motif est évident.

Voir également:

• Catamorphisme
• Anamorphisme
• Hylomorphisme

C'est un peu déroutant, mais la déforestation est appliquée (au moment de la compilation) pour éliminer les arbres intermédiaires qui seraient créés (au moment de l'exécution). La déforestation n'implique pas de pirater des parties de l'arbre de syntaxe abstraite (c'est l'élimination des branches mortes :-)

Une autre chose qui vous a peut-être dérouté est que les listes sont des arbres, juste des arbres très déséquilibrés!