아주 좋은 답변이 있습니다. 나는 토론에 기여하려고 노력할 것이다.

Prolog의 선언적, 논리 프로그래밍 주제 에 대해 Richard O’Keefe의 “The Craft of Prolog”라는 저서가 있습니다. 매우 비효율적 인 프로그램을 작성할 수있는 프로그래밍 언어를 사용하여 효율적인 프로그램을 작성하는 것입니다. 이 책에서 저자는 여러 알고리즘의 효율적인 구현 ( “프로그래밍 방법”장에서)을 논의하면서 다음과 같은 접근법을 취합니다.

• 영어로 문제를 정의하다
• 가능한 한 선언적인 작업 솔루션을 작성하십시오. 일반적으로, 그것은 당신이 당신의 질문에 가지고있는 것을 거의 정확하게 의미합니다.
• 거기에서 구현을 개선하여 더 빠르게 구현하십시오.

이 작업을 수행하는 동안 내가 할 수있는 가장 깨달은 (나를 위해) 관찰 :

예, 구현의 최종 버전은 저자가 시작한 “선언적”사양보다 훨씬 효율적입니다. 여전히 매우 선언적이고 간결하며 이해하기 쉽습니다. 그 사이에 일어난 일은 최종 솔루션이 초기 솔루션이 잊어 버린 문제의 속성을 캡처한다는 것입니다.

다시 말해, 솔루션을 구현하는 동안 가능한 한 문제에 대한 많은 지식을 사용했습니다. 비교:

모든 요소가 오름차순으로되도록 목록의 순열을 찾습니다.

에:

정렬 된 목록 두 개를 병합하면 정렬 된 목록이됩니다. 이미 정렬 된 하위 목록이있을 수 있으므로 길이가 1 인 하위 목록 대신 시작 지점으로 사용하십시오.

작은 것을 제외하고 : 당신이 제공 한 것과 같은 정의는 매우 일반적이기 때문에 매력적입니다. 그러나 순열이 조합 문제라는 사실을 의도적으로 무시한다는 느낌을 피할 수는 없습니다. 이것은 우리가 이미 알고있는 것입니다 ! 이것은 비판이 아니라 관찰 일뿐입니다.

실제 질문에 관해서 : 앞으로 나아가는 방법? 글쎄, 한 가지 방법은 우리가 컴퓨터에 선언하는 문제에 대해 많은 지식을 제공하는 것입니다.

내가 실제로 문제를 해결하기 위해 알고있는 최선의 방법은 Alexander Stepanov가 공동으로 저술 한 책인 “Programs of Programming” 과 “Mathematics에서 Generic Programming”에 나와 있습니다. 슬프게도이 책의 모든 내용을 요약 (또는 완전히 이해)하는 일은 아닙니다. 그러나 입력의 모든 관련 속성을 미리 알고 있다는 조건 하에서 효율적인 (또는 최적의) 라이브러리 알고리즘 및 데이터 구조를 정의하는 방법이 있습니다. 최종 결과는 다음과 같습니다.

• 잘 정의 된 각 변환은 이미 적용된 제약 조건 (알려진 속성)을 개선 한 것입니다.
• 우리는 컴퓨터가 기존의 제약 조건에 따라 최적의 변환을 결정하도록합니다.

왜 아직 일어나지 않았는 지에 관해서는, 컴퓨터 과학은 정말 어린 분야이며, 우리는 여전히 대부분의 참신함을 진정으로 이해하고 있습니다.

추신

“구현을 구체화”함으로써 내가 의미하는 바를 맛 보려면 : Prolog에서 목록의 마지막 요소를 얻는 쉬운 문제를 예로 들어 보자. 정식 선언적 해결책은 다음과 같습니다.

last(List, Last) :-
    append(_, [Last], List).

여기에서 선언적 의미는 다음과 같습니다 append/3.

List1AndList2연결 List1과List2

두 번째 인수 이후에 append/3우리는 단 하나 개의 요소 목록을 가지고 있고, 첫 번째 인수는 무시 (밑줄), 우리 (목록의 전면 폐기 원래 목록의 분할 수있다 List1의 맥락에서를 append/3)과 요구가 뒷면 ( List2의 컨텍스트에서 append/3)은 실제로 하나의 요소 만있는 목록입니다. 따라서 마지막 요소입니다.

SWI-Prolog에 의해 제공되는 실제 구현은 , 그러나, 말한다 :

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

이것은 여전히 ​​훌륭하게 선언적입니다. 위에서 아래로 읽습니다.

목록의 마지막 요소는 하나 이상의 요소 목록에만 적합합니다. 꼬리 쌍과 목록 머리의 마지막 요소는 머리, 꼬리가 비었을 때 또는 비어 있지 않은 꼬리의 마지막입니다.

이 구현이 제공되는 이유 는 Prolog 의 실행 모델 과 관련된 실제 문제를 해결하기위한 것 입니다. 이상적으로는 사용되는 구현에 차이를 두지 않아야합니다. 마찬가지로 다음과 같이 말할 수 있습니다.

last(List, Last) :-
    reverse(List, [Last|_]).

리스트의 마지막 요소는 반전 된리스트의 첫 번째 요소입니다.

유익하고 선언적인 프롤로그에 대한 결론을 얻지 않으려면 스택 오버플 로의 프롤로그 태그 에서 몇 가지 질문과 답변을 살펴보십시오 .

---

답변