Decide Before Running What Can Be Decided — Bytecode

한 줄 요약

트리를 매번 걷는 대신, 트리를 한 번 평평한 명령 목록(바이트코드) 으로 옮겨 두고 그 목록을 반복문 하나로 돌리는 것이 바이트코드 VM 입니다. 값은 스택 하나에 올렸다 내리고, 이름은 컴파일할 때 슬롯 번호로 바꿔 두며, if·while 은 나중에 채우는 점프 오프셋이 됩니다.

왜 이게 필요했나

트리 인터프리터는 a + b 하나를 계산하는 데도 노드 이름을 비교하고, 재귀로 내려가고, 이름을 환경 사슬에서 찾습니다. 반복문 안에서 백만 번 돌면 이 일을 백만 번 합니다. 그런데 그중 상당수는 프로그램이 돌기 전에 이미 정해져 있습니다. x 가 어느 선언인지, 그 선언이 함수의 몇 번째 지역 변수인지, while 의 끝이 어디인지 — 모두 코드만 보고 알 수 있습니다.

바이트코드 컴파일러는 이런 결정을 한 번만 내려 명령에 박아 둡니다. GET_LOCAL 2 는 "사슬을 올라가며 x 를 찾아라" 가 아니라 "프레임의 2번 칸을 올려라" 입니다. CPython·JVM·Lua 가 모두 이 구조입니다(CPython 은 python3 -m dis 로 볼 수 있습니다).

어떻게 동작하나

청크와 상수 풀. 함수 하나의 코드를 청크라고 부릅니다. 명령은 [이름, 인자, 줄, 칸] 이고, 숫자·참거짓·전역 이름·함수 청크는 상수 풀에 한 번씩 넣고 명령은 그 번호를 씁니다. 같은 값은 한 번만 넣는데, 파이썬에서 True == 1 이고 해시도 같아서 값만 열쇠로 쓰면 true 와 1 이 한 칸을 나눠 씁니다 — 타입까지 열쇠에 넣어야 합니다.

스택 하나. 이 VM 은 스택이 하나입니다. 스크립트의 지역 변수, 호출된 함수 값과 인자, 계산 중인 임시값이 모두 같은 스택에 쌓입니다. 프레임은 (청크, 다음 명령 자리, 바닥)이고, 바닥은 그 프레임의 슬롯 0 이 있는 스택 자리입니다.

fn f(a, b) { let c = a * b; return c + 1; }     print f(3, 4);

스크립트: GET_GLOBAL f · CONST 3 · CONST 4 · CALL 2 · PRINT
스택      [ … | <fn f> | 3 | 4 ]   CALL 2 → 새 프레임의 바닥 = 스택 길이 − 2 = 'a' 칸
f:        GET_LOCAL 0 · GET_LOCAL 1 · MUL        [ … | <fn f> | 3 | 4 | 12 ]  ← 12 가 곧 c(슬롯 2)
          GET_LOCAL 2 · CONST 1 · ADD · RETURN    RETURN: 결과를 내리고 바닥 − 1(함수 값)까지 걷고 결과를 올림
          CONST 0 · RETURN                        return 없이 끝날 때를 위한 꼬리(여기서는 닿지 않는다)

let 으로 만든 지역 변수는 값이 이미 올라간 그 자리가 곧 슬롯입니다. 따로 옮기지 않습니다. 대신 블록을 나올 때 그 블록의 지역 변수 수만큼 POP 해야 스택이 제자리로 돌아옵니다. 식 문장(f(1);)의 값도 POP 으로 버려야 합니다. 둘 중 하나라도 빠지면 반복문이 돌 때마다 스택이 한 칸씩 자랍니다 — 결과는 맞는데 메모리가 샙니다. 그래서 이 실습은 스택 최대 깊이를 기준과 한 칸까지 대조합니다.

점프 패치. if (c) { A } else { B } 를 옮길 때 JUMP_IF_FALSE 를 내는 순간에는 else 가 어디서 시작할지 모릅니다. 인자 자리를 비워 둔 채 내보내고(emit_jump), A 를 다 옮긴 뒤 돌아와 채웁니다(patch_jump). 오프셋은 점프 다음 명령에서 셉니다 — 목적지 = 점프 자리 + 1 + 오프셋. 점프 자리에서 세느냐 다음 자리에서 세느냐의 한 칸 차이가 가장 흔한 버그이고, 그 버그는 대개 "가끔 한 줄을 건너뛴다" 로 나타납니다.

if 없이 else:   조건 · JUMP_IF_FALSE →끝 · then
else 가 있으면: 조건 · JUMP_IF_FALSE →else · then · JUMP →끝 · else
while:          [처음] 조건 · JUMP_IF_FALSE →끝 · 몸체 · JUMP →처음(음수 오프셋)
&&:             왼쪽 · JUMP_IF_FALSE_OR_POP →끝 · 오른쪽        (거짓이면 값을 남긴 채 건너뛴다)
||:             왼쪽 · JUMP_IF_TRUE_OR_POP  →끝 · 오른쪽

이 VM 은 함수를 맨 바깥에서만 선언하게 합니다. 함수 안의 함수가 바깥 지역 변수를 붙잡으려면(클로저) 그 변수를 스택에서 꺼내 힙으로 옮기는 장치(Lua·clox 의 upvalue)가 필요한데, 이 코스는 그 이야기를 읽기로만 두고 VM 은 전역 함수와 재귀까지 다룹니다.

현장에서 만나는 모습

• python3 -m dis. 파이썬 함수를 디스어셈블하면 LOAD_FAST 0(지역 슬롯), LOAD_CONST, POP_JUMP_IF_FALSE 가 보입니다. 이 모듈에서 만드는 것과 거의 같은 모양입니다. 한 줄짜리 식 문장 뒤의 POP_TOP 도 보입니다.
• JVM 의 스택 맵. 자바 바이트코드 검증기는 모든 점프 목적지에서 스택 깊이와 타입이 맞는지 확인합니다. 블록 끝의 POP 이나 식 문장의 POP 을 빠뜨린 컴파일러가 만든 클래스는 로딩 단계에서 거절됩니다 — 스택 깊이가 '결과' 만큼 중요한 계약이라는 뜻입니다.
• 레지스터 VM. Lua 5 와 Dalvik 은 스택 대신 가상 레지스터를 쓰는 VM 입니다. 명령 수가 줄어드는 대신 명령이 커집니다. 어느 쪽이든 '실행 전에 정할 수 있는 것은 정해 둔다' 는 생각은 같습니다.

다음 실습에서 할 것

compiler.py 와 vm.py 를 번갈아 키웁니다 — 상수 풀과 식 명령(그리고 사람이 읽는 disassemble), 산술 VM, 전역과 지역 슬롯, 점프 패치, 점프 실행, 함수와 CALL/RETURN, 그리고 소스부터 VM 까지 잇는 파이프라인. 채점기는 컴파일러 쪽은 명령 하나하나를, VM 쪽은 출력·실행한 명령 수·스택 최대 깊이를 기준과 대조합니다. 끝으로 고정 프로그램 넷을 여러분의 VM 으로 돌려 숫자를 보고서로 남깁니다.