바이트코드 덩어리

이론에만 거의 모든 시간을 쏟고 있다면, 실용적인 것에 관심을 돌리십시오. 그러면 당신의 이론이 향상될 것입니다. 실용적인 것에만 거의 모든 시간을 쏟고 있다면, 이론적인 것에 관심을 돌리십시오. 그러면 당신의 실용적인 능력이 향상될 것입니다.

도널드 커누스(Donald Knuth)

jlox를 통해 Lox를 완벽하게 구현했지만, 아직 책이 끝나지 않은 이유는 무엇일까요? 부분적으로는 jlox가 많은 일을 JVM에 의존하기 때문입니다. 인터프리터가 하드웨어(metal) 수준까지 어떻게 작동하는지 이해하고 싶다면, 이러한 세부적인 부분들을 직접 구축해야 합니다.

jlox만으로는 충분하지 않은 더 근본적인 이유는 너무 느리기 때문입니다. 트리 순회 인터프리터는 일부 고수준의 선언적 언어에는 적합합니다. 하지만 일반적인 목적의 명령형 언어—심지어 Lox와 같은 “스크립팅” 언어라도—이는 통용되지 않습니다. 다음의 작은 스크립트를 예로 들어봅시다.

fun fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2); 
}

var before = clock();
print fib(40);
var after = clock();
print after - before;

제 노트북에서는 이 코드를 jlox로 실행하는 데 약 72초가 걸립니다. 동등한 C 프로그램은 0.5초 만에 완료됩니다. 우리의 동적 타입 스크립팅 언어가 수동 메모리 관리가 가능한 정적 타입 언어만큼 빠를 수는 없지만, 두 자릿수 이상 느린 속도에 만족할 필요는 없습니다.

jlox를 프로파일러로 실행하여 핫스팟(hotspot)을 튜닝하고 조정할 수도 있지만, 그것만으로는 한계가 있습니다. AST를 순회하는 실행 모델은 근본적으로 잘못된 설계입니다. AMC 그렘린(Gremlin)을 SR-71 블랙버드(Blackbird)로 광택낼 수 없는 것처럼, 우리는 이 모델을 원하는 성능으로 마이크로 최적화할 수 없습니다.

우리는 핵심 모델을 재고해야 합니다. 이 장에서는 그 모델인 바이트코드(bytecode)를 소개하고, 우리의 새로운 인터프리터인 clox를 시작합니다.

14 . 1바이트코드?

엔지니어링에서 트레이드오프(trade-off)가 없는 선택은 거의 없습니다. 바이트코드를 선택하는 이유를 가장 잘 이해하려면, 다른 몇 가지 대안과 비교해봅시다.

14 . 1 . 1왜 AST를 순회하지 않는가?

기존 인터프리터는 몇 가지 장점이 있습니다.

• 우선, 이미 작성했습니다. 끝났죠. 그리고 그렇게 된 주된 이유는 이러한 방식의 인터프리터가 구현하기 정말 간단하기 때문입니다. 코드의 런타임 표현이 문법에 직접 매핑됩니다. 파서에서 런타임에 필요한 데이터 구조로 넘어가는 과정은 거의 노력이 들지 않습니다.

• 휴대성(portable)이 좋습니다. 현재 인터프리터는 Java로 작성되었고 Java가 지원하는 모든 플랫폼에서 실행됩니다. 우리는 동일한 접근 방식을 사용하여 C로 새로운 구현을 작성하고 기본적으로 모든 플랫폼에서 언어를 컴파일하고 실행할 수 있습니다.

이것들은 분명한 장점입니다. 하지만 다른 한편으로는 메모리 효율적이지 않습니다. 각 문법 조각은 AST 노드가 됩니다. 1 + 2와 같은 작은 Lox 표현식은 다음과 같이 수많은 객체와 그 사이의 많은 포인터로 변환됩니다.

각 포인터는 객체에 32비트 또는 64비트의 추가 오버헤드를 더합니다. 더 나쁜 것은, 힙(heap)에 느슨하게 연결된 객체들의 웹 형태로 데이터를 분산시키면 공간 지역성(spatial locality)에 좋지 않은 영향을 미칩니다.

현대 CPU는 RAM에서 데이터를 가져오는 것보다 훨씬 빠르게 데이터를 처리합니다. 이를 보완하기 위해 칩은 여러 계층의 캐시를 가지고 있습니다. 필요한 메모리가 이미 캐시에 있다면 더 빠르게 로드될 수 있습니다. 100 배 이상 더 빠릅니다.

데이터는 어떻게 캐시로 들어갈까요? 기계는 추측성으로 데이터를 캐시에 채워 넣습니다. 그 휴리스틱(heuristic)은 아주 간단합니다. CPU가 RAM에서 데이터를 읽을 때마다 인접한 바이트 묶음 전체를 가져와 캐시에 저장합니다.

만약 프로그램이 다음에 캐시 라인 내에 충분히 가까운 데이터를 요청한다면, 우리의 CPU는 공장의 잘 기름칠된 컨베이어 벨트처럼 작동합니다. 우리는 이것을 정말 활용하고 싶습니다. 캐시를 효과적으로 사용하려면, 메모리에서 코드를 표현하는 방식이 밀집되어 읽는 순서대로 정렬되어야 합니다.

이제 저 트리를 다시 봅시다. 저 하위 객체들은 어디에나 있을 수 있습니다. 트리 순회자가 자식 노드의 참조를 따라가는 모든 단계는 캐시 범위를 벗어나 CPU가 RAM에서 새로운 데이터 덩어리를 가져올 때까지 대기하도록 강제할 수 있습니다. 단순히 포인터 필드와 객체 헤더를 가진 저 트리 노드들의 오버헤드만으로도 객체들을 서로 멀리 떨어뜨리고 캐시 밖으로 밀어내는 경향이 있습니다.

우리의 AST 순회자는 인터페이스 디스패치와 Visitor 패턴에 대한 다른 오버헤드도 가지고 있지만, 지역성(locality) 문제만으로도 더 나은 코드 표현을 정당화하기에 충분합니다.

14 . 1 . 2왜 네이티브 코드로 컴파일하지 않는가?

