Arrow 쓰는 방법 (스케치 중)

Sun Sep 24 03:19:40 AM KST 2023 아직 이해하지 못한 부분이 있어 계속 정리 중인 글입니다. 대부분 아직 상상입니다. 모나드보다 표현력이 좋다하지만, 모나드로 표현할 수 있는 건 굳이 Arrow로 표현하진 않는 것 같습니다. 어떤 문제, 대상을 보면 Arrow를 떠올려야 할지 찾고 있습니다.

Arrow가 무엇인지는 Arrow는 모나드의 일반화에 정리해 두었습니다. 여기선 언제 Arrow를 쓸 생각을 하면 되는지 찾는 게 목표입니다.

생각 스트레칭

a -> m b를 받는 함수와 m a를 받는 함수 중 어느 게 더 표현력이 좋을까요? 혹은 더 추상적일까요?
말을 바꾸면, 함수와 타입 중 어느 게 더 표현력이 좋을까요? 결론부터 말하면, 타입이 더 표현력이 좋습니다. 여기서 “표현력이 좋다”는, 함수가 하는 일은 타입으로도 할 수 있다는 말입니다. 타입 안에다 함수를 넣어 놓을 수도 있고, 타입을 타입 클래스의 인스턴스로 만들고, 메소드로 정의해 둔 함수가 돌게 할 수도 있습니다. 여기다, 함수와 연계되는 함수들을 지정할 수도 있고, 타입 체크를 위한 동작도 정해 줄 수 있습니다. 타입으로 만들면 많은 일이 일어납니다.

파서를 Arrow로 만들어 보자

Haskell/Understanding arrows - wikibooks # Using arrows
Arrow 설명부터 활용까지 잘 나와 있는 위키북스에 있는 글인데요, 여기서는 활용 부분만 보면서, 노트한 글입니다. 아래 있는 코드들은 전부 이 페이지에서 발췌했습니다.

느리고 특별할 것 없는, 가장 기본 파서

newtype Parser s a = Parser { runParser :: [s] -> Maybe (a, [s]) }
--                                         입력스트림   (파싱결과, 남은 스트림)

char :: Char -> Parser Char Char
char c = Parser $ \input -> case input of
    [] -> Nothing
    x : xs -> if x == c then Just (c, xs) else Nothing

글자 하나를 파싱하는 파서입니다.

GHCi> runParser (char 'H') "Hello"
Just ('H',"ello")
GHCi> runParser (char 'G') "Hello"
Nothing

위 구현만 있으면, 현재까지는 한 번 실행하는 모양만 가능한 인터페이스입니다. 이제 함수형에서 늘 그렇듯 합성이 가능하도록, 입력 스트림, 파싱 결과를 같이 받아서 잃어버리지 않고 다음으로 넘겨 주는 코드를 작성해야 합니다. 이 때 Monad나, Applicatives 인터페이스를 사용하면, 이들의 인터페이스 설계를 그대로 따르면 됩니다. 여기선 Applicatives를 보면,

instance Applicative (Parser s) where
  pure a = Parser (\s -> Just (a, s))
  (Parser p1) <*> (Parser p2) = Parser (\s -> do
    (f, s1) <- p1 s
    (a,s2) <- p2 s1
    Just (f a, s2))

isHel :: Parser Char ()
isHel = char 'H' *> char 'e' *> char 'l' *> pure ()

한 글자가 아니라, 단어를 파싱하려면, 위와 같이 한 글자 파서를 이어 붙이는combine 작업을 하도록 아래같은 함수를 생각해 볼 수 있습니다.

string :: String -> Parser Char String
string = traverse char

이제 Alternative의 <|>를 쓰면 다음 파서가 가능합니다.

solfege :: Parser Char String
solfege = string "Do" <|> string "Re" <|> string "Mi"

잘 생각해 보면, 여기엔 퍼포먼스 문제가 있습니다. "Fa" 문자열을 받아 파서를 돌리면, 빠르게 Nothing 결과를 받으면 좋은데, string "Do", string "Re", string "Mi"를 모두 돌려 보기 전에는 결과를 받을 수 없습니다. <|>는 Nothing을 만난다고 바로 끝나지 않습니다. 나머지 Alternative들도 확인해야만 합니다. 만일, 하나 하나가 복잡한 파서로 입력 문자열을 많이 먹었다consume가 실패하면 다시 먹기 전으로 돌리는 작업이라면 퍼포먼스는 더 떨어질 겁니다. 다음 파서가 읽을 수도 있는 입력 문자열은 모두 메모리에 유지도 해야 합니다. 파서가 복잡해지면 유의미한 공간 누수space leak가 생길 수 있습니다.

