Membangkitkan Bytecode

Menerjemahkan pernyataan dan ekspresi AST menjadi deret instruksi bytecode.

Daftar isi

Topik ini membahas pembangkitan bytecode dari AST ke mesin sasaran stack VM yang ditetapkan pada spesifikasi set instruksi. Pembaca memperoleh kelas CodeGenerator dengan satu metode visit_* untuk tiap node AST, sehingga seluruh konstruk bahasa mini v1 dapat diturunkan menjadi deret instruksi bytecode. Setelah membaca topik ini, pembaca dapat menjelaskan strategi post-order untuk ekspresi, menjelaskan pemakaian label untuk kontrol alur pada If dan While, serta membaca bytecode yang dihasilkan oleh codegen dan memverifikasinya secara manual terhadap semantik sumber.

Strategi post-order untuk ekspresi#

Codegen ekspresi dilakukan dengan menelusuri pohon ekspresi secara post-order: anak kiri dikunjungi lebih dahulu, anak kanan dikunjungi berikutnya, lalu opcode operator dikeluarkan. Untuk 1 + 2, codegen membangkitkan PUSH 1, PUSH 2, lalu ADD. Instruksi ADD mengambil dua puncak tumpukan, yaitu 2 di puncak dan 1 di bawahnya, sesuai konvensi a di bawah b yang ditetapkan pada vm_spec.py. Urutan post-order menjamin urutan operand yang benar untuk operasi nonkomutatif seperti SUB, DIV, LT, dan GT.

Urutan ini menjadi krusial pada ekspresi berlapis. Untuk a - b, codegen membangkitkan LOAD a, LOAD b, SUB. Bila urutan terbalik menjadi LOAD b, LOAD a, SUB, hasilnya menjadi b - a tanpa pesan error dari VM, sebab VM hanya mengikuti urutan pop yang ditetapkan. Tanggung jawab menjaga urutan ini berada di codegen, bukan di VM. Pemisahan tanggung jawab inilah yang membuat VM tetap sederhana, yaitu sekadar pelaksana instruksi sesuai kontrak.

Node Grouping ditembus langsung ke ekspresi dalamnya. Tanda kurung pada sumber hanya menentukan urutan evaluasi yang sudah dipastikan oleh struktur pohon, sehingga pada tahap codegen struktur pohon sudah mengodekan urutan tersebut. Bila codegen mencoba memetakan Grouping ke instruksi terpisah, bytecode menjadi lebih panjang tanpa manfaat semantik. Demikian pula Literal dipetakan ke satu instruksi PUSH, dan Variable ke satu instruksi LOAD.

Pemetaan operator biner dan uner#

Pemetaan operator biner ke opcode bersifat langsung untuk operator yang tersedia pada set instruksi: + menjadi ADD, - menjadi SUB, * menjadi MUL, / menjadi DIV, == menjadi EQ, < menjadi LT, dan > menjadi GT. Operator yang tidak memiliki opcode tunggal diturunkan menjadi dua instruksi. Operator != menjadi EQ diikuti NOT, sebab a != b setara dengan !(a == b). Operator <= menjadi GT diikuti NOT, sebab a <= b setara dengan !(a > b). Operator >= menjadi LT diikuti NOT dengan alasan yang sama. Pemetaan dua instruksi ini menghasilkan bytecode yang sedikit lebih panjang, tetapi menghindari penambahan opcode baru pada kontrak set instruksi.

Operator uner - tidak memiliki opcode negasi langsung. Codegen menyusun ulang negasi menjadi 0 - operand dengan urutan instruksi PUSH 0, evaluasi operand, lalu SUB. Pada titik SUB dieksekusi, stack berisi [0, operand], sehingga SUB menghitung 0 - operand yang merupakan nilai negatifnya. Operator uner ! dipetakan ke NOT tanpa susunan ulang, sebab NOT sudah ada pada set instruksi dan mengambil satu puncak tumpukan.

Kontrol alur dengan label#

Pernyataan If dan While memerlukan lompatan, yang pada kontrak stack VM disandikan sebagai JUMP lbl dan JUMP_IF_FALSE lbl. Codegen memakai nama label string sebagai sasaran lompatan, dengan pseudo-instruksi LABEL name menandai posisi lompatan. Pendekatan label string dipilih agar bytecode tetap dapat dibaca manusia dan terhindar dari backpatching dua pass. Setiap kali codegen memerlukan label baru, sebuah penghitung internal dinaikkan, sehingga nama yang dihasilkan unik di seluruh program.

