Menghapus rekursi - pandangan ke teori di balik layar

Saya baru di situs ini dan pertanyaan ini tentu saja bukan tingkat penelitian - tetapi oh well. Saya memiliki sedikit latar belakang dalam rekayasa perangkat lunak dan hampir tidak ada di CSTheory, tetapi saya merasa menarik. Untuk membuat cerita panjang pendek, saya ingin jawaban yang lebih rinci untuk yang berikut jika pertanyaan ini dapat diterima di situs ini.

Jadi, saya tahu bahwa setiap program rekursif memiliki analog berulang dan saya agak memahami penjelasan populer yang ditawarkan untuk itu dengan mempertahankan sesuatu yang mirip dengan "system stack" dan mendorong pengaturan lingkungan seperti alamat pengirim dll. Saya menemukan jenis gelombang tangan ini .

Menjadi sedikit lebih konkret, saya ingin (secara formal) melihat bagaimana seseorang membuktikan pernyataan ini dalam kasus di mana Anda memiliki fungsi memanggil rantai . Lebih lanjut, bagaimana jika ada beberapa pernyataan kondisional yang dapat menyebabkan F i membuat panggilan ke F j ? Yaitu, grafik panggilan fungsi potensial memiliki beberapa komponen yang sangat terhubung.$F_0 \rightarrow F_1 \ldots F_i \rightarrow F_{i+1} \ldots F_n \rightarrow F_0$$F_i$$F_j$

Saya ingin tahu bagaimana situasi ini dapat ditangani dengan membiarkan kami mengatakan beberapa konverter berulang untuk berulang. Dan apakah deskripsi handwavy yang saya sebutkan sebelumnya, cukup untuk masalah ini? Maksud saya lalu mengapa saya menemukan menghapus rekursi dalam beberapa kasus mudah. Secara khusus menghapus rekursi dari traversal pre-order dari pohon Binary benar-benar mudah - itu adalah pertanyaan wawancara standar tetapi menghilangkan rekursi jika post order selalu menjadi mimpi buruk bagi saya.

Apa yang sebenarnya saya tanyakan adalah pertanyaan$2$

(1) Apakah benar-benar ada bukti yang lebih formal (meyakinkan?) Bahwa rekursi dapat dikonversi menjadi iterasi?

(2) Jika teori ini benar-benar di luar sana, lalu mengapa saya menemukan, misalnya, membuat iterasi preorder lebih mudah dan postorder begitu sulit? (selain kecerdasan saya yang terbatas)

Jika saya mengerti dengan benar, Anda jelas tentang mengonversi fungsi yang tidak mengandung panggilan fungsi lain selain untuk diri mereka sendiri.

$F \to F_1 \to \dots \to F_n \to F$$F_1, \dots, F_n$$F$

$F_j$$F$$F_j \to \dots \to F \to \dots \to F_j$

f(0) = a
f(n) = f'(g(n-1))

g(0) = b
g(n) = g'(f(n-1))

dengan f'dan g'fungsi non-rekursif (atau setidaknya independen fdan g) menjadi

h(0) = (a,b)
h(n) = let (f,g) = h(n-1) in (f'(g), g'(f)) end

f(n) = let (f, _) = h(n) in f end
g(n) = let (_, g) = h(n) in g end

Ini secara alami meluas ke lebih banyak fungsi yang terlibat dan fungsi yang lebih rumit.

Ya, ada alasan meyakinkan untuk percaya bahwa rekursi dapat diubah menjadi iterasi. Inilah yang dilakukan oleh setiap kompiler ketika menerjemahkan kode sumber ke bahasa mesin. Untuk teori Anda harus mengikuti saran Dave Clarke. Jika Anda ingin melihat kode aktual yang mengubah rekursi menjadi kode non-rekursif, lihatlah machine.mldalam bahasa MiniML di Kebun Binatang PL saya (perhatikan bahwa loopfungsi di bagian bawah, yang benar-benar menjalankan kode, bersifat rekursif ekor sehingga dapat dikonversi sepele ke loop aktual).

Satu hal lagi. MiniML tidak mendukung fungsi yang saling rekursif. Tapi ini bukan masalah. Jika Anda memiliki rekursi timbal balik antar fungsi

rekursi dapat diekspresikan dalam bentuk peta rekursif tunggal

Anda mungkin ingin melihat mesin SECD . Bahasa fungsional (meskipun bisa bahasa apa saja) diterjemahkan ke dalam serangkaian instruksi yang mengatur hal-hal seperti menempatkan argumen tumpukan, "menjalankan" fungsi baru dan sebagainya, semua dikelola oleh satu loop sederhana.
Panggilan rekursif tidak pernah benar-benar dipanggil. Alih-alih, instruksi tubuh fungsi yang dipanggil ditempatkan pada tumpukan untuk dijalankan.

Pendekatan terkait adalah mesin CEK .

