클로저

그가 말했듯이, 모든 복잡한 문제에는 간단한 해결책이 있고, 그 해결책은 틀렸다.

움베르토 에코, 푸코의 진자

지난 장에서 열심히 작업한 덕분에, 우리는 함수가 작동하는 가상 머신을 갖게 되었습니다. 하지만 클로저(closure)는 아직 부족합니다. 전역 변수(이것은 특별한 종류의 변수입니다)를 제외하고는, 함수는 자기 자신의 본문 밖에 선언된 변수를 참조할 방법이 없습니다.

var x = "global";
fun outer() {
  var x = "outer";
  fun inner() {
    print x;
  }
  inner();
}
outer();

이 예제를 지금 실행하면 "global"이 출력됩니다. 원래는 "outer"가 출력되어야 합니다. 이를 수정하려면 변수를 해석할 때 모든 주변 함수의 전체 렉시컬 스코프를 포함해야 합니다.

이 문제는 바이트코드 VM이 지역 변수를 스택에 저장하기 때문에 jlox에서보다 clox에서 더 어렵습니다. 제가 지역 변수는 스택 의미론(변수는 생성된 역순으로 폐기됨)을 가진다고 주장했기 때문에 스택을 사용했습니다. 하지만 클로저의 경우, 이것은 거의 맞습니다.

fun makeClosure() {
  var local = "local";
  fun closure() {
    print local;
  }
  return closure;
}

var closure = makeClosure();
closure();

바깥 함수인 makeClosure()는 변수 local을 선언합니다. 또한 이 변수를 포획(capture)하는 내부 함수 closure()를 생성합니다. 그리고 makeClosure()는 그 함수에 대한 참조를 반환합니다. 클로저가 지역 변수를 붙잡고 있는 채로 탈출하기 때문에, local은 생성된 함수 호출보다 더 오래 살아남아야 합니다.

이 문제는 모든 지역 변수에 동적으로 메모리를 할당함으로써 해결할 수 있습니다. jlox가 Java 힙에 떠다니는 Environment 객체에 모든 것을 넣음으로써 그렇게 했습니다. 하지만 우리는 그렇게 하고 싶지 않습니다. 스택을 사용하는 것은 정말 빠릅니다. 대부분의 지역 변수는 클로저에 의해 포획되지 않고 스택 의미론을 가집니다. 포획되는 드문 지역 변수를 위해 모든 것을 느리게 만드는 것은 좋지 않을 것입니다.

이는 우리 Java 인터프리터에서 사용했던 것보다 더 복잡한 접근 방식이 필요하다는 의미입니다. 일부 지역 변수는 수명이 매우 다르기 때문에 두 가지 구현 전략을 가질 것입니다. 클로저에서 사용되지 않는 지역 변수는 스택에 그대로 유지합니다. 지역 변수가 클로저에 의해 포획되면, 필요할 때까지 힙에 올리는 다른 해결책을 채택할 것입니다.

클로저는 메모리 바이트와 CPU 사이클이 에메랄드보다 더 귀했던 초기 Lisp 시절부터 존재해 왔습니다. 수십 년 동안 해커들은 클로저를 최적화된 런타임 표현으로 컴파일하는 모든 방법을 고안했습니다. 일부는 더 효율적이지만, 우리가 clox에 쉽게 적용하기에는 너무 복잡한 컴파일 과정을 요구합니다.

여기서 설명할 기술은 Lua VM의 설계에서 비롯되었습니다. 빠르고, 메모리를 절약하며, 상대적으로 적은 코드로 구현됩니다. 더욱 인상적인 것은, clox와 Lua 모두 사용하는 단일 패스 컴파일러에 자연스럽게 들어맞는다는 점입니다. 하지만 다소 복잡합니다. 모든 조각이 여러분의 머릿속에서 맞춰지는 데 시간이 좀 걸릴 수 있습니다. 우리는 하나씩 단계를 밟아 나갈 것이고, 개념들을 단계별로 소개하려고 노력할 것입니다.

25 . 1클로저 객체

우리 VM은 런타임에 ObjFunction을 사용하여 함수를 나타냅니다. 이 객체들은 컴파일 중에 프론트엔드에 의해 생성됩니다. 런타임에 VM이 하는 일은 상수 테이블에서 함수 객체를 로드하고 이를 이름에 바인딩하는 것뿐입니다. 런타임에 함수를 "생성"하는 작업은 없습니다. 문자열 및 숫자 리터럴과 마찬가지로, 함수는 순전히 컴파일 시간에 인스턴스화되는 상수입니다.

이는 함수를 구성하는 모든 데이터가 컴파일 시간에 알려져 있기 때문에 합리적이었습니다. 함수의 본문에서 컴파일된 바이트코드 덩어리와 본문에서 사용된 상수들 말이죠. 하지만 클로저를 도입하면 이러한 표현으로는 더 이상 충분하지 않습니다. 다음을 살펴보세요.

fun makeClosure(value) {
  fun closure() {
    print value;
  }
  return closure;
}

var doughnut = makeClosure("doughnut");
var bagel = makeClosure("bagel");
doughnut();
bagel();

makeClosure() 함수는 함수를 정의하고 반환합니다. 우리는 이 함수를 두 번 호출하여 두 개의 클로저를 얻습니다. 이 클로저들은 동일한 중첩 함수 선언인 closure에 의해 생성되지만, 서로 다른 값들을 포획합니다. 두 클로저를 호출하면 각각 다른 문자열을 출력합니다. 이는 함수 선언이 실행될 때 존재하는 주변 지역 변수들을 포획하는 런타임 표현이 필요하며, 단순히 컴파일될 때가 아니라는 것을 의미합니다.

변수 포획으로 나아가기 전에, 좋은 첫 단계는 객체 표현을 정의하는 것입니다. 우리의 기존 ObjFunction 타입은 함수 선언의 "원시" 컴파일 시간 상태를 나타냅니다. 단일 선언에서 생성된 모든 클로저는 동일한 코드와 상수를 공유하기 때문입니다. 런타임에 함수 선언을 실행할 때, ObjFunction을 새로운 ObjClosure 구조체로 감쌉니다. 후자는 기본 함수에 대한 참조와 함수가 닫히는 변수들에 대한 런타임 상태를 가집니다.

함수가 실제로 주변 지역 변수를 닫고 포획하지 않더라도 모든 함수를 ObjClosure로 감쌀 것입니다. 이것은 약간 낭비이지만, 우리가 항상 호출하는 함수가 ObjClosure라고 가정할 수 있으므로 VM을 단순화합니다. 이 새로운 구조체는 다음과 같이 시작합니다:

typedef struct {
  Obj obj;
  ObjFunction* function;
} ObjClosure;

지금은 단순히 ObjFunction을 가리키고 필요한 객체 헤더 정보를 추가합니다. clox에 새로운 객체 타입을 추가하기 위한 일반적인 절차에 따라, 새로운 클로저를 생성하는 C 함수를 선언합니다.

} ObjClosure;

ObjClosure* newClosure(ObjFunction* function);

ObjFunction* newFunction();

그리고 여기에서 구현합니다:

ObjClosure* newClosure(ObjFunction* function) {
  ObjClosure* closure = ALLOCATE_OBJ(ObjClosure, OBJ_CLOSURE);
  closure->function = function;
  return closure;
}

이 함수는 감싸는 ObjFunction에 대한 포인터를 인자로 받습니다. 또한 타입 필드를 새로운 타입으로 초기화합니다.

