Tulis juru bahasa Haskell di Haskell

Latihan pemrograman klasik adalah menulis penerjemah Lisp / Skema di Lisp / Skema. Kekuatan bahasa lengkap dapat dimanfaatkan untuk menghasilkan penerjemah untuk subset bahasa.

Apakah ada latihan serupa untuk Haskell? Saya ingin mengimplementasikan subset Haskell menggunakan Haskell sebagai mesinnya. Tentu saja dapat dilakukan, tetapi adakah sumber daya online yang tersedia untuk dilihat?

Saya sedang mengeksplorasi ide menggunakan Haskell sebagai bahasa untuk mengeksplorasi beberapa konsep dalam kursus Struktur Diskrit yang saya ajarkan. Untuk semester ini saya telah memilih Miranda , bahasa yang lebih kecil yang menginspirasi Haskell. Miranda melakukan sekitar 90% dari apa yang saya ingin lakukan, tetapi Haskell melakukan sekitar 2000%. :)

Jadi ide saya adalah membuat bahasa yang memiliki fitur Haskell yang saya suka dan tidak mengizinkan yang lainnya. Seiring kemajuan siswa, saya dapat secara selektif "mengaktifkan" berbagai fitur setelah mereka menguasai dasar-dasarnya.

"Tingkat bahasa" pedagogis telah berhasil digunakan untuk mengajar Java dan Skema . Dengan membatasi apa yang dapat mereka lakukan, Anda dapat mencegah mereka menembak diri sendiri saat mereka masih menguasai sintaks dan konsep yang Anda coba ajarkan. Dan Anda dapat menawarkan pesan kesalahan yang lebih baik.

Saya suka tujuan Anda, tapi itu pekerjaan besar. Beberapa petunjuk:

• Saya telah mengerjakan GHC, dan Anda tidak menginginkan bagian mana pun dari sumber. Pelukan adalah implementasi yang jauh lebih sederhana dan lebih bersih, tetapi sayangnya itu dalam C.

• Ini adalah bagian kecil dari teka-teki, tetapi Mark Jones menulis makalah yang indah berjudul Typing Haskell in Haskell yang akan menjadi titik awal yang bagus untuk front end Anda.

Semoga berhasil! Mengidentifikasi tingkat bahasa untuk Haskell, dengan bukti pendukung dari kelas, akan sangat bermanfaat bagi komunitas dan pasti merupakan hasil yang dapat dipublikasikan!

Ada parser Haskell lengkap: http://hackage.haskell.org/package/haskell-src-exts

Setelah Anda menguraikannya, menghapus atau melarang hal-hal tertentu itu mudah. Saya melakukan ini untuk tryhaskell.org untuk melarang pernyataan impor, untuk mendukung definisi tingkat atas, dll.

Parsing saja modulnya:

parseModule :: String -> ParseResult Module

Kemudian Anda memiliki AST untuk modul:

Module SrcLoc ModuleName [ModulePragma] (Maybe WarningText) (Maybe [ExportSpec]) [ImportDecl] [Decl]    

Jenis Decl sangat luas: http://hackage.haskell.org/packages/archive/haskell-src-exts/1.9.0/doc/html/Language-Haskell-Exts-Syntax.html#t%3ADecl

Yang perlu Anda lakukan adalah menentukan daftar putih - deklarasi, impor, simbol, sintaks yang tersedia, lalu jalankan AST dan berikan "parse error" pada apa pun yang Anda tidak ingin mereka sadari. Anda dapat menggunakan nilai SrcLoc yang dilampirkan ke setiap node di AST:

data SrcLoc = SrcLoc
     { srcFilename :: String
     , srcLine :: Int
     , srcColumn :: Int
     }

Tidak perlu menerapkan ulang Haskell. Jika Anda ingin memberikan kesalahan kompilasi yang lebih bersahabat, cukup parsing kode, filter, kirim ke compiler, dan parse keluaran compiler. Jika itu adalah "tidak bisa mencocokkan jenis yang diharapkan dengan yang disimpulkan a -> b" maka Anda tahu itu mungkin terlalu sedikit argumen untuk suatu fungsi.

Kecuali jika Anda benar-benar ingin menghabiskan waktu menerapkan Haskell dari awal atau mengotak-atik internal Hugs, atau implementasi yang bodoh, saya pikir Anda sebaiknya memfilter apa yang diteruskan ke GHC. Dengan begitu, jika siswa Anda ingin mengambil basis kode mereka dan membawanya ke langkah berikutnya dan menulis beberapa kode Haskell yang benar-benar lengkap, transisinya akan transparan.

Apakah Anda ingin membangun penerjemah Anda dari awal? Mulailah dengan menerapkan bahasa fungsional yang lebih mudah seperti kalkulus lambda atau varian cadel. Untuk yang terakhir ada sebuah wiki yang cukup bagus bernama Write yourself a Scheme in 48 hours memberikan pengenalan yang keren dan pragmatis ke dalam teknik parsing dan interpretasi.

Menafsirkan Haskell dengan tangan akan jauh lebih kompleks karena Anda harus berurusan dengan fitur yang sangat kompleks seperti kelas tipe, sistem tipe yang sangat kuat (tipe-inferensi!) Dan evaluasi malas (teknik reduksi).

