Arrow 예시 - Circuit

Posted on September 29, 2023

Sat Sep 30 12:37:49 AM KST 2023 작성 중… 아직 완전히 이해하지 못하고, 일부는 추측하며 정리하고 있습니다.

Haskell/Arrow tutorial - wikibooks
Arrow 실 사용 예시를, 자세한 설명과 함께 볼 수 있는 글 입니다. 처음엔 언제 Arrow를 사용하면 좋을 지 알기 위해 봤는데, 재귀 패턴, 모양을 더 공부하게 만든 예시입니다. Arrow가 어떻게 쓰이는 지만 보기엔 적당한 글이 아닐 수도 있습니다. 우아한 Arrow로 넘어가기 전에 일단 Circuit에서 막히니까요. 여기 글은 위 링크에 있는 튜토리얼을 그대로 가져와 읽으며, 메모를 추가한 정도의 글입니다. 아래에 나오는 코드는 모두 위 링크에서 발췌했습니다.

어느 정도 쓰고 돌아보니, 길게도 썼습니다. 오류가 있을지도 모르는 긴 글을 누가 읽을까 싶은데요. 위 텍스트로 Arrow를 공부하며 벽에 부딪히는 분들을 위한 아이디어가 몇 개 있긴 합니다. 정답을 알려주는 텍스트가 아니라, 같이 공부하는 옆 친구의 노트입니다.

※ 추가적인 메모없이 깨끗한 번역만 보시려면, codeonwort님의 애로우 튜토리얼 - WikibooksHaskell 번역이 공개되어 있습니다.

생각 스트레칭

반복을 표현하는 방법

A.
(+10)을 for, 재귀 등으로 10번 반복해

B.
data AddTen a = AddTen (AddTen a)

즉 AddTen (AddTen (AddTen ...)) 무한이 가능한 재귀 타입을 만든다.
패턴 매칭으로 AddTen을 벗겨 낼 때마다 (+10)을 하도록 정의한다.
패턴 매칭을 10번 한다.

(+10)을 한 번 더하고 싶으면, A 경우엔 그냥 (+10)을 한 번 더하면 되고,
B 경우엔 한 번 패턴 매칭하면 됩니다.

그런데, AddTen타입은 리스트 정의처럼 종료([] 혹은 Empty)를 표시하는 엣지 케이스가 없습니다. AddTen은 AddTen값이 있어야 되는데, 처음 AddTen값은 어떻게 정의할까요? 그리고 정의가 되었다 해도, 무한하게 가버리는 걸 실용에서 어찌 써먹을까요?

A보다 B가 훨씬 더 복잡하고, 머리를 괴롭히는데 B로 하면 A로 하는 것 보다 어떤 장점이 있을까요?

Circuit

newtype Circuit a b = Circuit {unCircuit :: a -> (Circuit a b, b)}
                                                  ^^^^^^^^^^^
                                                  continuation

Circuit안에 또 Circuit

순환하는 타입 읽기가 불편하지 않나요? 저는 아직도 편하지 않습니다.

Circuit 타입을 생성하려면 생성자 Circuit에 (\a -> ???) 같은 함수를 넣어야 하는데, ??? 부분에는 뭐가 들어가면 될까요? Circuit 타입을 넣어 줘야 하는데, 그러려면 안 쪽에 또 Circuit 타입이 있고, 그냥 대체하면서 따라가면 무한으로 가버립니다. 타입에서는 이렇게 써 준다고 무한 재귀하는 모양이 아닙니다. 안에 있는 Circuit타입 값이, 꼭 현재 정의하고 있는 Circuit과 같은 값일 필요는 없으니, 재귀가 아닌 경우도 있을 수 있습니다. 물론, 값을 만들 때 재귀하는 모양의 값을 만들 순 있습니다. 하지만, 혼자서 무한히 도는 일은 일어나지 않습니다.

data List a = a : List a | []

[], 1:[], 1:2:[] … 등이 모두 List 타입의 값이 될 수 있다는 얘기지, 재귀 함수를 읽듯 List가 무한히 호출되지는 않습니다. 그런데, List의 경우는 에지 케이스, 즉 []라는 표현이 있어, 더 이상 이어지는 값이 없을 경우 []으로 마감하면 됩니다. 하지만 Circuit의 경우는 Sum타입으로 에지 케이스를 가지고 있지 않습니다. Circuit은 종료를 표현할 수 없으니 무한 반복으로 갈 것만 같습니다.

하스켈은 Lazy합니다. 타입 생성자로 쌓여 있는 건 패턴 매칭으로 벗겨내거나, unCircuit같은 함수를 실행하기 전에는 안에 들어있는 값을 볼 수 없습니다. Circuit 안에 들어 있는 Circuit은 또 풀려고 하지 말고, 그냥 안을 보지 않은 채로 Circuit으로만 봐야 합니다. 안을 들여다 볼 필요가 있기 전 까지, 안은 안보면 됩니다.

여기까진 그런대로 쫓아 올만한데, 그럼 아무 Circuit타입 값이 없는 제일 처음에 Circuit 타입의 값을 만들려면(값 생성자로 생성하려면) 어떻게 할까요?

