이리저리 건너뛰기

우리 마음이 상상하는 질서는 어떤 목표에 도달하기 위해 만들어진 그물이나 사다리와 같다. 하지만 나중에 그 사다리를 버려야 하는데, 유용했을지라도 무의미했다는 것을 발견하기 때문이다.

움베르토 에코, 장미의 이름

여기까지 오는 데 시간이 좀 걸렸지만, 드디어 가상 머신에 제어 흐름(control flow)을 추가할 준비가 되었습니다. jlox용으로 만들었던 트리-순회(tree-walk) 인터프리터에서는 Java의 제어 흐름을 사용하여 Lox의 제어 흐름을 구현했습니다. Lox의 if 문을 실행하기 위해 Java의 if 문을 사용하여 선택된 분기를 실행했죠. 이는 작동하지만, 완전히 만족스럽지는 않습니다. JVM 자체나 네이티브 CPU는 어떤 마법으로 if 문을 구현할까요? 이제 자체 바이트코드 VM을 가지고 있으니, 그 질문에 답할 수 있습니다.

"제어 흐름"이라고 말할 때 무엇을 의미하는 걸까요? "흐름"이란 프로그램 텍스트를 통해 실행이 이동하는 방식을 의미합니다. 마치 컴퓨터 안에 작은 로봇이 우리의 코드를 돌아다니며 여기저기 조각들을 실행하는 것과 같습니다. 흐름은 그 로봇이 취하는 경로이며, 로봇을 제어함으로써 어떤 코드 조각을 실행할지 결정합니다.

jlox에서 로봇의 주의 지점(locus of attention)—즉 현재 코드 조각—은 다양한 Java 변수에 저장된 AST 노드와 우리가 실행 중인 Java 코드에 따라 암묵적으로 결정되었습니다. clox에서는 훨씬 더 명시적입니다. VM의 ip 필드는 현재 바이트코드 명령어의 주소를 저장합니다. 이 필드의 값은 정확히 프로그램에서 "우리가 어디에 있는지"를 나타냅니다.

실행은 ip를 증가시키면서 정상적으로 진행됩니다. 하지만 우리는 이 변수를 원하는 대로 변경할 수 있습니다. 제어 흐름을 구현하기 위해 필요한 것은 ip를 더 흥미로운 방식으로 변경하는 것뿐입니다. 가장 간단한 제어 흐름 구조는 else 절이 없는 if 문입니다:

if (condition) print("condition was truthy");

VM은 조건식에 대한 바이트코드를 평가합니다. 결과가 참 같은 값(truthy)이면, 계속 진행하여 본문의 print 문을 실행합니다. 흥미로운 경우는 조건이 거짓 같은 값(falsey)일 때입니다. 이런 일이 발생하면, 실행은 then 분기를 건너뛰고 다음 문장으로 진행됩니다.

코드 덩어리를 건너뛰려면, 단순히 ip 필드를 해당 코드 다음에 오는 바이트코드 명령어의 주소로 설정합니다. 특정 코드를 조건부로 건너뛰려면, 스택 맨 위의 값을 확인하는 명령어가 필요합니다. 만약 그 값이 거짓 같은 값이라면, ip에 주어진 오프셋을 더하여 일정 범위의 명령어를 건너뛰도록 합니다. 그렇지 않으면, 아무것도 하지 않고 평소처럼 실행이 다음 명령어로 진행되도록 합니다.

바이트코드로 컴파일할 때, 코드의 명시적인 중첩 블록 구조는 사라지고 평면적인 명령어 시리즈만 남습니다. Lox는 구조적 프로그래밍 언어이지만, clox 바이트코드는 그렇지 않습니다. 적절한(혹은 잘못된, 관점에 따라 다르지만) 바이트코드 명령어 세트는 블록의 중간으로 점프하거나, 한 스코프에서 다른 스코프로 점프할 수 있습니다.

VM은 결과가 스택을 알 수 없고 일관성 없는 상태로 만들더라도 기꺼이 이를 실행할 것입니다. 따라서 바이트코드가 비구조적일지라도, 컴파일러가 Lox 자체와 동일한 구조와 중첩을 유지하는 깨끗한 코드만 생성하도록 주의를 기울일 것입니다.

이것이 실제 CPU가 작동하는 방식입니다. 비록 우리가 구조화된 제어 흐름을 요구하는 고수준 언어를 사용하여 프로그래밍하더라도, 컴파일러는 이를 원시적인 점프(raw jumps)로 변환합니다. 결국, 가장 기본적인 수준에서는 goto가 유일한 진정한 제어 흐름이라는 것이 밝혀집니다.

