KAL
Menu

Struktur Data Runtime

Menambahkan array dan map ke bahasa mini beserta semantik operasinya.

Daftar isi

Topik ini memperkenalkan representasi array dan map pada runtime bahasa mini, lengkap dengan semantik mutasi dan lookup kunci. Pembaca memperoleh kelas ArrayObject dengan backing list yang mendukung get, set, length, dan push, kelas MapObject dengan backing dict yang mendukung get, set, keys, values, items, dan has, serta demo yang membangun array [10, 20, 30] dan map {a: 1, b: 2}, melakukan mutasi, lalu mencetak. Implementasi pada topik ini berdiri sendiri dan tidak terintegrasi dengan StackVM pada modul 5, sebab bahasa mini v1 belum memuat array maupun map. Tujuannya adalah menunjukkan struktur objek yang dibutuhkan ketika tipe data komposit ditambahkan ke runtime. Setelah membaca topik ini, pembaca dapat menjelaskan backing list untuk array, menjelaskan backing dict untuk map, dan menjelaskan perbedaan mutasi pada objek komposit dibanding penugasan variabel biasa.

Array dengan backing list#

ArrayObject menyimpan elemen pada list Python, dengan indeks berbasis nol yang menyatakan posisi dalam list. Penggunaan list sebagai backing menyederhanakan implementasi: length cukup mengembalikan len, get cukup mengakses items[index], dan set cukup menugaskan ulang items[index]. Operasi push menggunakan list.append untuk menambah elemen di akhir. Semua operasi ini berjalan dalam waktu rata-rata konstan, sebab list Python sudah mendukung perilaku itu secara internal. Bila sebuah bahasa ingin mendukung prepend yang efisien, backing list Python tidak cukup, sehingga implementasi runtime perlu beralih ke struktur seperti deque atau linked list.

Pemeriksaan batas indeks dilakukan secara eksplisit pada get dan set. Bila indeks berada di luar rentang [0, length), kedua metode memunculkan IndexError. Pemeriksaan ini penting karena akses tanpa batas pada list Python dapat berperilaku berbeda, misalnya indeks negatif yang berarti dihitung dari akhir. Pada bahasa mini, indeks negatif biasanya diperlakukan sebagai error agar semantik lebih jelas, dan implementasi referensi menegakkan aturan itu dengan membandingkan indeks terhadap nol dan panjang. Aturan ini juga mencegah kebisingan semantik seperti arr[-1] yang diam-diam mengakses elemen terakhir padahal pembaca mungkin bermaksud menulis indeks biasa.

Mutasi pada ArrayObject bersifat in-place, yaitu mengubah isi list yang sama, bukan membuat list baru. Akibatnya, bila dua variabel menunjuk ke objek array yang sama, mutasi melalui salah satu variabel terlihat dari variabel lain. Perilaku ini disebut reference semantics, dan berbeda dari penugasan variabel biasa pada bahasa mini yang melakukan penyalinan nilai. Pemisahan ini lazim pada bahasa dengan tipe komposit: variabel primitif seperti integer dan boolean disalin, sedangkan objek komposit seperti array dan map dibagi. Pada topik ini, perbedaan tersebut tidak tampak secara langsung karena demo hanya menggunakan satu variabel per objek, tetapi perlu disadari saat array dan map benar-benar digunakan dalam program yang lebih besar.

Map dengan backing dict#

MapObject menyimpan pasangan kunci-nilai pada dict Python. Penggunaan dict sebagai backing memberikan tiga jaminan yang penting untuk semantik map. Pertama, pencarian kunci berjalan dalam rata-rata waktu konstan, sehingga get dan set tetap efisien walaupun jumlah pasangan besar. Kedua, kunci bersifat unik, sehingga set pada kunci yang sudah ada selalu menimpa nilai lama, bukan menambah pasangan baru. Ketiga, iterasi melalui keys, values, dan items mencerminkan urutan penyisipan pada Python 3.7 dan yang lebih baru, sehingga keluaran iterasi bersifat terprediksi.

Operasi get pada MapObject mengembalikan None bila kunci tidak ada, alih-alih memunculkan error. Pilihan ini sesuai untuk map yang sering digunakan sebagai wadah opsional, sehingga pemanggil dapat memeriksa nilai None dan menggantinya dengan nilai bawaan. Bila pemanggil ingin membedakan kunci yang ada dengan nilai None dari kunci yang tidak ada, metode has dapat digunakan sebelum get. Pemisahan has dan get mengikuti pola yang lazim pada pustaka standar banyak bahasa, sehingga pembaca dapat memetakan langsung antar bahasa.

