변수 확인 및 바인딩

가끔은 묘한 상황에 처하게 됩니다. 점진적으로, 아주 자연스럽게 그 상황에 발을 들여놓지만, 막상 그 한가운데 서게 되면 갑자기 깜짝 놀라며 대체 어떻게 이런 일이 벌어졌는지 자문하게 됩니다.

토르 헤이에르달, 콘티키

아, 이런! 우리 언어 구현이 물에 잠기고 있습니다! 변수와 블록을 추가했을 때만 해도 스코프는 깔끔하게 처리되고 있었습니다. 하지만 나중에 클로저를 추가하면서, 이전에 완벽했던 인터프리터에 구멍이 생겨버렸습니다. 대부분의 실제 프로그램은 이 구멍을 통해 문제를 일으킬 가능성이 낮지만, 언어 구현자로서 우리는 의미론의 가장 깊고 습한 부분까지 정확성에 신경 쓰겠다는 신성한 맹세를 합니다.

이 장 전체를 통해 이 누수를 탐색하고, 조심스럽게 메워 나갈 것입니다. 이 과정에서 Lox 및 C 계열 언어에서 사용되는 렉시컬 스코프에 대해 더 엄밀한 이해를 얻게 될 것입니다. 또한 사용자 소스 코드를 실행하지 않고도 그 의미를 추출하는 강력한 기법인 의미 분석(semantic analysis)—에 대해서도 배울 기회를 얻게 될 것입니다.

11 . 1정적 스코프

간단히 복습해봅시다. Lox는 대부분의 현대 언어와 마찬가지로 렉시컬(lexical) 스코프를 사용합니다. 즉, 프로그램 텍스트를 읽는 것만으로도 변수 이름이 어떤 선언을 참조하는지 파악할 수 있다는 뜻입니다. 예를 들어:

var a = "outer";
{
  var a = "inner";
  print a;
}

여기서 출력되는 a가 바로 이전 줄에 선언된 변수이며, 전역 변수가 아니라는 것을 우리는 알고 있습니다. 프로그램을 실행하는 것은 이것에 영향을 미치지 않으며—미칠 수 없습니다—. 스코프 규칙은 언어의 정적(static) 의미론의 일부이며, 그렇기 때문에 정적 스코프(static scope)라고도 불립니다.

저는 아직 이 스코프 규칙들을 자세히 설명하지 않았지만, 이제는 정확하게 다룰 시간입니다.

변수 사용은 해당 변수가 사용된 표현식을 감싸는 가장 안쪽 스코프에서 같은 이름으로 선언된 앞선 선언을 참조합니다.

이 문장에는 풀어야 할 내용이 많습니다:

• “변수 표현식(variable expression)” 대신 “변수 사용(variable usage)”이라고 말한 것은 변수 표현식과 할당 모두를 포함하기 위함입니다. “변수가 사용된 표현식”도 마찬가지입니다.

• “앞선(preceding)”은 프로그램 텍스트에서 먼저 나타난다는 의미입니다.

  var a = "outer";
  {
    print a;
    var a = "inner";
  }
  

  여기서 출력되는 a는 이를 사용하는 print 문장 보다 먼저 나타나기 때문에 바깥쪽 a입니다. 대부분의 경우, 직선적인 코드에서는 텍스트상 먼저 선언된 것이 시간상으로도 먼저 사용됩니다. 하지만 항상 그런 것은 아닙니다. 살펴보겠지만, 함수는 코드 덩어리를 지연시켜 동적인 시간적(dynamic temporal) 실행이 더 이상 정적인 텍스트적(static textual) 순서를 반영하지 않게 만들 수 있습니다.

• “가장 안쪽(innermost)”이라는 표현은 우리의 친한 친구인 섀도잉(shadowing) 때문에 존재합니다. 다음과 같이 바깥 스코프에 주어진 이름과 같은 이름의 변수가 여러 개 있을 수 있습니다:

  var a = "outer";
  {
    var a = "inner";
    print a;
  }
  

  우리의 규칙은 가장 안쪽 스코프가 우선한다고 말함으로써 이 경우를 명확하게 구분합니다.

이 규칙은 어떤 런타임 동작에 대해서도 언급하지 않으므로, 변수 표현식이 프로그램 실행 전체 동안 항상 동일한 선언을 참조한다는 것을 의미합니다. 지금까지 우리의 인터프리터는 이 규칙을 대부분 올바르게 구현했습니다. 하지만 클로저를 추가하면서 오류가 슬그머니 들어왔습니다.

var a = "global";
{
  fun showA() {
    print a;
  }

  showA();
  var a = "block";
  showA();
}

이 코드를 입력하고 실행하기 전에, 무엇이 출력되어야 한다고 생각하는지 결정해보세요.

자 . . . 결정하셨나요? 다른 언어의 클로저에 익숙하다면, "global"이 두 번 출력될 것이라고 예상할 겁니다. 첫 번째 showA() 호출은 아직 내부 a의 선언에 도달하지 않았으므로 분명히 "global"을 출력해야 합니다. 그리고 변수 표현식이 항상 동일한 변수로 확인된다는 우리 규칙에 따르면, 두 번째 showA() 호출도 같은 것을 출력해야 합니다.

하지만, 실제로는 다음과 같이 출력됩니다:

global
block

이 프로그램은 어떤 변수도 재할당하지 않으며 단 하나의 print 문만 포함한다는 점을 강조하고 싶습니다. 그런데도 어찌 된 일인지, 한 번도 할당되지 않은 변수를 위한 print 문이 서로 다른 시점에 두 가지 다른 값을 출력합니다. 우리는 어딘가에서 분명히 무언가를 망가뜨렸습니다.

11 . 1 . 1스코프와 가변 환경

우리 인터프리터에서 환경(environment)은 정적 스코프의 동적 표현입니다. 둘은 대체로 서로 동기화된 상태를 유지합니다—새로운 스코프에 진입할 때 새 환경을 생성하고, 스코프를 벗어날 때 환경을 폐기합니다. 환경에 대해 우리가 수행하는 또 다른 작업이 하나 있는데, 바로 환경 안에 변수를 바인딩하는 것입니다. 버그는 여기에 있습니다.

