Halo Saya persembahkan untuk Anda bagian ketiga dari terjemahan panduan ini untuk menerapkan bahasa pemrograman JavaScript - Tutorial PL .

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 CPS

Bahasa λ kami memiliki dua kelemahan:

• Rekursi terbatas pada stack JS, jadi kami tidak memiliki cara normal untuk melakukan loop.
• Penerjemahnya lambat, jadi rekursi sangat lambat.

Sekarang kita akan memperbaiki kesalahan pertama tanpa memperhatikan fakta bahwa penerjemah akan menjadi lebih lambat. Kami akan menulis ulang penerjemah dalam gaya "kelanjutan-lewat gaya" (CPS).

Apa itu "transfer lanjutan"

Anda melakukan ini di NodeJS sepanjang waktu:

 fs.readFile("file.txt", "utf8", function CC(error, data){ //   - "" //     'return', // 'readFile'  ,  . }); 

Di setiap langkah ada panggilan balik yang akan dipanggil ketika Anda perlu melanjutkan. Gaya transfer lanjutan membuat transfer kontrol “eksplisit” - Anda tidak menggunakan return , throw , break atau continue . Tidak ada lompatan implisit dalam kode. Anda bahkan tidak dapat menggunakan for atau while loop dengan fungsi asinkron. Dalam hal ini, mengapa kita membutuhkannya dalam bahasa pemrograman?

Menulis kode dengan gaya mentransmisikan kelanjutan sulit dan mudah untuk membuat kesalahan, tetapi kami hanya akan menulis ulang penerjemah dengan gaya itu.

evaluate fungsi

Fungsi evaluate akan menerima tiga argumen: ekspresi (AST), konteks (Lingkungan), dan fungsi yang akan dipanggil ketika hasilnya. Ini kodenya, untuk setiap fragmen ada penjelasan:

 function evaluate(exp, env, callback) { switch (exp.type) { 

Untuk konstanta, kami hanya akan mengembalikan nilainya. Namun ingat, kami tidak memiliki return - alih-alih kami hanya menelepon kembali dan meneruskan nilainya.

  case "num": case "str": case "bool": callback(exp.value); return; 

Node var juga sederhana - dapatkan variabel dari konteks dan berikan ke fungsi:

  case "var": callback(env.get(exp.value)); return; 

Untuk assign node, kita perlu mendapatkan nilai dari ekspresi kiri ( right ). Untuk melakukan ini, kita panggil evaluate , dengan meneruskan fungsi yang akan mendapatkan hasilnya (untuk sisi kanan ekspresi). Dan kemudian kita callback panggilan callback dengan nilai variabel, atur variabel dalam konteks saat ini:

  case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function(right){ callback(env.set(exp.left.value, right)); }); return; 

Hampir sama untuk node tipe binary , tetapi di sini kita harus terlebih dahulu mendapatkan nilai dari field left , dan hanya kemudian nilai dari field yang right . Kemudian kita panggil saja callback, melewati hasil operasi:

  case "binary": evaluate(exp.left, env, function(left){ evaluate(exp.right, env, function(right){ callback(apply_op(exp.operator, left, right)); }); }); return; 

let simpul terlihat lebih rumit, tetapi sebenarnya itu sederhana. Kami memiliki beberapa variabel. Bidang def mereka (nilai awal) mungkin kosong, dalam hal ini kami akan menjadikannya false . Tetapi jika ada nilai, maka kita perlu memanggil evaluate secara rekursif untuk mendapatkannya.

Jika Anda pernah bekerja dengan NodeJS sebelumnya, Anda telah melakukan ini berkali-kali sebelumnya. Karena panggilan balik, kami tidak dapat menggunakan for , oleh karena itu, kami harus menafsirkan ekspresi ini satu per satu (bayangkan fungsi evaluate sebagai tidak sinkron). Fungsi loop bawah ini (segera dipanggil) mendapatkan konteks dan jumlah definisi yang perlu diproses:

• Jika angka ini sama dengan jumlah variabel ( vars.length ), maka ini berarti bahwa kita telah mendefinisikan semua ekspresi sehingga kita dapat mengeksekusi tubuh ekspresi. Harap dicatat bahwa saat ini kami tidak menelepon panggilan callback , tetapi meneruskannya untuk evaluate , yang kemudian akan memanggilnya.
• Jika angka ini kurang, maka Anda perlu menghitung definisi saat ini dan meneruskan fungsi yang akan memanggil loop(scope, i + 1) , sebelum menyalin konteks.
  

    case "let": (function loop(env, i){ if (i < exp.vars.length) { var v = exp.vars[i]; if (v.def) evaluate(v.def, env, function(value){ var scope = env.extend(); scope.def(v.name, value); loop(scope, i + 1); }); else { var scope = env.extend(); scope.def(v.name, false); loop(scope, i + 1); } } else { evaluate(exp.body, env, callback); } })(env, 0); return; 

Node lambda akan diproses dalam fungsi terpisah, seperti sebelumnya:

  case "lambda": callback(make_lambda(env, exp)); return; 

Untuk menafsirkan if , pertama-tama kita menafsirkan kondisi. Jika tidak salah, maka kami menafsirkan ungkapan itu, dalam kasus lain, menafsirkan else jika ada, atau mengembalikan false jika tidak. Seperti sebelumnya, untuk then dan yang else kami hanya meneruskan callback sebagai "tindakan yang harus dilakukan setelah eksekusi" dari ekspresi:

  case "if": evaluate(exp.cond, env, function(cond){ if (cond !== false) evaluate(exp.then, env, callback); else if (exp.else) evaluate(exp.else, env, callback); else callback(false); }); return; 

prog node diartikan mirip dengan let node, tetapi dengan perbedaan itu kita tidak perlu menyalin konteks atau mendefinisikan variabel. Dan lagi, kami memiliki fungsi loop yang mengambil nomor ekspresi. Ketika itu sama dengan prog.length , maka kami telah menyelesaikan semua ekspresi dan kami hanya mengembalikan hasil dari ekspresi terakhir (dengan kata "return" yang saya maksud kami sebut callback dengannya). Harap perhatikan bahwa kami mengingat nilai terakhir dengan meneruskannya sebagai argumen ke fungsi loop (pada awalnya itu false untuk kasus ketika tubuh kosong):

  case "prog": (function loop(last, i){ if (i < exp.prog.length) evaluate(exp.prog[i], env, function(val){ loop(val, i + 1); }); else { callback(last); } })(false, 0); return; 

Untuk simpul call tipe call kita perlu menafsirkan func dan kemudian semua argumen dalam urutan. Dan lagi, ada fungsi loop yang bekerja pada prinsip yang sama dengan let atau prog , dengan perbedaan yang sekarang ia membangun sebuah array sebagai hasilnya:

  case "call": evaluate(exp.func, env, function(func){ (function loop(args, i){ if (i < exp.args.length) evaluate(exp.args[i], env, function(arg){ args[i + 1] = arg; loop(args, i + 1); }); else { func.apply(null, args); } })([ callback ], 0); }); return; 

Nah, akhir standar: jika kita tidak tahu harus berbuat apa, lempar pengecualian:

  default: throw new Error("I don't know how to evaluate " + exp.type); } } 

Anda mungkin memperhatikan bahwa setiap case atas berakhir dengan kata kunci return . Tetapi tidak ada nilai balik - hasilnya selalu diteruskan ke fungsi callback .

Fungsi make_lambda baru

Dalam juru bahasa ini, semua fungsi akan menerima "kelanjutan" sebagai argumen pertama - fungsi yang harus kita panggil untuk memberikan hasil. Setelah itu adalah argumen biasa ke fungsi. Ini adalah kode baru untuk fungsi make_lambda :

 function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i + 1 < arguments.length ? arguments[i + 1] : false); evaluate(exp.body, scope, callback); } return lambda; } 

