KAL
Menu

Interpreter VM

Siklus fetch-decode-execute pada stack VM beserta implementasi referensi.

Daftar isi

Topik ini mengimplementasikan interpreter untuk stack VM yang menjadi sasaran codegen. Pembaca memperoleh kelas StackVM dengan metode run(bytecode) yang menjalankan siklus fetch-decode-execute pada deret instruksi bytecode, mendukung akses lingkungan lewat STORE dan LOAD, lompatan lewat JUMP dan JUMP_IF_FALSE, serta keluaran lewat PRINT. Setelah membaca topik ini, pembaca dapat menjelaskan tiga tahap siklus interpreter, menjelaskan pemetaan nama label ke indeks instruksi pada pass awal, dan menjalankan bytecode yang dihasilkan codegen untuk program dengan If dan While sederhana.

Siklus fetch-decode-execute#

Siklus interpreter stack VM terdiri atas tiga tahap yang berulang hingga program counter pc mencapai akhir bytecode. Tahap pertama, fetch, mengambil instruksi pada indeks pc saat ini dari daftar bytecode. Tahap kedua, decode, memisahkan instruksi menjadi opcode dan operand. Tahap ketiga, execute, melakukan aksi yang ditetapkan opcode, lalu memperbarui stack, env, atau pc sesuai kebutuhan. Untuk sebagian besar instruksi, pc dinaikkan sebesar satu, sehingga eksekusi bersifat sekuensial. Untuk instruksi JUMP dan JUMP_IF_FALSE, pc diperbarui ke indeks instruksi sasaran, sehingga eksekusi bersifat non-sekuensial.

Tiga tahap ini dapat dilihat secara langsung pada struktur metode run. Loop utama while self.pc < len(bytecode) adalah loop fetch. Penguraian instr = bytecode[self.pc] dan op = instr[0] adalah decode. Rantai if dan elif yang menyusuri op adalah execute, dengan setiap cabang memperbarui state mesin. Pemisahan tahap tidak menghasilkan kode yang lebih panjang, sebab pemetaan opcode ke aksi memang sudah bersifat satu-satu. Yang menjadikan tiga tahap ini layak disebut adalah cara pc diperbarui: konstan sebesar satu untuk instruksi sekuensial, dan melompat ke indeks lain untuk instruksi lompatan.

Stack dan env adalah dua wadah state interpreter. Stack menyimpan operand sementara untuk aritmetika, komparasi, dan operasi lain yang memerlukan operand implisit. Env menyimpan nilai variabel yang dipetakan dari nama ke nilai. Instruksi STORE name memindahkan nilai dari puncak stack ke env[name], sedangkan LOAD name mengambil nilai dari env[name] dan mendorongnya ke puncak stack. Pemisahan dua wadah ini menyederhanakan codegen: ekspresi sementara menggunakan stack, sedangkan variabel bernama menggunakan env.

Resolusi label pada pass awal#

Bytecode yang dihasilkan codegen memakai nama label sebagai operand lompatan, misalnya JUMP_IF_FALSE L_else_1. Interpreter perlu mengganti nama label dengan indeks instruksi saat eksekusi. Pemetaan ini dibangun satu kali pada awal run lewat metode _build_label_map, yang memindai seluruh bytecode dan mencatat indeks setiap pseudo-instruksi LABEL. Pemetaan label ke indeks disimpan sebagai dict[str, int], sehingga pencarian saat eksekusi berjalan dalam waktu konstan.

Pendekatan dua pass ini dipilih agar codegen tidak perlu menghitung indeks lompatan secara manual. Bila codegen harus menghasilkan indeks numerik, setiap perubahan pada instruksi sebelum lompatan memaksa perhitungan ulang seluruh indeks. Dengan label string, codegen cukup meminta nama label baru, lalu meneruskannya sebagai operand. Pseudo-instruksi LABEL sendiri adalah no-op pada tahap execute: cabang if op == "LABEL" di dalam loop hanya menaikkan pc sebesar satu, tanpa menyentuh stack atau env.

Konsekuensi pemakaian label adalah interpreter perlu memvalidasi setiap nama label yang dirujuk. Bila sebuah JUMP menyebut nama yang tidak pernah dideklarasikan oleh LABEL mana pun, akses labels[instr[1]] akan menimbulkan KeyError. Pada implementasi referensi di topik ini, validasi tersebut mengikuti perilaku bawaan Python, yaitu KeyError yang melaporkan kunci yang hilang. Pada compiler produksi, pesan error yang jelas pada tahap pemeriksaan statis setelah codegen lebih diutamakan daripada error dinamis saat runtime.

Implementasi VM#

Berkas vm.py berisi kelas StackVM dengan metode run dan utilitas format bytecode. Konstruktor menerima env opsional sehingga VM dapat dijalankan dengan lingkungan awal. Metode run mengembalikan daftar nilai yang dicetak oleh PRINT, sehingga keluaran program dapat diperiksa secara terprogram tanpa harus menangkap stdout.

