Halo Saya hadir untuk Anda bagian kedua dari terjemahan saya panduan untuk menerapkan bahasa pemrograman JavaScript Anda - PL Tutorial .
Dari penerjemah
Kami akan membuat bahasa pemrograman kami sendiri - bahasa λ (dalam bahasa asli - λ bahasa ). Dalam proses pembuatan, kami akan menggunakan banyak teknik menarik, seperti keturunan rekursif, kontrol gaya transfer, dan teknik optimasi dasar. Dua versi penerjemah akan dibuat - penerjemah reguler dan CPS, trans-kompiler dalam JavaScript.
Penulis aslinya adalah Mihai Bazon , penulis perpustakaan UglifyJS yang terkenal (alat untuk meminimalkan dan memformat kode JS).
PS Ada bug di interpreter dan compiler: dalam ekspresi seperti a() && b() atau a() || b() a() || b() kedua bagian selalu dieksekusi. Ini, tentu saja, salah karena a() salah untuk operator && , atau tidak salah untuk || , maka nilai b() tidak memainkan peran apa pun. Ini tidak sulit untuk diperbaiki.
Penerjemah sederhana
Di bagian sebelumnya, kami menulis 3 fungsi: InputStream , TokenStream dan parse . Untuk mendapatkan AST dari kode, kami menggunakan kode berikut:
var ast = parse(TokenStream(InputStream(code)));
Menulis penerjemah lebih mudah daripada parser: kita hanya melintasi pohon secara rekursif dan mengeksekusi ekspresi dalam urutan normal mereka.
Konteks ( Environment )
Untuk eksekusi kode yang tepat, kita memerlukan konteks - objek yang berisi semua variabel di lokasi tertentu. Ini akan diteruskan sebagai argumen ke fungsi evaluate .
Setiap kali kita memasukkan node lambda , kita harus menambahkan variabel baru ke argumen konteks - fungsi. Jika argumen tumpang tindih variabel dari blok eksternal, kita harus mengembalikan nilai variabel lama setelah keluar dari fungsi.
Cara termudah untuk melakukan ini adalah dengan menggunakan warisan prototipe JavaScript. Ketika kita memasukkan fungsi baru, kita membuat konteks baru, mengatur konteks eksternal sebagai prototipe, dan memanggil fungsi dalam konteks baru. Berkat ini, kami tidak memiliki apa-apa - dalam konteks eksternal semua variabelnya akan tetap ada.
Berikut ini adalah implementasi objek Environment :
function Environment(parent) { this.vars = Object.create(parent ? parent.vars : null); this.parent = parent; } Environment.prototype = { extend: function() { return new Environment(this); }, lookup: function(name) { var scope = this; while (scope) { if (Object.prototype.hasOwnProperty.call(scope.vars, name)) return scope; scope = scope.parent; } }, get: function(name) { if (name in this.vars) return this.vars[name]; throw new Error("Undefined variable " + name); }, set: function(name, value) { var scope = this.lookup(name);
Objek Environment memiliki bidang parent yang menunjuk ke konteks eksternal. Ini akan menjadi null untuk konteks global. Ini memiliki bidang vars di mana ada semua variabel yang termasuk dalam konteks ini. Untuk konteks global, itu langsung sama dengan objek kosong ( Object.create(null) ) dan salinan variabel dari konteks induk ( Object.create(parent.vars) ) untuk yang non-global.
Ini memiliki beberapa metode:
extend() - salin konteks saat ini.lookup(name) - menemukan konteks di mana variabel bernama name didefinisikan.get(name) - dapatkan nilai dari variabel bernama name . Melempar pengecualian jika variabel belum ditentukan.set(name, value) - mengatur nilai suatu variabel. Metode ini mencari konteks di mana variabel didefinisikan. Jika tidak didefinisikan, dan kami tidak dalam konteks global, pengecualian akan dilemparkan.def(name, value) - membuat (atau tumpang tindih atau menimpa) variabel dalam konteks saat ini.
evaluate fungsi
Sekarang kita memiliki objek Environment , kita dapat melanjutkan untuk menyelesaikan masalah utama. Fungsi ini akan menjadi blok switch besar, yang akan melakukan beberapa tindakan tergantung pada jenis node yang ditransmisikan:
function evaluate(exp, env) { switch (exp.type) {
Untuk literal, kami cukup mengembalikan nilainya:
case "num": case "str": case "bool": return exp.value;
Variabel diambil dari konteks (nama variabel terkandung dalam bidang value ):
case "var": return env.get(exp.value);
Untuk menetapkan, kita harus memastikan bahwa di sisi kiri kita memiliki nama variabel (node var ). Jika tidak, maka kami hanya melempar pengecualian (kami tidak mendukung penugasan ke variabel selain variabel). Selanjutnya, kita mengatur nilai variabel menggunakan env.set . Perhatikan bahwa sisi kanan ekspresi harus dihitung menggunakan panggilan rekursif untuk evaluate :
case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); return env.set(exp.left.value, evaluate(exp.right, env));
Untuk simpul tipe binary kita harus menerapkan operator untuk kedua operan. Kami akan menulis fungsi apply_op nanti. Juga, kami memanggil evaluate untuk kedua bagian ekspresi:
case "binary": return apply_op(exp.operator, evaluate(exp.left, env), evaluate(exp.right, env));
Sebuah simpul tipe lambda akan mengembalikan penutupan JavaScript normal, sehingga dapat disebut seperti fungsi biasa bahkan dari JavaScript. Saya menambahkan fungsi make_lambda , yang akan saya tunjukkan nanti:
case "lambda": return make_lambda(env, exp);
Eksekusi dari simpul if cukup sederhana: pertama kita temukan nilai kondisinya. Jika tidak salah, maka kembalikan nilai cabang then . Kalau tidak, jika ada cabang else , maka nilainya, atau false :
case "if": var cond = evaluate(exp.cond, env); if (cond !== false) return evaluate(exp.then, env); return exp.else ? evaluate(exp.else, env) : false;
Node prog adalah urutan ekspresi. Kami cukup menjalankan semua ekspresi secara berurutan dan mengambil nilai yang terakhir (nilai urutan kosong false ):
case "prog": var val = false; exp.prog.forEach(function(exp){ val = evaluate(exp, env) }); return val;
Untuk simpul call tipe call kita perlu memanggil fungsi. Sebelum itu, kita akan menemukan nilai fungsi itu sendiri, menemukan nilai semua argumen dan memanggil fungsi menggunakan apply :
case "call": var func = evaluate(exp.func, env); return func.apply(null, exp.args.map(function(arg){ return evaluate(arg, env); }));
Kami tidak akan pernah sampai di sini, tetapi jika kami menambahkan tipe simpul baru ke parser dan lupa menambahkannya ke juru bahasa:
default: throw new Error("I don't know how to evaluate " + exp.type); } }
Ini adalah bagian utama dari penerjemah. Di atas, kami menggunakan dua fungsi yang belum kami implementasikan, jadi mari kita mulai:
apply_op :
function apply_op(op, a, b) { function num(x) { if (typeof x != "number") throw new Error("Expected number but got " + x); return x; } function div(x) { if (num(x) == 0) throw new Error("Divide by zero"); return x; } switch (op) { case "+" : return num(a) + num(b); case "-" : return num(a) - num(b); case "*" : return num(a) * num(b); case "/" : return num(a) / div(b); case "%" : return num(a) % div(b); case "&&" : return a !== false && b; case "||" : return a !== false ? a : b; case "<" : return num(a) < num(b); case ">" : return num(a) > num(b); case "<=" : return num(a) <= num(b); case ">=" : return num(a) >= num(b); case "==" : return a === b; case "!=" : return a !== b; } throw new Error("Can't apply operator " + op); }
Ia menerima jenis dan argumen operator. switch sederhana dan intuitif. Tidak seperti JavaScript, yang dapat mengambil nilai apa pun, seperti variabel, bahkan yang tidak masuk akal. Kami mengharuskan operan operator aritmatika menjadi angka dan tidak mengizinkan pembagian dengan nol. Untuk string, kita akan menemukan sesuatu nanti.
make_lambda :
function make_lambda(env, exp) { function lambda() { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i < arguments.length ? arguments[i] : false); return evaluate(exp.body, scope); } return lambda; }
Seperti yang Anda lihat di atas, ia mengembalikan fungsi JavaScript biasa yang menggunakan konteks yang diteruskan dan fungsi AST. Semua pekerjaan dilakukan hanya ketika fungsi itu sendiri disebut: konteks dibuat, argumen ditetapkan (jika mereka tidak cukup, mereka menjadi false ). Selanjutnya, tubuh fungsi hanya dieksekusi dalam konteks baru.
Fungsi asli
Seperti yang Anda lihat, kami tidak punya cara untuk berinteraksi dengan JavaScript dari bahasa kami. Saya dulu menggunakan fungsi print dan println , tapi saya tidak mendefinisikannya di mana pun. Kita perlu menulisnya dalam JavaScript dan hanya menambahkannya ke konteks global.
Berikut ini contoh kode tersebut:
Seluruh kode
Anda dapat mengunduh semua kode yang telah kami tulis selama ini. Itu dapat diluncurkan menggunakan NodeJS. Cukup berikan kode ke aliran standar:
echo 'sum = lambda(x, y) x + y; println(sum(2, 3));' | node lambda-eval1.js
Contoh kode
Bahasa pemrograman kami, meskipun sederhana, dapat (secara teoritis) menyelesaikan masalah yang dapat diselesaikan oleh komputer sama sekali. Ini karena beberapa pria lebih pintar daripada saya - Alonzo Church dan Alan Turing - pernah membuktikan bahwa λ-calculus (lambda calculus) setara dengan mesin Turing, dan bahasa kami mengimplementasikan λ-calculus.
Ini berarti bahwa meskipun bahasa kita tidak memiliki peluang, kita semua dapat mewujudkannya menggunakan apa yang sudah kita miliki. Atau, jika ini sulit dilakukan, kita dapat menulis penerjemah untuk bahasa lain di sini.
Siklus
Loop tidak menjadi masalah jika kita mengalami rekursi. Saya sudah menunjukkan contoh loop diimplementasikan di atas rekursi. Ayo kita coba lagi.
print_range = λ(a, b) if a <= b { print(a); if a + 1 <= b { print(", "); print_range(a + 1, b); } else println(""); }; print_range(1, 10);
Tetapi di sini kita memiliki masalah: jika kita menambah jumlah iterasi, katakanlah menjadi 1000. Sebagai contoh, saya mendapatkan kesalahan “Ukuran stack panggilan maksimum terlampaui” setelah 600. Ini terjadi karena interpreter bersifat rekursif dan rekursi mencapai kedalaman maksimum.
Ini masalah serius, tetapi ada solusinya. Saya ingin menambahkan konstruksi baru untuk iterasi ( for atau while ), tapi mari kita coba lakukan tanpa itu. Rekursi itu terlihat indah, jadi mari kita tinggalkan. Kita akan lihat nanti bagaimana cara mengatasi batasan ini.
Struktur data (ketiadaan)
Ada tiga jenis data dalam bahasa λ kami: angka, string, dan tipe Boolean. Tampaknya Anda tidak dapat membuat tipe yang kompleks, seperti array, atau objek. Tapi ini bukan tat, kita punya satu lagi jenis: fungsi. Ternyata jika kita mengikuti kalkulus λ, maka kita dapat membuat struktur data apa pun, termasuk objek, bahkan dengan warisan.
Saya akan menunjukkannya pada contoh daftar. Mari kita bayangkan bahwa kita memiliki fungsi cons yang menciptakan objek yang berisi dua nilai. Sebut objek ini "sel" atau "pasangan." Kami akan memberi nama salah satu nilai "mobil" dan yang lainnya "cdr". Hanya karena mereka disebut dalam Lisp. Sekarang, jika kita memiliki objek "sel", maka kita bisa mendapatkan nilainya menggunakan fungsi car dan cdr :
x = cons(10, 20); print(car(x));
Sekarang kita dapat dengan mudah mendefinisikan daftar:
Daftar adalah pasangan yang mengandung elemen pertama di `car` dan elemen lainnya di` cdr`. Tetapi `cdr` hanya dapat berisi satu nilai! Nilai ini akan menjadi daftar. Daftar adalah pasangan yang mengandung elemen pertama di `car` dan elemen lainnya di` cdr`. Tetapi `cdr` hanya dapat berisi satu nilai! Nilai ini akan menjadi daftar. [...]
Ini adalah tipe data rekursif. Tetapi satu masalah tetap ada: kapan Anda harus berhenti? Secara logis, kita harus berhenti ketika cdr adalah daftar kosong. Tetapi apa itu daftar kosong? Untuk melakukan ini, mari kita tambahkan objek baru yang disebut "NIL". Ini dapat digunakan sebagai pasangan (kita dapat menggunakan car dan cdr di atasnya, tetapi hasilnya adalah NIL itu sendiri). Sekarang mari kita buat daftar item 1, 2, 3, 4, 5:
x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL))))); print(car(x));
Ini terlihat mengerikan ketika tidak ada sintaks khusus untuk ini. Tapi saya hanya ingin menunjukkan bahwa ini dapat dilakukan dengan menggunakan fitur bahasa λ yang ada. Berikut implementasinya:
cons = λ(a, b) λ(f) f(a, b); car = λ(cell) cell(λ(a, b) a); cdr = λ(cell) cell(λ(a, b) b); NIL = λ(f) f(NIL, NIL);
Ketika saya pertama kali melihat cons / car / cdr dibuat dengan cara ini, saya terkejut bahwa mereka tidak memerlukan satu if (tapi ini aneh mengingat fakta bahwa itu tidak ada dalam λ-calculus asli). Tentu saja, tidak ada bahasa pemrograman yang melakukan hal ini, karena ini sangat tidak efisien, tetapi tidak membuat λ-calculi kurang indah. Dalam bahasa yang jelas, kode ini melakukan hal berikut:
- fungsi
cons mengambil dua nilai ( a dan b ) dan mengembalikan fungsi yang menampungnya. Fungsi itu adalah objek utama pasangan. Dia mengambil argumen dan menyebutnya untuk kedua nilai pasangan. - Fungsi
car memanggil argumen yang diteruskan, melewati fungsi yang mengembalikan argumen pertama. - fungsi
cdr melakukan hal yang sama dengan fungsi car , tetapi dengan satu-satunya perbedaan adalah bahwa fungsi yang dikirimkan mengembalikan argumen kedua. - fungsi
NIL bekerja sama dengan cons , tetapi mengembalikan pasangan dengan dua nilai yang sama dengan NIL.
cons = λ(a, b) λ(f) f(a, b); car = λ(cell) cell(λ(a, b) a); cdr = λ(cell) cell(λ(a, b) b); NIL = λ(f) f(NIL, NIL); x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL))))); println(car(x));
Ada banyak algoritma pada daftar yang dapat diimplementasikan secara rekursif dan terlihat logis. Misalnya, berikut adalah fungsi yang memanggil fungsi yang diteruskan untuk setiap item daftar:
foreach = λ(list, f) if list != NIL { f(car(list)); foreach(cdr(list), f); }; foreach(x, println);
Dan di sini ada satu lagi yang membuat daftar untuk sejumlah angka:
range = λ(a, b) if a <= b then cons(a, range(a + 1, b)) else NIL;
Daftar yang kami terapkan di atas tidak dapat diubah (kami tidak dapat mengubah car atau cdr setelah daftar dibuat). Sebagian besar Lisp memiliki fungsi untuk mengubah pasangan. Dalam Skema mereka disebut set-car! / set-cdr! . Dalam Common Lisp, rplaca / rplacd . Kali ini kami menggunakan nama-nama dari Skema:
cons = λ(x, y) λ(a, i, v) if a == "get" then if i == 0 then x else y else if i == 0 then x = v else y = v; car = λ(cell) cell("get", 0); cdr = λ(cell) cell("get", 1); set-car! = λ(cell, val) cell("set", 0, val); set-cdr! = λ(cell, val) cell("set", 1, val);
Ini menunjukkan bahwa kita dapat menerapkan struktur data yang bisa berubah. Saya tidak akan masuk jauh ke cara kerjanya, jelas dari kode.
Kita dapat melangkah lebih jauh dan mengimplementasikan objek, tetapi tanpa perubahan dalam sintaks akan sulit untuk dilakukan. Cara lain adalah dengan mengimplementasikan sintaks baru dalam tokenizer / parser dan menambahkan pemrosesan mereka dalam interpreter. Semua bahasa pemrograman utama melakukan ini, dan perlu untuk mencapai kinerja normal. Kami akan menambahkan sintaks baru di bagian artikel selanjutnya.
[Dari penerjemah: jika Anda tertarik dengan lambda calculus, ada artikel keren tentang Habré yang didedikasikan untuk topik ini: Lambda calculus dalam JavaScript .]
Konstruksi sintaksis baru
Bahasa λ kami memiliki beberapa konstruksi sintaksis. Misalnya, tidak ada cara langsung untuk menambahkan variabel baru. Seperti yang saya katakan sebelumnya, kita harus menggunakan IIFE, sehingga terlihat seperti ini:
(λ(x, y){ (λ(z){
Kami akan menambahkan kata kunci let . Ini akan memungkinkan kami untuk menulis sesuatu seperti ini:
let (x = 2, y = 3, z = x + y) print(x + y + z);
Untuk setiap variabel di blok let , variabel sebelumnya harus tersedia bahkan dari blok yang sama. Karenanya, kode di atas akan setara dengan yang berikut:
(λ(x){ (λ(y){ (λ(z){ print(x + y + z); })(x + y); })(3); })(2);
Perubahan-perubahan ini dapat dilakukan secara langsung di parser dan kemudian tidak akan membutuhkan perubahan dalam penerjemah. Alih-alih menambahkan node let baru, kita dapat mengubahnya menjadi node call dan lambda . Ini berarti bahwa kami tidak melakukan perubahan semantik dalam bahasa kami - ini disebut "gula sintaksis", dan operasi mengubah ini menjadi node AST yang ada sebelumnya disebut "tanpa gula" (asli: "desugaring").
Namun, kita harus mengganti pengurai. Mari kita tambahkan "let" node baru karena dapat ditafsirkan lebih efisien (tidak perlu membuat penutupan dan memanggil mereka segera, kita hanya perlu menyalin dan mengubah konteksnya).
Kami juga akan menambahkan dukungan untuk "beri nama", yang ada di Skema. Itu membuatnya lebih mudah untuk membuat loop:
print(let loop (n = 10) if n > 0 then n + loop(n - 1) else 0);
Ini adalah loop "rekursif" yang menghitung jumlah 10 + 9 + ... + 0. Sebelumnya, kita harus melakukannya seperti ini:
print((λ(loop){ loop = λ(n) if n > 0 then n + loop(n - 1) else 0; loop(10); })());
Selain itu, untuk mempermudah ini, kami akan menambahkan sintaks "fungsi dengan nama". Ini akan terlihat seperti ini:
print((λ loop (n) if n > 0 then n + loop(n - 1) else 0) (10));
Modifikasi yang perlu dilakukan untuk ini:
- Dukungan untuk nama opsional setelah kata kunci
lambda . Jika ada, maka kita harus menambahkan variabel ke konteks saat ini yang akan menunjuk ke fungsi itu sendiri. Ini persis sama dengan fungsi dengan nama dalam JavaScript. - Dukungan untuk kata kunci
let baru. Berikutnya adalah nama opsional dan daftar (mungkin kosong) definisi variabel dalam formulir ini: foo = EXPRESSION , dipisahkan oleh koma. Tubuh ekspresi let adalah ekspresi tunggal (yang, tentu saja, dapat menjadi urutan ekspresi).
Perubahan Parser
Pertama, perubahan kecil dalam tokenizer, tambahkan kata kunci let ke daftar kata kunci:
var keywords = " let if then else lambda λ true false ";
Ubah fungsi parse_lambda ia membaca nama opsional:
function parse_lambda() { return { type: "lambda", name: input.peek().type == "var" ? input.next().value : null,
Sekarang tambahkan fungsi yang mem-parsing ekspresi let :
function parse_let() { skip_kw("let"); if (input.peek().type == "var") { var name = input.next().value; var defs = delimited("(", ")", ",", parse_vardef); return { type: "call", func: { type: "lambda", name: name, vars: defs.map(function(def){ return def.name }), body: parse_expression(), }, args: defs.map(function(def){ return def.def || FALSE }) }; } return { type: "let", vars: delimited("(", ")", ",", parse_vardef), body: parse_expression(), }; }
Ini menangani dua kasus. Jika setelah let ada token tipe var , maka ini let dengan nama. Selanjutnya, kami membaca daftar definisi menggunakan fungsi yang delimited , karena mereka berada dalam tanda kurung dan dipisahkan oleh koma, dan kami menggunakan fungsi parse_vardef , yang ditunjukkan di bawah ini. Selanjutnya, kami mengembalikan simpul tipe call , yang segera memanggil fungsi bernama (IIFE). Argumen untuk fungsi adalah variabel yang ditentukan oleh let , dan node call akan meneruskan nilai sebagai argumen. Dan, tentu saja, isi fungsi dibaca menggunakan parse_expression() .
Jika let sederhana, maka kita mengembalikan simpul tipe let dengan vars dan bidang isian. Bidang vars berisi larik variabel dalam format berikut: { name: VARIABLE, def: AST } , yang diuraikan oleh fungsi berikut:
function parse_vardef() { var name = parse_varname(), def; if (is_op("=")) { input.next(); def = parse_expression(); } return { name: name, def: def }; }
Selain itu, Anda perlu menambahkan tanda centang untuk jenis ekspresi baru di fungsi parse_atom :
Perubahan Interpreter
Karena kami memutuskan untuk mengubah struktur AST alih-alih “memecahnya” menjadi tipe node yang lama, kami harus menambahkan pemrosesan logika baru ke interpreter.
Untuk menambahkan dukungan untuk nama fungsi opsional, kami memodifikasi fungsi make_lambda :
function make_lambda(env, exp) { if (exp.name) {
Jika fungsi memiliki nama, maka saat kami membuat penutupan, kami membuat salinan konteks, dan menambahkan fungsi ke konteks. Sisanya tetap sama.
Dan akhirnya, untuk memproses sebuah simpul bertipe let , kita menambahkan case berikut ke interpreter:
case "let": exp.vars.forEach(function(v){ var scope = env.extend(); scope.def(v.name, v.def ? evaluate(v.def, env) : false); env = scope; }); return evaluate(exp.body, env);
Perhatikan bahwa untuk setiap variabel konteks baru dibuat di mana variabel baru ditambahkan. Setelah itu, kita cukup mengeksekusi tubuh dalam konteks terakhir.
Contohnya
println(let loop (n = 100) if n > 0 then n + loop(n - 1) else 0); let (x = 2, y = x + 1, z = x + y) println(x + y + z);
— .
. , , , . JavaScript λ.
:
globalEnv.def("fibJS", function fibJS(n){ if (n < 2) return n; return fibJS(n - 1) + fibJS(n - 2); }); globalEnv.def("time", function(fn){ var t1 = Date.now(); var ret = fn(); var t2 = Date.now(); println("Time: " + (t2 - t1) + "ms"); return ret; });
time , , , .
fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); print("fib(10): "); time( λ() println(fib(10)) ); print("fibJS(10): "); time( λ() println(fibJS(10)) ); println("---");
, Google Chrome, n (27), λ , , JS 4 . , , .
λ JavaScript. , for / while ; JS. ? JS , .
, , JavaScript, , JavaScript.
, , . , .
Kesimpulan
, . , - ; , , ? — JavaScript. , JavaScript — ? , , JavaScript, , , . JavaScript ( , ).
, , Lisp — : //. , , .. Lisp . Lisp let , , Lisp.
: JavaScript. Bagian 3: juru bahasa CPS