Dia tidak jauh berbeda. Ini menambahkan variabel baru ke konteks baru. Juga, kita harus mempertimbangkan bahwa argumen pertama adalah callback . Akhirnya, fungsi evaluate digunakan untuk mengeksekusi kode fungsi dalam konteks baru, tetapi, seperti sebelumnya, kami meneruskan callback .

Omong-omong, ini adalah satu-satunya tempat yang saya gunakan for loop. Ini karena nilai argumen sudah dihitung ketika node call diproses.

Fungsi asli

Dalam juru bahasa ini, fungsi asli menerima callback sebagai argumen pertama. Kita harus mengingat ini ketika kita mendefinisikan fungsi asli. Berikut ini contoh kode untuk juru bahasa baru:

 var code = "sum = lambda(x, y) x + y; print(sum(2, 3));"; var ast = parse(TokenStream(InputStream(code))); var globalEnv = new Environment(); // define the "print" primitive function globalEnv.def("print", function(callback, txt){ console.log(txt); callback(false); // call the continuation with some return value // if we don't call it, the program would stop // abruptly after a print! }); // run the evaluator evaluate(ast, globalEnv, function(result){ // the result of the entire program is now in "result" }); 

Tes kecil

Mari kita coba menghitung angka Fibonacci lagi:

 fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(10)) ); 