Jadi, Anda harus menentukan sebagian kecil Haskell untuk dikerjakan dan mungkin mulai dengan memperluas contoh Skema selangkah demi selangkah.

Tambahan:

Perhatikan bahwa di Haskell, Anda memiliki akses penuh ke interpreters API (setidaknya di bawah GHC) termasuk parser, compiler, dan tentu saja interpreter.

Paket yang akan digunakan adalah petunjuk (Language.Haskell. *) . Sayangnya saya tidak menemukan tutorial online tentang ini atau mencobanya sendiri tetapi kelihatannya cukup menjanjikan.

membuat bahasa yang memiliki fitur Haskell yang persis seperti yang saya suka dan tidak mengizinkan yang lainnya. Seiring kemajuan siswa, saya dapat secara selektif "mengaktifkan" berbagai fitur setelah mereka menguasai dasar-dasarnya.

Saya menyarankan solusi yang lebih sederhana (seperti dalam sedikit pekerjaan yang terlibat) untuk masalah ini. Alih-alih membuat implementasi Haskell di mana Anda bisa mematikan fitur, bungkus kompiler Haskell dengan program yang pertama memeriksa bahwa kode tidak menggunakan fitur apa pun yang Anda larang, dan kemudian menggunakan kompiler siap pakai untuk mengkompilasinya.

Itu akan mirip dengan HLint (dan juga jenis kebalikannya):

HLint (sebelumnya Dr. Haskell) membaca program Haskell dan menyarankan perubahan yang diharapkan membuatnya lebih mudah untuk dibaca. HLint juga memudahkan untuk menonaktifkan saran yang tidak diinginkan, dan untuk menambahkan saran kustom Anda sendiri.

• Terapkan "saran" Petunjuk Anda sendiri untuk tidak menggunakan fitur yang tidak Anda izinkan
• Nonaktifkan semua saran HLint standar.
• Buat pembungkus Anda menjalankan HLint yang telah dimodifikasi sebagai langkah pertama
• Perlakukan saran HLint sebagai kesalahan. Artinya, jika HLint “mengeluh” maka program tidak melanjutkan ke tahap kompilasi

Baskell adalah implementasi pengajaran, http://hackage.haskell.org/package/baskell

Anda bisa mulai dengan memilih, katakanlah, sistem tipe yang akan diterapkan. Itu serumit juru bahasa untuk Skema, http://hackage.haskell.org/package/thih

Seri kompiler EHC mungkin adalah taruhan terbaik: dikembangkan secara aktif dan tampaknya persis seperti yang Anda inginkan - serangkaian kompiler / juru bahasa lambda calculi yang berpuncak pada Haskell '98.

