Стековая виртуальная машина

Байткод сгенерирован — теперь нужна машина, которая прочитает его и выполнит.

Виртуальная машина (ВМ) — программа, имитирующая процессор: она читает байткод инструкция за инструкцией и выполняет их над своим внутренним состоянием.

Стековая ВМ устроена удивительно просто. У неё есть стек значений и список инструкций. Она читает инструкции по порядку и для каждой меняет стек. После последней инструкции на вершине стека лежит результат.

Цикл выборки и исполнения

Сердце любой ВМ — цикл «прочитать инструкцию → выполнить → перейти к следующей». На английском это называют fetch-decode-execute.

    +---- взять следующую инструкцию
    |              |
    |              v
    |       что это за код?
    |              |
    |              v
    |        выполнить над стеком
    |              |
    +--------------+  (пока инструкции не кончатся)

Реализация ВМ на Python

Возьмём байткод из прошлого урока и исполним его. Стек — обычный список, методы append и pop работают как push/pop.

def run(code):
    stack = []
    for instr in code:
        op = instr[0]
        if op == "PUSH":
            stack.append(instr[1])
        elif op == "ADD":
            b = stack.pop(); a = stack.pop(); stack.append(a + b)
        elif op == "SUB":
            b = stack.pop(); a = stack.pop(); stack.append(a - b)
        elif op == "MUL":
            b = stack.pop(); a = stack.pop(); stack.append(a * b)
        elif op == "DIV":
            b = stack.pop(); a = stack.pop(); stack.append(a / b)
    return stack[-1]

# байткод для 2 + 3 * 4
code = [("PUSH", 2), ("PUSH", 3), ("PUSH", 4), ("MUL",), ("ADD",)]
print(run(code))

Вывод:

14

Как работает под капотом

Проследим стек по шагам для 2 + 3 * 4:

Каждая операция снимает ровно столько операндов, сколько ей нужно, и кладёт один результат. В конце на стеке остаётся единственное число — ответ. Обратите внимание на порядок pop: для SUB и DIV сначала снимается правый операнд b, потом левый a, и считается a - b, а не наоборот.

Почему важен порядок снятия

Проверим некоммутативную операцию.

def run(code):
    stack = []
    for instr in code:
        if instr[0] == "PUSH": stack.append(instr[1])
        elif instr[0] == "SUB":
            b = stack.pop(); a = stack.pop(); stack.append(a - b)
    return stack[-1]

print(run([("PUSH", 10), ("PUSH", 3), ("SUB",)]))  # 10 - 3

Вывод:

7

Частые ошибки

Главная — перепутать порядок снятия для SUB и DIV. Стек выдаёт элементы в обратном порядке (последний положенный снимается первым), поэтому правый операнд снимается раньше левого. Перепутаете — получите 3 - 10 = -7 вместо 7.

Вторая — забыть, что после исполнения на стеке должен остаться ровно один элемент. Если осталось больше или меньше, значит, байткод сгенерирован неправильно (например, лишний PUSH).

Итог

• ВМ имитирует процессор: читает байткод и меняет внутреннее состояние.
• Цикл fetch-execute читает инструкции по порядку и применяет к стеку.
• Стек — это список; PUSH добавляет, операции снимают операнды и кладут результат.
• Для SUB/DIV важен порядок снятия: правый операнд снимается раньше левого.