Tetapi, jika kita mencoba menemukan angka ke-27, maka kita mendapatkan stack overflow. Secara umum, tumpukan sekarang tumbuh jauh lebih cepat, sehingga ternyata sekarang kita dapat menghitung angka Fibonacci hanya sampai ke-12 (setidaknya di browser saya). Ini tidak terlalu bagus, jadi Anda harus memperbaikinya.

Kami melindungi tumpukan

Dalam interpreter CPS, stack tumbuh lebih cepat karena interpreter selalu memanggil fungsi secara rekursif, tidak pernah mengembalikan hasil. Meskipun kami telah return sebagai penerjemah, kami membutuhkan mereka, tetapi dalam kasus rekursi yang sangat dalam, kami tidak pernah mencapai mereka.

Mari kita bayangkan bagaimana tumpukan kita mencari program yang sangat sederhana. Saya akan menunjukkan kode pseudo dan saya tidak menambahkan env karena tidak memainkan peran apa pun di sini:

 print(1 + 2 * 3); ## : evaluate( print(1 + 2 * 3), K0 ) evaluate( print, K1 ) K1(print) #  'var',      evaluate( 1 + 2 * 3, K2 ) evaluate( 2 * 3, K3 ) evaluate( 2, K4 ) K4(2) # 2  ,      evaluate( 3, K5 ) #    3,      K5(3) K3(6) #  2*3 evaluate( 1, K6 ) #  ,  K6(1) K2(7) #  1+2*3 print(K0, 7) # ,     'print' K0(false) #  . 'print'  'false'. 

Hanya setelah panggilan terakhir, urutan panjang return tidak berguna mengurangi tumpukan. Jika kita menggunakan begitu banyak ruang stack untuk program sederhana, sulit untuk membayangkan apa yang akan terjadi untuk fib(13) .

Perlindungan tumpukan

Dalam juru bahasa baru kami, tumpukan tidak diperlukan. Semua itu perlu dilakukan setelah beberapa ekspresi terjadi dalam callback , yang diteruskan sebagai argumen. Jadi di sini kita punya pertanyaan: bagaimana jika JavaScript memungkinkan untuk "membuang" tumpukan. Lalu kita bisa menjatuhkan tumpukan, dan rekursi dalam yang tak terhingga akan bekerja.

Mari kita bayangkan bahwa kita memiliki fungsi GUARD yang dapat melakukan ini. Ia mendapat dua nilai: fungsi untuk memanggil, dan argumen yang harus dilewati. Ini memeriksa: jika tumpukan terlalu dalam, itu akan menghapus tumpukan dan memanggil fungsi yang lewat. Dalam kasus lain, dia tidak melakukan apa-apa.