어쨌든, 너무 철학적으로 들리지는 않기를 바랍니다. 중요한 점은 조건부 점프 명령어 하나만 있으면 Lox의 if 문을 구현하기에 충분하다는 것입니다. else 절이 없는 if 문이라면 말이죠. 그럼 바로 시작해 보겠습니다.

23 . 1If 문

수많은 장을 거쳐 여기까지 왔으니, 이제 새로운 기능이 프런트 엔드에서 시작하여 파이프라인을 거쳐가는 과정을 알 것입니다. if 문은 문장이므로, 파서에 연결하는 지점입니다.

  if (match(TOKEN_PRINT)) {
    printStatement();

  } else if (match(TOKEN_IF)) {
    ifStatement();

  } else if (match(TOKEN_LEFT_BRACE)) {

if 키워드를 만나면 컴파일을 이 함수에 위임합니다:

static void ifStatement() {
  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'if'.");
  expression();
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after condition."); 

  int thenJump = emitJump(OP_JUMP_IF_FALSE);
  statement();

  patchJump(thenJump);
}

먼저 괄호로 묶인 조건식을 컴파일합니다. 런타임에 이로 인해 조건 값이 스택 맨 위에 남게 됩니다. 이 값을 사용하여 then 분기를 실행할지 건너뛸지 결정합니다.

그런 다음 새로운 OP_JUMP_IF_FALSE 명령어를 생성합니다. 이 명령어는 ip를 얼마나 오프셋할지—즉, 건너뛸 코드 바이트 수에 대한 피연산자(operand)를 가집니다. 조건이 거짓 같은 값(falsey)이면, ip를 그만큼 조정하여 건너뜁니다. 대략 다음과 같습니다:

하지만 문제가 있습니다. OP_JUMP_IF_FALSE 명령어의 피연산자를 작성할 때, 얼마나 멀리 점프해야 할지 어떻게 알 수 있을까요? 아직 then 분기를 컴파일하지 않았으므로, 얼마나 많은 바이트코드가 포함될지 알 수 없습니다.

이를 해결하기 위해 백패칭(backpatching)이라는 고전적인 트릭을 사용합니다. 먼저 점프 명령어를 자리 표시자 오프셋 피연산자와 함께 내보냅니다. 그리고 그 미완성 명령어의 위치를 추적합니다. 다음으로 then 본문을 컴파일합니다. 본문이 완료되면 얼마나 멀리 점프해야 할지 알게 됩니다. 그래서 돌아가서 그 자리 표시자 오프셋을 이제 계산할 수 있는 실제 값으로 교체합니다. 컴파일된 코드의 기존 천에 패치를 꿰매는 것과 비슷합니다.

이 트릭을 두 개의 헬퍼 함수에 인코딩합니다.

static int emitJump(uint8_t instruction) {
  emitByte(instruction);
  emitByte(0xff);
  emitByte(0xff);
  return currentChunk()->count - 2;
}

첫 번째 함수는 바이트코드 명령어를 내보내고 점프 오프셋에 대한 자리 표시자 피연산자를 작성합니다. 나중에 이 헬퍼를 사용하는 두 가지 다른 명령어가 있을 것이므로 opcode를 인수로 전달합니다. 점프 오프셋 피연산자에는 두 바이트를 사용합니다. 16비트 오프셋을 사용하면 최대 65,535바이트의 코드를 건너뛸 수 있으며, 이는 우리의 필요에 충분할 것입니다.

이 함수는 청크에서 내보낸 명령어의 오프셋을 반환합니다. then 분기를 컴파일한 후, 이 오프셋을 가져와 다음 함수에 전달합니다:

static void patchJump(int offset) {
  // 점프 오프셋 바이트코드 자체의 크기를 보정하기 위해 -2를 합니다.
  int jump = currentChunk()->count - offset - 2;

  if (jump > UINT16_MAX) {
    error("Too much code to jump over.");
  }

  currentChunk()->code[offset] = (jump >> 8) & 0xff;
  currentChunk()->code[offset + 1] = jump & 0xff;
}

이 함수는 바이트코드 내부로 돌아가서 주어진 위치의 피연산자를 계산된 점프 오프셋으로 교체합니다. 우리가 점프가 착지하기를 원하는 다음 명령어를 내보내기 직전에 patchJump()를 호출하여, 현재 바이트코드 카운트를 사용하여 얼마나 멀리 점프할지 결정합니다. if 문의 경우, 이는 then 분기를 컴파일한 직후이자 다음 문장을 컴파일하기 직전을 의미합니다.

컴파일 시점에는 이것으로 충분합니다. 이제 새로운 명령어를 정의해 보겠습니다.

  OP_PRINT,

  OP_JUMP_IF_FALSE,

  OP_RETURN,

VM에서는 다음과 같이 작동합니다:

        break;
      }

      case OP_JUMP_IF_FALSE: {
        uint16_t offset = READ_SHORT();
        if (isFalsey(peek(0))) vm.ip += offset;
        break;
      }

      case OP_RETURN: {

이것은 우리가 추가한 첫 번째 16비트 피연산자를 사용하는 명령어입니다. 청크에서 이를 읽기 위해 새로운 매크로를 사용합니다.

#define READ_CONSTANT() (vm.chunk->constants.values[READ_BYTE()])

#define READ_SHORT() \
    (vm.ip += 2, (uint16_t)((vm.ip[-2] << 8) | vm.ip[-1]))

#define READ_STRING() AS_STRING(READ_CONSTANT())

이는 청크에서 다음 두 바이트를 가져와 16비트 부호 없는 정수를 만듭니다. 늘 그렇듯이, 작업이 끝나면 매크로를 정리합니다.

#undef READ_BYTE

#undef READ_SHORT

#undef READ_CONSTANT

오프셋을 읽은 후, 스택 맨 위의 조건 값을 확인합니다. 만약 거짓 같은 값(falsey)이라면, 이 점프 오프셋을 ip에 적용합니다. 그렇지 않으면, ip를 그대로 두고 실행은 점프 명령어 다음의 다음 명령어로 자동으로 진행됩니다.

조건이 거짓 같은 값(falsey)인 경우, 다른 작업을 할 필요가 없습니다. ip를 오프셋했으므로, 외부 명령어 디스패치 루프가 다시 돌 때, then 분기의 모든 코드를 지나 새로운 명령어에서 실행을 재개할 것입니다.

점프 명령어는 스택에서 조건 값을 팝(pop)하지 않는다는 점에 유의하세요. 따라서 이로 인해 스택에 추가 값이 남아돌게 되므로, 여기서 완전히 끝난 것은 아닙니다. 곧 이를 정리할 것입니다. 잠시 무시하더라도, 이제 Lox에서 작동하는 if 문을 가지게 되었으며, VM 런타임에서 이를 지원하는 데 단 하나의 작은 명령어만 필요했습니다.

23 . 1 . 1Else 절

else 절을 지원하지 않는 if 문은 고메즈 없는 모티시아 아담스 같습니다. 따라서, then 분기를 컴파일한 후 else 키워드를 찾습니다. else 키워드를 찾으면, else 분기를 컴파일합니다.

  patchJump(thenJump);

  if (match(TOKEN_ELSE)) statement();

}