let cir = Circuit (\a -> (???,b))

cir에 넣어 줄, 알고 있는 Circuit 타입 값이 없습니다?!
아닙니다. 적어도 하나가 있습니다. 바로 정의되고 있는 자기 자신입니다.
(아래 쪽에 보면, id도 있긴 합니다. 다른 Circuit값을 못 쓰진 않지만, 텍스트에선 “처음 생성”에는 모두 순환하는 예시만 보입니다. )

let cir =

이라고만 해도, 쓸 수 있는 cir이 하나 생겼습니다. ??? 자리엔 Circuit을 넣어줘야 하니, cir을 넣어줘도 됩니다. Lazy하니 cir이 무슨 값인지는 필요할 때, 또 보면 됩니다. ※ 컴파일러가 바인딩하는 과정(WHNF 개념 포함)을 보면, 이런 재귀적인 표현들이 “약간” 더 편해지긴 합니다.

let cir = Circuit (\a -> (cir, b))

타입 정의 자체가 순환 정의는 아니지만, 위와 같이 값을 선언하면 순환하는 값을 가지게 됩니다.
※ cir값을 위와 같이 만들어 뒀다면, let cir2 = Circuit (\a -> (cir, b))로 cir2 정의할 때 cir을 가져다 쓸 수 있습니다. 텍스트를 보면, 시작부터 다른 Circuit을 가지게 하진 않고, 컴비네이션을 하는 동안, 두 Circuit을 합친다든지 하며 다른 Circuit이 들어갑니다.

Category 클래스의 인스턴스

합성을 추상화 시킨 인터페이스는 Category 클래스에 있습니다.

class Category cat where
  id :: cat a a
  (.) :: cat b c -> cat a b -> cat a c

(.)

instance Cat.Category Circuit where
  (.) = dot
    where
      (Circuit cir2) `dot` (Circuit cir1) = Circuit $ \a ->
        let (cir1', b) = cir1 a
            (cir2', c) = cir2 b
        in  (cir2' `dot` cir1', c)

Circuit 두 개를 모두 거쳐 결과값c를 만들고, 또 언제든 두 개를 모두 거칠 수 있도록 dot으로 합성한 걸 가지고 있습니다. dot을 구현하는데, 안에 또 dot이 나옵니다. Circuit안에 Circuit이 또 들어 있으니, 당연히 또 나오겠거니 예측할 수 있긴 합니다.

Circuit은 a를 받고, 결과값을 갖고 있는 2튜플을 돌려주는 함수입니다. Circuit을 잠시 가리고 보면,

a -> (           , b)

텍스트에선 b를 내부 상태값internal state이라 표현하고 있습니다. a를 받아 b상태가 되고, b를 받아 c상태가 되게 하고, 여전히 Circuit안에 들어 있게 하면 2튜플의 두 번째 자리에 상태를 유지할 수 있습니다. 저는 정보량으로 추상화 시켜서 보곤 합니다. a -> b와 달리 a -> (??, b)는 분명히 추가 정보를 가지고 있습니다. 이 함수 자체만으로는 추가 정보가 어떤 역할을 하지 못하지만, ??을 꺼내가는 다른 절차가 끼어들어 다른 역할을 할 수 있을 거라 추측해 볼 수 있습니다.

무한히 반복될 것만 같아 불편하다.

마지막 (cir2' dot cir1') 해석이 어렵습니다.

실제 코드가 아니라 눈에 잘 보이게, c1과 c2의 합성을 c1-c2로 쓰고, 합성 결과에 있는 ...(c2' dot c1',...)를 c1'-c2'라고 쓰겠습니다. 한 번돌고나서 새로 만들어지는 Circuit은 프라임'을 붙이겠습니다.

이 무한히 쌓여갈 것만 같은 dot의 반복은 어떻게 해석할까요?

in을 빼고 let부분만 보면, 첫 번째 Circuit를 돌리고 나온 결과를, 두 번째 Circuit에 입력으로 넣어주고 있습니다. 텍스트에서 보면 c1이 안에 가지고 있는 c1'은 둘이 같거나, c1과 인자를 달리해서 만들어냅니다.(텍스트에선 결과에 의존해서 새 Circuit을 만듭니다.) c1-c2를 돌린 다음에, 또 돌린다면 c1'-c2'을 돌립니다. 그 다음에 돌린다면 c1''-c2''을 돌릴 겁니다. Circuit들은 입출력으로 서로 이어지고 있지만, 다음 돌릴 자신의 “후임” Circuit은 각자 알아서 독립적으로 만들어 냅니다.

만일 5개의 Circuit을 합성했다면, 순서대로 입출력을 넘겨 받으며 c1-c2-c3-c4-c5를 실행하고, 다음 번에도 c1'-c2'-c3'-c4'-c5'를 돌릴거란 뜻으로 Circuit $ \a -> (c1'-c2'-c3'-c4'-c5', 다섯 개 Circuit을 연이어 돈 결과)를 반환합니다. runCircuit이 “리스트에 남은 원소가 있다면”, 준비한 c1'-c2'-c3'-c4'-c5'를 돌리고, 다음 돌릴 Circuit은 c1''-c2''-c3''-c4''-c5''으로 준비 할 겁니다. 만일, runCircuit하기 전에 c6을 합성한다면 (c1-c2-c3-c4-c5-c6, 여섯 개 Circuit을 연이어 돈 결과)를 준비합니다.

제 생각을 쓰는 것도 어려우니, 읽는 분들에게 전달이 잘 될리가 없겠습니만, 그래도, 최선을 다해 불편함을 주는 부분을 짚어보면,

전체적으로 불편함을 주는 이유는, 여기선 무한 반복으로 갈 것만 같은 코드 모양이지만, runCircuit이 리스트에 원소가 남아 있는 동안만 반복 시킵니다. 무한 리스트를 정의하고, 필요한 만큼만 take하는 것과 비슷합니다. 하스켈에서 만나는 (실용적인) 무한한 것들은 대부분 필요한 만큼만 꺼내올 줄 아는 파트너가 존재합니다. 언제 멈출 수 있는지, 언제 다음 반복을 시작하는지를 알게 되면 조금 덜 불편합니다.

id

이제 위 (.)을 만나 아무 일도 일어나지 않는 id를 정의합니다.

instance Cat.Category Circuit where
  id = Circuit $ \a -> (Cat.id, a)

Q. Circuit값이 들어갈 자리에 Cat.id가 들어가 있다. cat a a타입이니 컴파일러가 Circuit a a로 추론할 수는 있겠지만, 디폴트 구현이 있거나 하진 않다. 실제 구현은 없는 상태인데, 이래도 되는가?
A. 추측) Cat.id를 Circuit a a로 추론할텐데, 그럼 현재 정의하고 있는 id를 재귀적으로 가지고 오면 됩니다.

