커리 (프로그래밍 언어)

**커리**(Curry)는 함수형 논리 프로그래밍 패러다임을 구현한 선언형 프로그래밍 언어이며, 하스켈 언어를 기반으로 한다. 커리는 함수형 및 논리 프로그래밍의 요소들을 병합하며, 여기에는 제약 프로그래밍의 통합이 포함된다.

커리는 거의 하스켈의 상위 집합에 가깝지만, 하스켈의 모든 언어 확장을 지원하지는 않는다. 하스켈과 대조적으로 커리는 탐색을 포함하는 비결정적 계산을 기본적으로 지원한다.

## 함수형 논리 프로그래밍의 기초

### 기본 개념
함수형 프로그램은 등식이나 규칙으로 정의된 함수들의 집합이다. 함수형 계산은 더 이상 교체(또는 축약)가 불가능하여 값이나 정규형(normal form)을 얻을 때까지 하위 식을 (함수 정의와 관련하여) 동일한 하위 식으로 교체하는 것으로 구성된다. 예를 들어, 다음과 같이 정의된 함수 double을 고려해 보자.

 double x = x+x

식 “”은 로 교체된다. 연산자 “”가 무한한 등식 집합(예: ,  등)으로 정의된다고 해석하면 후자는 로 교체될 수 있다. 비슷한 방식으로 중첩된 식을 평가할 수 있다(교체될 하위 식은 따옴표로 표시함).

 '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

이 경우 두 유도 과정은 동일한 결과에 도달하며, 이러한 성질을 합류성(confluence)이라고 한다. 이는 순수 함수형 언어의 근본적인 속성인 참조 투명성에서 기인한다. 즉, 부작용이 없기 때문에 계산된 결과의 값은 평가 순서나 시간에 의존하지 않는다. 이는 순수 함수형 프로그램을 추론하고 유지 관리하는 것을 단순하게 만든다.

하스켈과 같은 많은 함수형 언어와 마찬가지로, 커리는 생성자를 나열하여 대수적 자료형을 정의하는 것을 지원한다. 예를 들어, 불리언 값의 타입은 다음과 같이 선언된 와  생성자로 구성된다.

```haskell
data Bool = True | False
```

불리언 함수는 패턴 매칭을 통해 정의될 수 있다. 즉, 서로 다른 인수 값에 대해 여러 등식을 제공한다.

```haskell
not True = False
 not False = True
```

동일한 것을 동일한 것으로 교체하는 원칙은 실제 인수가 요구되는 형태를 갖춘 경우 여전히 유효하다. 예:

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

더 복잡한 자료 구조는 재귀 자료형을 통해 얻을 수 있다. 예를 들어, 요소의 타입이 임의적인(타입 변수 로 표시됨) 요소 리스트는 빈 리스트 “”이거나, 첫 번째 요소 와 리스트 로 구성된 비어 있지 않은 리스트 “”이다.

```haskell
data List a = [] | a : List a
```

타입 “”는 보통 로 쓰이며, 유한 리스트 x1x2...xn은 x1x2...xn으로 쓰인다. 패턴 매칭이 서로 다른 사례를 편리하게 분리해 주는 귀납적 정의를 통해 재귀 자료형에 대한 연산을 정의할 수 있다. 예를 들어, 다형성 리스트에 대한 연결 연산 “”는 다음과 같이 정의할 수 있다(첫 번째 줄의 선택적 타입 선언은 “”가 두 개의 리스트를 입력으로 받아 하나의 출력 리스트를 생성하며, 모든 리스트 요소는 동일한 지정되지 않은 타입임을 명시한다).

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

다양한 프로그래밍 작업에 적용되는 것 외에도, “” 연산은 리스트에 대한 다른 함수의 동작을 지정하는 데에도 유용하다. 예를 들어 리스트의 마지막 요소를 반환하는 함수 last의 동작은 다음과 같이 지정할 수 있다. 모든 리스트 xs와 요소 e에 대해, ∃ysyse = xs이면  xs = e이다.

이 명세를 바탕으로 논리 프로그래밍 기능을 사용하여 이 명세를 충족하는 함수를 정의할 수 있다. 논리 언어와 유사하게, 함수형 논리 언어는 존재 기호가 붙은 변수에 대한 해답 탐색을 제공한다. 순수 논리 언어와 대조적으로, 이들은 중첩된 함수 식에 대한 방정식 풀이를 지원하므로 yse = 과 같은 방정식은 ys를 리스트 로, e를 값 으로 인스턴스화하여 풀 수 있다. 커리에서 last 연산은 다음과 같이 정의할 수 있다.

