Prolog Language
데이터 추론

비고

재귀

프롤로그에는 반복이 없지만 모든 반복은 재귀를 사용하여 다시 작성할 수 있습니다. 재귀는 술어가 자신을 참조하는 목표를 포함 할 때 나타납니다. Prolog에 이러한 술어를 작성할 때 표준 재귀 패턴은 항상 최소한 두 부분으로 이루어집니다.

• 기본 (비 재귀) 절 : 일반적으로 기본 사례 규칙은 해결하려는 문제의 가장 작은 가능한 예를 나타냅니다. 구성원이 없거나 한 구성원 만있는 목록이거나 트리 구조로 작업하면, 빈 트리 또는 하나의 노드 만있는 트리 등을 처리 할 수 ​​있습니다. 재귀 적으로 비 반복적으로 프로세스의 기본을 설명합니다.

• 재귀 (계속) 절 : 반복 호출을 포함하여 필요한 모든 논리를 포함합니다.

예를 들어 잘 알려진 술어 append/3 정의합니다. 선언적으로 보면, 목록 L3 이 목록 L1 과 L2 를 추가 한 결과 인 경우 append(L1,L2,L3) 유지됩니다. 술어의 선언적 의미를 파악하려고 할 때, 술어가 가지고있는 해를 설명하려고합니다. 여기에서의 어려움은 술어가 보여야하는 절차 적 행동을 명심하면서 단계적 반복 세부 사항을 피하려고 노력하는 데있다.

% Base case
append([],L,L).

% Recursive clause
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

기본 경우는 선언적으로 "빈 목록에 추가 된 모든 L은 L"입니다. L이 비어 있거나 목록이되는 것에 대해 아무 것도 말하지 않습니다 (Prolog에서 모든 것은 용어로 요약됩니다).

?- append(X,some_term(a,b),Z).
X = [],
Z = some_term(a, b).

재귀 규칙을 설명 할 때 Prolog는 왼쪽에서 오른쪽으로 규칙을 실행하지만 머리를 생략하고 처음부터 몸통을 봅니다. 오른쪽에서 왼쪽으로 규칙을 읽습니다.

    append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

이제 우리는 몸체가 다음과 같이 말한다면 : " append(L1,L2,L3) 이 append(L1,L2,L3) 고 가정하면"

    append([X|L1],L2,[X|L3]) :-  append(L1,L2,L3). 

그러면 헤드도 마찬가지입니다 : "그러면 append([X|L1],L2,[X|L3])

보통 영어로 이것은 간단하게 번역됩니다 :

L3이 L1과 L2의 연결이라고 가정하면 [X 다음에 L3]은 [X 다음에 L1이]와 L2가 연결됩니다.

실용적인 예를 들면 다음과 같습니다.

[1,2,3]을 [1]과 [2,3]의 연결이라고 가정하면 [a, 1,2,3]은 또한 [a, 1]과 [2,3]의 연결입니다. "

이제 몇 가지 쿼리를 살펴 보겠습니다.

특정 시나리오 테스트 케이스를 제공하지 않고 가장 일반적인 쿼리로 귀하의 조건자를 초기에 테스트하는 것이 항상 좋은 생각입니다. Prolog의 통일 때문에 우리는 테스트 데이터를 제공 할 필요가 없습니다. 우리는 단지 그것을 자유 변수로 넘깁니다!

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_G1162],
L3 = [_G1162|L2] ;                          % Answer #2
L1 = [_G1162, _G1168],
L3 = [_G1162, _G1168|L2] ;                  % Answer #3
L1 = [_G1162, _G1168, _G1174],
L3 = [_G1162, _G1168, _G1174|L2] ;          % Answer #4
...

더 나은 개요를 얻으려면 알파벳 변수로 무료 변수 _G1162 와 같은 표기법을 대체하십시오.

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_A],
L3 = [_A|L2] ;                              % Answer #2
L1 = [_A, _B],
L3 = [_A, _B|L2] ;                          % Answer #3
L1 = [_A, _B, _C],
L3 = [_A, _B, _C|L2] ;                      % Answer #4
...

첫 번째 대답에서 기본 사례는 패턴 일치이며 Prolog는 L1 을 빈 목록에 인스턴스화하고 L3 이 빈 목록과 L2의 연결임을 증명하는 통합 된 L2 및 L3 을 작성했습니다.

반복적 인 역 추적을 통한 응답 # 2에서 재귀 절이 나타나고 Prolog는 L1 헤드의 일부 요소가 L2 와 연결된 L3 인지 확인하려고 시도합니다. 그렇게하기 위해 새로운 자유 변수 _A 가 L1의 머리와 통합되고 L3은 [_A|L2] 증명됩니다.

새로운 재귀 호출이 만들어졌으며 이제는 L1 = [_A] 입니다. 한 번 더, 프롤로그는 L1 의 머리에있는 어떤 요소가 L2 와 연결된 그 요소가 머리에있는 L3 임을 증명하려고합니다. _A 가 이미 규칙과 완벽하게 일치하는 L1 의 머리 부분이므로 Prolog는 재귀를 통해 _A 를 새로운 자유 변수 앞에두고 L1 = [_A,_B] 및 L3 = [_A,_B|L2]

우리는 명확하게 재귀 패턴이 반복되는 것을 보았습니다. 예를 들어 재귀에서 100 번째 단계의 결과는 다음과 같이 보일 것입니다.

L1 = [X1,X2,..,X99],
L3 = [X1,X2,..,X99|L2]

참고 : 좋은 Prolog 코드에서 일반적인 것처럼 append/3 의 재귀 적 정의는 목록이 다른 두 목록의 연결인지 여부를 확인할 수있을뿐만 아니라 모든 논리적 관계를 만족시키는 모든 가능한 대답을 생성 합니다 또는 부분적으로 인스턴스화 된 목록.

목록 액세스

회원

member/2 는 서명 member(?Elem, ?List) 가지며, Elem 이 List 의 멤버 true 나타낸다. 이 술어는 목록에서 변수를 액세스하는 데 사용할 수 있습니다. 여기서 다른 솔루션은 역 추적을 통해 검색됩니다.

검색어 예 :

?- member(X, [1,2,3]).
X = 1 ;
X = 2 ;
X = 3.

?- member(X,[Y]).
X = Y.

?- member(X,Y).
Y = [X|_G969] ;
Y = [_G968, X|_G972] ;
Y = [_G968, _G971, X|_G975] ;
Y = [_G968, _G971, _G974, X|_G978]
...

패턴 매칭

액세스해야하는 색인이 작을 때 패턴 일치가 좋은 해결책이 될 수 있습니다. 예 :

third([_,_,X|_], X).
fourth([_,_,_,X|_], X).