Menggunakan fungsi baru, kami menulis ulang penerjemah seperti yang ditunjukkan di bawah ini. Saya tidak akan mengomentari setiap kasus individu, ada kode yang dijelaskan sebelumnya, tetapi menggunakan fungsi GUARD :

 function evaluate(exp, env, callback) { GUARD(evaluate, arguments); switch (exp.type) { case "num": case "str": case "bool": callback(exp.value); return; case "var": callback(env.get(exp.value)); return; case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function CC(right){ GUARD(CC, arguments); callback(env.set(exp.left.value, right)); }); return; case "binary": evaluate(exp.left, env, function CC(left){ GUARD(CC, arguments); evaluate(exp.right, env, function CC(right){ GUARD(CC, arguments); callback(apply_op(exp.operator, left, right)); }); }); return; case "let": (function loop(env, i){ GUARD(loop, arguments); if (i < exp.vars.length) { var v = exp.vars[i]; if (v.def) evaluate(v.def, env, function CC(value){ GUARD(CC, arguments); var scope = env.extend(); scope.def(v.name, value); loop(scope, i + 1); }); else { var scope = env.extend(); scope.def(v.name, false); loop(scope, i + 1); } } else { evaluate(exp.body, env, callback); } })(env, 0); return; case "lambda": callback(make_lambda(env, exp)); return; case "if": evaluate(exp.cond, env, function CC(cond){ GUARD(CC, arguments); if (cond !== false) evaluate(exp.then, env, callback); else if (exp.else) evaluate(exp.else, env, callback); else callback(false); }); return; case "prog": (function loop(last, i){ GUARD(loop, arguments); if (i < exp.prog.length) evaluate(exp.prog[i], env, function CC(val){ GUARD(CC, arguments); loop(val, i + 1); }); else { callback(last); } })(false, 0); return; case "call": evaluate(exp.func, env, function CC(func){ GUARD(CC, arguments); (function loop(args, i){ GUARD(loop, arguments); if (i < exp.args.length) evaluate(exp.args[i], env, function CC(arg){ GUARD(CC, arguments); args[i + 1] = arg; loop(args, i + 1); }); else { func.apply(null, args); } })([ callback ], 0); }); return; default: throw new Error("I don't know how to evaluate " + exp.type); } } 

Untuk fungsi anonim, kami perlu menambahkan nama agar kami bisa meneruskannya ke fungsi GUARD . Saya menggunakan nama CC ( current continuation ). Anda bisa menggunakan arguments.callee , tetapi ini adalah API yang sudah ketinggalan zaman.

Juga, perubahan yang sama pada make_lambda :

 function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { GUARD(lambda, arguments); // <--  var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i + 1 < arguments.length ? arguments[i + 1] : false); evaluate(exp.body, scope, callback); } return lambda; } 

Implementasi GUARD sangat sederhana. Bagaimana cara keluar dari panggilan yang dalam? Menggunakan pengecualian. Untuk melakukan ini, akan ada variabel global yang akan menunjukkan berapa banyak rekursi yang bisa kita lakukan. Jika mencapai nol, kita melempar objek Continuation , di mana akan ada lanjutan - fungsi dan argumen:

 var STACKLEN; function GUARD(f, args) { if (--STACKLEN < 0) throw new Continuation(f, args); } function Continuation(f, args) { this.f = f; this.args = args; } 

Dan pada akhirnya, kita membutuhkan sebuah loop yang akan menangkap objek Continuation . Kita harus memanggil juru bahasa melalui loop ini sehingga semuanya berfungsi:

 function Execute(f, args) { while (true) try { STACKLEN = 200; return f.apply(null, args); } catch(ex) { if (ex instanceof Continuation) f = ex.f, args = ex.args; else throw ex; } } 

Fungsi Execute menerima fungsi yang akan dipanggil dan argumen untuk itu. Ini bekerja dalam satu lingkaran, tetapi perhatikan untuk return jika fungsinya bekerja tanpa stack overflow, kami berhenti segera. STACKLEN diatur ulang setiap kali kami memulai perulangan berulang. Nilai 200 - pas. Ketika kita menangkap objek Continuation , kita mengganti fungsi dan argumen baru, dan melanjutkan loop. Selain itu, karena pengecualian, tumpukan dihapus, sehingga kami dapat melanjutkan.

Untuk memulai juru bahasa, kami sekarang menggunakan Execute :

 Execute(evaluate, [ ast, globalEnv, function(result){ console.log("*** Result:", result); }]); 

Tes

Fungsi fib sekarang akan bekerja:

 fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(20)) ); # 6765, ~300ms 

Sayang sekali, tetapi jika Anda mencoba untuk menemukan fib(27) , itu akan memakan waktu sekitar empat kali lebih lama dari seorang juru bahasa biasa. Tapi kemudian kita sekarang memiliki rekursi tak terbatas:

 sum = λ(n, ret) if n == 0 then ret else sum(n - 1, ret + n); # compute 1 + 2 + ... + 50000 time( λ() println(sum(50000, 0)) ); # 1250025000, ~700ms 

