[프언] #19. Continuations

Redex와 Continuation

(1 + 2) + (3 + 4)

위 Expression을 계산한다고 가정합시다. 그럼 아래와 같은 순서로 계산이 진행됩니다.

• Expression 1을 계산해 1을 얻습니다.
• Expression 2를 계산해 2를 얻습니다.
• 1과 2를 더해 3을 얻습니다.
• Expression 3을 계산해 3을 얻습니다.
• Expression 4를 계산해 4를 얻습니다.
• 3과 4를 더해 7을 얻습니다.
• 3과 7을 더해 10을 얻습니다.

이 과정 중 어떤 과정을 기준으로 저희는 과정 전체를 두 부분으로 쪼갤 수 있습니다. 이렇게 어떤 과정을 기준으로 그전에 시행된 작업을 Redex, 그 이후에 시행될 작업을 Continuation이라고 합니다.

계산 과정을 기술할 때, 저희는 Continuation을 _를 포함한 Expression으로 나타낼 수 있습니다. 예를 들어 1을 계산해 1을 얻는 과정에서 Redex는 1입니다. 그리고 Continuation은 (_  +2 ) + (3 + 4)입니다. 이에 착안해 Continuation을 아래와 같이 프로시져로 만들 수 있습니다. 

proc x ((x + 2) + (3 + 4))

이렇게 Expression을 계산하는 과정은 Redex와 Continuation을 계산하는 과정으로 생각할 수 있습니다.

 

Continuation-Passing Style (CPS)

CPS는 프로그래밍의 스타일로, 계산된 결과를 남아 있는 계산 과정에 파라미터로 넘기는 방식입니다. 지금까지 저희가 알고 있는 프로그래밍 스타일은 Store-Passing Style (SPS) 인데요. 예시를 통해 둘의 차이가 뭔지 알아보겠습니다.

def factorial(n: Int): Int =
	if (n <= 1)
		1
	else
		n * factorial(n - 1)

이는 SPS로 짜여진 팩토리얼을 계산하는 코드입니다. 이 프로시져는 n을 받아 n! 을 리턴합니다. 그러나 CPS로 짜인 프로시져는 어떤 값을 리턴하지 않습니다. n을 받아 n!을 계산한 이후, n! 을 Continuation에 넘겨줍니다. 

def factorialCPS(n: Int, k: Cont): Int =
	if (n <= 1)
		k(1)
	else
		factorialCPS(n - 1, x => k(n * x))

이런 식으로 작동하는 것이 CPS입니다. 

 

Small-Step Semantics

1+2라는 Expression을 계산하면 3이 됩니다. 이렇게 하나의 State에서 다음 State로 넘어가는 것을 Reduction이라고 합니다. 그러면 프로그램을 계산하는 것은 여러 번의 Reduction을 반복하는 것이라고 생각할 수 있습니다.

저희 언어에 이 State 개념을 한번 추가해보겠습니다. 각 State는 Computation Stack과 Value Stack, 이렇게 2개의 Stack으로 정의됩니다. Computation Stack $k$에는 현재 계산되고 있는 프로시져나 연산이 저장됩니다. Value Stack $s$에는 계산에 필요한 값들이 저장됩니다. $k$와 $s$로 정의되는 State를 나타내기 위한 기호로 $k||s$를 사용합니다.

Reduction이 일어날 때, Computation Stack에서 원소를 하나 꺼내고 이 꺼내진 원소가 어떤 원소인지에 따라 Value Stack에서 원소들을 꺼내 연산을 진행합니다. 그리고 연산이 끝나면 계산된 새로운 값은 다시 Value Stack으로 들어갑니다.

예를 들어 현재 State가 아래와 같다고 생각합시다.

$$+::k||2::1::s$$

먼저 Computation Stack에서 하나를 꺼내면 그 값은 +입니다. +는 2개의 Value를 필요로 하므로 2개의 원소 2, 1을 꺼내 연산을 진행하고, 그 값인 3을 Value Stack에 넣습니다. 그러면 아래와 같은 상태가 됩니다.

$$k||3::s$$

Computation Stack에 있는 상수 Expression은 [] |- 1와 같이 표기합니다. 이를 계산하면 아래와 같습니다.

(*은 빈 Value Stack을 의미합니다.)

만약 위 과정이 정상적으로 시행되다가 Computation Stack에 있는 모든 연산이 빠져나오면, 이것을 Normal Termination이라고 부릅니다. 오류 없이 프로그램의 계산이 끝났다는 거죠. 반대로 연산 중 뭔가 문제가 생기면 이것을 Abnormal Termination이라고 합니다. Normal Termination 이후 계산된 결과값을 더 큰 스케일의 Semantic으로 옮기면 아래와 같습니다.

 

감사합니다.

---

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