Cheney di MTA: kompiler di mana tumpukan juga berfungsi sebagai heap

 

Apakah dia pernah kembali? Tidak, dia tidak pernah kembali,

Dan nasibnya masih belum dipelajari,

Dia mungkin berkendara selamanya di jalanan Boston,

Dia orang yang tidak pernah kembali.



"Charlie di MTA", 1949

1. Penutupan

Salah satu fitur praktis dari bahasa pemrograman modern adalah fungsi bersarang:

def bubble(arr, comp):

    def swap(i, j):
        temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp

    flag = True
    while flag:
        flag = False
        for i in range(len(arr) - 1):
            if comp(arr[i], arr[i+1]) > 0:
                swap(i, i+1)
                flag = True

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Kemungkinan ini sendiri bukanlah hal baru: itu sudah ada di Algol (1958) dan akrab bagi banyak orang dari Pascal (1970). Mengompilasi fungsi bersarang itu mudah: misalnya, bingkai tumpukan fungsi bagian dalam dapat menyimpan penunjuk ke bingkai tumpukan fungsi luar sehingga fungsi bagian dalam dapat mengakses parameter dan variabel lokal dari yang terluar. Seseorang mungkin ingat bahwa instruksi enter



dan leave



, yang muncul pada 80186 (1982), mengimplementasikan dengan tepat jenis dukungan ini untuk fungsi bersarang (walaupun saya belum pernah melihat kompiler yang melakukannya).



Kesulitan dimulai jika bahasa memungkinkan Anda mentransfer fungsi internal di luar fungsi eksternal:

def by_field(name):

    def comp(x, y):
        return x[name] – y[name]

    return comp

bubble(my_records, by_field("year"))

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Bagaimana fungsi bagian dalam mengakses parameter dan variabel lokal dari luar setelah kembali dari fungsi luar telah menghancurkan bingkai tumpukannya? Entah bagaimana fungsi bagian dalam harus "mengambil" variabel yang digunakan bersama dengannya; fungsi bersama dengan variabel yang ditangkap secara eksternal disebut "penutupan". Pascal tidak lagi mendukung ini; tetapi misalnya, di C # 7 (2017), untuk ini, sebuah objek dibuat di heap, berisi semua parameter dan variabel lokal yang dirujuk oleh fungsi internal; dan panggilan baik dari itu maupun dari fungsi eksternal tidak pergi ke nilai di tumpukan, tetapi ke bidang objek di heap. Apakah mungkin dilakukan tanpa kerumitan ini, dan terus bekerja dengan stack - untuk menghindari pengalamatan tidak langsung yang tidak perlu dan mempertahankan lokalitas panggilan, dan tidak mengotori cache data dengan lompatan di heap?

2. Melewati Lanjutan

Saat menyusun bahasa pemrograman fungsional, di mana menangkap variabel lokal dengan fungsi kembali adalah teknik yang sangat umum, langkah pertama adalah menerjemahkan seluruh program ke dalam "Continuation-passing style" (CPS). hasil dari fungsi diganti dengan callback eksplisit yang diteruskan ke setiap fungsi sebagai argumen tambahan. Misalnya, dalam fungsi sederhana ini yang menghitung produk dari semua bilangan prima dari 1 hingga n



inklusif:

def prodprimes(n):
    if n == 1:
        return 1
    elif isprime(n):
        return n * prodprimes(n-1)
    else:
        return prodprimes(n-1)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- prodprimes



alamat pengirim yang berbeda secara implisit ditransfer ke dua panggilan . Jika alamat ini ditetapkan sebagai j



dan h



, dan alamat pengirim diteruskan sebagai argumen eksplisit c



, maka seluruh transfer kontrol dapat dibuat eksplisit:

def prodprimes(n, c):
    if n == 1:
        c(1)
    else:
        def k(b):
            if b:
                def j(p):
                    c(n * p)
                prodprimes(n-1, j)
            else:
                def h(q):
                    c(q)
                prodprimes(n-1, h)
        isprime(n, k)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Dalam CPS, tidak ada perbedaan antara memanggil fungsi dan mengembalikan nilai dari fungsi - keduanya diabstraksi sebagai "berikan nilai ke alamat yang ditentukan". Teknik ini telah digunakan di sebagian besar penyusun Skema sejak pertama (1975); seluruh buku "Compiling with Continuations" (1992) dikhususkan untuknya, dari mana contoh di atas diambil. Baru-baru ini, gaya pemrograman serupa telah menjadi populer dengan nama "janji".



Alasan mengapa CPS digunakan secara internal oleh kompiler sebagai representasi perantara sebelum SSA(ditemukan pada tahun 1988) telah menjadi lebih populer - kesederhanaan: ini bukan bahasa lain dengan aturannya sendiri, tetapi sub-bahasa dari PL asli dengan batasan bahwa fungsi atau panggilan lanjutan hanya diperbolehkan sebagai fungsi terakhir atau operator lanjutan. Mudah untuk menerjemahkan kode PL ke dalam CPS dengan satu set transformasi formal, dan mudah untuk menerapkan transformasi sederhana ke kode CPS - misalnya, mengetahui bahwa kelanjutannya h