문제를 일으킨 예제를 단계별로 살펴보며 각 단계에서 환경이 어떻게 보이는지 확인해봅시다. 먼저, 전역 스코프에 a를 선언합니다.

그러면 하나의 변수만 포함된 단일 환경이 만들어집니다. 그 다음 블록에 진입하여 showA()의 선언을 실행합니다.

블록을 위한 새로운 환경이 생성됩니다. 그 환경에서 우리는 showA라는 이름을 선언하는데, 이는 함수를 나타내기 위해 생성한 LoxFunction 객체에 바인딩됩니다. 이 객체는 함수가 선언된 환경을 캡처하는 closure 필드를 가지고 있으므로, 블록을 위한 환경을 다시 참조하게 됩니다.

이제 showA()를 호출합니다.

인터프리터는 showA() 함수의 본문을 위한 새로운 환경을 동적으로 생성합니다. 이 함수는 변수를 선언하지 않으므로 환경은 비어 있습니다. 이 환경의 부모는 함수의 클로저—즉, 바깥쪽 블록 환경입니다.

showA()의 본문 안에서 우리는 a의 값을 출력합니다. 인터프리터는 환경 체인을 따라 이 값을 찾습니다. 전역 환경에 도달해서야 a를 찾고 "global"을 출력합니다. 좋습니다.

다음으로, 이번에는 블록 내부에 두 번째 a를 선언합니다.

이는 showA()와 같은 블록—같은 스코프—에 있으므로, 같은 환경으로 들어갑니다. 이 환경은 showA()의 클로저가 참조하는 환경과 동일합니다. 여기서부터 흥미로워집니다. showA()를 다시 호출합니다.

우리는 showA()의 본문을 위해 다시 새로운 빈 환경을 생성하고, 그 클로저에 연결한 다음, 본문을 실행합니다. 인터프리터가 a를 찾기 위해 환경 체인을 탐색할 때, 이제 블록 환경에서 새로운 a를 발견하게 됩니다. 이런.

저는 스코프에 대한 여러분의 비공식적인 직관과 일치하기를 바라는 방식으로 환경을 구현했습니다. 우리는 블록 내의 모든 코드가 같은 스코프 내에 있다고 생각하는 경향이 있으며, 따라서 우리 인터프리터는 이를 나타내기 위해 단일 환경을 사용합니다. 각 환경은 변경 가능한 해시 테이블입니다. 새로운 지역 변수가 선언되면, 해당 스코프에 대한 기존 환경에 추가됩니다.

그 직관은, 인생의 많은 것들과 마찬가지로, 완전히 옳지는 않습니다. 블록이 반드시 모두 같은 스코프인 것은 아닙니다. 다음을 고려해보세요:

{
  var a;
  // 1.
  var b;
  // 2.
}

첫 번째 표시된 줄에서는 a만 스코프 내에 있습니다. 두 번째 줄에서는 a와 b 모두 스코프 내에 있습니다. "스코프"를 선언들의 집합으로 정의한다면, 이들은 분명히 같은 스코프가 아닙니다—동일한 선언을 포함하지 않으니까요. 마치 각 var 문이 블록을 두 개의 분리된 스코프로 나누는 것과 같습니다. 변수가 선언되기 전의 스코프와 그 이후의 스코프(새 변수를 포함하는)로 말이죠.

하지만 우리 구현에서는 환경이 마치 전체 블록이 하나의 스코프인 것처럼 동작하며, 단지 시간이 지남에 따라 변하는 스코프일 뿐입니다. 클로저는 이를 좋아하지 않습니다. 함수가 선언될 때, 함수는 현재 환경에 대한 참조를 캡처합니다. 함수는 함수가 선언된 순간 존재했던 환경의 고정된 스냅샷을 캡처해야 합니다. 하지만 대신, Java 코드에서는 실제 변경 가능한 환경 객체에 대한 참조를 가지고 있습니다. 나중에 해당 환경에 해당하는 스코프에서 변수가 선언되면, 해당 선언이 함수보다 먼저 나타나지 않았음에도 불구하고 클로저는 새 변수를 보게 됩니다.

11 . 1 . 2영속적인 환경

영속적인 데이터 구조(persistent data structures)라고 불리는 것을 사용하는 프로그래밍 스타일이 있습니다. 명령형 프로그래밍에서 익숙한 가변(squishy) 데이터 구조와 달리, 영속적인 데이터 구조는 직접 수정될 수 없습니다. 대신, 기존 구조에 대한 어떤 "수정"이든 원래의 모든 데이터와 새로운 수정 사항을 포함하는 새로운 객체를 생성합니다. 원본은 변경되지 않은 상태로 남습니다.

만약 이 기법을 Environment에 적용한다면, 변수를 선언할 때마다 이전에 선언된 모든 변수와 새 변수 하나를 포함하는 새로운 환경을 반환할 것입니다. 변수를 선언하는 것은 변수가 선언되기 전과 후의 환경이 나뉘는 암묵적인 "분할"을 수행하게 됩니다:

클로저는 함수가 선언될 당시 활성화된 Environment 인스턴스에 대한 참조를 유지합니다. 해당 블록에서 나중에 선언된 변수들은 새로운 Environment 객체를 생성할 것이므로, 클로저는 새 변수를 보지 못하고 우리의 버그는 해결될 것입니다.

이것은 문제를 해결하는 합법적인 방법이며, Scheme 인터프리터에서 환경을 구현하는 전통적인 방식입니다. Lox에서도 그렇게 할 수 있지만, 기존 코드를 대량으로 수정해야 한다는 의미가 됩니다.

저는 여러분을 그 복잡한 과정으로 끌고 가지 않을 것입니다. 우리는 환경을 나타내는 방식을 그대로 유지할 것입니다. 데이터를 더 정적으로 구조화하는 대신, 정적 변수 확인(static resolution)을 접근 작업 자체에 포함시킬 것입니다.

11 . 2의미 분석