정말 빠르고 싶다면, 모든 간접 계층을 제거하고 싶을 것입니다. 바로 하드웨어(metal) 수준으로. 머신 코드(Machine code). 심지어 빠르게 들립니다. 머신 코드.

칩이 지원하는 네이티브 명령어 집합으로 직접 컴파일하는 것이 가장 빠른 언어들이 하는 일입니다. 네이티브 코드를 목표로 하는 것은 엔지니어들이 실제로 머신 코드로 프로그램을 손으로 작성했던 초창기부터 가장 효율적인 옵션이었습니다.

머신 코드나 그것의 약간 더 인간 친화적인 사촌인 어셈블리 코드를 한 번도 작성해본 적이 없다면, 아주 부드러운 소개를 해드리겠습니다. 네이티브 코드는 이진수로 직접 인코딩된 밀집된 일련의 연산입니다. 각 명령어는 1바이트에서 몇 바이트 길이이며, 거의 정신 나갈 정도로 저수준입니다. "이 주소에서 이 레지스터로 값을 이동하라." "이 두 레지스터에 있는 정수를 더하라." 그런 것들입니다.

CPU는 명령어들을 순서대로 디코딩하고 실행합니다. 우리의 AST처럼 트리 구조는 없으며, 제어 흐름은 코드의 한 지점에서 다른 지점으로 직접 점프하여 처리됩니다. 간접성도, 오버헤드도, 불필요한 건너뛰기나 포인터 추적도 없습니다.

번개처럼 빠르지만, 그 성능에는 대가가 따릅니다. 우선, 네이티브 코드로 컴파일하는 것은 쉽지 않습니다. 오늘날 널리 사용되는 대부분의 칩은 수십 년에 걸쳐 축적된 수많은 명령어들을 가진 복잡한 비잔틴(Byzantine) 아키텍처를 가지고 있습니다. 이들은 정교한 레지스터 할당, 파이프라이닝 및 명령어 스케줄링을 요구합니다.

그리고 물론, 휴대성을 포기해야 합니다. 특정 아키텍처를 마스터하는 데 몇 년을 보낸다 해도, 여전히 여러 인기 있는 명령어 집합 중 하나에만 적용됩니다. 여러분의 언어를 모든 아키텍처에서 사용하려면, 모든 명령어 집합을 배우고 각각에 대해 별도의 백엔드를 작성해야 합니다.

14 . 1 . 3바이트코드란?

이 두 가지 요점을 기억해둡시다. 한쪽 끝에는 간단하고 휴대성이 좋지만 느린 트리 순회 인터프리터가 있습니다. 다른 쪽 끝에는 복잡하고 플랫폼에 종속적이지만 빠른 네이티브 코드가 있습니다. 바이트코드는 그 중간에 위치합니다. 바이트코드는 트리 순회자의 휴대성을 유지합니다—이 책에서는 어셈블리 코드로 손을 더럽힐 필요가 없습니다. 성능 향상을 위해 일부 단순성을 희생하지만, 네이티브 코드만큼 빠르지는 않습니다.

구조적으로 바이트코드는 머신 코드와 유사합니다. 밀집된 선형적인 이진 명령어 시퀀스입니다. 이는 오버헤드를 낮추고 캐시와 잘 작동합니다. 하지만 바이트코드는 실제 칩보다 훨씬 간단하고 고수준의 명령어 집합입니다. (많은 바이트코드 형식에서 각 명령어는 단일 바이트 길이이므로 "바이트코드"라고 불립니다.)

어떤 소스 언어에서 네이티브 컴파일러를 작성하고 있다고 상상해 보십시오. 그리고 가장 쉽게 목표로 삼을 수 있는 아키텍처를 정의할 전권을 부여받았다고 가정합시다. 바이트코드는 그런 식입니다. 컴파일러 작성자로서의 삶을 더 쉽게 만들어주는 이상적인 환상적인 명령어 집합입니다.

물론, 환상적인 아키텍처의 문제는 그것이 존재하지 않는다는 것입니다. 우리는 이를 에뮬레이터(emulator)를 작성하여 해결합니다—소프트웨어로 작성된 시뮬레이션 칩이 바이트코드를 한 번에 하나의 명령어씩 해석합니다. 즉, 가상 머신(VM)인 셈입니다.

이 에뮬레이션 계층은 오버헤드를 추가하며, 이것이 바이트코드가 네이티브 코드보다 느린 주요 이유입니다. 하지만 그 대가로 우리는 휴대성을 얻습니다. 우리가 관심 있는 모든 기계에서 이미 지원되는 C와 같은 언어로 VM을 작성하면, 우리가 원하는 모든 하드웨어 위에서 에뮬레이터를 실행할 수 있습니다.

이것이 우리가 새로운 인터프리터인 clox로 선택할 경로입니다. 우리는 Python, Ruby, Lua, OCaml, Erlang 등의 주요 구현체들의 발자취를 따를 것입니다. 여러 면에서 우리 VM의 설계는 이전 인터프리터의 구조와 유사할 것입니다.

물론, 우리는 단계를 엄격하게 순서대로 구현하지 않을 것입니다. 이전 인터프리터와 마찬가지로, 언어 기능을 하나씩 구현하면서 왔다 갔다 할 것입니다. 이 장에서는 애플리케이션의 골격을 잡고 바이트코드 덩어리를 저장하고 표현하는 데 필요한 데이터 구조를 생성할 것입니다.

14 . 2시작하기

어디에서 시작해야 할까요? 당연히 main()부터죠. 여러분의 믿음직한 텍스트 에디터를 켜고 타이핑을 시작하세요.

#include "common.h"

int main(int argc, const char* argv[]) {
  return 0;
}

이 작은 씨앗에서 우리는 전체 VM을 키울 것입니다. C는 우리에게 거의 아무것도 제공하지 않으므로, 먼저 흙을 다지는 데 시간을 좀 투자해야 합니다. 그중 일부가 이 헤더 파일에 들어갑니다.

#ifndef clox_common_h
#define clox_common_h

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#endif

인터프리터 전체에서 사용할 몇 가지 타입과 상수가 있는데, 이곳이 그것들을 두기에 편리한 장소입니다. 지금은 유서 깊은 NULL, size_t, C99의 훌륭한 부울 타입 bool, 그리고 명시적 크기의 정수 타입들—uint8_t와 그 친구들입니다.