Untuk If tanpa else, codegen membangkitkan label L_else_N dan L_end_N. Kondisi dievaluasi lebih dahulu, lalu JUMP_IF_FALSE L_else_N melompat ke akhir apabila kondisi falsy. Cabang then dijalankan bila kondisi truthy, lalu JUMP L_end_N melompat ke akhir. Bila cabang else ada, codegen menempatkan cabang tersebut di antara LABEL L_else_N dan LABEL L_end_N. Untuk While, codegen membangkitkan LABEL L_top_N di awal, lalu mengevaluasi kondisi, JUMP_IF_FALSE L_end_N, badan perulangan, dan JUMP L_top_N untuk kembali ke atas. Struktur ini menghasilkan satu pemeriksaan kondisi per iterasi, yang sesuai dengan semantik while.

Logika pendek and dan or juga memakai label. Untuk a and b, codegen membangkitkan evaluasi a, JUMP_IF_FALSE L_false_N yang langsung melompat ke label false apabila a falsy, lalu evaluasi b dengan JUMP_IF_FALSE L_false_N kedua. Bila keduanya truthy, PUSH true dikeluarkan. Bila salah satu falsy, PUSH false dikeluarkan. Logika or menggunakan dua jalur serupa dengan label L_eval_b_N dan L_false_N. Implementasi ini menghasilkan bool, sehingga nilai a dan b asli tidak dipertahankan. Untuk demo pada topik ini, logika pendek tidak dipakai, tetapi pemetaannya tetap disertakan agar codegen lengkap untuk seluruh node AST.

Codegen untuk program kecil#

Berkas codegen.py berisi kelas CodeGenerator dengan metode visit_* untuk setiap node AST. Kelas mempertahankan daftar instruksi self.instrs dan penghitung label self._n. Metode generate(program) adalah titik masuk yang menelusuri setiap pernyataan program. Pemetaan operator biner, uner, logika pendek, dan kontrol alur terkonsolidasi pada satu kelas agar perubahan pada kontrak set instruksi hanya memengaruhi satu berkas.

python codegen.py

"""Pembangkit bytecode stack VM dari AST bahasa mini v1.

Antarmuka publik:

    CodeGenerator().generate(program) -> list[tuple[str, ...]]

Keluaran adalah deret instruksi bytecode sesuai kontrak vm_spec.py.
Setiap instruksi disimpan sebagai tuple dengan
elemen pertama berupa nama opcode dan sisanya operand.

Strategi codegen adalah post-order traversal AST. Untuk ekspresi,
anak kiri dikunjungi lebih dahulu sehingga nilainya berada di bawah
anak kanan di puncak stack, lalu opcode operator dikeluarkan. Untuk
pernyataan kontrol alur (If, While) dan logika pendek (Logical),
codegen memakai label bernama sebagai sasaran lompatan, dengan
pseudo-instruksi LABEL menandai posisi lompatan. Pendekatan label
string menghindari backpatching dua pass: codegen cukup meminta nama
label baru saat dibutuhkan, lalu meneruskannya ke JUMP/JUMP_IF_FALSE
sebagai operand.

Catatan: Assign pada implementasi ini hanya menyimpan nilai ke env
tanpa meninggalkan salinan di stack. Implementasi cukup untuk
ExprStmt yang membuang hasil, namun tidak mendukung penetapan
berantai seperti `let y = (x = 5)`. Logical dievaluasi dengan
short-circuit dan menghasilkan bool.
"""
from dataclasses import dataclass, field
from typing import Any


# ----- AST (kanonis dari topik desain-ast, salinan ringkas) -----
@dataclass
class Expr:
    """Akar hierarki ekspresi."""


@dataclass
class Binary(Expr):
    left: Expr
    op: str
    right: Expr


@dataclass
class Unary(Expr):
    op: str
    operand: Expr


@dataclass
class Literal(Expr):
    value: Any


@dataclass
class Variable(Expr):
    name: str


@dataclass
class Assign(Expr):
    name: str
    value: Expr


@dataclass
class Logical(Expr):
    left: Expr
    op: str  # "and" atau "or"
    right: Expr


@dataclass
class Grouping(Expr):
    expression: Expr


@dataclass
class Stmt:
    """Akar hierarki pernyataan."""


@dataclass
class Let(Stmt):
    name: str
    initializer: Expr


@dataclass
class Print(Stmt):
    expression: Expr


@dataclass
class If(Stmt):
    condition: Expr
    then_branch: Stmt
    else_branch: Stmt | None = None


@dataclass
class While(Stmt):
    condition: Expr
    body: Stmt


@dataclass
class Block(Stmt):
    statements: list[Stmt] = field(default_factory=list)


@dataclass
class Expression(Stmt):
    expression: Expr


@dataclass
class Program:
    statements: list[Stmt] = field(default_factory=list)