우리 인터프리터는 변수 표현식이 평가될 때마다 변수를 확인(resolves)합니다—즉, 어떤 선언을 참조하는지 추적합니다. 만약 그 변수가 천 번 실행되는 루프 안에 있다면, 그 변수는 천 번 다시 확인됩니다.

우리는 정적 스코프가 변수 사용이 항상 동일한 선언으로 확인되며, 이는 텍스트만 보고도 결정될 수 있다는 것을 알고 있습니다. 그렇다면 왜 매번 동적으로 이 작업을 수행할까요? 그렇게 하는 것은 우리의 성가신 버그로 이어지는 구멍을 열 뿐만 아니라, 불필요하게 느리기도 합니다.

더 나은 해결책은 각 변수 사용을 한 번만 확인하는 것입니다. 사용자 프로그램을 검사하고, 언급된 모든 변수를 찾아 각각이 어떤 선언을 참조하는지 파악하는 코드 덩어리를 작성하는 것이죠. 이 과정은 의미 분석(semantic analysis)의 한 예입니다. 파서가 프로그램이 문법적으로 올바른지 여부만을 알려주는 (구문 분석(syntactic)) 반면, 의미 분석은 더 나아가 프로그램의 각 부분이 실제로 무엇을 의미하는지 파악하기 시작합니다. 이 경우, 우리의 분석은 변수 바인딩을 확인할 것입니다. 우리는 어떤 표현식이 변수 인지 뿐만 아니라, 어떤 변수인지 알게 될 것입니다.

변수와 그 선언 간의 바인딩을 저장할 수 있는 방법은 여러 가지가 있습니다. Lox용 C 인터프리터에 도달하면 지역 변수를 저장하고 접근하는 훨씬 더 효율적인 방법을 갖게 될 것입니다. 하지만 jlox의 경우, 기존 코드베이스에 가하는 부수적인 피해를 최소화하고 싶습니다. 대부분 괜찮은 코드를 많이 버리는 것을 원치 않습니다.

대신, 기존 Environment 클래스를 최대한 활용하는 방식으로 변수 확인 정보를 저장할 것입니다. 문제 예제에서 a에 대한 접근이 어떻게 해석되었는지 기억해봅시다.

첫 번째 (올바른) 평가에서는 전역 a 선언을 찾기 전에 체인에서 세 개의 환경을 살펴봅니다. 그 다음, 안쪽 a가 나중에 블록 스코프에서 선언될 때, 전역 a를 섀도잉합니다.

다음 조회는 체인을 따라가서 두 번째 환경에서 a를 찾고 그곳에서 멈춥니다. 각 환경은 변수가 선언되는 단일 렉시컬 스코프에 해당합니다. 만약 변수 조회가 항상 환경 체인에서 동일한 수의 링크를 따라가도록 보장할 수 있다면, 매번 동일한 스코프에서 동일한 변수를 찾도록 보장할 수 있을 것입니다.

변수 사용을 "확인(resolve)"하려면, 선언된 변수가 환경 체인에서 얼마나 많은 "홉(hops)" 떨어져 있는지 계산하기만 하면 됩니다. 흥미로운 질문은 이 계산을 언제 수행할 것인가—다시 말해, 인터프리터 구현의 어느 부분에 이 코드를 넣을 것인가 하는 것입니다.

우리는 소스 코드의 구조에 기반한 정적 속성을 계산하고 있으므로, 명백한 답은 파서 안에 있습니다. 그것이 전통적인 위치이며, 나중에 clox에서 그렇게 구현할 것입니다. 여기서도 작동하겠지만, 저는 다른 기술을 보여드리고 싶습니다. 우리의 리졸버를 별도의 패스로 작성할 것입니다.

11 . 2 . 1변수 확인 패스

파서가 구문 트리를 생성한 후, 인터프리터가 실행을 시작하기 전에, 우리는 트리를 한 번 순회하여 포함된 모든 변수를 확인할 것입니다. 파싱과 실행 사이에 추가적인 패스를 두는 것은 흔한 일입니다. 만약 Lox에 정적 타입이 있었다면, 우리는 타입 검사기를 그 사이에 끼워 넣을 수 있었을 것입니다. 최적화 역시 종종 이와 같은 별도의 패스로 구현됩니다. 기본적으로 런타임에만 사용 가능한 상태에 의존하지 않는 모든 작업은 이런 방식으로 수행될 수 있습니다.

우리 변수 확인 패스는 일종의 미니 인터프리터처럼 작동합니다. 트리를 순회하며 각 노드를 방문하지만, 정적 분석은 동적 실행과 다릅니다:

• 부작용이 없습니다. 정적 분석이 print 문장을 방문할 때, 실제로 아무것도 출력하지 않습니다. 네이티브 함수 호출이나 외부 세계로 나가는 다른 작업은 스텁 처리되어 아무런 효과가 없습니다.

• 제어 흐름이 없습니다. 루프는 한 번만 방문됩니다. if 문에서는 양쪽 분기 모두 방문됩니다. 논리 연산자는 단락 평가되지 않습니다.

11 . 3리졸버 클래스

Java의 모든 것과 마찬가지로, 우리 변수 확인 패스도 클래스에 구현됩니다.

package com.craftinginterpreters.lox;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

class Resolver implements Expr.Visitor<Void>, Stmt.Visitor<Void> {
  private final Interpreter interpreter;

  Resolver(Interpreter interpreter) {
    this.interpreter = interpreter;
  }
}

리졸버는 구문 트리의 모든 노드를 방문해야 하므로, 우리가 이미 구현해 둔 방문자 추상화를 구현합니다. 변수를 확인하는 데 있어 흥미로운 노드는 몇 가지 종류뿐입니다:

• 블록 문(block statement)은 포함하는 문장들을 위한 새로운 스코프를 도입합니다.

• 함수 선언(function declaration)은 본문을 위한 새로운 스코프를 도입하고, 그 스코프 안에 매개변수를 바인딩합니다.

• 변수 선언(variable declaration)은 현재 스코프에 새 변수를 추가합니다.