스마트 파서

Arrow의 쓰임새를 보여주려고, 파서 예를 드는데, 일단 파서의 동작을 이해해야 왜 Arrow가 적합한지 알 수 있을 것 같아 좀 자세히 뜯어 보았습니다. Swierstra와 Duponcheel은 다음 방법을 제안 했습니다. "Do", "Re", "Mi"를 파싱을 위해, 각각 첫 글자 D, R, M 파서를 먼저 돌립니다. 텍스트에선 첫 글자 파서를 추가한 파서를 스마트 파서라 부르고 있습니다.

스마트 파서는 D를 파싱했으면, 이어서 o를 파싱 시도할 거란 걸 알고 있고, R을 파싱했으면, 이어서 e를 파싱할 거란 걸 알고 있습니다. (텍스트에서 could look ahead가 이 뜻이 아닐까요?) 가베지 콜렉팅도 바로 할 수 있습니다. 예를 들어, D 파싱에 성공했다면, 더 이상 다른 파서가 D를 돌아볼 필요가 없기 때문에 바로 메모리에서 날려도 됩니다. 스마트 파서가 아니었다면, 다른 파서가 모두 돌 때까지 D를 날릴 수 없습니다.

• 첫 글자 D, R, M 중 하나가 있는지 먼저 파싱하고
• 이들 중 하나가 있다면, 해당 글자에 따라 다음 파서를 고른다.

제안한 방법은, 각 파서들이 첫글자파서 + 나머지파서를 가지고 있게 만듭니다. 텍스트에서는 나오지 않지만, 헛갈리지 않게 둘을 합친 파서를 전체파서라고 부르겠습니다. 전체파서 둘을 받아 묶어 놓으려면, 첫글자파서끼리 묶고, 나머지파서끼리 묶어 놓아야 합니다. 그래야 첫글자파서만 먼저 돌리는게 가능할테니까요.

전체파서 = 첫글자파서 + 나머지파서

이렇게 생긴 것 세 개를 합성한다면

(첫글자파서1 | 첫글자파서2 | 첫글자파서3) 를 먼저 돌리고,
다음 돌리는 나머지파서는, 모두 돌릴 필요없이 이전 결과에 따라 돌릴 파서를 선택해야 합니다. 최종 합성한 전체파서 모양을 추측해보면,

전체파서 =
  첫글자파서1 | 첫글자파서2 | 첫글자파서3      <--- 정적?
  위 작업이 실패면 Nothing, 아니면             <--- 동적?
    첫글자파서1이 성공이면 
      나머자파서1이 실패면 Nothing 아니면 결과
    첫글자파서2가 성공이면 
      나머자파서2이 실패면 Nothing 아니면 결과
    첫글자파서3이 성공이면 
      나머자파서3이 실패면 Nothing 아니면 결과

텍스트에선 이런 이유로 첫글자파서를 정적 파서, 나머지파서를 동적 파서라고 이름 붙인 것 같습니다.

Q. 스마트 파서는 모나드로 구현한 것과 비슷해 보이지만, export static information을 한다는 큰 차이가 있다고 합니다. 정적인 정보가 뭘까요? 그럼 모나드는 동적이란 얘기일텐데요.

모나드 (혹은 체인) :: a -> m b
solfege            :: Parser Char String

m을 얻으려면 동적으로 a를 넣어 봐야 알게 되겠지만,
solfege는 Parser타입이 가진 정보를 (a를 넣어 실행하는 것 같은 동적 작업 없이) 바로 볼 수 있습니다. 타입과 함수의 차이라고 봐도 되겠습니다. static information이란 이 걸 말하는 걸까요?

정적인 정보를 가지고 있게 하려면, 모나드로는 안되고 Arrow 인터페이스가 필요하다고 합니다.

@todo @재경님 설명 정리

텍스트에선 파서(전체파서)를 정적 파서(첫글자파서), 동적 파서(나머지파서)로 부릅니다. 정적 파서는 빠르게 현재 입력값이 파싱 시도할만 한가만 알려주고, 동적 파서가 상대적으로 느리게 실제 파싱 작업을 합니다.

import Control.Arrow
import qualified Control.Category as Cat
import Data.List (union)

data Parser s a b = P (StaticParser s) (DynamicParser s a b)
data StaticParser s = SP Bool [s] -- SP 빈문자열여부 [첫글자]
newtype DynamicParser s a b = DP ((a, [s]) -> (b, [s]))