Tentu saja, bahasa λ jauh lebih lambat daripada JavaScript. Bayangkan saja, setiap akses ke variabel melewati objek Environment . Tidak masuk akal untuk mencoba mengoptimalkan juru bahasa - kita tidak akan mendapatkan perolehan kinerja yang signifikan. Untuk meningkatkan kinerja, ada satu solusi: kompilasi bahasa λ di JS, dan inilah yang akan kami lakukan. Pada awalnya, mari kita lihat hal menarik apa yang bisa kita lakukan dengan juru bahasa CPS.

Lanjutan

Sekarang interpreter bekerja dengan gaya kelanjutan transmisi, dan semua fungsi, baik fungsi λ bahasa dan fungsi JS asli, menerima fungsi kelanjutan sebagai argumen pertama untuk mengembalikan hasilnya (argumen ini diperlukan untuk fungsi JavaScript, meskipun tidak terlihat untuk fungsi bahasa λ).

Panggilan callback variabel berarti kelanjutan dari seluruh program. Semua itu akan dilakukan program selanjutnya. Kami akan memanggil variabel ini 'kelanjutan saat ini', atau k dalam kode.

Juga, jika kita tidak menyebabkan kelanjutan, maka program akan berhenti. Kami tidak dapat melakukan ini dari bahasa λ karena make_lambda memanggil kelanjutan. Tetapi kita dapat melakukan ini dari fungsi asli. Saya membuat fungsi untuk menunjukkan bagaimana ini bekerja:

 globalEnv.def("halt", function(k){}); 

Ini adalah fungsi yang tidak melakukan apa-apa. Dia menerima kelanjutan ( k ), tetapi tidak menyebutnya:

 println("foo"); halt(); println("bar"); 

Kesimpulan:

 foo 

Jika Anda menghapus panggilan halt() , hasilnya adalah: foo / bar / ***Result: false (karena println terakhir mengembalikan false ). Tetapi dengan halt() ini hanya menghasilkan foo . * Sekarang bahkan tidak ada hasil karena halt() tidak menyebabkan kelanjutan dan, oleh karena itu, panggilan balik yang kami lewati untuk evaluate - yang menampilkan string ***Result , tidak pernah dipanggil. Fungsi yang disebut evaluate tidak memperhatikan bahwa program telah berhenti. Di NodeJS, itu akan menjadi tembakan di kaki.