• 변수 표현식(variable expression)과 할당 표현식(assignment expression)은 변수를 확인해야 합니다.

나머지 노드들은 특별한 작업을 수행하지 않지만, 서브트리로 탐색하기 위한 방문(visit) 메서드를 여전히 구현해야 합니다. + 표현식 자체에는 확인할 변수가 없더라도, 양쪽 피연산자 중 하나는 변수를 포함할 수 있기 때문입니다.

11 . 3 . 1블록 확인

모든 마법이 일어나는 지역 스코프를 생성하기 때문에 블록부터 시작합니다.

  @Override
  public Void visitBlockStmt(Stmt.Block stmt) {
    beginScope();
    resolve(stmt.statements);
    endScope();
    return null;
  }

이는 새로운 스코프를 시작하고, 블록 내의 문장들을 탐색한 다음, 스코프를 버립니다. 재미있는 부분은 저 헬퍼 메서드에 있습니다. 간단한 것부터 시작해봅시다.

  void resolve(List<Stmt> statements) {
    for (Stmt statement : statements) {
      resolve(statement);
    }
  }

이는 문장 목록을 순회하며 각 문장을 확인합니다. 그리고 차례로 다음을 호출합니다:

  private void resolve(Stmt stmt) {
    stmt.accept(this);
  }

김에, 나중에 표현식을 확인하는 데 필요할 또 다른 오버로드(overload)를 추가해봅시다.

  private void resolve(Expr expr) {
    expr.accept(this);
  }

이 메서드들은 Interpreter의 evaluate() 및 execute() 메서드와 유사합니다—주어진 구문 트리 노드에 Visitor 패턴을 적용합니다.

진정으로 흥미로운 동작은 스코프 주변에서 발생합니다. 새로운 블록 스코프는 다음과 같이 생성됩니다:

  private void beginScope() {
    scopes.push(new HashMap<String, Boolean>());
  }

