Delimited Continuation (작성 중)

아이디어

간략하게, Delimited continuation(구분?한정? 후속문)의 아이디어를 짚으면, 보통 Continuation Passing Style이라 할 때, 프로그램에서 현 시점 이후에 실행할 모든 작업이 후속문으로 잡히는 데, Delimited Continuation은 일정 범위까지만 후속문으로 잡을 수 있습니다.

reset, shift

Cont모나드에는 callCC외에 reset, shift 구현이 있습니다. hoogle - Cont

reset :: Cont r r -> Cont r' r
-- reset m delimits the continuation of any shift inside m

shift :: ((a -> r) -> Cont r r) -> Cont r a
-- shift f captures the continuation up to the nearest enclosing reset and passes it to f

아래 코드는 Calvin’s Notebook - Delimited continuation에서 발췌했습니다.

1 + reset (2 * shift \k -> k (k 5))
^^^        ^^^       ^^^^^^^^^^^^^

k는 후속문을 받을 자리인데, reset 다음부터 shift 이전까지를 후속문으로 받아 옵니다. 1+를 제외한, reset이 구분한 2*까지만 후속문이 됩니다.

\k -> k (k 5)가 현행문,
2 *가 후속문,

일반 Continuation과 Delimited Continuation의 차이

보통 봐왔던 Continuation과 차이는 1+는 후속문에 안들어갑니다.
reset이하로 후속문 실행 작업이 끝나 (k로 2 *가 들어가) 2 * (2 * 5) = 20이되고, 최종 결과는 20 + 1해서 21이 됩니다.

※ 왠 일로, 후속문을 받는 람다 헤드에 있는 변수는, 거의 모든 텍스트에서 \k로 통일되어 있습니다. k가 보이면, 그 자리로 후속문이 들어가겠거니 생각해도 됩니다.

하스켈에서 reset, shift 구현

CPS - Continuation Passing Style에서 callCC 코드를 뜯어 봤던 것처럼 reset과 shift를 뜯어보겠습니다.

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
           ^^^^^^^^^^^^^^^

shift와 비슷한 고(고)차 함수 모양입니다. callCC 안에서 밑줄 친 서명 모양의 함수를 넣어줄 거라 예상할 수 있습니다.

runC :: Cont r r -> r
runC ct = runCont ct id

runC가 꼬리로 id를 붙여, 마치 더 이상 꼬리를 연결할 수 없도록 마감하는 역할을 합니다.

reset :: Cont a a -> Cont r a
reset CONT = Cont $ \k -> k (runC CONT)

runC로 마감을 해 놓고는, 또 다시 꼬리를 붙일 수 있도록 k를 받게끔 만들고 있습니다. 왜 이렇게 할까요?

Continuation을 더 이상 못 붙이도록 만든 후, 다시 붙이게 하는 이유

shift :: ((a -> r) -> Cont r r) -> Cont r a
          ^^^^^^^mkCONT^^^^^^^
shift mkCONT = Cont $ \k -> runC (mkCONT k)

callCC와 비슷하게 고(고)차 함수를 받습니다. 바인드가 다른 Cont와 붙일 때, 꼬리를 넣어주는데, 이 걸 써먹는 모양의 함수입니다. 위 예시에서는 꼬리를 두 번 써먹는 k (k 5) 모양입니다. 물론 결과는 다시 Cont 액션인데, 여기서 또 runC를 돌려 마감시킵니다. 어떻게 reset, shift 조합이 흐름의 변화를 만들어내는지 이해가 안가 다음처럼 다 펼쳐놔 봤습니다.

1 + reset (2 * shift \k -> k (k 5))

Calvin 글에선 아래와 같이 liftM2를 이용해 하스켈 Cont모나드로 구현한 예시를 보여주는데, 전 bind로 구현한 예시가 궁금했습니다.

example :: Cont Int Int
example = liftM2 (+) (return 1) $
                     reset (liftM2 (*) (return 2) 
                           (shift (\k -> k <$> k <$> (return 5))))
            

아래와 같이 bind로 바꿨습니다.