Tetapi Anda juga dapat melihat berbagai bahasa yang dikembangkan di Jenis dan Bahasa Pemrograman Pierce , atau penerjemah Helium (Haskell lumpuh yang ditujukan untuk siswa http://en.wikipedia.org/wiki/Helium_(Haskell) ).

Jika Anda mencari subset dari Haskell yang mudah diimplementasikan, Anda dapat menyingkirkan kelas tipe dan pemeriksaan tipe. Tanpa kelas tipe, Anda tidak memerlukan inferensi tipe untuk mengevaluasi kode Haskell.

Saya menulis kompiler subset Haskell yang dapat dikompilasi sendiri untuk tantangan Code Golf. Dibutuhkan kode subset Haskell pada input dan menghasilkan kode C pada output. Maaf, tidak tersedia versi yang lebih dapat dibaca; Saya mengangkat definisi bersarang dengan tangan dalam proses membuatnya sendiri.

Untuk seorang siswa yang tertarik dalam mengimplementasikan penerjemah untuk subset Haskell, saya akan merekomendasikan untuk memulai dengan fitur-fitur berikut:

• Evaluasi malas. Jika penerjemah ada di Haskell, Anda mungkin tidak perlu melakukan apa pun untuk ini.

• Definisi fungsi dengan argumen dan pelindung yang cocok dengan pola. Hanya khawatirkan variabel, kontra, nihil, dan _pola.

• Sintaks ekspresi sederhana:

  • Literal bilangan bulat

  • Literal karakter

  • [] (nol)

  • Aplikasi fungsi (asosiatif kiri)

  • Infix :(kontra, asosiatif kanan)

  • Kurung

  • Nama variabel

  • Nama fungsi

Lebih konkretnya, tulis penerjemah yang dapat menjalankan ini:

-- tail :: [a] -> [a]
tail (_:xs) = xs

-- append :: [a] -> [a] -> [a]
append []     ys = ys
append (x:xs) ys = x : append xs ys

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _      _      = []

-- showList :: (a -> String) -> [a] -> String
showList _    []     = '[' : ']' : []
showList show (x:xs) = '[' : append (show x) (showItems show xs)

-- showItems :: (a -> String) -> [a] -> String
showItems show []     = ']' : []
showItems show (x:xs) = ',' : append (show x) (showItems show xs)

-- fibs :: [Int]
fibs = 0 : 1 : zipWith add fibs (tail fibs)

-- main :: String
main = showList showInt (take 40 fibs)

Pemeriksaan jenis adalah fitur penting dari Haskell. Namun, beralih dari tidak ada ke kompiler Haskell yang memeriksa tipe sangat sulit. Jika Anda mulai dengan menulis penerjemah untuk hal di atas, menambahkan pemeriksaan jenis seharusnya tidak terlalu menakutkan.

Anda mungkin melihat Happy (parser mirip yacc di Haskell) yang memiliki parser Haskell.

Ini mungkin ide yang bagus - buat versi kecil NetLogo di Haskell. Inilah penerjemah kecil itu.

lihat apakah helium akan menjadi basis yang lebih baik untuk dibangun daripada haskell standar.

Uhc / Ehc adalah rangkaian kompiler yang mengaktifkan / menonaktifkan berbagai fitur Haskell. http://www.cs.uu.nl/wiki/Ehc/WebHome#What_is_UHC_And_EHC

Saya telah diberitahu bahwa Idris memiliki parser yang cukup kompak, tidak yakin apakah itu benar-benar cocok untuk diubah, tetapi ditulis dalam Haskell.

Kebun Binatang Bahasa Pemrograman Andrej Bauer memiliki implementasi kecil dari bahasa pemrograman murni yang berfungsi agak nakal bernama "minihaskell". Ini sekitar 700 baris OCaml, jadi sangat mudah dicerna.

Situs ini juga berisi versi mainan dari bahasa pemrograman ML-style, Prolog-style dan OO.

Tidakkah menurut Anda akan lebih mudah untuk mengambil sumber GHC dan menghapus apa yang tidak Anda inginkan, daripada menulis juru bahasa Haskell Anda sendiri dari awal? Secara umum, harus ada banyak sedikit usaha yang terlibat dalam menghilangkan fitur sebagai lawan untuk menciptakan / menambahkan fitur.

GHC ditulis di Haskell, jadi secara teknis itu tetap dengan pertanyaan Anda tentang juru bahasa Haskell yang ditulis di Haskell.

Mungkin tidak akan terlalu sulit untuk membuat semuanya terhubung secara statis dan kemudian hanya mendistribusikan GHCi yang Anda sesuaikan, sehingga siswa tidak dapat memuat modul sumber Haskell lainnya. Mengenai berapa banyak pekerjaan yang diperlukan untuk mencegah mereka memuat file objek Haskell lainnya, saya tidak tahu. Anda mungkin ingin menonaktifkan FFI juga, jika Anda memiliki banyak penipu di kelas Anda :)

Alasan mengapa ada begitu banyak juru bahasa LISP adalah karena LISP pada dasarnya adalah pendahulu JSON: format sederhana untuk menyandikan data. Ini membuat bagian frontend cukup mudah ditangani. Dibandingkan dengan itu, Haskell, terutama dengan Ekstensi Bahasa, bukanlah bahasa yang paling mudah untuk diurai. Ini adalah beberapa konstruksi sintaksis yang terdengar sulit untuk dilakukan dengan benar:

• operator dengan prioritas yang dapat dikonfigurasi, asosiatif, dan fiksasi,
• komentar bertingkat
• aturan tata letak
• sintaks pola
• do- blok dan desugaring ke kode monadik

Masing-masing, kecuali mungkin operator, dapat ditangani oleh siswa setelah Kursus Konstruksi Penyusun mereka, tetapi ini akan mengalihkan fokus dari cara kerja Haskell yang sebenarnya. Selain itu, Anda mungkin tidak ingin menerapkan semua konstruksi sintaksis Haskell secara langsung, tetapi menerapkan operan untuk menyingkirkannya. Yang membawa kita ke inti literal dari masalah ini, permainan kata-kata yang dimaksudkan sepenuhnya.

Saran saya adalah menerapkan pemeriksaan ketik dan penerjemah Corealih - alih Haskell penuh. Kedua tugas ini sendiri sudah cukup rumit. Bahasa ini, meskipun masih merupakan bahasa fungsional yang diketik dengan kuat, jauh lebih mudah untuk ditangani dalam hal pengoptimalan dan pembuatan kode. Namun, itu masih independen dari mesin yang mendasarinya. Oleh karena itu, GHC menggunakannya sebagai bahasa perantara dan menerjemahkan sebagian besar konstruksi sintaksis Haskell ke dalamnya.

Selain itu, Anda tidak boleh menghindari penggunaan frontend GHC (atau kompiler lain). Saya tidak akan menganggapnya curang karena LISP kustom menggunakan parser sistem LISP host (setidaknya selama bootstrap). Membersihkan Corecuplikan dan menyajikannya kepada siswa, bersama dengan kode aslinya, harus memungkinkan Anda memberikan gambaran umum tentang apa yang dilakukan frontend, dan mengapa lebih baik untuk tidak menerapkannya kembali.

Berikut beberapa link ke dokumentasi Coreseperti yang digunakan di GHC:

• Sistem FC: batasan dan paksaan kesetaraan
• GHC / Sebagai perpustakaan
• The CoreTipe