Como o 'desmatamento' remove 'árvores' de um programa?

Eu acho que entendo como o desmatamento consome e produz uma lista ao mesmo tempo (de uma dobra e uma função desdobrada - veja esta boa resposta no CodeReview aqui ), mas quando eu comparei isso com a entrada da Wikipedia sobre a técnica que ele falou sobre 'remover árvores de um programa.

Entendo como um programa pode ser analisado em uma árvore de análise sintática (isso mesmo?), Mas qual é o significado desse uso do desmatamento para algum tipo de simplificação (é?) Dos programas? E como eu faria isso no meu código?

Yatima2975 parece ter coberto suas duas primeiras perguntas, tentarei cobrir a terceira. Para fazer isso, tratarei um caso irrealisticamente simples, mas tenho certeza de que você será capaz de imaginar algo mais realista.

Imagine que você deseja calcular a profundidade de toda a árvore binária da ordem . O tipo de árvores binárias (sem rótulo) é (na sintaxe Haskell):$n$

type Tree = Leaf | Node Tree Tree

Agora a árvore completa da ordem é:$n$

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

E a profundidade de uma árvore é calculada por

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

$\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))

Isso evita a alocação de memória da árvore completa e a necessidade de executar a correspondência de padrões, o que melhora muito o desempenho. Além disso, se você adicionar a otimização

max t t --> t

$\mathrm{full\_depth}$

A única compilador tradicional que executa o desmatamento automática é GHC, e se bem me lembro, esta é executada somente ao compor built-in funções (por razões técnicas).

Primeiro, as listas são um tipo de árvore. Se representamos uma lista como uma lista vinculada , é apenas uma árvore cujo cada nó tem 1 ou 0 descendentes.

Árvores de análise são apenas uma utilização de árvores como uma estrutura de dados. As árvores têm muitas aplicações na ciência da computação, incluindo classificação, implementação de mapas, matrizes associativas etc.

Em geral, lista, árvores etc. são estruturas de dados recursivas: Cada nó contém algumas informações e outra instância da mesma estrutura de dados. Dobrar é uma operação sobre todas essas estruturas que transforma recursivamente os nós em valores "de baixo para cima". O desdobramento é o processo inverso, converte valores em nós "de cima para baixo".

Para uma dada estrutura de dados, podemos construir mecanicamente suas funções de dobrar e desdobrar.

Como exemplo, vamos fazer listas. (Usarei Haskell para os exemplos, pois é digitado e sua sintaxe é muito limpa.) Lista é um final ou um valor e uma "cauda".

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

Agora vamos imaginar que estamos dobrando uma lista. Em cada etapa, temos o nó atual a ser dobrado e já dobramos seus subnós recursivos. Podemos representar esse estado como

data ListF a r = NilF | ConsF a r

onde ré o valor intermediário construído dobrando a sub-lista. Isso nos permite expressar uma função dobrável sobre as listas:

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

Nós convertemos List em ListFdobrando recursivamente sobre sua sublist e, em seguida, usamos uma função definida em ListF. Se você pensar bem, esta é apenas outra representação do padrão 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

Podemos construir unfoldListda mesma maneira:

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')

Novamente, é apenas outra representação de unfoldr:

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

(Notar que Maybe (a, r) é isomórfico para ListF a r.)

E também podemos construir uma função de desmatamento:

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)

Simplesmente deixa de fora o intermediário Liste funde as funções de dobrar e desdobrar.

O mesmo procedimento pode ser aplicado a qualquer estrutura de dados recursiva. Por exemplo, uma árvore cujos nós podem ter 0, 1, 2 ou descendentes com valores em nós com 1 ou 0 ramificações:

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)

Claro, podemos criar deforestTree tão mecanicamente quanto antes.

(Normalmente, expressaríamos de forma treeFoldmais conveniente como:

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

)

Vou deixar de fora os detalhes, espero que o padrão seja óbvio.

Veja também:

• Catamorfismo
• Anamorfismo
• Hylomorfismo

É um pouco confuso, mas o desmatamento é aplicado (em tempo de compilação) para eliminar as árvores intermediárias que seriam criadas (em tempo de execução). O desmatamento não envolve cortar partes da árvore de sintaxe abstrata (que é a eliminação de galhos mortos :-)

Outra coisa que pode ter despertado você é que listas são árvores, apenas muito desequilibradas!