```haskell
last xs | ys++[e] =:= xs = e where ys,e free
```

여기서 “” 기호는 정의 등식과 구문적으로 구별하기 위해 등식 제약 조건에 사용된다. 마찬가지로, 오타로 인한 버그를 탐지할 기회를 제공하기 위해 추가 변수(즉, 정의 등식의 왼쪽에 나타나지 않는 변수)는 “”를 통해 명시적으로 선언된다. l  c  r 형태의 조건부 등식은 조건 c가 해결된 경우 축약에 적용 가능하다. 조건이 불리언 값으로만 평가되는 순수 함수형 언어와 달리, 함수형 논리 언어는 조건 내의 미지수 값을 추측하여 조건을 해결하는 것을 지원한다. 다음 섹션에서 설명하는 내로잉(Narrowing)이 이러한 종류의 조건을 해결하는 데 사용된다.

### 내로잉
내로잉(Narrowing)은 제약 조건에 의해 부과된 대안들 중에서 선택된 값에 변수를 바인딩하는 메커니즘이다. 가능한 각 값을 순서대로 시도하며, 각 경우에 프로그램의 나머지 부분을 호출하여 바인딩의 유효성을 결정한다. 내로잉은 유사한 탐색을 수행한다는 점에서 논리 프로그래밍의 확장이라 볼 수 있지만, 단순히 값을 테스트하는 데 그치지 않고 탐색의 일부로 실제로 값을 생성할 수 있다.

내로잉은 함수를 관계(relation)로 취급할 수 있게 해주기 때문에 유용하다. 즉, 함수의 값을 "양방향"으로 계산할 수 있다. 이전 섹션의 커리 예제가 이를 잘 보여준다.

이전 섹션에서 언급했듯이 내로잉은 프로그램 항 그래프(term graph)에 대한 축약으로 생각할 수 있으며, 주어진 항 그래프를 축약하는 방법(전략)은 종종 여러 가지가 존재한다. 세르히오 안토이(Sergio Antoy) 등은 1990년대에 특정 내로잉 전략인 '필요 내로잉(needed narrowing)'이 타당하고 완전한 전략들 중에서 최소인 해에 해당하는 "정규형"에 도달하기 위한 축약 횟수 측면에서 최적임을 증명했다. 필요 내로잉은 프롤로그의 SLD 해결 전략과 대조적으로 지연 전략에 해당한다.

### 함수형 패턴
위에서 보여준 를 정의하는 규칙은 실제 인수가  식을 내로잉한 결과와 일치해야 한다는 사실을 표현한다. 커리는 이 속성을 다음과 같이 더 간결한 방식으로 표현할 수 있다.

```haskell
last (ys++[e]) = e
```

하스켈은 왼쪽 패턴에 정의된 함수()가 포함되어 있기 때문에 이러한 선언을 허용하지 않는다. 이러한 패턴을 함수형 패턴(functional pattern)이라고도 한다. 함수형 패턴은 커리의 결합된 함수 및 논리 기능에 의해 활성화되며, 계층적 자료 구조에서 깊은 패턴 매칭이 필요한 작업의 간결한 정의를 지원한다.

### 비결정론
커리는 알 수 없는 값을 가진 함수 호출을 포함하는 방정식을 풀 수 있기 때문에, 그 실행 메커니즘은 논리 프로그래밍과 유사하게 비결정적 계산을 기반으로 한다. 이 메커니즘은 비결정적 연산, 즉 주어진 입력에 대해 하나 이상의 결과를 제공하는 연산의 정의도 지원한다. 비결정적 연산의 원형은 인수 중 하나를 반환하는 로 불리는 사전 정의된 중위 연산자(선택 연산자)이다. 이 연산자는 다음 규칙에 의해 정의된다.

  x ? y = x
  x ? y = y

따라서 식 의 평가는 과 을 모두 반환한다. 비결정적 연산을 사용한 계산과 내로잉을 통한 자유 변수 계산은 동일한 표현력을 갖는다.

를 정의하는 규칙은 커리의 중요한 특징을 보여준다. 어떤 연산을 평가하기 위해 모든 규칙이 시도된다는 것이다. 따라서 다음과 같이 정의하면

