Apa sifat-sifat bahasa pemrograman yang membuat kompilasi tidak mungkin?

72

Pertanyaan:

"Properti tertentu dari bahasa pemrograman mungkin mensyaratkan bahwa satu-satunya cara agar kode yang tertulis di dalamnya dieksekusi adalah dengan interpretasi. Dengan kata lain, kompilasi ke kode mesin asli dari CPU tradisional tidak dimungkinkan. Apa properti ini?"

Penyusun: Prinsip dan Praktek oleh Parag H. Dave dan Himanshu B. Dave (2 Mei 2012)

Buku ini tidak memberikan petunjuk tentang jawabannya. Saya mencoba menemukan jawaban pada Konsep Bahasa Pemrograman (SEBESTA), tetapi tidak berhasil. Pencarian web juga sedikit berhasil. Apakah Anda punya petunjuk?

Anderson Nascimento Nunes
sumber
31
Terkenal, Perl bahkan tidak bisa diurai . Selain itu, klaim tampaknya salah sepele tanpa asumsi lebih lanjut: jika ada seorang juru bahasa, saya selalu dapat menggabungkan juru bahasa dan kode dalam satu executable, voila.
Raphael
4
@ Raphael: Ide bagus, tapi ... 1) Anda mengasumsikan kode tersedia sebelum dieksekusi. Itu tidak berlaku untuk penggunaan interaktif. Tentu, Anda dapat menggunakan kompilasi just-in-time ke kode asli pada pernyataan bash atau isi stack PostScript, tapi itu ide yang cukup gila. 2) Ide Anda sebenarnya tidak mengkompilasi kode: bundel bukan versi kode yang dikompilasi, tetapi masih merupakan juru bahasa untuk kode tersebut.
reinierpost
7
Di masa lalu yang baik saya memiliki program gwbasic mengedit diri (gwbasic menyimpan program dasar dalam semacam bytecode). Saat ini saya tidak bisa memikirkan cara yang waras untuk mengkompilasi mereka ke kode mesin asli sambil mempertahankan kemampuan mereka untuk mengedit sendiri.
PlasmaHH
15
@PlasmaHH: Self Modifying Code kembali ke tahun 1948. Kompiler pertama ditulis pada tahun 1952. Konsep kode modifikasi diri ditemukan dalam kode mesin asli.
Mooing Duck
10
@reinierpost Raphael mengambil sikap teoretis tentang masalah ini. Ini memiliki kelebihan menunjukkan keterbatasan konseptual pertanyaan. Kompilasi adalah terjemahan dari bahasa S ke bahasa T. Bahasa T bisa merupakan ekstensi dari S yang dapat ditafsirkan kode dalam bahasa lain. Jadi bundling S dan interpreternya adalah sebuah program dalam bahasa T. Tampaknya absurd bagi seorang insinyur, tetapi itu menunjukkan bahwa tidaklah mudah untuk merumuskan pertanyaan dengan bermakna. Bagaimana Anda membedakan proses kompilasi yang dapat diterima dari yang tidak dapat diterima (seperti Raphael) dari sudut pandang teknik?
babou

Jawaban:

61

Perbedaan antara kode yang ditafsirkan dan dikompilasi mungkin fiksi, seperti yang digarisbawahi oleh komentar Raphael :

the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...

Faktanya adalah bahwa kode selalu diinterpretasikan, oleh perangkat lunak, oleh perangkat keras atau kombinasi keduanya, dan proses kompilasi tidak dapat menentukan mana yang akan.

Apa yang Anda anggap kompilasi adalah proses terjemahan dari satu bahasa (untuk sumber) ke bahasa lain (untuk target). Dan, juru bahasa untuk biasanya berbeda dari interpreter untuk .T S TSTST

Program ini disusun diterjemahkan dari satu bentuk sintaksis ke bentuk sintaksis lain , sehingga, mengingat semantik dimaksudkan dari bahasa dan , dan P T memiliki perilaku komputasi yang sama, hingga beberapa hal yang Anda biasanya mencoba untuk berubah, mungkin untuk mengoptimalkan, seperti kompleksitas atau efisiensi sederhana (waktu, ruang, permukaan, konsumsi energi). Saya mencoba untuk tidak berbicara tentang kesetaraan fungsional, karena akan membutuhkan definisi yang tepat.P T S T P SPSPTSTPSPT

Beberapa kompiler telah benar-benar digunakan hanya untuk mengurangi ukuran kode, bukan untuk "meningkatkan" eksekusi. Ini adalah kasus untuk bahasa yang digunakan dalam sistem Plato (meskipun mereka tidak menyebutnya kompilasi).