렉시컬 스코프는 인터프리터와 리졸버 모두에서 중첩됩니다. 이는 스택처럼 동작합니다. 인터프리터는 Environment 객체의 체인인 연결 리스트를 사용하여 스택을 구현합니다. 리졸버에서는 실제 Java Stack을 사용합니다.

  private final Interpreter interpreter;

  private final Stack<Map<String, Boolean>> scopes = new Stack<>();

  Resolver(Interpreter interpreter) {

이 필드는 현재 스코프 내의 스코프 스택을 추적합니다. 스택의 각 요소는 단일 블록 스코프를 나타내는 Map입니다. Environment에서와 마찬가지로 키는 변수 이름입니다. 값은 Boolean이며, 그 이유는 곧 설명할 것입니다.

스코프 스택은 지역 블록 스코프에만 사용됩니다. 전역 스코프의 최상위 레벨에서 선언된 변수들은 Lox에서 더 동적이기 때문에 리졸버에 의해 추적되지 않습니다. 변수를 확인할 때, 지역 스코프 스택에서 찾을 수 없다면 전역 변수라고 가정합니다.

스코프가 명시적인 스택에 저장되므로, 스코프를 벗어나는 것은 간단합니다.

  private void endScope() {
    scopes.pop();
  }

이제 빈 스코프 스택을 푸시하고 팝할 수 있습니다. 거기에 몇 가지를 넣어봅시다.

11 . 3 . 2변수 선언 확인

변수 선언을 확인하는 것은 현재 가장 안쪽 스코프의 맵에 새로운 항목을 추가합니다. 간단해 보이지만, 우리가 해야 할 작은 작업이 있습니다.

  @Override
  public Void visitVarStmt(Stmt.Var stmt) {
    declare(stmt.name);
    if (stmt.initializer != null) {
      resolve(stmt.initializer);
    }
    define(stmt.name);
    return null;
  }

우리는 다음과 같은 재미있는 엣지 케이스를 처리하기 위해 바인딩을 선언(declaring)과 정의(defining)의 두 단계로 나눕니다:

var a = "outer";
{
  var a = a;
}

지역 변수의 초기화 표현식이 선언되는 변수와 같은 이름을 가진 변수를 참조할 때 무슨 일이 발생할까요? 몇 가지 옵션이 있습니다:

1. 초기화 표현식을 실행한 다음, 새 변수를 스코프에 넣습니다. 이 경우, 새로운 지역 변수 a는 전역 변수 a의 값인 "outer"로 초기화될 것입니다. 다시 말해, 이전 선언은 다음과 같이 구문 변환될 것입니다:

   var temp = a; // 초기화 표현식 실행.
   var a;        // 변수 선언.
   a = temp;     // 초기화.
   

2. 새 변수를 스코프에 넣은 다음, 초기화 표현식을 실행합니다. 이는 변수가 초기화되기 전에 변수를 관찰할 수 있다는 의미이므로, 변수가 그 시점에 어떤 값을 가질지 알아내야 할 것입니다. 아마도 nil일 것입니다. 이는 새로운 지역 변수 a가 암묵적으로 초기화된 값인 nil로 다시 초기화될 것임을 의미합니다. 이제 구문 변환은 다음과 같이 보일 것입니다:

   var a; // 변수 정의.
   a = a; // 초기화 표현식 실행.
   

3. 변수의 초기화 표현식에서 해당 변수를 참조하는 것을 오류로 만듭니다. 초기화 표현식이 초기화되는 변수를 언급하면 컴파일 시간 또는 런타임에 인터프리터가 실패하도록 합니다.

처음 두 옵션 중 어느 것이 사용자가 실제로 원하는 것처럼 보이나요? 섀도잉은 드물고 종종 오류를 유발하므로, 섀도잉되는 변수의 값에 기반하여 섀도잉 변수를 초기화하는 것은 의도적인 행동으로 보이지 않습니다.

두 번째 옵션은 훨씬 덜 유용합니다. 새 변수는 항상 nil 값을 가질 것입니다. 이름으로 언급할 필요가 전혀 없습니다. 대신 명시적인 nil을 사용할 수 있습니다.

처음 두 옵션은 사용자 오류를 숨길 가능성이 있으므로, 우리는 세 번째 옵션을 택할 것입니다. 또한, 런타임 오류 대신 컴파일 오류로 만들 것입니다. 그렇게 하면 사용자는 코드가 실행되기 전에 문제에 대해 알림을 받게 됩니다.

이를 위해 표현식을 방문할 때, 우리가 어떤 변수의 초기화 표현식 안에 있는지 알아야 합니다. 우리는 바인딩을 두 단계로 나누어 이 작업을 수행합니다. 첫 번째는 변수를 선언(declaring)하는 것입니다.

  private void declare(Token name) {
    if (scopes.isEmpty()) return;

    Map<String, Boolean> scope = scopes.peek();
    scope.put(name.lexeme, false);
  }

선언은 변수를 가장 안쪽 스코프에 추가하여 외부 스코프의 변수를 섀도잉하고 변수가 존재한다는 것을 알립니다. 우리는 스코프 맵에서 변수 이름을 false로 바인딩하여 "아직 준비되지 않음"으로 표시합니다. 스코프 맵의 키와 연결된 값은 해당 변수의 초기화 표현식 확인을 완료했는지 여부를 나타냅니다.

변수를 선언한 후, 새 변수는 존재하지만 아직 사용할 수 없는 동일한 스코프에서 초기화 표현식을 확인합니다. 초기화 표현식이 완료되면 변수는 사용 준비가 완료됩니다. 우리는 이를 변수를 정의(defining)함으로써 수행합니다.

  private void define(Token name) {
    if (scopes.isEmpty()) return;
    scopes.peek().put(name.lexeme, true);
  }

스코프 맵에서 변수의 값을 true로 설정하여 완전히 초기화되었고 사용 가능함을 표시합니다. 이제 활성화된 것입니다!

11 . 3 . 3변수 표현식 확인

변수 선언—그리고 우리가 곧 다룰 함수 선언—은 스코프 맵에 씁니다. 이 맵들은 변수 표현식을 확인할 때 읽힙니다.

  @Override
  public Void visitVariableExpr(Expr.Variable expr) {
    if (!scopes.isEmpty() &&
        scopes.peek().get(expr.name.lexeme) == Boolean.FALSE) {
      Lox.error(expr.name,
          "Can't read local variable in its own initializer.");
    }

    resolveLocal(expr, expr.name);
    return null;
  }

먼저, 변수가 자신의 초기화 표현식 안에서 접근되고 있는지 확인합니다. 여기서 스코프 맵의 값들이 중요하게 작용합니다. 만약 현재 스코프에 변수가 존재하지만 그 값이 false라면, 이는 변수를 선언했지만 아직 정의하지 않았다는 의미입니다. 우리는 이 오류를 보고합니다.

이 확인 후에, 이 헬퍼(helper)를 사용하여 실제로 변수 자체를 확인합니다:

  private void resolveLocal(Expr expr, Token name) {
    for (int i = scopes.size() - 1; i >= 0; i--) {
      if (scopes.get(i).containsKey(name.lexeme)) {
        interpreter.resolve(expr, scopes.size() - 1 - i);
        return;
      }
    }
  }

이 코드는 당연하게도 Environment의 변수 평가 코드와 매우 유사합니다. 우리는 가장 안쪽 스코프부터 시작하여 바깥쪽으로 이동하며, 각 맵에서 일치하는 이름을 찾습니다. 변수를 찾으면, 현재 가장 안쪽 스코프와 변수가 발견된 스코프 사이의 스코프 개수를 전달하여 변수를 확인합니다. 따라서 변수가 현재 스코프에서 발견되면 0을 전달합니다. 바로 바깥 스코프에 있다면 1을 전달합니다. 어떤 식인지 아시겠죠.

모든 블록 스코프를 탐색해도 변수를 찾지 못하면, 확인되지 않은 상태로 남겨두고 전역 변수라고 가정합니다. 해당 resolve() 메서드의 구현은 조금 후에 다룰 것입니다. 지금은 다른 구문 노드들을 계속 처리해봅시다.

11 . 3 . 4할당 표현식 확인

변수를 참조하는 또 다른 표현식은 할당입니다. 할당 표현식을 확인하는 방법은 다음과 같습니다:

  @Override
  public Void visitAssignExpr(Expr.Assign expr) {
    resolve(expr.value);
    resolveLocal(expr, expr.name);
    return null;
  }

먼저, 할당되는 값의 표현식을 확인합니다. 이 표현식이 다른 변수에 대한 참조를 포함할 수 있기 때문입니다. 그런 다음 기존의 resolveLocal() 메서드를 사용하여 할당 대상이 되는 변수를 확인합니다.

11 . 3 . 5함수 선언 확인

마지막으로 함수입니다. 함수는 이름을 바인딩하고 스코프를 도입합니다. 함수 자체의 이름은 함수가 선언된 주변 스코프에 바인딩됩니다. 함수 본문으로 들어갈 때, 함수의 매개변수 또한 내부 함수 스코프에 바인딩합니다.

  @Override
  public Void visitFunctionStmt(Stmt.Function stmt) {
    declare(stmt.name);
    define(stmt.name);

    resolveFunction(stmt);
    return null;
  }

visitVariableStmt()와 유사하게, 현재 스코프에 함수의 이름을 선언하고 정의합니다. 하지만 변수와 달리, 함수의 본문을 확인하기 전에 이름을 즉시 정의합니다. 이렇게 하면 함수가 자신의 본문 안에서 재귀적으로 자신을 참조할 수 있습니다.

그 다음, 다음 코드를 사용하여 함수의 본문을 확인합니다:

  private void resolveFunction(Stmt.Function function) {
    beginScope();
    for (Token param : function.params) {
      declare(param);
      define(param);
    }
    resolve(function.body);
    endScope();
  }

이것은 나중에 클래스를 추가할 때 Lox 메서드를 확인하는 데도 사용할 것이므로 별도의 메서드입니다. 이 메서드는 본문을 위한 새로운 스코프를 생성한 다음, 각 함수의 매개변수에 대한 변수를 바인딩합니다.

준비가 되면 해당 스코프에서 함수 본문을 확인합니다. 이는 인터프리터가 함수 선언을 처리하는 방식과 다릅니다. 런타임에는 함수를 선언하는 것이 함수 본문에 아무것도 하지 않습니다. 함수가 호출될 때까지 본문은 건드려지지 않습니다. 정적 분석에서는 함수 선언 시 즉시 본문으로 탐색합니다.

11 . 3 . 6다른 구문 트리 노드 확인

이로써 문법의 흥미로운 부분들을 모두 다뤘습니다. 변수가 선언, 읽기, 쓰기 되는 모든 곳과 스코프가 생성되거나 파괴되는 모든 곳을 처리합니다. 변수 확인에 영향을 받지 않더라도, 우리는 여전히 다른 모든 구문 트리 노드에 대해 서브트리로 재귀적으로 탐색하기 위한 방문(visit) 메서드를 구현해야 합니다. 죄송하지만 이 부분은 지루할 수 있으니 조금만 참아주세요. 우리는 "하향식(top down)" 방식으로 접근하여 문장부터 시작하겠습니다.

표현식 문장(expression statement)은 탐색할 단일 표현식을 포함합니다.

  @Override
  public Void visitExpressionStmt(Stmt.Expression stmt) {
    resolve(stmt.expression);
    return null;
  }

if 문은 조건을 위한 표현식과 분기들을 위한 하나 또는 두 개의 문장을 가집니다.

  @Override
  public Void visitIfStmt(Stmt.If stmt) {
    resolve(stmt.condition);
    resolve(stmt.thenBranch);
    if (stmt.elseBranch != null) resolve(stmt.elseBranch);
    return null;
  }

여기서 변수 확인이 해석(interpretation)과 어떻게 다른지 볼 수 있습니다. if 문을 확인할 때, 제어 흐름은 없습니다. 우리는 조건과 두 분기 모두를 확인합니다. 동적 실행은 실제로 실행되는 분기만으로 진입하는 반면, 정적 분석은 보수적입니다—실행될 수 있는 모든 분기를 분석합니다. 런타임에 둘 중 어느 하나에 도달할 수 있으므로, 우리는 둘 다 확인합니다.

표현식 문장과 마찬가지로, print 문장도 단일 하위 표현식을 포함합니다.

  @Override
  public Void visitPrintStmt(Stmt.Print stmt) {
    resolve(stmt.expression);
    return null;
  }

return 문도 마찬가지입니다.

  @Override
  public Void visitReturnStmt(Stmt.Return stmt) {
    if (stmt.value != null) {
      resolve(stmt.value);
    }

    return null;
  }

if 문과 마찬가지로, while 문에서도 조건과 본문을 정확히 한 번 확인합니다.

  @Override
  public Void visitWhileStmt(Stmt.While stmt) {
    resolve(stmt.condition);
    resolve(stmt.body);
    return null;
  }

이것으로 모든 문장을 다뤘습니다. 이제 표현식으로 . . . 

오랜 친구인 이항 표현식입니다. 우리는 양쪽 피연산자를 탐색하고 확인합니다.

  @Override
  public Void visitBinaryExpr(Expr.Binary expr) {
    resolve(expr.left);
    resolve(expr.right);
    return null;
  }

함수 호출도 마찬가지입니다—인수 목록을 순회하여 모두 확인합니다. 호출되는 대상 또한 표현식(일반적으로 변수 표현식)이므로, 그것도 확인됩니다.

  @Override
  public Void visitCallExpr(Expr.Call expr) {
    resolve(expr.callee);

    for (Expr argument : expr.arguments) {
      resolve(argument);
    }

    return null;
  }

괄호는 쉽습니다.

  @Override
  public Void visitGroupingExpr(Expr.Grouping expr) {
    resolve(expr.expression);
    return null;
  }

리터럴은 가장 쉽습니다.

  @Override
  public Void visitLiteralExpr(Expr.Literal expr) {
    return null;
  }

리터럴 표현식은 어떤 변수도 언급하지 않고 어떤 하위 표현식도 포함하지 않으므로 할 일이 없습니다.

정적 분석은 제어 흐름이나 단락 평가를 수행하지 않으므로, 논리 표현식은 다른 이항 연산자와 정확히 동일합니다.

  @Override
  public Void visitLogicalExpr(Expr.Logical expr) {
    resolve(expr.left);
    resolve(expr.right);
    return null;
  }

그리고 마지막으로, 마지막 노드입니다. 우리는 단일 피연산자를 확인합니다.

  @Override
  public Void visitUnaryExpr(Expr.Unary expr) {
    resolve(expr.right);
    return null;
  }

이 모든 방문(visit) 메서드 덕분에, Java 컴파일러는 Resolver가 Stmt.Visitor와 Expr.Visitor를 완전히 구현했음에 만족할 것입니다. 이제 잠시 쉬고, 간식을 먹고, 짧은 낮잠을 자기에 좋은 시간입니다.

11 . 4확인된 변수 해석

우리 리졸버가 무엇에 유용한지 봅시다. 변수를 방문할 때마다, 리졸버는 현재 스코프와 변수가 정의된 스코프 사이에 몇 개의 스코프가 있는지 인터프리터에게 알려줍니다. 런타임에 이것은 인터프리터가 변수 값을 찾을 수 있는 현재 환경과 감싸는 환경 사이의 환경 수와 정확히 일치합니다. 리졸버는 다음을 호출하여 그 숫자를 인터프리터에 전달합니다:

  void resolve(Expr expr, int depth) {
    locals.put(expr, depth);
  }

변수 또는 할당 표현식이 나중에 실행될 때 사용할 수 있도록 확인 정보를 어딘가에 저장하고 싶지만, 어디에 저장해야 할까요? 한 가지 분명한 장소는 구문 트리 노드 자체입니다. 그것도 좋은 접근 방식이며, 많은 컴파일러가 이러한 분석 결과를 저장하는 곳입니다.

그렇게 할 수도 있지만, 구문 트리 생성기를 만져야 할 것입니다. 대신, 우리는 또 다른 일반적인 접근 방식을 택하여 각 구문 트리 노드와 확인된 데이터를 연결하는 맵에 별도로 저장할 것입니다.

IDE와 같은 대화형 도구는 종종 사용자 프로그램의 일부를 점진적으로 다시 파싱하고 다시 확인합니다. 구문 트리의 복잡한 구조 속에 숨어 있는 재계산이 필요한 모든 상태 조각을 찾는 것은 어려울 수 있습니다. 이 데이터를 노드 외부에 저장하는 이점은 데이터를 버리기 쉽다는 것입니다—맵을 비우기만 하면 됩니다.

  private Environment environment = globals;

  private final Map<Expr, Integer> locals = new HashMap<>();

  Interpreter() {

같은 변수를 참조하는 여러 표현식이 있을 때 혼동을 피하려면 어떤 종류의 중첩된 트리 구조가 필요하다고 생각할 수도 있습니다. 하지만 각 표현식 노드는 고유한 정체성을 가진 자체 Java 객체입니다. 단일 모놀리식 맵은 이들을 분리하는 데 아무런 문제가 없습니다.

늘 그렇듯이, 컬렉션을 사용하려면 몇 가지 이름을 임포트해야 합니다.

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

그리고:

import java.util.List;

import java.util.Map;

class Interpreter implements Expr.Visitor<Object>,

11 . 4 . 1확인된 변수 접근

우리 인터프리터는 이제 각 변수의 확인된 위치에 접근할 수 있게 되었습니다. 마침내 이를 활용할 때입니다. 변수 표현식에 대한 방문(visit) 메서드를 다음 코드로 대체합니다:

  public Object visitVariableExpr(Expr.Variable expr) {

    return lookUpVariable(expr.name, expr);

  }

이는 다음으로 위임합니다:

  private Object lookUpVariable(Token name, Expr expr) {
    Integer distance = locals.get(expr);
    if (distance != null) {
      return environment.getAt(distance, name.lexeme);
    } else {
      return globals.get(name);
    }
  }

여기서는 몇 가지 일이 벌어집니다. 첫째, 맵에서 확인된 거리(distance)를 찾습니다. 우리는 지역 변수만 확인했음을 기억하세요. 전역 변수는 특별히 처리되며 맵에 포함되지 않습니다 (그래서 이름이 locals입니다). 따라서 맵에서 거리를 찾지 못하면, 전역 변수여야 합니다. 이 경우, 전역 환경에서 동적으로 직접 변수를 찾습니다. 만약 변수가 정의되어 있지 않으면 런타임 오류를 발생시킵니다.

만약 거리를 얻으면, 우리는 지역 변수를 가지고 있으며 정적 분석 결과를 활용할 수 있습니다. get()을 호출하는 대신, Environment에 있는 이 새로운 메서드를 호출합니다:

  Object getAt(int distance, String name) {
    return ancestor(distance).values.get(name);
  }

이전 get() 메서드는 감싸는 환경들의 체인을 동적으로 순회하며, 변수가 어딘가에 숨어 있을지 찾아보기 위해 각 환경을 샅샅이 뒤졌습니다. 하지만 이제 우리는 체인에서 정확히 어느 환경이 변수를 가질지 알고 있습니다. 우리는 이 헬퍼 메서드를 사용하여 해당 환경에 도달합니다:

  Environment ancestor(int distance) {
    Environment environment = this;
    for (int i = 0; i < distance; i++) {
      environment = environment.enclosing; 
    }

    return environment;
  }

이는 부모 체인을 따라 고정된 수의 홉(hops)만큼 올라가 해당 환경을 반환합니다. 이를 얻은 후, getAt()은 단순히 해당 환경의 맵에 있는 변수 값을 반환합니다. 변수가 존재하는지 확인할 필요조차 없습니다—리졸버가 이미 이전에 찾아냈기 때문에 변수가 존재할 것임을 알고 있습니다.

11 . 4 . 2확인된 변수에 할당하기

변수에 값을 할당함으로써 변수를 사용할 수도 있습니다. 할당 표현식을 방문하는 변경 사항은 유사합니다.

  public Object visitAssignExpr(Expr.Assign expr) {
    Object value = evaluate(expr.value);

    Integer distance = locals.get(expr);
    if (distance != null) {
      environment.assignAt(distance, expr.name, value);
    } else {
      globals.assign(expr.name, value);
    }

    return value;

다시, 변수의 스코프 거리를 찾습니다. 찾지 못하면 전역 변수라고 가정하고 이전과 동일한 방식으로 처리합니다. 그렇지 않으면 이 새로운 메서드를 호출합니다:

  void assignAt(int distance, Token name, Object value) {
    ancestor(distance).values.put(name.lexeme, value);
  }

getAt()이 get()과 같은 관계인 것처럼, assignAt()은 assign()과 같은 관계입니다. 이는 고정된 수의 환경을 탐색한 다음, 그 맵에 새 값을 채워 넣습니다.

이것이 Interpreter에 대한 유일한 변경 사항입니다. 이것이 제가 최소한의 침습적인 방식으로 확인된 데이터 표현을 선택한 이유입니다. 나머지 모든 노드는 이전과 동일하게 작동합니다. 환경을 수정하는 코드조차도 변경되지 않았습니다.

11 . 4 . 3리졸버 실행

하지만 실제로 리졸버를 실행해야 합니다. 파서가 작업을 완료한 후에 새로운 패스를 삽입합니다.

    // Stop if there was a syntax error.
    if (hadError) return;

    Resolver resolver = new Resolver(interpreter);
    resolver.resolve(statements);

    interpreter.interpret(statements);

파싱 오류가 있을 경우 리졸버를 실행하지 않습니다. 코드에 구문 오류가 있다면 절대 실행되지 않을 것이므로, 이를 확인하는 것은 거의 가치가 없습니다. 구문이 깔끔하다면, 리졸버에게 작업을 수행하도록 지시합니다. 리졸버는 인터프리터에 대한 참조를 가지고 있으며, 변수를 순회하면서 확인된 데이터를 인터프리터에 직접 주입합니다. 인터프리터가 다음으로 실행될 때, 필요한 모든 것을 갖추게 됩니다.

적어도 리졸버가 성공하는 경우에만 그렇습니다. 하지만 확인 과정에서 오류가 발생하면 어떻게 될까요?

11 . 5변수 확인 오류

의미 분석 패스를 수행하고 있으므로, Lox의 의미론을 더 정확하게 만들고, 사용자가 코드를 실행하기 전에 버그를 조기에 발견하도록 도울 기회가 있습니다. 이 나쁜 코드를 보세요:

fun bad() {
  var a = "first";
  var a = "second";
}

우리는 전역 스코프에서 같은 이름으로 여러 변수를 선언하는 것을 허용하지만, 지역 스코프에서 그렇게 하는 것은 아마도 실수일 것입니다. 만약 변수가 이미 존재한다는 것을 알았다면, var를 사용하는 대신 변수에 할당했을 것입니다. 그리고 만약 변수가 존재한다는 것을 몰랐다면, 이전 변수를 덮어쓸 의도는 없었을 것입니다.

우리는 변수 확인 중에 이 실수를 정적으로 감지할 수 있습니다.

    Map<String, Boolean> scope = scopes.peek();

    if (scope.containsKey(name.lexeme)) {
      Lox.error(name,
          "Already a variable with this name in this scope.");
    }

    scope.put(name.lexeme, false);

지역 스코프에서 변수를 선언할 때, 우리는 이미 해당 스코프 내에서 이전에 선언된 모든 변수의 이름을 알고 있습니다. 충돌이 발생하면 오류를 보고합니다.

11 . 5 . 1유효하지 않은 return 오류

여기 또 다른 불쾌한 작은 스크립트가 있습니다:

return "at top level";

이것은 return 문을 실행하지만, 함수 안에 전혀 있지 않습니다. 최상위 레벨 코드입니다. 사용자가 무엇이 일어날 것이라고 생각하는지는 모르겠지만, Lox가 이것을 허용하기를 원치 않습니다.

리졸버를 확장하여 이것을 정적으로 감지할 수 있습니다. 트리를 순회하면서 스코프를 추적하는 것과 유사하게, 현재 방문 중인 코드가 함수 선언 내부에 있는지 여부를 추적할 수 있습니다.

  private final Stack<Map<String, Boolean>> scopes = new Stack<>();

  private FunctionType currentFunction = FunctionType.NONE;

  Resolver(Interpreter interpreter) {

순수한 Boolean 대신, 이 재미있는 enum을 사용합니다:

  private enum FunctionType {
    NONE,
    FUNCTION
  }

지금은 다소 엉뚱해 보일 수 있지만, 나중에 몇 가지 케이스를 더 추가하면 더 이해가 될 것입니다. 함수 선언을 확인할 때, 이 값을 전달합니다.

    define(stmt.name);

    resolveFunction(stmt, FunctionType.FUNCTION);

    return null;

resolveFunction()에서는 해당 매개변수를 받아 본문을 확인하기 전에 필드에 저장합니다.

  private void resolveFunction(
      Stmt.Function function, FunctionType type) {
    FunctionType enclosingFunction = currentFunction;
    currentFunction = type;

    beginScope();

먼저 필드의 이전 값을 지역 변수에 임시 저장합니다. Lox는 지역 함수를 지원하므로, 함수 선언을 임의의 깊이로 중첩할 수 있음을 기억하세요. 우리는 단순히 함수 안에 있다는 것뿐만 아니라, 몇 개의 함수 안에 있는지 추적해야 합니다.

이를 위해 FunctionType 값들의 명시적인 스택을 사용할 수도 있지만, 대신 JVM에 편승할 것입니다. 우리는 이전 값을 Java 스택의 지역 변수에 저장합니다. 함수 본문 확인을 마친 후, 필드를 그 값으로 복원합니다.

    endScope();

    currentFunction = enclosingFunction;

  }`

이제 우리가 함수 선언 내부에 있는지 여부를 항상 알 수 있으므로, return 문을 확인할 때 이를 확인합니다.

  public Void visitReturnStmt(Stmt.Return stmt) {

    if (currentFunction == FunctionType.NONE) {
      Lox.error(stmt.keyword, "Can't return from top-level code.");
    }

    if (stmt.value != null) {

깔끔하죠?

한 가지 더 있습니다. 모든 것을 함께 엮는 주요 Lox 클래스에서, 파싱 오류가 발생하면 인터프리터를 실행하지 않도록 주의합니다. 이 확인은 구문적으로 유효하지 않은 코드를 확인하려 하지 않도록 리졸버 전에 실행됩니다.

하지만 변수 확인 오류가 있을 경우에도 인터프리터를 건너뛰어야 하므로, 또 다른 확인을 추가합니다.

    resolver.resolve(statements);

    // 변수 확인 오류가 있었다면 중단.
    if (hadError) return;

    interpreter.interpret(statements);

이곳에서 다른 많은 분석을 수행할 수 있다고 상상할 수 있습니다. 예를 들어, Lox에 break 문을 추가한다면, 아마도 이것이 루프 안에서만 사용되는지 확인하고 싶을 것입니다.

더 나아가, 반드시 틀린 것은 아니지만 유용하지 않을 수 있는 코드에 대해 경고를 보고할 수도 있습니다. 예를 들어, 많은 IDE는 return 문 뒤에 도달할 수 없는 코드가 있거나 값이 전혀 읽히지 않는 지역 변수가 있는 경우 경고를 보냅니다. 이 모든 것은 우리의 정적 방문 패스에 추가하거나 별도의 패스로 구현하는 것이 아주 쉬울 것입니다.

하지만 지금은 그 제한된 양의 분석에 머무를 것입니다. 중요한 것은 그 이상하고 성가신 엣지 케이스 버그를 고쳤다는 점인데, 이를 위해 이만큼의 작업이 필요했다는 것이 놀라울 수도 있습니다.