화살표(컴퓨터 과학)

Arrow (computer science)
이 기사는 컴퓨터 과학의 개념에 관한 것입니다.다른 용도는 화살표(동음이의하지 않음)를 참조하십시오.

컴퓨터 과학에서 화살표 또는 볼트()는 프로그래밍에서 순수하고 선언적인 방식으로 계산을 설명하는 데 사용되는 유형 클래스입니다.컴퓨터 과학자 John Hughes에 의해 모나드의 일반화로 처음 제안된 [1]화살표는 계산에서 논리적 단계 사이의 관계를 참조하여 투명하게 표현하는 방법을 제공합니다.모나드와 달리 화살표는 입력을 하나만 갖는 것으로 단계를 제한하지 않습니다.그 결과, 그들은 다른 응용 프로그램 [1][2]중에서도 기능 반응형 프로그래밍, 포인트 프리 프로그래밍 및 파서에 사용되었습니다.

동기와 역사

화살표가 별개의 클래스로 인식되기 전에 사용되었지만, John Hughes가 화살표에 초점을 맞춘 연구를 처음 발표한 것은 2000년이 되어서였습니다.그때까지 모나드는 프로그램 로직을 순수 코드로 조합해야 하는 대부분의 문제에 충분하다는 것이 입증되었습니다.그러나 그래픽 사용자 인터페이스 및 특정 효율적인 파서를 위한 Fudgets 라이브러리와 같은 일부 유용한 라이브러리는 단항 [1]형식으로 다시 쓰기를 거부했습니다.

화살표의 공식적인 개념은 모나딕 코드에 대한 이러한 예외를 설명하기 위해 개발되었으며, 그 과정에서 모나드 [1]자체가 화살표의 하위 집합으로 밝혀졌습니다.그 이후로, 화살은 활발한 연구 분야가 되었습니다.그들의 기본적인 법과 운영은 여러 번 개선되었으며, 화살 미적분과 같은 최근 공식은 5개의 [3]법만 필요로 합니다.

범주 이론과의 관계

범주 이론에서, 모든 모나드의 클라이즐리 범주는 [1]휴즈 화살표의 적절한 부분 집합을 형성합니다.한때 [4]프레이드 범주가 화살표와 동등하다고 믿었지만, 그 이후로 화살표가 훨씬 더 일반적이라는 것이 증명되었습니다.사실, 화살표는 단순히 동등한 것이 아니라 농축된 프레이드 [5]범주와 직접적으로 동일합니다.

정의.

모든 유형 클래스와 마찬가지로 화살표는 모든 데이터 유형에 적용할 수 있는 품질 집합으로 생각할 수 있습니다.해스켈 프로그래밍 언어에서 화살표는 함수를 허용합니다.->기호)를 사용하여 수정된 형식으로 결합합니다.하지만, 실제 용어 "화살표"는 (모든 것은 아니지만) 일부 화살표가 다른 클라이슬리 범주의 형태론(범주 이론에서 "화살표"라고도 함)에 대응한다는 사실에서 유래했을 수도 있습니다.비교적 새로운 개념으로, 단일 표준 정의는 없지만, 모든 공식은 논리적으로 동등하고, 몇 가지 필수 방법을 특징으로 하며, 특정 수학 법칙을 [6]엄격하게 따릅니다.

기능들

현재 Haskell 표준 라이브러리에서 사용되는 설명은 세 가지 기본 연산만 필요합니다.

  • 형식 시공자 모든 유형에서 다른 t로 함수 ->를 가져가고, 두 [7]유형 사이의 화살표 A로 해당 함수를 들어 올리는 ar.
아어 (s -> t)        ->   A s t
  • 먼저 두 유형 사이에 화살표를 가져다가 튜플 사이에 화살표로 변환하는 배관 방식입니다.튜플의 첫 번째 요소는 변경된 입력 및 출력 부분을 나타내며, 두 번째 요소는 [7]계산을 우회하는 변경되지 않은 부분을 설명하는 세 번째 유형입니다.
첫번째 (A s t)       ->   A (s,u) (t,u)
  • 모든 화살표는 범주여야 하므로 범주 클래스에서 세 번째 작업을 상속합니다.제1함수의 출력과 제2함수의 입력이 일치하는 [7]타입을 갖는 한, 제1함수에 제2화살표를 부가할 수 있는 구성 연산자 >>.
A s t  >>>  A t u   ->   A s u

