Alt programlar II: activation record, static ve dynamic chain

Geçen hafta alt programların ne yaptığını konuştuk; bu hafta derleyicinin bunu nasıl uyguladığını. Merkezde tek bir yapı var: activation record (ARI). Bir alt program her çağrıldığında run-time stack’e bir ARI konur, dönünce kaldırılır. Sınav soruları: ARI’nin içeriği, verilen çağrı dizisinde yığının resmi, static/dynamic link’lerin nereyi gösterdiği ve (chain_offset, local_offset) çiftleri.

Altın kurallar:

1. Dynamic link çağıranı, static link static parent’ı gösterir.
2. Static parent metinden okunur, çağrı sırasından değil.
3. chain_offset = referans yerinin derinliği − bildirim yerinin derinliği.
4. Her çağrı yeni ARI: özyinelemede aynı fonksiyonun birden çok ARI’si yığındadır.

Çağrı ve dönüş semantiği

Bir çağrıda yapılması gerekenler (call semantics):

1. Çağıranın çalışma durumunu kaydet.
2. Yerel değişkenler için yer ayır (stack-dynamic ise).
3. Parametreleri aktar (value ise kopyala, reference ise adres).
4. Return address’i kaydet.
5. Nonlocal erişim için gereken bağlantıyı kur (static link).
6. Kontrolü çağrılana ver.

Dönüşte (return semantics): out ve inout parametrelerin değerlerini geri kopyala, function ise dönüş değerini çağıranın erişebileceği yere koy, yığını eski haline getir, return address’e dön.

Activation record

Bir alt programın çalışırken ihtiyaç duyduğu yerel verinin biçimine activation record, bunun belirli bir çağrıya ait somut örneğine activation record instance (ARI) denir.

            ┌──────────────────┐  ← yığının tepesi
            │ yerel değişkenler │
            │ parametreler      │
            │ dynamic link      │  → çağıranın ARI'si
            │ static link       │  → static parent'ın ARI'si
            │ return address    │
            └──────────────────┘  ← ARI'nin tabanı

Basit durum: özyineleme yok, iç içelik yok

Erken Fortran’da tüm yereller static’ti. Her alt programın tek bir ARI’si vardı, derlemede sabit bir yere konurdu. Hızlı, ama özyineleme imkânsız: ikinci bir aktivasyon birincinin değişkenlerinin üstüne yazar.

Stack-dynamic yereller: run-time stack

C, Java gibi dillerde her çağrı yığına yeni bir ARI koyar. Environment pointer (EP) o an çalışan birimin ARI’sinin tabanını gösterir; yerellere EP + sabit ofset ile erişilir. Dynamic link, çağıranın ARI’sini gösterir; dönüşte EP bu değere geri alınır. Dynamic link’lerin oluşturduğu zincire dynamic chain (call chain) denir.

static int f(int n) {
    System.out.print("in" + n + " ");
    int r = (n <= 1) ? 1 : n * f(n - 1);
    System.out.print("out" + n + " ");
    return r;
}
// main: int v = f(3); System.out.println(); System.out.println(v);

in3 in2 in1 out1 out2 out3 
6

f(1) çalışırken yığın: main, f(3), f(2), f(1). Her ARI’nin kendi n’i ve r’si var. fact(4) main’den çağrılırsa yığında en fazla 5 ARI olur.

İç içe alt programlar: static chain

Ada, JavaScript, Python gibi dillerde bir fonksiyon başka bir fonksiyonun içinde tanımlanabilir. Static scope’ta nonlocal bir değişken, static ata’ların ARI’lerinden birindedir. Sorun: o ARI yığında nerede? Çözüm: her ARI’ye static parent’ın ARI’sini gösteren bir static link eklenir. Static link’lerin zincirine static chain denir.

• Static depth: birimin en dıştan kaç seviye içeride olduğu. Main 0.
• chain_offset (nesting depth): referansın yapıldığı birimin static depth’i − değişkenin bildirildiği birimin static depth’i.
• local_offset: değişkenin kendi ARI’si içindeki konumu.

