최근에 arota라고 하는 AI와 함께하는 일정 알람 앱을 만들었습니다. AI에게 할 일을 만들어 달라고 하면 할 일과 함께 끄지 않으면 계속 울리는 알람을 등록해줍니다. 할 일을 놓치지 않게 해주고 또 AI가 이전 할 일들과 일정을 잘 조율하거나 너무 큰 할 일이라면 단계적으로 쪼개서 할 일을 제안해 주기도 합니다. 성인 ADHDer 분들에게 도움이 될 것으로 생각합니다. 제목은 조금 무섭게 해두고 서비스 소개가 길었네요.

Arota 역시 하스켈로 백엔드를 만들어서 운영 중입니다. 이번에도 Constacts 백엔드에서 한 것처럼 Effect 처리를 mtl 스타일로 했는데요. 최근에 Zurihac 2025 영상을 보고 effect handler를 effectful로 바꿨습니다. effectful에 대한 내용은 다른 글로 정리해야 할 것 같네요. 이 글에서는 하스켈 effect handler에서 여러 effect handler가 아직 해결하지 못한 비결정 계산 지원에 관한 문제와 관련되어 있는 Continuation에 간단히 정리하려고 합니다. 아쉽게도 아직 effect handler와 관련된 문제에 대해서는 다 이해하지 못해서 알게되면 또 정리하겠습니다. 여기서는 Continuation의 개념을 간단히 정리해보려고 합니다.

Continuation

오래전에 박상규님께서 Continuation에 대해 자세히 정리해주셔서 정리하는데 큰 도움이 되었습니다. 조금 긴 내용이지만 짤게 요약해보려고 합니다. 그래도 요약외에 가치를 더해 본다면 상규님 글에 후속으로 예고했던 Delimited Continuation에 대해 짧게라도 소개한다는 점이 되겠네요. 상규님이 Continuation을 후속문로 번역해 주셨기 때문에 후속문라는 말도 섞어 쓰겠습니다. (Continuation은 길기도하고 오타가 날 수도 있어서 :))

Continuation은 무엇인가?

후속문(Continuation)는 코드의 평가와 관련되어 있습니다. 다음과 같은 프로그램이 있다고 합시다.

(+ 1 (+ 2 3))

이 코드를 평가할 때 여러가지 방법이 있겠지만 만약 안쪽에 있는 (+ 2 3)을 먼저 평가한다면 5가 됩니다. 그 다음에 해야 할 일은 평가 결과인 5에 프로그램의 나머지 부분인 (+ 1 ⛳️)를 적용하는 일입니다. ⛳️에 5를 넣어서 6을 얻으면 됩니다. 여기서 프로그램의 나머지 부분을 후속문(Continuation)이라고 부릅니다. 프로그램의 나머지 부분은 상대적이기 때문에 평가하는 위치에 따라 후속문이 다를 수 있습니다. 만약 위 코드에서 3 값 자체를 평가한다면 3이 되는데 그 기준으로 보면 후속문은 (+ 1 (+ 2 ⛳️)) 입니다.

일급 후속문(Continuation)이란?

후속문을 일급으로 다룰 수 있는 기능이 있는 언어도 있습니다. 함수형 언어에서 함수가 일급이라는 말을 많이 들어봤을 것입니다. 함수가 일급이라는 값과 같아서 이름을 붙여서 나중에 쓰거나 함수의 결과로 돌려줄 수도 있다는 말입니다. 마찬가지로 Continuation에 이름을 붙여 변수에 넣고 나중에 사용하거나 함수의 리턴 값으로 쓸 수 있다는 말입니다. 위에서 본 것 처럼 후속문에는 구멍(⛳️)이 있고 구멍에 값을 넣어야 결과를 얻을 수 있습니다. 그래서 후속문은 함수로 만들어집니다. (+ 1 ⛳️) 후속문은 다음과 같은 함수로 표현하고 일급으로 다룰 수 있습니다.

(fn [x]
  (+ 1 x))

후속문을 잡자!

그럼 코드에서 후속문을 어떻게 함수로 만들어 변수에 넣을 수 있나요? 아쉽게도 모든 언어가 그런 기능이 있는 것이 아닙니다. Continuation 관련 기능이 잘 되어 있는 Racket 언어를 통해 살펴봅시다.

(define saved-k #f)

(+ 1 (call/cc (lambda (k) (set! saved-k k))))

(saved-k 2)
;; 3

이 코드는 (+ 1 ⛳️) 형태의 후속문을 잡아서 saved-k라는 전역 변수에 저장하고 저장된 후속문을 인자 2를 넣어 불러(후속문은 함수 값이기 때문에) 3을 얻는 코드입니다.

여기서 call/cc라고 하는 함수를 사용했습니다. 코드에서 call/cc가 나타나면 call/cc 외 나머지 부분인 후속문을 모두 함수로 만들어 call/cc의 두번째 함수 인자인 k로 넘겨줍니다. 여기서 call/cc의 나머지 부분은 (+ 1 ⛳️) 입니다. 이 함수를 k에 바인딩해서 뒤에 익명 함수에 넘겨줍니다. 위 예제에서 saved-k에 저장했지만 그냥 k 후속문을 불러도 같은 결과 입니다.

(+ 1 (call/cc (lambda (k) (k 2))))
;; 3

잠깐 call/cc 다음에 코드는요?

위 예제에서 call/cc를 부른 결과가 만약 후속문인 (+ 1 ⛳️)라고 한다면 다음과 같이 최종 결과는 4가 되어야 하는 것이 아닌가요?

(+ 1 (call/cc (lambda (k) (k 2))))

;; (call/cc (lambda (k) (k 2)))의 결과가 3이라고 했으니 
;; (+ 1 3)이 되어
;; 4가 나와야 하는 것이 아닌가?

후속문은 후속문 함수인 k를 실행하고 나면 나머지 계산을 하지 않도록 되어 있습니다. 왜냐하면 call/cc를 하고나면 원래 호출 스택이 사라지고 새로운 스택이 생기기 때문입니다. 상규님 글에 call/cc 호출시 콜스택의 변화를 보면 그림으로 잘 설명하고 있습니다.

프로그램의 나머지 부분을 모두 후속문으로 잡지 않기

call/cc를 부르면 부른 곳외 나머지 부분이 모두 후속문로 잡힙니다. 하지만 후속문로 모든 부분을 잡는 것이 아니고 특정 범위를 제한(delimited)해서 후속문로 잡을 수도 있습니다. Racket에 그런 함수들 중에 shift/reset, prompt/control등 다양한 버전이 있지만 여기서는 prompt와 control 함수를 쓰겠습니다. 다음 코드를 봅시다.

(+ 1 (+ 2 (call/cc (lambda (k) (k 5)))))
;; 결과는 후속문 `(+ 1 (+ 2 ⛳️))`에 `5`를 넘겨 `8`이 됩니다.

이 코드는 그냥 call/cc이기 때문에 (+ 1 (+ 2 ⛳️))를 후속문로 잡습니다. 만약 가장 밖에 있는 (+ 1 ...은 빼고 (+ 2 ⛳️) 만 후속문로 잡으려면 prompt라는 함수로 범위를 제한(delimited) 또는 표시할 수 있습니다. 그리고 잡는 부분에는 control을 써주면 됩니다.

(+ 1 (prompt (+ 2 (control k (k 5)))))

control은 call/cc 처럼 익명함수를 인자로 받지 않지만 k에 잡은 후속문을 반환 한다고 보면 됩니다. Racket에 다른 후속문 함수들은 조금씩 기능이 다른 버전들이 있습니다. 위 코드에서 후속문은 prompt로 제한된 곳까지만 잡습니다. 그래서 k에는 후속문 (+ 2 ⛳️)만 잡히고 call/cc처럼 실행이 종료되지 않고 다머지 계산인 (+ 1...을 이어서 합니다. 결과는 8로 같지만 다른 방식으로 실행된 것을 알 수 있습니다.

이러한 후속문을 Delimited Continuation이라고 합니다. (이건 아직 적당한 한글 해석이 없네요)

보너스로 Racket에는 call/comp라고 하는 것도 있는데 그것은 call/cc가 후속문를 실행하고 종료하는 대신 후속문 실행 결과를 가지고 나머지 밖같 부분도 계속 계산을 이어가는 버전도 있습니다.

(+ 1 (+ 2 (call/comp (lambda (k) (k 5)))))
;; 11

후속문 (+ 1 (+ 2 ⛳️))를 잡아 5를 넣은 계산을 밖에 있는 나머지 계산을 이어서 11이라는 결과가 나왔습니다.

마무리

후속문은 goto, if, for, while와 같이 코드의 제어 흐름을 바꾸는 또 다른 개념으로 이해할 수 있습니다. native로 지원하는 언어가 많지 않습니다. 다른 많은 언어를 확인해보지 않았지만 하스켈에서는 Alexis King이 GHC 9.6에 MagicHash 언어 확장을 사용한 prompt#, control0#를 넣어 native로 지원하고 있습니다. 후속문은 여러 언어의 코루틴이나 파이썬의 generator, 스위프트의 Continuation등 다양한 모습으로 보이고 있고 비동기와 같은 복잡한 흐름 제어가 필요한 경우 개념적인 기반으로 사용되고 있는 것 같아 알아두면 좋은 개념일 것 같습니다.

나중에 추가한 하스켈 예제

하스켈도 natvie GHC 9.6부터 native continuation을 지원합니다. 다음 Racket 예제를 하스켈로 바꾸면 다음과 같습니다.

(+ 1 (prompt (+ 2 (control k (k 5)))))

result :: IO Int
result = do
  tag <- mkTag
  (+ 1) <$> (prompt tag $ (+ 2) <$> (control0 tag \k -> k (pure 5)))

두 코드를 비교해서 보면 대략 이해하기 어려운 점은 없습니다. 다음은 위 예제의 하스켈 전체 코드입니다. 다른 의존성은 없고 GHC 9.6 이상에서 실행하면 됩니다.

{-# LANGUAGE BlockArguments #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}

module Main
  ( main,
  )
where

import GHC.Exts (PromptTag#, control0#, newPromptTag#, prompt#)
import GHC.IO (IO (..))

data PromptTag a = PromptTag (PromptTag# a)

mkTag :: IO (PromptTag a)
mkTag =
  IO
    ( \s -> case newPromptTag# s of
        (# s', tag #) -> (# s', PromptTag tag #)
    )

prompt :: PromptTag a -> IO a -> IO a
prompt (PromptTag tag) (IO m) = IO (prompt# tag m)

control0 :: PromptTag a -> ((IO b -> IO a) -> IO a) -> IO b
control0 (PromptTag tag) f =
  IO (control0# tag (\k -> case f (\(IO a) -> IO (k a)) of IO b -> b))

result :: IO Int
result = do
  tag <- mkTag
  (+ 1) <$> (prompt tag $ (+ 2) <$> (control0 tag \k -> k (pure 5)))

main :: IO ()
main = print =<< result