Anda dapat mempertimbangkan kode Anda sepenuhnya dikompilasi jika setelah proses kompilasi, Anda tidak perlu lagi interpreter untuk . Paling tidak, itulah satu-satunya cara saya dapat membaca pertanyaan Anda, sebagai rekayasa daripada pertanyaan teoretis (karena, secara teoritis, saya selalu dapat membangun kembali penerjemah).S

Satu hal yang dapat menimbulkan masalah, afaik, adalah meta-sirkularitas . Saat itulah sebuah program akan memanipulasi struktur sintaksis dalam bahasa sumbernya sendiri , menciptakan fragmen program yang kemudian diintepretasi seolah-olah mereka telah menjadi bagian dari program aslinya. Karena Anda dapat menghasilkan fragmen program yang sewenang-wenang dalam bahasa S sebagai hasil perhitungan sewenang-wenang memanipulasi fragmen sintaksis yang tidak bermakna, saya kira Anda bisa membuatnya hampir mustahil (dari sudut pandang teknik) untuk mengkompilasi program ke dalam bahasa T , sehingga sekarang menghasilkan fragmen T . Oleh karena itu penerjemah untuk S akan diperlukan, atau setidaknya kompiler dari S keSSTTSS untukkompilasi on-the-fly onfragmen yang dihasilkan dalam S (lihat jugadokumen ini).TS

Tapi saya tidak yakin bagaimana ini bisa diformalkan dengan benar (dan tidak punya waktu sekarang untuk itu). Dan tidak mungkin adalah kata besar untuk masalah yang tidak diformalkan.

Keterangan lebih lanjut

Ditambahkan setelah 36 jam. Anda mungkin ingin melewatkan sekuel yang sangat panjang ini.

Banyak komentar untuk pertanyaan ini menunjukkan dua pandangan tentang masalah: pandangan teoretis yang melihatnya sebagai tidak berarti, dan pandangan teknik yang sayangnya tidak begitu mudah diformalkan.

Ada banyak cara untuk melihat interpretasi dan kompilasi, dan saya akan mencoba membuat sketsa beberapa. Saya akan berusaha menjadi informal seperti yang saya bisa lakukan

Diagram Tombstone

Salah satu formalisasi awal (awal 1960-an hingga akhir 1990) adalah diagram T atau Tombstone . Diagram-diagram ini disajikan dalam elemen grafis komposable bahasa implementasi interpreter atau kompiler, bahasa sumber ditafsirkan atau dikompilasi, dan bahasa target dalam kasus kompiler. Versi yang lebih rumit dapat menambahkan atribut. Representasi grafis ini dapat dilihat sebagai aksioma, aturan inferensi, dapat digunakan untuk menghasilkan generasi prosesor secara otomatis dari bukti keberadaannya dari aksioma, à la Curry-Howard (walaupun saya tidak yakin hal itu dilakukan pada tahun enam puluhan :).

Evaluasi parsial

Pandangan lain yang menarik adalah paradigma evaluasi parsial . Saya mengambil pandangan sederhana tentang program sebagai semacam implementasi fungsi yang menghitung jawaban yang diberikan beberapa data input. Kemudian seorang juru untuk bahasa S adalah sebuah program yang mengambil program p S ditulis dalam S dan data d untuk program tersebut, dan menghitung hasil sesuai dengan semantik S . Evaluasi parsial adalah teknik untuk mengkhususkan program dua argumen yang 1 dan yang 2 , ketika hanya satu argumen, mengatakan sebuah 1sayaSShalSSdSSebuah1Sebuah2Sebuah1, dikenal. Maksudnya adalah untuk memiliki evaluasi yang lebih cepat ketika Anda akhirnya mendapatkan argumen kedua . Hal ini sangat berguna jika suatu 2 perubahan lebih sering daripada sebuah 1 karena biaya evaluasi parsial dengan sebuah 1 dapat diamortisasi pada semua perhitungan di mana hanya satu 2 berubah.Sebuah2Sebuah2Sebuah1Sebuah1Sebuah2

Ini adalah situasi yang sering terjadi dalam perancangan algoritma (seringkali menjadi topik dari komentar pertama pada SE-CS), ketika beberapa bagian yang lebih statis dari data diproses sebelumnya, sehingga biaya pra-pemrosesan dapat diamortisasi pada semua aplikasi dari algoritma dengan lebih banyak bagian variabel dari data input.

Ini juga merupakan situasi para penafsir, karena argumen pertama adalah program yang akan dieksekusi, dan biasanya dieksekusi berkali-kali dengan data yang berbeda (atau meminta sub-bagian dieksekusi berkali-kali dengan data yang berbeda). Oleh karena itu menjadi ide alami untuk mengkhususkan juru bahasa untuk evaluasi yang lebih cepat dari program yang diberikan dengan sebagian mengevaluasinya pada program ini sebagai argumen pertama. Ini dapat dilihat sebagai cara menyusun program, dan telah ada pekerjaan penelitian yang signifikan untuk menyusun dengan mengevaluasi sebagian penerjemah pada argumen (program) pertamanya.