sepele dan mengganti penggunaannya h



dengan c



. Fitur penting CPS bagi kami adalah bahwa closure digunakan dalam lingkup yang sama di mana mereka dideklarasikan, dan oleh karena itu dapat mengakses variabel yang diambil dari luar dengan cara yang sama seperti pada 80186 - melalui pointer ke frame stack eksternal:

def by_field(name, c):

    def comp(x, y, c):
        c(x[name] – y[name])

    c(comp)

def by_year(comp):
    bubble(my_records, comp, halt)

by_field("year", by_year)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Setelah dikonversi ke CPS comp



, ia mengetahui bahwa itu sendiri adalah fungsi bersarang 2, dan nilainya name



terletak pada bingkai bersarang 1, jadi kompilasi panggilan ke name



tidak akan menimbulkan kesulitan.



Tetapi CPS memiliki kelemahan: karena kelanjutan tidak pernah dijalankan return



maka tumpukan bingkai mereka tidak pernah dihancurkan dan tumpukan akan meluap dengan sangat cepat. Di sisi lain, kelanjutan mungkin memerlukan bingkai tumpukan tertentu, baik jika bingkai itu sendiri merujuk padanya, atau jika ia menerima sebagai parameter kelanjutan yang merujuk ke bingkai ini. Selain itu, transisi ke kelanjutan berikutnya harus menjadi tindakan terakhir di dalam kelanjutan, sehingga alamat dan parameter kelanjutan berikutnya dapat dianggap sebagai hasil kelanjutan. (Model "promise" mengembalikan hasil ini secara eksplisit.) Kompiler Skema klasik menggunakan dispatcher sebagai loop tak terbatas berikut:

1. Jalankan kelanjutan saat ini dan dapatkan alamat dan parameter kelanjutan berikutnya sebagai hasilnya;
2. Periksa frame tumpukan mana yang dapat diakses oleh parameter kelanjutan dan kelanjutan berikutnya yang diteruskan padanya;
3. , .

Dengan implementasi ini, tumpukan panggilan sistem tidak digunakan, dan transisi antara operator dan kelanjutan diimplementasikan seperti biasa jmp



. Bingkai kelanjutan dipisahkan dari tumpukan panggilan dan dihancurkan dalam urutan acak, bukan LIFO , sehingga koleksinya dapat dianggap sebagai tumpukan dan juga tumpukan.



Seperti yang Anda duga, dengan pemeriksaan tumpukan pada setiap cabang di antara kelanjutan, kinerja program meninggalkan banyak hal yang diinginkan. Salah satu pengoptimalan yang mungkin adalah memeriksa ukuran tumpukan saat ini sebelum keluar dari kelanjutan, dan jika tidak melebihi ambang batas yang ditentukan, langsung lanjutkan ke kelanjutan berikutnya; jika tidak, transfer kontrol ke petugas operator sehingga ia mengumpulkan semua sampah dari tumpukan. Lulusan Boston MIT Henry Baker mengomentari pendekatan ini: "alih-alih melompat-lompat di atas trampolin sepanjang waktu, kami melompat dari Empire State Building - tetapi lebih jarang."

3. Di MTA

Pada tahun 1948, Boston Metro (Metropolitan Transit Authority) menaikkan tarif dari 10 sen menjadi 15 sen. Alih-alih mengganti semua uang receh, di pintu masuk kereta bawah tanah, kondektur diperintahkan untuk mengenakan biaya tambahan lima sen saat keluar dari kereta. Mengolok-olok pendekatan ini, seorang calon walikota Boston memerintahkan rekaman lagu tentang Charlie tertentu, yang tidak memiliki cukup uang untuk membayar keluar, dan dia ditakdirkan untuk naik kereta bawah tanah tanpa henti. Kandidat mendapatkan reputasi sebagai komunis, hanya memenangkan 1,2% suara dalam pemilihan, dan meninggalkan politik selamanya; Tetapi lagu tentang penumpang yang tidak pernah kembali ke permukaan bumi ternyata jauh lebih populer: bahkan kartu kereta bawah tanah Boston, yang diperkenalkan pada tahun 2006, disebut CharlieCard untuk menghormati penumpang yang sama itu.



Kisah Charlie mengilhami Henry Baker untuk menulis kompiler Skema pada tahun 1994 yang mengubah setiap kelanjutan menjadi fungsi C sehingga eksekusi fungsi tersebut tidak pernah mencapai return



: misalnya,

(define (revappend old new)
  (if (null? old)
      new
      (revappend (cdr old) (cons (car old) new))))

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- berubah menjadi