```haskell
insert x ys     = x : ys
 insert x (y:ys) = y : insert x ys
```

요소를 리스트의 정해지지 않은 위치에 삽입하는 연산이 되며, 다음과 같이 정의된 연산 은

```haskell
perm []     = []
 perm (x:xs) = insert x (perm xs)
```

주어진 입력 리스트의 임의의 순열을 반환한다.

### 전략
부작용이 없기 때문에 함수형 논리 프로그램은 다양한 전략으로 실행될 수 있다. 식을 평가하기 위해 커리는 느긋한 계산법과 비결정적 탐색 전략을 결합한 필요 내로잉 전략의 변형을 사용한다. 해를 찾기 위해 백트래킹을 사용하는 프롤로그와 달리, 커리는 특정 탐색 전략을 고정하지 않는다. 따라서 KiCS2와 같은 커리 구현체에서는 사용자가 깊이 우선 탐색(백트래킹), 너비 우선 탐색, 반복적 심화 탐색 또는 병렬 탐색과 같은 탐색 전략을 쉽게 선택할 수 있다.

## 구현체 및 프로그래밍 도구
다양한 커리 구현체를 사용할 수 있다. 가장 유명한 대표 사례로는 커리 프로그램을 프롤로그로 컴파일하는 포틀랜드 아헨 킬 커리 시스템(Portland Aachen Kiel Curry System) PAKCS, 커리 프로그램을 하스켈로 컴파일하는 킬 커리 시스템(Kiel Curry System) KiCS2, 뮌스터 커리 컴파일러(Münster Curry Compiler) MCC, 그리고 커리 프로그램을 Go 프로그램으로 컴파일하고 비결정적 평가를 경량 프로세스(고루틴)로 매핑하여 공정한 병렬 탐색을 지원하는 Curry2Go가 있다.

커리 프로그래밍을 지원하기 위해 커리 소프트웨어 패키지 모음, 커리 API 검색 엔진, 비주얼 스튜디오 코드 등에서 IDE 지원을 제공하는 커리 언어 서버, 그리고 다양한 프로그램 문서화 및 분석 도구가 있다.

## 논의 및 추가 읽을거리
존 앨런 로빈슨은 그의 초대 CL2000 논문에서 함수형 프로그래밍과 논리 프로그래밍의 통합에 대해 논의하며 다음과 같이 썼다. "두 관용구가 계산 논리 목록 내에서 그렇게 오랫동안 떨어져 있었다는 것은 설명하기 어렵다. 두 종류의 프로그래밍이 모두 가능하고 서로 조합하여 사용할 수 있는 단일 프로그래밍 언어가 필요하다." 그는 여러 시도를 조사하고 커리가 "가장 유망한 것"이라고 결론지었다.

프로그래밍 언어의 원리와 실습에 관한 교과서에는 커리 프로그래밍에 관한 장이 포함되어 있다.

## 각주

## 외부 링크
* 
* Smap - 다양한 예제 프로그램이 포함된 웹 기반 커리 및 하스켈 실행 환경
* Curry packages - 커리용 소프트웨어 패키지 모음
* MCC - 뮌스터 커리 컴파일러, C를 타겟으로 함
* PAKCS - 주요 커리 구현체, 프롤로그를 타겟으로 함
* KiCS2 - 커리 구현체, 하스켈을 타겟으로 함
* Curry2Go - 커리 구현체, Go를 타겟으로 하며 공정한 병렬 탐색 지원
* GitHub 저장소 - 커리 구현체 및 도구 포함
* Curry Mailing List
* 미하엘 하누스(Michael Hanus)의 홈페이지
* Purely Functional Lazy Non-deterministic Programming (Fischer, Kiselyov, Shan, 2009), Transforming Functional Logic Programs into Monadic Functional Programs (Braßel, Fischer, Hanus, Reck, 2010): 순수 함수형 언어(하스켈)에서 지연 비결정적(논리) 프로그래밍(커리와 같은)을 모델링하는 것에 관하여. 이러한 접근 방식은 프로그래머에게 (커리의 경우 내장된) 전략에 대한 제어에 더 많은 유연성을 제공할 수 있다.

분류:병행 프로그래밍 언어
분류:하스켈 프로그래밍 언어 계열
분류:1995년 개발된 프로그래밍 언어
분류:정적 타입 프로그래밍 언어
분류:고급 프로그래밍 언어
분류:문학적 프로그래밍
분류:BSD 라이선스 소프트웨어