조건이 거짓 같은 값(falsey)이면 then 분기를 건너뛸 것입니다. else 분기가 있다면, ip는 그 코드의 시작 지점에 도달할 것입니다. 하지만 이것만으로는 충분하지 않습니다. 다음은 이로 인해 발생하는 흐름입니다:

조건이 참 같은 값(truthy)이면, 원하는 대로 then 분기를 실행합니다. 하지만 그 후에도 실행은 else 분기로 바로 이어집니다. 이런! 조건이 참이면, then 분기를 실행한 후에 else 분기를 건너뛰어야 합니다. 이렇게 해야 어떤 경우든 단일 분기만 실행하게 됩니다. 다음과 같이 말이죠:

이를 구현하려면 then 분기의 끝에서 다른 점프가 필요합니다.

  statement();

  int elseJump = emitJump(OP_JUMP);

  patchJump(thenJump);

이 오프셋은 else 본문의 끝에서 패치합니다.

  if (match(TOKEN_ELSE)) statement();

  patchJump(elseJump);

}

then 분기를 실행한 후, 이는 else 분기 다음의 다음 문장으로 점프합니다. 다른 점프와 달리, 이 점프는 무조건적입니다. 우리는 항상 이 점프를 사용하므로, 이를 표현하는 또 다른 명령어가 필요합니다.

  OP_PRINT,

  OP_JUMP,

  OP_JUMP_IF_FALSE,