화살표를 정의하려면 이 세 가지 절차만 엄격히 필요하지만 실제 및 이론에서 화살표를 사용하기 쉽게 하는 다른 방법을 도출할 수 있습니다.

ar와 first에서 하나 더 유용한 방법을 도출할 수 있습니다(그리고 첫 번째 방법을 도출할 수 있습니다).

  • 입력 및 출력 유형이 서로 다를 수 있는 두 개의 화살표를 사용하여 두 개의 복합 유형 사이에 하나의 화살표로 융합하는 병합 연산자 ***.병합 연산자가 반드시 [7]교환 연산자일 필요는 없습니다.
A s t  ***  A u v   ->   A (s,u) (t,v)

화살의 법칙

화살표는 몇 가지 명확한 절차를 제공할 뿐만 아니라 다음과 같은 모든 유형에 대해 특정 규칙을 준수해야 합니다.

  • 화살표는 항상 모든 유형의 ID ID(기본적으로 [7]범주 내 모든 유형에 대한 모든 값의 정의)를 유지해야 합니다.
아어 이드              ==   이드
  • 두 기능 f&g를 연결할 때 필요한 화살표 작업은 [7]왼쪽부터 구성에 걸쳐 분산되어야 합니다.
아어 (f >>> g)       ==   아어 f  >>>  아어 g 첫번째 (f >>> g)     ==   첫번째 f  >>>  첫번째 g
  • 이전 법에서는 배관과 리프팅이 [7]함께 발생할 때 순서가 무관해야 하기 때문에 배관을 기능에 직접 적용할 수 있습니다.
아어 (첫번째 f)       ==   첫번째 (아어 f)

나머지 법칙은 성분의 순서가 뒤바뀌었을 때 파이프 방법이 어떻게 동작하는지를 제한하며, 식을 단순화할 수도 있습니다.

  • ID가 두 번째 함수와 병합되어 화살표를 형성하는 경우, 이를 파이프 함수에 연결하는 [7]것이 교환적이어야 합니다.
아어 (이드 *** g)  >>>  첫번째 f       ==   첫번째 f  >>>  아어 (이드 *** g)
  • 형식 단순화 전에 함수를 배관하는 것은 비지핑 함수에 [7]연결하기 전에 형식을 단순화하는 것과 같아야 합니다.
첫번째 f  >>>  아어 ((s,t) -> s)     ==   아어 ((s,t) -> s)  >>>  f
  • 마지막으로, 중첩된 결과 튜플을 다시 연결하기 전에 함수를 두 번 배관하는 것은 함수의 단일 바이패스를 연결하기 전에 중첩된 튜플을 다시 연결하는 것과 같아야 합니다.즉,[7] 스택된 바이패스는 함수에 의해 변경되지 않은 요소를 먼저 번들링하여 평평하게 만들 수 있습니다.
첫번째 (첫번째 f)  >>>  아어 ( ((s,t),u) -> (s,(t,u)) )   ==   아어 ( ((s,t),u) -> (s,(t,u)) )  >>>  첫번째 f

적용들

추가 작업 및 제한을 정의하여 특정 상황에 맞게 화살표를 확장할 수 있습니다.일반적으로 사용되는 버전에는 계산이 조건부 결정을 할 수 있는 선택사항이 있는 화살표와 단계에서 자체 출력을 입력으로 취할 수 있는 피드백이 있는 화살표가 있습니다.응용 프로그램이 있는 화살표로 알려진 또 다른 화살표 세트는 실제로 [6]모나드와 동일하기 때문에 실제로 거의 사용되지 않습니다.

효용.

화살표에는 여러 가지 이점이 있는데, 대부분 프로그램 논리를 명시적이면서도 간결하게 만드는 능력에서 비롯됩니다.부작용을 피하는 것 외에도, 순수하게 기능적인 프로그래밍은 정적 코드 분석을 위한 더 많은 기회를 만듭니다.이것은 이론적으로 더 나은 컴파일러 최적화, 더 쉬운 디버깅 및 구문 [6]sugar와 같은 기능으로 이어질 수 있습니다.

화살표를 엄격하게 요구하는 프로그램은 없지만, 그들은 순수하고 선언적인 코드를 전달하는 밀도 높은 함수의 대부분을 일반화합니다.또한 프로그램 단계 간의 공통 연결에 고유한 클래스 정의를 부여하여 코드 재사용을 장려할 수 있습니다.일반적으로 유형에 적용할 수 있는 기능은 재사용 가능성에 기여하고 인터페이스를 [6]단순하게 유지합니다.

