2강 : 꼬리재귀, 매개변수 다형성, 사용자 정의 타입
3강 : 커링, 스테이징, map, filter, fold
2강에서 우리는 accumulator변수를 이용해 꼬리재귀 함수를 만드는것을 보았다.
이번에는 함수를 accumulator처럼 다루는 방식, 컨티뉴에이션 패싱 스타일 (Continuation-Passing Style, 줄여서 CPS)을 다뤄본다.
아 참고로 썸네일은 여기서 다운받아서 오늘의 주제를 합성해서 올린다. (2강, 3강은 원래 있던거 씀)
1. CPS의 예시
(2+3)*4라는 계산을 생각해보자. 이 식을 계산할때 우리는 2와 3을 더하고, 그 결과값을 4에 곱한다.
방금 말한 문장에서 “결과값” 이라는 개념을 중요하게 생각해보자.
이 계산을 표현할 수 있는 다른 방식이 있을까? 람다식을 사용할 수도 있다.
과 같이 말이다. 이러면 결과값이 res에 저장된다.
한걸음 더 나아가서 이 계산을 하나의 값을 함수에 계속 넘기면서 추가 연산을 하는 식으로 생각해보자.
를 생각해보자.
2를 람다식에 넣어서
가 되고 결과적으로 20이 되니 (2 + 3) * 4와 똑같은 계산을 하는 표현식이다. 좀 이해하기 어렵게 썼을 뿐.
저 식은 바로 20이 되지만 만약 여기서 이 계산 자체만 따로 저장하려면 위 식을 람다식으로 감싸줘야 한다.
1강에서 잠시 나온 unit 타입을 인자로 받는 람다식을 쓰자 (unit은 void같은거임).
(2 + 3) * 4와 위의 람다식은 똑같은 일을 한다. 단지 한쪽은 바로 20이라는 값이 되고, 한쪽은 람다식으로 남아있어 20이 되지 않는다. (함수가 이미 값이기 때문에)
이 람다식은 (2+3)*4가 하는 계산을 나중에 할수 있게 저장해둔다고 볼 수도 있다. 이 개념을 컨티뉴에이션(continuation)이라고 한다.
또는, 컨티뉴에이션을 어떤 계산이 행해질지 적어놓은 지시서로 볼 수도 있다.
컨티뉴에이션은 오늘 강의의 핵심적인 개념으로, 함수는 컨티뉴에이션을 추가하거나 다른 컨티뉴에이션이 실행되게 할수도 있다.
2. CPS를 직관적으로 이해하기
다음 코드를 보자.
fun factCPS 0 k = k 1
| factCPS n k = factCPS (n - 1) (fn res => k (n * res))
factCPS는 두개의 인자를 받는다. 첫번째는 팩토리얼을 계산하기 위한 카운터 n이고, 두번째 k는 컨티뉴에이션이다.
이 k는 계산이 끝나고 난뒤에 남아있는 계산에 해당한다.
만약 n!를 그냥 계산하고 싶고, 아무 계산도 남아있지 않다면
를 쓸 수 있으며,
n!의 결과를 문자열로 바꾸고 싶으면
을 쓸 수 있다. 이런식으로 CPS는 나중에 할 계산을 적어놓는 방식으로 작동한다.
다음은
가 어떻게 계산되는지 보여준다.
Int.toString 6으로 계산이 되는걸 확인할 수 있다.
하지만 왜 이게 되는걸까?
우리는 팩토리얼을 계산하기 위한 지시서를 만드는 거다. 지시서는 아래로 내려가면서 만들고, 실제로 행해지는건 아래에서 위로 이다.
재귀호출을 하면서 우리는 지시서를 만들고, 호출이 밑바닥까지 내려가서 k 1이 호출될때 1부터 n까지 곱하면서 지시서대로 행한다.
k는 “이후에 행해질 지시서”를 의미한다. 예를 들어 i를 곱해야 하는 시점에서
의 k는 i+1, i+2, …, n을 곱하라 라는 지시서를 의미하고, 현재 i를 곱했으니 다음에는 i-1를 곱해야 하므로 factCPS n-1이 된다.
재귀 호출이 그 결과값을 컨티뉴에이션으로 전달한다고 볼 수도 있다.
factCPS n k는 n!를 k에게 전달한다고 볼 수 있고, 더 나아가
는 (n-1)!를 저 람다식에게 전달한다고 볼 수 있다.
컨티뉴에이션은 또 스택처럼 작동한다. 위의 factCPS가 작동하는걸 보면, 람다식을 다른 람다식으로 감싸거나 (push), 인자가 주어졌을때 람다식을 pop하는것 처럼 작동한다.
이렇게 스택 안에 컨티뉴에이션이 담겨있고, factCPS 함수 내에서 재귀호출을 할때 스택을 쌓아올리고, 재귀가 끝난 시점에 k 1이 되어 람다식에 호출될때부터는 스택을 하나씩 pop하는것으로 생각하자.
아직 잘 이해가 되지 않는다면 다시 잘 읽어보자. 어려운 개념이고 나도 사실 헷갈린다.
3. CPS의 정의
컨티뉴에이션이란 어떠한 계산의 결과에 무엇을 해야하는지 지시하는 함수를 말한다.
함수가 컨티뉴에이션 패싱 스타일 (Continuation Passing Style, CPS)로 쓰여졌다는 것은 다음의 세가지 조건을 만족한다는 뜻이다.
- 컨티뉴에이션을 인자로 받고 함수 몸체에서 쓴다.
- 컨티뉴에이션이 담긴 함수를 꼬리호출한다.
- 꼬리호출에서만 컨티뉴에이션을 호출한다.
우리가 본 factCPS 함수도 CPS이다.
| factCPS n k = factCPS (n-1) (fn res => k (n * res))
컨티뉴에이션 k를 인자로 받고 쓰며, 컨티뉴에이션이 담긴 람다식을 꼬리호출 하고, 꼬리호출에서만 컨티뉴에이션을 호출한다.
4. 트리 자료구조에서의 CPS
다음의 treeSumCPS 함수는 주어진 트리의 모든 원소의 합을 구하는 CPS 함수이다.
Empty |
Node of 'a tree * 'a * 'a tree
fun treeSumCPS Empty k = k 0
| treeSumCPS (Node (L, x, R)) k =
treeSumCPS L (fn leftSum => treeSumCPS R (fn rightSum => k (leftSum + x + rightSum)))
(* 1
/ \
2 3
/ \ / \
4 5 6 7 *)
val t = Node(Node(Node(Empty,4,Empty),2,Node(Empty,5,Empty)),1,
Node(Node(Empty,6,Empty),3,Node(Empty,7,Empty)))
treeSumCPS t Int.toString
treeSumCPS를 읽어보면 뭔가 이상하다. 재귀호출 안에 람다식 안에 재귀호출이 또 있다…?
하지만 위의 코드를 직접 실행시켜보자. 트리의 노드를 모두 더한 값을 string으로 바꾸니까 “28”이 나올 것이다. 따라서 코드는 잘 작동된다.
이제 저 함수가 왜 되는지 살펴보자.
우선 트리가 빈 트리라면 합은 0이므로 다음 컨티뉴에이션에 0을 넘기면 된다.
빈 트리가 아니라면, 트리는 datatype ‘a tree의 정의에 의해 Node(L, x, R)의 구조를 가지고 있을 것이다 (L은 왼쪽 서브트리, R은 오른쪽 서브트리, x는 노드에 담겨있는 값).
| treeSumCPS (Node (L, x, R)) k =
이제 위에서 말했던 지시서 비유를 떠올리자. k는 이후에 행해질 지시서를 의미한다.
또한 3강에서 설명했듯이 재귀함수가 올바른 값을 도출한다고 가정하자. treeSumCPS L k’는 왼쪽 서브트리의 합을 구해서 k’에 전달할 것이다.
전체 트리의 합 = 왼쪽 서브트리의 합 + 오른쪽 서브트리의 합 + 현재 노드의 값 이니까 아직 지시서를 더 만들어야 한다.
어디에 만들까? k’안에 지시서를 하나 더 만드는 거다!
로 두자. 이러면 왼쪽 서브트리의 합을 구한 다음, 그 결과값을 다른 지시서에 보낸다.
무슨 지시서로 보내냐고? 오른쪽 서브트리의 합을 구하라 라는 지시서에 보낸다!
아직 현재 노드의 값을 더하지 않았으므로 지시서 만들기는 끝나지 않았다.
지시서를 하나 더 만든다!! 어디에? k'' 안에 지시서를 하나 더 꽂아넣는다.
이다. 이러면 전체 트리의 합을 구한다…하지만 이건 정답이 아니다. 아직 끝나지 않았다.
였지 않은가? k는 결과값이 구해진 후 행해질 지시서였지 않은가? 따라서 우리가 구한 결과값을 k로 보내야 한다.
따라서
가 된다.
정리하면 전체 함수는 다음과 같다.
| treeSumCPS (Node (L, x, R)) k =
treeSumCPS L (fn leftSum => treeSumCPS R (fn rightSum => k (leftSum + x + rightSum)))
5. 백트래킹을 이용해 배낭문제 풀기
일단 배낭 문제가 뭔지 알아야 한다.
배낭 문제에서는 배낭과 아이템이 주어진다. 아이템은 무게와 가격이 있으며, 가격이 높은 아이템을 배낭에 최대한 많이 담는것이 좋다. 단, 배낭은 무게 제한이 있어서 일정 무게를 넘어가면 배낭이 찢어진다.
우리가 풀 배낭 문제에서는, 같은 아이템을 2번 이상 담을 수 있으며, 최소 가격이 주어진다.
당신의 목표는 아이템을 배낭에 담아 총 가격의 합이 이 최소가격 이상이 되게 하는 것이다. 물론 배낭이 찢어지지 않을 정도로 담아야 한다.
배낭 문제를 푸는 CPS함수를 만들어 보자. 우선 무게와 가격은 둘다 int 타입인데, 헷갈리지 않게 독립적으로 정의하자.
type value = int (* 가격 *)
이제 weight와 value를 int처럼 쓸 수 있다.
우리는 knapsackCPS라는 함수를 만들어 볼것이다. 보통 CPS함수는 인자로 컨티뉴에이션을 한개만 받는데, knapsackCPS는 두개를 받을 것이다.
하나는 해가 존재할때 부르는 컨티뉴에이션 (success continuation; sc)라고 할것이고
다른 하나는 해가 없을때 부르는 컨티뉴에이션(failure continuation; fc)라고 한다.
sc : (value * weight) list -> ‘a 이고 fc : unit -> ‘a로 할 것이다.
다른 인자는 무엇이 있을지 생각해보자. 일단 아이템의 리스트를 받아야 한다.
아이템은 (value, weight) 쌍으로 정의할 수 있으니 L : (value * weight) list라는 리스트가 필요하다.
또 최소 가격 minVal : value와 가방이 견딜 수 있는 최대 무게를 저장할 인자 maxWeight : weight이 필요하다.
따라서 knapsackCPS : (value * weight) list -> value -> weight -> ((value * weight) list -> ‘a) -> (unit -> ‘a) -> ‘a이다.
사실 이건 별로 중요하지 않지만 함수형 프로그래밍에서 타입이 얼마나 괴상해질 수 있나를 보여주고 싶었다.
리스트를 다루는 함수니까 L이 빈 리스트일때와 (v, w)::xs일때로 구분한다.
| knapsackCPS ((v, w)::xs) minVal maxWeight sc fc =
L이 빈 리스트라면 어떻게 해야할까? 주어진 리스트가 최소 가격을 만족하는지를 봐야 하니 minVal <= 0이여야 한다. 또한 가방이 찢어지면 안되니 maxWeight >= 0이여야 한다.
둘다 만족하면 []라는 해가 존재하니 sc []를 부르고 아니라면 해가 없으므로 fc를 부른다.
fc의 인자 타입은 unit이고 unit은 ()로도 쓸 수 있으니 fc ()를 쓰면 된다. 따라서
if minVal <= 0 andalso maxWeight >= 0
then sc []
else fc ()
| knapsackCPS ((v, w)::xs) minVal maxWeight sc fc =
L이 (v, w)::xs의 형태라면? 일단 maxWeight < 0인지 확인한다. 만약 그렇다면 해가 아예 있을 수 없기 때문이다.
if maxWeight < 0
then fc ()
else
이제 어려운 파트다. 어떻게 문제를 풀어야 할까?
CPS 함수는 보통 재귀적이므로 knapsackCPS를 호출해야 할것이고, 이건 꼬리호출이 되야 하므로 else 바로 뒤에 올 것이다.
if maxWeight < 0
then fc ()
else knapsackCPS ? ? ? sc' fc'
재귀적으로 문제를 풀려면 문제를 작게 만들어야 한다. 리스트를 더 작은 리스트로 만들거나 minVal또는 maxWeight를 감소시키는 방법이 있다.
하지만 우리가 푸는 배낭 문제에서는 리스트에서 같은 아이템을 2회 이상 가져갈 수 있으므로 리스트를 더 작게 만드는 방법은 옳지 않다.
따라서 minVal과 maxWeight를 감소시킬 것이고, 첫번째 물음표는 아무것도 바뀌지 않은 ((v, w)::xs)이다.
if maxWeight < 0
then fc ()
else knapsackCPS ((v, w)::xs) ? ? sc' fc'
이렇게 생각해보자. (v, w)라는 아이템을 해 리스트에 넣어보는 것이다. 만약 되면 sc’를 호출하고, 안되면 fc’를 호출한다.
(v, w)가 해 리스트에 담겨있다는 정보를 최소 가격에서 v를 빼고, maxWeight에서 w를 뺌으로서 표현할 수 있다.
최소 가격이 v만큼 낮아지는것과 가격이 v인 아이템을 해 리스트에 추가하는것은 같은 정보를 나타내고, 또 가방의 수용가능한 무게가 w만큼 낮아지는것과 무게가 w인 아이템을 추가하는것도 같다.
if maxWeight < 0
then fc ()
else knapsackCPS ((v, w)::xs) (minVal - v) (maxWeight - w) sc' fc'
이제 sc’와 fc’ 컨티뉴에이션을 만들어야 한다.
만약 (v, w)를 해 리스트에 추가했는데 된다면? 그대로 출력값에 (v, w)를 추가한다.
만약 안된다면? 출력값에 아무것도 추가하지 않고, (v, w)가 없던것처럼 행동한다.
이게 함수형에서의 백트래킹이다. 해보고 안됐을경우 뒤로 한발짝 물러나서 다른 방식을 시도해보는 것이다.
그리하여 전체 코드는 이렇게 된다.
type value = int
fun knapsackCPS [] minVal maxWeight sc fc =
if minVal <= 0 andalso maxWeight >= 0
then sc []
else fc ()
| knapsackCPS ((v, w)::xs) minVal maxWeight sc fc =
if maxWeight < 0
then fc ()
else knapsackCPS ((v, w)::xs) (minVal - v) (maxWeight - w)
(fn L' => sc ((v, w)::L'))
(fn () => knapsackCPS xs minVal maxWeight sc fc)
knapsackCPS [(5, 4), (7, 5), (11, 9), (23, 15)] 37 26 (fn x => x) (fn () => [])
(* 결과값 = [(7,5),(7,5),(23,15)] *)
직접 코드를 실험해보자. 맞게 나온다.
CPS는 일반적으로 실무에서 쓸일이 아예없지만, 특정한 상황에서 굉장히 유용하다. 컴파일러를 개발할때 CPS로 IR을 만들면 최적화를 더 쉽게 할 수 있다고 한다.
이해가 안된다면 정상이다. 나도 이걸 수업에서 들은지 몇개월이 지난 지금에서야 간신히 머리에 들어갈락 말락 하고 있다. 처음 들었을때는 아예 기말고사에 이게 나온다는 사실에 멘탈이 나갔다.
번역하면서 내가 먼저 일단 이해한 뒤에 글을 쓰려고 했고 좀더 쉽게 전달하려고 의역한곳이 많은데 도움이 되었으면 좋겠다.
사실 이 4강까지 따라와준것만 해도 고맙다. 여러분 덕분에 공부할 힘이 난다.
3강에서도 말했듯이 궁금하거나 이해 잘 안되는거 있으면 댓글로 물어보면 내가 아는선에서 최대한 답변해줄테니 많이 물어봐라. 묻고 답하는 과정에서 배우는것도 크니까.
다음에는 우리가 이때까지 배웠던걸 총동원해서 n-Bishops문제의 변형판을 풀어볼 것이다.