SP는 왜 빈문자열 여부를 가리는 인자가 왜 필요한지, DP의 a, b 인자는 뭘 의미하는지 눈에 안들어와 더 뜯어 봤습니다.

정적 파서

정적 파서는 빈 문자열을 입력으로 받을 수 있는지 알려 주는 플래그와, 시작 글자 목록 조합으로 구성됩니다.

-- sp는 static parser, A는 한 글자를 뜻하는 것 같다. 
spCharA :: Char -> StaticParser Char
spCharA c = SP False [c]
--             ^^^^^ ^^^
                 |   첫 글자 목록
                 |
               빈 문자열 못받음

위 정적 파서 spCharA는 첫 글자 c를 위한 파서이며, 빈 문자열은 받지 못합니다.

Q. 빈 문자열을 받을 수 있는지 여부를 왜 갖고 있어야 할까요?
빈 문자열은 보통 에지 케이스로 쓰이는 경우가 많습니다. 문자열을 받아 조금씩 먹으며 재귀를 돌다가 빈 문자열이 되면 멈춘다든지 할 때 쓰입니다. 뒤에 나오는 runParser의 동작을 보면, 빈 문자열 플래그가 True이고, 빈 문자열 []이 들어오면, 바로 동적 파서에 (초기값, [])을 넘겨 실행시킵니다.

추측1) 동적 파서가 빈 문자열이 들어와서 오류가 났다는 결과를 내뱉을 수 있다면, 빈 문자열이 의미 있을 수도 있겠습니다.

추측2) 만일 동적 파서가 빈 문자열 처리를 할 수 없다면, 이 옵션을 False로 만들어 정적 파서에서 걸러낼 수 있습니다. 아래에 나오는 dpCharA 같은 동적 파서는 _:xs로 패턴 매칭하므로, 빈 입력 문자열은 동적 파서까지는 오지 말아야 합니다. 아래 Arrow 인스턴스를 만들 대 arr이 옵션을 True로 쓰고 있습니다.
arr f = P (SP True []) (DP (\(b,s) -> (f b, s)))
여기 있는 정적 파서는, 정적 파서들 합성에서 id 같이 어떤 영향도 주지 않아야 하고 (하나라도 False면 전부 False가 되니, 영향을 미치지 않기 위해 True값을 가지고, 당연히 첫 글자 목록도 비어있어야 합니다.)
동적 파서도, 동적 파서들 합성에서 id 같은 역할을 해야 합니다.
아직 확실한 이유는 모릅니다. 아시는 분은 댓글 부탁 드립니다.

동적 파서

동적 파서는 (a, [s]) -> (b, [s]) 모양의 함수입니다. 금방 눈에 들어오진 않지만, 두 개의 파서를 순서대로 늘어 놓은 걸로 읽어도 된다고 합니다. (이전 파서의 결과, 입력 문자열)을 넣어 주면 (b, [s]) 2튜플을 반환하는 함수입니다. 예를 들어, 현재까지 파싱된 글자수 Int를 결과로 가지는 (Int, String) -> (Int, String) 같은 걸 생각해 볼 수 있습니다. cake란 문자열을 파싱하는 걸 보면,

첫 번째 (Int, String) -> (Int, String)
          0    cake        1    ake
                 두 번째 (Int, String) -> (Int, String)
                           1    ake         2     ke
                                  세 번째 (Int, String) -> (Int, String)
                                            2     ke         3     e

동적 파서는 이전 파서의 결과를 받아 뭔 짓(여기서는 +1)을 하고, 입력 문자열 하나를 먹는 두 가지 작업을 합니다. 작업을 타입으로 표현하면 (a -> b) 작업과 ([s] -> [s]) 작업, 두 개의 작업을 합니다. 두 개를 병행하는 걸 하나의 함수로 표현하려면 2튜플로 표현할 수 있습니다.

DP ((a, [s]) -> (b, [s]))

여러 글자가 아닌, 딱 한 글자를 파싱을 위한 동적 파서를 생각해 봅시다.

첫 번째 해야 할 작업은, 이전 파서의 결과를 무시하고, 입력 문자열에서 첫 글자를 먹은 걸로 만들고, 첫 글자를 반환해야 합니다.

dpCharA :: Char -> DynamicParser Char a Char
dpCharA c = DP ( \(_, _:xs) -> (c,xs) )
                   |   |
                   |   +남은 문자열의 첫 글자 떼어내서 버리기
                   |
                   + 이전 결과 무시  