Keduanya sudah ada sejak lama, jadi ada banyak pekerjaan di sana. Dan tentu saja ada bukti bahwa mereka bekerja dan prosedur untuk "menyusun" suatu program menjadi instruksi SECD adalah linier dalam ukuran program (tidak harus memikirkan program).

Inti dari jawaban saya adalah bahwa ada prosedur otomatis untuk melakukan apa yang Anda inginkan. Sayangnya, transformasi tidak harus dalam hal yang segera mudah bagi seorang programmer untuk menafsirkan. Saya pikir kuncinya adalah bahwa ketika Anda ingin program iterize, Anda perlu menyimpan di stack apa yang perlu dilakukan program ketika Anda kembali dari panggilan fungsi iterized (ini disebut kelanjutan). Untuk beberapa fungsi (seperti fungsi rekursif ekor) kelanjutannya sepele. Bagi yang lain, kelanjutannya mungkin sangat kompleks, terutama jika Anda harus menyandikannya sendiri.

T : "Apakah benar-benar ada bukti yang lebih formal (meyakinkan?) Bahwa rekursi dapat dikonversi menjadi iterasi?"

A : Kelengkapan Turing dari Mesin Turing :-)

Bercanda terpisah, model mesin RASP (Random Access tersimpan program) setara dengan bagaimana mikroprosesor nyata bekerja dan set instruksi hanya berisi lompatan bersyarat (tanpa rekursi). Kemungkinan memodifikasi kode secara dinamis membuat tugas menerapkan subrutin dan panggilan rekursif lebih mudah.

Saya pikir Anda dapat menemukan banyak makalah / artikel tentang " konversi rekursif ke berulang " (lihat jawaban Dave atau hanya Google kata kunci), tetapi mungkin pendekatan yang kurang dikenal (dan praktis ) adalah penelitian terbaru tentang implementasi perangkat keras dari algoritma rekursif ( menggunakan bahasa VHDL yang "dikompilasi" langsung ke perangkat keras). Sebagai contoh, lihat makalah V.Sklyarov " implementasi algoritma rekursif berbasis FPGA " ( Makalah ini menyarankan metode baru untuk mengimplementasikan algoritma rekursif dalam perangkat keras .... .... Dua aplikasi praktis dari algoritma rekursif dalam penyortiran data dan area kompresi telah dipelajari. secara detail .... ).

Jika Anda terbiasa dengan bahasa yang mendukung lambdas maka satu jalan adalah melihat ke dalam transformasi CPS. Menghapus penggunaan tumpukan panggilan (dan rekursi khususnya) persis seperti yang dilakukan transformasi CPS. Ini mengubah program yang berisi panggilan prosedur menjadi program dengan hanya panggilan ekor (Anda dapat menganggap ini sebagai gotos, yang merupakan konstruksi berulang).

Transformasi CPS terkait erat dengan secara eksplisit menjaga stack panggilan dalam stack berbasis array tradisional, tetapi bukannya dalam array stack panggilan diwakili dengan penutupan terkait.

menurut pendapat saya pertanyaan ini kembali ke asal-usul definisi perhitungan dan sudah lama terbukti dengan ketat sekitar waktu itu ketika kalkulus lambda gereja (yang sangat menangkap konsep rekursi) terbukti setara dengan mesin Turing, dan berisi dalam terminologi yang masih digunakan "bahasa / fungsi rekursif". juga tampaknya ref kunci kemudian di sepanjang garis ini adalah sebagai berikut

Sebagaimana ditunjukkan oleh makalah Peter Landin tahun 1965 A Correspondence antara ALGOL 60 dan notasi Lambda Gereja, bahasa pemrograman prosedural berurutan dapat dipahami dalam hal kalkulus lambda, yang menyediakan mekanisme dasar untuk abstraksi prosedural dan penerapan prosedur (subprogram) aplikasi.

sebagian besar bkd tentang ini ada di halaman wikipedia ini tesis gereja-turing . Saya tidak yakin secara spesifik, tetapi artikel wikipedia tampaknya mengindikasikan Rosser (1939) yang pertama kali membuktikan kesetaraan ini antara kalkulus lambda dan mesin turing. mungkin / mungkin makalahnya memiliki mekanisme seperti tumpukan untuk mengubah panggilan lambda (mungkin rekursif) ke konstruksi tm?

Rosser, JB (1939). "Sebuah Eksposisi Informal Bukti Teorema Godel dan Teorema Gereja". Jurnal Logika Simbolik (Jurnal Logika Simbolik, Vol. 4, No. 2) 4 (2): 53-60. doi: 10.2307 / 2269059. JSTOR 2269059.

perhatikan tentu saja bagi siapa pun yang tertarik pada prinsip-prinsip bahasa Lisp modern dan Skema varian yang sengaja memiliki kemiripan yang kuat dengan kalkulus lambda. mempelajari kode juru bahasa untuk evaluasi ekspresi mengarah ke ide-ide yang semula terkandung dalam makalah untuk kelengkapan kalkulasi turing lambda.