카레(프로그래밍 언어)

Curry (programming language)
이 기사는 프로그래밍 언어 Curry(수학자와 논리학자의 이름을 딴)에 관한 것입니다.수학자와 논리학자는 하스켈 커리를 참조하십시오.컴퓨터 공학 기술에 대해서는 Currying을 참조하십시오.
카레시
패러다임기능, 로직, 비표준, 모듈러
설계자마이클 하누스, 세르지오 안토이 등
타이핑 분야정적, 강력, 추론
OS휴대할 수 있다
웹 사이트카레시
주요 구현
PAKCS(프롤로그를 타깃으로 함), mcc(C를 타깃으로 함), KiCS2(Haskell을 타깃으로 함)
영향을 받다
하스켈과 프롤로그

Curry는[1] Haskell 언어를 기반으로 하는 실험적인 함수 로직 프로그래밍 [2]언어입니다.제약조건 프로그래밍 통합을 포함한 기능 프로그래밍 요소와 논리 프로그래밍 [3]요소를 병합합니다.

이것은 Haskell의 거의 슈퍼셋으로, Munnster Curry [4]컴파일러와 같은 일부 구현에서 언어 확장으로 제공하는 유형 클래스를 사용하는 오버로드에 대한 지원이 부족합니다.

기능 로직 프로그래밍의 기초

기본 개념

함수 프로그램은 방정식 또는 규칙에 의해 정의된 함수 집합입니다.함수 계산은 더 이상의 치환(또는 감소)이 불가능하고 값 또는 정규 형태를 얻을 때까지 (함수 정의에 관해) 동일한 서브식으로 치환하는 것으로 구성됩니다.예를 들어, 함수는 다음에 의해 이중으로 정의됩니다.

이중 x = x+x

"라는 표현은double 1"은 1+1로 대체됩니다.연산자 "+"를 무한 방정식 집합(예: 1+1 = 2, 1+2 = 3 등)으로 정의하도록 해석하면 후자는 2로 대체될 수 있다.비슷한 방법으로 중첩된 표현식(바꿀 하위 표현식이 따옴표로 묶인 부분 표현식)을 평가할 수 있습니다. 

'double (1+2)' → '(1+2)'+(1+2) → 3+'(1+2) → '3+3' → 6

연산자의 인수를 오른쪽에서 왼쪽으로 바꾸는 경우에도 평가 순서가 있습니다.

'double (1+2)' → (1+2)+'(1+2)' → '(1+2)+3' → '3+3' → 6

이 경우, 두 파생물은 동일한 결과, 즉 합류로 알려진 속성으로 이어집니다.이는 참조 투명성이라고 불리는 순수 기능 언어의 기본 속성에서 비롯된다. 즉, 부작용이 없기 때문에 계산된 결과의 값은 평가 순서나 시간에 의존하지 않는다.이를 통해 순수 기능 프로그램에 대한 추론 및 유지보수가 단순해집니다.

Haskell과 같은 많은 함수 언어가 그렇듯이 Curry는 생성자를 열거함으로써 대수 데이터 유형의 정의를 지원합니다.예를 들어 부울 값의 유형은 다음과 같이 선언된 생성자 True 및 False로 구성됩니다.

 데이터. 불 = 진실의   거짓의

Boulans의 함수는 패턴 매칭에 의해 정의될 수 있습니다. 즉, 다른 인수 값에 대한 여러 방정식을 제공합니다.

 것은 아니다. 진실의 = 거짓의  것은 아니다. 거짓의 = 진실의

equals를 equals로 치환하는 원칙은 실제 인수가 다음과 같은 필수 형식을 가질 경우 여전히 유효합니다. 

not '(not False)' → 'not True' → False

더 복잡한 데이터 구조는 재귀 데이터 유형을 통해 얻을 수 있습니다.예를 들어 요소 유형이 임의인 요소 목록은 비어 있는 목록 "[]" 또는 비어 있지 않은 목록 "x:xs"로 첫 번째 요소 x와 목록 xs로 구성됩니다.

 데이터. 목록. a = []   a : 목록. a

