[프언] #08. States

이번 글에서는 저희 언어에 State를 한번 추가해 볼 겁니다.

let f = proc x x
in f (f 1)

 이런 프로그램을 실행할 때, 저희는 f가 2번 호출된다는 사실을 알 수 있습니다. 하지만 프로그램은 f가 몇 번 호출되는지 알 길이 없습니다. 왜냐하면 Procedure는 Caller에게 결괏값만을 제공할 뿐, 그 외의 행동은 하지 않기 때문입니다.

let count = 0
in let f = proc x (let count = count + 1 in x)
in let a = f (f 1) in count

따라서 이런 식으로 변수를 따로 만들어서 f가 호출된 횟수를 세는 것은 가능하지 않습니다. 이번 글에서는 이것이 가능하도록, Procedure가 Procedure 외부에 있는 값들을 수정할 수 있는 방법에 대해 알아볼 겁니다.

 

Implicit vs. Explicit

C, C++ 등의 언어에서 모든 변수는 그 주소값을 가지고, 그 주소값을 통해 여러 연산을 수행할 수 있습니다. 이런 방식을 Implicit Reference라고 합니다. 아마 많은 분들께서 이 방법이 익숙하실 겁니다.

이에 반해 어떤 값의 주소를 표현할 때, 완전히 새로운 값을 만들어 그 위치를 표현할 수도 있는데요, 이런 방식을 Explicit Reference라고 합니다.

 

Explicit Reference

Explicit Reference에서 메모리 관리를 위해서 아래와 같은 명령어들을 도입하겠습니다.

• ref E : 값 E를 저장할 새로운 공간을 만들어 그 공간을 값 E에게 할당합니다.
• ! E : Dereference 작업을 수행합니다. (E가 가리키고 있는 공간에 있는 값을 불러옵니다.)
• $E_1$ := $E_2$ : $E_1$의 위치에 있는 값을 $E_2$로 교체합니다.
• $E_1$ ; $E_2$ : $E_1$을 실행한 뒤 $E_2$를 실행합니다.

이 명령어들을 활용해서, 간단하게 f가 몇 번 호출되는지를 확인하는 코드를 만들어보겠습니다.

let count = ref 0
in let f = proc x (count := !count + 1; !count)
in let a = f 1
	in let b = f 1
		in let a + b

먼저 1번째 줄에서 0을 저장할 위치를 만들고, 그 위치를 count라고 정의했습니다. 따라서, 2번째 줄에 있는 !count + 1은 count에 있는 값에 1을 더하라는 뜻이 되고, 앞에 count :=이 붙어있기 때문에 그 값을 count 위치에 저장하라는 뜻이 됩니다. 따라서, count := !count + 1까지 count 위치에 있는 값에 1을 더한다는 뜻이 되겠죠.

그리고 !count 값을 계산하고 그 값이 Procedure의 계산값이 되므로, f가 한번 실행될 때마다 count 위치에 있는 값이 1씩 증가하게 됩니다. 따라서 a에 저장되는 값은 1이 될 것이고, b에 저장되는 값은 2가 되므로 위 프로그램 전체는 3으로 계산됩니다.

let f = let count = ref 0
	in proc x (count := !count + 1; !count)
in let a = f 1
	in let b = f 1
		in a + b

이것은 위의 코드를 약간 변형한 것입니다. Procedure f를 정의할 때 같이 count를 정의해 주었는데요, 이렇게 정의해 주어도 아까의 코드와 정확히 같은 행동을 하며, 그 결괏값 역시 3이 됩니다.

이렇게 count라는 값을 f 내부에서 정의하여, f 내부에서만 이 값을 사용하고 f 외부에서는 이 값을 사용할 수 없도록 하는 것을 변수를 숨긴다(Hide)고 표현합니다.

let f = proc x (let count = ref 0
	in (count := !count + 1; !count))
in let a = f 1
	in let b = f 1
		in let a + b

이러한 코드의 경우는 Procedure의 Body 부분에 count가 정의되고 있습니다. 이렇게 되면 f가 호출될 때마다 count 위치에 있는 값이 0으로 초기화되기 때문에, a에 1, b에 1이 저장되어 결괏값은 2가 됩니다.

 

또한, 주소값의 주소값 역시 표현이 가능합니다.

let x = ref (ref 0)
in (!x := 11; !(!x))

이 코드에서 x는 0의 주소값의 주소값을 의미합니다. 따라서 !x := 11은 x가 가리키는 주소값이 가르키는 곳에 저장된 값을 11로 바꾸라는 뜻이 됩니다. 따라서, 위 코드는 11의 값을 가집니다. 

 

지금까지 Expression을 계산할 때 아래와 같은 기호를 써왔었습니다.

$$\rho \vdash E \Rightarrow v $$

그러나 지금부터는 새로운 개념인 메모리가 생겼습니다. 현재 메모리 상태를 표현하는 기호로 저희는 $ \sigma $를 사용할 것입니다.

$$\rho,\sigma \vdash E \Rightarrow v,  \sigma'$$

이렇게 $\rho, \sigma$인 환경에서 Expression $E$를 계산하면 그 값은 $v$이고, 메모리 상태는 $\sigma'$으로 변한다는 것을 위 식을 통해 나타낼 수 있습니다.

위는 새롭게 정의했던 4개의 명령어를 식으로 나타낸 것입니다. 크게 이해가 어려운 부분은 없을 듯 하니 자세한 설명은 생략하도록 하겠습니다.

 

Implicit Reference

Implicit Reference에서는 Explicit Reference와는 다르게 모든 변수가 각자의 메모리 주소를 가집니다. 사용하는 표현 자체는 Explicit Reference에서 사용한 것과 크게 다르지 않습니다.

• x := $E_2$ : x의 값을 $E_2$로 변경합니다.

똑같이 f가 사용된 횟수를 알아보는 코드를 예시로 보겠습니다.

let count = 0
in let f = proc x (count := count + 1; !count)
in let a = f 1
	in let b = f 1
		in a + b

변수를 정의하는 과정을 제외하고는 Explicit Reference와 큰 차이가 없습니다.

 

Implicit Reference에서 어떤 값의 주소값은 Val의 종류가 아닙니다. 즉, Explicit Reference에서는

$$Val = \mathbb{Z} + Bool + Procedure +Loc$$

이였습니다. 반면, Implicit Reference에서는 Loc 부분이 빠집니다.

 

Call-by-Value vs. Call-by-Reference

지금까지 저희는 Call-by-Value라는 방법을 사용해 Procedure를 설계해 왔습니다. 

이렇게 Procedure가 호출될 때 사용되는 값들은 Local Value로, Procedure 안에서 인자의 값이 변경되더라도 Procedure 바깥에 있는 변수의 값은 변하지 않습니다. 반면, Call-by-Reference 방식에서 Procedure를 호출할 때는 그 값 자체가 아닌 그 값의 Reference를 Procedure로 보냅니다. 즉, 그 변수 자체를 Procedure가 수정할 수 있습니다.

Call-by-Reference 방식을 지원하도록 하기 위해 꺽쇠괄호를 사용할 겁니다.

Procedure를 호출할 때, 인수를 꺽쇠괄호로 감싸주면 그것은 Call-by-Reference를 사용하겠다는 것을 의미합니다.

 

감사합니다.

---

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