처음 텍스트를 봤을 때, 이 게 무슨 말인가 했습니다. 왜 이전 작업 결과는 무시하고, x == c 같은 작업은 왜 안 보일까요? 지금은 Do같이 여러 글자를 파싱하는 게 아니라, 오직 한 글자를 위한 파서에서 쓸 동적 파서입니다. 한 글자를 파싱하는 정적+동적 전체파서를 다음과 같이 정의할 수 있습니다.

charA :: Char -> Parser Char a Char
charA c = P (spCharA c) (dpCharA c)
            ^^^^^^^^^^^ ^^^^^^^^^^^
                  |        |
                  |        + 실제 파싱 역할
                  |
                  +한 글자를 보고 계속 파싱할지 말지를 결정하는 역할

한 글자기 때문에 정적 파서가 이미 필요한 글자 매칭 여부는 들여다 봤습니다. 이게 성공해서 동적 파서로 넘어가면, 항상 그렇다는 게 아니라, 딱 이 경우에는 동적 파서가 하는 일이 없습니다. 그냥 정적 파서가 매칭 성공한 한 글자와, 앞 글자 하나를 떼어내고 나머지 문자열을 반환하면 됩니다.

파서를 실행하려면 정적 파서를 먼저 돌리고, 통과하면, 입력 문자열에 동적 파서를 적용하는 작업이 필요합니다.

runParser :: Eq s => Parser s a b -> a -> [s] -> Maybe (b, [s])
-- 먹을 게 없는 빈 문자열이 들어 왔을 때
runParser (P (SP emp _) (DP p))  a  [] 
  | emp = Just (p (a, [])) -- emp는 불린값, 빈 문자열을 허용한다면, 
                           -- (a, [])로 동적 파서를 부른다. 
  | otherwise = Nothing
-- 먹을 문자열이 있을 때
runParser (P (SP _ start) (DP p))  a  input@(x:_) 
  | x `elem` start = Just (p (a, input)) -- 첫 글자들 중 하나라면, 동적 파서를 돌린다.
                                         -- 여기가 x == c 작업을 하는 곳
  | otherwise = Nothing

GHCi> runParser (charA 'D') () "Do"
Just ('D',"o")
GHCi> runParser (charA 'D') () "Re"
Nothing

지금까지는 전체파서가 “한 글자”를 파싱하는 작업이었습니다. runParser¹ 서명을 보면, 전체파서와 초기값 a를 받아 [s] -> Maybe (b, [s]) 함수를 반환합니다. 모나드 액션과 같은 타입입니다.

Arrow로 넘어가기 숨 차네요. 왜 필요한지 보이기 위한 “상황” 자체를 이해하는 것도 쉽지 않습니다.

Arrow 컴비네이터 활용

전체파서에서 동적파서는 2튜플을 넣어 주며 “실행compute”하게 되지만, 정적파서는 별다른 “실행” 없이도 어떻게 생겼는지 볼 수 있습니다. 전체파서 3개를 합성했다면, P (SP (True && False && True) ['a','b','c']) (...동적 파서 합성...) 모양이 되고, 언제든 패턴 매칭만으로 SP를 꺼낼 수 있습니다. 외부 입력 값에 따라 SP 값은 변하지 않지만, DP는 값이 변합니다. 타입과 타입을 연결하는 게 아니라, 함수와 함수를 연결한다면, “정적”인 정보를 둘 데가 없습니다. 함수가 외부 통로를 열어 놨으니 더 융통성이 있을 것처럼 보이지만, 타입이 더 표현력이 좋습니다. 체인에서 정적인 정보가 병행하는 게 보이면 Arrow를 떠올려야 할 때입니다.

instance Eq s => Arrow (Parser s) where

  arr f = P (SP True []) (DP (\(b,s) -> (f b, s)))

