mazeppa
v0.4.3
Supercompilation 1 adalah teknik transformasi program yang secara simbolis mengevaluasi program yang diberikan, dengan nilai-nilai run-time sebagai tidak diketahui. Dengan demikian, ia menemukan pola eksekusi dari program asli dan mensintesisnya ke dalam fungsi mandiri; Hasil supercompilation adalah program residu yang lebih efisien. Dalam hal kekuatan transformasional, supercompilation subsume baik deforestasi 2 dan evaluasi parsial 3 , dan bahkan menunjukkan kemampuan tertentu dari pembuktian teorema.
Mazeppa adalah supercompiler modern yang dimaksudkan untuk menjadi target kompilasi untuk bahasa fungsional bernilai panggilan oleh. Memiliki superkompiler sebelumnya dengan rajin dibandingkan dan direvisi, mazeppa
Pertama, siapkan sistem OCAML di mesin Anda:
$ bash -c "sh <(curl -fsSL https://raw.githubusercontent.com/ocaml/opam/master/shell/install.sh)"
$ opam init --auto-setup
Kemudian instal Mazeppa sebagai paket opam :
$ opam install mazeppa
Ketik mazeppa --help untuk mengonfirmasi instalasi.
Atau, Anda dapat mengkloning repositori dan menginstal mazeppa secara manual:
$ git clone https://github.com/mazeppa-dev/mazeppa.git
$ cd mazeppa
$ ./scripts/install.sh
Flambda adalah program yang kuat dan spesial untuk OCAML. Jika Anda membangun mazeppa dengan kompiler OCAML yang diaktifkan Flambda, Anda mungkin melihat kinerja yang jauh lebih baik. Untuk mengaturnya:
$ opam switch create 5.2.0+flambda ocaml-variants.5.2.0+options ocaml-option-flambda
$ eval $(opam env --switch=5.2.0+flambda)
(Anda dapat menggunakan versi yang berbeda, bukan 5.2.0 jika diinginkan.)
Untuk memeriksa apakah Flambda berhasil diaktifkan, jalankan:
$ ocamlopt -config | grep flambda
Anda dapat bermain dengan mazeppa tanpa benar -benar memasangnya. Memasang OCAML dan repositori dikloning (seperti di atas), jalankan perintah berikut dari direktori root:
$ ./scripts/play.sh
(GraphViz Diperlukan: sudo apt install graphviz .)
Ini akan meluncurkan mazeppa dengan --inspect on playground/main.mz dan memvisualisasikan grafik proses di target/graph.svg . Yang terakhir dapat dilihat dalam kode VS dengan ekstensi pratinjau SVG.
./scripts/play.sh akan secara otomatis mengkompilasi ulang sumber di OCAML, jika ada yang diubah.
Cara terbaik untuk memahami cara kerja superkompilasi adalah dengan contoh. Pertimbangkan fungsi berikut yang mengambil daftar dan menghitung sejumlah elemen kuadratnya:
[ examples/sum-squares/main.mz ]
main(xs) := sum(mapSq(xs));
sum(xs) := match xs {
Nil() -> 0i32,
Cons(x, xs) -> +(x, sum(xs))
};
mapSq(xs) := match xs {
Nil() -> Nil(),
Cons(x, xs) -> Cons(*(x, x), mapSq(xs))
};
Program ini ditulis dalam gaya fungsional idiomatik dan daftar . Setiap fungsi hanya melakukan satu hal, dan melakukannya dengan baik. Namun, ada masalah serius di sini: mapSq pada dasarnya membuat daftar yang akan segera didekonstruksi dengan sum , yang berarti bahwa kita 1) kita perlu mengalokasikan memori ekstra untuk daftar perantara, dan 2) kita membutuhkan dua umpan perhitungan alih -alih satu. Solusi untuk masalah ini disebut deforestasi 2 , yang merupakan kasus khusus superkompilasi.
Mari kita lihat apa yang dilakukan Mazeppa dengan program ini:
$ mkdir sum-squares
$ cd sum-squares
# Copy-paste the program above.
$ nano main.mz
$ mazeppa run --inspect
Bendera --inspect memberitahu Mazeppa untuk memberikan laporan terperinci tentang proses transformasi. sum-squares/target/ direktori akan berisi file-file berikut:
target
├── graph.dot
├── nodes.json
├── output.mz
└── program.json
graph.dot berisi grafik proses lengkap untuk program kami. Anda dapat memperoleh gambar grafik dengan menjalankan dot -Tsvg target/graph.dot > target/graph.svg .nodes.json berisi konten semua node dalam grafik. Tanpa file ini, Anda tidak akan dapat memahami banyak dari grafik saja.program.json berisi program awal di Mazeppa IR : SuperCompiler kami bekerja dengan representasi khusus ini alih -alih program asli.output.mz berisi program residu akhir. output.mz akan berisi kode berikut:
[ examples/sum-squares/target/output.mz ]
main(xs) := f0(xs);
f0(xs) := match xs {
Cons(x, xs') -> +(*(x, x), f0(xs')),
Nil() -> 0i32
};
Supercompiler telah berhasil menggabungkan sum dan mapSq menjadi satu fungsi, f0 ! Berbeda dengan program asli, f0 bekerja dalam satu pass, tanpa harus mengalokasikan memori tambahan.
Bagaimana supercompiler sampai ke titik ini? Mari kita lihat grafik proses yang dihasilkan:
Untuk referensi, nodes.json berisi data berikut di JSON:
[
[ " n0 " , " main(xs) " ],
[ " n1 " , " sum(mapSq(xs)) " ],
[ " n2 " , " sum(.g1(xs)) " ],
[ " n3 " , " xs " ],
[ " n4 " , " sum(Cons(*(.v0, .v0), mapSq(.v1))) " ],
[ " n5 " , " .g0(Cons(*(.v0, .v0), mapSq(.v1))) " ],
[ " n6 " , " +(*(.v0, .v0), sum(mapSq(.v1))) " ],
[ " n7 " , " +(*(.v0, .v0), sum(.g1(.v1))) " ],
[ " n8 " , " *(.v0, .v0) " ],
[ " n9 " , " .v0 " ],
[ " n10 " , " .v0 " ],
[ " n11 " , " sum(.g1(.v1)) " ],
[ " n12 " , " .v1 " ],
[ " n13 " , " +(.v3, .v4) " ],
[ " n14 " , " .v3 " ],
[ " n15 " , " .v4 " ],
[ " n16 " , " sum(Nil()) " ],
[ " n17 " , " .g0(Nil()) " ],
[ " n18 " , " 0i32 " ]
] (Kita tidak perlu memeriksa program.json untuk contoh kecil ini, tetapi jangan ragu untuk melihatnya: itu tidak terlalu rumit.)
Supercompiler dimulai dengan simpul n0 yang mengandung main(xs) . Setelah dua langkah fungsi berlangsung, kami mencapai simpul n2 yang mengandung sum(.g1(xs)) , di mana .g1 adalah fungsi IR yang sesuai dengan mapSq kami. Pada titik ini, kami tidak memiliki pilihan lain selain menganalisis panggilan .g1(xs) dengan menduga nilai apa yang mungkin diambil xs saat run-time. Karena mapSq kami hanya menerima konstruktor Nil dan Cons , cukup untuk mempertimbangkan kasus xs=Cons(.v0, .v1) dan xs=Nil() saja.
Node n4 adalah apa yang terjadi setelah kami mengganti Cons(.v0, .v1) untuk xs , di mana .v0 dan .v1 adalah variabel segar. Setelah tiga fungsi lagi berlangsung, kami tiba di n7 . Ini adalah pertama kalinya kita harus membagi panggilan +(*(.v0, .v0), sum(.g1(.v1))) menjadi .v3=*(.v0, .v0) ( n8 ) dan .v4=sum(.g1(.v1)) ( n11 ) dan lanjutkan supercompiling +(.v3, .v4) ( n13 ); Alasan untuk melakukannya adalah bahwa node sebelumnya ( n2 ) secara struktural tertanam di n7 , sehingga superkompilasi mungkin berlanjut selamanya. Sekarang, apa yang terjadi dengan sum(.g1(.v1)) ( n11 )? Kami telah melihatnya sebelumnya! Ingat bahwa n2 berisi sum(.g1(xs)) , yang hanya penggantian sum(.g1(.v1)) ; Jadi kami memutuskan untuk melipat n11 menjadi n2 , karena tidak masuk akal untuk mengamati hal yang sama dua kali. Cabang -cabang n7 lainnya, yaitu n13 dan n8 , terurai , yang berarti bahwa kita hanya melanjutkan mengubah argumen mereka.
Adapun cabang lain dari n2 , sum(Nil()) ( n16 ), itu cukup untuk hanya membuka panggilan ini ke 0i32 ( n18 ).
Setelah grafik proses selesai, residualisasi mengubahnya menjadi program akhir. Selama tahap ini, pola eksekusi dinamis menjadi fungsi - simpul n2 sekarang menjadi fungsi f0 , karena beberapa simpul lain ( n11 ) menunjuk ke sana. Dalam program residual apa pun, akan ada persis seperti banyak fungsi karena ada node dengan garis putus -putus yang masuk, ditambah main .
Singkatnya, supercompilation terdiri dari 1) definisi fungsi yang sedang berlangsung, 2) Menganalisis panggilan yang cocok dengan variabel yang tidak diketahui, 3) memecah perhitungan menjadi bagian yang lebih kecil, 4) melipat perhitungan berulang, dan 5) panggilan terurai yang tidak dapat dibuka, seperti +(.v3, .v4) ( n13 ) dalam contoh kami. Seluruh proses superkompilasi dijamin akan berakhir, karena ketika beberapa perhitungan menjadi sangat besar dan lebih besar, kami memecahnya menjadi subproblem dan menyelesaikannya secara terpisah.
Ada banyak contoh menarik lainnya dari deforestasi dalam examples/ folder, termasuk struktur data seperti pohon. Faktanya, kami telah mengimplementasikan semua sampel dari pekerjaan sebelumnya pada superkompilasi nilai-per-nilai orde tinggi oleh Peter A. Jonsson dan Johan Nordlander 4 5 ; Dalam semua kasus, Mazeppa telah melakukan hal yang sama atau lebih baik.
Sekarang pertimbangkan contoh lain, kali ini melibatkan evaluasi parsial:
[ examples/power-sq/main.mz ]
main(a) := powerSq(a, 7u8);
powerSq(a, x) := match =(x, 0u8) {
T() -> 1i32,
F() -> match =(%(x, 2u8), 0u8) {
T() -> square(powerSq(a, /(x, 2u8))),
F() -> *(a, powerSq(a, -(x, 1u8)))
}
};
square(a) := *(a, a);
powerSq mengimplementasikan algoritma eksponensiasi-demi-square yang terkenal. Program asli tidak efisien: ia secara rekursif memeriksa parameter x powerSq , meskipun sangat dikenal pada waktu kompilasi. Menjalankan Mazeppa di main(a) akan menghasilkan program residual berikut:
[ examples/power-sq/target/output.mz ]
main(a) := let v0 := *(a, *(a, a)); *(a, *(v0, v0));
Seluruh fungsi powerSq telah dihilangkan, sehingga mencapai efek evaluasi parsial. (Jika kami menganggap powerSq sebagai juru bahasa untuk program x dan memasukkan data a , maka itu adalah proyeksi Futamura pertama: mengkhususkan seorang penerjemah untuk mendapatkan program target yang efisien.) Juga, perhatikan bagaimana SuperCompiler telah berhasil membagikan argumen *(a, *(a, a)) dua kali, sehingga itu tidak dikompilasi ulang setiap kali. Program residual memang mencerminkan eksponensial dengan mengkuadratkan.
Mari kita melampaui deforestasi dan evaluasi parsial. Pertimbangkan fungsi matches(p, s) dari dua string, yang mengembalikan T() jika s berisi p dan F() sebaliknya. Implementasi naif di Mazeppa akan menjadi sebagai berikut, di mana p berspesialisasi untuk "aab" :
[ examples/kmp-test/main.mz ]
main(s) := matches(Cons('a', Cons('a', Cons('b', Nil()))), s);
matches(p, s) := go(p, s, p, s);
go(pp, ss, op, os) := match pp {
Nil() -> T(),
Cons(p, pp) -> goFirst(p, pp, ss, op, os)
};
goFirst(p, pp, ss, op, os) := match ss {
Nil() -> F(),
Cons(s, ss) -> match =(p, s) {
T() -> go(pp, ss, op, os),
F() -> failover(op, os)
}
};
failover(op, os) := match os {
Nil() -> F(),
Cons(_s, ss) -> matches(op, ss)
};
(Di sini kami mewakili string sebagai daftar karakter untuk kesederhanaan, tetapi jangan khawatir, Mazeppa menyediakan string bawaan juga.)
Algoritma ini benar tetapi tidak efisien. Pertimbangkan apa yang terjadi ketika "aa" berhasil dicocokkan, tetapi 'b' tidak. Algoritma akan mulai mencocokkan "aab" sekali lagi dari karakter kedua s , meskipun sudah dapat dikatakan bahwa karakter kedua s adalah 'a' . Otomat terbatas deterministik yang dibangun oleh Knuth-Morris-Pratt Algorithm (KMP) 6 adalah cara alternatif untuk menyelesaikan masalah ini.
Dengan menjalankan mazeppa pada sampel di atas, kami dapat memperoleh algoritma pencocokan string yang efisien untuk p="aab" yang mencerminkan KMP dalam tindakan:
[ examples/kmp-test/target/output.mz ]
main(s) := f0(s);
f0(s) := match s {
Cons(s', ss) -> match =(97u8, s') {
F() -> f1(ss),
T() -> f2(ss)
},
Nil() -> F()
};
f1(ss) := f0(ss);
f2(ss) := match ss {
Cons(s, ss') -> match =(97u8, s) {
F() -> f1(ss'),
T() -> f4(ss')
},
Nil() -> F()
};
f3(ss) := f2(ss);
f4(ss) := match ss {
Cons(s, ss') -> match =(98u8, s) {
F() -> match =(97u8, s) {
F() -> f1(ss'),
T() -> f4(ss')
},
T() -> T()
},
Nil() -> F()
};
Algoritma naif yang kami tulis telah secara otomatis diubah menjadi versi efisien yang terkenal! Sementara algoritma naif memiliki kompleksitas o (| p | * | s |) , yang terspesialisasi adalah o (| s |) .
Sintesis KMP adalah contoh standar yang menampilkan kekuatan superkompilasi sehubungan dengan teknik lain (misalnya, lihat 7 dan 8 ). Memperoleh KMP dengan evaluasi parsial tidak dimungkinkan tanpa mengubah definisi asli matches 9 10 .
Valentin Turchin, penemu superkompilasi, menggambarkan konsep transisi metasystem dengan cara berikut 11 12 13 :
Pertimbangkan sistem apa pun. Misalkan ada cara untuk membuat sejumlah salinan darinya, mungkin dengan variasi. Misalkan sistem ini disatukan menjadi sistem baru yang memiliki sistem jenis S sebagai subsistemnya, dan termasuk juga mekanisme tambahan yang mengontrol perilaku dan produksi subsistem S. Kemudian kita menyebut S ' A Metasystem sehubungan dengan S , dan penciptaan transisi S' a metasystem. Sebagai hasil dari transisi metasystem berturut -turut, struktur kontrol bertingkat, yang memungkinkan bentuk perilaku yang rumit.
Dengan demikian, superkompilasi dapat dengan mudah dilihat sebagai transisi metasystem: ada program objek di Mazeppa, dan ada SuperCompiler Mazeppa yang mengontrol dan mengawasi pelaksanaan program objek. Namun, kita dapat melangkah lebih jauh dan melakukan sejumlah transisi metasystem dalam ranah program objek itu sendiri, seperti yang ditunjukkan oleh contoh berikutnya.
Kami akan menggunakan kode dari examples/lambda-calculus/ . Di bawah ini adalah prosedur evaluasi normalisasi standar untuk mendapatkan bentuk normal beta dari istilah kalkulus lambda yang tidak diketik:
normalize(lvl, env, t) := quote(lvl, eval(env, t));
normalizeAt(lvl, env, t) := normalize(+(lvl, 1u64), Cons(vvar(lvl), env), t);
vvar(lvl) := Neutral(NVar(lvl));
eval(env, t) := match t {
Var(idx) -> indexEnv(env, idx),
Lam(body) -> Closure(env, body),
Appl(m, n) ->
let mVal := eval(env, m);
let nVal := eval(env, n);
match mVal {
Closure(env, body) -> eval(Cons(nVal, env), body),
Neutral(nt) -> Neutral(NAppl(nt, nVal))
}
};
quote(lvl, v) := match v {
Closure(env, body) -> Lam(normalizeAt(lvl, env, body)),
Neutral(nt) -> quoteNeutral(lvl, nt)
};
quoteNeutral(lvl, nt) := match nt {
NVar(var) -> Var(-(-(lvl, var), 1u64)),
NAppl(nt, nVal) -> Appl(quoteNeutral(lvl, nt), quote(lvl, nVal))
};
indexEnv(env, idx) := match env {
Nil() -> Panic(++("the variable is unbound: ", string(idx))),
Cons(value, xs) -> match =(idx, 0u64) {
T() -> value,
F() -> indexEnv(xs, -(idx, 1u64))
}
};
( eval / quote kadang -kadang disebut reflect / reify .)
Ini pada dasarnya adalah mesin langkah besar untuk substitusi penghindaran penangkapan yang efisien: alih-alih merekonstruksi istilah pada setiap pengurangan beta, kami mempertahankan lingkungan nilai. eval Projects Suatu istilah ke "domain semantik", sementara quote melakukan sebaliknya; normalize hanyalah komposisi quote dan eval . Untuk menghindari repot -repot dengan generasi nama yang segar, kami menempatkan indeks de Bruijn di tingkat konstruktor Var dan de bruijn di NVar ; Yang terakhir dikonversi menjadi yang pertama dalam quoteNeutral .
Sekarang mari kita menghitung sesuatu dengan mesin ini:
main() := normalize(0u64, Nil(), example());
example() := Appl(Appl(mul(), two()), three());
two() := Lam(Lam(Appl(Var(1u64), Appl(Var(1u64), Var(0u64)))));
three() := Lam(Lam(Appl(Var(1u64), Appl(Var(1u64), Appl(Var(1u64),
Var(0u64))))));
mul() := Lam(Lam(Lam(Lam(Appl(
Appl(Var(3u64), Appl(Var(2u64), Var(1u64))),
Var(0u64))))));
Tubuh main menghitung bentuk normal dari istilah lambda example() yang melipatgandakan angka gereja two() dan three() .
Dengan superkompilasi main() , kami memperoleh angka gereja 6:
[ examples/lambda-calculus/target/output.mz ]
main() := Lam(Lam(Appl(Var(1u64), Appl(Var(1u64), Appl(Var(1u64), Appl(Var(1u64)
, Appl(Var(1u64), Appl(Var(1u64), Var(0u64)))))))));
Interpreter kalkulus Lambda telah sepenuhnya dimusnahkan!
Dalam contoh ini, kita baru saja melihat tangga metasystem dua tingkat (dalam terminologi Turchin 14 ): pada level 0, kami memiliki mazeppa supercompiler mengubah program objek, sementara pada level 1, kami memiliki program objek yang menormalkan istilah kalkulus Lambda. Mungkin ada jumlah tingkat interpretasi yang sewenang -wenang, dan mazeppa dapat digunakan untuk runtuh semuanya. Perilaku umum superkompilasi ini dieksplorasi oleh Turchin sendiri dalam 1 (Bagian 7), di mana ia dapat mengawasi dua program yang dapat ditafsirkan, satu seperti Fortran dan satu di LISP, untuk mendapatkan faktor speedup 40 dalam kedua kasus.
Lambda Normalizer juga menunjukkan kepada kita bagaimana menjelajah fungsi tingkat tinggi ke dalam bahasa orde pertama. Di Mazeppa, kami tidak dapat memperlakukan fungsi sebagai nilai, tetapi itu tidak berarti bahwa kami tidak dapat mensimulasikannya! Dengan melakukan transisi metasystem, kami dapat secara efisien menerapkan fungsi tingkat tinggi dalam bahasa orde pertama. Seiring dengan defungsialisasi dan konversi penutupan, teknik ini dapat digunakan untuk kompilasi bahasa tingkat tinggi menjadi kode orde pertama yang efisien.
Contoh terkait: Mesin virtual imperatif, self-interpreter.
Dalam retrospeksi, masalah utama yang mencegah adopsi superkompilasi yang meluas adalah ketidakpastiannya - sisi gelap kekuatannya. Untuk memahami apa artinya, pertimbangkan bagaimana kita bisa menyelesaikan masalah SAT "dengan cepat":
[ examples/sat-solver/main.mz ]
main(a, b, c, d, e, f, g) := solve(formula(a, b, c, d, e, f, g));
formula(a, b, c, d, e, f, g) :=
and(or(Var(a), or(Not(b), or(Not(c), F()))),
and(or(Not(f), or(Var(e), or(Not(g), F()))),
and(or(Var(e), or(Not(g), or(Var(f), F()))),
and(or(Not(g), or(Var(c), or(Var(d), F()))),
and(or(Var(a), or(Not(b), or(Not(c), F()))),
and(or(Not(f), or(Not(e), or(Var(g), F()))),
and(or(Var(a), or(Var(a), or(Var(c), F()))),
and(or(Not(g), or(Not(d), or(Not(b), F()))),
T()))))))));
or(x, rest) := match x {
Var(x) -> If(x, T(), rest),
Not(x) -> If(x, rest, T())
};
and(clause, rest) := match clause {
If(x, m, n) -> If(x, and(m, rest), and(n, rest)),
T() -> rest,
F() -> F()
};
solve(formula) := match formula {
If(x, m, n) -> analyze(x, m, n),
T() -> T(),
F() -> F()
};
analyze(x, m, n) := match x {
T() -> solve(m),
F() -> solve(n)
};
Ada dua hal yang salah dengan kode yang benar -benar benar ini: 1) SuperCompiler akan memperluas formula dalam ruang eksponensial, dan 2) supercompiler akan mencoba untuk menyelesaikan rumus yang diperluas dalam waktu eksponensial. Terkadang, kami hanya tidak ingin mengevaluasi semuanya pada waktu kompilasi.
Namun, putus asa: kami memberikan solusi untuk masalah ini. Pertama-tama mari kita pertimbangkan cara menunda memecahkan formula sampai run-time. Ternyata satu -satunya hal yang perlu kita lakukan adalah memberi anotasi formula fungsi dengan @extract sebagai berikut:
@extract
formula(a, b, c, d, e, f, g) :=
// Everything is the same.
Ketika mazeppa melihat solve(formula(a, b, c, d, e, f, g)) , ia mengekstrak panggilan untuk formula menjadi variabel segar .v0 dan melanjutkan kompilasi panggilan yang diekstraksi dan solve(.v0) secara terpisah. Panggilan terakhir hanya akan mereproduksi pemecah SAT asli.
Tetapi mengawasi panggilan ke formula masih akan menghasilkan ledakan eksponensial. Mari kita periksa mengapa ini terjadi. Formula asli kami terdiri dari panggilan ke or dan and ; Sementara or jelas tidak berbahaya, and menyebarkan parameter rest ke kedua cabang If (case match pertama) - ini adalah tempat yang tepat di mana blowup terjadi. Jadi mari kita tandai and dengan @extract juga:
@extract
and(clause, rest) := match clause {
// Everything is the same.
};
Hanya itu saja! Kapan and harus diubah, Mazeppa akan mengekstraksi panggilan keluar dari konteksnya di sekitarnya dan mengawasinya secara terpisah. Dengan menambahkan dua anotasi di tempat yang tepat, kami telah memecahkan masalah penipuan kode dan waktu berjalan eksponensial superkompilasi. Secara umum, setiap kali Mazeppa melihat ctx[f(t1, ..., tN)] , di mana f ditandai @extract dan ctx[.] Adalah konteks di sekitarnya yang tidak kosong . Dalam posisi redex , itu akan mencolokkan variabel v segar ke ctx dan melanjutkan mengubah node berikut secara terpisah: f(t1, ..., tN) dan ctx[v] .
Akhirnya, perhatikan bahwa @extract hanyalah mekanisme tingkat rendah; Front-end kompiler harus melakukan mesin tambahan untuk memberi tahu Mazeppa mana yang berfungsi untuk diekstrak. Ini bisa dilakukan dengan dua cara:
formula dan and dapat diekstraksi, membuat semua fungsi lain tidak tersentuh.Kedua metode dapat digabungkan untuk mencapai efek yang diinginkan.
Mazeppa menggunakan pilihan desain yang menarik untuk memiliki fungsi yang bersemangat dan konstruktor malas. Contoh berikut, di mana magic(1u32, 1u32) menghasilkan angka fibonacci, diadopsi dari Haskell:
[ examples/lazy-fibonacci/main.mz ]
main() := getIt(magic(1u32, 1u32), 3u64);
magic(m, n) := match =(m, 0u32) {
T() -> Nil(),
F() -> Cons(m, magic(n, +(m, n)))
};
getIt(xs, n) := match xs {
Nil() -> Panic("undefined"),
Cons(x, xs) -> match =(n, 1u64) {
T() -> x,
F() -> getIt(xs, -(n, 1u64))
}
};
Jika konstruktor bersemangat, magic(1u32, 1u32) tidak akan pernah berakhir. Namun, Cons tidak mengevaluasi argumennya! Karena getIt hanya mengkonsumsi sebagian dari daftar tak terbatas, program berakhir dan mencetak 2u32 :
$ mazeppa eval
2u32
Konstruktor malas memungkinkan deforestasi yang mudah, seperti yang dibahas di bawah ini.
Setelah menginstal mazeppa melalui opam atau ./scripts/install.sh , tersedia sebagai perpustakaan OCAML!
Siapkan proyek Dune baru sebagai berikut:
$ dune init project my_compiler
Tambahkan mazeppa sebagai perpustakaan pihak ketiga ke dalam bin/dune Anda:
(executable
(public_name my_compiler)
(name main)
(libraries my_compiler mazeppa))
Tempel kode berikut ke bin/main.ml (ini adalah examples/sum-squares/main.mz yang dikodekan dalam ocaml):
open Mazeppa
let input : Raw_program.t =
let sym = Symbol. of_string in
let open Raw_term in
let open Checked_oint in
[ [], sym " main " , [ sym " xs " ], call ( " sum " , [ call ( " mapSq " , [ var " xs " ]) ])
; ( []
, sym " sum "
, [ sym " xs " ]
, Match
( var " xs "
, [ (sym " Nil " , [] ), int ( I32 ( I32. of_int_exn 0 ))
; ( (sym " Cons " , [ sym " x " ; sym " xs " ])
, call ( " + " , [ var " x " ; call ( " sum " , [ var " xs " ]) ]) )
] ) )
; ( []
, sym " mapSq "
, [ sym " xs " ]
, Match
( var " xs "
, [ (sym " Nil " , [] ), call ( " Nil " , [] )
; ( (sym " Cons " , [ sym " x " ; sym " xs " ])
, call
( " Cons "
, [ call ( " * " , [ var " x " ; var " x " ]); call ( " mapSq " , [ var " xs " ]) ] ) )
] ) )
]
;;
let () =
try
let output = Mazeppa. supercompile input in
Printf. printf " %s n " ( Raw_program. show output)
with
| Mazeppa. Panic msg ->
Printf. eprintf " Something went wrong: %s n " msg;
exit 1
;; Jalankan dune exec my_compiler untuk melihat program residual yang diinginkan:
[([], "main", ["xs"], (Raw_term.Call ("f0", [(Raw_term.Var "xs")])));
([], "f0", ["xs"],
(Raw_term.Match ((Raw_term.Var "xs"),
[(("Cons", ["x"; "xs'"]),
(Raw_term.Call ("+",
[(Raw_term.Call ("*", [(Raw_term.Var "x"); (Raw_term.Var "x")]));
(Raw_term.Call ("f0", [(Raw_term.Var "xs'")]))]
)));
(("Nil", []), (Raw_term.Const (Const.Int (Checked_oint.I32 0))))]
)))
]
Anda dapat menghubungi Mazeppa sebanyak yang Anda inginkan, termasuk secara paralel. Perhatikan bahwa kami mengekspos antarmuka terbatas ke supercompiler; Secara khusus, tidak ada cara untuk memeriksa apa yang dilakukannya dalam proses (yaitu, --inspect ).
Selain superkompilasi, kami juga menyediakan evaluator bawaan:
val eval : Raw_program .t -> Raw_term .t Ini hanya dapat dipanggil pada program yang fungsi main tidak menerima parameter. Tidak seperti supercompile , ia menghasilkan istilah yang dievaluasi dari tipe Raw_term.t dan mungkin dapat menyimpang.
Lihat fungsi API lainnya dan dokumentasinya di lib/mazeppa.mli .
Misalkan main.mz berisi versi yang sedikit dimodifikasi dari contoh Fibonacci malas:
main(n) := getIt(magic(1u32, 1u32), n);
magic(m, n) := match =(m, 0u32) {
T() -> Nil(),
F() -> Cons(m, magic(n, +(m, n)))
};
getIt(xs, n) := match xs {
Nil() -> Panic("undefined"),
Cons(x, xs) -> match =(n, 1u64) {
T() -> x,
F() -> getIt(xs, -(n, 1u64))
}
};
Perintah berikut menerjemahkannya ke C11 dengan ekstensi GNU (yaitu, -std=gnu11 ):
$ cat main.mz | mazeppa translate --language C --entry fib
#include "mazeppa.h"
MZ_ENUM_USER_TAGS ( op_Cons , op_Nil );
static mz_Value op_main ( mz_ArgsPtr args );
static mz_Value op_magic ( mz_ArgsPtr args );
static mz_Value op_getIt ( mz_ArgsPtr args );
static mz_Value thunk_0 ( mz_EnvPtr env ) {
mz_Value var_m = ( env )[ 0 ];
mz_Value var_n = ( env )[ 1 ];
return ({
struct mz_value args [ 2 ];
( args )[ 0 ] = var_n ;
( args )[ 1 ] = MZ_OP2 ( var_m , add , var_n );
op_magic ( args );
});
}
static mz_Value op_main ( mz_ArgsPtr args ) {
mz_Value var_n = ( args )[ 0 ];
return ({
struct mz_value args [ 2 ];
( args )[ 0 ] = ({
struct mz_value args [ 2 ];
( args )[ 0 ] = MZ_INT ( U , 32 , UINT32_C ( 1 ));
( args )[ 1 ] = MZ_INT ( U , 32 , UINT32_C ( 1 ));
op_magic ( args );
});
( args )[ 1 ] = var_n ;
op_getIt ( args );
});
}
static mz_Value op_magic ( mz_ArgsPtr args ) {
mz_Value var_m = ( args )[ 0 ];
mz_Value var_n = ( args )[ 1 ];
return ({
struct mz_value tmp = MZ_OP2 ( var_m , equal , MZ_INT ( U , 32 , UINT32_C ( 0 )));
switch (( tmp ). tag ) {
case op_T : {
tmp = MZ_EMPTY_DATA ( op_Nil );
break ;
}
case op_F : {
tmp = MZ_DATA ( op_Cons , 2 , MZ_SIMPLE_THUNK ( var_m ), MZ_THUNK ( thunk_0 , 2 , var_m , var_n ));
break ;
}
default : MZ_UNEXPECTED_TAG (( tmp ). tag );
}
tmp ;
});
}
static mz_Value op_getIt ( mz_ArgsPtr args ) {
mz_Value var_xs = ( args )[ 0 ];
mz_Value var_n = ( args )[ 1 ];
return ({
struct mz_value tmp = var_xs ;
switch (( tmp ). tag ) {
case op_Nil : {
tmp = mz_panic ( MZ_STRING ( "undefined" ));
break ;
}
case op_Cons : {
mz_Value var_x = (( tmp ). payload )[ 0 ];
mz_Value var_xs$ = (( tmp ). payload )[ 1 ];
tmp = ({
struct mz_value tmp = MZ_OP2 ( var_n , equal , MZ_INT ( U , 64 , UINT64_C ( 1 )));
switch (( tmp ). tag ) {
case op_T : {
tmp = mz_force ( var_x );
break ;
}
case op_F : {
tmp = ({
struct mz_value args [ 2 ];
( args )[ 0 ] = mz_force ( var_xs$ );
( args )[ 1 ] = MZ_OP2 ( var_n , sub , MZ_INT ( U , 64 , UINT64_C ( 1 )));
op_getIt ( args );
});
break ;
}
default : MZ_UNEXPECTED_TAG (( tmp ). tag );
}
tmp ;
});
break ;
}
default : MZ_UNEXPECTED_TAG (( tmp ). tag );
}
tmp ;
});
}
extern mz_Value fib ( mz_Value var_n ) {
return MZ_CALL_MAIN ( var_n );
} Perintah translate membutuhkan kedua --language , yang merupakan bahasa target untuk terjemahan, dan --entry , yang merupakan nama simbol eksternal yang akan sesuai dengan fungsi main Anda. Program input mazeppa berasal dari stdin ( cat main.mz dalam contoh kami); Program Output GNU11 ditulis ke stdout .
Mari kita maju lebih lanjut dan kompilasi program output ke file objek. Pertama, salin c/deps/sds.c , c/deps/sds.h , dan c/deps/sdsalloc.h ke direktori Anda saat ini; Kedua, instal Boehm GC di komputer Anda:
$ sudo apt install libgc-dev -y
Kemudian jalankan perintah berikut:
$ cat main.mz
| mazeppa translate --language C --entry fib --dump-header-to .
| gcc -c -o program.o -std=gnu11 -xc -
Opsi --dump-header-to menulis konten mazeppa.h ke lokasi tertentu; Ini diperlukan untuk dikompilasi oleh program output. Perintah gcc menerima program output dari stdin dan menghasilkan program.o .
Sekarang yang tersisa adalah untuk benar -benar memohon fungsi fib yang dihasilkan. Buat main.c dengan konten berikut:
#include "mazeppa.h"
mz_Value fib ( mz_Value n );
int main ( void ) {
// Always initialize Boehm GC before invoking Mazeppa code.
GC_INIT ();
mz_Value v = fib ( MZ_INT ( U , 64 , 10 ));
printf ( "fib(10) = %" PRIu32 "n" , MZ_GET ( U32 , v ));
} Program "driver" ini hanya memanggil fib dengan integer Mazeppa ( MZ_INT ) dan mencetak hasilnya. Anda dapat menggunakan fungsionalitas apa pun dari mazeppa.h , asalkan tidak diawali dengan mz_priv_ atau MZ_PRIV_ .
Untuk menyatukan semua bagian:
$ gcc main.c program.o sds.c -lgc -std=gnu11
./a.out mencetak fib(10) = 55 dan keluar, seperti yang diharapkan.
--inspect dalam lingkungan nyata: Gunakan hanya untuk tujuan debugging.@extract (seperti yang ditunjukkan di atas) untuk mengontrol apakah akan melanjutkan superkompilasi atau mengekstrak redex."otus" lebih kecil dari "octopus" tetapi "octopusx" tidak. Mazeppa menggunakan beberapa pilihan desain yang menarik (diperingkat dengan penting):
Kode orde pertama. Max Bolingbroke dan Simon Peyton Jones 15 melaporkan bahwa untuk satu contoh tertentu, supercompiler tingkat tinggi mereka untuk subset Haskell menghabiskan 42% waktu eksekusi untuk mengelola nama dan penggantian nama. Meskipun benar bahwa model evaluasi sederhana, seperti normalisasi istilah lambda, memungkinkan kita untuk menghindari overhead yang signifikan dari penghindaran penangkapan, superkompilasi lebih rumit. Sebagai contoh, selain melakukan perhitungan simbolik, superkompilasi perlu menganalisis hasil yang sebelumnya dihitung untuk membuat keputusan berdasarkan informasi tentang transformasi lebih lanjut: pertimbangkan tes instance istilah, tes embedding homeomorphic, generalisasi paling spesifik, dll. Memperkenalkan fungsi tingkat tinggi yang lebih sulit dikonsumsi dengan lebih sulit. Di Mazeppa, kami tetap dengan filosofi perbaikan bertahap: alih -alih mencoba menangani banyak fitur mewah pada saat yang sama, kami 1) memperbaiki bahasa inti untuk manipulasi yang nyaman dengan mesin, 2) melakukan sebanyak mungkin transisi metasystem yang diperlukan untuk membuat bahasa inti lebih baik untuk manusia.
Konstruktor malas. Ini adalah pengamatan terkenal bahwa bahasa-bahasa bernilai panggilan demi panggilan sulit untuk deforestasi yang tepat. Masih dimungkinkan untuk menghapus mereka, tetapi bukan tanpa analisis tambahan 4 5 . Namun, jika konstruktor malas (yaitu, mereka tidak mengevaluasi argumen mereka), deforestasi hanya berhasil . Turchin membuatnya bekerja dengan transformasi orde normal dari bahasa panggilan-demi-bernilai, tetapi hasilnya adalah bahwa kode residual dapat diakhiri lebih sering. Di Mazeppa, kami memiliki fungsi-fungsi panggilan demi panggilan dan konstruktor call-by-name (call-by-kebutuhan), yang 1) memungkinkan deforestasi dan 2) melestarikan semantik asli kode.
Grafik proses bebas istilah. Di Mazeppa, grafik proses tidak mengandung referensi apa pun untuk istilah: residualisasi dapat bekerja tanpa mereka. Akibatnya, pengumpul sampah dapat menangani istilah yang digunakan selama pembangunan subgraph. Selain itu, kebijakan ini memiliki beberapa keunggulan penting lainnya: 1) Grafik masih ada untuk diperiksa dengan --inspect , 2) ketika diambil, hanya mengungkapkan informasi tentang keputusan yang diambil SuperCompiler, yang membuatnya lebih mudah untuk dilihat. Beberapa super kompiler yang ada menahan diri dari grafik proses yang tepat (misalnya, Supero 17 Neil Mitchell dan 15 yang disebutkan di atas), tetapi sebagai hasilnya, 1) mereka kurang mampu diperiksa oleh pengguna, 2) algoritma menjadi berantakan dengan rincian pembuatan kode.
Analisis Konfigurasi Dua Dimensi. Biasanya supercompiler menyimpan "sejarah" subset dari semua leluhur sambil mengubah node; Jika simpul ini "cukup dekat" dengan salah satu leluhurnya, sekarang saatnya untuk memecah istilah menjadi bagian yang lebih kecil untuk menjamin penghentian. Di Mazeppa, kami menyimpan dua struktur data terpisah sebagai gantinya: yang berisi subset leluhur node dan yang berisi subset dari node yang sepenuhnya berubah. Struktur data sebelumnya digunakan untuk menjamin penghentian (seperti biasa), sedangkan yang terakhir digunakan untuk meningkatkan berbagi fungsi dalam kode residual. Secara khusus, jika simpul saat ini (jenis khusus) adalah penggantian nama beberapa simpul yang sebelumnya ditransformasikan, kami melipat simpul saat ini ke dalam node sebelumnya. Dengan cara ini, Mazeppa melakukan analisis konfigurasi vertikal dan horizontal , yang membuat kode residual lebih kompak dan superkompilasi lebih efisien.
Analisis produktivitas fungsi. Ketika panggilan fungsi dalam-pencocokan pola-pencocokan nilai yang tidak diketahui, dua hal yang berpotensi berbahaya terjadi: 1) Supercompilation mereproduksi struktur fungsi pencocokan pola, 2) Supercompilation mendorong seluruh konteks di sekitarnya ke semua cabang fungsi ini. Tanpa kontrol lebih lanjut, situasi ini dapat menyebabkan ledakan yang signifikan dalam ukuran kode, kadang -kadang bahkan menyebabkan superkompiler tidak berakhir dalam jumlah waktu yang wajar. Untuk memperbaiki, Mazeppa menduplikasi konteks IFF, panggilan batin ini menghasilkan nilai tingkat atas yang pasti dari setidaknya satu titik keluar, karena jika terjadi, kemungkinan besar bahwa nilai ini dapat didekonstruksi dengan pencocokan pola berikutnya. Kalau tidak, Mazeppa mengekstrak panggilan dalam dan mengubahnya secara terpisah (seperti jika ditandai dengan @extract ). Selain itu, jika konteksnya sebenarnya diduplikasi, aturan berikut berlaku untuk semua cabang: jika cabang menghasilkan nilai tingkat atas yang pasti dari semua titik keluar, itu diubah dalam konteks seperti biasa; Kalau tidak, cabang diekstraksi dari konteks dan diubah secara terpisah. Dalam praktiknya, analisis ini mencegah sejumlah besar spesialisasi yang tidak dibutuhkan, sehingga memadatkan ukuran program residual dan membuat superkompilasi jauh lebih mudah ditelusuri.
Sejarah Cerdas. Instead of blindly comparing a current node with all its ancestors, we employ a more fine-grained control, that is: 1) global nodes (the ones that analyze an unknown variable) are compared with global nodes only, 2) local nodes (the ones that reduce linearly in a single step) are compared with local nodes only up to the latest global node, but not including it, and 3) trivial nodes (the ones that break down terms into smaller components) are not compared with anything kalau tidak. Selain pendekatan yang lebih ekonomi untuk pemeriksaan penghentian, skema ini memungkinkan Mazeppa untuk menemukan lebih banyak peluang optimasi; Lihat 18 , Bagian 4.6 dan 4.7. Pengakhiran superkompilasi dijamin oleh fakta bahwa embedding homeomorfik masih diuji pada semua yang berpotensi tak terbatas setelah istilah global dan lokal (tidak ada urutan tak terbatas dari istilah sepele saja).
Tanda tangan redex. Peluit hanya diuji dengan istilah dengan tanda tangan Redex yang sama. Redex Signature adalah sepasang 1) simbol fungsi dan 2) daftar kategori nilai argumen. Kategori nilai adalah semacam informasi tentang argumen, yang dapat berupa 1) VConst untuk nilai -nilai seperti 42i32 atau "hello world" , 2) VNeutral untuk nilai -nilai seperti x atau +(x, x) , atau 3) VCCall(c) untuk panggilan konstruktor seperti Foo(...) . Peluit masih diuji pada semua urutan istilah yang berpotensi tak terbatas, karena setiap urutan yang tak terbatas harus mengandung setidaknya satu setelahnya istilah dengan tanda tangan Redex yang sama. Strategi ini memungkinkan Mazeppa untuk menghindari generalisasi yang berlebihan dalam kasus-kasus tertentu, seperti yang ditunjukkan oleh dua contoh berikut:
f(A()) tertanam secara homorfis ke dalam f(g(B(A()))) ; Namun, karena operator redex berbeda ( f dan g ), Mazeppa terus mengurangi dan mencapai hasil yang ideal.f(A(Good())) is embedded into f(f(f(B(A(Good()))))) and the redex operator is f in both cases, Mazeppa does not over-generalize because these two terms have different value categories in their redex signatures: in the first case, f is called on A(...) , while in the second case, it is called on B(...) . Sama seperti pada contoh sebelumnya, Mazeppa mencapai hasil yang ideal dari superkompilasi semata -mata dengan pengurangan.Embedding homeomorfik yang dioptimalkan. Selama beberapa dekade, embedding homeomorfik telah mendapatkan reputasi sebagai metode yang sangat baik untuk penghentian online 19 . Sayangnya, terutama karena aliran kontrol non-linear (ketika menyelam dan kopling berlaku), harganya bisa mahal untuk dihitung. Yang lebih buruk lagi, itu dieksekusi ulang untuk semua node orang tua yang memenuhi syarat setiap kali istilah baru ditambahkan ke sejarah, yang secara progresif memperlambat supercompilation seiring dengan tumbuhnya sejarah: pergi sejauh makan sebagian besar waktu superkompilasi! Untuk mengatasinya, kami mempertahankan dua cache yang terpisah:
Hash consing. Cakes embedding homeomorfik yang dijelaskan di atas tergantung pada berapa banyak istilah yang dibagikan . Oleh karena itu kami menggunakan hash consing saat membuka badan fungsi: jika beberapa istilah baru t secara struktural sama dengan beberapa istilah yang ada, yang terakhir digunakan kembali. Untuk menghindari kebocoran memori, kami menggunakan ephemeron global yang memegang pointer lemah untuk istilah. Selain waktu superkompilasi yang lebih baik (karena memoisasi), hash consing juga mengurangi konsumsi memori - lihat #4 (komentar).
Normalisasi selama pembukaan. Ketika panggilan fungsi dibuka, kami mengganti parameter dan menormalkan tubuh sebanyak mungkin (yaitu, tanpa pembukaan lebih lanjut, untuk menjamin penghentian). Untuk melihat alasannya, pertimbangkan fungsi faktorial f(n) ; Dengan pembukaan yang sederhana, kami akan menjebak dalam situasi yang tidak menyenangkan di mana f(1u32) tertanam menjadi *(1u32, f(-(1u32, 1u32))) , menyebabkan generalisasi yang berlebihan . Pada kenyataannya, Mazeppa akan dibuka f(1u32) menjadi *(1u32, f(0u32)) , menjadikan yang terakhir kandidat untuk pembukaan lebih lanjut. Pendekatan ini disarankan dalam 20 , Bagian 4.5. Kelebihan lainnya adalah: 1) Lebih sedikit pekerjaan untuk langkah -langkah mengemudi di masa depan, 2) Kurang perhitungan "dangkal" dalam grafik proses, 3) Pengurangan jumlah tes embedding homeomorfik yang mahal.
*(1u32, f(-(1u32, 1u32))) tidak lagi diperiksa terhadap f(1u32) karena operator redex yang berbeda. Namun, keunggulan lain dari normalisasi masih berlaku.Implementasi di OCAML. Mazeppa diimplementasikan menggunakan kombinasi gaya pemrograman fungsional dan imperatif, yang sangat alami untuk dilakukan di OCAML. Pengecualian digunakan tidak hanya untuk situasi "luar biasa", mutabilitas fungsi di dalam adalah umum. Meskipun kami tidak memiliki supercompiler serupa yang ditulis dalam EG Haskell atau Rust untuk perbandingan, kami percaya bahwa OCAML yang memberi kami implementasi kerja tanpa harus bertengkar dengan bahasa dan tidak pernah menyelesaikan pekerjaan.
Sementara sebagian besar hal di atas tidak terlalu baru, kami percaya bahwa kombinasi fitur -fitur ini membuat Mazeppa alternatif yang lebih praktis daripada pendahulunya.
A symbol <SYMBOL> is a sequence of letters ( a , ... , z and A , ... , Z ) and digits ( 0 , ... , 9 ), followed by an optional question mark ( ? ), followed by an optional sequence of ' characters. The underscore character ( _ ) may be the first character of a symbol, which may informally indicate that the value or function being defined is not used; otherwise, the first character must be a letter. The following sequences of characters are also permitted as symbols: ~ , # , + , - , * , / , % , | , & , ^ , << , >> , = , != , > , >= , < , <= , ++ . The following are reserved words that may not be used as symbols: match , let .
There are four classes of unsigned integer constants :
0b ( 0B ) followed by a non-empty sequence of binary digits 0 and 1 .0o ( 0O ) followed by a non-empty sequence of octal digits 0 , ... , 7 .0 , ... , 9 .0x ( 0X ) followed by a non-empty sequence of decimal digits 0 , ... , 9 and letters a , ... , f ( A , ... , F ).Notes:
_ ) except for the first position in the sequence of digits.- ) placed right before the sequence of digits and underscore characters.<INT> produced by appending an integer type <INT-TY> ( u8 , u16 , u32 , u64 , u128 , i8 , i16 , i32 , i64 , i128 ) right after the original integer constant. For example, the constants 123i8 , 123u16 , and 123i32 all belong to the set <INT> . A string constant <STRING> is a sequence, between double quotes ( " ), of zero or more printable characters (we refer to printable characters as those numbered 33-126 in the ASCII character set), spaces, or string escape sequences :
| Escape sequence | Arti |
|---|---|
f | Form feed (ASCII 12) |
n | Line feed (ASCII 10) |
r | Carriage return (ASCII 13) |
t | Horizontal tab (ASCII 9) |
v | Vertical tab (ASCII 11) |
xhh | ASCII code in hexadecimal |
" | " |
\ | |
where h is either 0 , ... , 9 or a , ... , f or A , ... , F .
A character constant <CHAR> is either a sole character enclosed in single quotes ( ' ) or a character escape sequence enclosed in single quotes. The character escape sequence is the same as for strings, except that " is replaced by ' .
There are no other constants in Mazeppa.
A comment <COMMENT> is any sequence of characters after // , which is terminated by a newline character. (We only allow single-line comments for simplicity.)
The entry point <program> is defined by the following rules:
<def-attr-list> <SYMBOL> ( <SYMBOL> , ... , <SYMBOL> ) := <term> ; <program><COMMENT> <program> where <def-attr-list> is a whitespace-separated sequence of function attributes (the same attribute can occur multiple times). Right now, the only allowed function attribute is @extract .
<term> is defined as follows:
<SYMBOL> (a variable)<const> (a constant)<SYMBOL> ( <term> , ... , <term> ) (a function call)match <term> { <match-case> , ... , <match-case> } (pattern matching)let <SYMBOL> := <term> ; <term> (a let-binding)let <pattern> := <term> ; <term> (a pattern let-binding)<COMMENT> <term> (a comment)The rest of the auxiliary rules are:
<const> :
<INT> or <STRING> or <CHAR> . <match-case> :
<pattern> -> <term> <pattern> :
<SYMBOL> ( <SYMBOL> , ... , <SYMBOL> ) . In Mazeppa, primitive operations employ the same syntax as that of ordinary function calls. To distinguish between the two, we define <op1> and <op2> to be the following sets of symbols:
<op1> is one of ~ , # , length , string , <INT-TY> .<op2> is one of + , - , * , / , % , | , & , ^ , << , >> , = , != , > , >= , < , <= , ++ , get . Furthermore, <op2> has the following subclasses:
<arith-op2> is one of + , - , * , / , % , | , & , ^ , << , >> .<cmp-op2> is one of = , != , > , >= , < , <= .<op1> or <op2> . 2) A function must define a symbol starting with a lowercase letter. 3) No duplicate symbols can occur among function parameters. 4) Every free variable inside a function body must be bound by a corresponding parameter in the function definition.match { ... } must not be empty. 2) No duplicate constructors can occur among case patterns in match { ... } . 3) No duplicate symbols can occur among pattern parameters C(x1, ..., xN) . 4) No let-binding can bind <op1> or <op2> . 5) Panic must be called with only one argument; T and F with zero arguments.If a program, function, or term conforms to these restrictions, we call it well-formed .
| Original form | Desugared form | Catatan |
|---|---|---|
// ... rest | rest | rest is in <program> or <term> |
let p := t; u | match t { p -> u } | p is in <pattern> |
c | ASCII(c) | c is in <CHAR> |
where ASCII(c) is an appropriate u8 integer constant, according to the ASCII table; for example, ASCII( 'a' ) is 97u8 .
Suppose that t is a well-formed term closed under environment env (defined below) and program is a well-formed program. Then the evaluation of t is governed by the following big-step environment machine:
eval(env, x) = eval({ }, env(x))eval(env, const) = const , where const is in <const> .eval(env, f(t1, ..., tN)) =t1Val ^= eval(env, t1)tNVal ^= eval(env, tN)eval({ x1 -> t1Val, ..., xN -> tNVal }, body) , where f(x1, ..., xN) := body; is in program .eval(env, C(t1, ..., tN)) = C(t1[env], ..., tN[env]) , where C starts with an uppercase letter.eval(env, op(t)) =tVal ^= eval(env, t)evalOp1(op, tVal) , where op is in <op1> .eval(env, op(t1, t2)) =t1Val ^= eval(env, t1)t2Val ^= eval(env, t2)evalOp2(t1Val, op, t2Val) , where op is in <op2> .eval(env, match t { p1 -> t1, ..., pN -> tN }) =Ci(s1, ..., sN) ^= eval(env, t)eval(env', tI) , whereCi(x1, ..., xN) -> tI is among the rules in match t { ... } , andenv' is env[x1 -> s1, ..., xN -> sN] .eval(env, let x := t; u) =tVal ^= eval(env, t)eval(env[x -> tVal], u)Notation:
env is a total environment over t , whose general form is { x1 -> t1, ..., xN -> tN } . Each tI term must be closed and well-formed; this property is preserved by eval .env(x) is tI , where x -> tI is in env .env[x1 -> t1, ..., xN -> tN] is the environment env extended with new bindings x1 -> t1 , ... , xN -> tN . If some xI is already bound in env , it is rebound.t[env] denotes a simultaneous substitution of all free variables in t by their bound values in env .tVal ^= eval(env, t) evaluates t under env ; Kemudian:Panic(t') , the result of the whole evaluation rule is Panic(t') .tVal is available for the next clauses. (Note that eval is a partial function, so evaluation of t can "get stuck" without a superimposed type system.)
In what follows, 1) signed integers are represented in two's complement notation, 2) panic denotes Panic(s) , where s is some (possibly varying) implementation-defined string constant.
evalOp1 takes care of the unary operators for primitive types ( x is in <INT> , s is in <STRING> ):
evalOp1(~, x) is the bitwise negation of x of the same type.evalOp1(string, x) is the string representation of x (in decimal).evalOp1(ty, x) , where ty is in <INT-TY> , is x converted to an integer of type ty .x is not in the range of ty , the result is panic .evalOp1(#, x) , where x is a u8 integer, is a string containing only the ASCII character of x .x is not printable, the result takes the form "xhh" .evalOp1(length, s) is a u64 integer denoting the length of s .evalOp1(string, s) is s . Likewise, evalOp2 takes care of the binary operators for primitive types:
evalOp2(x, op, y) , where x and y have the same integer type and op is in <arith-op2> , performs a corresponding arithmetic operation on x and y , yielding a value of the same type as that of x and y .evalOp2(x, op, y) , where x and y have the same integer type and op is in <cmp-op2> , performs a corresponding comparison operation on x and y , yielding either T() or F() .evalOp2(s1, op, s2) , where s1 and s2 are strings and op is in <cmp-op2> , performs a corresponding lexicographical comparison on s1 and s2 , yielding either T() or F() .evalOp2(s1, ++, s2) is the concatenation of s1 and s2 .evalOp2(s, get, idx) , where idx is a u64 integer, is the idx -th character (of type u8 ) of s .idx is out of bounds, the result is panic . The definition of eval is now complete.
version field in dune-project and bin/main.ml .dune build to generate mazeppa.opam .CHANGELOG.md .Not yet, we need to battle-test Mazeppa on some actual programming language. Our long-term goal is to find suitable heuristics to profitably supercompile any source file under 10'000 LoC (in Mazeppa).
For debugging and other purposes, we provide a built-in definitional interpreter that can execute Mazeppa programs. You can launch it by typing mazeppa eval (make sure that your main function does not accept parameters). For the purpose of real execution, we recommend translating Mazeppa to C and then compiling C to machine code, as shown above.
Since Mazeppa is a purely functional language, the only way to implement I/O is as in Haskell 23 : having a pure program that performs computation and a dirty runtime that performs side effects issued by the program. There are no plans to introduce direct I/O into Mazeppa: it will only make everything more complicated.
No, we do not think that a type system is necessary at this point. It is the responsibility of a front-end compiler to ensure that programs do not "go wrong".
The more we make supercompilation predictable, the less it is capable of theorem proving. For those interested in program analysis rather than optimization, we suggest looking into distillation 24 .
For the English audience, the following paper presents a decent introduction into supercompilation:
However, the following papers in Russian describe a supercompilation model that is closer the majority of existing supercompilers, including Mazeppa:
Mazeppa itself is inspired by this excellent paper (in English):
Finally, the international META workshops are great collections of articles about supercompilation and adjacent fields:
Several approaches can lead to superlinear speedup of non-esoteric programs by supercompilation:
None of the above is planned to be implemented in Mazeppa, because 1) we think that writing asymptotically good programs is the responsibility of the programmer, not the optimizer, and 2) predictability of supercompilation is of greater importance to us. However, for those who are interested in this topic, the references may be helpful.
Just fork the repository, work in your own branch, and submit a pull request. Prefer rebasing when introducing changes to keep the commit history as clean as possible.
Valentin F. Turchin. 1986. The concept of a supercompiler. ACM Trans. Program. Lang. Syst. 8, 3 (July 1986), 292–325. https://doi.org/10.1145/5956.5957 ↩ ↩ 2
Philip Wadler. 1988. Deforestation: transforming programs to eliminate trees. Theor. Comput. Sci. 73, 2 (June 22, 1990), 231–248. https://doi.org/10.1016/0304-3975(90)90147-A ↩ ↩ 2
Futamura, Y. (1983). Partial computation of programs. In: Goto, E., Furukawa, K., Nakajima, R., Nakata, I., Yonezawa, A. (eds) RIMS Symposia on Software Science and Engineering. Lecture Notes in Computer Science, vol 147. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-11980-9_13 ↩
Peter A. Jonsson and Johan Nordlander. 2009. Positive supercompilation for a higher order call-by-value language. SIGPLAN Not. 44, 1 (January 2009), 277–288. https://doi.org/10.1145/1594834.1480916 ↩ ↩ 2
Jonsson, Peter & Nordlander, Johan. (2010). Strengthening supercompilation for call-by-value languages. ↩ ↩ 2
DE Knuth, JH Morris, and VR Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6:page 323 (1977). ↩
Glück, R., Klimov, AV (1993). Occam's razor in metacomputation: the notion of a perfect process tree. In: Cousot, P., Falaschi, M., Filé, G., Rauzy, A. (eds) Static Analysis. WSA 1993. Lecture Notes in Computer Science, vol 724. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57264-3_34 ↩
Sørensen MH, Glück R, Jones ND. A positive supercompiler. Journal of Functional Programming. 1996;6(6):811-838. doi:10.1017/S0956796800002008 ↩
Consel, Charles, and Olivier Danvy. "Partial evaluation of pattern matching in strings." Information Processing Letters 30.2 (1989): 79-86. ↩
Jones, Neil & Gomard, Carsten & Sestoft, Peter. (1993). Partial Evaluation and Automatic Program Generation. ↩
Turchin, VF (1996). Metacomputation: Metasystem transitions plus supercompilation. In: Danvy, O., Glück, R., Thiemann, P. (eds) Partial Evaluation. Lecture Notes in Computer Science, vol 1110. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61580-6_24 ↩
Turchin, Valentin F. "Program transformation with metasystem transitions." Journal of Functional Programming 3.3 (1993): 283-313. ↩
Turchin, Valentin F.. “A dialogue on Metasystem transition.” World Futures 45 (1995): 5-57. ↩
Turchin, V., and A. Nemytykh. Metavariables: Their implementation and use in Program Transformation. CCNY Technical Report CSc TR-95-012, 1995. ↩
Maximilian Bolingbroke and Simon Peyton Jones. 2010. Supercompilation by evaluation. In Proceedings of the third ACM Haskell symposium on Haskell (Haskell '10). Association for Computing Machinery, New York, NY, USA, 135–146. https://doi.org/10.1145/1863523.1863540 ↩ ↩ 2
Friedman, Daniel P. and David S. Wise. “CONS Should Not Evaluate its Arguments.” International Colloquium on Automata, Languages and Programming (1976). ↩
Mitchell, Neil. “Rethinking supercompilation.” ACM SIGPLAN International Conference on Functional Programming (2010). ↩
Sørensen, MHB (1998). Convergence of program transformers in the metric space of trees. In: Jeuring, J. (eds) Mathematics of Program Construction. MPC 1998. Lecture Notes in Computer Science, vol 1422. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054297 ↩
Leuschel, Michael. "Homeomorphic embedding for online termination of symbolic methods." The essence of computation: complexity, analysis, transformation (2002): 379-403. ↩
Jonsson, Peter & Nordlander, Johan. (2011). Taming code explosion in supercompilation. PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. 33-42. 10.1145/1929501.1929507. ↩ ↩ 2
Tejiščák, Matúš. Erasure in dependently typed programming. Diss. University of St Andrews, 2020. ↩
Glück, Robert, Andrei Klimov, and Antonina Nepeivoda. "Nonlinear Configurations for Superlinear Speedup by Supercompilation." Fifth International Valentin Turchin Workshop on Metacomputation. 2016. ↩
Peyton Jones, Simon. (2002). Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell. ↩
GW Hamilton. 2006. Poitín: Distilling Theorems From Conjectures. Elektron. Notes Theor. Comput. Sci. 151, 1 (March, 2006), 143–160. https://doi.org/10.1016/j.entcs.2005.11.028 ↩
Klyuchnikov, Ilya, and Dimitur Krustev. "Supercompilation: Ideas and methods." The Monad. Reader Issue 23 (2014): 17. ↩
Klimov, Andrei & Romanenko, Sergei. (2018). Supercompilation: main principles and basic concepts. Keldysh Institute Preprints. 1-36. 10.20948/prepr-2018-111. ↩
Romanenko, Sergei. (2018). Supercompilation: homeomorphic embedding, call-by-name, partial evaluation. Keldysh Institute Preprints. 1-32. 10.20948/prepr-2018-209. ↩
Robert Glück and Morten Heine Sørensen. 1996. A Roadmap to Metacomputation by Supercompilation. In Selected Papers from the International Seminar on Partial Evaluation. Springer-Verlag, Berlin, Heidelberg, 137–160. https://dl.acm.org/doi/10.5555/647372.724040 ↩
Secher, JP (2001). Driving in the Jungle. In: Danvy, O., Filinski, A. (eds) Programs as Data Objects. PADO 2001. Lecture Notes in Computer Science, vol 2053. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44978-7_12 ↩
Hoffmann, B., Plump, D. (1988). Jungle evaluation for efficient term rewriting. In: Grabowski, J., Lescanne, P., Wechler, W. (eds) Algebraic and Logic Programming. ALP 1988. Lecture Notes in Computer Science, vol 343. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-50667-5_71 ↩
Hamilton, Geoff. (2007). Distillation: Extracting the essence of programs. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation. 61-70. 10.1145/1244381.1244391. ↩
Hamilton, GW (2010). Extracting the Essence of Distillation. In: Pnueli, A., Virbitskaite, I., Voronkov, A. (eds) Perspectives of Systems Informatics. PSI 2009. Lecture Notes in Computer Science, vol 5947. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11486-1_13 ↩
Hamilton, Geoff & Mendel-Gleason, Gavin. (2010). A Graph-Based Definition of Distillation. ↩
Hamilton, Geoff & Jones, Neil. (2012). Distillation with labelled transition systems. Conference Record of the Annual ACM Symposium on Principles of Programming Languages. 15-24. 10.1145/2103746.2103753. ↩
Hamilton, Geoff. "The Next 700 Program Transformers." International Symposium on Logic-Based Program Synthesis and Transformation. Cham: Springer International Publishing, 2021. ↩
Klyuchnikov, Ilya, and Sergei Romanenko. "Towards higher-level supercompilation." Second International Workshop on Metacomputation in Russia. Vol. 2. No. 4.2. 2010. ↩
