[프언] #07. Lexical Scoping of Variables

Static Scope

이전 글에서 Static Scoping을 사용해 정의된 Procedure에서 Environment는 Procedure가 정의된 시점의 Environment를 따른다고 했었습니다. 이렇게 Static Scoping을 사용하면, 어떤 변수에 대한 Scope는 Static 한 성질을 가집니다.

갑자기 모르는 말이 나와서 당황하셨을 분들을 위해 설명드리겠습니다. 어떤 변수의 Scope라는 것은, 이 변수를 사용할 수 있는 범위라는 뜻을 가집니다. 모든 변수는 자기 자신만의 Scope를 가집니다. 프로그램 전체에서 사용 가능한 변수도 있고, 특정 Expression 내부에서만 사용할 수 있는 변수도 있는 법이니깐요.

어떤 성질이 Static 하다는 것은, 그 성질은 프로그램을 굳이 돌려보지 않아도 그 값을 계산할 수 있다는 뜻입니다. Static의 반대말은 Dynamic인데요, 어떤 성질이 Dynamic 하다면 그 값은 프로그램을 돌려보아야만 알 수 있습니다. 예를 들어, 어떤 변수의 Type은 C++에서는 Static Property이지만 Python에서는 Dynamic Property입니다.

 

Nameless Representation

이제 Static Scoping에서 변수들은 각자의 Scope를 가지고, 그 Scope는 Static 하다는 사실을 알았습니다. 이제 Lexical Depth에 대해 이야기해 보겠습니다.

let x = 1
	in let y = 2
		in x + y

위와 같은 코드를 생각해 봅시다. 위 코드에서 변수 x를 먼저 고려해 볼 건데, 우리가 x를 실제로 사용하는 시점은 x를 참조(Reference)하는 3번째 줄일 것입니다. 여기서 저희는 x가 참조된 시점이 x가 정의(Declaration)된 시점에서 얼마나 떨어졌는지에 집중할 것입니다. 어떻게 하느냐? x가 참조된 시점으로부터 위로 올라가면서 Declaration의 개수를 세보는 겁니다.

예컨대, x가 참조된 것은 3번째 줄입니다. 3번째 줄에서 시작해서 위로 올라가다 보면, 2번째 줄에서 y의 Declaration이 나옵니다. 그리고 그다음 줄에서 x의 Declaration을 찾을 수 있죠. 따라서 x가 참조된 곳에서 x가 정의된 곳까지 총 1번의 Declaration이 있었으므로 우리가 구하고자 하는 값은 1이 됩니다. 이 값을 Lexical Depth라고 합니다.

반면 y의 경우 3번째 줄에서 참조되었고 바로 그전에 정의되었으므로, y의 Lexical Depth는 0이 됩니다.

재미있는 사실은, 변수를 하나 정의할 때마다 다른 변수들의 Lexical Depth가 달라지기 때문에 Lexical Depth만을 이용해서 변수를 표현할 수 있다는 것입니다. 아래와 같이요.

let 1
	in let 2
		in #1 + #0

이러한 표현을 Nameless Representation, 혹은 De Bruijin Representation이라고 합니다.

조금 더 복잡한 예시를 보겠습니다.

(let x = 37
	in proc y
		let z = y - x
			in z - y) 10

위 코드를 한번 Nameless Representation으로 바꿔보겠습니다. 먼저 3번째 줄에서 첫 번째 참조가 등장합니다. y의 Lexical Depth는 0이고 x의 Lexical Depth는 1이므로 #0 - #1이라고 표현할 수 있습니다. 4번째 줄에 있는 참조의 경우, z의 Lexical Depth는 0, y의 Lexical Depth는 1이므로 #0 - #1이라고 할 수 있습니다.

(let 37
	in proc
		let #0 - #1
			in #0 - #1) 10

그래서 Nameless Representation은 위와 같습니다. 3번째 줄과 4번째 줄에서 전부 #0 - #1이 사용되었지만, 이들이 실제로 의미하는 값은 다릅니다.

 

Translation Function

Translation Function은 일반적인 방식으로 쓰인 Procedure를 Nameless Procedure로 변환해 주는 역할을 합니다.

기본적으로 이렇게 정의되어 있습니다. 중요하게 봐야 할 부분은 let, proc이 함수를 통과하면 어떻게 되는지입니다. let x, proc x 등으로 변수가 정의될 경우 현재 environment에 x를 추가하여 변수가 하나 더 정의되었음을 기억하는 겁니다. 예를 들어, 위에서 보았던 예시를 Translation Function을 이용해서 변환하면 아래와 같습니다.

감사합니다.

---

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.