토탈 함수 프로그래밍

Total functional programming

토탈 펑셔널 프로그래밍(total functional programming, 일반 또는 약한 펑셔널 프로그래밍과 대비됨)[1]은 프로그램의 범위를 종료 가능한 프로그램으로 제한하는 프로그래밍 패러다임입니다.[2]

제한사항

종료는 다음과 같은 제한에 의해 보장됩니다.

  1. 제한된 형태의 재귀는 Walther 재귀, 하위 구조적 재귀 또는 코드의 추상적 해석에 의해 입증된 "강력한 정규화"와 같은 "축소된" 형태의 인수에만 작동합니다.[3]
  2. 모든 함수는 부분 함수가 아닌 전체 함수여야 합니다. 즉, 도메인 내의 모든 것에 대한 정의가 있어야 합니다.
    • 일반적으로 사용되는 분할과 같은 부분 함수를 전체로 확장하는 몇 가지 가능한 방법이 있습니다. 함수가 일반적으로 정의되지 않은 입력에 대해 임의의 결과를 선택합니다(:∀ x ∈ N. x ÷ 0={\\forall x\mathbb {N}).위해 x\ 00}); 해당 입력에 대한 결과를 지정하기 위해 다른 인수를 추가하거나, 정제 유형과 같은 유형 시스템 기능을 사용하여 제외합니다.

이러한 제한은 전체 함수 프로그래밍이 튜링-완전하지 않다는 것을 의미합니다. 그러나 사용할 수 있는 알고리즘 세트는 여전히 엄청납니다. 예를 들어, 점근적 상한이 계산될 수 있는 알고리즘(자체적으로 발터 재귀만을 사용하는 프로그램에 의해)은 반복 또는 재귀마다 감소되는 추가 인수로 상한을 사용하여 증명 가능하게 종료되는 함수로 사소한 변환이 가능합니다.

예를 들어 퀵 정렬은 사소한 구조적 재귀적인 것으로 나타나지 않지만 벡터 길이의 최대 깊이(최악의 경우 시간 복잡도 O(n2))로만 재귀합니다. Haskell을 사용한 목록의 빠른 정렬 구현은 다음과 같습니다. 

수입품 Data.List (칸막이의)  qsort []       = [] qsort [a]      = [a] qsort (a:~하듯이)   = 허락하다 (덜한, 보다 큰) = 칸막이의 (<a) ~하듯이                  안에 qsort 덜한 ++ [a] ++ qsort 보다 큰

벡터의 길이를 한계로 사용하여 하위 구조적 재귀를 만드는 방법은 다음과 같습니다. 

수입품 Data.List (칸막이의)  qsort x = qsortSub x x -- 최소격 qsortSub []     ~하듯이     = ~하듯이 -- 종료를 나타냅니다. -- 표준 qsort 케이스 qsortSub (l:ls) []     = [] -- 비재귀적인, 그래서 받아들여진 qsortSub (l:ls) [a]    = [a] -- 비재귀적인, 그래서 받아들여진 qsortSub (l:ls) (a:~하듯이) = 허락하다 (덜한, 보다 큰) = 칸막이의 (<a) ~하듯이                             -- 재귀적이지만 재귀적인 것은 의 하위 구조인                             -- 첫 번째 입력입니다.                          안에 qsortSub ls 덜한 ++ [a] ++ qsortSub ls 보다 큰

일부 알고리즘 클래스는 이론적 상한이 없지만 실제 상한이 있습니다(예를 들어, 일부 휴리스틱 기반 알고리즘은 너무 많은 재귀 후 "포기"하도록 프로그래밍되어 종료를 보장할 수 있습니다).

전체 기능 프로그래밍의 또 다른 결과는 엄격한 평가와 게으른 평가 모두 원칙적으로 동일한 동작을 초래한다는 것입니다. 그러나 성능상의 이유로 둘 중 하나가 여전히 바람직할 수 있습니다(또는 필요하기도 합니다).[4]

전체 기능 프로그래밍에서는 데이터와 코데이터를 구분합니다. 전자는 유한한 반면 후자는 잠재적으로 무한합니다. 잠재적으로 무한한 데이터 구조는 I/O와 같은 애플리케이션에 사용됩니다. 코데이터를 사용하는 것은 코커싱과 같은 작업의 사용을 수반합니다. 그러나 코데이터 없이도 (종속형이 있는) 전체 기능 프로그래밍 언어로 I/O를 할 수 있습니다.[5]

Epigram과 Charity 둘 다 Turner가 논문에서 명시한 방식으로 작동하지는 않지만 전체 기능 프로그래밍 언어로 간주될 수 있습니다. 그래서 일반적인 시스템 F, 마르틴-뢰프 유형 이론 또는 구성의 미적분학에서 직접 프로그래밍할 수 있습니다.

참고 항목

참고문헌

  1. ^ 이 기간은 다음과 같습니다. Turner, D.A. (December 1995). Elementary Strong Functional Programming. First International Symposium on Functional Programming Languages in Education. Springer LNCS. Vol. 1022. pp. 1–13..
  2. ^ a b Turner, D.A. (2004-07-28), "Total Functional Programming", Journal of Universal Computer Science, 10 (7): 751–768, doi:10.3217/jucs-010-07-0751
  3. ^ Turner, D. A. (2000-04-28), "Ensuring Termination in ESFP", Journal of Universal Computer Science, 6 (4): 474–488, doi:10.3217/jucs-006-04-0474
  4. ^ 게으른 평가와 열정적인 평가의 차이점은 다음에서 설명합니다. 특히 pp를 참조하십시오. 86–91.
  5. ^ Granström, J. G. (May 2012), "A New Paradigm for Component-based Development", Journal of Software, 7 (5): 1136–1148, doi:10.4304/jsw.7.5.1136-1148[데드링크] 보관된 복사본