Mengapa Term Rewriting?

Saya telah melakukan sedikit googleing dan sedikit lebih pendek.

Saya bertanya-tanya apa alasan utama komputasi ilmuwan, programmer, untuk mempelajari penulisan ulang istilah, dan / atau penulisan ulang grafik istilah.

Sejauh yang saya tahu, itu hanya membantu untuk alasan dasar tentang program fungsional dan kontrol program (keharusan). Tampaknya, ini adalah topik yang sangat menarik bagi para ahli logika dan mereka yang mempelajari aljabar abstrak yang konstruktif.

Bantuan apa pun akan sangat dihargai!

Saya tidak yakin ini akan membawa Anda lebih dari yang Anda tahu. Tapi kemudian, saya mungkin gagal memahami alasan yang membuat Anda bertanya-tanya tentang istilah penulisan ulang. Itu membantu.

Seperti yang Anda ketahui, tata bahasa adalah sistem penulisan ulang string. Di bagian atas hierarki Chomsky, Anda memiliki tipe 0 tata bahasa, yang mendefinisikan bahasa yang berulang secara berulang (RE), dan memiliki kekuatan komputasi mesin Turing.

Jadi itu memberitahu Anda bahwa sistem penulisan ulang secara umum banyak hubungannya dengan algoritma expressing.

Masalah dengan string secara umum adalah bahwa tidak ada cara yang jelas untuk melampirkan semantik padanya. Ini adalah semacam penulisan ulang amorf.

Apa yang orang biasanya tertarik adalah mengekspresikan algoritma dalam domain tertentu yang memiliki struktur dan properti. Domain semacam itu sering didefinisikan dari entitas elementer (atom), dan ditutup oleh berbagai operasi, mungkin dibagikan oleh hubungan ekivalensi, dan sebagainya. Ini sering disebut aljabar.

Domain-domain ini seringkali abstrak. Tetapi perhitungan pada elemen-elemennya hanya dapat diekspresikan pada representasi konkret. Istilah adalah representasi alami dari unsur-unsur ini karena mereka menyatakan bagaimana unsur-unsur dapat diperoleh untuk unsur-unsur lain dengan penerapan operasi, secara rekursif turun ke unsur-unsur atom (meskipun sifat-sifat umum tidak selalu harus sepenuhnya turun). Istilah adalah sejenis sintaksis struktur pohon yang dapat dimanipulasi untuk mengekspresikan algoritma (seperti untuk string). Tetapi struktur istilah operan operator juga memungkinkan pengaitannya dengan semantik dalam beberapa domain abstrak melalui homomorfisme.

Daripada mengambil pandangan yang sangat formal dari wikipedia dan banyak teks tentang topik ini, lebih baik pertimbangkan program. Biasanya diakui bahwa representasi sintaksis program yang mudah adalah apa yang disebut Pohon Sintaksis Abstrak (AST). Tetapi AST hanyalah istilah untuk mewakili objek program. Semantik denotasional adalah cara untuk mendefinisikan domain abstrak dan mengaitkan nilai-nilai dari domain ini ke AST (atau subtitle AST) dengan cara homomorfisme. Program dalam bentuk AST dapat diubah atau dioptimalkan dengan menerapkan aturan penulisan ulang (saya tidak menyatakan bahwa semua optimasi dapat atau harus dilakukan dengan cara itu).

Transformasi ekspresi aljabar untuk berbagai keperluan dapat diungkapkan dengan istilah penulisan ulang. Misalnya penyederhanaan beberapa ekspresi. Berbagai jenis perhitungan juga dapat secara alami dinyatakan sebagai penulisan ulang istilah, seperti perhitungan derivatif. Menulis ulang istilah juga kadang-kadang digunakan untuk mendefinisikan bentuk kanonik dalam aljabar, ketika entitas semantik yang sama dapat memiliki beberapa representasi sintaksis.

Saya sarankan Anda melihat artikel wikipedia tentang topik ini .

Pikir saya, itu karena Term Rewriting adalah sesuatu yang sangat mendasar, dan itu memungkinkan Anda menggambarkan hal-hal dengan cara yang sangat rendah, terlepas dari perangkat keras apa pun.

Menulis ulang istilah dapat menjelaskan tata bahasa, tetapi juga memberi Anda mekanisme untuk menggambarkan sistem logis, seperti logika urutan pertama, dll. Pembuktian dan deduksi dapat ditulis sebagai penulisan istilah. Kemudian, penggantian istilah-penulisan ulang adalah satu-satunya operasi yang Anda miliki. Kesederhanaan di sini berharga karena Anda menggambarkan logika, jadi Anda tidak dapat menggunakan kompleksitas logika untuk menggambarkan sistem Anda (karena itulah sistem yang Anda coba gambarkan).

Ini kemudian memberi Anda mekanisme yang Anda butuhkan untuk berbicara tentang kalkulus lambda sebagai sistem logis / aksiomatik, yang memberi Anda versi perhitungan yang sangat formal dan mendasar.

Mesin Turing sangat berguna, tetapi definisi dasarnya mengharuskan Anda untuk memiliki konsep set, fungsi, dll. Ada lebih banyak matematika yang diasumsikan telah dibuat.

Sebaliknya, kalkulus Lambda didefinisikan dalam bentuk logika, sehingga Anda dapat menggunakannya tanpa banyak definisi untuk teori set, fungsi, dll.

Menulis ulang istilah, dimodelkan dengan logika, tidak hanya berlaku untuk pemrograman fungsional. Ketika Anda melakukan verifikasi formal perangkat keras atau perangkat lunak, Anda akan selalu melakukan semacam pertimbangan, dan alasan ini dapat dimodelkan dengan istilah penulisan ulang.

Salah satu alasan yang sangat praktis adalah bahwa hal itu mengarah pada pembangunan sistem transformasi program , alat yang memungkinkan seseorang memanipulasi kode untuk program sebagai istilah (pohon sintaksis abstrak) menggunakan penulisan ulang permukaan-sintaks.

Salah satu contoh dari sistem saya ini, Deng Software Reengineering Toolkit , yang telah digunakan untuk berbagai macam analisis program dan tugas transformasi besar-besaran. Anda dapat melihat bagaimana DMS mengekspresikan penulisan ulang . Penulisan ulang ini diterapkan oleh sistem penulisan ulang asosiatif-komutatif yang beroperasi di belakang layar.