Nonlocal erişim: chain_offset kadar static link izle, varılan ARI’de local_offset’e git. İki sayı da derleme zamanında bilinir.

Çözümlü örnek

Main     declares p, q, r          static depth 0
  Sub1   declares q, s             static depth 1   (Main'in içinde)
    Sub2 declares t, p             static depth 2   (Sub1'in içinde)
  Sub3   declares r, s             static depth 1   (Main'in içinde)

Çağrı dizisi: Main → Sub3 → Sub1 → Sub2
ARI düzeni: 0 return address, 1 static link, 2 dynamic link, yereller 3'ten itibaren

Sub2 çalışırken yığın (alttan üste):

#  ARI    static link →   dynamic link →
3  Sub2   Sub1             Sub1
2  Sub1   Main             Sub3      ← dikkat: static parent Main, çağıran Sub3
1  Sub3   Main             Main
0  Main   -                -

Sub2 içindeki referanslar:

Sub3 içinde q ise Main’de: (1, 4). Sub3’ün kendi r’si: (0, 3).

TUZAK · static link çağırana gitmez. Sub1’i Sub3 çağırdı ama Sub1’in static link’i Main’i gösterir. Static link metindeki iç içeliği izler. Sınavda en sık kaybedilen puan bu: yığında hemen alttaki ARI’ye ok çizmek.

Static link nasıl kurulur?

Çağrı anında, çağrılanın static parent’ının en son aktif ARI’si bulunmalı. Derleyici bunu da ofsetle yapar: çağıranın static depth’i ile çağrılanın static parent’ının depth’i arasındaki fark kadar static link izlenir. Sub3 (depth 1) Sub1’i (parent Main, depth 0) çağırıyor: Sub3’ten 1 link izle → Main.

Eleştiri: derin bir nonlocal’e erişim birçok link takibi gerektirir ve erişim süresi derinliğe göre değişir; zamana duyarlı kodda tahmin zorlaşır. Alternatif display yöntemi her derinlik için bir göstergeyi bir dizide tutar. Pratikte iç içelik nadiren 3’ü geçtiği için static chain yeterli.

Bloklar

{ int c, d; ... } gibi bloklar iki şekilde uygulanabilir:

1. Parametresiz, hep aynı yerden çağrılan alt programlar gibi: her girişte ARI.
2. Daha verimlisi: bloğun değişkenleri çevreleyen alt programın ARI’sine statik olarak yerleştirilir. Yan yana (sibling) bloklar aynı anda aktif olamaz, aynı hücreleri paylaşır.

void f() {
    int a, b;
    { int c, d; ... }
    { int e, f, g; ... }
}
gereken yerel hücre: 2 + max(2, 3) = 5

Dynamic scope’un uygulanması

Deep access: nonlocal bir isim, dynamic chain’de yukarıdan aşağı aranır. ARI’lerde değişken adları da tutulmalı (hangi değişkenin hangi ARI’de olduğu derlemede bilinmez). Zincir uzunluğu belirsiz, erişim yavaş.

Yukarıdaki program dynamic scope’lu olsaydı Sub2’deki r: Sub2’de yok, Sub1’de yok, Sub3’te var → Sub3.r. Static scope’ta Main.r. s ise iki kuralda da Sub1.s (Sub1 hem static parent hem çağıran).

Shallow access: her değişken adı için ayrı bir yığın (ya da merkezi tablo) tutulur; en üstteki aktif olan. Erişim hızlı, ama çağrı ve dönüşler pahalı (her yerel için push/pop).

Sık yapılan hatalar

Main     declares p, q, r
  Sub1   (nested in Main) declares q, s
    Sub2 (nested in Sub1) declares t, p
  Sub3   (nested in Main) declares r, s

static int f(int n) {
    System.out.print("in" + n + " ");
    int r = (n <= 1) ? 1 : n * f(n - 1);
    System.out.print("out" + n + " ");
    return r;
}
// main: System.out.println(f(3));