Bagaimana menjembatani teori dan implementasi untuk loop sementara?

8

Saya sedang mengerjakan bahasa pemrograman kecil saya sendiri untuk tujuan pendidikan, dan saya mengalami sedikit masalah. Ada beberapa solusi berbeda untuk itu, tetapi semuanya tampaknya tidak sempurna - dan dari apa yang saya pahami, tidak perlu. Tetapi membaca buku-buku yang saya miliki dan pencarian google, saya tidak dapat menemukan solusi yang elegan.

Jadi, masalahnya adalah bahwa saya membangun kalkulus lambda dasar seperti yang saya mengerti. Saya telah mendefinisikan benar / salah sebagai istilah abstraksi. Saya dapat menggabungkan ini dengan fungsi yang harus dilakukan jika / maka / selain itu semacam perilaku. Masalahnya muncul dengan loop. Saya bisa mendefinisikan loop sementara dasar melalui rekursi, tetapi dalam praktiknya, itu menyebabkan stack overflow. Seperti yang saya pahami, solusi yang biasa dilakukan adalah dengan melakukan Tail Call Optimization, tetapi saya tidak melihat bagaimana saya bisa - kondisional didefinisikan dalam bahasa. Karena itu, kompiler tidak tahu bahwa tubuh loop sementara berada di posisi ekor.

Buku naga berfokus pada penerapan loop dengan asumsi ada label dan foto. Saya pasti bisa melakukan itu. Tampaknya seolah-olah bahasa lain yang tidak membangun dalam konstruksi perulangan setidaknya membangun dalam kondisi dan kemudian melakukan TCO. Dan saya pasti bisa melakukannya juga. Tetapi pemahaman saya adalah bahwa selama saya dapat menerapkan abstraksi dan melakukan reduksi, maka loop (dan yang lainnya) harus dapat dibangun dari blok dasar tersebut.

Jadi apa yang saya lewatkan? Atau apakah ini salah satu kasus di mana "Anda dapat memodelkan apa pun setelah Anda memiliki X dan Y" tidak sama dengan "Anda dapat memodelkan apa pun setelah Anda memiliki X dan Y di komputer nyata" dan built-in diperlukan untuk praktis tujuan?

Telastyn
sumber
Saya pikir Anda menjawab pertanyaan Anda sendiri dalam paragraf terakhir itu. Hanya karena teorinya mengatakan Anda dapat melakukan sesuatu tidak berarti praktis untuk melakukannya.
svick
1
Banyak bahasa yang memiliki kondisi dan rekursi serta menerapkan optimisasi panggilan-ekor. Cari di luar buku naga.
Dave Clarke
Biarkan saya meluruskan ini: Anda mulai dari yang murni λ-kalkulus? Artinya, tidak ada apa-apanya selainλdan abstraksi?
Andrej Bauer
svick - tentu saja, tetapi sebagai pembelajar, saya tidak dapat memastikan apakah itu yang terjadi di sini atau jika saya tidak mengetahui sesuatu. dave clarke - banyak bahasa telah dibangun di conditional dan menerapkan optimasi panggilan ekor. Saya telah melakukan pencarian dan tidak menghasilkan hasil untuk conditional dan TCO dalam bahasa. Jika Anda memiliki referensi yang saya abaikan ... Andrej Bauer - tidak cukup, tapi cukup dekat. Tidak ada tipe bawaan, tidak ada fungsi bawaan. Anda dapat mendeklarasikan fungsi dan menerapkan fungsi. Mendalami situasi khusus saya akan membuat pertanyaan yang jelek.
Telastyn
1
@ Raphael Menggunakan kalkulus lambda sebagai bahasa perantara adalah hal yang besar di tahun 1970-an-1980-an. Saya percaya tujuannya adalah untuk mendeteksi optimasi semantik. Pemahaman saya (berhati-hatilah bahwa saya bukan ahli dalam teknik kompilasi) adalah ternyata optimasi semantik sangat sulit, sedangkan optimasi lokal dapat membayar banyak dan lebih mudah dilihat pada bahasa dengan tugas register dan penggunaan goto yang moderat. Meskipun demikian ide-ide dari kalkulus lambda relevan untuk desain kompiler, misalnya ide tugas tunggal dan konsep kelanjutan.
Gilles 'SANGAT berhenti menjadi jahat'