다음과 같이 해석합니다:

        break;
      }

      case OP_JUMP: {
        uint16_t offset = READ_SHORT();
        vm.ip += offset;
        break;
      }

      case OP_JUMP_IF_FALSE: {

여기서도 특별히 놀라운 점은 없습니다—유일한 차이점은 조건을 확인하지 않고 항상 오프셋을 적용한다는 것입니다.

이제 then 및 else 분기가 작동하므로 거의 다 되었습니다. 마지막으로 스택에 남겨두었던 조건 값을 정리해야 합니다. 기억하세요, 각 문장은 스택 효과가 0이어야 합니다—문장 실행이 완료된 후 스택은 이전과 동일한 높이여야 합니다.

OP_JUMP_IF_FALSE 명령어가 조건 자체를 팝하도록 할 수도 있지만, 곧 논리 연산자에서는 조건을 팝하지 않아야 하므로 동일한 명령어를 사용할 것입니다. 대신, if 문을 컴파일할 때 컴파일러가 두 개의 명시적인 OP_POP 명령어를 내보내도록 할 것입니다. 생성된 코드를 통한 모든 실행 경로가 조건을 팝하도록 주의해야 합니다.

조건이 참 같은 값(truthy)이면, then 분기 내부 코드 직전에 팝합니다.

  int thenJump = emitJump(OP_JUMP_IF_FALSE);

  emitByte(OP_POP);

  statement();

그렇지 않으면, else 분기 시작 시 팝합니다.

  patchJump(thenJump);

  emitByte(OP_POP);

  if (match(TOKEN_ELSE)) statement();

이 작은 명령은 또한 사용자가 else 절을 작성하지 않았더라도 모든 if 문이 암묵적인 else 분기를 가진다는 것을 의미합니다. 사용자가 생략한 경우, 이 분기는 조건 값을 버리는 역할만 합니다.

완전히 올바른 흐름은 다음과 같습니다:

따라가 보면, 항상 단일 분기를 실행하고 조건이 먼저 팝되는 것을 확인할 수 있습니다. 남은 것은 작은 디스어셈블러(disassembler) 지원뿐입니다.

      return simpleInstruction("OP_PRINT", offset);

    case OP_JUMP:
      return jumpInstruction("OP_JUMP", 1, chunk, offset);
    case OP_JUMP_IF_FALSE:
      return jumpInstruction("OP_JUMP_IF_FALSE", 1, chunk, offset);

    case OP_RETURN:

이 두 명령어는 16비트 피연산자를 사용하는 새로운 형식이므로, 이를 디스어셈블하는 새로운 유틸리티 함수를 추가합니다.

static int jumpInstruction(const char* name, int sign,
                           Chunk* chunk, int offset) {
  uint16_t jump = (uint16_t)(chunk->code[offset + 1] << 8);
  jump |= chunk->code[offset + 2];
  printf("%-16s %4d -> %d\n", name, offset,
         offset + 3 + sign * jump);
  return offset + 3;
}

자, 하나의 완전한 제어 흐름 구조가 완성되었습니다. 만약 이것이 80년대 영화였다면, 몽타주 음악이 흘러나오고 나머지 제어 흐름 구문은 저절로 해결되었을 것입니다. 아쉽게도 80년대는 오래전에 지났으므로, 우리는 직접 해결해야 합니다.

23 . 2논리 연산자

jlox에서 기억하실지 모르겠지만, 논리 연산자 and와 or는 +와 -와 같은 또 다른 이항 연산자가 아닙니다. 이들은 단락 평가(short-circuit)를 수행하며, 왼쪽 피연산자의 값에 따라 오른쪽 피연산자를 평가하지 않을 수 있기 때문에 제어 흐름 표현식처럼 작동합니다.

기본적으로 else 절이 있는 if 문에 대한 약간의 변형입니다. 이를 설명하는 가장 쉬운 방법은 컴파일러 코드와 결과 바이트코드에서 생성되는 제어 흐름을 보여주는 것입니다. and부터 시작하여, 표현식 파싱 테이블에 다음과 같이 연결합니다:

  [TOKEN_NUMBER]        = {number,   NULL,   PREC_NONE},

  [TOKEN_AND]           = {NULL,     and_,   PREC_AND},

  [TOKEN_CLASS]         = {NULL,     NULL,   PREC_NONE},

이것은 새로운 파서 함수로 연결됩니다.

static void and_(bool canAssign) {
  int endJump = emitJump(OP_JUMP_IF_FALSE);

  emitByte(OP_POP);
  parsePrecedence(PREC_AND);

  patchJump(endJump);
}

이 함수가 호출되는 시점에는 왼쪽 피연산자 표현식이 이미 컴파일된 상태입니다. 즉, 런타임에는 그 값이 스택 맨 위에 있을 것입니다. 만약 그 값이 거짓 같은 값(falsey)이라면, 전체 and 표현식이 거짓임이 분명하므로, 오른쪽 피연산자를 건너뛰고 왼쪽 피연산자 값을 전체 표현식의 결과로 남겨둡니다. 그렇지 않으면, 왼쪽 피연산자 값을 버리고 오른쪽 피연산자를 평가하며, 그 값이 전체 and 표현식의 결과가 됩니다.

저 네 줄의 코드가 정확히 그 기능을 수행합니다. 흐름은 다음과 같습니다:

이제 OP_JUMP_IF_FALSE가 스택 맨 위에 값을 남겨두는 이유를 알 수 있습니다. and의 왼쪽 피연산자가 거짓 같은 값(falsey)일 때, 그 값이 전체 표현식의 결과로 남게 됩니다.

23 . 2 . 1논리 OR 연산자

or 연산자는 조금 더 복잡합니다. 먼저 파싱 테이블에 추가합니다.

  [TOKEN_NIL]           = {literal,  NULL,   PREC_NONE},

  [TOKEN_OR]            = {NULL,     or_,    PREC_OR},

  [TOKEN_PRINT]         = {NULL,     NULL,   PREC_NONE},

파서가 중위(infix) or 토큰을 인식하면, 다음 함수를 호출합니다:

static void or_(bool canAssign) {
  int elseJump = emitJump(OP_JUMP_IF_FALSE);
  int endJump = emitJump(OP_JUMP);

  patchJump(elseJump);
  emitByte(OP_POP);

  parsePrecedence(PREC_OR);
  patchJump(endJump);
}

or 표현식에서 왼쪽 피연산자가 참 같은 값(truthy)이면, 오른쪽 피연산자를 건너뜁니다. 따라서 값이 참 같은 값일 때 점프해야 합니다. 별도의 명령어를 추가할 수도 있지만, 컴파일러가 언어의 의미를 원하는 명령어 시퀀스로 자유롭게 매핑할 수 있음을 보여주기 위해, 이미 가지고 있는 점프 명령어들을 사용하여 구현했습니다.

왼쪽 피연산자가 거짓 같은 값(falsey)일 때는 다음 문장을 건너뛰는 작은 점프를 합니다. 그 문장은 오른쪽 피연산자 코드를 건너뛰는 무조건적인 점프입니다. 이 작은 동작은 값이 참 같은 값일 때 효과적으로 점프를 수행합니다. 흐름은 다음과 같습니다:

솔직히 말하면, 이것이 최선의 방법은 아닙니다. 디스패치할 명령어가 더 많고 오버헤드가 더 큽니다. or가 and보다 느릴 이유가 없는데도 말이죠. 하지만 새로운 명령어를 추가하지 않고 두 연산자를 모두 구현할 수 있다는 점은 꽤 재미있습니다. 제 관용을 용서해 주십시오.

좋습니다. 이것이 Lox의 세 가지 분기(branching) 구조입니다. 즉, 이들은 코드를 앞으로만 건너뛰는 제어 흐름 기능입니다. 다른 언어에는 종종 switch와 같은 다중 분기 문이나 ?:와 같은 조건부 표현식이 있지만, Lox는 단순하게 유지합니다.

23 . 3While 문

이제 반복(looping) 문으로 넘어갑니다. 이는 코드를 두 번 이상 실행할 수 있도록 뒤로 점프합니다. Lox에는 while과 for 두 가지 반복 구조만 있습니다. while 반복문이 (훨씬) 간단하므로, 여기서부터 시작합니다.

    ifStatement();

  } else if (match(TOKEN_WHILE)) {
    whileStatement();

  } else if (match(TOKEN_LEFT_BRACE)) {

while 토큰에 도달하면 다음을 호출합니다:

static void whileStatement() {
  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'while'.");
  expression();
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after condition.");

  int exitJump = emitJump(OP_JUMP_IF_FALSE);
  emitByte(OP_POP);
  statement();

  patchJump(exitJump);
  emitByte(OP_POP);
}

이것의 대부분은 if 문을 반영합니다—필수 괄호로 둘러싸인 조건식을 컴파일합니다. 그 다음에는 조건이 거짓 같은 값(falsey)일 경우 뒤따르는 본문 문장을 건너뛰는 점프 명령어가 옵니다.

본문을 컴파일한 후에 점프를 패치하고, 어느 경로든 스택에서 조건 값을 팝하도록 주의합니다. if 문과의 유일한 차이점은 반복입니다. 이것은 다음과 같습니다:

  statement();

  emitLoop(loopStart);

  patchJump(exitJump);

본문 후에 "반복(loop)" 명령어를 내보내기 위해 이 함수를 호출합니다. 이 명령어는 얼마나 뒤로 점프해야 하는지 알아야 합니다. 앞으로 점프할 때는, 점프 명령어를 내보내기 전까지 얼마나 멀리 점프할지 몰랐기 때문에 명령어를 두 단계로 내보내야 했습니다. 지금은 그 문제가 없습니다. 우리가 점프하려는 코드의 지점은 이미 컴파일되었습니다—조건식 바로 앞입니다.

우리가 해야 할 일은 컴파일할 때 그 위치를 포착하는 것뿐입니다.

static void whileStatement() {

  int loopStart = currentChunk()->count;

  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'while'.");

while 루프의 본문을 실행한 후, 우리는 조건식 바로 앞까지 완전히 되돌아갑니다. 이렇게 하면 각 반복마다 조건식을 다시 평가합니다. 우리는 청크의 현재 명령어 카운트를 loopStart에 저장하여 컴파일할 조건식 바로 앞의 바이트코드 오프셋을 기록합니다. 그런 다음 이 헬퍼 함수에 전달합니다:

static void emitLoop(int loopStart) {
  emitByte(OP_LOOP);

  int offset = currentChunk()->count - loopStart + 2;
  if (offset > UINT16_MAX) error("Loop body too large.");

  emitByte((offset >> 8) & 0xff);
  emitByte(offset & 0xff);
}

이것은 emitJump()와 patchJump()를 합쳐놓은 것과 비슷합니다. 새로운 반복(loop) 명령어를 내보내며, 주어진 오프셋만큼 뒤로 무조건 점프합니다. 점프 명령어와 마찬가지로, 그 뒤에는 16비트 피연산자가 옵니다. 우리는 현재 명령어 위치부터 점프하려는 loopStart 지점까지의 오프셋을 계산합니다. + 2는 OP_LOOP 명령어 자체의 피연산자 크기를 고려하여 우리가 건너뛰어야 하는 부분입니다.

VM의 관점에서는 OP_LOOP와 OP_JUMP 사이에 의미론적인 차이는 없습니다. 둘 다 단순히 ip에 오프셋을 더합니다. 우리는 둘 모두에 하나의 명령어를 사용하고 부호 있는 오프셋 피연산자를 줄 수도 있었을 것입니다. 하지만 부호 있는 16비트 정수를 두 바이트로 수동으로 패킹하는 데 필요한 성가신 비트 조작을 피하는 것이 좀 더 쉽다고 생각했고, opcode 공간도 충분하므로 사용하지 않을 이유가 없다고 생각했습니다.

새로운 명령어는 여기에 있습니다:

  OP_JUMP_IF_FALSE,

  OP_LOOP,

  OP_RETURN,

그리고 VM에서는 다음과 같이 구현합니다:

      }

      case OP_LOOP: {
        uint16_t offset = READ_SHORT();
        vm.ip -= offset;
        break;
      }

      case OP_RETURN: {

OP_JUMP와의 유일한 차이점은 덧셈 대신 뺄셈이라는 것입니다. 디스어셈블리도 비슷합니다.

      return jumpInstruction("OP_JUMP_IF_FALSE", 1, chunk, offset);

    case OP_LOOP:
      return jumpInstruction("OP_LOOP", -1, chunk, offset);

    case OP_RETURN:

이것이 우리의 while 문입니다. 두 개의 점프를 포함합니다—조건이 충족되지 않을 때 루프를 벗어나기 위한 조건부 전방 점프와 본문을 실행한 후 무조건 후방으로 반복하는 점프입니다. 흐름은 다음과 같습니다:

23 . 4For 문

Lox의 또 다른 반복문은 C에서 상속받은 유서 깊은 for 반복문입니다. while 반복문에 비해 훨씬 더 많은 것이 진행됩니다. 세 가지 절을 가지며, 이들은 모두 선택 사항입니다:

• 초기화 구문(initializer)은 변수 선언이거나 표현식일 수 있습니다. 이는 문장의 시작 부분에서 한 번 실행됩니다.

• 조건 구문(condition clause)은 표현식입니다. while 반복문처럼, 거짓 같은 값으로 평가되면 반복을 종료합니다.

• 증감 표현식(increment expression)은 각 반복의 끝에서 한 번 실행됩니다.

jlox에서는 파서가 for 반복문을, 앞에 몇 가지 추가 사항과 본문 끝에 추가 사항이 있는 while 반복문의 합성 AST로 desugar했습니다. 우리는 비슷한 방식으로 진행할 것이지만, AST와 같은 것을 거치지는 않을 것입니다. 대신, 우리의 바이트코드 컴파일러는 이미 가지고 있는 점프 및 반복 명령어를 사용할 것입니다.

for 키워드부터 시작하여 한 번에 한 조각씩 구현을 진행해 나갈 것입니다.

    printStatement();

  } else if (match(TOKEN_FOR)) {
    forStatement();

  } else if (match(TOKEN_IF)) {

이것은 헬퍼 함수를 호출합니다. 만약 for (;;)와 같이 빈 절을 가진 for 루프만 지원한다면, 다음과 같이 구현할 수 있습니다:

static void forStatement() {
  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'for'.");
  consume(TOKEN_SEMICOLON, "Expect ';'.");

  int loopStart = currentChunk()->count;
  consume(TOKEN_SEMICOLON, "Expect ';'.");
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after for clauses.");

  statement();
  emitLoop(loopStart);
}

위쪽에는 여러 개의 필수 구두점이 있습니다. 그런 다음 본문을 컴파일합니다. while 루프에서 했던 것처럼, 본문 상단의 바이트코드 오프셋을 기록하고 그 후에 해당 지점으로 돌아가는 루프를 내보냅니다. 이제 무한 루프의 작동 구현을 갖게 되었습니다.

23 . 4 . 1초기화 구문

이제 첫 번째 구문인 초기화 구문을 추가하겠습니다. 이 구문은 본문 전에 한 번만 실행되므로 컴파일이 간단합니다.

  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'for'.");

  if (match(TOKEN_SEMICOLON)) {
    // 초기화 구문 없음.
  } else if (match(TOKEN_VAR)) {
    varDeclaration();
  } else {
    expressionStatement();
  }

  int loopStart = currentChunk()->count;

변수 선언이나 표현식 중 하나를 허용하므로 구문이 약간 복잡합니다. var 키워드의 존재 여부로 어떤 유형인지 구별합니다. 표현식의 경우, expression() 대신 expressionStatement()를 호출합니다. 이는 세미콜론을 찾는데, 여기서도 필요하며, 값을 버리기 위한 OP_POP 명령어도 내보냅니다. 초기화 구문이 스택에 어떤 것도 남기지 않기를 원합니다.

for 문이 변수를 선언하는 경우, 해당 변수는 루프 본문으로 범위가 지정되어야 합니다. 우리는 전체 문장을 스코프로 감싸서 이를 보장합니다.

static void forStatement() {

  beginScope();

  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'for'.");

그런 다음 끝에서 닫습니다.

  emitLoop(loopStart);

  endScope();

}

23 . 4 . 2조건 구문

다음은 루프를 종료하는 데 사용될 수 있는 조건식입니다.

  int loopStart = currentChunk()->count;

  int exitJump = -1;
  if (!match(TOKEN_SEMICOLON)) {
    expression();
    consume(TOKEN_SEMICOLON, "Expect ';' after loop condition.");

    // 조건이 거짓이면 루프를 빠져나갑니다.
    exitJump = emitJump(OP_JUMP_IF_FALSE);
    emitByte(OP_POP); // 조건.
  }

  consume(TOKEN_RIGHT_PAREN, "Expect ')' after for clauses.");

이 절은 선택 사항이므로, 실제로 존재하는지 확인해야 합니다. 만약 이 절이 생략되었다면, 다음 토큰은 세미콜론이어야 하므로, 이를 통해 파악합니다. 세미콜론이 없다면, 조건식이 있어야 합니다.

이 경우, 이를 컴파일합니다. 그런 다음, while과 마찬가지로, 조건이 거짓 같은 값(falsey)이면 루프를 종료하는 조건부 점프를 내보냅니다. 점프는 값을 스택에 남기므로, 본문을 실행하기 전에 팝합니다. 이는 조건이 참일 때 값을 버리도록 보장합니다.

루프 본문 후에 그 점프를 패치해야 합니다.

  emitLoop(loopStart);

  if (exitJump != -1) {
    patchJump(exitJump);
    emitByte(OP_POP); // 조건.
  }

  endScope();
}

이것은 조건 구문이 있을 때만 수행합니다. 만약 조건 구문이 없다면, 패치할 점프도 없고 스택에 팝할 조건 값도 없습니다.

23 . 4 . 3증감 구문

가장 중요한 증감 구문은 마지막에 남겨두었습니다. 꽤 복잡합니다. 텍스트상으로는 본문 앞에 나타나지만, 본문 실행 후에 실행됩니다. 만약 AST로 파싱하고 별도의 패스에서 코드를 생성했다면, for 문 AST의 본문 필드를 증감 구문보다 먼저 순회하여 컴파일할 수 있었을 것입니다.

불행히도, 우리 컴파일러는 코드를 한 번만 지나가기 때문에 증감 구문을 나중에 컴파일할 수 없습니다. 대신, 증감 구문을 건너뛰고, 본문을 실행한 다음, 증감 구문으로 다시 점프하여 실행하고, 다음 반복으로 넘어갈 것입니다.

조금 이상하게 들리겠지만, C에서 AST를 메모리에서 수동으로 관리하는 것보다는 낫겠죠? 코드는 다음과 같습니다:

  }

  if (!match(TOKEN_RIGHT_PAREN)) {
    int bodyJump = emitJump(OP_JUMP);
    int incrementStart = currentChunk()->count;
    expression();
    emitByte(OP_POP);
    consume(TOKEN_RIGHT_PAREN, "Expect ')' after for clauses.");

    emitLoop(loopStart);
    loopStart = incrementStart;
    patchJump(bodyJump);
  }

  statement();