"List a" 유형은 보통 [a]로 쓰이고 유한 목록 x1:x2:...xn:[]은 [x1,x2,...xn]로 쓰입니다.우리는 패턴 매칭이 다른 사례의 편리한 분리를 지원하는 귀납적 정의에 의해 재귀적 유형에 대한 연산을 정의할 수 있다.예를 들어, 다형 목록에서의 연결 연산 "+"는 다음과 같이 정의할 수 있습니다(첫 번째 줄의 옵션 유형 선언은 "+"가 2개의 목록을 입력으로 받아 출력 목록을 생성하도록 지정합니다.여기서 모든 목록 요소는 동일한 미지정 유형입니다). 

 (++) :: [a] -> [a] -> [a]   [] ++ ys = ys   (x:xs) ++ ys = x : xs++ys

다양한 프로그래밍 태스크에 적용할 뿐만 아니라, "+" 연산은 목록에 있는 다른 함수의 동작을 지정하는데도 유용합니다.예를 들어 목록의 마지막 요소를 생성하는 함수의 동작을 다음과 같이 지정할 수 있습니다. 모든 목록 xs 및 요소 e에 대해 마지막 xs = e(ys:ys++[e] = xs이면 마지막 xs = e).

이 사양에 근거해, 로직 프로그래밍 기능을 이용하는 것으로, 이 사양을 만족시키는 함수를 정의할 수 있다.논리언어와 마찬가지로 함수논리언어는 기존 수량화된 변수에 대한 솔루션을 검색합니다.순수 논리 언어와 달리, 이들은 ys를 목록 [1,2]에 인스턴스화하고 e를 값 3에 인스턴스화함으로써 ys++[e] = [1,2,3]과 같은 방정식을 풀 수 있도록 중첩된 함수식에 대한 방정식 해법을 지원한다.Curry(커리)에서는 다음과 같이 마지막 작업을 정의할 수 있습니다.

 지난 xs   ys++[e] =:= xs = e 어디에 ys,e 공짜

여기서 기호 "=:="는 정의 방정식과의 구문적 구별을 제공하기 위해 등식 제약에 사용된다.마찬가지로, 추가 변수(즉, 정의 방정식의 왼쪽에서 발생하지 않는 변수)는 "여기서..."로 명시적으로 선언된다."free"를 클릭하면 오타로 인한 버그를 검출할 수 있습니다.l c = r 형식의 조건부 방정식은 조건 c가 해결된 경우 저감에 적용할 수 있다.조건이 부울값으로만 평가되는 순수 기능적 언어와는 대조적으로 기능적 논리언어는 조건 내의 미지의 값을 추측함으로써 조건의 해결을 지원한다.다음 절에서 설명하는 바와 같이 좁혀지는 것은 이러한 상황을 해결하기 위해 사용됩니다.

좁히다

좁혀지는 것은 변수가 제약에 의해 부과된 대안 중에서 선택된 값에 결합되는 메커니즘이다.가능한 각 값은 일정한 순서로 시행되며, 나머지 프로그램은 각각의 경우에 호출되어 바인딩의 유효성을 판단합니다.좁힘은 논리 프로그래밍의 확장으로, 유사한 검색을 수행하지만 단순히 테스트에 국한되지 않고 검색의 일부로 값을 생성할 수 있습니다.

좁힘은 함수를 관계로서 취급할 수 있도록 하기 때문에 유용합니다.그 값은 "양방향"으로 계산될 수 있습니다.이전 섹션의 Curry 예는 이를 보여줍니다.

이전 섹션에서 설명한 바와 같이, 좁혀지는 것은 프로그램 용어 그래프의 축소라고 생각할 수 있으며, 대부분의 경우 주어진 용어 그래프를 줄이는 다양한 방법(전략)이 있습니다.Antoy [5]et al.는 1990년대에 견고하고 완전한 전략 중 최소한의 해결책에 대응하는 "정상적인 형태"에 도달하기 위해 여러 가지 감소를 하는 의미에서 좁혀야 하는 특정 좁힘 전략이 최적이라는 것을 증명했다.필요한 범위를 좁히는 것은 프롤로그의 SLD 해결 전략과는 대조적으로 게으른 전략에 해당합니다.

기능 패턴