# ----- CodeGenerator -----
class CodeGenerator:
    """Pembangkit bytecode stack VM dari AST."""

    def __init__(self) -> None:
        self.instrs: list[tuple] = []
        self._n = 0

    def _new_label(self, prefix: str) -> str:
        self._n += 1
        return f"{prefix}_{self._n}"

    def _emit(self, op: str, *args: Any) -> None:
        self.instrs.append((op,) + args)

    def generate(self, program: Program) -> list[tuple]:
        for s in program.statements:
            self.visit_stmt(s)
        return self.instrs

    # ----- pernyataan -----
    def visit_stmt(self, s: Stmt) -> None:
        if isinstance(s, Let):
            self.visit_Let(s)
        elif isinstance(s, Print):
            self.visit_Print(s)
        elif isinstance(s, If):
            self.visit_If(s)
        elif isinstance(s, While):
            self.visit_While(s)
        elif isinstance(s, Block):
            self.visit_Block(s)
        elif isinstance(s, Expression):
            self.visit_Expression(s)
        else:
            raise TypeError(f"stmt tidak didukung: {type(s).__name__}")

    def visit_Let(self, s: Let) -> None:
        self.visit_expr(s.initializer)
        self._emit("STORE", s.name)

    def visit_Print(self, s: Print) -> None:
        self.visit_expr(s.expression)
        self._emit("PRINT")

    def visit_Expression(self, s: Expression) -> None:
        # hasil ekspresi dibuang: PUSH lalu POP
        self.visit_expr(s.expression)
        self._emit("POP")

    def visit_Block(self, s: Block) -> None:
        for st in s.statements:
            self.visit_stmt(st)

    def visit_If(self, s: If) -> None:
        else_lbl = self._new_label("L_else")
        end_lbl = self._new_label("L_end")
        self.visit_expr(s.condition)
        self._emit("JUMP_IF_FALSE", else_lbl)
        self.visit_stmt(s.then_branch)
        self._emit("JUMP", end_lbl)
        self._emit("LABEL", else_lbl)
        if s.else_branch is not None:
            self.visit_stmt(s.else_branch)
        self._emit("LABEL", end_lbl)

    def visit_While(self, s: While) -> None:
        top_lbl = self._new_label("L_top")
        end_lbl = self._new_label("L_end")
        self._emit("LABEL", top_lbl)
        self.visit_expr(s.condition)
        self._emit("JUMP_IF_FALSE", end_lbl)
        self.visit_stmt(s.body)
        self._emit("JUMP", top_lbl)
        self._emit("LABEL", end_lbl)

    # ----- ekspresi -----
    def visit_expr(self, e: Expr) -> None:
        if isinstance(e, Binary):
            self.visit_Binary(e)
        elif isinstance(e, Unary):
            self.visit_Unary(e)
        elif isinstance(e, Literal):
            self.visit_Literal(e)
        elif isinstance(e, Variable):
            self.visit_Variable(e)
        elif isinstance(e, Assign):
            self.visit_Assign(e)
        elif isinstance(e, Logical):
            self.visit_Logical(e)
        elif isinstance(e, Grouping):
            self.visit_Grouping(e)
        else:
            raise TypeError(f"expr tidak didukung: {type(e).__name__}")

    def visit_Binary(self, e: Binary) -> None:
        # anak kiri didorong lebih dahulu, sehingga berada di bawah anak kanan
        self.visit_expr(e.left)
        self.visit_expr(e.right)
        op_map = {
            "+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV",
            "==": "EQ", "<": "LT", ">": "GT",
        }
        if e.op in op_map:
            self._emit(op_map[e.op])
        elif e.op == "!=":
            self._emit("EQ")
            self._emit("NOT")
        elif e.op == "<=":
            self._emit("GT")
            self._emit("NOT")
        elif e.op == ">=":
            self._emit("LT")
            self._emit("NOT")
        else:
            raise ValueError(f"operator biner tidak dikenal: {e.op}")

    def visit_Unary(self, e: Unary) -> None:
        if e.op == "-":
            # negasi: PUSH 0; eval(operand); SUB → 0 - operand
            self._emit("PUSH", 0)
            self.visit_expr(e.operand)
            self._emit("SUB")
        elif e.op == "!":
            self.visit_expr(e.operand)
            self._emit("NOT")
        else:
            raise ValueError(f"operator uner tidak dikenal: {e.op}")

    def visit_Literal(self, e: Literal) -> None:
        self._emit("PUSH", e.value)

    def visit_Variable(self, e: Variable) -> None:
        self._emit("LOAD", e.name)

    def visit_Assign(self, e: Assign) -> None:
        # simpan ke env; tidak meninggalkan salinan di stack
        self.visit_expr(e.value)
        self._emit("STORE", e.name)

    def visit_Logical(self, e: Logical) -> None:
        # short-circuit menghasilkan bool dari kedua operand
        if e.op == "and":
            false_lbl = self._new_label("L_false")
            end_lbl = self._new_label("L_end")
            self.visit_expr(e.left)
            self._emit("JUMP_IF_FALSE", false_lbl)
            self.visit_expr(e.right)
            self._emit("JUMP_IF_FALSE", false_lbl)
            self._emit("PUSH", True)
            self._emit("JUMP", end_lbl)
            self._emit("LABEL", false_lbl)
            self._emit("PUSH", False)
            self._emit("LABEL", end_lbl)
        elif e.op == "or":
            eval_b_lbl = self._new_label("L_eval_b")
            false_lbl = self._new_label("L_false")
            end_lbl = self._new_label("L_end")
            self.visit_expr(e.left)
            self._emit("JUMP_IF_FALSE", eval_b_lbl)
            self._emit("PUSH", True)
            self._emit("JUMP", end_lbl)
            self._emit("LABEL", eval_b_lbl)
            self.visit_expr(e.right)
            self._emit("JUMP_IF_FALSE", false_lbl)
            self._emit("PUSH", True)
            self._emit("JUMP", end_lbl)
            self._emit("LABEL", false_lbl)
            self._emit("PUSH", False)
            self._emit("LABEL", end_lbl)
        else:
            raise ValueError(f"operator logika tidak dikenal: {e.op}")

    def visit_Grouping(self, e: Grouping) -> None:
        # tanda kurung hanya menentukan urutan evaluasi yang sudah dipatuhi
        # oleh struktur pohon; ditembus langsung ke inner.
        self.visit_expr(e.expression)