다시 말하지만, 선택 사항입니다. 이 절이 마지막 절이므로, 생략될 경우 다음 토큰은 닫는 괄호가 될 것입니다. 증감 구문이 있다면, 지금 컴파일해야 하지만 아직 실행되어서는 안 됩니다. 따라서 먼저, 증감 구문의 코드를 건너뛰고 루프 본문으로 넘어가는 무조건 점프를 내보냅니다.

다음으로, 증감 표현식 자체를 컴파일합니다. 이것은 보통 할당(assignment)입니다. 무엇이든, 우리는 단지 부수 효과(side effect)를 위해 실행하므로, 그 값을 버리기 위해 팝 명령어도 내보냅니다.

마지막 부분은 조금 까다롭습니다. 먼저 반복 명령어를 내보냅니다. 이것은 for 루프의 맨 위—조건식이 있다면 조건식 바로 앞—으로 돌아가는 주 반복입니다. 이 반복은 증감 구문 바로 다음에 발생하는데, 이는 증감 구문이 각 루프 반복의 끝에서 실행되기 때문입니다.

그런 다음 loopStart를 증감 표현식이 시작되는 오프셋을 가리키도록 변경합니다. 나중에 본문 문장 뒤에 반복 명령어를 내보낼 때, 이것은 증감 구문이 없을 때처럼 루프의 맨 위로 점프하는 대신 증감 표현식으로 점프하게 할 것입니다. 이것이 본문 실행 후에 증감 구문을 실행하도록 하는 방법입니다.