Operasi set selalu menimpa. Bila kunci sudah ada, pasangan lama diganti dengan pasangan baru. Bila kunci belum ada, pasangan baru ditambahkan. Aturan ini berbeda dari beberapa bahasa yang membedakan operasi insert dan update, tetapi cukup untuk bahasa mini. Iterasi keys, values, dan items mengembalikan salinan list sehingga mutasi pada map setelah iterasi tidak mengganggu iterator. Pemilihan salinan alih-alih tampilan langsung mengorbankan sedikit memori untuk keamanan, dan menjadi pilihan yang masuk akal pada ukuran map yang biasa digunakan.

Implementasi referensi#

Berkas data_struct.py berisi kelas ArrayObject dan MapObject plus demo. Demo pertama membangun array [10, 20, 30], membaca elemen indeks satu, mengubahnya menjadi 200, lalu menambah 40 dengan push. Demo kedua membangun map {a: 1, b: 2}, mencetak seluruh pasangan, lalu menambah kunci baru c dan menimpa kunci a dengan 100. Demo ketiga mengiterasi array dan map untuk menghitung penjumlahan elemen.

python data_struct.py 
"""Struktur data runtime: ArrayObject dan MapObject.

Topik ini memperkenalkan representasi array dan map pada runtime
bahasa mini. Implementasi ini berdiri sendiri dan tidak terintegrasi
dengan VM modul 5.

Antarmuka:

    ArrayObject(items)         dengan get/set/length/push/append
    MapObject(pairs)           dengan get/set/keys/values/items/has
"""

from typing import Any


class ArrayObject:
    """Array dengan backing list Python.

    Indeks berbasis nol. get dan set memeriksa batas sehingga
    akses di luar rentang memunculkan IndexError. Operasi push
    menambahkan elemen di akhir.
    """

    def __init__(self, items: list[Any] | None = None) -> None:
        self.items: list[Any] = list(items or [])

    def length(self) -> int:
        return len(self.items)

    def get(self, index: int) -> Any:
        if index < 0 or index >= len(self.items):
            raise IndexError(f"indeks {index} di luar batas [0, {len(self.items)})")
        return self.items[index]

    def set(self, index: int, value: Any) -> None:
        if index < 0 or index >= len(self.items):
            raise IndexError(f"indeks {index} di luar batas [0, {len(self.items)})")
        self.items[index] = value

    def push(self, value: Any) -> int:
        self.items.append(value)
        return len(self.items)

    def __repr__(self) -> str:
        return f"ArrayObject({self.items!r})"


class MapObject:
    """Map dengan backing dict Python.

    Kunci dapat berupa nilai hashable apa pun. get mengembalikan
    None bila kunci tidak ada, sedangkan set selalu menimpa nilai lama.
    Operasi keys, values, dan items mengembalikan tampilan yang
    merefleksikan state internal dict.
    """

    def __init__(self, pairs: dict[Any, Any] | None = None) -> None:
        self.pairs: dict[Any, Any] = dict(pairs or {})

    def has(self, key: Any) -> bool:
        return key in self.pairs

    def get(self, key: Any) -> Any:
        return self.pairs.get(key)

    def set(self, key: Any, value: Any) -> None:
        self.pairs[key] = value

    def keys(self) -> list[Any]:
        return list(self.pairs.keys())

    def values(self) -> list[Any]:
        return list(self.pairs.values())

    def items(self) -> list[tuple[Any, Any]]:
        return list(self.pairs.items())

    def __repr__(self) -> str:
        return f"MapObject({self.pairs!r})"


def main() -> None:
    print("=== Array [10, 20, 30] ===")
    arr = ArrayObject([10, 20, 30])
    print(f"awal    : {arr}")
    print(f"length  : {arr.length()}")
    print(f"arr[1]  : {arr.get(1)}")
    arr.set(1, 200)
    print(f"set(1, 200): {arr}")
    arr.push(40)
    print(f"push(40): {arr}")
    print()

    print("=== Map {a: 1, b: 2} ===")
    mp = MapObject({"a": 1, "b": 2})
    print(f"awal        : {mp}")
    print(f"keys()      : {mp.keys()}")
    print(f"values()    : {mp.values()}")
    print(f"items()     : {mp.items()}")
    print(f"get('a')    : {mp.get('a')}")
    print(f"get('z')    : {mp.get('z')}")
    print(f"has('b')    : {mp.has('b')}")
    mp.set("c", 3)
    print(f"set('c', 3) : {mp}")
    mp.set("a", 100)
    print(f"set('a', 100): {mp}")
    print()

    print("=== Mutasi dan iterasi ===")
    print(f"array saat ini: {arr.items}")
    total = 0
    for i in range(arr.length()):
        total += arr.get(i)
    print(f"jumlah elemen array: {total}")
    print(f"map saat ini : {mp.pairs}")
    total_map = 0
    for _, v in mp.items():
        total_map += v
    print(f"jumlah nilai map: {total_map}")


