Bagaimana menerapkan evaluasi malas if ()

10

Saat ini saya menerapkan evaluator ekspresi (ekspresi garis tunggal, seperti rumus) berdasarkan hal berikut:

  • ekspresi yang dimasukkan tokenized untuk memisahkan boolean literal, integer, desimal, string, fungsi, pengidentifikasi (variabel)
  • Saya menerapkan algoritma Shunting-yard (sedikit dimodifikasi untuk menangani fungsi dengan sejumlah variabel argumen) untuk menyingkirkan tanda kurung dan memesan operator dengan prioritas yang layak dalam urutan postfixed
  • halaman shunting-saya hanya menghasilkan antrian token (disimulasikan) (melalui array, bahasa Powerbuilder Classic saya dapat mendefinisikan objek, tetapi hanya memiliki array dinamis sebagai penyimpanan asli - bukan daftar yang benar, tidak ada kamus) yang saya evaluasi secara berurutan dengan mesin tumpukan sederhana

Penilai saya bekerja dengan baik, tetapi saya masih kehilangan if()dan saya bertanya-tanya bagaimana untuk melanjutkan.

Dengan evaluasi shunting-yard postfixed dan stack-based saya, jika saya menambahkan if()sebagai fungsi lain dengan bagian yang benar dan salah, satu if(true, msgbox("ok"), msgbox("not ok"))akan menampilkan kedua pesan sementara saya hanya ingin menunjukkan satu. Ini karena ketika saya perlu mengevaluasi suatu fungsi, semua argumennya telah dievaluasi dan ditempatkan di tumpukan.

Bisakah Anda memberi saya beberapa cara untuk diterapkan if()dengan cara yang malas?

Saya berpikir tentang memproses ini sebagai semacam makro, tetapi pada saat awal saya belum evaluasi kondisi. Mungkin saya perlu menggunakan jenis struktur selain antrian untuk menjaga secara terpisah kondisi dan ekspresi benar / salah? Untuk saat ini ekspresi diuraikan sebelum evaluasi, tetapi saya juga berencana untuk menyimpan representasi perantara sebagai jenis ekspresi yang dikompilasi untuk evaluasi di masa depan.

Sunting : setelah beberapa masalah, saya pikir saya bisa membangun representasi pohon ekspresi saya (AST bukannya aliran token linier), dari mana saya dapat dengan mudah mengabaikan satu atau cabang lain dari saya if().

language-design compiler interpreters Seki
sumber

Jawaban:

9

Ada dua opsi di sini.

1) Jangan menerapkan ifsebagai fungsi. Jadikan fitur bahasa dengan semantik khusus. Mudah dilakukan, tetapi kurang "murni" jika Anda ingin semuanya berfungsi.

2) Menerapkan semantik "panggil nama", yang jauh lebih rumit, tetapi memungkinkan sihir kompiler untuk mengurus masalah evaluasi malas sambil tetap ifsebagai fungsi alih-alih elemen bahasa. Bunyinya seperti ini:

ifadalah fungsi yang mengambil dua parameter, yang keduanya dinyatakan sebagai "dengan nama". Ketika kompiler melihat bahwa ia mengirimkan sesuatu ke parameter dengan nama, itu mengubah kode yang akan dihasilkan. Alih-alih mengevaluasi ekspresi dan meneruskan nilai, itu menciptakan penutupan yang mengevaluasi ekspresi, dan sebaliknya. Dan ketika memanggil parameter dengan nama di dalam fungsi, kompiler menghasilkan kode untuk mengevaluasi penutupan.

Mason Wheeler
sumber
Saya tidak yakin, tetapi haruskah "penutupan" menjadi "pencuri"? Hmm, mungkin tidak; hanya melihat halaman wikipedia: "thunk adalah penutupan tanpa parameter".
Ketika Anda mengatakan "panggilan dengan nama" yang Anda maksudkan secara global? Atau untuk panggilan-dengan-nama global hanya menerapkan tipe penutupan, maka fungsi if hanya membutuhkan 3 penutupan dan mengevaluasi dua (kondisi dan kemudian atau yang lain), tetapi tidak semua yang perlu diakui sebagai penutupan seperti panggilan-oleh- penuh nama semantik
Jimmy Hoffa
@ Matt: Istilah "thunk" dapat berarti beberapa hal lain dalam konteks pemrograman, dan "parameterless closure" bukan yang pertama yang saya pikirkan ketika saya mendengarnya. "Penutupan" jauh lebih jelas.
Mason Wheeler
1
@JimmyHoffa: Ketika saya mengatakan "panggil nama", saya merujuk pada gaya spesifik pengaturan argumen fungsi, yang seharusnya opsional. Sama seperti banyak bahasa yang ada akan memungkinkan Anda untuk memilih untuk melewati parameter dengan-nilai atau dengan-referensi, untuk skenario ini Anda perlu pilihan untuk melewati dengan nama.
Mason Wheeler
Sementara saran Anda tentang semantik "panggil nama" menunjukkan kepada saya beberapa poin menarik, itu sedikit berlebihan bagi evaluator saya yang bukan kompiler lengkap, karena panggilan fungsi saya adalah satu-baris (pikirkan tentang formula MS-excel). Saya berpikir saya bisa menambahkan langkah setelah antrian token dengan melakukan evaluasi semu tumpukan untuk menyimpulkan pohon panggilan. Seharusnya lebih mudah untuk mengetahui dari pohon cabang yang akan dibuang.
Seki
3

Daripada fungsi yang memiliki tanda tangan:

object if(bool, object, object)

Berikan tanda tangan:

object if(bool, object function(), object function())

Kemudian iffungsi Anda akan memanggil fungsi yang sesuai berdasarkan kondisi, hanya mengevaluasi salah satunya.

Makanan Tangan
sumber
1

Sangat mudah, jika Anda menyusun semuanya dengan malas. Anda harus memiliki beberapa cara untuk melihat apakah suatu nilai sudah dievaluasi, atau jika perlu lebih banyak evaluasi.

Kemudian Anda dapat melakukan hal berikut: Jika itu adalah literal atau variabel (apakah Anda memiliki itu ?, yaitu nama fungsi?), Dorong pada tumpukan. Jika ini merupakan aplikasi dari suatu fungsi, kompilasi secara terpisah, dan dorong titik masuk pada tumpukan.

Eksekusi program adalah, kemudian, hanya pengulangan sampai bagian atas tumpukan dievaluasi dan bukan fungsi. Jika tidak dievaluasi atau berfungsi, panggil kode bagian atas tumpukan.

Ingo
sumber