[프로그래밍언어론] 17. 범위 규칙 구현(Scope Rule Implementation)

범위 규칙 구현

• 정적 범위 규칙 구현
  
  • 정적 링크(Static Link)
  • 디스플레이(The Display)
• 동적 범위 규칙 구현
  
  • 연관 목록(association lists)
  • 중앙 참조 테이블(Central Referencing Table)

 

---

 

정적 범위 규칙 구현

• 정적 범위 규칙 구현에는 단순히 스택을 사용하는 것보다 더 많은 관리가 필요하다.

• foo 프로시저에서 변수 x는 C가 아닌 블록 B의 x를 참조한다.
• 단, foo에 동적 링크로 연결된 활성화 레코드는 Block C이다.

• 따라서 블록을 즉시 둘러싸는 블록에 대한 링크가 하나 더 필요하다.
• 정적 링크(점선)를 사용하여 둘러싸는 블록을 가리킨다.
• 정적 범위를 관리할 때는 동적 링크 대신 정적 링크를 사용한다.

 

---

 

정적 링크

• 다음 구조의 예를 고려해보자

• 블록 B, C는 블록 A 내부에 선언
• 블록 D, E는 블록 C에 포함
• 호출 시퀀스
  
  • A, B, C, D, E, C
• 활성화 레코드가 스택에 푸시되면, 정적 링크의 주소를 결정해야 한다.
• 가장 일반적인 접근 방식에서는 caller가 링크를 계산하여 callee에게 전달한다.
• 두 가지 경우가 있다.

 

1. caller가 callee 외부에 존재 (예: E가 C를 호출)

• caller는 가시성 규칙에 따라 calee의 외부 블록에 있어야 한다.
• 따라서 caller의 활성화 레코드가 이미 스택에 있어야 한다.
• 따라서 우리는 새 블록에 대한 새 링크를 찾기 위해 정적 링크를 역추적할 수 있다.

 

2. caller가 callee 내부에 존재 (예: C가 D를 호출)

• 가시성 규칙은 호출이 발생한 동일한 블록에서 caller가 선언되도록 보장한다.
• 따라서 caller에 대한 정적 링크를 간단히 설정할 수 있다.

 

---

 

디스플레이(The Display)

• 정적 링크에는 각 프로시저 호출에 대해 여러 가지 메모리 액세스가 필요하다.
• 로컬이 아닌 이름이 k 레벨의 블록에서 선언되면 정적 링크를 따라가기 위해 k 메모리 액세스가 필요하다.
• 일반적으로 중첩이 너무 많지는 않지만(즉, k는 크지 않음) 더 잘할 수 있다.
• 디스플레이 기술에는 지속적인 메모리 액세스(2회)만 필요하다.

 

• 디스플레이라는 벡터를 사용한다.
  
  • k번째 요소에는 k번째 중첩 수준의 현재 활성화 레코드에 대한 포인터가 포함된다.
• 레벨 n의 블록에 선언된 로컬이 아닌 이름을 찾으려면,
  
  • 요소 n에서 포인터를 따라갈 수 있다.
  • 그런 다음 로컬 오프셋을 사용하여 이름을 찾는다.

 

• 디스플레이 처리가 간단하다.
• 레벨 k에서 프로시저가 호출되면, 디스플레이의 k번째 요소는 caller의 활성화 레코드에 대한 포인터로 업데이트된다.
• A, B, C, D, E, C 호출 순서를 다시 생각해보자

 

• 동일한 레벨에서 프로시저가 호출되는 경우
  
  • 디스플레이에 이전 값을 저장해야 한다.
  • 덮어씌우기 때문.
• 블록 C도 레벨 2에 있으므로 블록 B에 대한 이전 포인터는 블록 C에서 B로의 링크로 저장한다.
• 이 이전 값은 C가 스택에서 벗어난 후에 복원될 수 있다.

 

• 수신자(Block D)가 발신자(Block C) 내부에 있는 경우,
  
  • 디스플레이 길이를 늘릴 수 있다.
  • 그런 다음 포인터를 다음 요소(세 번째 요소)에 놓는다.

 

• 블록 E를 호출하면 요소 3의 이전 값이 저장된다.
• 그런 다음 블록 E에 대한 포인터가 업데이트된다.
• 변수 x가 블록 C에서 선언되고 블록 E에서 사용된다고 가정한다.
  
  • 우리는 x가 컴파일 타임(정적 범위)에 C에서 선언된다는 것을 알고 있다.
  • 블록 C는 레벨 2이므로 표시 요소 2를 확인
  • 그런 다음 로컬 오프셋을 사용하여 x의 바인딩을 찾는다.

 

• 블록 C는 블록 E에서 호출된다.
  
  • 블록 C에서는 블록 E에 선언된 로컬 이름을 사용할 수 없다.
  • 디스플레이에는 요소 2의 C에 대한 포인터가 포함되어 있으므로 이 뒤에 있는 요소는 비활성화된다.

 

---

 

동적 범위 규칙 구현

 

• 동적 범위에서는 비로컬 환경이 활성화 순서대로 고려된다.
• 따라서 적절한 바인딩을 찾으려면 스택에서 뒤로 이동해야 한다.

 

• 동적 범위 규칙 구현에서는 다음의 예제를 사용한다.
• A, B, C, D 호출을 고려해야한다.
• 회색은 비활성화된 바인딩을 의미한다.

 

---

 

연관 목록(Association List)

• 활성화 레코드에 직접 저장하는 것 외에,
  
  • 바인딩은 연관 목록(A-list)에 별도로 저장할 수 있다.
• 프로그램이 새로운 환경에 들어갈 때,
  
  • 바인딩은 A-list에 삽입되고 프로그램이 환경을 종료할 때 제거된다.

• 두 가지 단점
  
  • 이름은 구조에 런타임 때 저장되어야 한다.
    
    • 컴파일 시간에는 위치를 추적할 수 없다.
  • 런타임에 이름을 검색하는 것은 비효율적이다.
    
    • 모든 목록을 확인해야 할 수도 있다.

 

---

 

중앙 참조 테이블(Central Referencing Table)

• 단점을 해결하기 위해 중앙 참조 테이블(CRT)을 사용할 수 있다.
• 프로그램에 사용되는 모든 이름은 CRT에 저장된다.
• 각 이름에는 활성 또는 비활성 여부를 나타내는 플래그가 있다.
• 전용 스택에는 상단의 이름에 대한 유효한 바인딩이 포함되어 있다.
  
  • 그리고 그 아래의 바인딩이 비활성화되었다.

 

• 비활성화된 모든 바인딩을 저장하기 위해 숨겨진 스택을 사용할 수도 있다.
• 세 번째 열에는 이름에 대한 표시 가능한 개체에 대한 참조가 포함된다.
• 숨겨진 스택(hidden stack)에 저장된 비활성화된 바인딩,
  
  • 다시 활성화되면 복원된다.