typedef enum {

  OBJ_CLOSURE,

  OBJ_FUNCTION,

그리고 클로저 사용이 끝나면 메모리를 해제합니다.

  switch (object->type) {

    case OBJ_CLOSURE: {
      FREE(ObjClosure, object);
      break;
    }

    case OBJ_FUNCTION: {

ObjClosure 자체만 해제하고 ObjFunction은 해제하지 않습니다. 이는 클로저가 함수를 소유하지 않기 때문입니다. 동일한 함수를 참조하는 여러 클로저가 있을 수 있으며, 그 어떤 클로저도 함수에 대한 특별한 권한을 주장하지 않습니다. 함수를 참조하는 모든 객체가 사라질 때까지(심지어 상수 테이블에 함수가 포함된 주변 함수까지 포함하여) ObjFunction을 해제할 수 없습니다. 이를 추적하는 것은 까다롭게 들리는데, 실제로 그렇습니다! 그래서 우리는 곧 가비지 컬렉터를 작성하여 이를 관리할 것입니다.

또한, 값의 타입을 확인하는 일반적인 매크로도 있습니다.

#define OBJ_TYPE(value)        (AS_OBJ(value)->type)

#define IS_CLOSURE(value)      isObjType(value, OBJ_CLOSURE)

#define IS_FUNCTION(value)     isObjType(value, OBJ_FUNCTION)

그리고 값을 캐스팅하기 위해:

#define IS_STRING(value)       isObjType(value, OBJ_STRING)

#define AS_CLOSURE(value)      ((ObjClosure*)AS_OBJ(value))

#define AS_FUNCTION(value)     ((ObjFunction*)AS_OBJ(value))

클로저는 일급 객체이므로 출력할 수 있습니다.

  switch (OBJ_TYPE(value)) {

    case OBJ_CLOSURE:
      printFunction(AS_CLOSURE(value)->function);
      break;

    case OBJ_FUNCTION:

이들은 ObjFunction과 똑같이 표시됩니다. 사용자 관점에서 ObjFunction과 ObjClosure의 차이는 순전히 숨겨진 구현 세부 사항입니다. 이제 작업 가능하지만 비어 있는 클로저 표현을 갖게 되었습니다.

25 . 1 . 1클로저 객체로 컴파일하기

우리는 클로저 객체를 가지고 있지만, VM은 결코 이들을 생성하지 않습니다. 다음 단계는 컴파일러가 주어진 ObjFunction을 감싸는 새로운 ObjClosure를 언제 생성해야 하는지 런타임에 지시하는 명령어를 내보내도록 하는 것입니다. 이는 함수 선언의 끝 부분에서 발생합니다.

  ObjFunction* function = endCompiler();

  emitBytes(OP_CLOSURE, makeConstant(OBJ_VAL(function)));

}

이전에는 함수 선언의 최종 바이트코드는 컴파일된 함수를 주변 함수의 상수 테이블에서 로드하여 스택에 푸시하는 단일 OP_CONSTANT 명령어였습니다. 이제 새로운 명령어가 있습니다.

  OP_CALL,

  OP_CLOSURE,

  OP_RETURN,

OP_CONSTANT와 마찬가지로, 함수에 대한 상수 테이블 인덱스를 나타내는 단일 피연산자를 받습니다. 하지만 런타임 구현으로 넘어가면 더 흥미로운 작업을 수행합니다.

먼저, 부지런한 VM 해커답게 명령어에 대한 디스어셈블러 지원을 추가합시다.

    case OP_CALL:
      return byteInstruction("OP_CALL", chunk, offset);

    case OP_CLOSURE: {
      offset++;
      uint8_t constant = chunk->code[offset++];
      printf("%-16s %4d ", "OP_CLOSURE", constant);
      printValue(chunk->constants.values[constant]);
      printf("\n");
      return offset;
    }

    case OP_RETURN:

여기에는 디스어셈블러에서 일반적으로 볼 수 있는 것보다 더 많은 것이 있습니다. 이 장의 끝에 가면 OP_CLOSURE가 꽤 특이한 명령어라는 것을 알게 될 것입니다. 지금은 간단합니다(단일 바이트 피연산자만 사용합니다), 하지만 앞으로 추가될 것입니다. 이 코드는 미래를 예상한 것입니다.

25 . 1 . 2함수 선언 해석하기

우리가 해야 할 대부분의 작업은 런타임에 있습니다. 당연히 새로운 명령어를 처리해야 합니다. 하지만 VM에서 ObjFunction을 사용하는 모든 코드 조각을 ObjClosure를 사용하도록 변경해야 합니다. 함수 호출, 호출 프레임 등 말이죠. 먼저 명령어부터 시작하겠습니다.

      }

      case OP_CLOSURE: {
        ObjFunction* function = AS_FUNCTION(READ_CONSTANT());
        ObjClosure* closure = newClosure(function);
        push(OBJ_VAL(closure));
        break;
      }

      case OP_RETURN: {

이전에 사용했던 OP_CONSTANT 명령어처럼, 먼저 컴파일된 함수를 상수 테이블에서 로드합니다. 이제 달라진 점은 해당 함수를 새로운 ObjClosure로 감싸고 결과를 스택에 푸시한다는 것입니다.

클로저를 얻었다면 결국에는 호출하고 싶을 것입니다.

    switch (OBJ_TYPE(callee)) {

      case OBJ_CLOSURE:
        return call(AS_CLOSURE(callee), argCount);

      case OBJ_NATIVE: {

OBJ_FUNCTION 타입의 객체를 호출하는 코드를 제거합니다. 모든 함수를 ObjClosure로 감싸므로, 런타임은 더 이상 '벌거벗은' ObjFunction을 호출하려고 시도하지 않을 것입니다. 이 객체들은 상수 테이블에만 존재하며, 다른 어떤 것이 이들을 보기 전에 즉시 클로저로 감싸집니다.

기존 코드를 대신 클로저를 호출하는 매우 유사한 코드로 대체합니다. 유일한 차이점은 call()에 전달하는 객체 타입입니다. 실제 변경 사항은 해당 함수에 있습니다. 먼저, 함수의 시그니처를 업데이트합니다.

static bool call(ObjClosure* closure, int argCount) {

  if (argCount != function->arity) {

그런 다음, 본문에서 함수를 참조하던 모든 것을 간접 계층을 도입했음을 처리하도록 수정해야 합니다. 인자 개수 확인부터 시작합니다.

static bool call(ObjClosure* closure, int argCount) {

  if (argCount != closure->function->arity) {
    runtimeError("Expected %d arguments but got %d.",
        closure->function->arity, argCount);

    return false;

변경된 내용은 클로저를 풀어서 기본 함수를 얻는 것뿐입니다. call()이 다음에 하는 일은 새 CallFrame을 생성하는 것입니다. 해당 코드를 변경하여 클로저를 CallFrame에 저장하고, 클로저의 함수에서 바이트코드 포인터를 가져오도록 합니다.

  CallFrame* frame = &vm.frames[vm.frameCount++];

  frame->closure = closure;
  frame->ip = closure->function->chunk.code;

  frame->slots = vm.stackTop - argCount - 1;

이러한 변경으로 CallFrame의 선언도 수정해야 합니다.

typedef struct {

  ObjClosure* closure;

  uint8_t* ip;

이 변경은 몇 가지 다른 연쇄적인 변경을 유발합니다. VM에서 CallFrame의 함수에 접근했던 모든 곳은 이제 대신 클로저를 사용해야 합니다. 먼저, 현재 함수의 상수 테이블에서 상수를 읽기 위한 매크로입니다.

    (uint16_t)((frame->ip[-2] << 8) | frame->ip[-1]))

#define READ_CONSTANT() \
    (frame->closure->function->chunk.constants.values[READ_BYTE()])

#define READ_STRING() AS_STRING(READ_CONSTANT())

DEBUG_TRACE_EXECUTION이 활성화되면, 클로저에서 청크에 접근해야 합니다.

    printf("\n");

    disassembleInstruction(&frame->closure->function->chunk,
        (int)(frame->ip - frame->closure->function->chunk.code));

#endif

마찬가지로 런타임 오류를 보고할 때도:

    CallFrame* frame = &vm.frames[i];

    ObjFunction* function = frame->closure->function;

    size_t instruction = frame->ip - function->chunk.code - 1;

거의 다 왔습니다. 마지막 부분은 Lox 스크립트의 최상위 코드 실행을 시작하기 위해 첫 번째 CallFrame을 설정하는 코드 블록입니다.

  push(OBJ_VAL(function));

  ObjClosure* closure = newClosure(function);
  pop();
  push(OBJ_VAL(closure));
  call(closure, 0);

  return run();

컴파일러는 스크립트를 컴파일할 때 여전히 원시 ObjFunction을 반환합니다. 그것은 괜찮지만, VM이 실행하기 전에 여기서 ObjClosure로 감쌀 필요가 있다는 것을 의미합니다.

우리는 이제 작동하는 인터프리터로 돌아왔습니다. 사용자는 어떤 차이도 알 수 없지만, 컴파일러는 이제 VM에게 각 함수 선언에 대해 클로저를 생성하도록 지시하는 코드를 생성합니다. VM이 함수 선언을 실행할 때마다 ObjFunction을 새로운 ObjClosure로 감쌉니다. 이제 VM의 나머지 부분은 이 ObjClosure들을 처리합니다. 지루한 부분은 끝났습니다. 이제 이 클로저들이 실제로 무언가를 하도록 만들 준비가 되었습니다.

25 . 2업밸류

지역 변수를 읽고 쓰는 기존 명령어는 단일 함수의 스택 창으로 제한됩니다. 주변 함수의 지역 변수는 내부 함수의 스택 창 밖에 있습니다. 새로운 명령어가 필요할 것입니다.

가장 쉬운 접근 방식은 현재 함수의 스택 창 이전에 도달할 수 있는 상대 스택 슬롯 오프셋을 취하는 명령어일 수 있습니다. 이는 닫힌 변수가 항상 스택에 있다면 작동할 것입니다. 그러나 앞서 보았듯이, 이러한 변수들은 때때로 선언된 함수보다 더 오래 살아남습니다. 이는 항상 스택에 있지 않을 것이라는 의미입니다.

clox가 단일 패스 컴파일러를 가지고 있지 않다면 이것은 좋은 접근 방식이었을 것입니다. 하지만 우리가 구현에서 선택한 제약 조건 때문에 상황이 더 어려워집니다. 이 예제를 살펴보세요.

fun outer() {
  var x = 1;    // (1)
  x = 2;        // (2)
  fun inner() { // (3)
    print x;
  }
  inner();
}

여기서 컴파일러는 (1)에서 x의 선언을 컴파일하고 (2)에서 할당을 위한 코드를 내보냅니다. 이 작업은 (3)에서 inner()의 선언에 도달하여 x가 실제로 클로저에 의해 닫힌다는 것을 발견하기 전에 이루어집니다. 이미 내보낸 코드를 다시 변경하여 x를 특별하게 처리하도록 하는 쉬운 방법은 없습니다. 대신, 닫힌 변수가 일반 지역 변수처럼 스택에 포획될 때까지 정확히 스택에 있도록 허용하는 해결책을 원합니다.

다행히 Lua 개발팀 덕분에 해결책을 찾았습니다. 우리는 그들이 업밸류(upvalue)라고 부르는 간접 계층을 사용합니다. 업밸류는 둘러싸는 함수에 있는 지역 변수를 참조합니다. 모든 클로저는 업밸류 배열을 유지하며, 클로저가 사용하는 각 주변 지역 변수에 대해 하나씩 가집니다.

업밸류는 포획된 변수가 존재하는 스택 위치를 가리킵니다. 클로저가 닫힌 변수에 접근해야 할 때, 해당 업밸류를 통해 접근합니다. 함수 선언이 처음 실행되고 클로저를 생성할 때, VM은 업밸류 배열을 생성하고 클로저가 필요한 주변 지역 변수들을 "포획"하도록 연결합니다.

예를 들어, 이 프로그램을 clox에 넣으면,

{
  var a = 3;
  fun f() {
    print a;
  }
}

컴파일러와 런타임은 협력하여 메모리에 다음과 같은 객체 집합을 구성할 것입니다:

압도적으로 보일 수 있지만, 걱정하지 마세요. 하나씩 해결해 나갈 것입니다. 중요한 부분은 업밸류가 스택에서 이동한 후에도 포획된 지역 변수를 계속 찾을 수 있도록 필요한 간접 계층 역할을 한다는 것입니다. 하지만 그 모든 것에 도달하기 전에, 포획된 변수를 컴파일하는 데 집중합시다.

25 . 2 . 1업밸류 컴파일하기

평소와 같이, 실행을 간단하고 빠르게 유지하기 위해 컴파일 중에 가능한 한 많은 작업을 하고 싶습니다. Lox에서 지역 변수는 렉시컬 스코프를 가지므로, 컴파일 시간에 함수가 어떤 주변 지역 변수에 접근하고 그 지역 변수들이 어디에 선언되었는지 해결할 충분한 정보가 있습니다. 이는 클로저가 얼마나 많은 업밸류가 필요한지, 어떤 변수들을 포획하는지, 그리고 해당 변수들이 선언된 함수의 스택 창에 있는 어떤 스택 슬롯에 포함되어 있는지 알 수 있다는 것을 의미합니다.

현재 컴파일러가 식별자를 해석할 때, 현재 함수의 블록 스코프를 가장 안쪽에서 바깥쪽으로 순회합니다. 해당 함수에서 변수를 찾지 못하면, 변수가 전역 변수라고 가정합니다. 둘러싸는 함수의 지역 스코프는 고려하지 않습니다. 즉, 건너뛰는 것입니다. 따라서 첫 번째 변경 사항은 외부 지역 스코프에 대한 해석 단계를 삽입하는 것입니다.

  if (arg != -1) {
    getOp = OP_GET_LOCAL;
    setOp = OP_SET_LOCAL;

  } else if ((arg = resolveUpvalue(current, &name)) != -1) {
    getOp = OP_GET_UPVALUE;
    setOp = OP_SET_UPVALUE;

  } else {

이 새로운 resolveUpvalue() 함수는 둘러싸는 함수 중 하나에 선언된 지역 변수를 찾습니다. 만약 찾으면, 해당 변수에 대한 "업밸류 인덱스"를 반환합니다. (이것이 무엇을 의미하는지는 나중에 자세히 다루겠습니다.) 그렇지 않으면, 변수를 찾지 못했음을 나타내기 위해 -1을 반환합니다. 변수가 발견되면, 해당 업밸류를 통해 변수를 읽거나 쓰기 위해 이 두 가지 새로운 명령어를 사용합니다.

  OP_SET_GLOBAL,

  OP_GET_UPVALUE,
  OP_SET_UPVALUE,

  OP_EQUAL,

이것을 상향식으로 구현하고 있으므로, 이들이 런타임에 어떻게 작동하는지 곧 보여드리겠습니다. 지금 집중해야 할 부분은 컴파일러가 실제로 식별자를 해석하는 방법입니다.

static int resolveUpvalue(Compiler* compiler, Token* name) {
  if (compiler->enclosing == NULL) return -1;

  int local = resolveLocal(compiler->enclosing, name);
  if (local != -1) {
    return addUpvalue(compiler, (uint8_t)local, true);
  }

  return -1;
}

이것은 현재 함수의 스코프에서 지역 변수를 해석하는 데 실패한 후에 호출되므로, 변수가 현재 컴파일러에 없다는 것을 알고 있습니다. Compiler는 둘러싸는 함수에 대한 Compiler 포인터를 저장하며, 이 포인터들은 최상위 코드의 루트 Compiler까지 이어지는 연결된 체인을 형성합니다. 따라서 둘러싸는 Compiler가 NULL이면, 지역 변수를 찾지 않고 가장 바깥쪽 함수에 도달했다는 것을 알 수 있습니다. 변수는 전역이어야 하므로, -1을 반환합니다.

그렇지 않으면, 식별자를 둘러싸는 컴파일러의 지역 변수로 해석하려고 시도합니다. 다시 말해, 현재 함수 바로 바깥에서 찾습니다. 예를 들어:

fun outer() {
  var x = 1;
  fun inner() {
    print x; // (1)
  }
  inner();
}

(1)의 식별자 표현식을 컴파일할 때, resolveUpvalue()는 outer()에 선언된 지역 변수 x를 찾습니다. 이 예제에서처럼 변수가 발견되면, 성공적으로 변수를 해석한 것입니다. 내부 함수가 이를 통해 변수에 접근할 수 있도록 업밸류를 생성합니다. 업밸류는 여기에서 생성됩니다.

static int addUpvalue(Compiler* compiler, uint8_t index,
                      bool isLocal) {
  int upvalueCount = compiler->function->upvalueCount;
  compiler->upvalues[upvalueCount].isLocal = isLocal;
  compiler->upvalues[upvalueCount].index = index;
  return compiler->function->upvalueCount++;
}

컴파일러는 각 함수의 본문에서 해결된 닫힌 식별자를 추적하기 위해 업밸류 구조체 배열을 유지합니다. 컴파일러의 Local 배열이 런타임에 지역 변수가 존재하는 스택 슬롯 인덱스를 반영했던 것을 기억하나요? 이 새로운 업밸류 배열도 동일하게 작동합니다. 컴파일러 배열의 인덱스는 런타임에 ObjClosure 내에 업밸류가 존재할 인덱스와 일치합니다.

이 함수는 해당 배열에 새로운 업밸류를 추가합니다. 또한 함수가 사용하는 업밸류의 개수도 추적합니다. 이 개수는 런타임에도 필요하기 때문에 ObjFunction 자체에 직접 저장합니다.

index 필드는 닫힌 지역 변수의 슬롯 인덱스를 추적합니다. 이를 통해 컴파일러는 둘러싸는 함수에서 어떤 변수가 포획되어야 하는지 알 수 있습니다. isLocal 필드의 용도는 곧 다시 다룰 것입니다. 마지막으로, addUpvalue()는 함수의 업밸류 목록에 새로 생성된 업밸류의 인덱스를 반환합니다. 이 인덱스는 OP_GET_UPVALUE 및 OP_SET_UPVALUE 명령어의 피연산자가 됩니다.

이것이 업밸류 해석의 기본 아이디어이지만, 함수는 완전히 완성되지 않았습니다. 클로저는 주변 함수에 있는 동일한 변수를 여러 번 참조할 수 있습니다. 이 경우, 각 식별자 표현식에 대해 별도의 업밸류를 생성하여 시간과 메모리를 낭비하고 싶지 않습니다. 이를 해결하기 위해, 새 업밸류를 추가하기 전에, 함수가 이미 해당 변수를 닫는 업밸류를 가지고 있는지 먼저 확인합니다.

  int upvalueCount = compiler->function->upvalueCount;

  for (int i = 0; i < upvalueCount; i++) {
    Upvalue* upvalue = &compiler->upvalues[i];
    if (upvalue->index == index && upvalue->isLocal == isLocal) {
      return i;
    }
  }

  compiler->upvalues[upvalueCount].isLocal = isLocal;

추가하려는 슬롯 인덱스와 일치하는 업밸류를 배열에서 찾으면, 해당 업밸류 인덱스를 반환하고 재사용합니다. 그렇지 않으면 다음으로 넘어가 새 업밸류를 추가합니다.

이 두 함수는 많은 새로운 상태에 접근하고 수정하므로, 이를 정의해 봅시다. 먼저 ObjFunction에 업밸류 카운트 필드를 추가합니다.

  int arity;

  int upvalueCount;

  Chunk chunk;

우리는 양심적인 C 프로그래머이므로, ObjFunction이 처음 할당될 때 이를 0으로 초기화합니다.

  function->arity = 0;

  function->upvalueCount = 0;

  function->name = NULL;

컴파일러에 업밸류 배열 필드를 추가합니다.

  int localCount;

  Upvalue upvalues[UINT8_COUNT];

  int scopeDepth;

단순화를 위해 고정 크기를 부여했습니다. OP_GET_UPVALUE 및 OP_SET_UPVALUE 명령어는 단일 바이트 피연산자를 사용하여 업밸류 인덱스를 인코딩하므로, 함수가 가질 수 있는 업밸류 수(얼마나 많은 고유한 변수를 클로저에 닫을 수 있는지)에 제한이 있습니다. 이를 고려할 때, 그렇게 큰 정적 배열을 사용할 여유가 있습니다. 또한 컴파일러가 해당 제한을 초과하지 않도록 해야 합니다.

    if (upvalue->index == index && upvalue->isLocal == isLocal) {
      return i;
    }
  }

  if (upvalueCount == UINT8_COUNT) {
    error("Too many closure variables in function.");
    return 0;
  }

  compiler->upvalues[upvalueCount].isLocal = isLocal;

마지막으로, Upvalue 구조체 타입 자체입니다.

typedef struct {
  uint8_t index;
  bool isLocal;
} Upvalue;

index 필드는 업밸류가 포획하는 지역 슬롯을 저장합니다. isLocal 필드는 다음 섹션에서 다룰 자체적인 중요성을 가집니다.

25 . 2 . 2업밸류 평탄화하기

제가 이전에 보여드린 예제에서, 클로저는 바로 둘러싸는 함수에 선언된 변수에 접근하고 있었습니다. Lox는 다음과 같이 어떤 둘러싸는 스코프에 선언된 지역 변수에도 접근하는 것을 지원합니다.

fun outer() {
  var x = 1;
  fun middle() {
    fun inner() {
      print x;
    }
  }
}

여기서 우리는 inner()에서 x에 접근하고 있습니다. 이 변수는 middle()이 아닌 outer()에 선언되어 있습니다. 이런 경우도 처리해야 합니다. 변수가 스택에서 더 아래쪽에 있을 뿐이므로 훨씬 어렵지 않다고 생각할 수도 있습니다. 하지만 이 교활한 예제를 고려해 보세요.

fun outer() {
  var x = "value";
  fun middle() {
    fun inner() {
      print x;
    }

    print "create inner closure";
    return inner;
  }

  print "return from outer";
  return middle;
}

var mid = outer();
var in = mid();
in();

이것을 실행하면 다음과 같이 출력되어야 합니다.

return from outer
create inner closure
value

복잡하다는 것을 압니다. 중요한 부분은 x가 선언된 outer()가 inner()의 선언이 실행되기 전에 반환되고 모든 변수를 스택에서 팝한다는 것입니다. 따라서 inner()에 대한 클로저를 생성하는 시점에는 x가 이미 스택에 없습니다.

여기서 실행 흐름을 추적해 보았습니다.

x가 캡처되기 ② 전에 팝 ①되고, 나중에 접근 ③되는 것을 볼 수 있습니까? 실제로 두 가지 문제가 있습니다.

1. 바로 둘러싸는 함수를 넘어, 주변 함수에 선언된 지역 변수를 해결해야 합니다.

2. 이미 스택을 벗어난 변수를 캡처할 수 있어야 합니다.

다행히도 우리는 VM에 업밸류를 추가하는 중이고, 업밸류는 스택을 벗어난 변수를 추적하기 위해 명시적으로 설계되었습니다. 따라서 영리한 자기 참조를 통해 업밸류를 사용하여 업밸류가 바로 주변 함수 외부에서 선언된 변수를 캡처할 수 있도록 할 수 있습니다.

해결책은 클로저가 지역 변수 또는 바로 둘러싸는 함수에 있는 기존 업밸류를 포획할 수 있도록 하는 것입니다. 중첩된 함수가 여러 단계 떨어진 곳에 선언된 지역 변수를 참조하는 경우, 각 함수가 다음 함수가 가져갈 업밸류를 포획하도록 하여 모든 중간 함수를 통해 스레드될 것입니다.

위 예제에서 middle()은 바로 둘러싸는 함수 outer()에 있는 지역 변수 x를 포획하여 자신의 업밸류에 저장합니다. middle() 자체는 x를 참조하지 않더라도 이렇게 합니다. 그런 다음, inner()의 선언이 실행될 때, 그 클로저는 x를 포획한 middle()에 대한 ObjClosure에서 업밸류를 가져옵니다. 함수는 (지역 변수 또는 업밸류를) 바로 둘러싸는 함수에서만 포획하며, 이 함수는 내부 함수 선언이 실행될 시점에 여전히 존재함이 보장됩니다.

이를 구현하기 위해 resolveUpvalue()는 재귀적으로 호출됩니다.

  if (local != -1) {
    return addUpvalue(compiler, (uint8_t)local, true);
  }

  int upvalue = resolveUpvalue(compiler->enclosing, name);
  if (upvalue != -1) {
    return addUpvalue(compiler, (uint8_t)upvalue, false);
  }

  return -1;

코드 세 줄만 추가했지만, 이 함수를 처음 올바르게 작성하는 것이 정말 어려웠습니다. 새로운 것을 발명한 것이 아니라 Lua에서 개념을 포팅하는 것에 불과했음에도 불구하고 말입니다. 대부분의 재귀 함수는 재귀 호출 전에 모든 작업을 수행하거나(선위 순회(pre-order traversal), 즉 "내려가는 길에"), 또는 재귀 호출 후에 모든 작업을 수행합니다(후위 순회(post-order traversal), 즉 "올라오는 길에"). 이 함수는 둘 다 수행합니다. 재귀 호출은 중간에 있습니다.

천천히 살펴보겠습니다. 먼저, 둘러싸는 함수에서 일치하는 지역 변수를 찾습니다. 하나를 찾으면, 해당 지역 변수를 캡처하고 반환합니다. 이것이 기저 사례입니다.

그렇지 않으면, 바로 둘러싸는 함수 너머의 지역 변수를 찾습니다. 이를 위해 현재 컴파일러가 아닌 둘러싸는 컴파일러에 대해 resolveUpvalue()를 재귀적으로 호출합니다. 이러한 resolveUpvalue() 호출 시리즈는 중첩된 컴파일러 체인을 따라 이동하다가, 실제 지역 변수를 캡처하거나 컴파일러가 소진되는 기저 사례 중 하나에 도달합니다.

지역 변수가 발견되면, 가장 깊게 중첩된 resolveUpvalue() 호출이 이를 캡처하고 업밸류 인덱스를 반환합니다. 이는 내부 함수 선언에 대한 다음 호출로 반환됩니다. 해당 호출은 주변 함수에 대한 ObjClosure에서 업밸류를 캡처하고, 이런 식으로 계속됩니다. resolveUpvalue()에 대한 각 중첩 호출이 반환될 때마다, 우리가 해결하고 있는 식별자가 나타나는 가장 안쪽 함수 선언으로 다시 내려갑니다. 각 단계마다, 우리는 중간 함수에 업밸류를 추가하고 결과 업밸류 인덱스를 다음 호출로 전달합니다.

x를 해석할 때 원래 예제를 살펴보면 도움이 될 수 있습니다.

새로운 addUpvalue() 호출은 isLocal 매개변수에 false를 전달한다는 점에 유의하세요. 이제 이 플래그가 클로저가 주변 함수에서 지역 변수를 캡처할지 또는 업밸류를 캡처할지를 제어한다는 것을 알 수 있습니다.

컴파일러가 함수 선언의 끝에 도달할 때쯤이면, 모든 변수 참조는 지역 변수, 업밸류 또는 전역 변수로 해석됩니다. 각 업밸류는 차례로 주변 함수의 지역 변수를 포획하거나, 전이적 클로저의 경우 업밸류를 포획할 수 있습니다. 마침내 모든 올바른 변수를 포획하는 클로저를 런타임에 생성하는 바이트코드를 내보낼 충분한 데이터를 확보했습니다.

  emitBytes(OP_CLOSURE, makeConstant(OBJ_VAL(function)));

  for (int i = 0; i < function->upvalueCount; i++) {
    emitByte(compiler.upvalues[i].isLocal ? 1 : 0);
    emitByte(compiler.upvalues[i].index);
  }

}

OP_CLOSURE 명령어는 가변 크기 인코딩을 가진다는 점에서 독특합니다. 클로저가 포획하는 각 업밸류에 대해 두 개의 단일 바이트 피연산자가 있습니다. 각 피연산자 쌍은 해당 업밸류가 무엇을 포획하는지 지정합니다. 첫 번째 바이트가 1이면 둘러싸는 함수에 있는 지역 변수를 포획하고, 0이면 함수에 있는 업밸류 중 하나를 포획합니다. 다음 바이트는 포획할 지역 슬롯 또는 업밸류 인덱스입니다.

이러한 이상한 인코딩은 OP_CLOSURE에 대한 디스어셈블리 코드에서 특별한 지원이 필요하다는 것을 의미합니다.

      printf("\n");

      ObjFunction* function = AS_FUNCTION(
          chunk->constants.values[constant]);
      for (int j = 0; j < function->upvalueCount; j++) {
        int isLocal = chunk->code[offset++];
        int index = chunk->code[offset++];
        printf("%04d      |                     %s %d\n",
               offset - 2, isLocal ? "local" : "upvalue", index);
      }

      return offset;

예를 들어, 이 스크립트를 사용합니다.

fun outer() {
  var a = 1;
  var b = 2;
  fun middle() {
    var c = 3;
    var d = 4;
    fun inner() {
      print a + c + b + d;
    }
  }
}

inner()에 대한 클로저를 생성하는 명령어를 디스어셈블하면 다음과 같이 출력됩니다.

0004    9 OP_CLOSURE          2 <fn inner>
0006      |                     upvalue 0
0008      |                     local 1
0010      |                     upvalue 1
0012      |                     local 2

디스어셈블러 지원을 추가해야 할 다른 두 가지 간단한 명령어가 있습니다.

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

    case OP_GET_UPVALUE:
      return byteInstruction("OP_GET_UPVALUE", chunk, offset);
    case OP_SET_UPVALUE:
      return byteInstruction("OP_SET_UPVALUE", chunk, offset);

    case OP_EQUAL:

둘 다 단일 바이트 피연산자를 가지므로 흥미로운 일은 없습니다. debug 모듈이 AS_FUNCTION()에 접근할 수 있도록 include를 추가해야 합니다.

#include "debug.h"

#include "object.h"

#include "value.h"

이것으로 컴파일러는 우리가 원하는 대로 되었습니다. 각 함수 선언에 대해 OP_CLOSURE 명령어를 출력하고, 그 뒤에 런타임에 포착해야 하는 각 업밸류에 대한 일련의 피연산자 바이트 쌍이 이어집니다. 이제 VM의 해당 측으로 넘어가서 코드를 실행할 시간입니다.

25 . 3업밸류 객체

각 OP_CLOSURE 명령어 다음에는 이제 ObjClosure가 소유해야 할 업밸류를 지정하는 일련의 바이트가 이어집니다. 이 피연산자들을 처리하기 전에, 업밸류에 대한 런타임 표현이 필요합니다.

typedef struct ObjUpvalue {
  Obj obj;
  Value* location;
} ObjUpvalue;

업밸류는 더 이상 스택에 존재하지 않는 닫힌 변수를 관리해야 하며, 이는 어느 정도의 동적 할당을 의미합니다. 우리 VM에서 가장 쉬운 방법은 이미 가지고 있는 객체 시스템을 기반으로 구축하는 것입니다. 그렇게 하면, 다음 장에서 가비지 컬렉터를 구현할 때, GC도 업밸류의 메모리를 관리할 수 있습니다.

따라서, 우리의 런타임 업밸류 구조체는 일반적인 Obj 헤더 필드를 가진 ObjUpvalue입니다. 그 다음에는 닫힌 변수를 가리키는 location 필드가 있습니다. 이것이 Value 자체가 아닌 Value에 대한 포인터라는 점에 주목하세요. 이것은 값이 아니라 변수에 대한 참조입니다. 이는 업밸류가 포획하는 변수에 할당할 때, 복사본이 아니라 실제 변수에 할당한다는 의미이므로 중요합니다. 예를 들어:

fun outer() {
  var x = "before";
  fun inner() {
    x = "assigned";
  }
  inner();
  print x;
}
outer();

이 프로그램은 클로저가 x에 할당하고 주변 함수가 x에 접근함에도 불구하고 "assigned"를 출력해야 합니다.

업밸류는 객체이므로, 생성자 같은 함수부터 시작하여 모든 일반적인 객체 메커니즘을 가지고 있습니다.

ObjString* copyString(const char* chars, int length);

ObjUpvalue* newUpvalue(Value* slot);

void printObject(Value value);

이 함수는 닫힌 변수가 존재하는 슬롯의 주소를 인자로 받습니다. 다음은 구현입니다:

ObjUpvalue* newUpvalue(Value* slot) {
  ObjUpvalue* upvalue = ALLOCATE_OBJ(ObjUpvalue, OBJ_UPVALUE);
  upvalue->location = slot;
  return upvalue;
}

객체를 초기화하고 포인터를 저장하기만 하면 됩니다. 이를 위해 새로운 객체 타입이 필요합니다.

  OBJ_STRING,

  OBJ_UPVALUE

} ObjType;

그리고 반대편에는 소멸자 같은 함수가 있습니다.

      FREE(ObjString, object);
      break;
    }

    case OBJ_UPVALUE:
      FREE(ObjUpvalue, object);
      break;

  }

여러 클로저가 동일한 변수를 닫을 수 있으므로, ObjUpvalue는 참조하는 변수를 소유하지 않습니다. 따라서 해제할 유일한 것은 ObjUpvalue 자체입니다.

그리고 마지막으로 출력하기 위해:

    case OBJ_STRING:
      printf("%s", AS_CSTRING(value));
      break;

    case OBJ_UPVALUE:
      printf("upvalue");
      break;

  }

출력 기능은 최종 사용자에게는 유용하지 않습니다. 업밸류는 VM의 메모리 관리를 활용하기 위해 객체일 뿐입니다. Lox 사용자가 프로그램에서 직접 접근할 수 있는 일급 값은 아닙니다. 따라서 이 코드는 실제로 실행되지 않을 것입니다 . . . 하지만 처리되지 않은 switch case에 대해 컴파일러가 경고하는 것을 막아주므로 이렇게 합니다.

25 . 3 . 1클로저의 업밸류

처음에 업밸류를 소개했을 때, 각 클로저가 업밸류 배열을 가지고 있다고 말했습니다. 이제 드디어 그 구현으로 돌아왔습니다.

  ObjFunction* function;

  ObjUpvalue** upvalues;
  int upvalueCount;

} ObjClosure;

다른 클로저는 다른 수의 업밸류를 가질 수 있으므로 동적 배열이 필요합니다. 업밸류 자체도 동적으로 할당되므로, 이중 포인터, 즉 동적으로 할당된 업밸류 포인터 배열에 대한 포인터로 끝납니다. 또한 배열의 요소 수도 저장합니다.

ObjClosure를 생성할 때, 적절한 크기의 업밸류 배열을 할당합니다. 이 크기는 컴파일 시간에 결정되어 ObjFunction에 저장됩니다.

ObjClosure* newClosure(ObjFunction* function) {

  ObjUpvalue** upvalues = ALLOCATE(ObjUpvalue*,
                                   function->upvalueCount);
  for (int i = 0; i < function->upvalueCount; i++) {
    upvalues[i] = NULL;
  }

  ObjClosure* closure = ALLOCATE_OBJ(ObjClosure, OBJ_CLOSURE);

클로저 객체 자체를 생성하기 전에, 업밸류 배열을 할당하고 모두 NULL로 초기화합니다. 이 메모리 관련 이상한 절차는 (곧 나올) 가비지 컬렉션 신들을 만족시키기 위한 신중한 작업입니다. 이는 메모리 관리자가 초기화되지 않은 메모리를 보지 않도록 보장합니다.

그런 다음 배열을 새 클로저에 저장하고, ObjFunction에서 개수를 복사합니다.

  closure->function = function;

  closure->upvalues = upvalues;
  closure->upvalueCount = function->upvalueCount;

  return closure;

ObjClosure를 해제할 때, 업밸류 배열도 해제합니다.

    case OBJ_CLOSURE: {

      ObjClosure* closure = (ObjClosure*)object;
      FREE_ARRAY(ObjUpvalue*, closure->upvalues,
                 closure->upvalueCount);

      FREE(ObjClosure, object);

ObjClosure는 ObjUpvalue 객체 자체를 소유하지 않지만, 해당 업밸류에 대한 포인터를 포함하는 배열을 소유합니다.

인터프리터가 클로저를 생성할 때 업밸류 배열을 채웁니다. 여기서 우리는 OP_CLOSURE 다음에 오는 모든 피연산자를 순회하여 각 슬롯이 어떤 종류의 업밸류를 캡처하는지 확인합니다.

        push(OBJ_VAL(closure));

        for (int i = 0; i < closure->upvalueCount; i++) {
          uint8_t isLocal = READ_BYTE();
          uint8_t index = READ_BYTE();
          if (isLocal) {
            closure->upvalues[i] =
                captureUpvalue(frame->slots + index);
          } else {
            closure->upvalues[i] = frame->closure->upvalues[index];
          }
        }

        break;

이 코드는 클로저가 살아나는 마법 같은 순간입니다. 클로저가 예상하는 각 업밸류를 반복합니다. 각 업밸류에 대해 한 쌍의 피연산자 바이트를 읽습니다. 업밸류가 둘러싸는 함수에 있는 지역 변수를 닫는 경우, captureUpvalue()가 작업을 수행하도록 합니다.

그렇지 않으면 주변 함수에서 업밸류를 포획합니다. OP_CLOSURE 명령어는 함수 선언의 끝에 내보내집니다. 이 선언을 실행하는 순간에 현재 함수는 주변 함수입니다. 이는 현재 함수의 클로저가 콜 스택 상단의 CallFrame에 저장된다는 것을 의미합니다. 따라서 둘러싸는 함수에서 업밸류를 가져오려면, 해당 CallFrame에 대한 참조를 캐시하는 frame 지역 변수에서 바로 읽을 수 있습니다.

지역 변수를 닫는 것은 더 흥미롭습니다. 대부분의 작업은 별도의 함수에서 이루어지지만, 먼저 전달할 인수를 계산합니다. 주변 함수의 스택 창에서 캡처된 지역 변수의 슬롯에 대한 포인터를 가져와야 합니다. 해당 창은 슬롯 0을 가리키는 frame->slots에서 시작합니다. index를 추가하면 캡처하려는 지역 슬롯으로 오프셋됩니다. 해당 포인터를 여기에 전달합니다.

static ObjUpvalue* captureUpvalue(Value* local) {
  ObjUpvalue* createdUpvalue = newUpvalue(local);
  return createdUpvalue;
}

이것은 좀 어리석어 보입니다. 주어진 스택 슬롯을 포획하는 새 ObjUpvalue를 생성하고 반환하는 것뿐입니다. 이를 위해 별도의 함수가 필요했을까요? 글쎄요, 아직은 아닙니다. 하지만 여기에 더 많은 코드를 넣게 될 것이라는 것을 알고 계실 겁니다.

먼저, 우리가 작업하고 있는 내용을 마무리합시다. OP_CLOSURE를 처리하는 인터프리터 코드로 돌아가서, 결국 업밸류 배열을 반복하고 각 업밸류를 초기화하는 작업을 마칩니다. 이 작업이 완료되면, 변수들을 가리키는 업밸류 배열로 가득 찬 새로운 클로저를 갖게 됩니다.

이를 바탕으로 해당 업밸류로 작업하는 명령어를 구현할 수 있습니다.

      }

      case OP_GET_UPVALUE: {
        uint8_t slot = READ_BYTE();
        push(*frame->closure->upvalues[slot]->location);
        break;
      }

      case OP_EQUAL: {

피연산자는 현재 함수의 업밸류 배열의 인덱스입니다. 따라서 단순히 해당 업밸류를 찾아 그 위치 포인터를 역참조하여 해당 슬롯의 값을 읽습니다. 변수를 설정하는 것도 비슷합니다.

      }

      case OP_SET_UPVALUE: {
        uint8_t slot = READ_BYTE();
        *frame->closure->upvalues[slot]->location = peek(0);
        break;
      }

      case OP_EQUAL: {

스택 최상단의 값을 가져와 선택된 업밸류가 가리키는 슬롯에 저장합니다. 지역 변수에 대한 명령어와 마찬가지로, 이 명령어들이 빨라야 한다는 것이 중요합니다. 사용자 프로그램은 변수를 끊임없이 읽고 쓰므로, 이것이 느리면 모든 것이 느립니다. 그리고 평소와 같이, 이들을 빠르게 만드는 방법은 간단하게 유지하는 것입니다. 이 두 가지 새로운 명령어는 꽤 좋습니다. 제어 흐름도 없고, 복잡한 산술도 없으며, 그저 몇 개의 포인터 간접 참조와 push()만 있습니다.

이것은 중요한 이정표입니다. 모든 변수가 스택에 남아 있는 한, 우리는 작동하는 클로저를 가집니다. 다음을 시도해 보세요.

fun outer() {
  var x = "outside";
  fun inner() {
    print x;
  }
  inner();
}
outer();

이것을 실행하면 "outside"가 올바르게 출력됩니다.

25 . 4닫힌 업밸류

물론 클로저의 핵심 기능은 변수를 선언한 함수가 반환된 후에도 필요한 동안 변수를 유지한다는 것입니다. 다음은 작동해야 할 또 다른 예입니다.

fun outer() {
  var x = "outside";
  fun inner() {
    print x;
  }

  return inner;
}

var closure = outer();
closure();

하지만 지금 실행하면 . . . 무슨 일이 일어날지 아무도 모릅니다. 런타임에는 더 이상 닫힌 변수를 포함하지 않는 스택 슬롯에서 읽게 될 것입니다. 제가 몇 번 언급했듯이, 핵심 문제는 클로저의 변수가 스택 의미론을 가지지 않는다는 것입니다. 이는 변수가 선언된 함수가 반환될 때 스택에서 힙으로 올려야 한다는 것을 의미합니다. 이 장의 마지막 섹션에서 이 작업을 수행합니다.

25 . 4 . 1값과 변수

코드를 작성하기 전에, 중요한 의미론적 지점을 깊이 파고들고 싶습니다. 클로저는 값을 닫을까요, 아니면 변수를 닫을까요? 이것은 순전히 학술적인 질문이 아닙니다. 저는 단순히 논점을 따지고 있는 것이 아닙니다. 다음을 고려해 보세요.

var globalSet;
var globalGet;

fun main() {
  var a = "initial";

  fun set() { a = "updated"; }
  fun get() { print a; }

  globalSet = set;
  globalGet = get;
}

main();
globalSet();
globalGet();

바깥쪽 main() 함수는 두 개의 클로저를 생성하고 이들을 전역 변수에 저장하여 main() 자체의 실행보다 더 오래 살아남도록 합니다. 이 두 클로저는 동일한 변수를 포획합니다. 첫 번째 클로저는 새 값을 할당하고 두 번째 클로저는 변수를 읽습니다.

globalGet() 호출은 무엇을 출력할까요? 클로저가 값을 포획한다면, 각 클로저는 함수 선언이 실행될 시점에 a가 가졌던 값을 가진 a의 자체 복사본을 얻습니다. globalSet() 호출은 set()의 a 복사본을 수정하지만, get()의 복사본은 영향을 받지 않을 것입니다. 따라서 globalGet() 호출은 "initial"을 출력할 것입니다.

클로저가 변수를 닫는다면, get()과 set()은 둘 다 동일한 가변 변수를 포획(참조)할 것입니다. set()이 a를 변경할 때, get()이 읽는 것과 동일한 a를 변경합니다. a는 오직 하나뿐입니다. 이는 globalGet() 호출이 "updated"를 출력할 것임을 의미합니다.

둘 중 어느 쪽일까요? Lox와 클로저가 있는 대부분의 다른 언어에 대한 답은 후자입니다. 클로저는 변수를 포획합니다. 값 자체가 존재하는 위치를 포획한다고 생각할 수 있습니다. 이는 더 이상 스택에 없는 닫힌 변수를 다룰 때 명심해야 할 중요한 사항입니다. 변수가 힙으로 이동할 때, 해당 변수를 포획하는 모든 클로저가 그 변수의 유일한 새 위치에 대한 참조를 유지하도록 해야 합니다. 그렇게 하면 변수가 변경될 때 모든 클로저가 변경 사항을 보게 됩니다.

25 . 4 . 2업밸류 닫기

지역 변수는 항상 스택에서 시작한다는 것을 알고 있습니다. 이것이 더 빠르고, 단일 패스 컴파일러가 변수가 포착되었다는 것을 발견하기 전에 코드를 내보낼 수 있게 합니다. 또한 닫힌 변수는 캡처된 변수가 선언된 함수보다 클로저가 더 오래 살아남는 경우 힙으로 이동해야 한다는 것도 알고 있습니다.

Lua를 따라, 우리는 스택에 여전히 있는 지역 변수를 가리키는 업밸류를 열린 업밸류(open upvalue)라고 부를 것입니다. 변수가 힙으로 이동할 때, 우리는 업밸류를 닫는(closing) 것이며, 그 결과는 당연히 닫힌 업밸류(closed upvalue)입니다. 우리가 답해야 할 두 가지 질문은 다음과 같습니다.

1. 닫힌 변수는 힙의 어디로 갈까요?

2. 언제 업밸류를 닫을까요?

첫 번째 질문에 대한 답은 쉽습니다. 우리는 이미 변수에 대한 참조를 나타내는 편리한 힙 객체인 ObjUpvalue 자체를 가지고 있습니다. 닫힌 변수는 ObjUpvalue 구조체 내부의 새 필드로 이동할 것입니다. 이렇게 하면 업밸류를 닫기 위해 추가적인 힙 할당을 할 필요가 없습니다.

두 번째 질문도 간단합니다. 변수가 스택에 있는 한, 해당 변수를 참조하는 코드가 있을 수 있으며, 그 코드는 올바르게 작동해야 합니다. 따라서 변수를 힙으로 옮기는 논리적인 시점은 가능한 한 늦게입니다. 지역 변수가 스코프를 벗어나는 즉시 이동하면, 그 시점 이후에는 어떤 코드도 스택에서 변수에 접근하려고 시도하지 않을 것이라고 확신할 수 있습니다. 변수가 스코프를 벗어난 후에는, 어떤 코드가 이를 사용하려고 시도했다면 컴파일러가 오류를 보고했을 것입니다.

컴파일러는 지역 변수가 스코프를 벗어날 때 이미 OP_POP 명령어를 내보냅니다. 변수가 클로저에 의해 포착되면, 대신 해당 변수를 스택에서 해당 업밸류로 올리는 다른 명령어를 내보낼 것입니다. 이를 위해 컴파일러는 어떤 지역 변수가 닫히는지 알아야 합니다.

컴파일러는 각 함수의 지역 변수에 대한 Upvalue 구조체 배열을 이미 유지하여 정확히 그 상태를 추적합니다. 이 배열은 "이 클로저는 어떤 변수를 사용합니까?"라는 질문에 답하는 데 좋습니다. 하지만 "어떤 함수라도 이 지역 변수를 포착합니까?"라는 질문에 답하는 데는 적합하지 않습니다. 특히, 특정 클로저에 대한 컴파일러가 작업을 마친 후에는, 변수가 포착된 둘러싸는 함수에 대한 컴파일러는 더 이상 어떤 업밸류 상태에도 접근할 수 없습니다.

다시 말해, 컴파일러는 업밸류에서 포착하는 지역 변수로의 포인터를 유지하지만, 그 반대 방향으로는 아닙니다. 따라서 주어진 지역 변수가 클로저에 의해 포착되는지 여부를 알 수 있도록 기존 Local 구조체에 추가적인 추적 기능을 추가해야 합니다.

  int depth;

  bool isCaptured;

} Local;

이 필드는 해당 지역 변수가 나중에 중첩된 함수 선언에 의해 캡처된 경우 true입니다. 초기에는 모든 지역 변수는 캡처되지 않은 상태입니다.

  local->depth = -1;

  local->isCaptured = false;

}

마찬가지로 컴파일러가 암묵적으로 선언하는 특별한 "슬롯 0 지역 변수"도 캡처되지 않습니다.

  local->depth = 0;

  local->isCaptured = false;

  local->name.start = "";

식별자를 해석할 때, 지역 변수에 대한 업밸류를 생성하게 되면, 해당 변수를 캡처됨으로 표시합니다.

  if (local != -1) {

    compiler->enclosing->locals[local].isCaptured = true;

    return addUpvalue(compiler, (uint8_t)local, true);

이제 블록 스코프가 끝날 때 컴파일러가 지역 변수에 대한 스택 슬롯을 해제하는 코드를 내보내면, 어떤 변수들이 힙으로 옮겨져야 하는지 알 수 있습니다. 이를 위해 새로운 명령어를 사용할 것입니다.

  while (current->localCount > 0 &&
         current->locals[current->localCount - 1].depth >
            current->scopeDepth) {

    if (current->locals[current->localCount - 1].isCaptured) {
      emitByte(OP_CLOSE_UPVALUE);
    } else {
      emitByte(OP_POP);
    }

    current->localCount--;
  }

이 명령어는 피연산자가 필요 없습니다. 이 명령어가 실행되는 시점에 변수는 항상 스택의 맨 위에 있을 것이라는 것을 알고 있습니다. 이 명령어를 선언합니다.

  OP_CLOSURE,

  OP_CLOSE_UPVALUE,

  OP_RETURN,

그리고 이것에 대한 사소한 디스어셈블러 지원을 추가합니다:

    }

    case OP_CLOSE_UPVALUE:
      return simpleInstruction("OP_CLOSE_UPVALUE", offset);

    case OP_RETURN:

아주 좋습니다. 이제 생성된 바이트코드는 각 캡처된 지역 변수가 언제 힙으로 옮겨져야 하는지 런타임에 정확히 알려줍니다. 더 좋은 점은, 이 특별한 처리가 필요한 클로저에 사용되는 지역 변수에 대해서만 이렇게 한다는 것입니다. 이는 사용자가 사용하는 기능에 대해서만 비용을 지불하게 하고자 하는 우리의 일반적인 성능 목표와 일치합니다. 클로저에 의해 사용되지 않는 변수들은 이전과 마찬가지로 스택에서만 존재하고 소멸합니다.

25 . 4 . 3열린 업밸류 추적하기

이제 런타임 측으로 넘어가겠습니다. OP_CLOSE_UPVALUE 명령어를 해석하기 전에 해결해야 할 문제가 있습니다. 이전에 클로저가 변수를 포착하는지 값을 포착하는지에 대해 이야기할 때, 두 클로저가 동일한 변수에 접근할 경우 메모리에서 정확히 동일한 저장 위치를 참조하는 것이 중요하다고 말했습니다. 그래야 한 클로저가 변수에 쓰면 다른 클로저가 변경 사항을 볼 수 있습니다.

지금은 두 클로저가 동일한 지역 변수를 포획하면 VM은 각 클로저에 대해 별도의 Upvalue를 생성합니다. 필요한 공유가 누락된 것입니다. 변수를 스택에서 이동할 때, 만약 하나의 업밸류에만 이동시키면 다른 업밸류는 고아 값을 갖게 될 것입니다.

이를 해결하기 위해, VM이 특정 지역 변수 슬롯을 포획하는 업밸류가 필요할 때마다, 먼저 해당 슬롯을 가리키는 기존 업밸류를 찾을 것입니다. 발견되면, 그것을 재사용할 것입니다. 문제는 이전에 생성된 모든 업밸류들이 다양한 클로저의 업밸류 배열 안에 숨겨져 있다는 것입니다. 이 클로저들은 VM 메모리의 어느 곳에나 있을 수 있습니다.

첫 번째 단계는 VM에 스택에 여전히 있는 변수를 가리키는 모든 열린 업밸류 목록을 제공하는 것입니다. VM이 업밸류가 필요할 때마다 목록을 검색하는 것이 느리게 들릴 수 있지만, 실제로는 그렇게 나쁘지 않습니다. 스택에서 실제로 닫히는 변수의 수는 적은 경향이 있습니다. 그리고 클로저를 생성하는 함수 선언은 사용자 프로그램에서 성능에 중요한 실행 경로에 거의 없습니다.

더 좋은 점은, 열린 업밸류 목록을 가리키는 스택 슬롯 인덱스 순서로 정렬할 수 있다는 것입니다. 일반적인 경우는 슬롯이 아직 캡처되지 않았다는 것입니다. 클로저 간에 변수를 공유하는 경우는 흔하지 않습니다. 그리고 클로저는 스택 맨 위 근처의 지역 변수를 캡처하는 경향이 있습니다. 열린 업밸류 배열을 스택 슬롯 순서로 저장하면, 캡처하려는 지역 변수가 있는 슬롯을 지나가는 즉시 찾을 수 없다는 것을 알 수 있습니다. 해당 지역 변수가 스택 맨 위에 가까이 있으면 루프를 꽤 일찍 종료할 수 있습니다.

정렬된 목록을 유지하려면 중간에 요소를 효율적으로 삽입해야 합니다. 이는 동적 배열 대신 연결 리스트를 사용하는 것을 제안합니다. ObjUpvalue 구조체를 직접 정의했기 때문에, 가장 쉬운 구현은 다음 포인터를 ObjUpvalue 구조체 자체 내에 직접 배치하는 침투형 리스트입니다.

  Value* location;

  struct ObjUpvalue* next;

} ObjUpvalue;

업밸류를 할당할 때, 아직 어떤 목록에도 연결되지 않았으므로 링크는 NULL입니다.

  upvalue->location = slot;

  upvalue->next = NULL;

  return upvalue;

VM이 목록을 소유하므로, 헤드 포인터는 주 VM 구조체 안에 바로 들어갑니다.

  Table strings;

  ObjUpvalue* openUpvalues;

  Obj* objects;

목록은 비어있는 상태로 시작합니다.

  vm.frameCount = 0;

  vm.openUpvalues = NULL;

}

VM이 가리키는 첫 번째 업밸류부터 시작하여, 각 열린 업밸류는 스택에서 더 아래쪽에 있는 지역 변수를 참조하는 다음 열린 업밸류를 가리킵니다. 예를 들어, 이 스크립트는,

{
  var a = 1;
  fun f() {
    print a;
  }
  var b = 2;
  fun g() {
    print b;
  }
  var c = 3;
  fun h() {
    print c;
  }
}

다음과 같이 연결된 업밸류 시리즈를 생성해야 합니다.

지역 변수를 닫을 때마다, 새 업밸류를 생성하기 전에 목록에서 기존 업밸류를 찾습니다.

static ObjUpvalue* captureUpvalue(Value* local) {

  ObjUpvalue* prevUpvalue = NULL;
  ObjUpvalue* upvalue = vm.openUpvalues;
  while (upvalue != NULL && upvalue->location > local) {
    prevUpvalue = upvalue;
    upvalue = upvalue->next;
  }

  if (upvalue != NULL && upvalue->location == local) {
    return upvalue;
  }

  ObjUpvalue* createdUpvalue = newUpvalue(local);

우리는 목록의 헤드에서 시작합니다. 스택의 맨 위에서 가장 가까운 업밸류입니다. 목록을 순회하면서, 찾고 있는 슬롯 위에 있는 슬롯을 가리키는 모든 업밸류를 건너뛰기 위해 작은 포인터 비교를 사용합니다. 이 작업을 하는 동안, 목록에서 이전 업밸류를 추적합니다. 만약 나중에 노드를 삽입하게 된다면 해당 노드의 next 포인터를 업데이트해야 할 것입니다.

루프를 종료할 수 있는 세 가지 이유가 있습니다.

1. 우리가 멈춘 지역 슬롯이 우리가 찾고 있는 슬롯인 경우. 변수를 캡처하는 기존 업밸류를 찾았으므로 해당 업밸류를 재사용합니다.

2. 더 이상 검색할 업밸류가 없는 경우. upvalue가 NULL인 경우, 목록의 모든 열린 업밸류가 우리가 찾고 있는 슬롯 위에 있는 지역 변수를 가리키거나 (더 가능성이 높게) 업밸류 목록이 비어 있음을 의미합니다. 어느 쪽이든, 우리 슬롯에 대한 업밸류를 찾지 못했습니다.

3. 우리가 찾고 있는 슬롯 아래에 있는 지역 슬롯을 가리키는 업밸류를 찾은 경우. 목록이 정렬되어 있으므로, 이는 우리가 닫고 있는 슬롯을 지나쳤으며, 따라서 해당 슬롯에 대한 기존 업밸류가 없어야 함을 의미합니다.

첫 번째 경우에는 작업이 완료되어 반환되었습니다. 그렇지 않으면, 로컬 슬롯에 대한 새 업밸류를 생성하고 올바른 위치에 목록에 삽입합니다.

  ObjUpvalue* createdUpvalue = newUpvalue(local);

  createdUpvalue->next = upvalue;

  if (prevUpvalue == NULL) {
    vm.openUpvalues = createdUpvalue;
  } else {
    prevUpvalue->next = createdUpvalue;
  }

  return createdUpvalue;

이 함수의 현재 구현은 이미 업밸류를 생성하므로, 업밸류를 목록의 올바른 위치에 삽입하는 코드만 추가하면 됩니다. 목록 순회를 종료한 것은 목록의 끝을 지나쳤거나, 찾고 있는 슬롯보다 스택 슬롯이 낮은 첫 번째 업밸류에서 멈췄기 때문입니다. 어느 경우든, 이는 upvalue가 가리키는 객체 앞에 새 업밸류를 삽입해야 함을 의미합니다 (목록의 끝에 도달한 경우 NULL일 수 있습니다).

데이터 구조 101에서 배웠듯이, 연결 리스트에 노드를 삽입하려면 이전 노드의 next 포인터가 새 노드를 가리키도록 설정해야 합니다. 우리는 목록을 순회하면서 편리하게 이전 노드를 추적해 왔습니다. 또한 목록의 헤드에 새 업밸류를 삽입하는 특별한 경우도 처리해야 합니다. 이 경우 "다음" 포인터는 VM의 헤드 포인터가 됩니다.

이 업데이트된 함수를 사용하면 VM은 이제 어떤 주어진 지역 슬롯에 대해 항상 단 하나의 ObjUpvalue만 존재하도록 보장합니다. 두 클로저가 동일한 변수를 포획하면 동일한 업밸류를 얻게 됩니다. 이제 이 업밸류를 스택에서 옮길 준비가 되었습니다.

25 . 4 . 4런타임에 업밸류 닫기

컴파일러는 지역 변수가 힙으로 옮겨져야 하는 정확한 시점을 VM에 알리기 위해 OP_CLOSE_UPVALUE 명령어를 친절하게 내보냅니다. 이 명령어를 실행하는 것은 인터프리터의 책임입니다.

      }

      case OP_CLOSE_UPVALUE:
        closeUpvalues(vm.stackTop - 1);
        pop();
        break;

      case OP_RETURN: {

명령어에 도달하면, 우리가 올리는 변수는 스택의 맨 위에 있습니다. 해당 스택 슬롯의 주소를 전달하여 헬퍼 함수를 호출합니다. 이 함수는 업밸류를 닫고 지역 변수를 스택에서 힙으로 옮기는 역할을 합니다. 그 후, VM은 스택 슬롯을 폐기할 수 있으며, 이는 pop()을 호출하여 수행합니다.

재미있는 일은 여기에서 일어납니다:

static void closeUpvalues(Value* last) {
  while (vm.openUpvalues != NULL &&
         vm.openUpvalues->location >= last) {
    ObjUpvalue* upvalue = vm.openUpvalues;
    upvalue->closed = *upvalue->location;
    upvalue->location = &upvalue->closed;
    vm.openUpvalues = upvalue->next;
  }
}

이 함수는 스택 슬롯에 대한 포인터를 받습니다. 이 슬롯이나 그 위의 스택 슬롯을 가리키는 모든 열린 업밸류를 찾아서 닫습니다. 지금은 스택의 가장 위 슬롯에 대한 포인터만 전달하므로 "또는 그 위" 부분은 적용되지 않지만, 곧 적용될 것입니다.

이를 위해, VM의 열린 업밸류 목록을 다시 위에서 아래로 순회합니다. 업밸류의 위치가 우리가 닫고 있는 슬롯 범위 내를 가리키면 업밸류를 닫습니다. 그렇지 않으면, 범위 밖의 업밸류에 도달하면 나머지도 마찬가지일 것이므로 반복을 중지합니다.

업밸류가 닫히는 방식은 꽤 멋집니다. 먼저, 변수의 값을 ObjUpvalue의 closed 필드에 복사합니다. 이곳은 닫힌 변수들이 힙에 존재하는 곳입니다. OP_GET_UPVALUE 및 OP_SET_UPVALUE 명령어는 변수가 이동된 후 해당 변수를 거기서 찾아야 합니다. 업밸류가 열려 있는지 닫혀 있는지 확인하기 위해 해당 명령어에 대한 인터프리터 코드에 조건 논리를 추가할 수도 있습니다.

하지만 이미 간접 계층이 존재합니다. 해당 명령어들은 변수의 값에 접근하기 위해 location 포인터를 역참조합니다. 변수가 스택에서 closed 필드로 이동할 때, 우리는 단순히 해당 location을 ObjUpvalue 자체의 closed 필드 주소로 업데이트합니다.

OP_GET_UPVALUE 및 OP_SET_UPVALUE가 해석되는 방식을 전혀 변경할 필요가 없습니다. 이는 코드를 간단하게 유지하고, 결과적으로 빠르게 만듭니다. 하지만 ObjUpvalue에 새로운 필드를 추가해야 합니다.

  Value* location;

  Value closed;

  struct ObjUpvalue* next;

그리고 ObjUpvalue를 생성할 때 0으로 초기화하여 초기화되지 않은 메모리가 떠돌지 않도록 해야 합니다.

  ObjUpvalue* upvalue = ALLOCATE_OBJ(ObjUpvalue, OBJ_UPVALUE);

  upvalue->closed = NIL_VAL;

  upvalue->location = slot;

컴파일러는 블록의 끝에 도달할 때마다 해당 블록의 모든 지역 변수를 폐기하고 클로저에 의해 닫힌 각 지역 변수에 대해 OP_CLOSE_UPVALUE 명령어를 내보냅니다. 컴파일러는 함수 본문을 정의하는 가장 바깥쪽 블록 스코프의 끝에는 어떤 명령어도 내보내지 않습니다. 해당 스코프는 함수의 매개변수와 함수 내부에 선언된 모든 지역 변수를 포함합니다. 이들도 닫혀야 합니다.

이것이 closeUpvalues()가 스택 슬롯에 대한 포인터를 받아들이는 이유입니다. 함수가 반환될 때, 동일한 헬퍼를 호출하고 함수가 소유하는 첫 번째 스택 슬롯을 전달합니다.

        Value result = pop();

        closeUpvalues(frame->slots);

        vm.frameCount--;

함수의 스택 창에서 첫 번째 슬롯을 전달함으로써, 반환하는 함수가 소유하는 모든 나머지 열린 업밸류를 닫습니다. 그리고 이것으로 우리는 완전히 작동하는 클로저 구현을 갖게 되었습니다. 닫힌 변수는 이를 포획하는 함수가 필요한 동안 살아남습니다.

이것은 많은 작업이었습니다! jlox에서는 클로저가 환경 표현에서 자연스럽게 파생되었습니다. clox에서는 새로운 바이트코드 명령어, 컴파일러의 더 많은 데이터 구조, 그리고 새로운 런타임 객체 등 많은 코드를 추가해야 했습니다. VM은 클로저의 변수를 다른 변수와 매우 다르게 취급합니다.

여기에는 합리적인 이유가 있습니다. 구현 복잡성 측면에서 jlox는 클로저를 "공짜"로 제공했습니다. 하지만 성능 측면에서는 jlox의 클로저는 결코 공짜가 아니었습니다. 모든 환경을 힙에 할당함으로써 jlox는 모든 지역 변수에 대해 상당한 성능 비용을 지불했으며, 그중 대부분은 클로저에 의해 포획되지 않았습니다.

clox에서는 더 복잡한 시스템을 가지고 있지만, 이를 통해 지역 변수에 대해 관찰되는 두 가지 사용 패턴에 맞게 구현을 조정할 수 있습니다. 스택 의미론을 가지는 대부분의 변수는 스택에 완전히 할당되어 간단하고 빠릅니다. 그리고 이것이 작동하지 않는 몇 안 되는 지역 변수에 대해서는 필요에 따라 더 느린 두 번째 경로를 선택할 수 있습니다.

다행히 사용자들은 이러한 복잡성을 인지하지 못합니다. 사용자 관점에서 Lox의 지역 변수는 간단하고 균일합니다. 언어 자체는 jlox의 구현만큼이나 간단합니다. 하지만 내부적으로 clox는 사용자가 하는 일을 지켜보고 특정 사용 사례에 맞게 최적화합니다. 언어 구현이 정교해질수록 이러한 작업을 더 많이 하게 될 것입니다. "최적화"의 상당 부분은 특정 사용을 감지하고 해당 패턴에 맞는 코드를 위해 맞춤형의 더 빠른 경로를 제공하는 특수 케이스 코드를 추가하는 것입니다.

이제 clox에서 렉시컬 스코프가 완전히 작동합니다. 이는 중요한 이정표입니다. 그리고 복잡한 수명을 가진 함수와 변수를 갖게 되면서 clox의 힙에는 포인터 웹으로 연결된 수많은 객체들이 떠다니게 됩니다. 다음 단계는 더 이상 필요 없는 객체들의 메모리를 해제하는 방법을 알아내는 것입니다.

var globalOne;
var globalTwo;

fun main() {
  {
    var a = "one";
    fun one() {
      print a;
    }
    globalOne = one;
  }

  {
    var a = "two";
    fun two() {
      print a;
    }
    globalTwo = two;
  }
}

main();
globalOne();
globalTwo();

var globalOne;
var globalTwo;

fun main() {
  for (var a = 1; a <= 2; a = a + 1) {
    fun closure() {
      print a;
    }
    if (globalOne == nil) {
      globalOne = closure;
    } else {
      globalTwo = closure;
    }
  }
}

main();
globalOne();
globalTwo();

var closures = [];
for (var i = 1; i <= 2; i++) {
  closures.push(function () { console.log(i); });
}

closures[0]();
closures[1]();

var closures = [];
var i;
for (i = 1; i <= 2; i++) {
  closures.push(function () { console.log(i); });
}

closures[0]();
closures[1]();

var closures = [];
for (let i = 1; i <= 2; i++) {
  closures.push(function () { console.log(i); });
}

closures[0]();
closures[1]();

closures = []
for i in range(1, 3):
  closures.append(lambda: print(i))

closures[0]()
closures[1]()

closures = []
for i in 1..2 do
  closures << lambda { puts i }
end

closures[0].call
closures[1].call

closures = []
(1..2).each do |i|
  closures << lambda { puts i }
end

closures[0].call
closures[1].call