화살표에는 화살표 법칙을 충족하는 화살표를 정의하는 초기 작업을 포함하여 몇 가지 단점이 있습니다.모나드는 일반적으로 구현하기 쉽고 화살표의 추가 기능이 필요하지 않을 수 있으므로 모나드를 [6]사용하는 것이 좋습니다.많은 기능적 프로그래밍 구조에 적용되는 또 다른 문제는 화살표가 있는 코드를 컴퓨터 명령 [citation needed]집합에 사용되는 명령형으로 효율적으로 컴파일하는 것입니다.

한계

다음을 정의해야 하는 요구 사항 때문에arr순수한 기능을 들어 올리는 기능, 화살표의 적용 가능성이 제한됩니다.예를 들어 양방향 변환은 화살표가 될 수 없습니다. 왜냐하면 사용할 때 순수 함수뿐만 아니라 역함수도 제공해야 하기 때문입니다.arr이것은[8] 또한 불필요한 전파를 중단시키는 푸시 기반 반응 프레임워크를 설명하는 화살표의 사용을 제한합니다.마찬가지로 쌍을 사용하여 값을 튜플링하면 값을 다시 그룹화하기 위해 추가 결합자가 필요한 어려운 코딩 스타일이 발생하고 다른 방식으로 그룹화된 화살표의 동등성에 대한 근본적인 질문이 제기됩니다.이러한 제한은 여전히 미해결 문제로 남아 있으며, 일반화 화살표[8] 및 N-ary[9] FRP와 같은 확장 기능은 이러한 문제를 탐구합니다.

화살표의 유용성의 대부분은 광학에 적용되는 Profunctor(함수가 있는 사전 및 사후 합성만 필요함)와 같은 더 일반적인 클래스에 의해 가정됩니다.화살표는 기본적으로 강력한 의미를 지니며, 법은 약간 다르지만 범주이기도 합니다.

레퍼런스

  1. ^ a b c d e Hughes, John (May 2000). "Generalising Monads to Arrows". Science of Computer Programming. 37 (1–3): 67–111. doi:10.1016/S0167-6423(99)00023-4. ISSN 0167-6423.
  2. ^ Paterson, Ross (27 March 2003). "Chapter 10: Arrows and Computation" (PS.GZ). In Gibbons, Jeremy; de Moor, Oege (eds.). The Fun of Programming. Palgrave Macmillan. pp. 201–222. ISBN 978-1403907721. Retrieved 10 June 2012.
  3. ^ Lindley, Sam; Wadler, Philip; Yallop, Jeremy (January 2010). "The Arrow Calculus" (PDF). Journal of Functional Programming. 20 (1): 51–69. doi:10.1017/S095679680999027X. hdl:1842/3716. ISSN 0956-7968. S2CID 7387691. Retrieved 10 June 2012.
  4. ^ Jacobs, Bart; Heunen, Chris; Hasuo, Ichiro (2009). "Categorical Semantics for Arrows". Journal of Functional Programming. 19 (3–4): 403–438. doi:10.1017/S0956796809007308. hdl:2066/75278.
  5. ^ Atkey, Robert (8 March 2011). "What is a Categorical Model of Arrows?". Electronic Notes in Theoretical Computer Science. 229 (5): 19–37. doi:10.1016/j.entcs.2011.02.014. ISSN 1571-0661.
  6. ^ a b c d e Hughes, John (2005). "Programming with Arrows" (PDF). Advanced Functional Programming. 5th International Summer School on Advanced Functional Programming. 14–21 August 2004. Tartu, Estonia. Springer. pp. 73–129. doi:10.1007/11546382_2. ISBN 978-3-540-28540-3. Retrieved 10 June 2012.
  7. ^ a b c d e f g h i j Paterson, Ross (2002). "Control.Arrow". base-4.5.0.0: Basic libraries. haskell.org. Archived from the original on 13 February 2006. Retrieved 10 June 2012.
  8. ^ a b Joseph, Adam Megacz (2014). "Generalized Arrows" (PDF). Technical Report No. UCB/EECS-2014-130. EECS Department, University of California, Berkeley. Retrieved 20 October 2018.
  9. ^ Sculthorpe, Neil (2011). Towards safe and efficient functional reactive programming (PDF) (PhD). University of Nottingham.

외부 링크

위키책 해스켈에는 다음과 같은 주제의 페이지가 있습니다.