Prototip düzeltme e-grafları derleyici optimizasyonuna eşitlik ekliyor

Derleyici yeniden yazımları olarak düzeltme

Prototip, e-grafın kök eşitlik ilişkisine yakın durumda olan gömülü bir eşitlik ilişkisi tanıtır. Motivasyon, derleyici yeniden yazımlarının sık yönlendirilmiş olmasında yatar: soyut veya yetersiz tanımlı programlar, makinede çalıştırılabilir daha biçimli hale dönüştürülür. Kaynak dillerde değerlendirme sırası tanımsız olabilir veya tamsayı taşması ve sıfıra bölme tanımsız kalabilir; bu da optimizasyon ve çeviri olanakları yaratır.

Kaynak, Max Wills'in microegg'i üzerine kurulu ve bir WASM demosuyla birlikte gelen bir prototipi sunar. Python kodu, eşitlik odaklı bir modeli eşitlik union-find işlemleriyle kapsar; bunlar arasında "küçük veya eşit" ilişkilerinin eklenmesi, kontrol edilmesi ve listelenmesi yolları bulunur.

Merkezi örnek, dijital devrelerde "önemli değil" değeridir. Bir değer desteklenmiyorsa, çıktı "önemli değil" olarak kabul edilebilir; bu da optimize edicinin en iyi devreyi sonucu seçmesine olanak tanır. Prototip, bu değeri doğru veya yanlış olarak düzeltebilir; böylece küresel eşitliği hiçbir tek değerle çakışmaz ve bu da ayrı uygulamalara bağımsız seçim özgürlüğü verir.

Semantik, terimleri mantıksal anlam kümeleriyle eşler; burada "küçük veya eşit", noktasal kümelerin içerme ilişkisini belirtir. rewrite-le ve rewrite-ge kuralları yönlendirilmiş düzeltmeleri işler. Çıkarım süreci, yukarı, aşağı veya yalnızca eşitlik yönünde arama yapabilir; bu, hangi tür düzeltilmiş terimin gerektiğine bağlıdır.

E-graftaki değişkenlik

İşlev sembolleri arasında ilişkileri yaymak için uygulama, her argümanın nasıl davrandığını takip eder: monoton, anti-monoton veya hiçbiri. Örneğin, kümeler farkı ilk argümanında monoton, ikinci argümanında anti-monotondur. Bu bildirimler, düzeltmelerin kapanışını, eşitlik göz önüne alınarak e-matching'i ve çıkarımı sağlar.

Devrelerin yanı sıra, öneri olası uygulamalar olarak mantıksal çıkarım, ilişkisel cebir, alt tipler, gereksinim kapsamı ve birinci sınıf yerleşim analizlerini kontrol eder. Yazar, düzeltmeyi standart e-graf kavramlarına doğrudan bir uzantı olarak tanımlar; ancak daha kesin şözdizimi ve yukarı-aşağı ilişki kümelerinin cebirsel görünümü hakkında sorulara dikkat çeker.