Mengapa trampolin bekerja?

Saya telah melakukan beberapa JavaScript fungsional. Saya mengira bahwa Tail-Call Optimization telah diterapkan, tetapi ternyata saya salah. Jadi, saya harus belajar sendiri Trampolining . Setelah sedikit membaca di sini dan di tempat lain, saya bisa mendapatkan dasar-dasarnya dan membangun trampolin pertama saya:

/*not the fanciest, it's just meant to
reenforce that I know what I'm doing.*/

function loopy(x){
    if (x<10000000){ 
        return function(){
            return loopy(x+1)
        }
    }else{
        return x;
    }
};

function trampoline(foo){
    while(foo && typeof foo === 'function'){
        foo = foo();
    }
    return foo;
/*I've seen trampolines without this,
mine wouldn't return anything unless
I had it though. Just goes to show I
only half know what I'm doing.*/
};

alert(trampoline(loopy(0)));

Masalah terbesar saya, adalah saya tidak tahu mengapa ini berhasil. Saya mendapatkan ide untuk menjalankan kembali fungsi dalam loop sementara daripada menggunakan loop rekursif. Kecuali, secara teknis fungsi basis saya sudah memiliki loop rekursif. Saya tidak menjalankan loopyfungsi dasar , tetapi saya menjalankan fungsi di dalamnya. Apa yang berhenti foo = foo()menyebabkan stack overflow? Dan bukankah secara foo = foo()teknis bermutasi, atau apakah saya melewatkan sesuatu? Mungkin itu hanya kejahatan yang perlu. Atau beberapa sintaks yang hilang.

Apakah ada cara untuk memahaminya? Atau hanya beberapa retasan yang entah bagaimana berhasil? Saya sudah bisa melewati semua yang lain, tetapi yang ini membuat saya bingung.

Alasan otak Anda memberontak terhadap fungsi tersebut loopy()adalah karena ia merupakan jenis yang tidak konsisten :

function loopy(x){
    if (x<10000000){ 
        return function(){ // On this line it returns a function...
            // (This is not part of loopy(), this is the function we are returning.)
            return loopy(x+1)
        }
    }else{
        return x; // ...but on this line it returns an integer!
    }
};

Cukup banyak bahasa bahkan tidak membiarkan Anda melakukan hal-hal seperti ini, atau setidaknya menuntut lebih banyak mengetik untuk menjelaskan bagaimana ini seharusnya masuk akal. Karena sebenarnya tidak. Fungsi dan bilangan bulat adalah jenis objek yang sama sekali berbeda.

Jadi mari kita lalui loop sementara, dengan hati-hati:

while(foo && typeof foo === 'function'){
    foo = foo();
}

Awalnya, foosama dengan loopy(0). Apa loopy(0)? Yah, itu kurang dari 10.000.000, jadi kita dapatkan function(){return loopy(1)}. Itu nilai yang benar, dan itu adalah fungsi, jadi perulangan terus berjalan.

Sekarang kita sampai foo = foo(). foo()sama dengan loopy(1). Karena 1 masih kurang dari 10.000.000, itu kembali function(){return loopy(2)}, yang kemudian kami tetapkan foo.

foomasih berfungsi, jadi kami terus berjalan ... sampai akhirnya foo sama dengan function(){return loopy(10000000)}. Itu fungsi, jadi kita melakukan foo = foo()sekali lagi, tapi kali ini, ketika kita memanggil loopy(10000000), x tidak kurang dari 10000000 jadi kita hanya mendapatkan x kembali. Karena 10000000 juga bukan fungsi, ini mengakhiri loop sementara juga.

Kevin dengan singkat menunjukkan bagaimana potongan kode khusus ini bekerja (bersama dengan mengapa itu cukup tidak bisa dipahami), tetapi saya ingin menambahkan beberapa informasi tentang bagaimana trampolin pada umumnya bekerja.

Tanpa optimasi tail-call (TCO), setiap panggilan fungsi menambahkan bingkai tumpukan ke tumpukan eksekusi saat ini. Misalkan kita memiliki fungsi untuk mencetak hitungan mundur angka:

function countdown(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    countdown(n - 1);
  }
}

Jika kita menelepon countdown(3), mari kita menganalisis bagaimana tumpukan panggilan akan terlihat tanpa TCO.

> countdown(3);
// stack: countdown(3)
Launch in 3
// stack: countdown(3), countdown(2)
Launch in 2
// stack: countdown(3), countdown(2), countdown(1)
Launch in 1
// stack: countdown(3), countdown(2), countdown(1), countdown(0)
Blastoff!
// returns, stack: countdown(3), countdown(2), countdown(1)
// returns, stack: countdown(3), countdown(2)
// returns, stack: countdown(3)
// returns, stack is empty