위의 마지막을 정의하는 규칙은 실제 인수가 ys++[e] 식의 범위를 좁힌 결과와 일치해야 한다는 사실을 나타냅니다.카레는 이 특성을 다음과 같이 간결하게 표현할 수 있습니다.

 지난 (ys++[e]) = e

왼쪽 패턴에 정의된 함수(+)가 포함되어 있기 때문에 Haskell은 이러한 선언을 허용하지 않습니다.이러한 패턴을 기능 [6]패턴이라고도 합니다.기능 패턴은 Curry의 기능적 특징과 로직적 특징을 조합하여 구현되며 계층적 데이터 구조에서 심층적인 패턴 매칭이 필요한 작업에 대한 간결한 정의를 지원합니다.

비결정론

Curry는 값을 알 수 없는 함수 호출을 포함하는 방정식을 풀 수 있기 때문에 논리 프로그래밍과 마찬가지로 비결정론적 연산을 기반으로 합니다.이 메커니즘은 비결정적 연산, 즉 특정 입력에 대해 둘 이상의 결과를 제공하는 연산의 정의도 지원합니다.비결정론적 연산의 원형은 선택 연산자라고 불리는 사전 정의된 infix 연산자이며, 인수 중 하나를 반환합니다.이 연산자는 다음 규칙에 의해 정의됩니다.

x ? y = x ? y = y

따라서 식 0 ?1의 평가는 1과 마찬가지로 0을 반환합니다.비결정적인 연산을 사용하는 컴퓨팅과 범위를 좁힘으로써 자유변수를 사용하는 컴퓨팅은 동일한 [7]표현력을 가집니다.

?을 정의하는 규칙은 Curry의 중요한 기능을 보여줍니다. 모든 규칙은 일부 작업을 평가하기 위해 시도됩니다.따라서 다음과 같이 정의할 수 있습니다.

 삽입하다 x ys     = x : ys  삽입하다 x (y:ys) = y : 삽입하다 x ys

에 의해 정의된 조작이 가능하게 하기 위해 요소를 불확정 위치에 있는 리스트에 삽입하는 조작

 파마 []     = []  파마 (x:xs) = 삽입하다 x (파마 xs)

지정된 입력 목록의 순열을 반환합니다.

전략들

부작용이 없기 때문에 다른 전략으로 기능 로직 프로그램을 실행할 수 있습니다.표현을 평가하기 위해 Curry는 게으른 평가와 비결정론적 검색 전략을 결합한 필요한 좁힘 전략의 변형을 사용합니다.백트래킹을 사용하여 솔루션을 검색하는 프롤로그와 달리 Curry는 특정 검색 전략을 수정하지 않습니다.따라서 사용자가 깊이 우선 검색(백트랙), 폭 우선 검색, 반복 심화 또는 병렬 검색과 같은 검색 전략을 쉽게 선택할 수 있는 KiCS2와 같은 Curry 구현이 있습니다.

레퍼런스

  1. ^ Michael Hanus (ed.). "Curry: A Truly Integrated Functional Logic Language".
  2. ^ Sergio Antoy and Michael Hanus (2010). "Functional Logic Programming". Communications of the ACM. ACM. 53 (4): 74–85. doi:10.1145/1721654.1721675. S2CID 14578759.
  3. ^ "Curry experimental programming language". MVPS.net. Retrieved 2 September 2021.
  4. ^ 먼스터 카레 컴파일러
  5. ^ Sergio Antoy, Rachid Echahed and Michael Hanus (2007). "A Needed Narrowing Strategy". Journal of the ACM. ACM. 47 (4): 776–822. doi:10.1145/347476.347484. ISSN 0004-5411. S2CID 47275506.
  6. ^ Antoy Sergio, Hanus Michael (2006). "Declarative Programming with Function Patterns". Lecture Notes in Computer Science. 3901: 6–22. doi:10.1007/11680093_2. ISBN 978-3-540-32654-0.
  7. ^ Antoy Sergio, Hanus Michael (2006). "Overlapping Rules and Logic Variables in Functional Logic Programs". Lecture Notes in Computer Science. 4079: 87–101. doi:10.1007/11799573_9. ISBN 978-3-540-36635-5.

외부 링크