Teorema Smn

Poin bagus tentang pendekatan evaluasi parsial adalah bahwa ia berakar pada teori (meskipun teori dapat menjadi pembohong), terutama dalam teorema Smn Kleene . Saya mencoba di sini untuk memberikan presentasi intuitif tentang itu, berharap itu tidak akan mengecewakan para ahli teori murni.

Dengan penomoran Gödel dari fungsi rekursif, Anda dapat melihat φ sebagai perangkat keras Anda, sehingga mengingat nomor Gödel p (baca kode objek ) dari sebuah program φ p adalah fungsi yang didefinisikan oleh p (yaitu dikomputasi oleh kode objek pada perangkat keras Anda ).φφhalφhalhal

Dalam bentuknya yang paling sederhana, teorema ini dinyatakan dalam wikipedia sebagai berikut (hingga perubahan kecil dalam notasi):

Diberikan penomoran Gödel dari fungsi rekursif, ada fungsi rekursif primitif σ dari dua argumen dengan properti berikut: untuk setiap angka Gödel q dari fungsi yang dapat dihitung sebagian f dengan dua argumen, ekspresi φ σ ( q , x ) ( y ) dan f ( x , y ) didefinisikan untuk kombinasi bilangan asli x dan y yang sama , dan nilainya sama untuk kombinasi tersebut. Dengan kata lain, persamaan fungsi ekstensional berikut berlaku untuk setiapφσqfφσ(q,x)(y)f(x,y)xy : xφσ(q,x)λy.φq(x,y).

Sekarang, dengan mengambil sebagai interpreter I S , x sebagai kode sumber program p S , dan y sebagai data d untuk program itu, kita dapat menulis: qISxpSydφσ(IS,pS)λd.φIS(pS,d).

dapat dilihat sebagai pelaksanaan penafsir saya S pada perangkat keras, yaitu, sebagai kotak hitam siap untuk menafsirkan program yang ditulis dalam bahasa S .φISISS

Fungsi dapat dilihat sebagai fungsi yang mengkhususkan juru bahasa I S untuk program P S , seperti dalam evaluasi parsial. Dengan demikian jumlah Gödel σ ( I S , p S ) dapat dilihat memiliki kode objek yang versi terkompilasi program p S .σISPSσ(IS,pS)pS

Jadi fungsinya dapat dilihat sebagai fungsi yang mengambil sebagai argumen kode sumber dari program q S yang ditulis dalam bahasa S , dan mengembalikan versi kode objek untuk program itu. Jadi C S adalah apa yang biasanya disebut sebuah kompiler.CS=λqS.σ((sayaS,qS)qSSCS

Beberapa kesimpulan

Namun, seperti yang saya katakan: "teori bisa menjadi pembohong", atau sebenarnya sepertinya satu. Masalahnya adalah kita tidak mengetahui fungsi . Sebenarnya ada banyak fungsi seperti itu, dan tebakan saya adalah bahwa pembuktian teorema dapat menggunakan definisi yang sangat sederhana untuk itu, yang mungkin tidak lebih baik, dari sudut pandang teknik, daripada solusi yang diusulkan oleh Raphael: untuk sekadar membundel kode sumber q S dengan interpreter saya S . Ini selalu bisa dilakukan, sehingga kita dapat mengatakan: kompilasi selalu mungkin.σqSsayaS

Memformalkan gagasan yang lebih ketat tentang apa itu kompiler akan memerlukan pendekatan teoretis yang lebih halus. Saya tidak tahu apa yang mungkin telah dilakukan ke arah itu. Pekerjaan yang sangat nyata dilakukan pada evaluasi parsial lebih realistis dari sudut pandang teknik. Dan tentu saja ada teknik lain untuk menulis kompiler, termasuk ekstraksi program dari bukti spesifikasi mereka, seperti yang dikembangkan dalam konteks tipe-teori, berdasarkan isomorfisma Curry-Howard (tapi saya keluar dari domain kompetensi saya) .

Tujuan saya di sini adalah untuk menunjukkan bahwa ucapan Raphael bukanlah "gila", tetapi pengingat yang waras bahwa segala sesuatu tidak jelas, dan bahkan tidak sederhana. Mengatakan bahwa sesuatu itu tidak mungkin adalah pernyataan yang kuat yang memang membutuhkan definisi dan bukti yang tepat, jika hanya untuk memiliki pemahaman yang tepat tentang bagaimana dan mengapa itu tidak mungkin . Tetapi membangun formalisasi yang tepat untuk mengekspresikan bukti semacam itu mungkin cukup sulit.

Ini mengatakan, bahkan jika fitur tertentu tidak dapat dikompilasi, dalam pengertian yang dipahami oleh para insinyur, teknik kompilasi standar selalu dapat diterapkan pada bagian-bagian dari program yang tidak menggunakan fitur seperti itu, seperti yang dinyatakan oleh jawaban Gilles.

Untuk mengikuti kata kunci Gilles bahwa, tergantung pada bahasanya, beberapa hal dapat dilakukan pada waktu kompilasi, sementara yang lain harus dilakukan pada saat run-time, sehingga memerlukan kode spesifik, kita dapat melihat bahwa konsep kompilasi sebenarnya tidak jelas, dan mungkin tidak dapat didefinisikan dengan cara apa pun yang memuaskan. Kompilasi hanya merupakan proses optimasi, seperti yang saya coba tunjukkan di bagian evaluasi parsial , ketika saya membandingkannya dengan preprocessing data statis dalam beberapa algoritma.

Sebagai proses optimasi yang kompleks, konsep kompilasi sebenarnya milik sebuah kontinum. Bergantung pada karakteristik bahasa, atau program, beberapa informasi mungkin tersedia secara statis dan memungkinkan pengoptimalan yang lebih baik. Hal-hal lain harus ditunda untuk dijalankan. Ketika segala sesuatunya menjadi sangat buruk, semuanya harus dilakukan pada saat run-time setidaknya untuk beberapa bagian program, dan menggabungkan kode sumber dengan penerjemah adalah yang dapat Anda lakukan. Jadi bundling ini hanyalah akhir dari rangkaian kompilasi ini. Banyak penelitian tentang kompiler adalah tentang menemukan cara untuk melakukan secara statis apa yang dulu dilakukan secara dinamis. Pengumpulan sampah waktu kompilasi tampaknya merupakan contoh yang baik.

Perhatikan bahwa mengatakan bahwa proses kompilasi harus menghasilkan kode mesin tidak membantu. Itulah yang dapat dilakukan bundling sebagai penerjemah adalah kode mesin (well, masalahnya bisa sedikit lebih kompleks dengan kompilasi silang).

babou
sumber
3
" mustahil adalah kata yang besar" Kata yang sangat sangat besar. =)
Brian S
3
Jika seseorang mendefinisikan "kompilasi" untuk merujuk pada urutan langkah-langkah yang terjadi seluruhnya sebelum program yang melaksanakan menerima input pertama, dan interpretasi sebagai proses memiliki aliran program kontrol data melalui sarana yang bukan bagian dari model mesin abstrak program , maka untuk bahasa yang akan dikompilasi itu harus mungkin bagi kompiler untuk mengidentifikasi, sebelum eksekusi dimulai, setiap makna yang mungkin dibangun oleh suatu bahasa. Dalam bahasa di mana konstruksi bahasa dapat memiliki jumlah makna yang tidak terbatas, kompilasi tidak akan berfungsi.
supercat
@ Brian Tidak, tidak, dan tidak mungkin untuk membuktikan sebaliknya;)
Michael Gazonda
@supercat Itu masih bukan definisi. Apa 'makna' konstruksi bahasa?
Rhymoid
Saya suka konsep melihat kompiler / interpreter sebagai semacam eksekusi parsial!
Bergi
17

Pertanyaannya sebenarnya bukan tentang kompilasi yang mustahil . Jika suatu bahasa dapat diartikan¹, maka itu dapat dikompilasi secara sepele, dengan menggabungkan penerjemah dengan kode sumber. Pertanyaannya adalah menanyakan fitur bahasa apa yang menjadikan ini satu-satunya cara.

Seorang juru bahasa adalah program yang mengambil kode sumber sebagai input dan berperilaku seperti yang ditentukan oleh semantik kode sumber itu. Jika diperlukan juru bahasa, ini berarti bahasanya termasuk cara untuk menafsirkan kode sumber. Fitur ini disebut eval. Jika juru bahasa diperlukan sebagai bagian dari lingkungan runtime bahasa, itu berarti bahwa bahasa tersebut meliputi eval: apakah evalada sebagai primitif, atau dapat dikodekan dalam beberapa cara. Bahasa yang dikenal sebagai bahasa scripting biasanya menyertakan evalfitur, seperti halnya sebagian besar dialek Lisp .

Hanya karena suatu bahasa termasuk evaltidak berarti bahwa sebagian besar tidak dapat dikompilasi dengan kode asli. Sebagai contoh, ada mengoptimalkan kompiler Lisp, yang menghasilkan kode asli yang baik, dan tetap mendukung eval; evalKode ed dapat ditafsirkan, atau dapat dikompilasi dengan cepat.

evaladalah fitur penterjemah kebutuhan utama, tetapi ada fitur lain yang membutuhkan penerjemah yang lebih pendek. Pertimbangkan beberapa fase khas kompiler:

  1. Parsing
  2. Ketik memeriksa
  3. Pembuatan kode
  4. Menautkan

evalberarti bahwa semua fase ini harus dilakukan pada saat runtime. Ada fitur lain yang membuat kompilasi asli menjadi sulit. Mengambilnya dari bawah, beberapa bahasa mendorong keterlambatan menghubungkan dengan menyediakan cara di mana fungsi (metode, prosedur, dll.) Dan variabel (objek, referensi, dll.) Dapat bergantung pada perubahan kode non-lokal. Ini menyulitkan (tetapi bukan tidak mungkin) untuk menghasilkan kode asli yang efisien: lebih mudah untuk menyimpan referensi objek sebagai panggilan di mesin virtual, dan membiarkan mesin VM menangani binding dengan cepat.

Secara umum, refleksi cenderung membuat bahasa sulit dikompilasi dengan kode asli. Eval primitive adalah kasus refleksi yang ekstrem; banyak bahasa tidak berjalan sejauh itu, tetapi tetap memiliki semantik yang didefinisikan dalam istilah mesin virtual, memungkinkan misalnya kode untuk mengambil kelas dengan nama, memeriksa warisannya, daftar metodenya, memanggil metode, dll. Java dengan JVM dan C # dengan .NET adalah dua contoh terkenal. Cara paling mudah untuk mengimplementasikan bahasa-bahasa ini adalah dengan mengkompilasinya ke bytecode , tetapi tetap ada kompiler asli (banyak just-in-time ) yang mengkompilasi setidaknya fragmen program yang tidak menggunakan fasilitas refleksi canggih.

Pengecekan tipe menentukan apakah suatu program valid. Bahasa yang berbeda memiliki standar yang berbeda untuk berapa banyak analisis dilakukan pada waktu kompilasi vs waktu berjalan: bahasa dikenal sebagai "diketik secara statis" jika melakukan banyak pemeriksaan sebelum mulai menjalankan kode, dan "diketik secara dinamis" jika tidak. Beberapa bahasa termasuk fitur pemeran dinamis atau fitur unmarshall-and-typecheck; fitur ini memerlukan penyematan typechecker di lingkungan runtime. Ini ortogonal untuk persyaratan termasuk generator kode atau juru bahasa di lingkungan runtime.

¹ Latihan: mendefinisikan bahasa yang tidak dapat diartikan.

Gilles 'SANGAT berhenti menjadi jahat'
sumber
(1) Saya tidak setuju tentang bundling juru bahasa dengan menghitung kode sumber sebagai kompilasi, tetapi sisa posting Anda sangat baik. (2) Sepenuhnya setuju tentang eval. (3) Saya tidak melihat mengapa refleksi akan membuat bahasa sulit dikompilasi dengan kode asli. Objective-C memiliki refleksi, dan (saya berasumsi) itu biasanya dikompilasi. (4) Catatan yang agak terkait, metamagic template C ++ biasanya ditafsirkan daripada dikompilasi kemudian dieksekusi.
Mooing Duck
Baru saja terjadi pada saya, Lua dikompilasi. The evalhanya mengkompilasi bytecode, dan kemudian sebagai langkah terpisah biner mengeksekusi bytecode. Dan itu pasti memiliki refleksi dalam biner yang dikompilasi.
Mooing Duck
Pada mesin Arsitektur Harvard, kompilasi harus menghasilkan kode yang tidak harus diakses sebagai "data". Saya berpendapat bahwa informasi dari file sumber yang akhirnya harus disimpan sebagai data daripada kode tidak benar-benar "dikompilasi". Tidak ada yang salah dengan kompiler yang mengambil deklarasi seperti int arr[] = {1,2,5};dan menghasilkan bagian data yang diinisialisasi yang berisi [1,2,5], tapi saya tidak akan menggambarkan perilakunya sebagai menerjemahkan [1,2,5] ke dalam kode mesin. Jika hampir semua program harus disimpan sebagai data, bagian mana yang benar-benar akan "dikompilasi"?
supercat
2
@supercat Itulah yang dimaksud oleh matematikawan dan ilmuwan komputer dengan sepele. Ini sesuai dengan definisi matematika, tetapi tidak ada yang menarik terjadi.
Gilles 'SO- stop being evil'
@Gilles: Jika istilah "kompilasi" disediakan untuk terjemahan ke instruksi mesin (tanpa penyimpanan "data" yang terkait) dan menerima bahwa dalam bahasa kompilasi, perilaku deklarasi array bukan untuk "mengkompilasi" array, maka ada beberapa bahasa di mana tidak mungkin untuk mengkompilasi setiap bagian kode yang berarti.
supercat
13

Saya pikir penulis berasumsi bahwa kompilasi berarti

  • program sumber tidak perlu hadir saat run-time, dan
  • tidak ada kompiler atau juru bahasa yang harus ada pada saat run-time.

Berikut adalah beberapa fitur contoh yang akan membuatnya bermasalah jika bukan "tidak mungkin" untuk skema seperti itu:

  1. Jika Anda dapat menginterogasi nilai suatu variabel pada saat run-time, dengan merujuk ke variabel dengan namanya (yang merupakan string), maka Anda akan memerlukan nama variabel untuk berada di sekitar pada saat run time.

  2. Jika Anda dapat memanggil fungsi / prosedur saat run-time, dengan merujuknya dengan namanya (yang merupakan string), maka Anda akan memerlukan nama fungsi / prosedur saat run-time.

  3. Jika Anda dapat membuat sepotong program saat run-time (sebagai string), katakanlah dengan menjalankan program lain, atau dengan membacanya dari koneksi jaringan dll., Maka Anda akan memerlukan penerjemah atau kompiler saat run-time untuk jalankan program ini.

Lisp memiliki ketiga fitur. Jadi, sistem Lisp selalu memiliki penerjemah yang dimuat pada saat run-time. Bahasa Java dan C # memiliki nama fungsi yang tersedia pada saat run time, dan tabel untuk mencari apa artinya. Mungkin bahasa seperti Basic dan Python juga memiliki nama variabel saat run time. (Saya tidak 100% yakin tentang itu).

Uday Reddy
sumber
Bagaimana jika "juru bahasa" dikompilasi ke dalam kode? Misalnya, menggunakan tabel pengiriman untuk memanggil metode virtual, apakah ini contoh interpretasi atau kompilasi?
Erwin Bolwidt
2
"tidak ada kompiler atau juru bahasa yang harus ada pada saat run-time", eh? Nah jika itu benar, maka dalam arti yang dalam, C tidak dapat "dikompilasi" pada sebagian besar platform. C runtime tidak memiliki banyak hal untuk dilakukan: startup, untuk mengatur tumpukan dan sebagainya, dan shutdown untuk atexitdiproses. Tapi itu masih harus ada di sana.
Nama samaran
1
"Sistem Lisp selalu memiliki penerjemah yang dimuat pada saat run-time." - Belum tentu. Banyak sistem Lisp memiliki kompiler saat runtime. Beberapa bahkan tidak memiliki penerjemah sama sekali.
Jörg W Mittag
2
Selamat mencoba, tetapi en.wikipedia.org/wiki/Lisp_machine#Technical_overview . Mereka mengkompilasi Lisp dan dirancang untuk mengeksekusi hasil secara efisien.
Peter - Pasang kembali Monica
@ Nama samaran: C runtime adalah perpustakaan, bukan kompiler atau juru bahasa.
Mooing Duck
8

mungkin saja balasan saat ini "terlalu memikirkan" pernyataan / jawaban. mungkin yang penulis maksudkan adalah fenomena berikut. banyak bahasa memiliki perintah "eval" seperti; mis. lihat javascript eval dan perilakunya biasanya dipelajari sebagai bagian khusus dari teori CS (misal Lisp) fungsi dari perintah ini adalah untuk mengevaluasi string dalam konteks definisi bahasa. karena itu pada dasarnya ia memiliki kemiripan dengan "kompiler bawaan". kompiler tidak dapat mengetahui isi string sampai runtime. oleh karena itu mengkompilasi hasil eval ke dalam kode mesin tidak dimungkinkan pada waktu kompilasi.

jawaban lain menunjukkan bahwa perbedaan bahasa yang ditafsirkan vs dikompilasi dapat mengaburkan secara signifikan dalam banyak kasus esp dengan bahasa yang lebih modern seperti katakanlah Java dengan "just in time compiler" alias "Hotspot" (mesin javascript misalnya V8 semakin menggunakan teknik yang sama). Fungsionalitas "seperti eval" tentu saja salah satunya.

vzn
sumber
2
V8 adalah contoh yang bagus. Ini adalah kompiler murni, tidak pernah ada interpretasi yang terjadi. Namun itu masih mendukung semantik lengkap ECMAScript, termasuk tidak dibatasi eval.
Jörg W Mittag
1
Lua melakukan hal yang sama.
Mooing Duck
3

LISP adalah contoh yang mengerikan, karena ia dianggap sebagai semacam bahasa "mesin" tingkat yang lebih tinggi sebagai dasar untuk bahasa "nyata". Kata "nyata" tidak pernah terwujud. Mesin LISP dibangun berdasarkan gagasan untuk melakukan (banyak) LISP dalam perangkat keras. Karena interpreter LISP hanyalah sebuah program, pada prinsipnya dimungkinkan untuk mengimplementasikannya dalam sirkuit. Mungkin tidak praktis; tapi jauh dari mustahil.