example2 :: Cont Int Int
example2 = do -- 바깥 컨텍스트(가)
  x <- reset $ do -- 바깥과 구분된 내부 컨텍스트(나)
    y <- return 2
    z <- (shift (\k -> return $ k (k 5)))
    return $ y * z
  return $ x + 1

새로운 컨텍스트

일단, reset이 새 컨텍스트 (나)를 시작하는 건 눈에 잘 보입니다.

여기서 어떻게 y *라는 continuation이 \k로 들어가는지 알아보는 게 목표입니다.

newtype Cont r a = Cont ((a -> r) -> r)
runCont :: Cont r a -> (a -> r) -> r
-- Cont액션을 CONT라 표기하고, Cont액션을 만들어mk내는 걸 mkCont로 표기하겠습니다.
                  cont $ \c -> runCont CONT                           c
CONT >>= mkCONT = cont $ \c -> runCont CONT (\x -> runCont (mkCONT x) c)
reset CONT = Cont $ \rest -> rest (runC CONT)
shift mkCONT = Cont $ \k -> runC (mkCONT k)

reset 안 쪽 (나)만 따로 떼어서 보겠습니다.

do 
  y <- return 2
  z <- (shift (\k -> return $ k (k 5)))
  return $ y * z

>>=가 눈에 보이게 하면,

return 2 >>= \y -> shift (\k -> return $ k (k 5)) >>= \z -> return y * z
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^(다)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^(라)

Cont 모나드의 바인드는 마치, 같은 모양의 레고 블럭을 끼우듯 연결합니다. return 2의 후속문은 (다)가 아니라, (라)입니다. ※ 모나드 3법칙으로 봐도 마찬가지입니다. \y...문은 (다)가 아니라 (라)입니다.

(라)를 2에 적용하니, \y에 2를 넣어 주면

shift (\k -> return $ k (k 5)) >>= \z -> return 2 * z

shift를 풀어 보겠습니다.

shift (\k -> return $ k (k 5)) >>= \z -> return 2 * z
Cont $ \k' -> runC ((\k -> return $ k (k 5)) k') >>= \z -> return 2 * z
-- shift는 인자로 받은 Cont액션 안에 있는 값을 꺼내는 역할만 합니다.
-- 그 안에 있는 액션은 앞으로 들어 올 후속문 `k`에 따라 값이 정해집니다.
Cont $ \k' -> runC (return $ k' (k' 5)) >>= \z -> return 2 * z
Cont $ \k' -> k' (k' 5) >>= \z -> return 2 * z

‘>>=’ 동작으로 k'에 (2 *)를 넣어 주면, 2 * (2 * 5) = 20이 됩니다.

정리하면, reset으로 제한된 영역을 만들고, 그 안에서 또 shift로 영역을 구분합니다. reset도, shift도 runC로 끊은 후, 다시 Cont로 만드는 이유입니다.

생각 스트레칭

\x ... --> \y {\y1 ... --> \y2 ... --> \y3 ...} --> \z ...

바깥 컨텍스트 속에 있는 값과 관계 없이 \y{...}만 경계를 두려면 어떻게 하면 될까요?
\y1, \y2, \y3는 외부와 소통하는 유일한 길인y와 관계없는 상태로 일단 만들어야 한다는 게 명확합니다. runC가 하는 역할입니다.

코루틴

@todo useEffect보다 더 좋은 게 있다고? - YOKITOMI.log
Javascript의 코루틴을 쓰는, useEffect를 대체할 수 있는 useEff를 소개하는 글입니다.

try, catch

@todo

Algebraic Effect

@todo

Proposal - Delimited Continuation Primops로 올라와 있던 게 GHC 9.6.1에 프리미티브 기능으로 들어 갔다 합니다.

참고
Keynote: Delimited Continuations, Demystified by Alexis King | Lambda Days 2023
중급자들 볼만한 자료들을 쏟아내고 있는 Alexis King이, 눈높이를 최대한 낮춰줘서, 저는 볼 만한 영상이었습니다.