arr은 보통의 함수를 Arrow로 바꿔 줍니다. arr 적용해 얻은 Arrow는 파싱할 첫 글자가 없고, 동적 파서에서도 문자열을 먹거나 하지 않습니다. 나중에 runParser를 돌릴 때, 동작할 수 있도록 동적 파서에 f를 끼워 놓기만 합니다. 별다른 작업은 안하고 Arrow 흐름 안에 f를 적용하는 인터페이스 입니다.

  first (P sp (DP p)) = (P sp (DP (\((b,d),s) -> 
    let (c, s') = p (b, s) -- (b,d)에서 앞에 b에만 동적 파서p 적용
    in  ((c, d), s')))) -- b는 c로 바뀌었지만, d는 손대지 않고 그대로 내보낸다.

Category 인스턴스도 만들어야 합니다.

instance Eq s => Cat.Category (Parser s) where
  id = P (SP True []) (DP (\(b,s) -> (b, s)))

이제 복잡한 (.)만 남았습니다. 정적+동적 파서 두 개를 받아 합쳐서 잘 돌아가게 준비를 해야 합니다.

(P (SP empty1 start1) (DP p1)) . (P (SP empty2 start2) (DP p2)) =
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    p (SP (empty1 && empty2) 
          (if not empty1 then start1 else start1 `union` start2))
      (DP (p2.p1)) 
    -- DP 안에 들어있는 (a,[s]) -> (b,[s]) 타입의 함수는 cake 예시처럼 그냥 합성합니다.

정적파서 합성 부분이 좀 어렵습니다.

  empty1 && empty2 -- 하나라도 빈 문자열을 못 받으면, 빈 문자열 못 받는 걸로 

  (if not empty1 then start1 else start1 `union` start2))
  -- 첫 번째 정적 파서가 빈 문자열을 못 받는다면, 첫 번째 정적 파서의 시작 글자 목록을
  -- 그렇지 않으면 정적 파서 두 개가 갖고 있는 시작 글자 목록 모두 합치기

텍스트 진행이 어디로 가는 건지 잘 모르겠습니다. charA는 아래 같이 조합해서 쓸 수 없습니다.

GHCi> runParser (charA 'D' >>> charA 'o') () "Do"
Nothing

charA가 가진 동적 파서가 하는 일을 봐서는, 이렇게 합성하면 안될 게 뻔히 보입니다. 앞의 한 글자 파싱 예시가 어떻게 다음으로 연결되는지 아직 모르겠습니다.

Sun Sep 24 03:07:26 AM KST 2023 작성 중…

모나딕으로 조합한 파서와 차이

첫 글자 파서를 두는 건 모나드로 표현 못한다고 하는데, 왜 그럴까요? “Do”를 파싱 중이면,

Q. 왜 첫 글자 파서를 운용할 때는 static infomation이 필요할까?
추측 A. 뒷 파서를 compute하지 않아도, 첫 글자 파서가 뭔지는 알 수 있기 때문입니다.

Arrow 인터페이스는 두 개의 파서(정적, 동적)를 transparently compose and manipulate할 수 있게 해줍니다. Sun Sep 24 11:54:42 AM KST 2023 작성 중 …

Arrow도 수학에서 온 걸까?

Freyd-categories

※ 프로그래밍과 수학은 표현 방식이 조금 다를 뿐, 한 쪽에서 구조를 위한 패턴, 개념이 보이면 다른 쪽에도 존재하는 것 같다.

정리

그냥 a -> b, b -> c 함수를 정의하고, (.)를 이용해서 a --...--> c를 만든 것과, Arrow 인터페이스를 이용하는 것의 차이는 뭘까요?

              (->) a    b    .                 (->) b    c
              (->) a (m b)  >=>                (->) b (m c)
ArrowInstance (->) a    b   >>>  ArrowInstnace (->) b    c

함수를 합성할 때마다, 반복되는 어떤 작업 (Effect를 잃어버리지 않기 위한 작업)이 있다면, 모나드 인터페이스가 딱이었습니다. a -> b의 합성과 m (m a) -> m a 작업을 “병행”해 주는 작업이 필요하면 모나드를 떠올리면 됐습니다.
추측) a -> b든 a -> m b든, 합성과 정적인 정보 유통²을 체인에서 병행해야 한다면 Arrow를 떠올리면 됩니다.

Sun Sep 24 03:20:50 AM KST 2023 작성 중…

@todo 아래는 아직 생각 정리가 안된 끄적임입니다.

타입과 함수의 차이, 생성generate 방법이 정해져 있는 타입과, 외부 정보에 의존하는 함수의 차이

m1 a -> (a -> m2 b) -> m3 b

이미 생성 방법이 정해진 m1과 a
외부 정보 a에 의존해서 생성 방법을 결정될 m2, 그리고 a에 의존해서 결정될 b

바인드 자체는 m1이 어떤 생성 방법을 쓸 것이라 결정된 상태로 예정하고 동작한다는 뜻이 아니라, 바인드로 들어 올 때부터 이미 정해진 상태로 들어온다는 뜻이다.

외부 정보를 받을 수 있는 인터페이스가 있는 것보다, 왜 타입이 표현력이 더 좋다고 할까?
타입은 당장 동작해야 할 코드가 아니라, 나중에 어떤 동작을 하겠다는 표기이다. 함수는 표기와 동시에 동작하는 것이고, 타입은 표기해 두고, 동작은 나중으로 미룰 수도 있게 해주니 더 표현력이 좋다.