Geliştirici, çalışan bir Python yorumlayıcısını 1024 baytlık C koduna sığdırdı

Katı sınırlarla bir hafta sonu meydan okuması

Austin Z. Henley, tam olarak 1.024 baytlık C kaynak kodundan oluşan, bir sohbet mesajına yapıştırılacak kadar küçük, Python'ın bir alt kümesi için çalışan bir yorumlayıcı yayımladı. Hafta sonu el yazımı alıştırması olarak yazılan program, def, iki nokta, girintiye duyarlı bloklar ve parantezsiz if deyimleriyle sıradan Python gibi okunan bir FizzBuzz betiğini çalıştırıyor. Yazı, Hacker News'in ana sayfasında öne çıkarıldı.

Henley ilk sınırı düz C'de 512 bayt olarak belirledi ve kendisine önişlemci hilelerini ve kütüphane yan çözümlerini yasakladı. İlk denemesi tanıdık yolu izledi: 1 + 2 değerlendirmesinden x = 1 + 2 * 3 gibi atamalara ve if x > y: z = 3 gibi koşullara uzanan özyinelemeli iniş çözümleyicisi. Anlattığına göre sonuç Python'dan çok bir hesap makinesiydi ve bayt bütçesini çoktan aşmıştı. Bunun üzerine kodun Python gibi okunmasını sağlayan yüzey özelliklerini listeledi ve limiti iki katına çıkardı.

Tek geçişte çözümleme ve çalıştırma

Gerçek CPython uygulaması kaynağı simgeleştirir, soyut sözdizimi ağacını çözümler, analiz edip optimize eder, bytecode üretir ve sonra bu bytecode'u yorumlar. Henley'nin yorumlayıcısı bunların hiçbirini yapmaz. Tüm durum birkaç global değişkende yaşar: program metnini boşlukların çoğu çıkarılmış halde tutan 999 karakterlik bir tampon, sembol tablosu olarak hizmet eden 256 girişli bir tamsayı dizisi ve kaynak içinde bir imleç.

İfadeler çözümlenirken değerlendirilir; yani hiçbir noktada ara temsil yoktur. Henley'nin deyişiyle herhangi bir hata işleme de yok: çözümleyici anahtar kelimelerin doğru yazıldığını varsayar ve bilinen karakterleri konum aritmetiğiyle atlar; örneğin for anahtar kelimesinden sonra "in range(" karakterlerinin doğrudan üstünden atlar. Girinti ve dizge değişmezleri içindeki boşluklar korunurken, girdideki boşlukların çoğu çıkarılır. Değişken adları tek bir küçük harfle sınırlıdır; bu sayede karakterin değeri sembol tablosunu doğrudan indeksler.

Yeniden çözümleyerek akış kontrolü

Bloklar, girinti bloğun başladığı düzeyin altına düşene kadar çalışır ve iç içe geçme C çağrı yığını tarafından ele alınır. Döngüler derlemeye hiç başvurmaz: yorumlayıcı döngü koşulunun kaynakta nerede durduğunu kaydeder ve her yinelemede onu ve gövdeyi yeniden çözümlemek için geri atlar. Fonksiyonlar da aynı hileyi kullanır. Sembol tablosu bir fonksiyonun gövdesinin kaynak konumunu saklar; bir çağrı çağıranın konumunu kaydeder, gövdeye atlar, onu çalıştırır ve sona erdiğinde konumu geri yükler. print özel olarak ele alınır ve for döngüleri range ile sabit şekilde eşleşir. Henley sonucu, hiçbir şey derlenmediği düşünüldüğünde şaşırtıcı derecede az durum barındırıyor olarak tanımlıyor.

Baytları golfle eritmek

Okunabilir bir sürüm çalıştıktan sonra Henley, C'de golf üzerine uzun süredir devam eden bir Stack Overflow başlığındaki tekniklerle küçülttü; bu tekniklerin birkaçı GNU C89'a özgü davranışlara dayanıyor: örtük int bildirimleri, ücretsizce sıfırla başlatılan global değişkenler, karakter değişmezlileri yerine ASCII kodları, üçlü ve virgül operatörleri, mantıksal olanlar yerine bitwise işlemler. Henley bunu yasakladığı kütüphane hilelerinden ayırıyor ve yalnızca derleyicinin varsayılan libc bağlantısına yaslanıyor. Bir düzine okunabilir satıra yayılan bir çözümleyici fonksiyonu, ASCII aritmetiğiyle kurulmuş tek bir keskin ifadeye sıkışıyor. Son okunabilir sürüm 4.800 baytı aşıyor; golf edilmiş derleme tam olarak 1.024'e oturuyor.

Yol boyunca özellikler kesildi ve sıradaki karşılaştırma operatörleriydi; çünkü doğruluk değeri, sıfırla karşılaştırmak yerine if n % 15: testi yapmak, FizzBuzz'da aynı etkiyi sağlıyor. Henley, yalnızca FizzBuzz'a odaklanan bir sürümün 800 baytın altına inebileceğini tahmin ediyor.

Neden önemli

Proje, bir dilin Python gibi hissettirmesi için ne kadar az mekanizmaya ihtiyaç duyduğunun kompakt bir gösterimi. Simgeleştirme geçişlerini, AST'leri ve bytecode'u kaldırmak temel soruları görünür hale getiriyor: deyimler nasıl tanınıyor, iç içe geçme yapıya nasıl eşleniyor ve akış kontrolü metindeki konumlar olarak nasıl modellenebiliyor. Hata işlemenin tamamen yokluğu onu bir araçtan çok bir gösterim yapıyor; ama mesele tam olarak bu: üretim yorumlayıcısının bunun ötesinde eklediği neredeyse her şey güvenilirlik, optimizasyon ve tanılama için var, temel yürütme için değil. Eğitimciler ve dil uygulayıcıları için 1.024 baytlık yorumlayıcı, birçok öğretim yorumlayıcısının ardındaki çözümle-ve-çalıştır tasarımlarının okunabilir bir uç örneği ve katı bir bayt bütçesinin yalnızca kısıtlamakla kalmayıp netleştiren bir tasarım kısıtı olarak nasıl işleyebildiğinin taze bir örneği.