Misalkan seseorang ingin beralasan tentang sifat-sifat kode di luar hal-hal seperti totalitas dan kemurnian fungsional - orang juga peduli dengan konsumsi memori, atau kompleksitas algoritmik suatu fungsi. Bisakah ini dilakukan melalui sistem pengetikan dan efek dependen?
type-theory
functional-programming
dependent-types
inductive-datatypes
John A Zoidberg
sumber
sumber
Jawaban:
Ya bisa. Walaupun secara konseptual tidak begitu sulit, tetapi belum banyak dipelajari. Salah satu aspek dari bidang ini adalah semantik biaya seperti penelitian yang dilakukan oleh Guy Blelloch .
Dalam uraian video Anton disebutkan adalah karya Daniellson dalam Analisis Kompleksitas Waktu Semiformal Ringan untuk Struktur Data Murni Fungsional . Ini memang menggunakan monad untuk membawa biaya per operasi. Monad serupa, pada tingkat semantik, digunakan dalam semantik biaya denotasi untuk bahasa fungsional dengan tipe induktif . Inilah makalah 2016 yang melakukan hal serupa di Coq, Perpustakaan Coq Untuk Verifikasi Internal Running-Times .
Orang-orang NuPRL juga telah lama tertarik melakukan hal-hal seperti ini. Dalam Mengekspresikan Kompleksitas Komputasi dalam Teori Tipe Kontruktif , yang pada dasarnya sama dengan penghitungan atas semantik operasional terstruktur. Di mana ia menjadi sedikit lebih menarik adalah bahwa Anda dapat mencerminkan semantik bahasa ke dalam bahasa tersebut. Contoh di bagian akhir, bagian 12, dari Teori Tipe Komputasi Naif menggambarkan dan membahas hal semacam ini.
sumber