[프언] #06. Procedures
저번 글에서 프로그래밍 언어를 하나 설계하는 것을 시작했고 Value, Environment, Expression 등을 정의해보았습니다. 이번 글에서는 이를 더 확장해서 Procedure라는 것을 한번 정의해보겠습니다.
Procedure
Procedure란, 다른 프로그래밍 언어에서 함수의 역할을 하는 Value입니다.
let f = proc (x) (x - 11)Procedure를 정의하기 위해서 "proc"이라는 단어를 사용하며 첫번째 괄호에는 이 함수의 입력값을, 두번째 괄호에는 출력값을 적어줍니다. 위의 예시에서 $f$라는 Procedure는 x를 받아 x-11을 출력하는 함수와 같이 작동합니다.
let f = proc (x) (x - 11)
in (f 77)이 Procedure를 Call하기 위해서는 먼저 이름을 적어주고, 그 다음에 입력값을 적어줍니다. 따라서, 위 예시를 계산한 값은 77에서 11을 뺀 66입니다.
Static Scoping vs. Dynamic Scoping
여기서 생각해보아야 할 개념이 하나 있습니다. 아래의 예시를 보겠습니다.
let x = 1
in let f = proc (y) (x + y)
in let x = 2
in (f 3)f는 y를 입력받아 x + y를 계산하는 Procedure입니다. 그런데 문제는 f가 정의될 때 x의 값은 1이지만, 그 이후에 x의 값이 2로 바뀐 뒤 f가 실행되었습니다. 그러면 (f 3)은 3+1인 4가 되어야 할까요? 아니면 3+2인 5가 되어야 할까요?
사실 정답은 없습니다. 관점의 차이죠. f가 정의될 때의 x값을 기준으로 계산하는 관점을 Static Scoping, f가 실행될 때의 x값을 기준으로 계산하는 관점을 Dynamic Scoping이라고 부릅니다.
Static Scoping에서는 Procedure가 정의될 때의 Environment를 따라 계산이 진행되기 때문에 위의 코드는 4로 계산되며, Dynamic Scoping에서는 Procedure가 실제 계산될 때의 Environment를 따라 계산이 진행되기 때문에 위의 코드는 5로 계산됩니다.
많은 현대 프로그래밍 언어에서 Static Scoping을 사용합니다. Static Scoping에서는 한 번 Procedure가 정의되고 나면 Procedure에 묶여 있는 변수들을 수정하거나, 삭제해도 아무런 문제가 발생하지 않기 때문에 Dynamic Scoping에 비해 비교적 안전하다는 장점이 있습니다.
그럼 이제 저희 언어가 Static Scoping을 사용한다고 가정하고, Syntax를 한번 기술해보도록 하겠습니다. 먼저 $\mathbf{Val}=\mathbb{Z}+Bool$에 새로운 종류의 Expression이 추가되었으니, 아래와 같이 적을 수 있습니다.
$$\mathbf{Val}=\mathbb{Z}+Bool+Procedure$$
그리고 Procedure는 입력받을 Var과 계산할 Expression, 그리고 Environment로 구성됩니다. 따라서, 아래와 같이 적을 수 있습니다.
$$Procedure=Var\times E \times Env$$
이제 Inference Rule을 사용해서 Procedure를 나타내보겠습니다.
먼저 Procedure를 정의하는 부분은 위와 같이 간단하게 나타낼 수 있습니다.
이건 Procedure를 실제 계산하는 부분입니다. $E_1$ 자리에 Procedure가 들어갑니다. 저희는 지금 Static Scoping을 사용하고 있기 때문에, $E_1$이 정의될 때의 Environment인 $\rho'$에서 실제 계산이 진행되는 것을 확인할 수 있습니다.
let x = 1
in let f = proc (y) (x + y)
in let x = 2
in (f 3)이건 아까 들었던 예시인데요, Inference Rule을 이용해서 위 코드를 한번 계산해보도록 하겠습니다. 코드 제일 윗부분인 let x = 1부터 차근차근 분해를 시작해봅시다.
그리고 이제 오른쪽 윗부분에 있는 코드의 제일 윗부분인 f를 정의하는 부분 역시 아래와 같이 분해가 가능합니다.
다시 오른쪽 윗부분의 코드는 아래와 같이 계산할 수 있습니다.
이 모든 Inference Rule들을 다 합쳐주면 하나의 식으로 나타내지긴 하겠지만 식이 너무 커지니 생략하도록 하겠습니다.
이제 반대로 Dynamic Scoping에서도 똑같이 Syntax를 기술해보겠습니다. 먼저, Dynamic Scoping에서는 Procedure를 정의할 때, Environment가 중요하지 않습니다. 따라서 Dynamic Scoping에서의 Procedure는 변수와 Enviroment, 2개의 인수로만 정의될 수 있습니다.
$$Procedure=Var\times E$$
Inference Rule을 이용하면 위와 같이 나타낼 수 있습니다. Static Scoping에서는 Expression을 계산할 때 $\rho'$을 이용했지만, Dynamic Scoping에서는 주어진 Environment $\rho$를 그대로 사용하는 것을 확인할 수 있습니다.
let x = 1
in let f = proc (y) (x + y)
in let x = 2
in (f 3)이 예시를 똑같이 Dynamic Scoping에서 계산해보겠습니다.
먼저, 이 과정까지는 아까와 동일합니다.
위 과정에서 Procedure를 정의하는 과정, 그리고 계산하는 과정에서 차이점 위주로 보시면 이해가 될 듯 합니다.
Recursive Procedures
이럻게 정의된 Procedure에는 문제점이 있습니다. 바로 귀납적인 함수를 정의할 수 없다는 것입니다. 귀납적인 Procedure를 사용하기 위해서, 새로운 변수 RecProcedure를 만들겠습니다.
$$RecProcedure = Var \times Var \times E \times Env$$
감사합니다.
이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.