Selain itu, ada banyak penerjemah yang diprogram dalam silikon, biasanya disebut "CPU". Dan seringkali berguna untuk menafsirkan (belum ada, tidak siap, ...) kode mesin. Misalnya x86_64 Linux pertama kali ditulis dan diuji pada emulator. Ada distribusi penuh di tangan ketika chip datang ke pasar, bahkan hanya untuk pengadopsi / penguji awal. Java sering dikompilasi ke kode JVM, yang merupakan juru bahasa yang tidak akan terlalu sulit untuk ditulis dalam silikon.

Sebagian besar bahasa "ditafsirkan" dikompilasi ke bentuk internal, yang dioptimalkan dan kemudian ditafsirkan. Inilah yang dilakukan Perl dan Python. Ada juga kompiler untuk bahasa yang ditafsirkan yang dimaksudkan, seperti shell Unix. Di lain pihak dimungkinkan untuk menafsirkan bahasa yang dikompilasi secara tradisional. Satu contoh yang agak ekstrem yang saya lihat adalah editor yang menggunakan interpretasi C sebagai bahasa ekstensi. Itu C bisa berjalan normal, tetapi sederhana, program tanpa masalah.

Di sisi lain, CPU modern bahkan mengambil input "bahasa mesin" dan menerjemahkannya ke dalam instruksi level yang lebih rendah, yang kemudian disusun ulang dan dioptimalkan (yaitu, "dikompilasi") sebelum diserahkan untuk dieksekusi.

Seluruh perbedaan "kompiler" vs "juru bahasa" ini benar-benar diperdebatkan, di suatu tempat di tumpukan ada juru bahasa utama yang mengambil "kode" dan menjalankannya "secara langsung". Input dari programmer mengalami transformasi sepanjang garis, yang mana dari yang disebut "kompilasi" hanya menggambar garis arbitrer di pasir.

vonbrand
sumber
1

Kenyataannya adalah bahwa ada perbedaan besar antara menafsirkan beberapa program Dasar dan mengeksekusi assembler. Dan ada beberapa area di antaranya dengan P-code / byte-code dengan atau tanpa kompiler (just-in-time). Jadi saya akan mencoba merangkum beberapa poin dalam konteks realitas ini.

  • Jika bagaimana kode sumber diuraikan tergantung pada kondisi run-time, menulis kompiler mungkin menjadi tidak mungkin, atau sangat sulit sehingga tidak ada yang akan repot.

  • Kode yang memodifikasi sendiri dalam kasus umum tidak mungkin dikompilasi.

  • Sebuah program yang menggunakan fungsi mirip-eval biasanya tidak dapat dikompilasi secara lengkap sebelumnya (jika Anda menganggap string diumpankan sebagai bagian dari program), meskipun jika Anda akan menjalankan kode eval'ed berulang kali mungkin masih berguna untuk membuat fungsi seperti eval Anda memanggil kompiler. Beberapa bahasa menyediakan API untuk kompiler agar mudah.

  • Kemampuan untuk merujuk hal-hal berdasarkan nama tidak menghalangi kompilasi, tetapi Anda memang membutuhkan tabel (seperti yang disebutkan). Memanggil fungsi berdasarkan nama (seperti IDispatch) membutuhkan banyak pipa ledeng, sampai pada titik di mana saya pikir kebanyakan orang akan setuju bahwa kita secara efektif berbicara tentang juru bahasa pemanggilan fungsi.

  • Pengetikan yang lemah (apa pun definisi Anda) membuat kompilasi lebih sulit dan mungkin hasilnya kurang efisien, tetapi seringkali tidak mustahil, kecuali nilai yang berbeda memicu parse yang berbeda. Ada skala geser di sini: jika kompiler tidak dapat menyimpulkan tipe yang sebenarnya, ia perlu memancarkan cabang, pemanggilan fungsi dan sedemikian rupa sehingga tidak akan ada di sana, secara efektif menanamkan bit interpreter ke dalam executable.

Pengecut Anonim
sumber
1

Saya akan menganggap fitur utama dari bahasa pemrograman yang membuat compiler untuk bahasa tidak mungkin (dalam arti yang ketat, lihat juga hosting sendiri ) adalah fitur modifikasi diri . Berarti bahasa memungkinkan untuk mengubah kode sumber selama run-time (sth penghasil compiler, tetap dan statis, kode objek tidak dapat melakukan). Contoh klasik adalah Lisp (lihat juga Homoiconicity ). Fungsionalitas serupa disediakan menggunakan konstruksi bahasa seperti eval , termasuk dalam banyak bahasa (misalnya javaScript). Eval benar-benar memanggil juru bahasa (sebagai fungsi) pada saat run-time .