void revappend(clos_type *cont, cons_type *old, cons_type *new) {
  if (old == NIL) {
    /* Call continuation with new as result. */
    return (cont->fn)(cont->env, new);
  }
  cons_type newer; /* Should check stack here. */
  /* Code for (revappend (cdr old) (cons (car old) new)). */
  newer.tag = cons_tag; newer.car = old->car; newer.cdr = new;
  return revappend(cont, old->cdr, &newer);
}

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Arti dari operator return



setelah konversi tersebut adalah untuk memberitahu compiler C bahwa tidak perlu menyimpan register sebelum memanggil kelanjutan; sebenarnya, fungsi yang disebut operand return



tidak akan pernah kembali. Di tempat yang ditandai sebagai /* Should check stack here. */



, pemeriksaan ukuran tumpukan dimasukkan, dan jika perlu, petugas operator dipanggil untuk pengumpulan sampah.



Pendekatan ini memiliki beberapa keunggulan dibandingkan yang klasik:

1. Scheme : ; – , .. (varargs); – , .. (VLA). 21 . LLVM, .
2. ABI – , Scheme. «» , CPS, . «» callback- «» , , , «» – , . Scheme, map



fold
   
   
   
   , , .

Di sisi lain, C tidak mendukung fungsi bertingkat, yang berarti bahwa semua pointer ke variabel yang diambil dari luar harus diteruskan secara eksplisit bersama dengan closure. Selain itu, ketika menempatkan frame lanjutan pada tumpukan sistem alih-alih yang ditulis sendiri, masalah muncul: bagaimana menerapkan pengumpulan sampah untuk tumpukan sistem, yang tidak terikat ke perangkat kompilator C tertentu pada arsitektur tertentu?

4. Pengumpul sampah Cheney

Pengumpul sampah yang paling pertama dan paling sederhana diimplementasikan pada tahun 1969 untuk LISP: saat setengah dari heap sudah penuh, program berhenti, dan semua data "langsung" dipindahkan secara rekursif (depth-first traversal) ditransfer ke paruh kedua heap. Pada tahun 1970, Chris Cheney - juga di Cambridge, tetapi di sisi lain lautan dari MIT - memperhatikan bahwa dengan melintasi data langsung secara luas, kolektor itu sendiri tidak memerlukan memori tambahan selama pembuatan; Sejak itu, pengumpulan sampah dengan menghentikan program dan memindahkan objek langsung ke paruh kedua heap disebut "algoritma Cheney". Kelemahan utamanya adalah bahwa data langsung hanya dapat menempati setengah dari memori yang tersedia, dan paruh kedua ditempati oleh "buffer untuk penyalinan".



Efisiensi pengumpulan sampah dapat ditingkatkan dengan mengamati bahwa data dalam program tipikal dibagi menjadi "berumur sangat pendek" dan "berumur sangat panjang": jika sebuah objek selamat dari satu pengumpulan sampah, sangat mungkin untuk bertahan pada pengumpulan sampah berikutnya koleksi juga. Oleh karena itu, heap dibagi menjadi "kamar bayi" untuk objek yang baru dibuat, dan "heap dewasa" yang terdiri dari dua bagian. Saat pembibitan penuh, data langsung darinya dipindahkan ke tumpukan dewasa; saat satu setengah dari tumpukan dewasa meluap, data langsung darinya akan dibawa ke setengah lainnya. Ini menghemat memori (tidak ada ruang yang dicadangkan untuk data berumur pendek di paruh kedua heap) dan waktu pembuatan (data berumur panjang tidak disalin bolak-balik dengan setiap pengumpulan sampah di pembibitan).



Saat menggunakan "Cheney di MTA", tumpukan bertindak sebagai cattery. Petugas operator yang dipanggil pada stack overflow secara eksplisit menerima sebagai penunjuk parameter ke semua data langsung: ini semua adalah parameter dan variabel lokal dari kelanjutan panggilan, termasuk variabel yang ditangkap yang diteruskan ke kelanjutan sebagai parameter implisit. Tidak seperti pengumpul sampah tradisional, Cheney di MTA tidak perlu mencari data langsung di dalam tumpukan: CPS memastikan bahwa semua data di bawah bingkai tumpukan terakhir sudah mati jika tidak tersedia dari bingkai terakhir. Ini berarti bahwa pengumpul sampah tidak peduli tentang struktur bingkai tumpukan, atau kemungkinan adanya bingkai "asing" dalam tumpukan, yang tersisa dari fungsi dalam bahasa lain.







Pendekatan "Cheney on the MTA" digunakan dalam penyusun Skema C "Skema Ayam" (2000) dan "Skema Siklon" (2016). Di Cyclone, untuk ide lama Baker, mereka menambahkan dukungan untuk pengumpulan sampah paralel, ketika hanya satu utas yang dihentikan selama pengumpulan, yang tumpukannya sedang diproses, dan sisanya terus berfungsi.