# ----- format bytecode -----
def format_bytecode(instrs: list[tuple]) -> str:
    lines: list[str] = []
    for instr in instrs:
        op = instr[0]
        args = instr[1:]
        if not args:
            lines.append(op)
        else:
            parts = [op] + [_fmt_operand(a) for a in args]
            lines.append(" ".join(parts))
    return "\n".join(lines)


def _fmt_operand(a: Any) -> str:
    if isinstance(a, bool):
        return "true" if a else "false"
    if a is None:
        return "nil"
    if isinstance(a, str):
        return a
    return repr(a)


def main() -> None:
    # Program sumber (AST dibangun manual sesuai parser modul 2):
    #   let x = 1 + 2
    #   print x
    program = Program(statements=[
        Let(name="x", initializer=Binary(
            left=Literal(1), op="+", right=Literal(2))),
        Print(expression=Variable(name="x")),
    ])
    print("=== Sumber ===")
    print("let x = 1 + 2;")
    print("print x;")
    print()
    gen = CodeGenerator()
    instrs = gen.generate(program)
    print("=== Bytecode ===")
    print(format_bytecode(instrs))


if __name__ == "__main__":
    main()

Program utama membangun AST untuk let x = 1 + 2; print x; secara manual, lalu memanggil CodeGenerator().generate(program) untuk memperoleh bytecode. Pembangunan AST dilakukan manual agar codegen menjadi titik perhatian. Pada pipeline nyata, AST ini dihasilkan oleh parser modul 2. Keluaran berikut diperoleh dengan menjalankan python3 codegen.py.

text Keluaran

=== Sumber ===
let x = 1 + 2;
print x;

=== Bytecode ===
PUSH 1
PUSH 2
ADD
STORE x
LOAD x
PRINT

Bytecode yang dihasilkan terdiri atas enam instruksi. Dua instruksi PUSH masing-masing mendorong 1 dan 2 ke puncak stack, lalu ADD menggabungkan keduanya menjadi 3 di puncak stack. Instruksi STORE x memindahkan 3 dari puncak stack ke env["x"], sehingga stack kembali kosong. Pernyataan print x diturunkan menjadi LOAD x yang mendorong 3 kembali ke puncak stack, lalu PRINT memunculkannya ke stdout. Verifikasi manual terhadap semantik sumber menunjukkan bahwa x = 1 + 2 = 3, dan print x mencetak 3, sehingga bytecode di atas sudah benar.

Ringkasan#

Codegen ekspresi menelusuri AST secara post-order, dengan anak kiri didorong lebih dahulu sehingga berada di bawah anak kanan di puncak stack.
Operator biner tanpa opcode tunggal, yaitu !=, <=, dan >=, diturunkan menjadi dua instruksi yang memanfaatkan NOT.
Kontrol alur pada If dan While memakai label string sebagai sasaran lompatan, dengan LABEL sebagai pseudo-instruksi penanda posisi.
Logika pendek and dan or dievaluasi dengan dua lompatan JUMP_IF_FALSE yang menghasilkan bool.

Referensi#

Three-address code — Wikipedia — Pembanding antara codegen tiga alamat dan codegen stack yang dipakai pada topik ini.
Crafting Interpreters — Robert Nystrom — Bab 17 membahas codegen dari AST ke bytecode stack VM dengan pola visitor yang serupa.
Stack machine — Wikipedia — Konvensi urutan operand pada instruksi aritmetika berbasis stack.