복잡하지만, 모든 것이 잘 작동합니다. 모든 절을 포함하는 완전한 루프는 다음과 같은 흐름으로 컴파일됩니다:

jlox에서 for 루프를 구현할 때와 마찬가지로, 런타임을 건드릴 필요가 없었습니다. 모든 것이 VM이 이미 지원하는 원시적인 제어 흐름 연산으로 컴파일됩니다. 이 장에서 우리는 큰 도약을 이루었습니다—clox는 이제 튜링 완전(Turing complete)합니다. 또한 세 가지 문장과 두 가지 표현식 형태라는 꽤 많은 새로운 구문을 다루었습니다. 그럼에도 불구하고, 단 세 가지 새로운 간단한 명령어만 필요했습니다. 이는 우리 VM 아키텍처에 대한 노력 대비 보상이 상당히 좋습니다.

// 매트릭스에 0이 포함되어 있는지 확인합니다.
bool found = false;
for (int x = 0; x < xSize; x++) {
  for (int y = 0; y < ySize; y++) {
    for (int z = 0; z < zSize; z++) {
      if (matrix[x][y][z] == 0) {
        printf("found");
        found = true;
        break;
      }
    }
    if (found) break;
  }
  if (found) break;
}

for (int x = 0; x < xSize; x++) {
  for (int y = 0; y < ySize; y++) {
    for (int z = 0; z < zSize; z++) {
      if (matrix[x][y][z] == 0) {
        printf("found");
        goto done;
      }
    }
  }
}
done: