Skip to content

Instantly share code, notes, and snippets.

@foriequal0

foriequal0/Continuation Monad.md

Created January 23, 2017 21:21
Show Gist options
  • Save foriequal0/30e1e5d5bf34b23a267a4a8173cb3bd6 to your computer and use it in GitHub Desktop.
Save foriequal0/30e1e5d5bf34b23a267a4a8173cb3bd6 to your computer and use it in GitHub Desktop.
Download ZIP
Continuation Monad
Raw
Continuation Monad.md

Continuation Monad

이성찬, 2017

Continuation

Continuation 은 제어 흐름 을 구체화 해 first-class citizen으로 다룰 수 있게 한 추상 표현. Exception, Generator, Coroutine 등을 인코딩하는 데 유용한 도구. - wiki/Continuation

Continuation Passing Style

연산의 결과를 호출자에게 직접 되돌려주지 않고, 호출자가 인자로 넘겨준, continuation function 이라 불리는 함수에 결과값을 인자로 호출하는 스타일.

Continuation 이 first-class citizen이 아니지만, tail call optimization을 가진 함수형 언어에서 해당 연산들을 구현할 수 있다.

우리는 이를 통해 제어 흐름을 자유롭게 제어 할 수 있다.

직접 리턴

설명이 필요 없는 간단한 예시

add :: Int -> Int -> Int
add x y = x + y

square x = x * x

pythagoras :: Int -> Int -> Int
pythagoras x y = add (square x) (square x)

thirteen = pythagoras 2 3

CPS

Continuation 함수를 매개변수로 받아, 연산의 결과를 인자로 호출.

# 단순한 CPS
add_cps :: Int
        -> Int
        -> (Int -> r) -- 주입 될 Cont. func.
        -> r
add_cps x y = \c -> c $ x + y

square_cps x = \c -> c $ x * x

pythagoras_cps :: Int -> Int -> ((Int -> r) -> r)
pythagoras_cps x y = \c -> 
  square_cps x 
  $ \xsq -> square_cps y 
  $ \ysq -> add_cps xsq ysq c
  
thirteen_cps = pythagoras_cps 2 3 $ id

괜히 간단하고 당연한 연산을 ($)만 늘려서 적어놓은 것 같다.

  • 런타임이 갖고 있던 제어 흐름을 first-class 로 얻어오려다보니 그렇게 된 것.

  • 이렇게까지 해서 얻는 그 힘이란게 무엇인가.
  • 소개하기 전에, CPS가 하스켈에 왔으니 빼놓을 수 없는 ...