14 . 3명령어 덩어리

다음으로, 코드 표현을 정의할 모듈이 필요합니다. 저는 바이트코드 시퀀스를 "덩어리(chunk)"라고 부르고 있었으니, 이 모듈의 공식 이름으로 지정합시다.

#ifndef clox_chunk_h
#define clox_chunk_h

#include "common.h"

#endif

우리 바이트코드 형식에서 각 명령어는 1바이트 연산 코드(operation code) (줄여서 opcode)를 가집니다. 이 숫자는 우리가 다루는 명령어의 종류—덧셈, 뺄셈, 변수 조회 등—를 제어합니다. 우리는 이것들을 여기에 정의합니다.

#include "common.h"

typedef enum {
  OP_RETURN,
} OpCode;

#endif

지금은 단일 명령어인 OP_RETURN으로 시작합니다. 완전한 VM을 갖게 되면, 이 명령어는 "현재 함수에서 반환하라"는 의미가 될 것입니다. 아직은 그리 유용하지 않다는 것을 인정하지만, 어딘가에서 시작해야 하며, 이것은 우리가 나중에 알게 될 이유로 인해 특히 간단한 명령어입니다.

14 . 3 . 1명령어 동적 배열

바이트코드는 일련의 명령어입니다. 결국, 우리는 명령어와 함께 다른 데이터도 저장할 것이므로, 이 모든 것을 담을 구조체(struct)를 미리 만들어 두겠습니다.

} OpCode;

typedef struct {
  uint8_t* code;
} Chunk;

#endif

현재 이것은 단순히 바이트 배열을 감싸는 래퍼입니다. 덩어리를 컴파일하기 전에 배열의 크기가 얼마나 될지 알 수 없으므로 동적이어야 합니다. 동적 배열은 제가 가장 좋아하는 데이터 구조 중 하나입니다. 바닐라가 가장 좋아하는 아이스크림 맛이라고 주장하는 것처럼 들리겠지만, 제 말을 들어보세요. 동적 배열은 다음을 제공합니다.

• 캐시 친화적이고 밀집된 저장 방식

• 상수 시간(constant-time)의 인덱스 요소 조회

• 배열 끝에 요소를 추가하는 상수 시간

이러한 기능들은 우리가 Java의 `ArrayList` 클래스를 통해 jlox에서 동적 배열을 항상 사용했던 이유와 정확히 일치합니다. 이제 C 언어를 사용하므로 직접 구현해야 합니다. 동적 배열에 대해 잘 모른다면, 아이디어는 매우 간단합니다. 배열 자체 외에 두 개의 숫자를 유지합니다: 할당된 배열의 요소 수("capacity")와 실제로 사용 중인 할당된 항목의 수("count").

typedef struct {

  int count;
  int capacity;

  uint8_t* code;
} Chunk;

요소를 추가할 때, count가 capacity보다 작으면, 이미 배열에 사용 가능한 공간이 있습니다. 우리는 그곳에 새 요소를 저장하고 count를 증가시킵니다.

사용 가능한 용량이 없으면, 과정이 조금 더 복잡해집니다.

1. 더 많은 용량을 가진 새로운 배열을 할당합니다.
2. 기존 요소들을 이전 배열에서 새 배열로 복사합니다.
3. 새로운 capacity를 저장합니다.
4. 이전 배열을 삭제합니다.
5. code를 새 배열을 가리키도록 업데이트합니다.
6. 이제 공간이 생겼으니 새 배열에 요소를 저장합니다.
7. count를 업데이트합니다.

구조체가 준비되었으니, 이제 이 구조체와 함께 작동할 함수들을 구현해 봅시다. C에는 생성자가 없으므로, 새로운 청크를 초기화하는 함수를 선언합니다.

} Chunk;

void initChunk(Chunk* chunk);

#endif

그리고 다음과 같이 구현합니다.

#include <stdlib.h>

#include "chunk.h"

void initChunk(Chunk* chunk) {
  chunk->count = 0;
  chunk->capacity = 0;
  chunk->code = NULL;
}

동적 배열은 완전히 비어있는 상태로 시작합니다. 우리는 아직 원시 배열(raw array)조차 할당하지 않습니다. 덩어리 끝에 바이트를 추가하려면 새 함수를 사용합니다.

void initChunk(Chunk* chunk);

void writeChunk(Chunk* chunk, uint8_t byte);

#endif

이것이 흥미로운 작업이 일어나는 곳입니다.

void writeChunk(Chunk* chunk, uint8_t byte) {
  if (chunk->capacity < chunk->count + 1) {
    int oldCapacity = chunk->capacity;
    chunk->capacity = GROW_CAPACITY(oldCapacity);
    chunk->code = GROW_ARRAY(uint8_t, chunk->code,
        oldCapacity, chunk->capacity);
  }

  chunk->code[chunk->count] = byte;
  chunk->count++;
}

가장 먼저 해야 할 일은 현재 배열에 새 바이트를 위한 용량이 이미 있는지 확인하는 것입니다. 용량이 없으면, 공간을 만들기 위해 배열을 먼저 확장해야 합니다. (배열이 NULL이고 capacity가 0인 경우, 첫 번째 쓰기에서도 이 경우에 해당됩니다.)

배열을 확장하기 위해, 먼저 새로운 용량을 계산하고 그 크기로 배열을 확장합니다. 이 두 가지 저수준 메모리 작업은 새로운 모듈에 정의되어 있습니다.

#include "chunk.h"

#include "memory.h"