Bayangkan kita membutuhkan fungsi sleepe yang menghentikan suatu program tanpa menghentikan browser (oleh karena itu, tanpa loop bodoh). Kami dapat dengan mudah mengimplementasikan ini menggunakan fungsi asli:

 globalEnv.def("sleep", function(k, milliseconds){ setTimeout(function(){ Execute(k, [ false ]); //   ,  'false' }, milliseconds); }); 

Sedikit ketidaknyamanan adalah bahwa kita harus menggunakan Execute , karena setTimeout akan menyebabkan panggilan balik, yang kemudian melempar Continuation , dan tidak ada yang akan menangkapnya. Berikut cara menggunakannya:

 let loop (n = 0) { if n < 10 { println(n); sleep(250); loop(n + 1); } }; println("And we're done"); 

Kesimpulan:

 0 1 2 3 4 5 6 7 8 9 And we're done ***Result: false 

Catatan, ada sedikit keterlambatan antara setiap baris. Anda dapat mencoba menjalankan kode ini di artikel asli .

Ini sudah merupakan sesuatu yang tidak dapat Anda lakukan dalam JavaScript normal, kecuali untuk menggunakan transmisi manual kelanjutan (dan juga, Anda tidak dapat menggunakan loop for ):

 (function loop(n){ if (n < 10) { console.log(n); setTimeout(function(){ loop(n + 1); }, 250); } else { println("And we're done"); //    } })(0); 

Bayangkan bagaimana Anda dapat menggunakan API NodeJS dalam bahasa λ:

 globalEnv.def("readFile", function(k, filename){ fs.readFile(filename, function(err, data){ // error handling is a bit more complex, ignoring for now Execute(k, [ data ]); // hope it's clear why we need the Execute }); }); globalEnv.def("writeFile", function(k, filename, data){ fs.writeFile(filename, data, function(err){ Execute(k, [ false ]); }); }); 

Penggunaan:

 copyFile = λ(source, dest) { writeFile(dest, readFile(source)); }; copyFile("foo.txt", "bar.txt"); 

Dan semua ini bekerja secara serempak. Tidak ada lagi panggilan balik neraka.

Berikut ini contoh yang lebih menarik. Saya menulis fungsi asli berikut:

 globalEnv.def("twice", function(k, a, b){ k(a); k(b); }); 

Program ini mengambil dua argumen a dan b dan memanggil kelanjutan dua kali, satu kali untuk setiap argumen. Mari kita coba menyebutnya:

 println(2 + twice(3, 4)); println("Done"); 

Kesimpulan:

 5 Done ***Result: false 6 Done ***Result: false 

Kesimpulannya aneh jika Anda belum pernah bekerja dengan meneruskan kelanjutan sebelumnya, tetapi cobalah untuk memahami kode ini sendiri. Sedikit petunjuk: program dimulai sekali, tetapi mengembalikan hasilnya dua kali.

Generalisasi: CallCC

Kami dulu bermain dengan api ketika kami menulis fungsi asli. Tidak ada cara dalam bahasa λ untuk mengganggu pelaksanaan kelanjutan saat ini. CallCC akan membantu menyelesaikan masalah ini. Namanya adalah singkatan dari fungsi dari Skema - call-with-current-continuation (yang biasanya disebut panggilan / cc dalam Skema).

 globalEnv.def("CallCC", function(k, f){ f(k, function CC(discarded, ret){ k(ret); }); }); 

Ini memverifikasi kelanjutan saat ini menjadi fungsi yang dapat dipanggil langsung dari bahasa λ. Fungsi ini akan mengabaikan kelanjutan discarded asli dan sebaliknya akan memanggil kelanjutan yang diteruskan ke fungsi CallCC .

Dengan menggunakan fungsi ini, kita dapat mengimplementasikan (sudah secara langsung dalam bahasa, bukan melalui fungsi asli!) Satu set besar pernyataan kontrol untuk aliran eksekusi yang bahkan tidak kita pikirkan sebelumnya - mulai dari pengecualian dan diakhiri dengan return . Mari kita mulai dari yang terakhir.

Pengembalian implementasi

 foo = λ(return){ println("foo"); return("DONE"); println("bar"); }; CallCC(foo); 

Kesimpulan:

 foo ***Result: DONE 

Fungsi foo menerima argumen yang melakukan hal yang sama seperti return dari JavaScript (tetapi disebut sebagai fungsi biasa). Itu melewatkan kelanjutan saat ini (yang akan menampilkan 'bar') dan keluar dari fungsi, mengembalikan nilai yang diberikan ("DILAKUKAN"). Tentu saja, ini hanya berfungsi jika Anda memanggil fungsi menggunakan CallCC untuk meneruskan kelanjutan sebagai return . Kami dapat membuat pembungkus untuk ini:

 with-return = λ(f) λ() CallCC(f); foo = with-return(λ(return){ println("foo"); return("DONE"); println("bar"); }); foo(); 

Kesimpulan:

 foo ***Result: DONE 

Keuntungan dari metode ini adalah bahwa kita tidak perlu lagi menggunakan CallCC ketika kita memanggil foo . Akan menyenangkan, tentu saja, jika kita tidak perlu menerima return sebagai argumen atau menggunakan fungsi with-return , tetapi dalam bahasa tidak ada cara untuk menambahkan gula sintaksis langsung dari itu, untuk ini kita setidaknya perlu memodifikasi parser (+1 untuk Lisp).

Transisi

Sebagai contoh, kita perlu menulis sebuah program yang akan mencari semua pasangan bilangan bulat positif hingga 100 sehingga jika perkaliannya menghasilkan 84. Ini bukan tugas yang sulit dan Anda bisa langsung membayangkan dua loop bersarang untuk menyelesaikannya, tetapi di sini kita pergi dengan cara yang berbeda. Kami akan membuat dua fungsi: guess dan fail . Yang pertama akan memilih nomornya, dan yang kedua memberi tahu dia "coba nomor lain." Kami akan menggunakannya seperti ini:

 a = guess(1); #  -  >= 1 b = guess(a); #  -  >= a if a * b == 84 { #    : print(a); print(" x "); println(b); }; fail(); #    `guess`     

:

 fail = λ() false; guess = λ(current) { CallCC(λ(k){ let (prevFail = fail) { fail = λ(){ current = current + 1; if current > 100 { fail = prevFail; fail(); } else { k(current); }; }; k(current); }; }); }; a = guess(1); b = guess(a); if a * b == 84 { print(a); print(" x "); println(b); }; fail(); 

, , a , 84 , b , 84 / a . guess : start end — . , .

try catch Common Lisp

— catch throw . :

 f1 = λ() { throw("foo", "EXIT"); print("not reached"); }; println(catch("foo", λ() { f1(); print("not reached"); })); #  EXIT 

• catch(TAG, function) , , TAG ', function .
• throw(TAG, value) , , TAG ' , value .

:

 ##  , 'throw'   . ##       `error`, ##     JavaScript.    . throw = λ(){ println("ERROR: No more catch handlers!"); halt(); }; catch = λ(tag, func){ CallCC(λ(k){ let (rethrow = throw, ret) { ##   ,     . throw = λ(t, val) { throw = rethrow; #   ,   . if t == tag then k(val) else throw(t, val); }; ##      . ret = func(); ##       (  'throw') ##    .   . throw = rethrow; # XXX ##  . ret; }; }); }; 

Contoh:

 # ... f1 = λ() { throw("foo", "EXIT"); print("not reached"); }; println(catch("foo", λ() { f1(); print("not reached"); })); 

catch , , , . , , , CallCC . , . " " — — . , , , catch / throw , .

. , catch . , throw , , catch , . Sebagai contoh:

 exit = false; #  . x = 0; # :   ,   'exit()'  CallCC( λ(k) exit = k ); ## 'exit()'   ... if x == 0 then catch("foo", λ(){ println("in catch"); x = 1; #  exit(); }); println("After catch"); throw("foo", "FOO"); 

Kesimpulan:

 After catch After catch ERROR: No more catch handlers! 

'After catch' , 'ERROR: No more catch handlers!'. - , 'After catch' , . , '' , catch . , 'XXX' catch , throw , catch .

( , .)

CallCC (, , CallCC ). , — CallCC .

Yield

, , yield :

 foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); # 1 println(foo()); # 2 println(foo()); # 3 println(foo()); # DONE 

yield , . , return . , , yield , .

:

 fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; }); ##   50   let loop (i = 0) { if i < 50 { println(fib()); loop(i + 1); }; }; 

fib . . yield . , , 50 , 50 .

, , , , .

, .

yield , , . , , return . , , yield , yield , . , . :

 with-yield = λ(func) { ## with-yield     λ() { CallCC(λ(kret){ # kret     let (yield) { ##  yield yield = λ(value) { # yield  ,    CallCC(λ(kyld){ # kyld    yield... func = kyld; # ...     kret(value); #  . }); }; ## , ,  ,   yield. func(yield); }; }); }; }; 

yield , . , , , "DONE".

, . , - , , 4 :

 println(foo()); foo(); 

.

№1: yield

, , , , yield ( kyld , , ) :

  yield(2); yield(3); "DONE"; 

yield ? yield , , yield . , . , yield return , :

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); # 'return'  ,     }); #        . }; # λ(val) { # CallCC(λ(kret){ # return = kret; # <-  func(val || yield); }); }; }; }; 

, , yield , yield ( ). yield .

, , println(foo()) :

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; func(val || yield); }); }; }; }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); println(foo()); println(foo()); 

, . , print(foo()); foo() . , println(foo()) ? ...

№2: WTF?

. : , foo() . , ? — .

 println(foo()); ## yield 1 <-----------------  ---------------------------+ println(foo()); ## yield 2 | println(foo()); ## yield 3 | println(foo()); ##   "DONE",   foo()  -->--+ 

with-yield :

  func(val || yield); #... 

yield , , #... . , , ( "DONE" ), , "DONE" , . foo() , "DONE" . :

 println(foo()); println("bar"); println(foo()); println(foo()); foo(); 

: 1, bar, 2, 3, DONE, bar, DONE, bar, ... .

func - , . , "no more continuations" :

  val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); 

:

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); }); }; }; }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); println(foo()); println(foo()); println(foo()); 