if __name__ == "__main__":
    main()

Demo array menunjukkan tiga sifat. Indeks 1 mengembalikan 20, yang sesuai dengan posisi elemen kedua pada [10, 20, 30]. Setelah set(1, 200), array berubah menjadi [10, 200, 30], dan setelah push(40), panjangnya bertambah menjadi empat. Demo map menunjukkan bahwa keys, values, dan items mengembalikan struktur yang konsisten dengan urutan penyisipan. Setelah set("c", 3) dan set("a", 100), nilai pada kunci a ditimpa, sedangkan kunci c ditambahkan di akhir. Keluaran berikut diperoleh dengan menjalankan python3 data_struct.py.

text Keluaran 
=== Array [10, 20, 30] ===
awal    : ArrayObject([10, 20, 30])
length  : 3
arr[1]  : 20
set(1, 200): ArrayObject([10, 200, 30])
push(40): ArrayObject([10, 200, 30, 40])

=== Map {a: 1, b: 2} ===
awal        : MapObject({'a': 1, 'b': 2})
keys()      : ['a', 'b']
values()    : [1, 2]
items()     : [('a', 1), ('b', 2)]
get('a')    : 1
get('z')    : None
has('b')    : True
set('c', 3) : MapObject({'a': 1, 'b': 2, 'c': 3})
set('a', 100): MapObject({'a': 100, 'b': 2, 'c': 3})

=== Mutasi dan iterasi ===
array saat ini: [10, 200, 30, 40]
jumlah elemen array: 280
map saat ini : {'a': 100, 'b': 2, 'c': 3}
jumlah nilai map: 105

Iterasi pada bagian akhir memperlihatkan bagaimana ArrayObject dan MapObject digunakan pada pola yang biasa dijumpai pada program nyata. Penjumlahan seluruh elemen array menghasilkan 280, yaitu 10 + 200 + 30 + 40, sedangkan penjumlahan seluruh nilai map menghasilkan 105, yaitu 100 + 2 + 3. Hasil ini sekaligus memverifikasi bahwa mutasi set dan push terjadi pada objek yang sama, bukan pada salinan.

Kesalahan umum#

Kesalahan paling sering adalah memperlakukan objek komposit seolah-olah disalin saat ditugaskan. Bila pemanggil membuat let b = a dengan a berupa array, lalu memutakhirkan b, isi a juga berubah, sebab keduanya menunjuk ke backing list yang sama. Penyebabnya adalah asumsi bahwa penugasan selalu menyalin nilai, padahal pada objek komposit penugasan hanya menyalin rujukan. Perbaikannya adalah membuat salinan eksplisit bila memang diperlukan, misalnya dengan menyediakan metode copy pada ArrayObject dan MapObject.

Kesalahan kedua adalah lupa memeriksa keberadaan kunci pada map. Bila sebuah pasangan dibaca dengan get dan kuncinya tidak ada, nilai yang dikembalikan adalah None, yang mungkin tidak dapat dibedakan dari nilai None yang sengaja disimpan. Penyebabnya adalah penggunaan get tanpa has pada situasi yang membutuhkan pembedaan. Perbaikannya adalah memanggil has terlebih dahulu, atau menyediakan get_or(key, default) yang menggunakan nilai bawaan eksplisit.

Ringkasan#

  • ArrayObject menggunakan list Python sebagai backing, dengan indeks berbasis nol dan pemeriksaan batas pada get dan set.
  • MapObject menggunakan dict Python sebagai backing, dengan kunci unik, set yang menimpa, dan iterasi yang mencerminkan urutan penyisipan.
  • Mutasi pada array dan map bersifat in-place, sehingga dua variabel yang menunjuk ke objek yang sama akan melihat mutasi dari satu sama lain.
  • Iterasi pada demo memperlihatkan pola penggunaan yang lazim, yaitu menjumlahkan seluruh elemen array dan seluruh nilai map setelah mutasi.

Referensi#