void initChunk(Chunk* chunk) {

이것으로 시작하기에 충분합니다.

#ifndef clox_memory_h
#define clox_memory_h

#include "common.h"

#define GROW_CAPACITY(capacity) \
    ((capacity) < 8 ? 8 : (capacity) * 2)

#endif

이 매크로는 주어진 현재 용량에 기반하여 새로운 용량을 계산합니다. 우리가 원하는 성능을 얻기 위해 중요한 부분은 이 매크로가 이전 크기를 기반으로 확장된다는 것입니다. 우리는 두 배로 성장시키는데, 이는 꽤 일반적인 방식입니다. 1.5배도 흔히 사용되는 선택지입니다.

또한 현재 용량이 0인 경우도 처리합니다. 이 경우, 1개부터 시작하는 대신 바로 8개 요소로 점프합니다. 이는 배열이 매우 작을 때 발생하는 약간의 추가 메모리 낭비를 줄여주지만, 매우 작은 덩어리에서는 몇 바이트의 낭비를 감수해야 합니다.

원하는 용량을 알면, GROW_ARRAY()를 사용하여 그 크기로 배열을 생성하거나 확장합니다.

#define GROW_CAPACITY(capacity) \
    ((capacity) < 8 ? 8 : (capacity) * 2)

#define GROW_ARRAY(type, pointer, oldCount, newCount) \
    (type*)reallocate(pointer, sizeof(type) * (oldCount), \
        sizeof(type) * (newCount))

void* reallocate(void* pointer, size_t oldSize, size_t newSize);

#endif

이 매크로는 실제 작업이 일어나는 reallocate() 함수 호출을 보기 좋게 만들어 줍니다. 매크로 자체는 배열 요소 타입의 크기를 가져오고 결과 void*를 올바른 타입의 포인터로 다시 캐스팅하는 작업을 처리합니다.

이 reallocate() 함수는 clox에서 모든 동적 메모리 관리—메모리 할당, 해제, 기존 할당 크기 변경—에 사용할 단일 함수가 될 것입니다. 모든 이러한 작업을 단일 함수를 통해 처리하는 것은 나중에 얼마나 많은 메모리가 사용 중인지 추적해야 하는 가비지 컬렉터(garbage collector)를 추가할 때 중요해질 것입니다.

reallocate()에 전달되는 두 개의 크기 인수는 수행할 작업을 제어합니다.

많은 경우를 처리해야 하는 것처럼 들리지만, 구현은 다음과 같습니다.

#include <stdlib.h>

#include "memory.h"

void* reallocate(void* pointer, size_t oldSize, size_t newSize) {
  if (newSize == 0) {
    free(pointer);
    return NULL;
  }

  void* result = realloc(pointer, newSize);
  return result;
}

newSize가 0일 때는 free()를 호출하여 할당 해제 경우를 직접 처리합니다. 그렇지 않으면, C 표준 라이브러리의 realloc() 함수에 의존합니다. 이 함수는 우리 정책의 다른 세 가지 측면을 편리하게 지원합니다. oldSize가 0일 때 realloc()은 malloc()을 호출하는 것과 같습니다.

흥미로운 경우는 oldSize와 newSize 모두 0이 아닐 때입니다. 이 경우들은 realloc()에게 이전에 할당된 블록의 크기를 조정하도록 지시합니다. 새 크기가 기존 메모리 블록보다 작으면, 단순히 블록의 크기를 업데이트하고 동일한 포인터를 반환합니다. 새 크기가 더 크면, 기존 메모리 블록을 확장하려고 시도합니다.

이는 해당 블록 이후의 메모리가 아직 사용 중이 아닐 때만 가능합니다. 블록을 확장할 공간이 없으면, realloc()은 대신 원하는 크기의 새로운 메모리 블록을 할당하고, 이전 바이트들을 복사하며, 이전 블록을 해제한 다음, 새 블록에 대한 포인터를 반환합니다. 기억하세요, 이것이 바로 우리 동적 배열이 원하는 동작입니다.

컴퓨터는 유한한 물질 덩어리이지, 컴퓨터 과학 이론이 우리에게 믿게 하려는 완벽한 수학적 추상화가 아니므로, 메모리가 부족하면 할당이 실패할 수 있으며 realloc()은 NULL을 반환할 것입니다. 우리는 이를 처리해야 합니다.

  void* result = realloc(pointer, newSize);

  if (result == NULL) exit(1);

  return result;

VM이 필요한 메모리를 얻을 수 없다면 실제로 유용하게 할 수 있는 일은 없지만, 적어도 이를 감지하고 프로세스를 즉시 중단합니다. NULL 포인터를 반환하고 나중에 문제를 발생시키지 않도록 합니다.

이제 새로운 덩어리를 만들고 그 안에 명령어를 쓸 수 있습니다. 다 끝났을까요? 아닙니다! 우리는 이제 C 언어를 사용하고 있으며, 기억하세요, 예전처럼 메모리를 직접 관리해야 합니다. 그리고 그것은 메모리를 해제하는 것도 포함합니다.

void initChunk(Chunk* chunk);

void freeChunk(Chunk* chunk);

void writeChunk(Chunk* chunk, uint8_t byte);

구현은 다음과 같습니다.

void freeChunk(Chunk* chunk) {
  FREE_ARRAY(uint8_t, chunk->code, chunk->capacity);
  initChunk(chunk);
}

우리는 모든 메모리를 할당 해제한 다음, initChunk()를 호출하여 필드들을 0으로 초기화하고 청크를 잘 정의된 빈 상태로 남겨둡니다. 메모리를 해제하기 위해 매크로 하나를 더 추가합니다.

#define GROW_ARRAY(type, pointer, oldCount, newCount) \
    (type*)reallocate(pointer, sizeof(type) * (oldCount), \
        sizeof(type) * (newCount))

#define FREE_ARRAY(type, pointer, oldCount) \
    reallocate(pointer, sizeof(type) * (oldCount), 0)

void* reallocate(void* pointer, size_t oldSize, size_t newSize);

GROW_ARRAY()처럼, 이것은 reallocate() 호출을 감싸는 래퍼입니다. 이 매크로는 새 크기에 0을 전달하여 메모리를 해제합니다. 알겠습니다, 지루하고 저수준적인 내용이 많았죠. 걱정 마세요, 앞으로의 장에서 이 기능들을 많이 사용할 것이고, 더 높은 수준에서 프로그래밍하게 될 것입니다. 하지만 그전에, 우리만의 기반을 다져야 합니다.

14 . 4덩어리 역어셈블링

이제 바이트코드 덩어리를 생성하는 작은 모듈이 생겼습니다. 샘플 덩어리를 수동으로 빌드하여 시험해 봅시다.

int main(int argc, const char* argv[]) {

  Chunk chunk;
  initChunk(&chunk);
  writeChunk(&chunk, OP_RETURN);
  freeChunk(&chunk);

  return 0;

include하는 것을 잊지 마세요.

#include "common.h"

#include "chunk.h;

int main(int argc, const char* argv[]) {

실행해서 시도해 보세요. 작동했나요? 음 . . . 누가 알겠어요? 우리가 한 일은 메모리에서 몇 바이트를 옮긴 것뿐입니다. 우리가 만든 덩어리 안에 실제로 무엇이 들어있는지 인간 친화적인 방식으로 볼 방법이 없습니다.

이 문제를 해결하기 위해, 우리는 역어셈블러(disassembler)를 만들 것입니다. 어셈블러(assembler)는 "ADD", "MULT"와 같은 CPU 명령어에 대한 사람이 읽을 수 있는 니모닉(mnemonic) 이름을 포함하는 파일을 받아 그것들을 이진 머신 코드 동등물로 번역하는 옛날 프로그램입니다. 역어셈블러는 그 반대 방향으로 작동합니다—머신 코드 덩어리가 주어지면, 명령어들의 텍스트 목록을 출력합니다.

우리는 유사한 것을 구현할 것입니다. 덩어리가 주어지면, 그 안에 있는 모든 명령어를 출력할 것입니다. Lox 사용자는 이것을 사용하지 않겠지만, 우리 Lox 유지보수자는 인터프리터의 내부 코드 표현을 들여다볼 수 있는 창을 제공하므로 분명히 이점을 얻을 것입니다.

main()에서, 덩어리를 생성한 후 역어셈블러로 전달합니다.

  initChunk(&chunk);
  writeChunk(&chunk, OP_RETURN);

  disassembleChunk(&chunk, "test chunk");

  freeChunk(&chunk);

다시 한번, 우리는 또 다른 모듈을 급히 만듭니다.

#include "chunk.h"

#include "debug.h"

int main(int argc, const char* argv[]) {

다음은 해당 헤더 파일입니다.

#ifndef clox_debug_h
#define clox_debug_h

#include "chunk.h"

void disassembleChunk(Chunk* chunk, const char* name);
int disassembleInstruction(Chunk* chunk, int offset);

#endif

main()에서는 disassembleChunk()를 호출하여 전체 덩어리 내의 모든 명령어를 역어셈블합니다. 이 함수는 단일 명령어만 역어셈블하는 다른 함수를 기반으로 구현됩니다. 이 함수가 헤더에 나타나는 이유는 나중에 VM에서 호출할 것이기 때문입니다.

구현 파일의 시작 부분은 다음과 같습니다.

#include <stdio.h>

#include "debug.h"

void disassembleChunk(Chunk* chunk, const char* name) {
  printf("== %s ==\n", name);

  for (int offset = 0; offset < chunk->count;) {
    offset = disassembleInstruction(chunk, offset);
  }
}

덩어리를 역어셈블하려면, 작은 헤더를 출력한 다음 (어떤 덩어리를 보고 있는지 알 수 있도록) 바이트코드를 통해 각 명령어를 역어셈블합니다. 코드를 반복하는 방식은 약간 특이합니다. 루프에서 offset을 증가시키는 대신, disassembleInstruction()이 그 역할을 하도록 합니다. 이 함수를 호출할 때, 주어진 오프셋의 명령어를 역어셈블한 후, 다음 명령어의 오프셋을 반환합니다. 이는 나중에 보겠지만, 명령어들이 크기가 다를 수 있기 때문입니다.

"debug" 모듈의 핵심은 이 함수입니다.

int disassembleInstruction(Chunk* chunk, int offset) {
  printf("%04d ", offset);

  uint8_t instruction = chunk->code[offset];
  switch (instruction) {
    case OP_RETURN:
      return simpleInstruction("OP_RETURN", offset);
    default:
      printf("Unknown opcode %d\n", instruction);
      return offset + 1;
  }
}

먼저, 주어진 명령어의 바이트 오프셋을 출력합니다—이는 덩어리 내에서 이 명령어가 어디에 있는지 알려줍니다. 이는 우리가 제어 흐름을 처리하고 바이트코드 내에서 점프를 시작할 때 유용한 이정표가 될 것입니다.

다음으로, 주어진 오프셋에서 바이트코드에서 단일 바이트를 읽습니다. 이것이 우리의 Opcode입니다. 우리는 그것에 따라 분기합니다. 각 명령어 종류에 대해, 그것을 표시하기 위한 작은 유틸리티 함수로 디스패치합니다. 주어진 바이트가 전혀 명령어로 보이지 않는다면—우리 컴파일러의 버그일 경우—그것도 출력합니다. 현재 우리가 가지고 있는 유일한 명령어인 OP_RETURN의 표시 함수는 다음과 같습니다.

static int simpleInstruction(const char* name, int offset) {
  printf("%s\n", name);
  return offset + 1;
}

반환 명령어에는 별다른 내용이 없으므로, Opcode의 이름만 출력한 다음 이 명령어 다음 바이트 오프셋을 반환합니다. 다른 명령어들은 더 많은 정보가 있을 것입니다.

지금 우리의 초보적인 인터프리터를 실행하면 실제로 다음과 같은 내용이 출력됩니다.

== test chunk ==
0000 OP_RETURN

성공했습니다! 이것이 우리 코드 표현의 일종의 "Hello, world!"입니다. 우리는 덩어리를 만들고, 명령어를 쓰고, 그 명령어를 다시 추출할 수 있습니다. 이진 바이트코드의 인코딩 및 디코딩이 작동하고 있습니다.

14 . 5상수

이제 기본적인 덩어리 구조가 작동하므로, 더 유용하게 만들어 봅시다. 덩어리에 코드를 저장할 수 있지만, 데이터는 어떻게 할까요? 인터프리터가 작동하는 많은 값들은 연산의 결과로 런타임에 생성됩니다.

1 + 2;

여기 코드 어디에도 값 3은 나타나지 않습니다. 하지만 리터럴 1과 2는 나타납니다. 이 문장을 바이트코드로 컴파일하려면 "상수를 생성하라"는 의미의 어떤 명령어가 필요하며, 그 리터럴 값들은 덩어리의 어딘가에 저장되어야 합니다. jlox에서는 Expr.Literal AST 노드가 값을 가지고 있었습니다. 구문 트리가 없는 지금은 다른 해결책이 필요합니다.

14 . 5 . 1값 표현

이 장에서는 코드를 실행하지는 않겠지만, 상수는 인터프리터의 정적 및 동적 세계 양쪽에 발을 걸치고 있기 때문에, 우리 VM이 값을 어떻게 표현해야 할지에 대해 최소한 약간은 생각하기 시작해야 합니다.

지금은 가능한 한 간단하게 시작할 것입니다—오직 배정밀도 부동 소수점 숫자만 지원할 것입니다. 이것은 시간이 지남에 따라 분명히 확장될 것이므로, 우리가 성장할 여지를 주기 위해 새로운 모듈을 설정할 것입니다.

#ifndef clox_value_h
#define clox_value_h

#include "common.h"

typedef double Value;

#endif

이 typedef는 Lox 값이 C에서 구체적으로 어떻게 표현되는지를 추상화합니다. 이 덕분에 우리는 값을 전달하는 기존 코드를 수정할 필요 없이 해당 표현을 변경할 수 있습니다.

다시 덩어리 내에 상수를 저장할 위치에 대한 질문으로 돌아가 봅시다. 정수와 같이 작고 고정된 크기의 값의 경우, 많은 명령어 집합은 Opcode 바로 다음에 코드 스트림에 값을 직접 저장합니다. 이러한 명령어들은 값의 비트가 Opcode 바로 뒤에 있기 때문에 즉시 명령어(immediate instructions)라고 불립니다.

이는 문자열과 같이 크거나 가변적인 상수에는 잘 작동하지 않습니다. 머신 코드로 컴파일하는 네이티브 컴파일러에서는 이러한 큰 상수들이 이진 실행 파일의 별도 "상수 데이터" 영역에 저장됩니다. 그런 다음, 상수를 로드하는 명령어는 그 섹션에 값이 저장된 위치를 가리키는 주소 또는 오프셋을 가집니다.

대부분의 가상 머신도 비슷하게 작동합니다. 예를 들어, Java 가상 머신은 각 컴파일된 클래스에 상수 풀(constant pool)을 연결합니다. clox에도 충분히 좋은 방법이라고 생각합니다. 각 덩어리는 프로그램의 리터럴로 나타나는 값들의 목록을 가지고 있을 것입니다. 더 간단하게 하기 위해, 모든 상수를, 심지어 단순한 정수도 거기에 넣을 것입니다.

14 . 5 . 2값 배열

상수 풀은 값들의 배열입니다. 상수를 로드하는 명령어는 그 배열에서 인덱스로 값을 찾습니다. 우리의 바이트코드 배열처럼, 컴파일러는 배열의 크기가 얼마인지 미리 알지 못합니다. 그래서 다시 한번, 동적 배열이 필요합니다. C는 제네릭 데이터 구조가 없으므로, 이번에는 `Value`를 위한 또 다른 동적 배열 데이터 구조를 작성할 것입니다.

typedef double Value;

typedef struct {
  int capacity;
  int count;
  Value* values;
} ValueArray;

#endif

Chunk의 바이트코드 배열과 마찬가지로, 이 구조체는 배열에 대한 포인터와 함께 할당된 용량 및 사용 중인 요소 수를 감싸고 있습니다. 또한 값 배열과 함께 작동하기 위한 동일한 세 가지 함수가 필요합니다.

} ValueArray;

void initValueArray(ValueArray* array);
void writeValueArray(ValueArray* array, Value value);
void freeValueArray(ValueArray* array);

#endif

구현은 아마도 데자뷔를 느끼게 할 것입니다. 먼저, 새로운 것을 생성하기 위해:

#include <stdio.h>

#include "memory.h"
#include "value.h"

void initValueArray(ValueArray* array) {
  array->values = NULL;
  array->capacity = 0;
  array->count = 0;
}

초기화된 배열을 갖게 되면, 이제 값을 추가하기 시작할 수 있습니다.

void writeValueArray(ValueArray* array, Value value) {
  if (array->capacity < array->count + 1) {
    int oldCapacity = array->capacity;
    array->capacity = GROW_CAPACITY(oldCapacity);
    array->values = GROW_ARRAY(Value, array->values,
                               oldCapacity, array->capacity);
  }

  array->values[array->count] = value;
  array->count++;
}

이전에 작성한 메모리 관리 매크로 덕분에 코드 배열의 일부 로직을 재사용할 수 있어서 그렇게 나쁘지 않습니다. 마지막으로 배열이 사용한 모든 메모리를 해제하려면 다음을 수행합니다.

void freeValueArray(ValueArray* array) {
  FREE_ARRAY(Value, array->values, array->capacity);
  initValueArray(array);
}

이제 동적 크기의 값 배열이 있으므로, 덩어리의 상수를 저장하기 위해 Chunk에 하나를 추가할 수 있습니다.

  uint8_t* code;

  ValueArray constants;

} Chunk;

include하는 것을 잊지 마세요.

#include "common.h"

#include "value.h"

typedef enum {

아, C, 그리고 그 석기 시대 모듈화 이야기. 어디까지 했었죠? 맞아요. 새로운 덩어리를 초기화할 때, 그 상수 목록도 초기화합니다.

  chunk->code = NULL;

  initValueArray(&chunk->constants);

}

마찬가지로, 덩어리를 해제할 때 상수를 해제합니다.

  FREE_ARRAY(uint8_t, chunk->code, chunk->capacity);

  freeValueArray(&chunk->constants);

  initChunk(chunk);

다음으로, 덩어리에 새 상수를 추가하는 편리한 메서드를 정의합니다. 아직 작성되지 않은 컴파일러는 Chunk 내부의 상수 배열에 직접 쓸 수 있습니다—C에는 private 필드 같은 것이 없으므로—하지만 명시적인 함수를 추가하는 것이 조금 더 좋습니다.

void writeChunk(Chunk* chunk, uint8_t byte);

int addConstant(Chunk* chunk, Value value);

#endif

그리고 구현합니다.

int addConstant(Chunk* chunk, Value value) {
  writeValueArray(&chunk->constants, value);
  return chunk->constants.count - 1;
}

상수를 추가한 후, 상수가 추가된 인덱스를 반환하여 나중에 그 상수를 찾을 수 있도록 합니다.

14 . 5 . 3상수 명령어

덩어리에 상수를 저장할 수 있지만, 상수를 실행할 수도 있어야 합니다. 다음과 같은 코드에서:

print 1;
print 2;

컴파일된 덩어리는 값 1과 2를 포함할 뿐만 아니라, 언제 그 값들을 생성해야 올바른 순서로 출력될지 알아야 합니다. 따라서 특정 상수를 생성하는 명령어가 필요합니다.

typedef enum {

  OP_CONSTANT,

  OP_RETURN,

VM이 상수 명령어를 실행하면, 사용을 위해 상수를 "로드"합니다. 이 새로운 명령어는 OP_RETURN보다 약간 더 복잡합니다. 위 예시에서는 두 개의 다른 상수를 로드합니다. 단일 Opcode만으로는 어떤 상수를 로드해야 할지 알기 어렵습니다.

이러한 경우를 처리하기 위해, 우리의 바이트코드는—대부분의 다른 바이트코드처럼—명령어가 오퍼랜드(operands)를 가질 수 있도록 합니다. 오퍼랜드는 명령어 스트림의 Opcode 바로 뒤에 이진 데이터로 저장되며, 명령어의 동작을 매개변수화할 수 있게 합니다.

각 Opcode는 몇 개의 오퍼랜드 바이트를 가지며, 그것들이 무엇을 의미하는지 결정합니다. 예를 들어, "반환"과 같은 간단한 연산에는 오퍼랜드가 없을 수 있지만, "지역 변수 로드" 명령어는 어떤 변수를 로드할지 식별하기 위한 오퍼랜드를 필요로 합니다. clox에 새로운 Opcode를 추가할 때마다, 우리는 그 오퍼랜드가 어떻게 생겼는지—즉, 명령어 형식(instruction format)을 지정합니다.

이 경우, OP_CONSTANT는 덩어리의 상수 배열에서 로드할 상수를 지정하는 단일 바이트 오퍼랜드를 가집니다. 아직 컴파일러가 없으므로, 테스트 덩어리에서 명령어를 "수동으로 컴파일"합니다.

  initChunk(&chunk);

  int constant = addConstant(&chunk, 1.2);
  writeChunk(&chunk, OP_CONSTANT);
  writeChunk(&chunk, constant);

  writeChunk(&chunk, OP_RETURN);

우리는 상수 값 자체를 덩어리의 상수 풀에 추가합니다. 이는 배열 내 상수의 인덱스를 반환합니다. 그런 다음 상수 명령어를 작성하는데, Opcode로 시작합니다. 그 후, 1바이트 상수 인덱스 오퍼랜드를 작성합니다. writeChunk()는 Opcode나 오퍼랜드를 모두 작성할 수 있다는 점에 유의하세요. 이 함수에게는 모두 원시 바이트일 뿐입니다.

지금 이 코드를 실행하려고 하면, 역어셈블러가 새로운 명령어를 디코딩하는 방법을 모르기 때문에 오류를 낼 것입니다. 이를 수정해 봅시다.

  switch (instruction) {

    case OP_CONSTANT:
      return constantInstruction("OP_CONSTANT", chunk, offset);

    case OP_RETURN:

이 명령어는 명령어 형식이 다르므로, 이를 역어셈블하는 새로운 헬퍼 함수를 작성합니다.

static int constantInstruction(const char* name, Chunk* chunk,
                               int offset) {
  uint8_t constant = chunk->code[offset + 1];
  printf("%-16s %4d '", name, constant);
  printValue(chunk->constants.values[constant]);
  printf("'\n");
}

여기서는 더 많은 작업이 진행됩니다. OP_RETURN과 마찬가지로, Opcode의 이름을 출력합니다. 그런 다음 덩어리의 다음 바이트에서 상수 인덱스를 추출합니다. 그 인덱스를 출력하지만, 이는 우리 인간 독자들에게는 그다지 유용하지 않습니다. 따라서 실제 상수 값도 찾아—결국 상수는 컴파일 시간에 알려져 있으므로—값 자체를 표시합니다.

이를 위해서는 clox `Value`를 출력하는 방법이 필요합니다. 이 함수는 "value" 모듈에 포함될 것이므로, 해당 모듈을 include합니다.

#include "debug.h"

#include "value.h"

void disassembleChunk(Chunk* chunk, const char* name) {

해당 헤더 파일에 다음을 선언합니다.

void freeValueArray(ValueArray* array);

void printValue(Value value);

#endif

그리고 다음은 구현입니다.

void printValue(Value value) {
  printf("%g", value);
}

멋지죠? 예상하시겠지만, Lox에 동적 타이핑을 추가하고 다양한 타입의 값을 갖게 되면 이것은 더욱 복잡해질 것입니다.

constantInstruction()으로 돌아가서, 남아있는 유일한 부분은 반환 값입니다.

  printf("'\n");

  return offset + 2;

}

disassembleInstruction()은 호출자에게 다음 명령어 시작 오프셋을 알려주는 숫자를 반환한다는 것을 기억하세요. OP_RETURN은 단일 바이트였지만, OP_CONSTANT는 Opcode용 1바이트와 오퍼랜드용 1바이트로 총 2바이트입니다.

14 . 6라인 정보

덩어리에는 런타임이 사용자 소스 코드에서 필요로 하는 거의 모든 정보가 들어 있습니다. jlox에서 생성했던 모든 AST 클래스를 바이트 배열과 상수 배열로 줄일 수 있다는 것은 정말 놀랍습니다. 이제 단 하나의 데이터 조각만 빠져 있습니다. 사용자 입장에서는 절대 보고 싶지 않은 것이지만, 우리에게는 필요합니다.

런타임 오류가 발생하면, 사용자에게 문제 소스 코드의 줄 번호를 표시합니다. jlox에서는 이 번호들이 토큰에 저장되었고, 우리는 이 토큰들을 AST 노드에 저장했습니다. 바이트코드를 선호하여 구문 트리를 버린 clox에서는 다른 해결책이 필요합니다. 어떤 바이트코드 명령어든 주어지면, 그것이 컴파일된 사용자 소스 프로그램의 줄을 결정할 수 있어야 합니다.

이를 인코딩할 수 있는 영리한 방법이 많이 있습니다. 저는 메모리 측면에서 부끄럽게도 비효율적임에도 불구하고, 제가 생각해낼 수 있는 가장 간단한 접근 방식을 취했습니다. 덩어리 안에 바이트코드와 병렬로 별도의 정수 배열을 저장합니다. 배열의 각 숫자는 바이트코드의 해당 바이트에 대한 줄 번호입니다. 런타임 오류가 발생하면, 코드 배열에서 현재 명령어의 오프셋과 동일한 인덱스에 있는 줄 번호를 찾습니다.

이를 구현하기 위해 Chunk에 또 다른 배열을 추가합니다.

  uint8_t* code;

  int* lines;

  ValueArray constants;

바이트코드 배열과 정확히 병렬이므로 별도의 count나 capacity가 필요하지 않습니다. code 배열을 건드릴 때마다, 초기화를 포함하여 lines 배열에도 해당 변경을 가합니다.

  chunk->code = NULL;

  chunk->lines = NULL;

  initValueArray(&chunk->constants);

마찬가지로 할당 해제도 다음과 같습니다.

  FREE_ARRAY(uint8_t, chunk->code, chunk->capacity);

  FREE_ARRAY(int, chunk->lines, chunk->capacity);

  freeValueArray(&chunk->constants);

덩어리에 코드 바이트를 쓸 때, 그것이 어떤 소스 라인에서 왔는지 알아야 하므로, writeChunk() 선언에 추가 매개변수를 추가합니다.

void freeChunk(Chunk* chunk);

void writeChunk(Chunk* chunk, uint8_t byte, int line);

int addConstant(Chunk* chunk, Value value);

그리고 구현에서:

void writeChunk(Chunk* chunk, uint8_t byte, int line) {

  if (chunk->capacity < chunk->count + 1) {

코드 배열을 할당하거나 확장할 때, 줄 정보도 똑같이 처리합니다.

    chunk->code = GROW_ARRAY(uint8_t, chunk->code,
        oldCapacity, chunk->capacity);

    chunk->lines = GROW_ARRAY(int, chunk->lines,
        oldCapacity, chunk->capacity);

  }

마지막으로, 줄 번호를 배열에 저장합니다.

  chunk->code[chunk->count] = byte;

  chunk->lines[chunk->count] = line;

  chunk->count++;

14 . 6 . 1라인 정보 역어셈블링

자, 이제 우리의 작은, 음, 수공예 덩어리로 이것을 시험해 봅시다. 먼저, writeChunk()에 새 매개변수를 추가했으므로, 해당 호출들을 수정하여—이 시점에서는 임의의—줄 번호를 전달해야 합니다.

  int constant = addConstant(&chunk, 1.2);

  writeChunk(&chunk, OP_CONSTANT, 123);
  writeChunk(&chunk, constant, 123);

  writeChunk(&chunk, OP_RETURN, 123);

  disassembleChunk(&chunk, "test chunk");

물론, 실제 프론트엔드가 생기면 컴파일러가 파싱하면서 현재 라인을 추적하고 그것을 전달할 것입니다.

이제 모든 명령어에 대한 줄 정보가 있으니, 이를 잘 활용해 봅시다. 역어셈블러에서는 각 명령어가 어떤 소스 줄에서 컴파일되었는지 보여주는 것이 유용합니다. 이는 바이트코드 덩어리가 무엇을 해야 하는지 파악하려고 할 때 원본 코드로 다시 매핑하는 방법을 제공합니다. 명령어의 오프셋—덩어리 시작부터의 바이트 수—를 출력한 후, 그 소스 줄을 보여줍니다.

int disassembleInstruction(Chunk* chunk, int offset) {
  printf("%04d ", offset);

  if (offset > 0 &&
      chunk->lines[offset] == chunk->lines[offset - 1]) {
    printf("   | ");
  } else {
    printf("%4d ", chunk->lines[offset]);
  }

  uint8_t instruction = chunk->code[offset];

바이트코드 명령어는 매우 세밀한 경향이 있습니다. 하나의 소스 코드 라인은 종종 일련의 명령어 전체로 컴파일됩니다. 이를 시각적으로 더 명확하게 하기 위해, 이전 명령어와 동일한 소스 라인에서 온 모든 명령어에 대해 |를 표시합니다. 수동으로 작성된 덩어리에 대한 결과 출력은 다음과 같습니다.

== test chunk ==
0000  123 OP_CONSTANT         0 '1.2'
0002    | OP_RETURN

우리는 3바이트 덩어리를 가지고 있습니다. 처음 두 바이트는 덩어리의 상수 풀에서 1.2를 로드하는 상수 명령어입니다. 첫 번째 바이트는 OP_CONSTANT Opcode이고, 두 번째 바이트는 상수 풀의 인덱스입니다. 세 번째 바이트(오프셋 2)는 단일 바이트 반환 명령어입니다.

남은 장들에서는 훨씬 더 많은 종류의 명령어로 이것을 채울 것입니다. 하지만 기본적인 구조는 여기에 있으며, 이제 가상 머신에서 런타임에 실행 가능한 코드 조각을 완벽하게 표현하는 데 필요한 모든 것을 갖추었습니다. jlox에서 정의했던 모든 AST 클래스들을 기억하시나요? clox에서는 그것들을 세 개의 배열로 줄였습니다: 코드 바이트, 상수 값, 그리고 디버깅을 위한 라인 정보입니다.

이러한 축소는 우리의 새로운 인터프리터가 jlox보다 빠를 주요 이유입니다. 바이트코드는 AST의 일종의 압축 직렬화로 생각할 수 있으며, 인터프리터가 실행하면서 필요한 순서대로 역직렬화하는 방식에 매우 최적화되어 있습니다. 다음 장에서 가상 머신이 정확히 어떻게 그것을 수행하는지 살펴볼 것입니다.