, :

 1 2 3 DONE NO MORE CONTINUATIONS NO MORE CONTINUATIONS NO MORE CONTINUATIONS ***Result: false 

1, 2, 3, DONE , "NO MORE CONTINUATIONS" . , :

 print("A. "); println(foo()); print("B. "); println(foo()); print("C. "); println(foo()); print("D. "); println(foo()); ##   : A. 1 B. 2 C. 3 D. DONE B. NO MORE CONTINUATIONS C. NO MORE CONTINUATIONS D. NO MORE CONTINUATIONS ***Result: false 

, : , , , , "B." .

, yield , :

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); }); }; }; }; fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; }); ##   50   let loop (i = 0) { if i < 50 { println(fib()); loop(i + 1); }; }; 

 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 ***Result: false 

, (, ), " ".

: reset shift

yield : reset shift . " " — , . reset , shift , CallCC .

, reset shift — . reset , shift , reset .

, with-yield :

 with-yield = λ(func) { let (yield) { ## 'yield'  'shift'     ##  'reset'.  ,   ,    ##   'func' — ,   `func()` ##    ,    . yield = λ(val) { shift(λ(k){ func = k; #    val; #    }); }; ##  `with-yield`      ##   'reset',    ,  ##   'yield' ( )    ##    λ(val) { reset( λ() func(val || yield) ); }; } }; 

, reset . , , , reset . , . , .

:

 with-yield = λ(func) { let (yield) { yield = λ(val) { shift(λ(k){ func = k; val; }); }; λ(val) { reset( λ() func(val || yield) ); }; } }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); #  1 println(foo()); #  2 println(foo()); #  3 println(foo()); #  DONE 

reset shift

, . . . , , , . Scheme ( — Oleg Kiselyov ). .

, ( CallCC ) . :

 var pstack = []; function _goto(f) { f(function KGOTO(r){ var h = pstack.pop(); h(r); }); } globalEnv.def("reset", function(KRESET, th){ pstack.push(KRESET); _goto(th); }); globalEnv.def("shift", function(KSHIFT, f){ _goto(function(KGOTO){ f(KGOTO, function SK(k1, v){ pstack.push(k1); KSHIFT(v); }); }); }); 

, reset , shift _goto , — . . _goto ( KGOTO ). , f ( CallCC ) - KGOTO , . , f , , KGOTO , , .

reset ( KRESET ) _goto(th) . , , , _goto . , , KGOTO KRESET .

, shift KGOTO , KGOTO pstack , SK , , shift ( shift — KSHIFT ). SK — — ( k1 ) . , shift2 , , pstack.push(k1); :

 println(reset(λ(){ 1 + shift( λ(k) k(k(2)) ); })); println(reset(λ(){ 1 + shift2( λ(k) k(k(2)) ); })); 

Kesimpulan:

 4 3 ***Result: false 

shift ( k ), reset . — 1 shift :

 1 + [?] 

k , ? . — k(k(2)) . 2 , k(2) 3. , k(3) 3 , 4.

shift2 : k(2) .

CallCC

, , CallCC , . , JS, , , . , CallCC , .

Bagian yang paling menarik dari kode ini adalah bagaimana kami mengimplementasikannya gotodan mengapa kami melakukannya dengan cara ini (tetapi cobalah untuk mencari tahu sendiri):

 pstack = NIL; goto = false; reset = λ(th) { CallCC(λ(k){ pstack = cons(k, pstack); goto(th); }); }; shift = λ(f) { CallCC(λ(k){ goto(λ(){ f(λ(v){ CallCC(λ(k1){ pstack = cons(k1, pstack); k(v); }); }); }); }); }; let (v = CallCC( λ(k){ goto = k; k(false) } )) { if v then let (r = v(), h = car(pstack)) { pstack = cdr(pstack); h(r); } }; 

Di bagian artikel selanjutnya, kita akan mulai mengerjakan kompiler - sekarang kode kita juga akan bekerja dengan cepat!