Dengan kata lain bahasa dapat mewakili sistem meta sendiri (lihat juga Metaprogramming )

Perhatikan bahwa refleksi bahasa , dalam arti menanyakan tentang meta-data dari kode sumber tertentu, dan mungkin memodifikasi meta-data saja, (seperti mekanisme refleksi Java atau PHP) tidak bermasalah untuk kompiler, karena sudah memiliki meta-data pada waktu kompilasi dan dapat membuatnya tersedia untuk program yang dikompilasi, sesuai kebutuhan, jika diperlukan.

Fitur lain yang membuat kompilasi menjadi sulit atau bukan pilihan terbaik (tetapi bukan tidak mungkin) adalah skema pengetikan yang digunakan dalam bahasa tersebut (yaitu pengetikan dinamis vs pengetikan statis dan pengetikan kuat vs pengetikan longgar). Ini menyulitkan kompiler untuk memiliki semua semantik pada waktu kompilasi, sehingga secara efektif bagian dari kompiler (dengan kata lain seorang juru bahasa) menjadi bagian dari kode yang dihasilkan yang menangani semantik pada saat run-time . Dengan kata lain, ini bukan kompilasi tetapi interpretasi .

Nikos M.
sumber
LISP adalah contoh yang mengerikan, seperti yang dikandung sebagai sprt
vonbrand
@vonbrand, mungkin tetapi menampilkan konsep homoiconicity dan seragam data-kode
Nikos M.
-1

Saya merasa pertanyaan awal tidak terbentuk dengan baik. Penulis pertanyaan mungkin bermaksud mengajukan pertanyaan yang agak berbeda: Apa sifat-sifat bahasa pemrograman yang memfasilitasi penulisan kompiler untuknya?

Sebagai contoh, lebih mudah untuk menulis kompiler untuk bahasa bebas konteks daripada bahasa sensitif konteks. Tata bahasa yang mendefinisikan suatu bahasa juga dapat memiliki masalah yang membuatnya sulit untuk dikompilasi, seperti ambiguitas. Masalah seperti itu dapat diatasi tetapi membutuhkan upaya ekstra. Demikian pula, bahasa yang didefinisikan oleh tata bahasa tidak terbatas lebih sulit diurai daripada bahasa konteks-sensitif (lihat Chomsky Hierarchy ). Setahu saya bahasa pemrograman prosedural yang paling banyak digunakan adalah dekat dengan konteks bebas, tetapi memiliki beberapa elemen konteks-sensitif, membuat mereka relatif mudah untuk dikompilasi.

Georgie
sumber
2
Pertanyaannya jelas bermaksud menentang / membandingkan kompiler dan penerjemah. Meskipun mereka dapat bekerja secara berbeda, dan biasanya melakukan kecuali untuk kasus batas @Raphael di atas, mereka memiliki masalah yang sama persis tentang analisis sintaksis dan ambiguitas. Jadi sintaks tidak bisa menjadi masalah. Saya juga percaya bahwa masalah sintaksis biasanya tidak menjadi perhatian utama dalam penulisan kompiler saat ini, meskipun sudah di masa lalu. Saya bukan downvoter: Saya lebih suka berkomentar.
babou
-1

Pertanyaannya memiliki jawaban yang benar yang sangat jelas sehingga biasanya diabaikan sebagai hal yang sepele. Tetapi itu penting dalam banyak konteks, dan merupakan alasan utama mengapa bahasa yang ditafsirkan ada:

Mengkompilasi kode sumber ke dalam kode mesin tidak mungkin jika Anda belum memiliki kode sumber.

Penerjemah menambah fleksibilitas, dan khususnya mereka menambahkan fleksibilitas menjalankan kode yang tidak tersedia ketika proyek yang mendasarinya dikompilasi.

tylerl
sumber
2
"Saya kehilangan kode sumber" bukan properti dari bahasa pemrograman tetapi dari program tertentu, sehingga tidak menjawab pertanyaan. Dan Anda pasti membutuhkan kutipan untuk klaim bahwa menghindari hilangnya kode sumber "alasan utama bahasa mengapa ditafsirkan ada", atau bahkan sebuah alasan mengapa mereka ada.
David Richerby
1
@ DavidRicherby Saya kira use case tyleri ada dalam pikiran adalah interpretasi interaktif, yaitu kode yang dimasukkan saat runtime. Saya setuju, bahwa itu di luar ruang lingkup pertanyaan karena itu bukan fitur bahasa.
Raphael
@DavidRicherby dan Raphael, saya mengatakan bahwa penulis posting ini menyiratkan (apa yang saya jelaskan dalam jawaban saya) sebagai fitur modifikasi diri yang tentu saja merupakan konstruksi bahasa dengan desain dan bukan artefak dari beberapa program khusus
Nikos M.