(.)구현에 넣어 보겠습니다. 두 번째 인자로 주면

(Circuit cir2) `dot` (Circuit $ \a -> (Cat.id, a)) = Circuit $ \init ->
  let (cir1', b) = (\a -> (Cat.id, a) init)  
  --             = (Cat.id, init)
      (cir2', c) = cir2 b 
  --                    init
  in  (cir2' `dot` Cat.id, c)
  --                       c는 init에 Circuit을 한 번 적용한 것 과 같다.

첫 번째 인자로 주면

(Circuit $ \a -> (Cat.id, a)) `dot` (Circuit cir1) = Circuit $ \init ->
  let (cir1', b) = cir1 init 
      (cir2', c) = (\a -> (Cat.id, a) b)
  --             = (Cat.id, b)
  in  (Cat.id `dot` cir1', c)
  --                       c는 init에 Circuit을 한 번 적용한 것 과 같다.

최종 결과에 여전히 남아 있는 Cat.id가 어찌될까 보기에 불편하긴 합니다. 그래도 정보량에서 다른 건 아닌가 하고요. 나중에 runCircuit으로 돌릴 때를 생각하면
Cat.id dot Circuit cir1과
Circuit cir1 dot Cat.id는
Circuit cir1과 같은 결과값을 가집니다.

Arrow 인스턴스

instance Arrow Circuit where
  arr f = Circuit $ \a -> (arr f, f a)
  first (Circuit cir) = Circuit $ (\(b, d) ->
    let (cir', c) = cir b
    in  (first cir', (c, d)) -- d는 손 대지 않는다.

Arrow는 합성할 함수를 래핑합니다. 여기선 입력 -> ( 다음에 쓸 Circuit , 현재 결과 )를 래핑합니다.

arr은 보통의 하스켈 함수를 Arrow로 리프팅할 때 씁니다.

runCircuit

타입으로 래핑해서 컴비네이션을 하는 것들은, 보통 run~과정을 거쳐 결과값을 얻습니다. 패턴 매칭이나 unCircuit같은 과정을 통해 래핑된 타입의 바깥 세계와 만나게 됩니다.

runCircuit :: Circuit a b -> [a] -> [b]
runCircuit _   []     = []
runCircuit cir (x:xs) =
  let (cir', x') = unCircuit cir x
  in  x' : runCircuit cir' xs

자기 자신을 가지고 있는 Circuit의 경우는 cir'과 cir이 같아져서 이런 패턴의 코드가 필요 없어도 될 것만 같지만, 다른 Circuit을 가지고 있을 수도 있기 때문에, runCircuit은 위와 같이 cir이 돈 후에, cir'이 돌도록 정의해햐 합니다. 무한 Circuit을 끊어주는 작업은 [] 패턴매칭이 담당합니다.

accum

accum :: acc -> (a -> acc -> (b, acc)) -> Circuit a b
accum acc f = Circuit $ \input ->
  let (output, acc') = input `f` acc
  in  (accum acc' f, output)

f input acc 작업을 Circuit으로 한 번 래핑한 덕분에, acc를 유지 및 유통할 수 있습니다.

Q. Circuit이 들어갈 자리에 accum acc' f가 들어갔다?
A. accum의 반환 타입은 Circuit a b입니다.

Q. accum이 무한 반복되는 건가?
A. acc, f만 줘서 accum을 실행하면, 안에 있는 accum이 바로 불리지 않습니다. 안에 있는 accum이 불리려면 추가 절차가 있어야 합니다. Circuit으로 패턴 매칭을 해서 \input -> ... (accum ...) 함수를 꺼내고, input값을 줘서 실행해야 합니다. 그렇게 실행하면 또 다시 Circuit값에 머물러 있고, 또 언젠가 패턴 매칭하면 그 때 다음 동작이 일어날 겁니다. 정리하면, 그냥은 반복되지 않고, 반복 절차로 들어가기 위한 추가 조건이 있는 셈입니다.

accum같은 함수를 읽을 때, 다음처럼 읽으면 도움이 됩니다.
accum은 acc와 f를 받아서 Circuit을 만들어 내는 함수입니다. 현재는 acc, f를 가지고 작업했지만, 다음 작업은 acc', f를 가지고 작업할 겁니다. acc가 acc'으로 바뀌었습니다.

Circuit primitives

accum' :: b -> (a -> b -> b) -> Circuit a b
accum' acc f = accum acc (\a b -> let b' = a `f` b in (b', b'))

accum이 두 번째 인자로 받는 함수는 a -> acc -> (b, acc) 2튜플을 반환하는 함수를 받습니다. accum'는 반환값이 2튜플이 아닌 a -> b -> b 함수를 받아, 결과를 복사해서 2튜플로 만드는 과정을 붙여 accum에게 넘기는 보조 함수입니다.

total :: Num a => Circuit a a
total = accum' 0 (+)

위 작업은 다음과 같습니다.

total = accum 0 (결과값 복사해서 2튜플 만들기 . (+))

이제 위에 그냥 무한 반복이 아니라, 반복하려면 절차가 필요하다고 말했던, 그 절차를 runCircuit으로 아래와 같이 실행할 수 있습니다.

GHCi> runCircuit total [1,0,1,0,0,2]
[1,1,2,2,2,4]

runCircuit은 Circuit타입과 리스트를 넘겨주면, 리스트 맨 앞 원소에 Circuit이 갖고 있는 작업을 진행해서 바꿔 놓고, 이어서 그 다음 원소에는 Circuit이 안에 갖고 있는 후임 Circuit을 적용합니다. 보통, 자기 자신과 같은 Circuit을 적용하거나, 조금 다른 인자로 만들어진 Circuit를 적용합니다.

Q. 자신과 같은 Circuit을 계속 부르는데, 어떻게 값이 누적되고 있을까?
A. accum의 반환 값 안에 있는 ...(accum acc' f, ...)에서 accum은 함수고, acc와 f를 줘야만 Circuit이 됩니다. 현재 Circuit에 있는 함수를 적용해서 acc'을 만들고, 이 값으로 accum을 호출해서 다음 적용할 Circuit을 만듭니다. 완전 동일한 Circuit을 매 번 적용하고 있는 건 아닙니다.

Arrow proc notation

mean1 :: Fractional a => Circuit a a
mean1 = (total &&& (const 1 ^>> total)) >>> arr (uncurry (/))

평균을 내려면 전체 합과 원소 수가 필요합니다.

여기선, 컴비네이터들이 하는 일만 간단히 보면,
(&&&)는 Arrow 두 개를 받아, 각각의 계산computation을 실행하고, 결과를 2튜플로 만듭니다.
(>>>)는 Arrow 두 개를 합성합니다.
(^>>)는 const 1 ^>> total = arr (const 1) >>> total 입니다.

※ 참고 - Arrow는 모나드의 일반화

mean1을 해석해 보면, 나중에 runCircuit으로 리스트가 들어오면,
total을 돌려 누적값으로 바꾸고,
const 1 ^>> total을 돌려, 들어온 값을 1로 바꾸고 total을 돌려 누적값으로 바꿉니다.
결국 리스트의 가장 마지막 누적값이 원소 개수가 됩니다.

uncurry가 없다면 [(모든 원소를 더한 값, 원소 개수)]이 됩니다. C1 &&& C2에서 C1은 C1대로 후임 Circuit을 만들고, C2는 C2대로 후임 Circuit을 만듭니다.

GHCi> runCircuit (total &&& (const 1 ^>> total)) $ [0,10,7,8]
[(0,1),(10,2),(17,3),(25,4)]
mean2 :: Fractional a => Circuit a a
mean2 = proc value -> do -- value에 0 10 7 8 순서대로 들어가면
  t <- total -< value -- 0 10 17 25 
  n <- total -< 1 -- 1 2 3 4
  return -< t / n -- 한 번 돌면 0/1 : 두 번째 10/2 : 세 번째 17/3 : 네 번째 25/4

※ 참고 - 확장 Arrows

mean1, mean2의 실행 결과는

GHCi> runCircuit mean1 [0,10,7,8]
[0.0,5.0,5.666666666666667,6.25]
GHCi> runCircuit mean2 [0,10,7,8]
[0.0,5.0,5.666666666666667,6.25]

total이 Arrow이기 때문에 (&&&)을 써서 병행하는 작업을 쉽게 표현할 수 있습니다.

Hangman 게임

행맨 게임: 낱말 맞추기. 알파벳 글자 수 만큼 빈자리를 만들어 둡니다. 돌아가며 한 글자를 골라서 낱말 안에 있으면 해당 자리에 보여주고, 없으면 페널티 포인트를 올리는 게임입니다.

위에서 정의한 Circuit을 이용해 게임 흐름을 모두 Arrow로 만드는 방법을 보여 줍니다.

제일 먼저 사전에서 랜덤하게 문제를 뽑습니다.

generator :: Random a => (a, a) -> StdGen -> Circuit () a
generator range rng = accum rng $ \() rng -> randomR range rng

accum은 나중에 runCircuit을 통해 입력을 받아 \() rng -> ... 함수를 실행한 후, 결과값을 가진 상태로 또 다음 accum 실행을 “준비”하는 함수입니다. 한 가지만 빼 놓고, 나머지 필요한 것들은 모두 미리 준비해 둔 작업입니다 .

dictionary = ["dog", "cat", "bird"]

pickWord :: StdGen -> Circuit () String
pickWord rng = proc () -> do -- 나중에 runCircuit으로 rng에 랜덤gen을 넘깁니다.
  idx <- generator (0, length dictionary - 1) rng -< ()
  returnA -< dictionary !! idx

여기선 특별한 외부 입력값을 받는 건 아니고, runCircuit으로 더미로 () 유닛을 받을 겁니다. 유닛으로 채워진 리스트를 받으면, gen값이 바뀌는 걸 잃어버리지 않고 다음으로 넘겨가며 유닛 개수만큼 랜덤값을 뽑아냅니다.
※ Reactive로 가면 이런 모양을 자주 만납니다. 시간의 흐름을 () 무한 리스트로 두고, 한 스텝(샘플링) 나아갈 때마다 ()를 가져오는 것으로 모델링합니다.
Circuit으로 래핑되어 있기 때문에, 안 쪽에 있는 함수에게 값을 주어 실행한다든지, 결과를 바깥으로 내보내려면, 매 번 패턴 매칭을 해서 풀어야 합니다. 하지만, Arrow 인스턴스로 만들었기 때문에, <-,-< 등을 이용해 쉽게 표현할 수 있습니다.

GHCi> rng <- getStdGen
GHCi> runCircuit (pickWord rng) [(), (), ()]
["dog","bird","dog"]
oneShot :: Circuit () Bool
oneShot = accum True $ \_ acc -> (acc, False)
--                                     False로 하드 코딩

당장은 이게 뭐하는 Circuit인가 싶은데 일단, 처음만 True를 돌려주고 그 후로는 False를 돌려준다는 것만 보고 넘어가 가겠습니다. (나중에 게임 시작에 딱 한 번만 일어나야 하는 동작을 표현할 때 씁니다.)

GHCi> runCircuit oneShot [(), (), (), (), ()]
[True,False,False,False,False]
delayedEcho :: a -> Circuit a a
delayedEcho acc = accum acc (\a b -> (b, a))
--                                   누적값과 결과값을 스왑

누적값과 결과값을 바꿔치기 합니다. 이 것도 뭐에 쓰는 물건인가 싶습니다.

GHCi> runCircuit (delayedEcho False) [True, False, False, False, True]
[False,True,False,False,False]

ArrowChoice

게임의 메인 Arrow는 계속 반복해서 실행되고, 낱말은 처음 한 번만 뽑고, 게임 진행동안 계속 기억하고 있어야 합니다. Rather than just mask its output on subsequent loops (이 말은 아마도, 실제 뽑는 작업은 하면서, 쓰지 않는 걸 얘기하는 것 같습니다.) 실제 한 번만 돌아가는게 퍼포먼스에서 유리합니다. 하지만, Circuit에선 “Arrow 뭉치combination”에 포함된 Arrow 컴포넌트의 모든 경로로 데이터가 흘러갑니다. (골드 버그 장치 혹은 도미노 등이 연상됩니다.) 하나의 경로로만 흘러가게 하려면, ArrowChoice클래스의 인스턴스로 만들어야 합니다.

※ 뭉치란 말이 투박하긴 하지만, 컴비네이션 결과물을 지칭하기에 적당한 의미를 가진 듯 합니다. 다른 곳에서도 쓰이는 “용어”는 아닙니다. 순수 한글 말을 쓰려고 고른 게 아니라, 대상을 가장 잘 표현하는 적당한 말같아 골랐습니다.

instance ArrowChoice Circuit where
  left orig@(Circuit cir) = Circuit $ \ebd -> case ebd of
    Left b  -> let (cir', c) = cir b
               in  (left cir', Left c)
    Right d -> (left orig, Right d)

left에 Circuit을 넣으면, Either를 받는 Circuit으로 바뀝니다. 입력으로 Left값이 들어 오면, 현재 Circuit이 가지고 있는 작업을 하고, Right가 들어 오면, 아무 작업도 하지 않습니다. 역시 마지막 라인의 (left orig, Right d)가 목에 걸립니다. Either를 받도록 바뀐 이 Circuit은, 다음 번 반복에도 Either를 받습니다. 위에서 설명한 (.)을 다시 떠올리면, c1-c2 Circuit을 돌렸다면, 다음 번엔 c1'-c2'을 돌리게 됩니다. 반복하려 할 때, 매 번 처음부터 다시 Arrow 뭉치를 만드는 게 아닙니다. 이전 반복에서 나온 결과들을 가지고 있는 상태입니다.

※ 하스켈은 다른 언어의 런타임들이 해주는 일을, runCircuit같은 걸로 사용자 수준으로 당겨온 느낌입니다.

ArrrowChoice 인스턴스로 만들면, <- 다음에 if를 쓸 수 있어, 이제 어떤 Arrow를 실행할지 고를 수 있습니다. 여기서 쓰인 if는 하스켈에서 보통 쓰던 그 if가 아닙니다.

local name binding

<-와 -< 사이에는 proc의 인자를 포함해서 어떤 local name binding도 들어갈 수 없습니다.

proc rng -> do
    idx <- generator (0, length dictionary -1) rng -< ()  --X 이렇게 못씀
                                           -- proc의 인자 rng를 <-, -< 사이에 써줄 수 없다.
    returnA -< dictionary !! idx

generator (0, length disctionary -1)을 평가 할 때는 rng가 스코프에 없습니다. 시작할 때만 Arrow가 생성되기 때문에 그렇습니다. 만일, 매 번 실행될 때마다 생성된다면 Arrow가 안에 상태state를 유지할 수 없을 겁니다.

getWord :: StdGen -> Circuit () String
getWord rng = proc () -> do
  firstTime <- oneShot -< () -- 처음 시작에만 True고, 그 뒤로는 모두 False
  mPicked <- if firstTime
    then do
      pciked <- pickWord rng -< () -- 처음 시작이면 단어 선택
      returnA -< Just picked
    else
      returnA -< Nothing -- 처음 시작이 아니라면 Nothing
  mWord <- accum' Nothing mplus -< mPicked 
  -- Nothing `mplus` (Just "dog") = Just "dog"
  -- (Just "cat") `mplus` (Just "dog") = Just "cat"
  returnA -< fromJust mWord
  -- fromJust는 Nothing이면 error를 던진다.

getWord를 실행해 보면,

GHCi> rng <- getStdGen
GHCi> runCircuit (getWord rng) [(), (), (), (), (), ()]
["dog","dog","dog","dog","dog","dog"]

여러 개의 Circuit들을 붙여 Circuit 뭉치를 만들고, 이 뭉치를 runCircuit으로 반복해서 돌릴텐데, 이렇게 도는 동안 getWord는 몇 번을 돌려도 처음 선택한 값만 가지고 있습니다.

Circuit 뭉치 실행

게임중에 반복되어 실행될 코드를 보면

attempts :: Int
attempts = 5

livesLeft :: Int -> String
livesLeft hung = "Lives: ["
                ++ replicate (attempts - hung) '#'
                ++ replicate hung ' '
                ++ "]"

hangman :: StdGen -> Circuit String (Bool, [String]) ------- Circuit 타입!
hangman rng = proc userInput -> do
  word <- getWord rng -< () -- 문제를 랜덤하게 고르고,
  let letter = listToMaybe userInput -- 나중에 runCircuit이 넣어 준다.
  guessed <- updateGuess -< (word, letter)
  hung <- updateHung -< (word, letter)
  end <- delayedEcho True -< not (word == guessed || hung >= attempts)
  let result = if word == guessed
                  then [guessed, "You won!"]
                  else if hung >= attempts
                       then [guessed, livesLeft hung, "You died!"]
                       else [guessed, livesLeft hung]
  returnA -< (end, result)
 where
  updateGuess :: Circuit (String, Maybe Char) String ------- Circuit 타입!
  updateGuess = accum' (repeat '_') $ \(word, letter) guess ->
    case letter of
      Just l -> map (\(w, g) -> if w == l then w else g) (zip word guess)
      Nothing -> take (length word) guess

  updateHung :: Circuit (String, Maybe Char) Int ------- Circuit 타입!
  updateHung = proc (word, letter) -> do
    total -< case letter of
      Just l -> if l `elem` word then 0 else 1
      Nothing -> 0

main :: IO ()
main = do
  rng <- getStdGen
  interact $ unlines
    . ("Welcome to Arrow Hangman":)
    . concat . map snd . takeWhile fst
    . runCircuit (hangman rng)
    . ("":)
    . lines

hangman이란 커다란 Circuit 뭉치를 만들고, runCircuit이 입력이 “한 번” 들어올 때마다 돌립니다. (합성 설명할 때처럼 바뀌었다는 의미에서 프라임을 붙이겠습니다.) 처음엔 Circuit을 돌리고, 그 다음 번엔 Circuit'을 돌리고, 그 다음엔 Circuit''… 이런 식입니다. Circuit이 돌고 나서 (continuation으로) 후임 Circuit'을 준비하는데, 기억해야 하는 정보를 모두 집어 넣어 준비합니다.

전역 변수 같은 바깥 스코프의 mutable한 변수-기억 장소-를 둘 수 없기 때문에 필요한 테크닉입니다. 지금 동작하는 함수 뭉치가, 결과값과 함께 다음 번 돌릴 함수continuation를 준비하면서 기억해야 될 것들을 새로 만드는 함수에 실어 놓습니다. 그리고는 runCircuit 같은 것들이 run하면서 준비된 함수를 실행합니다.

※ Reactive(Reactive-banana, Yampa, Reflex)를 볼 때 비슷한 모양들을 만나게 되니, 이런 continuation을 가진 모양에 충분히 익숙해지면 도움이 됩니다. 쓰고 보니, 함수형 전반에 걸쳐서 계속 만나는 모양입니다.

Welcome to Arrow Hangman
___
Lives: [#####]
a
___
Lives: [#### ]
g
__g
Lives: [#### ]
d
d_g
Lives: [#### ]
o
dog
You won!

Lazy 와 Stream

interact함수는 전체 stdin 입력을 받아 String -> String 함수에 넘깁니다.
lines는 String을 받아 [String] 리스트로 만듭니다.
runCircuit은 Circuit과 리스트를 받으면 리스트를 출력합니다.

interact가 받은 함수는, 한 번 돌아서 작업을 마친 후에, 또 반복하며 도는게 아닙니다. String을 받아 한 번만 돌고 String을 출력할 뿐입니다. 중간에, 원소 하나에 대한 작업이 끝나면 볼 수 있게 해놨을 뿐, interact가 String -> String함수를 loop 돌리는 게 아닙니다. 실행시킨 후 특별히 Ctrl-c 등으로 stdin을 끌내지 않으면, 입력으로 들어가는 String이 무한히 들어갑니다. Enter키를 누를 때마다 lines가 출력할 리스트의 원소 하나가 준비됩니다. 그럼 리스트를 받는 runCircuit이 전체는 아직이라도, 원소 하나가 준비되는대로 가져옵니다. 원소 하나를 받아 Circuit을 돌리고, 후임 Circuit을 준비한 후 다음 원소를 Lazy하게 기다립니다.

스트림(여기선 무한 리스트지만, 어떤 것이든 재귀로 정의된 타입)을 다루는 Lazy 표현은 우아하지만, Strict 나라에서 살던 사람이, Lazy 나라로 넘어와서, 읽는 것을 넘어 원어민처럼 생각 자체를 Lazy하게 하려면 벽이 심하게 높은 것 같습니다.

바나나 브라켓 - 함수와 arrow 명령어 묶기combine

GHC에는 arrow 구문과, arrow에 적용하는 함수를 컴바인하는 바나나 브라켓 (| |)가 있습니다. 이를 이용하면 다음처럼 쓸 수 있습니다.

mean3 :: Fractional a => Circuit a a
mean3 = proc value -> do
  (t, n) <- (| (&&&) (total -< value) (total -< 1) |)
  returnA -< t / n
mean2 :: Fractional a => Circuit a a
mean2 = proc value -> do
  t <- total -< value
  n <- total -< 1
  returnA -< t / n

Arrow를 인자로 받아 동작하는 함수와 Arrow 구문을 묶을 때 바나나 브라켓을 쓴다고 합니다. (Ross Paterson 논문에선 괄호 대신 form 키워드를 썼다고 합니다.) 바나나 브라켓 안의 첫 번째 아이템은 임의의 개수의 Arrow를 입력으로 받아 Arrow를 돌려주는 함수입니다. 중위 연산자는 이 안에서는 쓸 수 없습니다.

mean3 :: Fractional a => Circuit a a
mean3 = proc value -> do
  (t, n) <- (| (&&&) (total -< value) (total -< 1) |)
               ^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^ 
                 |        Arrow          Arrow
               Arrow를 받는 함수
  returnA -< t / n

“Although there’s no reason to” 라고 하는 걸로 보아, 잘 안 쓰이나 봅니다. proc 구문을 쓰지 않고 편하게 Arrow를 묶을combine 수 있는 게 장점인데,

mean4 :: Fractional a => Circuit a a
mean4 = proc value -> do
  (t, n) <- (total -< value) &&& (total -< 1)
  return -< t / n

이렇게, 바나나 브라켓을 떼어내도 GHC가 알아서 잘 해석한다니, 가볍게 보고 지나가도 될 것 같습니다.

왜 Hangman 게임 흐름을 Arrow 인스턴스인 Circuit으로 모델링했을까?

이 글은, 어떤 요소가 Arrow로 해결하면 좋은가를 찾는 게 목표입니다.

먼저 Circuit을 왜 Arrow 인스턴스로 만들었을까요?

Circuit 타입은 뭘 의미할까요?

eachTimeAddOne = Circuit (\a -> ( eachTimeAddOne, (+1) a))
-- 원래 작업은            \a ->                   (+1) a

\a -> a + 1을 Circuit 타입에 넣으면 무슨 일을 할 수 있을까요?

함수형은 모든 필요한 값은 인자로 받아야만 하고, 전역 변수같이 메모리를 따로 둘 수 없어 체이닝동안 생기는 기억해야 할 값들을 편리하게 다루기 위한 테크닉들이 필요합니다.

(지금 부터는 아주 상상입니다.)

함수 + 추가 정보

\a -> a + 1을 Circuit으로 래핑해 두면, 반드시 Circuit을 패턴 매칭해서 안을 봐야 a + 1을 꺼내 올 수 있으니, 반드시 일어나야 하는 절차를 둘 곳이 생깁니다. 타입으로 래핑하니, 같이 따라 다녀야 할 정보를 둘 자리도 튜플같은 Product 타입으로 마련할 수 있습니다.

여러 정보를 한 곳에 묶어두는 방법으로 함수 안에다 두는 방법이 있습니다. 체이닝동안 필요한 정보를 product 타입으로 둘 수도 있지만, 함수가 가지고 있게 할 수도 있습니다. 동적인 정보라면 이렇게 하는 쪽이 더 적합할 수 있습니다.

사실은 컴비네이터 체이닝

보통 함수 체이닝을 할 때 (.)을 써서 체이닝을 합니다. 하스켈에서 이루어지는 체이닝(컴비네이션)들은 자세히 보면, 타입이 가지고 있는 함수를 체이닝 하거나, 혹은 함수 자체를 체이닝 하는 것처럼 말하지만, 사실은 컴비네이터를 체이닝하는 것입니다. 예를 들어 a -> b, b -> c, c -> d를 체이닝한다면, (.) (b -> c) (a -> b)와 (c -> d)를 다시 (.)으로 묶습니다. (.)의 체인입니다. 체이닝할때마다 반복되는 작업이 있다면 (.)을 새롭게 정의하면 됩니다. 모나드 같은 경우는 Effect 관련 작업은 바인드가 맡아서 하도록 해 뒀습니다. 모나드 경우도 a -> m b의 체인이 아니라, 바인드의 체인입니다.

RUN!

코드 구석 구석을 읽다보면, 이 부분을 간과하는 경우가 많은 것 같습니다. 타입, 컴비네이터 공조만으로 끝난 게 아니라, 한 가지가 더 있습니다. 바로 트리거를 당기는 역할을 하는 run~류의 함수들입니다. 우리말로는 “실행기runner”라 번역하기도 합니다. Circuit타입을 정의하고, 합성하거나 흐름을 제어하는 컴비네이터들을 정의해서 커다란 Circuit 뭉치를 만들었다면, 마지막 runCircuit을 거치게 됩니다.

입력 a를 받아서 b를 얻기까지 보통 함수와 Circuit의 차이

a -> b    vs    Circuit 타입
                각 종 컴비네이터
                runCircuit

절차를 이리 많이 추가해 뒀으니, 훨씬 많은 걸 표현할 수 있는 건 당연한데, 명령형에 머리가 고정되어 있어, 가끔 퍼포먼스가 염려되긴 합니다.

반복해서 돈다. 그래서 이름이 Circuit이다.

이제 위 시각으로 Circuit을 읽어 보겠습니다.
언젠가 a를 받으면 b를 돌려주는 게 아니라,
언젠가 a를 받으면, (후임 Circuit - 다음 이어지는 작업에 할 일, 결과 b) 2튜플을 결과로 돌려줄 “준비”를 한 함수를 돌려줍니다. 후임 Circuit은 결과 b에 의존해서 만들거나 현재 Circuit과 같을 수 있습니다. 그럼, runCircuit이 처음 입력값 a를 가지고, 리스트의 첫 번째 원소에 작업을 하고, 그 다음 원소를 꺼내 후임 Circuit을 꺼내와 사용합니다. 이 후임 Circuit 안에는 또 이어서 쓸 후임 Circuit이 들어 있습니다.

반복되는 작업을 Circuit으로 모델링

계속 반복되는 메인 루프가 있고, 루프가 도는 동안 기억해야 할 정보들이 있습니다. 아주 일반적인 상황 아닌가 싶은데요. 행맨 정도의 게임에서는 Circuit으로 모델링하는 게 우아해 보이기는 한데, 루프가 복잡해져도 우아할 수 있을까 싶습니다.

왜 Circuit을 Arrow 인스턴스로 만들까?

루프 안을 뜯어보면, 데이터 흐름을 요리 조리 바꿔야 합니다. 병행 작업을 하는 것도 있고, 상황에 따라 분기(if)해야 하는 것도 있고요. 이럴 때 Arrow 인터페이스를 도입하면, 병행, if를 다루는 인터페이스도 있고, 무엇보다 do 노테이션으로 보기 좋게 표현할 수 있다는데 눈이 갑니다.

위 정리는 너무 일반적인 상황이라, 이 게 Arrow가 쓰이는 이유라면, 엄청나게 많은 경우에 Arrow를 쓸텐데, 그러지 않는 걸 보면 모델링 대상이 복잡해지면 우아하지 않기 때문 아닐까요?

합성 (.)을 일반화 하기 위해 타입으로 래핑한다는 생각은 어렵지 않지만, 이렇게 래핑한 것들의 흐름을 제어할 수 있는 체계들을 정돈되게 만들어 둔 건 쉽게 생각할 수 있는 건 아니겠습니다.

참고
Arrow를 이론적으로 접근하면 Freyd Category로 접근해야 하는데, 그나마 실용에 좀 가까운 “이론”으로 접근하려면 Bartosz Milewski - Arrows are strong profunctor 이 출발점이 될 수 있겠습니다.

Github 계정이 없는 분은 메일로 보내주세요. lionhairdino at gmail.com