data Cont' r a = { runCont' :: (a -> r) -> r }
-- Functor, Applicative 생략
instance Monad (Cont' r) where
  pure x = Cont' $ ($ x)
  m >>= f = Cont' $ \c1 -> 
      runCont' m
      $ \x -> runCont' (f x) c1
  • f가 m에 continuation으로 주입된다는 사실을 주목.
  • 그래서 m은 continuation을 통해 선형의 제어흐름을 벗어날 수 있는 주도권을 갖는다.

do-sugar

addM :: Int -> Int -> Cont' r Int
addM x y = pure $ x + y

squareM x = pure $ x * x

pythagorasM :: Int -> Int -> Cont' Int r
pythagorasM x y = do
  xsq <- squareM x
  ysq <- squareM y
  addM xsq ysq

thirteenM = runCont' (pytagorasM 2 3) id
  • monad를 구현하고, do-sugar를 이용해 한층 간결해졌다.
  • CPS가 제어흐름을의 주도권을 갖는 강력한 예시를 보여줄 때가 되었다.

예시: Fizzbuzz

fizzbuzz :: Cont' [String] String
fizzbuzz = do
  i <- (Cont' $ \fzbz -> catMaybes $ map fzbz [1..15])
  num <- pure $ Just (show i)
  fizz <- pure $ justWhen (i `mod` 3 == 0) "Fizz"
  buzz <- pure $ justWhen (i `mod` 5 == 0) "Buzz"
  pure $ fizz <> buzz <|> num
 where justWhen b v = if b then Just v else Nothing

첫번째줄의 Cont'는 뒤따라올 statements들을 fzbz 란 이름의 continuation으로 넘겨받았지만, 앞선 pythagoras 예제처럼 continuation으로 tail call을 하지 않고, 몇번이고 호출하고 싶은 만큼 호출했다.

fizzbuzz (cont'd)

앞선 fizzbuzz를 continuation 주입이 일어남을 명시적으로 보여줌

fizzbuzz :: Cont' [String] String
fizzbuzz = do
  (CPS $ \fzbz -> catMaybes $ map fzbz [1..15])
  >>= \i -> do
    num <- return $ Just (show i)
    fizz <- return $ justWhen (i `mod` 3 == 0) "Fizz"
    buzz <- return $ justWhen (i `mod` 5 == 0) "Buzz"
    return $ fizz <> buzz <|> num)
 where justWhen b v = if b then Just v else Nothing

callCC

callCC :: ((a -> Cont' r b) -> Cont' r a) -> Cont' r a
callCC f = Cont' $ \c2 -> 
  let exit y = Cont' $ const (c2 y)
  in runCont' (f exit) c2

whatsYourName :: String -> String
whatsYourName name =
  (`runCont'` id) $ do
    res <- callCC $ \exit -> do            -- (1)
      when (null name) (exit "empty name") -- (2)
      return $ "Welcome, " ++ name ++ "!"  -- (3)
    return res                             -- (4)

(2) 에서 (exit "empty name") 이 평가되면 (3) 은 반영되지 않고, callCC 구문은 CPS $ \_ -> "empty name"으로 평가되어, "empty name"을 리턴한다.

  • callCC는 (4)를 exit이란 이름의 continuation으로 받아, (2)에서 그 제어 흐름을 (4)로 옮길 수 있다고 해석하는것이 자연스럽다.

Callbacks

Monad 위에 ContT를 얹으면, ContT를 깔린 monad에 대한 callback 처럼 사용할 수 있고, 체이닝 할 수 있습니다.

data Hole = Swing Int | Attack Target

unitAttack :: Target -> ContT () IO Hole
unitAttack target = ContT $ \callback -> do
    callback (Swing 60); callback (Attack target)
    
handler :: Hole -> ContT () IO String
handler (Swing  n) = ContT $ \log -> do ... log $ "Swing " ++ show n
handler (Attack t) = ContT $ \log -> do ... log $ "Attack " ++ show t
  
stdoutLogger :: String -> ContT () IO ()
stdoutLogger text = ContT $ \_ -> putStrLn text
silentLogger text = ContT $ \_ -> pure ()

main = 
  runContT (unitAttack target
    >>= handler 
    >>= silentLogger) return

The Mother of All Monads

다음처럼 하면 ContT로 모든 모나드를 구현할 수 있다고 한다.

i x = Cont' $ \k -> x >>= k

listM = (`runCont` return) $ do
  a <- i [1, 2]
  b <- i [10, 20]
  return $ a + b

maybeM = (`runCont` return) $ do
  a <- i $ Just "Fizz"
  b <- i $ Just "Buzz"
  return $ a <> b

The Mother of All Monads (cont'd)

i :: Monad m => m a
i x = Cont' $ \k -> x >>= k 
  -- free ride on Monad m

(i x) >>= f
  -- suppose x :: m a, (>>=) in Monad (Cont' (m a))
== Cont' $ \k' -> runCont (i x)
                  $ \y -> runCont (f y) k'
== Cont' $ \k' -> runCont (Cont' $ \k -> x >>= k) 
                  $ \y -> runCont (f y) k'
== Cont' $ \k' -> x >>= \y -> runCont (f y) k'
                    -- (>>=) in Monad m

i x 는 continuation k를 tail call 해서 Cont' do-block에 의해 주어진 순서 그대로, 제어 흐름을 변경하지 않고 (>>=) 했다.

Chinese-room VM

  • Toy VM 만드는 중.
  • Esoteric programming language 비슷.
    • ex: 아희, Brainfuck, etc.
  • John Searle의 "중국어 방 논증"
  • 우리는 튜링 테스트 피험자가 된다.
  • ex: 명령어 Add에 대한 콜백으로
    • auto: do {a <- pop; b <- pop; push $ a+b}
    • manual: do {dump stack; hand_over_to_user; }
  • release는 manual 로 나가지만, 테스트는 auto 여야하니 ContT를 callback처럼 사용한다.

못한 얘기

ContT로 Generator, Coroutine 구현하기. -> Iteratee, Pipe로 이어지나요?

참고자료

참고자료 (cont'd)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment