무한 루프를 깨는 방법

Haskell에서 무한 루프를 만드는 것은 쉽습니다.

main = mapM_ print [1..]
-- 1
-- 2
-- 3
-- ...

물론 while(1) 를 사용하여 다른 언어에서도 무한 루프를 생성할 수 있지만 명령형 프로그래밍 언어에서처럼 무한 루프에서 벗어날 수 있습니까break?

Haskell에서 할 수 있는 방법은 다음과 같습니다.

import Control.Monad.Cont

main :: IO ()
main = do
  putStrLn "Start"

  withBreak $ \break ->
    forM_ [1..] $ \i -> do
      liftIO . putStrLn $ "Loop: " ++ show i
      when (i == 5) $ break ()

  putStrLn "End"
  where
    withBreak = flip runContT pure . callCC

실행합니다.

$ runhaskell Main.hs
Start
Loop: 1
Loop: 2
Loop: 3
Loop: 4
Loop: 5
End

가장 중요한 부분은 여기에 있습니다.

withBreak $ \break ->
  forM_ [1..] $ \i -> do
    liftIO . putStrLn $ "Loop: " ++ show i
    when (i == 5) $ break ()

다음은 C 의 동일한 코드입니다.

int i = 0;
while (1) {
  i++;
  printf("Loop: %d\n", i);
  if (i == 5) break;
}

이 기사의 뒷부분에서 withBreak 설명하겠습니다. forM_는 mapM_ 인수가 뒤집힌 함수로 간단히 구현됩니다.

forM_ :: (Monad m) => [a] -> (a -> m b) -> m ()
forM_ = flip mapM_

liftIO는 withBreak에서 IO action을 사용하기 위한 함수이고 when는 첫 번째 인자의 조건이 만족될 때만 두 번째 인자를 실행한다.
forM_ 에 전달된 목록은 [1..] 인데 실제로는 무한 목록이지만 실행 결과에서 볼 수 있듯이 프로세스는 break 로 끝납니다.

먼저 withBreak 의 구현을 살펴보겠습니다.

withBreak = flip runContT pure . callCC

가장 중요한 두 가지는 runContT 와 callCC 입니다.

runContT :: ContT r m a -> (a -> m r) -> m r

callCC :: ((a -> ContT r m b) -> ContT r m a) -> ContT r m a

ContT는 연속 모나드라고 하며, 이는 후속 계산을 처리할 수 있는 모나드입니다.

사실, break의 withBreak $ \break -> ...는 후속 계산을 그냥 버립니다.

여기서 무슨 일이 일어나고 있는지 이해하기 위해 더 세분화withBreak합시다. 우선 ContT 는 다음과 같이 정의되는데, (a -> m r) -> m r 와 동형일 뿐입니다.

newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }

callCC의 구현은

callCC :: ((a -> ContT r m b) -> ContT r m a) -> ContT r m a
callCC f = ContT $ \ c -> runContT (f (\ x -> ContT $ \ _ -> c x)) c

, 그러나 isomorphic을 사용하여 다시 작성하려고 하면 다음과 같이 됩니다.

callCC :: ((a -> (b -> m r) -> m r) -> (a -> m r) -> m r) -> (a -> m r) -> m r
callCC f c = f (\x _ -> c x) c

. 유형은 더 복잡해졌지만 구현은 매우 쉬워졌습니다. 이것으로 withBreak는

withBreak :: ((a -> (b -> m r) -> m r) -> (a -> m r) -> m r) -> m r
withBreak f = f (\x _ -> pure x) pure

. 첫 번째 프로그램에서 f에 대한 대응은 \break -> ... 입니다. 마지막으로 break는

break :: a -> (b -> m r) -> m r
break = \x _ -> pure x

.

다시 연속 모나드로 돌아가 보겠습니다. ContT 모나드의 구현은 다음과 같습니다.

instance Monad (ContT r m) where
  return x = ContT ($ x)
  m >>= k  = ContT $ \c -> runContT m (\x -> runContT (k x) c)

>>= 의 동형에 따라 ContT 를 다시 작성해 봅시다.

(>>=) :: ((a -> m r) -> m r) -> (a -> ((b -> m r) -> m r)) -> (b -> m r) -> m r
m >>= k = \c -> m (\x -> (k x) c)

다시 말하지만, 유형은 더 복잡하지만 구현은 더 읽기 쉽습니다. 구현을 보면 k 평가한 다음 해당 값을 사용하여 m 평가하는 것을 볼 수 있습니다.

이제 준비가 되었으므로 다음 표현식을 고려하여 break 의 동작을 살펴보겠습니다.

actionA >> break () >> actionB

먼저 왼쪽에 있는 >>를 확장합니다.

(\c -> actionA (\_ -> break () c)) >> actionB

다음으로 확장합니다break.

(\c -> actionA (\_ -> pure ()) >> actionB

이때 후속 계산c이 사라진 것을 확인할 수 있습니다.

마지막 남은 부분을 확장합니다>>.

\c -> actionA (\_ -> pure ())

actionB가 멋지게 사라졌습니다.

마지막으로 첫 번째 프로그램으로 돌아가 보겠습니다.

withBreak $ \break ->
  forM_ [1..] $ \i -> do
    liftIO . putStrLn $ "Loop: " ++ show i
    when (i == 5) $ break ()

우리가 이미 보았듯이 i가 5에 도달하고 break가 평가되면 뒤따르는 무한 계산은 버려집니다.