python vm.py 
"""Interpreter stack VM dengan siklus fetch-decode-execute.

Antarmuka publik:

    StackVM(env=None).run(bytecode) -> list[str]

Bytecode adalah list[tuple[str, ...]] sesuai kontrak vm_spec.py.
Pseudo-instruksi LABEL ditandai pada satu pass awal
untuk membangun pemetaan nama label ke indeks instruksi, lalu
diabaikan saat eksekusi. Lompatan menyebut nama label sebagai
operand, dan interpreter mengganti nama dengan indeks pada saat
eksekusi.

Siklus fetch-decode-execute:
  1. fetch: ambil instruksi pada pc saat ini
  2. decode: pisahkan opcode dan operand
  3. execute: lakukan aksi opcode, perbarui stack/env/pc

Pemisahan tiga tahap ini menjadi jelas pada cabang `JUMP` dan
`JUMP_IF_FALSE` yang memperbarui pc secara non-sekuensial, sedangkan
instruksi lain menaikkan pc sebesar satu.
"""

from typing import Any


class StackVM:
    """Mesin sasaran berbasis stack dengan siklus fetch-decode-execute."""

    def __init__(self, env: dict[str, Any] | None = None) -> None:
        self.env: dict[str, Any] = dict(env or {})
        self.stack: list[Any] = []
        self.pc: int = 0

    def _build_label_map(self, instrs: list[tuple]) -> dict[str, int]:
        labels: dict[str, int] = {}
        for i, instr in enumerate(instrs):
            if instr[0] == "LABEL":
                labels[instr[1]] = i
        return labels

    def run(self, bytecode: list[tuple]) -> list[str]:
        """Jalankan bytecode; kembalikan daftar nilai yang dicetak PRINT."""
        labels = self._build_label_map(bytecode)
        self.stack = []
        self.pc = 0
        printed: list[str] = []
        while self.pc < len(bytecode):
            instr = bytecode[self.pc]
            op = instr[0]
            # ----- fetch-decode-execute -----
            if op == "LABEL":
                # pseudo-instruksi: penanda posisi lompatan, no-op
                self.pc += 1
            elif op == "PUSH":
                self.stack.append(instr[1])
                self.pc += 1
            elif op == "POP":
                self.stack.pop()
                self.pc += 1
            elif op in ("ADD", "SUB", "MUL", "DIV"):
                b = self.stack.pop()
                a = self.stack.pop()
                if op == "ADD":
                    self.stack.append(a + b)
                elif op == "SUB":
                    self.stack.append(a - b)
                elif op == "MUL":
                    self.stack.append(a * b)
                else:  # DIV
                    if isinstance(a, int) and isinstance(b, int) and a % b == 0:
                        self.stack.append(a // b)
                    else:
                        self.stack.append(a / b)
                self.pc += 1
            elif op in ("EQ", "LT", "GT"):
                b = self.stack.pop()
                a = self.stack.pop()
                if op == "EQ":
                    self.stack.append(a == b)
                elif op == "LT":
                    self.stack.append(a < b)
                else:
                    self.stack.append(a > b)
                self.pc += 1
            elif op == "NOT":
                a = self.stack.pop()
                self.stack.append(not a)
                self.pc += 1
            elif op == "JUMP":
                # lompat tak bersyarat ke label
                self.pc = labels[instr[1]]
            elif op == "JUMP_IF_FALSE":
                v = self.stack.pop()
                if not v:
                    self.pc = labels[instr[1]]
                else:
                    self.pc += 1
            elif op == "STORE":
                self.env[instr[1]] = self.stack.pop()
                self.pc += 1
            elif op == "LOAD":
                self.stack.append(self.env[instr[1]])
                self.pc += 1
            elif op == "PRINT":
                printed.append(str(self.stack.pop()))
                self.pc += 1
            else:
                raise ValueError(f"opcode tak dikenal: {op}")
        return printed


def format_bytecode(instrs: list[tuple]) -> str:
    def fmt(a: Any) -> str:
        if a is None:
            return "nil"
        if isinstance(a, bool):
            return "true" if a else "false"
        if isinstance(a, str):
            return a
        return repr(a)

    lines: list[str] = []
    for instr in instrs:
        op = instr[0]
        args = instr[1:]
        if not args:
            lines.append(op)
        else:
            lines.append(op + " " + " ".join(fmt(a) for a in args))
    return "\n".join(lines)


def main() -> None:
    # Demo 1: bytecode dari codegen topik sebelumnya untuk
    #   let x = 1 + 2;
    #   print x;
    demo1 = [
        ("PUSH", 1), ("PUSH", 2), ("ADD",),
        ("STORE", "x"), ("LOAD", "x"), ("PRINT",),
    ]
    print("=== Demo 1: let x = 1 + 2; print x; ===")
    vm1 = StackVM()
    out1 = vm1.run(demo1)
    print("bytecode:")
    print(format_bytecode(demo1))
    print(f"env  : {vm1.env}")
    print(f"PRINT: {out1}")
    print()

    # Demo 2: percabangan If sederhana.
    #   let n = 5;
    #   if (n > 3) { print 100 } else { print 200 }
    demo2 = [
        ("PUSH", 5), ("STORE", "n"),
        ("LOAD", "n"), ("PUSH", 3), ("GT",),
        ("JUMP_IF_FALSE", "L_else"),
        ("PUSH", 100), ("JUMP", "L_end"),
        ("LABEL", "L_else"), ("PUSH", 200),
        ("LABEL", "L_end"), ("PRINT",),
    ]
    print("=== Demo 2: let n = 5; if (n > 3) print 100; else print 200; ===")
    vm2 = StackVM()
    out2 = vm2.run(demo2)
    print("bytecode:")
    print(format_bytecode(demo2))
    print(f"env  : {vm2.env}")
    print(f"PRINT: {out2}")
    print()

    # Demo 3: perulangan While sederhana.
    #   let n = 3; let s = 0;
    #   while (n > 0) { s = s + n; n = n - 1 }
    #   print s;
    demo3 = [
        ("PUSH", 3), ("STORE", "n"),
        ("PUSH", 0), ("STORE", "s"),
        ("LABEL", "L_top"),
        ("LOAD", "n"), ("PUSH", 0), ("GT",),
        ("JUMP_IF_FALSE", "L_end"),
        ("LOAD", "s"), ("LOAD", "n"), ("ADD",), ("STORE", "s"),
        ("LOAD", "n"), ("PUSH", 1), ("SUB",), ("STORE", "n"),
        ("JUMP", "L_top"),
        ("LABEL", "L_end"),
        ("LOAD", "s"), ("PRINT",),
    ]
    print("=== Demo 3: hitung 3 + 2 + 1 dengan while ===")
    vm3 = StackVM()
    out3 = vm3.run(demo3)
    print("bytecode:")
    print(format_bytecode(demo3))
    print(f"env  : {vm3.env}")
    print(f"PRINT: {out3}")


if __name__ == "__main__":
    main()

Program utama menjalankan tiga demo. Demo pertama memakai bytecode persis seperti yang dihasilkan codegen untuk let x = 1 + 2; print x;, sehingga kesinambungan antara codegen dan interpreter terlihat secara langsung. Demo kedua menjalankan percabangan If dengan cabang else, sedangkan demo ketiga menjalankan perulangan While yang menghitung penjumlahan 3 + 2 + 1. Keluaran berikut diperoleh dengan menjalankan python3 vm.py.

text Keluaran 
=== Demo 1: let x = 1 + 2; print x; ===
bytecode:
PUSH 1
PUSH 2
ADD
STORE x
LOAD x
PRINT
env  : {'x': 3}
PRINT: ['3']

=== Demo 2: let n = 5; if (n > 3) print 100; else print 200; ===
bytecode:
PUSH 5
STORE n
LOAD n
PUSH 3
GT
JUMP_IF_FALSE L_else
PUSH 100
JUMP L_end
LABEL L_else
PUSH 200
LABEL L_end
PRINT
env  : {'n': 5}
PRINT: ['100']

=== Demo 3: hitung 3 + 2 + 1 dengan while ===
bytecode:
PUSH 3
STORE n
PUSH 0
STORE s
LABEL L_top
LOAD n
PUSH 0
GT
JUMP_IF_FALSE L_end
LOAD s
LOAD n
ADD
STORE s
LOAD n
PUSH 1
SUB
STORE n
JUMP L_top
LABEL L_end
LOAD s
PRINT
env  : {'n': 0, 's': 6}
PRINT: ['6']

Keluaran ketiga demo memperlihatkan tiga sifat VM. Demo pertama menunjukkan ekspresi aritmetika sederhana: 1 + 2 dihitung menjadi 3, disimpan ke x, lalu dimuat dan dicetak. Demo kedua menunjukkan percabangan: n > 3 menghasilkan True pada puncak stack, sehingga JUMP_IF_FALSE L_else tidak mengambil lompatan, dan cabang then PUSH 100 dijalankan hingga PRINT mencetak 100. Demo ketiga menunjukkan perulangan: perulangan while mengakumulasi s hingga n mencapai nol, lalu PRINT mencetak 6, yaitu hasil 3 + 2 + 1. State akhir env pada demo ketiga menunjukkan n = 0 dan s = 6, sesuai dengan semantik while.

Ringkasan#

  • Siklus interpreter stack VM terdiri atas tiga tahap, yaitu fetch instruksi pada pc, decode opcode dan operand, lalu execute aksi yang memperbarui stack, env, atau pc.
  • Pemetaan nama label ke indeks instruksi dibangun pada satu pass awal, sehingga JUMP dan JUMP_IF_FALSE dapat melompat ke indeks tanpa mengulang pemindaian bytecode.
  • Pseudo-instruksi LABEL adalah no-op pada tahap execute. Tugasnya hanya menandai posisi lompatan untuk pass awal.
  • Tiga demo, yaitu ekspresi aritmetika, percabangan If, dan perulangan While, menunjukkan bahwa VM mampu menjalankan bytecode yang dihasilkan codegen untuk seluruh konstruk bahasa mini v1.

Referensi#