Bagaimana 'deforestasi' menghilangkan 'pohon' dari suatu program?

Saya pikir mengerti bagaimana deforestasi mengkonsumsi dan menghasilkan daftar pada saat yang sama (dari lipatan dan fungsi buka - lihat jawaban yang bagus ini di CodeReview di sini ), tetapi ketika saya membandingkannya dengan entri wikipedia pada teknik ini, ia berbicara tentang 'menghapus' pohon dari sebuah program.

Saya mengerti bagaimana suatu program dapat diuraikan menjadi pohon parse sintaksis (apakah itu benar?), Tetapi apa arti dari penggunaan penggundulan hutan ini untuk semacam penyederhanaan (bukan?) Program? Dan bagaimana saya melakukannya dengan kode saya?

Yatima2975 tampaknya telah membahas dua pertanyaan pertama Anda, saya akan mencoba untuk membahas yang ketiga. Untuk melakukan ini, saya akan menangani kasus sederhana yang tidak realistis, tetapi saya yakin Anda akan dapat membayangkan sesuatu yang lebih realistis.

Bayangkan Anda ingin menghitung kedalaman pohon biner penuh urutan . Jenis pohon biner (tidak berlabel) adalah (dalam sintaksis Haskell):$n$

type Tree = Leaf | Node Tree Tree

Sekarang pohon urutan penuh adalah:$n$

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

Dan kedalaman pohon dihitung oleh

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

Sekarang Anda dapat melihat bahwa perhitungan apa pun dari pertama-tama akan membangun pohon urutan penuh menggunakan dan kemudian mendekonstruksi pohon itu menggunakan . Deforestasi bergantung pada pengamatan bahwa pola seperti itu (konstruksi diikuti oleh dekonstruksi) seringkali dapat mengalami hubungan pendek : kita dapat mengganti panggilan apa pun ke dengan satu panggilan ke :n f u l l d e p t h d e p t h ( f u l l n ) f u l l _ d e p t $\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))

Ini menghindari alokasi memori pohon lengkap, dan kebutuhan untuk melakukan pencocokan pola, yang sangat meningkatkan kinerja. Selain itu, jika Anda menambahkan optimasi

max t t --> t

Maka Anda telah mengubah prosedur waktu eksponensial menjadi waktu linear ... Akan lebih baik jika ada optimasi tambahan yang mengakui bahwa adalah identitas pada bilangan bulat, tetapi saya tidak yakin bahwa ada optimasi digunakan dalam praktik.$\mathrm{full\_depth}$

Satu-satunya compiler utama yang melakukan deforestasi otomatis GHC, dan jika saya ingat benar, ini dilakukan hanya saat menulis built-in fungsi (untuk alasan teknis).

Pertama, daftar adalah sejenis pohon. Jika kami mewakili daftar sebagai daftar tertaut , itu hanya pohon yang setiap simpulnya memiliki keturunan 1 atau 0.

Pohon parse hanyalah pemanfaatan pohon sebagai struktur data. Pohon memiliki banyak banyak aplikasi dalam ilmu komputer, termasuk menyortir, mengimplementasikan peta, array asosiatif, dll.

Secara umum, daftar, pohon dll adalah struktur data rekursif: Setiap node berisi beberapa informasi dan contoh lain dari struktur data yang sama. Lipat adalah operasi atas semua struktur seperti itu yang secara rekursif mengubah node menjadi nilai "bottom up". Berlangsung adalah proses sebaliknya, itu mengkonversi nilai menjadi node "top down".

Untuk struktur data yang diberikan, kita dapat secara mekanis membangun fungsi lipatan dan lipatannya.

Sebagai contoh, mari kita ambil daftar. (Saya akan menggunakan Haskell untuk contoh-contoh saat diketik dan sintaksnya sangat bersih.) Daftar bisa berupa akhir atau nilai dan "ekor".

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

Sekarang mari kita bayangkan kita melipat daftar. Pada setiap langkah, kami memiliki simpul saat ini untuk dilipat dan kami telah melipat sub-node rekursifnya. Kita dapat mewakili negara ini sebagai

data ListF a r = NilF | ConsF a r

di mana rnilai menengah dibangun dengan melipat sublist. Ini memungkinkan kami untuk mengekspresikan fungsi lipat dari daftar:

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

Kami mengkonversi Listmenjadi ListFdengan secara rekursif melipat lebih dari sublist dan kemudian menggunakan fungsi yang ditentukan ListF. Jika Anda memikirkannya, ini hanyalah representasi standar lain 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

Kita dapat membangun unfoldListdengan cara yang sama:

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

Sekali lagi, ini hanyalah representasi lain dari unfoldr:

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

(Perhatikan itu Maybe (a, r)isomorfik untuk ListF a r.)

Dan kita dapat membangun fungsi deforestasi juga:

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)

Ini hanya meninggalkan fungsi antara Listdan sekering fungsi lipat dan terbuka bersama.

Prosedur yang sama dapat diterapkan pada struktur data rekursif apa pun. Misalnya, pohon yang simpulnya dapat memiliki 0, 1, 2 atau turunan dengan nilai pada simpul bercabang 1- atau 0:

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)

Tentu saja, kita dapat membuat deforestTreesecara mekanis seperti sebelumnya.

(Biasanya, kami akan mengekspresikan treeFoldlebih nyaman sebagai:

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

)

Saya akan meninggalkan detailnya, saya harap polanya jelas.

Lihat juga:

• Catamorfisme
• Anamorfisme
• Hylomorfisme

Agak membingungkan, tetapi deforestasi diterapkan (pada waktu kompilasi) untuk menghilangkan pohon-pohon perantara yang akan dibuat (pada saat run time). Deforestasi tidak melibatkan peretasan bagian-bagian dari pohon sintaksis abstrak (itu adalah penghapusan cabang mati :-)

Hal lain yang mungkin membuat Anda terlempar adalah bahwa daftar adalah pohon, hanya yang sangat tidak seimbang!