Dengan TCO, setiap panggilan rekursif countdownberada di posisi ekor (tidak ada yang tersisa untuk dilakukan selain mengembalikan hasil panggilan) sehingga tidak ada bingkai tumpukan yang dialokasikan. Tanpa TCO, tumpukan meledak bahkan sedikit besar n.

Trampolining mengatasi batasan ini dengan memasukkan pembungkus di sekitar countdownfungsi. Kemudian, countdowntidak melakukan panggilan rekursif dan sebaliknya segera mengembalikan fungsi untuk memanggil. Berikut ini contoh implementasi:

function trampoline(firstHop) {
  nextHop = firstHop();
  while (nextHop) {
    nextHop = nextHop()
  }
}

function countdown(n) {
  trampoline(() => countdownHop(n));
}

function countdownHop(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    return () => countdownHop(n-1);
  }
}

Untuk lebih memahami bagaimana ini bekerja, mari kita lihat tumpukan panggilan:

> countdown(3);
// stack: countdown(3)
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(3)
Launch in 3
// return next hop from countdownHop(3)
// stack: countdown(3), trampoline
// trampoline sees hop returned another hop function, calls it
// stack: countdown(3), trampoline, countdownHop(2)
Launch in 2
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(1)
Launch in 1
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(0)
Blastoff!
// stack: countdown(3), trampoline
// stack: countdown(3)
// stack is empty

Pada setiap langkah countdownHopfungsi mengabaikan kontrol langsung dari apa yang terjadi selanjutnya, alih-alih mengembalikan fungsi untuk memanggil yang menggambarkan apa yang ingin terjadi selanjutnya. Fungsi trampolin kemudian mengambil ini dan menyebutnya, lalu memanggil fungsi apa pun yang kembali, dan seterusnya hingga tidak ada "langkah selanjutnya". Ini disebut trampolining karena aliran kontrol "memantul" antara setiap panggilan rekursif dan implementasi trampolin, alih-alih fungsi yang berulang secara langsung. Dengan mengabaikan kontrol siapa yang melakukan panggilan rekursif, fungsi trampolin dapat memastikan tumpukan tidak terlalu besar. Catatan: implementasi ini trampolinemenghilangkan nilai yang dikembalikan untuk kesederhanaan.

Sulit untuk mengetahui apakah ini ide yang bagus. Kinerja dapat menurun karena setiap langkah mengalokasikan penutupan baru. Optimalisasi yang cerdik dapat membuat ini layak, tetapi Anda tidak pernah tahu. Trampolining sebagian besar berguna untuk mengatasi batas rekursi keras, misalnya ketika implementasi bahasa menetapkan ukuran tumpukan panggilan maksimum.

Mungkin menjadi lebih mudah untuk dipahami jika trampolin diimplementasikan dengan tipe pengembalian khusus (alih-alih menyalahgunakan fungsi):

class Result {}
// poor man's case classes
class Recurse extends Result {
    constructor(a) { this.arg = a; }
}
class Return extends Result {
    constructor(v) { this.value = v; }
}

function loopy(x) {
    if (x<10000000)
        return new Recurse(x+1);
    else
        return new Return(x);
}

function trampoline(fn, x) {
    while (true) {
        const res = fn(x);
        if (res instanceof Recurse)
            x = res.arg;
        else if (res instanceof Return)
            return res.value;
    }
}

alert(trampoline(loopy, 0));

Bandingkan ini dengan versi Anda trampoline, di mana case rekursi adalah ketika fungsi mengembalikan fungsi lain, dan case dasar adalah ketika ia mengembalikan sesuatu yang lain.

Apa yang berhenti foo = foo()menyebabkan stack overflow?

Itu tidak menyebut dirinya lagi. Sebagai gantinya, ia mengembalikan hasil (dalam implementasi saya, secara harfiah a Result) yang menyampaikan apakah akan melanjutkan rekursi atau apakah akan keluar.

Dan bukankah secara foo = foo()teknis bermutasi, atau apakah saya melewatkan sesuatu? Mungkin itu hanya kejahatan yang perlu.

Ya, inilah persisnya kejahatan yang diperlukan dalam lingkaran itu. Seseorang dapat menulis trampolinetanpa mutasi juga, tetapi itu akan membutuhkan rekursi lagi:

function trampoline(fn, x) {
    const res = fn(x);
    if (res instanceof Recurse)
        return trampoline(fn, res.arg);
    else if (res instanceof Return)
        return res.value;
}

Tetap saja, ini menunjukkan gagasan tentang apa fungsi trampolin bahkan lebih baik.

Titik trampol adalah abstrak panggilan ekor-rekursif dari fungsi yang ingin menggunakan rekursi menjadi nilai kembali, dan melakukan rekursi aktual hanya di satu tempat - trampolinefungsi, yang kemudian dapat dioptimalkan di satu tempat untuk menggunakan lingkaran.