확장 Arrows (작성 중)

GHC User Guide 6.2.19. Arrow notation
[Programming with Arrow - John Hughes](https://www.cse.chalmers.se/~rjmh/afp-arrows.pdf> 챕터 3.1

Arrow Notation

do표기처럼 단순하고, 읽기 편할 줄 알았는데, 좀 복잡합니다. Arrow 자체도 깊게 알고 있는 상태가 아니라서 지금 필요한 정도까지만 봐야 할 것 같습니다. 이 번 글은, 다 이해한 후에 작성하는 게 아니라, 공부 중에 노트한 걸 올려두고, 정리가 될 때마다 조금씩 수정해 가려 합니다. 아마도 오랫동안 미완성 문서일 듯 합니다.

참고
A New Notation for Arrows - Ross Paterson

어느 정도 이해를 하고 나서도, proc abstraction을 기억하기가 쉽지 않습니다. 처음 봤을 때, 모나드의 do 구문보단 직관적이지 않아 좀 못 생겼다는 생각이 들었습니다. 모나드의 do에서

do
  a <- action1
  b <- action2
  return $ a + b

a는 \a -> action2가 받으며, b는 그 다음 라인의 \b -> return...이 받습니다. proc 안에 있는 do구문에서도 <- 역할은 이와 같습니다. 다음 라인의 람다 변수로 들어간다는 <-와 Arrow 함수들을 합쳐 <-Arrow함수-< 모양 전체를 Arrow라고 부르기도 합니다. 최종 아래 모양으로 보이도록 만드는 게 목표입니다.
출력 <--- 함수 <--- 입력

proc

arrow 확장을 쓰는 표현에서 proc는 lambda abstraction에서 lambda 같은 역할을 합니다. proc는 함수가 아니라, 새로운 키워드입니다. proc 전체를 프로시저, 혹은 arrow abstraction이라 부릅니다.

 \   x ->      x+1    -- 람다식과 비교
proc x -> f -< x+1
          ^^^^^^^^
          proc의 body부분을 명령어command라 부릅니다.
          (Arrow의 body는 expression이 아닙니다.)

proc는 \ 람다같은 역할입니다.
\x가 람다식에서 쓸 묶인binding 변수를 나타내듯이,
proc x에서 x는 arrow 식에서 쓸 묶인 변수입니다.

Command는 기존에 없던 문법 구성 요소라 하는데, 자세한 설명은 없습니다. 컴비네이터들을 써서 Arrow를 구성하는construct 걸 표현할 때 쓰기 위해 새로 도입했다고 합니다. 가장 단순한 Command인 f -< exp를 보면, f $ v같은 “arrow application”이라 생각할 수도 있습니다. 모양이나 구조가 그리 직관적으로 보이지 않긴 합니다.

-<

-<는 식별자가 아니고, arrow 타입 식과 arrow의 입력으로 넘길 식에서 Command를 만들어내는 작업을 나타내는 심볼입니다. analogue of application for arrow라는데, 우리 말로는 뭐라하면 좋은 지 아직 모르겠습니다.

proc x -> f -< x+1는 확장없이 쓰면, 아래와 같습니다.

arr (\x -> x + 1) >>> f

proc pat -> a -< e ----> arr (\pat -> e) >>> a

pat같은 arrow-bound 변수는 -< 왼쪽에서는 유효하지 않습니다.(not in scope) 이 말은 람다식을 인자로 받는 컴비네이터로는 proc를 구현할 수 없다는 뜻입니다.

proc (f, x) -> f -< x

이렇게는 못 씁니다. 확장을 안쓰고 표현하면 arr (\(f, x) -> x) >>> f 이렇게 되는데, f가 유효 범위 바깥에서 쓰이고 있습니다. 바깥에서 입력을 받아 오려면 app을 써야 합니다. (언제 이런 게 필요할까 생각해보면, f가 continuation인 경우가 떠오릅니다.)

-<<, app

아래 둘은 같은 표현입니다.

proc (f,x) -> app -<  (f,x)
-- arr (\(f,x) -> (f,x)) >>> app
proc (f,x) -> f   -<< x

app :: arr (arr b c, b) c은 입력으로 2튜플을 받고, c타입을 출력하는 함수를 가지고 있습니다. app의 -> 인스턴스는 app :: (b -> c, b) ->c

아래 둘은 같은 표현입니다.

proc x -> f x -<< x+1
arr(\x -> (f x, x+1)) >>> app

마치 바운딩된 변수가 오른 쪽에만 나타나면 <를 하나만 써서 -<, 왼쪽 오른쪽 모두에 나타난다면, <를 두 번 써서 -<<로 나타내는 것처럼 보입니다. 이런 모양을 고른 이유를 알면 기억하기 좋을텐데, 기호를 고른 이유를 말해주는 텍스트는 못봤습니다. 이 경우에 쓰이는 arrow는 ArrowApply 클래스 인스턴스여야 하며, 이런 arrow들은 모나드와 동일합니다. 보통은 이렇게 쓰는 것보단 모나드가 편하다고 합니다.

command를 위한 do표기법

proc x -> do
  y <- f -< x+1 
  g -< 2*y
  let z = x+y
  t <- h -< x*z
  returnA -< t+z

• y <- f -< x+1 arrow f에 x+1을 넣어 주고, 결과값을 y에 매치합니다.
• g -< 2*y arrow g에 2*y를 넣어 주고, 결과값은 무시합니다.
• let z = x+y x+y를 z로 놓고,
• t <- h -< x*z arrow h에 x*z를 넣어주고, 결과값을 t에 매치합니다.
• returnA -< t+z (returnA는 Control.Arrow에 id로 정의되어 있습니다.)

이 글을 쓰는 1차 목표가 위 코드를 아래같이 읽을 수 있는 지식을 얻는 거였습니다.

• arr (\x -> (x, x)) >>>: x를 기억하기 위해 x를 duplicate합니다.

• first (arr (\x -> x + 1) >>> f) >>>: (x, x) 두 개중 앞에것만 f arrow를 적용합니다.

• arr (\ (y, x) -> (y, (x, y))) >>>: (y, (x, y)) 처음 받아 온 x와 f의 결과값 y를 모두 가지고 있는 2튜플을 준비해야 합니다. 2튜플의 두 번째가 x만 기억했던 것이 지금은 (x, y)를 가지고 있습니다. (※ 계속 결과값을 무시하지 않고 진행하면 ((x, y), z)… 이런 식으로 2튜플 속에 2튜플로 계속 결과값들을 기억합니다.)

  (현재결과값, x) —- (현재결과값, (x, y))

• arr snd: g의 결과값을 무시하므로 snd로 (현재결과값, (x, y)) 두 번째 튜플을 가져옵니다.

• arr (\ (x,y) -> let z = x+y in ((x,z), z)) >>>: 여긴 arrow 관련 동작은 없습니다.

• first (arr (\ (x, z) -> x*z) >>> h) >>>: 받은 2튜플의 첫 번째 (x, z)에만 h arrow를 적용

• arr (\ (t, z) -> t+z) >>>: (결과값, z)를 (t, z)로 받아 t+z

• returnA: 최종 t+z를 반환

처음 봤을 때는, 조금 귀찮지만 확장 없이 써도 되겠다 생각했는데, 위를 보면 도저히 확장없이 arrow를 쓰는 건 어려울 것 같습니다. 필요한 값들을 잃어버리지 않도록, 일일이 2튜플속에 2튜플…을 만들면서 진행해야 합니다. 이렇게 쓰는 사람이 있을까 싶은데요.

rec

rec 키워드를 써서 상호 재귀 바인딩을 구현하는 것도 가능합니다.

counter :: ArrowCircuit a => a Bool Int
counter = proc reset -> do
        rec     output <- returnA -< if reset then 0 else next -- output은 next에 의존
                next <- delay 0 -< output+1                    -- next는 output에 의존
        returnA -< output

output과 next가 서로 물고 물려 있는 상호 재귀가 딱 봐도 불편합니다.

rec는 ArrowLoop의 loop 함수로 구현되어 있습니다.

class Arrow a => ArrowLoop a where
        loop :: a (b,d) (c,d) -> a b c
                ^^^^^^^^^^^^^
               매개 변수는 하나

instance ArrowLoop (->) where
        loop f b = let (c,d) = f (b,d) in c

loop는 어찌 됐건 인자 하나만 받습니다. 그런데 (->)의 ArrowLoop 인스턴스 정의는 loop f b 로 인자 두 개를 받고 있습니다.
이유는 (->)에 있습니다. a자리에 (->)를 넣어 보겠습니다.

loop :: ((b,d) -> (c,d)) -> (b -> c)
loop :: ((b,d) -> (c,d)) -> b -> c
--      ^^^^^^^^^^^^^^^^   ^^^
--             f            b

f는 (b,d)를 받아서 (c,d)를 돌려주는 함수입니다. 최종 결과는 여기에서 c만 가져 갑니다. 이게 어째서 loop일까요? (※ Fix 함수, MonadFix 참고)

let ( ,d) = f ( , d)

f는 (b,d)를 받아야 하는데, b는 인자로 받았는데, d는 어디서 왔을까요?

d = snd(f (b, d))
d = snd(f (b, snd(f(b, d))))
d = snd(f (b, snd(f(b, snd(f (b, d))))))
...

f (b, snd(f (b, snd(f(b, snd(f (b, ...))))))) 결국 이 값을 구하는 것으로 보면 되는데, 머리도 마음도 불편합니다. 이유는 무한히 가고 있는 ... 때문입니다. 언제 멈출 것인가? 하스켈에서 무한한 표현들은 값이 쓰일 무렵에는 결국 파트너를 만나든지 스스로 끝내든지 해서 실용적인 값으로 바뀝니다.
How does this definition of ArrowLoop.loop work? 여기 첫 번째 답변의 코드를 가져와서 보겠습니다.

powers = loop $ \(x,l) -> (l, x:map (*x) l)

if…then…else

arr (\x -> if p x then Left x else Right x) >>> f ||| g

확장을 쓰면 다음처럼 표현할 수 있습니다.

proc x -> if p x then f -< x else g -< x

여기서 쓰인 if...then...else 는 일반 if문이 아니라, proc 안에서 쓰는 conditional command라 부르고, 다음 처럼 번역됩니다.

proc pat -> if e then c1 else c2
----->
arr (\pat -> if e then Left pat else Right pat) >>> (proc pat -> c1 ||| proc pat -> c2)

case

mapA f = arr listcase >>>
         arr (const []) ||| (f *** mapA f >>> arr (uncurry (:)))
  where listcase [] = Left ()
        listcase (x:xs) = Right (x,s)
--확장을 쓰면-->
mapA f = proc xs ->
  case xs of
    [] -> returnA -< []
    x:xs' -> (f *** mapA f >>> uncurry (:)) -< (x, xs')

…작성 중