Jawaban:

5

Jadi saya berhasil menyelesaikan masalah ini hari ini. Kode untuk loop sementara saya:

while (condition: ~>bool) (body: ~>void) => void {
    if condition { 
        body; 
        while condition body; 
    };
}

Ketika saya pergi untuk membangun ini ke CIL (runtime berbasis stack, penting untuk psuedocode, tidak penting untuk jawabannya) sepertinya:

ldarg 0
<build closure from { body; while condition body; }>
call if

Yang penting saya hilang adalah bahwa dalam whilekode, kondisional adalah hal di posisi ekor. Dari perspektif kompiler, fungsi blok dan sementara adalah dua fungsi terpisah, dengan dua "ekor" terpisah. Masing-masing mudah dievaluasi untuk posisi ekor, membuat optimisasi layak meskipun kurangnya persyaratan bawaan.

Telastyn
sumber
5

Saya pikir Anda kehilangan gagasan kelanjutan . Meskipun kompiler Anda mungkin tidak mengandalkan gagasan itu, sebagai perancang kompiler dengan bahasa fungsional sebagai bahasa sumber atau menengah (atau target), penting untuk memahami gagasan itu dan mengingatnya.

Kelanjutan sepotong kode menjelaskan apa yang keluar dari kode. Dalam istilah imperatif, ini tidak hanya mencakup lokasi tempat kode melompat atau jatuh, tetapi juga status program (tumpukan dan tumpukan) pada saat itu. Dalam istilah kalkulus lambda, kelanjutan subterm adalah konteks di mana ia dievaluasi.

Ketika Anda menerjemahkan kode imperatif ke dalam bahasa fungsional, salah satu kesulitannya adalah mengatasi kode yang dapat keluar dengan beberapa cara berbeda. Misalnya, kode dapat mengembalikan atau menaikkan pengecualian. Atau, badan loop dapat melanjutkan untuk memeriksa kondisi lagi atau keluar dari loop sama sekali ( breakmembangun). Ada dua cara utama untuk mengatasinya:

  • Multiplexing: membuat kode mengembalikan tipe penjumlahan untuk semua kemungkinan keluar. Dalam kasus loop body, itu akan menjadi Continue | Break.
  • Gaya meneruskan kelanjutan : menerjemahkan kode ke fungsi yang mengambil parameter tambahan yang merupakan fungsi yang akan dieksekusi berikutnya. Parameter tambahan ini adalah kelanjutan fungsi. Kode yang dapat keluar dengan cara yang berbeda menerima satu parameter tersebut untuk masing-masing cara.

Gaya kelanjutan-kelanjutan adalah bagaimana struktur data dimasukkan ke dalam kalkulus lambda murni. Misalnya, ketika Anda menyatakan true sebagaiλx,y.x dan salah sebagai λx,y.y, argumennya x dan y adalah dua kemungkinan kelanjutan, dan boolean adalah pernyataan "jika" yang memilih salah satu atau kelanjutan lainnya.

Dalam gaya kelanjutan-lewat,

while (condition) body

diterjemahkan ke

let rec f (continuation) =
  if (condition, body (f (continuation)), continuation)

Dalam penerjemahan suatu program dalam bahasa imperatif tipikal dengan gaya kelanjutan-kelanjutan, kelanjutan selalu menjadi hal terakhir yang dijalankan oleh sepotong kode. Misalnya, kelanjutan di bodyatas dijalankan setelah semua kode body, jadi pengoptimalan panggilan ekor menghasilkan pembebasan semua variabel lokal bodysebelum menjalankan kelanjutan.

Beberapa bahasa menawarkan kelanjutan kelas satu dengan konstruksi seperti panggilan-dengan-kelanjutan saat ini . Panggilan / cc pada umumnya tidak dapat menerima pengoptimalan panggilan - ini sebenarnya bisa menjadi operasi yang agak mahal karena dapat menyebabkan duplikasi seluruh kondisi program.

Gilles 'SANGAT berhenti menjadi jahat'
sumber