논리 프로그래밍 언어 : Robert W. Sebesta

이 장의 목적은 논리 프로그래밍의 개념과 Prolog 부분 집합의 간결한 기술을 포함하여 논리 프로그래밍 언어를 소개하는 것이다. 논리 프로그래밍 언어의 기초가 되는 술어 해석학 (Predicate calculus) 의 소개로 시작한다. 뒤이어 술어 해석학이 자동 정리 증명 시스템에서 사용될 수 있는 방법을 논의한다. 그 후에, 논리 프로그래밍의 전체적인 개관을 소개한다. 다음으로, 긴 절은 산술, 리스트 처리를 포함한 Prolog 프로그래밍의 기초와 프로그램을 디버깅하는 데 도움을 주고 Prolog 시스템이 동작하는 방법을 설명하는 데 사용되는 추적 도구의 사용을 소개한다. 마지막 두 절은 논리 언어로서 Prolog 의 문제점과 Prolog 가 사용되고 있는 응용 분야를 기술한다.

1. 서론

14 장은 명령형 언어에서 사용된 소프트웨어 개발 방법론과 매우 다른 함수 프로그래밍 패러다임을 논의했다. 이 장에서는 다른 프로그래밍 방법론을 기술한다. 이 경우에서 접근 방법은 프로그램을 기호 논리의 형식으로 표현하고 결과를 도출하는 논리적 추론 과정을 사용하는 것이다. 논리 프로그램은 절차적이라기보다는 선언적이다. 그것은 결과를 도출하기 위한 세부적인 절차가 아니라 원하는 결과의 명세가 서술된다는 것을 의미한다.

프로그래밍 언어로서 기호 논리의 형식을 사용하는 프로그래밍은 논리 프로그래밍 (logic Programming language) 또는 선언적 언어 (declarative language) 라 불린다. 우리는 논리 프로그래밍 언어를 기술하기 위해 Prolog 를 선택했다. 왜냐하면 Prolog 는 광범위하게 사용되는 유일한 언어이기 때문이다.

논리 프로그래밍 언어의 구문은 명령형 언어나 함수 언어의 구문과는 현저하게 다르다. 논리 프로그램의 의미는 명령형 언어 프로그램의 의미와 거의 닮지 않았다. 이런 관찰은 독자에게 논리 프로그래밍과 선언형 언어의 본질에 관해 호기심을 유발시킨다.

2. 술어 해석학

논리 프로그래밍을 논의하기 전에 기초인 형식 논리를 간단하게 조사하고자 한다. 이것이 이 책에서 형식논리에 처음 접하는 것은 아니다. 형식 논리는 3 장에서 서술한 공리 의미론 (axiomatic semantics) 에서 광범위하게 사용되었다.

명제 (proposition) 는 참이거나 거짓인 논리적 문장이라고 생각될 수 있다. 명제는 객체와 객체 상호간의 관계로 구성된다. 형식적으로 언급된 명제의 유효성이 검사되는 것을 허용할 목적으로, 형식 논리는 명제를 기술하기 위한 방법을 제공하기 위해 개발되었다.

기호 논리 (Symbolic logic) 는 형식 논리의 세 가지 기본 요구 - 명제 표현, 명제 사이의 관계 표현, 참이라고 추정되는 명제의 초기 집합 (initial set) 이다. 정리는 초기 집합으로부터 추론될 수 있는 부가적인 명제이다.

논리 프로그래밍을 위해 사용된 기호 논리의 특별한 형식을 술어 해석학 (predicate calculus) 이라 부른다. 다음부절에서, 우리는 술어 해석학을 간단히 소개한다. 우리의 목적은 논리 프로그래밍과 논리 프로그래밍 언어 Prolog 의 논의를 위한 기초를 준비하는 것이다.

(1) 명제

논리 프로그래밍 명제에서 객체는 상수나 변수인 단순한 항에 의해서 표현된다. 상수는 객체를 표현하는 기호이며, 변수는, 비록 어느 의미에서 명령형 프로그래밍 언어의 변수보다 수학에 좀더 가까울지라도, 각기 다른 시간에 다른 객체를 표현하는 기호이다.

기본 명제 (atomic propositions) 라 불리는 가장 간단한 명제는 복합 항으로 구성된다. 복합 항 (Compound term) 은 수학 관계의 원소이며, 수학 함수 기호의 모양을 갖는 형식으로 쓰여진다. 수학 함수는 표현식, 튜플의 테이블, 또는 튜플 리스트로 표현된 사상이라는 것을 14 장으로부터 상기하자. 그러므로 복합 항은 함수의 테이블 정의의 원소이다.

복합 항은 두 부분으로 구성된다. 관계를 명명하는 함수 기호인 작용자 (functor) 와 매개변수의 순서화 리스트이다. 단일 매개변수를 갖는 복합 항은 1-튜플이고, 두 개의 인자를 갖는 복합 항은 2-튜플이다. 같은 방법으로 계속된다. 예로 들면, 두 개의 명제

man (jake)
like (bob, steak)

이 있다고 하자. 여기서 {jake} 는 man 이라고 명명된 관계의 1-튜플이고, {bob, steak} 는 like 라고 명명된 관계의 2-튜플이다. 만약 우리가 명제

man (fred)

를 위의 두 명제에 첨가하면, 관계 man 은 두 개의 다른 원소인 {jake} 와 {fred} 를 갖는다. 이런 명제에서 모든 간단한 항 - man, jake, like, bob, 그리고 steak - 은 상수이다. 이런 명제는 본질적인 의미를 갖지 않음에 유의하라. 그것들은 우리가 의미하고자 하는 것을 나타낸다. 예로 들면, 위에서 두번째 예제는 bob 이 steak 를 좋아하거나, 또는 steak 가 bob 을 좋아하거나, bob 이 어떤 면에서 steak 와 비슷하다는 것을 의미한다.

명제는 두 가지 양식 (mode) 으로 나타낼 수 있다. 명제가 참으로 정의되는 양식과, 명제의 진리 값이 결정될 수 있는 양식이다. 다시 말하면, 명제는 사실이나 질의를 나타낸다. 위의 명제는 사실이나 질의일 수 있다.

복합 명제 (compound proposition) 는 복합 논리식이 명령형 언어에서 구성된 것과 동일한 방법으로 논리 연결자 즉 연산자에 의해 연결된 두 개 또는 그 이상의 기본 명제 (atom proposition) 를 가지고 있다. 술어 해석학의 논리적 연결자 (logical connector) 의 이름, 기호, 의미는 다음과 같다.

이름

기호

예제

의미

부정

논리곱

논리합

동등

함축

￢

∩

∪

≡

⊃

⊂

￢a

a ∩ b

a ∪ b

a ≡ b

a ⊃ b

a ⊂ b

a 가 아니다.

a 그리고 b

a 또는 b

a 는 b 와 동치이다.

a 는 b 를 포함한다.

b 는 a 를 포함한다.

다음은 복합 명제의 예제이다.

a ∩ b ⊃ c

a ∩ ￢b ⊃ d

연산자 ￢ 은 가장 높은 연산자 우선 순위를 갖는다. 연산 ∩, ∪ 과 ≡ 은 모두 ⊃ 과 ⊂ 보다 높은 연산자 우선 순위를 갖는다. 그래서 위의 두번째 예제는

(a ∩ (￢b)) ⊃ d

과 동치를 이룬다.

변수는 한정사 (quantifier) 라 불리는 특별한 기호에 의해 기술될 때만 명제에 나타난다. 술어 해석학은 다음에서 기술되는 두 개의 한정사를 포함하고 있다. 여기서 X 는 변수이고, P 는 명제이다.

이름

예제

의미

전칭 한정사

존재 한정사

∀X.P

∃X.P

모든 X 에 대하여 P 는 참이다.

P 가 참인 X 가 존재한다.

X 와 P 사이의 마침표 ( .) 는 명제에서 변수를 간단하게 분리한다. 예로, 다음을 생각해보자.

∀X. (woman (X) ⊃ human (X))
∃X. mother (mary, X) ∩ male (X))

첫번째 명제는 X 의 모든 값에 대해, 만약 X 가 여자면, X 는 사람이라는 것을 의미한다. 두번째 명제는 mary 는 X 의 어머니이고, X 는 남자인 X 의 값이 존재한다는 것을 의미한다. 다시 말하면, mary 에게는 아들이 있는 것이다. 전칭 (universal) 과 존재 (existential) 한정사의 영역은 한정사가 첨부된 기본 명제이다. 그런 영역은 방금 서술한 두 개의 명제처럼 괄호를 사용해서 확장된다. 그래서 전칭 한정사의 존재 한정사는 다른 연산자들보다 높은 연산자 우선 순위를 갖는다.

(2) 클로즈 형식

우리는 술어 해석학이 논리 프로그래밍 언어의 기초이기 때문에 술어 해석학을 논의하고 있다. 다른 언어와 마찬가지로, 논리 언어는 중복 (redundancy) 이 기초화된 것을 의미하는 제일 단순한 형식이 가장 좋다.

지금까지 서술한 술어 해석학의 문제는 동일한 의미를 갖는 명제를 표현하는 다른 방법이 너무 많다는 것이다. 즉 중복이 너무 많이 존재한다. 이것은 논리학자에게는 문제가 되지 않지만, 만약 술어 해석학이 자동화된 시스템에서 사용된다면, 그것은 심각한 문제이다. 문제를 단순화하기 위해 명제의 표준 형식이 바람직하다. 상대적으로 명제의 간단한 형식인 클로즈 형식 (clausal form) 은 표준 형식중의 하나이다. 일반성을 잃지 않고, 모든 명제는 클로즈 형식으로 표현될 수 있다. 클로즈 형식에서 명제는 아래와 같은 일반적인 구문을 갖는다.

여기서 A 와 B 는 항이다. 이런 클로즈 형식 명제의 의미는 다음과 같다. 만약 모든 A 가 참이면, 적어도 하나의 B 는 참이다. 클로즈 형식 명제의 기본적인 특성은 다음과 같다. 존재 한정사는 요구되지 않고, 전칭 한정사는 기본 명제의 변수 사용에서 묵시적이고, 논리곱 (conjunction) 과 논리합 (disjunction) 이외의 다른 연산자는 요구되지 않는다. 물론, 논리곱과 논리합은 일반적인 클로즈 형식에서 보여진 순서로 나타나는 것이 필요하다. 논리합은 왼쪽에 논리곱은 오른쪽에 위치한다. 모든 술어 해석학 명제는 알고리즘에 의해 클로즈 형식으로 변환된다. Nilsson (1971) 은 변환을 수행하기 위한 간단한 변환 알고리즘과 알고리즘이 제대로 수행된다는 것을 증명하였다.

클로즈 형식 명제의 우변을 전제 (antecedent) 라 부르며, 좌변은 전제 진리 값의 결과이기 때문에 결론 (consequent) 이라 불린다. 클로즈 형식 명제의 예제로서 다음을 생각해 보자.

likes (bob, trout) ⊂ likes (bob, fish) ∩ fish (trout)

father (louis, al) ∪ father (louis, violet) ⊂ father (al, bob) ∩ mother (violet, bob) ∩ grandfather (louis, bob)

첫번째 예제에는 만약 bob 이 fish 를 좋아하고, trout 가 fish 이면, bob 은 trout 을 좋아한다는 것을 나타낸다. 두번째 예제는 만약 al 이 bob 의 아버지이고 violet 이 bob 의 어머니이고 louis 가 bob 의 할아버지라면, louis 는 al 의 아버지이거나 violet 의 아버지이다를 나타낸다.

3. 술어 해석학과 정리 증명

술어 해석학은 명제의 집합을 표현하는 방법을 제공한다. 명제 집합의 사용은 어떤 흥미롭거나 유용한 사실이 명제 집합으로부터 추론될 수 있는지를 결정하는 것이다. 이것은 이미 알려진 정리나 공리로부터 추론될 수 있는 새로운 정리를 발견할려고 노력하는 수학자의 연구와 아주 유사하다.

컴퓨터 과학의 초기시대 (1950 년대 ~ 1960 년대 초) 에는 정리 증명 과정을 자동화하는 데 많은 흥미를 보였다. 자동 정리 증명에서 가장 중요한 돌파구는 Syracuse 대학의 Alan Robinson 에 의해 해 도출 원리 (resolution principle) 의 발견이다 (Robinson, 1965).

해 도출 (resolution) 은 추론된 명제가 주어진 명제로부터 계산되는 것을 허용하는 추론 규칙이다. 따라서 해도출은 자동 정리 증명에 적용 가능한 방법을 제공한다. 해 도출은 클로즈 형식의 명제에 적용하기 위해 고안되었다. 해도출의 개념은 다음과 같다. 다음과 같은 형식을 두 개의 명제가 있다고 가정하자.

이것은 가 을 포함하고, 가 을 포함하는 것을 의미한다. 더욱이 이 와 동일하다고 하면, 우리는 과 를 T 로 다시 쓸 수 있다고 가정하자. 그러면, 우리는 다음과 같이 두 개의 명제를 다시 쓸 수 있다.

이제, 가 T 를 포함하고, T 가 을 포함하기 때문에, 아래에 쓴 것처럼, 논리적으로 명백히 가 을 포함한다.

원래의 두 명제로부터 이 명제를 추론하는 방법이 해 도출이다.

다른 예로서, 다음 두 개의 명제를 생각해 보자.

older (joanne, jake) ⊂ mother (joanne, jake)

이 명제로부터, 다음의 명제가 해 도출을 사용해서 만들어질 수 있다.

wiser (joanne, jake) ⊂ mother (joanne, jake)

이런 해 도출의 구성 메카니즘은 간단하다. 두 명제의 좌변의 항은 새로운 명제의 좌변을 만들기 위해 함께 AND 연산을 한다. 그런후, 동일한 방법으로 새로운 명제의 우변을 만든다. 다음으로, 새로운 명제의 양변에 나타나는 항은 양변에서 제거된다. 명제가 다중 항을 한 변이나 양변에 갖더라도 그 과정은 동일하다. 새롭게 추론된 명제의 좌변은 처음에 주어진 두 명제의 좌변의 모든 항을 가지고 있다. 새로운 우변도 비슷한 방법으로 만들어진다. 그런후, 새로운 명제의 양변에 나타나는 항을 제거한다. 예를 들어, 다음과 같은 명제를 가지고 있다고 가정하자.

father (bob, jake) ∪ mother (bob, jake) ⊂ parent (bob, jake)

grandfather (bob, fred) ⊂ father (bob, jake) ∩ father (jake, fred)

해 도출은 다음과 같다.

mother (bob, jake) ∪ grandfather (bob, fred) ⊂ parent (bob, jake) ∩ father (jake, fred)

이 명제는 원래 명제의 기본 명제 중 하나만을 제외하고 모든 명제를 가지고 있다. 첫번째 명제의 좌변과 두번째 명제의 우변에 있는 연산 father (bob, jake) 를 허용한 기본 명제가 생략되었다. 문장으로 다음과 같이 말할 것이다.

if : bob 이 jake 의 부모이다는 bob 이 jake 의 아버지이거나 어머니이다를 포함한다.

and : bob 이 jake 의 아버지이고 jake 가 fred 의 아버지이다는 bob 이 fred 의 할아버지이다를 포함한다.

then : if bob 이 jake 이 부모이고 jake 가 fred 의 아버지이다, then : bob 이 jake 의 어머니이거나 bob 이 fred 의 할아버지이다.

해 도출은 실제로 이런 간단한 예제가 설명하는 것보다 더욱 복잡하다. 특히, 명제에서 변수의 존재는 해 도출 과정에서 부합 과정 (matching process) 이 성공하는 것을 허용하는 변수의 값을 찾으라고 요구된다. 변수의 유용한 값을 결정하는 이런 과정을 단일화 (unification) 라고 부른다. 단일화를 허용하기 위해 변수에 값을 일시적으로 대입시키는 것을 사례화 (instantiation) 라 부른다.

해 도출 단계에서 변수에 값을 사례화하고 요구된 매칭을 완성하는 것이 실패된 후에 역행해서 변수에 다른 값을 사례화하는 것은 일반적이다. Prolog 의 문맥에서 단일화와 역행 (backtracking) 을 좀더 광범위하게 논의할 것이다.

해 도출의 아주 중요한 성질을 주어진 명제 집합에서 어떤 불일치 (inconsistency) 를 탐지하는 능력이다. 이런 성질은 다음과 같이, 해 도출을 정리를 증명하는 데 사용하는 것을 허용한다. 술어 해석학 관점에서 정리 증명을 적당한 명제의 주어진 집합 (정리의 부정을 새 명제로 서술됨) 으로 볼 수 있다. 해 도출이 불일치를 발견함으로써 정리를 증명하는 데 사용될 수 있도록 정리는 부정된다. 이것이 모순에 의한 증명 (proof by contradiction) 이다. 전형적으로 원래의 명제는 가설 (hypotheses) 이라고 불리고, 정리의 부정은 목적 (goal) 이라고 불린다.

이론상으로, 이것은 유효하고 유용한 과정이다. 그러나 해 도출에 요구되는 시간이 문제가 될 수 있다. 명제의 집합이 유한일 때 해 도출도 유한 과정일지라도, 거대한 명제 데이터 베이스에서 불일치를 찾는 데 요구되는 시간은 거대할 수 있다.

정리 증명은 논리 프로그래밍의 기초이다. 계산되는 많은 부분이 가설로서 주어진 사실과 관계의 리스트와, 해 도출을 사용하여 가설로부터 추론된 목적의 형식으로 표현된다.

명제가 해 도출을 위해 사용될 때, 해 도출 과정을 더욱 단순화시키는 제한된 종류의 클로즈 형식이 사용될 수 있다. 이 특수한 명제를 혼 클로즈 (Horn clauses) 라 불리며, 단지 2 가지 형식으로 존재한다. 즉 좌변이 단일 기본 명제이거나 생략된다. [혼 클로즈는 이런 형식으로 클로즈를 연구한 Alfred Horn 의 이름을 따서 붙여졌다 (horn, 1951).] 클로즈 형식 명제의 좌변은 때때로 헤드 (head) 라 불리고, 좌변을 갖는 혼 클로즈는 유두 혼 클로즈 (headed Horn clause) 라고 불린다. 다음과 같이 유두 혼 클로즈는 관계를 나타내는 데 사용된다.

likes (bob, trout) ⊂ likes (bob, fish) ∩ fish (trout)

사실을 나타내는 데 자주 사용되는 좌변이 없는 혼 클로즈는 모두 혼 클로즈 (headless Horn clause) 라 불린다. 예를 들면, 아래와 같다.

father (bob, jake)

모두는 아니지만, 대부분의 명제는 혼 클로즈로 나타낼 수 있다.

4. 논리 프로그래밍의 개관

논리 프로그래밍을 위해 사용된 언어를 선언적 언어 (declarative language) 라고 부른다. 왜냐하면 그 언어로 작성된 프로그램이 배정문이나 제어 흐름문이 아닌 선언으로 구성되기 때문이다. 이런 선언은 기호 논리에서 실제적으로 문장, 즉 명제이다.

논리 프로그래밍 언어의 필수적인 특성은 선언적 의미론 (declarative semantics) 이라 불리는 의미론이다. 이 의미론의 기본 개념은 각 문장의 의미를 결정하는 간단한 방법이 있고, 의미는 문제를 풀기 위해 문장이 사용되는 방법에 종속되지 않는다는 것이다. 선언적 의미론은 명령형 언어 (imperative language) 의 의미론보다 간단하다. 예를 들면, 논리 프로그래밍 언어에서 주어진 명제의 의미는 문장 그 자체로부터 간결하게 결정될 수 있다. 명령형 언어에서 간단한 배정문의 의미는 지역 선언의 조사, 언어의 여역 규칙의 지식, 그리고 심지어 배정문 변수의 타입을 결정하기 위해 다른 파일의 프로그램 조사를 요구한다. 그런 후, 배정문 표현식이 변수를 가지고 있다면, 배정문 이전의 프로그램의 실행은 반드시 이런 변수의 값을 결정하기 위해 추적되어야 한다. 그 다음에 배정문의 결과는 실행 시간 문맥에 달려 있다. 이것을 단일 문장의 간단한 검사, 텍스트의 문맥이나 실행순서를 고려할 필요가 없는 것과 비교하면, 선언적 의미론이 명령형 언어의 의미론보다 더욱 간단하다는 것은 명백하다. 그러므로, 선언적 의미론은 선언적 언어가 명령형 언어에 대해서 가지는 장점 중에 하나이다 (Hogger, 1984, pp. 240 - 241).

명령형 언어와 함수 언어에서의 프로그래밍은 기본적으로 절차적 (procedural) 이다. 그것은 프로그래머가 프로그램에 의해 무엇이 성취되는지를 알고 계산이 정확하게 어떻게 수행되는지를 컴퓨터에게 지시하는 것을 의미한다. 다시 말하면, 컴퓨터는 명령을 따르는 간단한 장치로서 취급된다. 계산되는 모든 것은 계산의 모든 세부 사항이 상세히 설명되어야 한다. 어떤 사람은 이런 것이 컴퓨터 프로그래밍을 어렵게 하는 핵심이라고 믿는다.

어떤 비명령형 언어에서의 프로그래밍, 특히 논리 프로그래밍 언어에서의 프로그래밍은 비절차적이다. 이러한 언어에서의 프로그램은 결과가 계산되는 방법을 정확하게 서술하지 않고 결과의 형식을 서술한다. 차이점은 우리가 컴퓨터 시스템이 어쨌든 결과가 얻어지는 방식을 결정한다고 가정하는 것이다. 논리 프로그래밍 언어에 이 능력을 제공하기 위해 필요한 것은 적당한 정보와 원하는 계산 결과를 추론하는 방법을 컴퓨터에게 제공하는 간결한 수단이다. 수렁 해석학은 컴퓨터에 대한 기본 통신 형식을 제공하고, Robinson 에 의해 첫번째로 개발된 증명 방법은 추론 기법을 제공한다.

절차적 시스템과 비절차적 시스템의 차이를 설명하는 데 사용되는 일반적인 예제는 데이터를 어떤 특정한 순서로 배열하는 과정 즉 정렬 (sorting) 이다. C++ 와 같은 언어에서 정렬은 C++ 컴파일러를 가진 컴퓨터에게 정렬 알고리즘의 모든 세부사항을 C++ 프로그램으로 기술함으로써 실행된다. C++ 프로그램을 기계 코드나 인터프리터 중간코드로 변환한 후에 컴퓨터는 명령어를 따르며 정렬된 리스트를 생성한다.

비절차적 언어에서는 정렬된 리스트의 특성을 기술하기만 하면 된다. 그것은 인접 2 원소의 각 쌍에 대해서, 주어진 관계식이 성립하는 리스트의 치환이다. 이것을 형식적으로 설명하자. 정렬되는 리스트가 첨자범위 1..n 을 갖는 list 라는 이름의 배열이라고 가정하자. old_list 라는 주어진 리스트의 원소를 정렬하고 그 결과를 다른 배열에 놓는다는 개념을 다음과 같이 표현할 수 있다.

sort (old_list, new_list) ⊂ permute (old_list, new_list) ∩ sorted (new_list)
sorted (list) ⊂ ∀j such that 1 ≤ j < n, list (j) ≤ list (j + 1)

여기서 permute 는 두번째 매개변수 배열이 첫번째 매개변수 배열의 치환이면, 참을 되돌려주는 술어 (predicate) 이다.

이런 서술로부터, 비절차적 언어 시스템은 정렬된 리스트를 생성할 수 있다. 그것은 비절차적 프로그래밍을 간결한 소프트웨어 요구 명세의 단순한 생산물처럼 보이게 한다. 그러나 불행하게도, 그렇게 간단하지 않다. 단지 해 도출만 사용하는 논리 프로그램은 기계 효율성이라는 심각한 문제에 직면한다. 더욱이, 논리 언어의 최적 형식은 아직까지 결정되지 않았고, 논리 프로그래밍 언어에서 거대한 문제를 해결하기 위한 프로그램을 생성하는 좋은 방법은 아직 개발되지 않았다.

5. Prolog 의 기원

2 장에서 서술한 것처럼, Edinburgh 대학의 Robert Kowalski 의 지원을 받은 Aix-marseille 대학의 Alain Colmerauer 와 Phillipe Roussel 은 Prolog 의 기본적인 설계를 개발하였다. Colmerauer 와 Roussel 은 자연어 처리에 관심이 있었고 Kowaski 는 자동화된 정리 증명에 관심이 있었다. Aix-Marseille 대학과 Edinburgh 대학의 협력은 1970 년대 중반까지 계속되었다. 그 후에, 언어 개발과 사용에 관한 연구가 두 지역에서 독립적으로 진행되었고, 그 결과 구문적으로 다른 두 개의 Prolog 파생어가 만들어졌다.

Prolog 의 개발과 논리 프로그래밍에서 다른 연구 노력은 일본 정부가 5 세대 컴퓨팅 시스템 (FGCS - Fifth Generation Computing Systems) (Fuchi, 1981 ; Moto-oka, 1981) 이라 불리는 대형 연구 프로젝트를 시작했다는 발표가 1981 년에 있기 전까지는 Edinburgh 와 Marseille 대학 외부에서는 제한적인 관심만을 받았다. 프로젝트의 기본 목적은 지능 기계를 개발하는 것이었고, Prolog 가 이런 연구의 기초로 선택되었다. FGCS 의 발표는 미국 정부와 유럽 여러 나라의 연구자와 정부에 인공지능과 논리 프로그래밍에 즉각적이고 강력한 관심을 불러 일으켰다.

6. Prolog 의 기본 원소

현재 많은 Prolog 의 다른 파생어가 존재한다. 이런 것은 여러 개의 부류로 분류할 수 있다. Marseille 그룹으로부터 발전한 것, Edinburgh 그룹으로부터 나온 것, 그리고 Clark 과 McCabe (1984) 에 의해 기술된 micro-Prolog 와 같은 마이크로 컴퓨터를 위해 개발된 파생어의 모임이다. 이것들의 구문 형식은 약간 다르다. Prolog 의 여러 파생어 혹은 이들의 혼합형 구문을 기술하기보다는, 광범위하게 사용되고 있고 Edinburgh 에서 개발한 특별한 파생어를 선택했다. 이 언어 형식은 때때로 Edinburgh 구문이라고 불린다. 그것의 첫번째 구현은 DEC 시스템 - 10 에서 이루어졌다 (Warren et al., 1979).

(1) 항

다른 언어의 프로그램처럼, Prolog 프로그램도 문장의 집합으로 구성된다. Prolog 에는 단지 2 ~ 3 종류의 문장이 있지만, 그것은 복잡할 수 있다. 모든 Prolog 문장은 항으로부터 구성된다.

Prolog 항은 상수, 변수, 또는 구조이다. 상수는 원자 (atom) 이거나 정수이다. 원자는 Prolog 의 기호 값이고, LISP 의 원자와 유사하다. 특히, 원자는 소문자로 시작하는 문자, 숫자, 밑줄 문자 (underscore) 의 스트링이거나 따옴표로 구분된 프린트 가능한 ASCII 문자의 스트링이다.

변수는 대문자로 시작하는 문자나 숫자, 밑줄 문자의 스트링이다. 변수는 선언에 의해 타입에 바인딩되지 않는다. 값과 타입을 변수에 결합시키는 것을 사례화 (instantiation) 라 부른다. 사례화는 해 도출 과정 (resolution process) 에서만 일어난다. 값 할당이 안된 변수는 비사례화 (uninstantiation) 변수라 불린다. 사례화는 한 명제의 증명이나 반증을 포함하는 하나의 완전한 목적을 만족시킬 수 있는 한 계속된다. Prolog 변수는, 의미나 사용 관점에서, 명령형 언어의 변수와는 다르다.

항의 마지막 종류는 구조라 불린다. 구조는 술어 해석학의 기본 명제로 표현되고, 일반적인 형식은 동일하다.

functor (매개변수 리스트)

functor 는 어떤 원자이고 구조를 인식하는 데 사용된다. 매개 변수 리스트는 원자, 변수나 다른 구조의 리스트가 될 수 있다. 다음 절에서 상세히 논의되겠지만, 구조는 Prolog 에서 사실 (fact) 을 명시하는 도구이다. 구조는 객체로 생각될 수 있다. 이 경우 구조는 사실이 관련된 여러 원자의 항에서 표시되는 것을 허용한다. 이런 의미에서, 구조는 항 사이의 관계를 나타내기 때문에 관계이다. 또한 구조는 문맥이 구조를 질문으로 명시할 때는 술어이다.

(2) 사실 문

Prolog 문에 대한 논의는 가설 즉 추정된 정보의 데이터베이스를 구성하는데 사용되는 문장으로 시작한다. 이 문장으로부터 새로운 정보가 추론될 수 있다.

Prolog 는 두 개의 기초 문장 형식을 갖는다. 이것은 술어 해석학의 무두 혼 클로즈에 해당된다. Prolog 의 무두 혼 클로즈의 가장 간단한 형식이 단일 구조이다. 이것은 무조건적 단언 즉 사실로 해석된다. 논리적으로 사실은 참인 단순 명제이다.

다음 예제는 Prolog 프로그램에서 가질 수 있는 사실의 종류를 설명한다. 모든 Prolog 문장이 마침표로 끝나는 것에 주의해라.

   female (shelley).
   male (bill).
   female (mary).
   male (jake).
   father (bill, jake).
   father (bill, shelley).
   mother (mary, jake).
   mother (mary, shelley).

이 간단한 구조들은 jake, shelley, bill, mary 에 관한 어떤 사실을 나타낸다. 예로, 첫번째 것은 shelley 가 여자라는 것을 나타낸다. 마지막 네 개는 원자 functor 로 이름이 붙여진 관계로 두 매개변수를 연결한다. 예를 들면, 다섯번째 명제는 bill 이 jake 의 아버지라는 의미로 해석된다. 술어 해석학의 명제처럼 Prolog 명제는 고유의 의미를 가지고 있지 않음에 유의하라. 그들은 프로그래머가 그들에게 나타내기를 원하는 것을 의미한다. 예를 들면, 명제

father (bill, jake).

는 bill 과 jake 가 동일한 아버지를 갖거나 jake 가 bill 의 아버지라는 것을 의미할 수 있다. 그러나 가장 일반적이고 직설적인 의미는 bill 이 jake 의 아버지라는 것이다.

(3) 규칙문

데이터베이스를 구성하기 위한 Prolog 의 다른 기본 형식은 유두 혼 클로즈에 대응된다. 이 형식은 수학에서 주어진 조건 집합이 만족되면 결과가 나오는 것으로 알려진 정리와 연관시킬 수 있다. 우변은 전제, 즉 if 부분이며, 좌변은 결론, 즉 then 부분이다. 만약 Prolog 문장의 전제가 참이면, 또한 문장의 결과도 참이다. 그들은 혼 클로즈이기 때문에, Prolog 문자의 결과는 단일 항이고, 반면에 전제는 단일 항이거나 논리곱 (conjunctions) 이 될 수 있다.

논리곱 (conjunctions) 은 논리 AND 연산자에 의해 분리된 다중 항을 가지고 있다. Prolog 에 AND 연산자는 암시적이다. 기본 명제를 논리곱으로 명기하는 구조는 콤마로 분리되며, 그래서 콤마를 AND 연산자로 간주할 수 있다. 논리곱 예제로서, 다음을 생각해 보자.

female (shelley), child (shelley).

Prolog 의 유두 혼 클로즈 문장의 일반적인 형식은 다음과 같다.

결론_1 :- 전제_표현식.

이것은 다음과 같이 읽을 수 있다. "만약 전제_표현식이 참이거나 변수의 사례화에 의해 참이 되면 결론_1 이 성립한다." 다음 예제를 보자.

ancestor (mary, shelly) :- mother (mary, shelley).

이 예제는 "만약 mary 가 shelley 의 어머니이면, mary 는 shelley 의 조상이다" 라는 것을 나타낸다. 유두 혼 클로즈는 명제사이의 함축 규칙을 서술하기 때문에, 유두 혼 클로즈는 규칙 (Rule) 이라고 불린다.

술어 해석학의 클로즈 형식 명제처럼, Prolog 문은 그들의 의미를 일반화하는 변수를 사용할 수 있다. 클로즈 형식의 변수는 내재된 전칭 (universal) 한정사를 제공한다. 다음은 Prolog 문에서 변수의 사용을 보여주고 있다.

   parent (X, Y) :- mother (X, Y).
   parent (X, Y) :- father (X, Y).
   grandparent (X, Z) :- parent (X, Y), parent (Y, Z).
   sibling (X, Y) :- mother (M, X), mother (M, Y), father (F, X), father (F, Y).

이 문은 변수나 일반 객체사이의 함축 규칙을 제공한다. 이 경우에, 일반 객체는 X, Y, Z, M, F 이다. 첫번째 규칙은 만약 mother (X, Y) 참이 되는 X, Y 의 사례화가 있다면, 동일한 X, Y 의 사례화에 대해 parent (X, Y) 도 참이다라는 규칙을 서술한다.

(4) 목적문

지금까지 우리는 알려진 사실이나 사실들의 논리적 관계를 나타내는 규칙을 기술하는 데 사용된 논리 명제를 위해 Prolog 문을 기술하였다. 이러한 문장은 정리 증명 모델에서 기초이다. 정리는 시스템이 증명이나 반증되기를 원하는 명제 형식이다. Prolog 에서, 이런 명제는 목적 (goal) 이나 질의 (query) 라고 불린다. Prolog 목적문의 구문 형식은 무두 혼 클로즈와 동일하다. 예를 들면, 다음 목적문을 보자.

man (fred).

이 목적문에 대해 시스템은 "예" 나 "아니오" 라고 응답한다. 대답이 "예" 이면 시스템은 주어진 사실과 관계의 데이터베이스에서 목적이 참이라고 시스템이 증명하였다는 것을 의미한다. 대답이 "아니오" 이면 목적이 거짓이거나 시스템이 증명이나 반증을 간단히 할 수 없다는 것을 의미한다.

논리곱 명제와 변수를 갖는 명제도 합법적인 목적 문이다. 변수가 존재할 때, 시스템은 목적의 유효성을 주장할 뿐만 아니라 목적을 참으로 만드는 변수의 사례화를 확인한다. 예를 들면,

father (X, mike).

로 질의할 수 있다. 그런 후에, 시스템은 단일화를 통해 목적을 참으로 만드는 X 의 사례화를 찾도록 시도한다.

목적문과 비목적문은 동일한 형식 (무두 혼 클로즈) 을 가지기 때문에, Prolog 구현은 이 두 개를 구별하는 방법을 반드시 가져야 한다. 대화식 Prolog 구현은 다른 대화식 프롬프트에 의해 표시되는 간단한 두 개의 모드를 가짐으로서 이것을 수행한다. 즉 사실과 규칙을 입력하는 프롬프트와 목적을 입력하는 프롬프트이다. 사용자는 언제라도 모드를 바꿀 수 있다.

(5) Prolog 의 추론 과정

이 절에서 Prolog 의 해 도출을 조사하고자 한다. Prolog 의 효율적인 사용은 프로그래머가 Prolog 시스템이 프로그램으로 수행하는 것을 자세히 알 것을 요구한다.

질의는 목적 (goal) 이라 불린다. 목적이 복합 명제일 때, 각 사실 (구조) 은 부목적 (subgoal) 이라 불린다. 목적이 참이라는 것을 증명하기 위해, 추론 과정은 목적을 데이터 베이스의 하나 또는 그 이상의 사실과 연결시키는 데이터 베이스의 추론 규칙과/또는 사실의 체인을 찾아야 한다. 예를 들면, 만약 Q 가 목적이면, Q 는 데이터베이스에서 사실로서 찾아지거나 추론 과정은 P 가 성립하는 사실 과 명제 의 순서열을 찾아야 한다.

물론, 이 과정은 규칙의 복합 명제로 구성된 우변과 규칙의 변수의 존재에 의해서 복잡해질 수 있고, 가끔은 복잡하다. P (존재할 때) 를 찾는 방법은 근본적으로 서로 다른 항과의 비교 즉 부합 (matching) 이다.

부목적을 증명하는 과정은 명제-부합 과정으로 수행되기 때문에, 그것은 때때로 부합이라 불린다. 어떤 경우에서는 부목적을 증명하는 것은 부목적을 만족 (satisfying) 하는 것이라 불린다.

다음 질의를 생각해보자.

man (bob).

이 목적문은 가장 간단한 종류이다. 해 도출이 참인지 거짓인지를 결정하는 것은 상대적으로 쉽다. 이 목적의 패턴은 데이터베이스의 사실과 규칙에 비교된다. 만약 데이터베이스가 사실

man (bob).

을 포함한다면, 증명은 단순하다. 그러나 만약 데이터베이스가 다음의 사실과 추론 규칙을 가지고 있다면,

father (bob).
man (X) :- father (X).

Prolog 는 이 두 문장을 찾도록 요구하며, 목적의 진리 값을 추론하기 위해 이들을 사용한다. 이것은 일시적으로 X 를 bob 으로 사례화하는 단일화를 필요로 한다.

이제 다음 목적을 살펴보자.

man (X).

이 경우에, Prolog 는 목적을 데이타베이스의 명제와 부합시켜야 한다. 매개변수로 객체를 갖고, 목적의 형식을 갖는 Prolog 가 찾는 첫번째 명제는 X 를 객체의 값으로 사례화시킨다. 그런 후, X 는 결과로서 디스플레이 (출력) 된다. 목적의 형식을 갖는 명제가 없다면, 시스템은 "아니오" 라고 말하면서, 목적을 만족시킬 수 없다고 나타낸다.

주어진 목적이 데이터베이스의 사실과 부합하기 위한 시도에는 두 가지 대립되는 접근 방법이 있다. 시스템은 데이터베이스의 사실과 규칙을 가지고 시작하고, 목적에 도달하는 부합 순서를 찾도록 시도한다. 이러한 접근 방법은 상향식 해 도출 또는 전향 체인 (forward chaining) 이라고 불린다. 다른 방법은 목적으로 시작하고, 데이터베이스에서 원래의 어떤 사실 집합에 도달하는 부합 명제의 순서를 탐색하도록 시인한다. 이런 접근 방식은 하향식 해 도출 또는 후향 체인 (backward chaining) 이라고 불린다. 일반적으로 후향 체인은 후보 해답의 집합이 적당하게 작을 때 잘 작동한다. 전향 체인 접근 방법은 가능한 답의 수가 많을 때 잘 동작한다. 이러한 상황에서 후향 체인은 해답을 얻기 위해 많은 수의 부합을 요구한다. 설계자는 거대한 부류의 문제에 대해 전향 체인보다 후향 체인이 적합하다고 믿기 때문에, Prolog 구현은 해 도출을 위해 후향 체인을 사용한다.

다시 질의 예제를 살펴보자.

man (bob).

데이터베이스에 다음이 있다고 가정하자.

father (bob).
man (X) :- father (X).

전향 체인은 첫번째 명제를 탐색하고 찾는다. 그런 후, X 를 bob 으로 사례화하여 첫번째 명제를 두번째 규칙의 우변 ((father (X)) 과 부합한 후 두번째 명제의 좌변을 목적에 부합시킴으로서 목적이 추론된다. 후향 체인은 먼저 X 를 bob 으로 사례화를 통해서 목적을 두번째 명제의 좌변 (man (X)) 과 부합한다. 마지막 단계에서, 두번째 명제의 우변 (father (bob)) 은 첫번째 명제와 부합한다.

다음 설계 문제는 위에서 본 예제처럼 목적이 하나 이상의 구조를 가질 때 발생한다. 여기에서의 문제는 해 도출 탐색이 넓이 우선 (breadth-first) 또는 깊이 우선 (depth-first) 으로 수행되느냐이다. 깊이 우선 탐색은 다른 부목적에 작업하기 전에 주어진 목적의 첫번째 부목적의 명제-증명- 의 완전한 순서를 찾는다. 넓이 우선 탐색은 주어진 목적의 모든 부목적에 병렬적으로 작업한다. Prolog 설계자는 깊이 우선 탐색 접근 방법이 적은 컴퓨터 자원을 가지고 수행될 수 있기 때문에 기본적으로 깊이 우선 탐색 접근 방법을 선택하였다. 넓이 우선 탐색은 많은 메모리 사용을 요구하는 병렬 탐색이다.

논의해야 할 Prolog 해 도출 구조의 마지막 특징은 역행 (backtracking) 이다. 다중 부목적을 가진 목적이 처리되고 시스템이 부목적 중 하나의 진리값을 보여주는 것을 실패할 때, 시스템은 증명할 수 없는 그 부목적을 포기한다. 대신에, 시스템은 만약 그 부목적이 있으면 이전 부목적을 다시 고려하여 다른 해답을 찾도록 시도한다. 이전에 증명된 부목적의 재고를 위해 목적에서 후퇴하는 것을 역행 (backtracking) 이라 부른다. 새로운 해답은 그 부목적의 이전 탐색이 중단된 곳에서 탐색을 시작함으로서 찾을 수 있다. 부목적의 다수의 해는 변수의 각각 다른 사례화에 기인한다. 역행은 시간과 공간을 많이 요구한다. 왜냐하면, 각 부목적의 모든 가능한 증명을 찾아야하기 때문이다. 이런 부목적 증명은 마지막 완전한 증명이 되는 결과 증명을 찾기 위해 요구된 시간이 최소화되도록 조직되지 않는다. 이것은 문제를 악화시킨다.

역행에 대한 이해를 확실히 하기 위해 다음 예제를 살펴보자. 데이터베이스에 사실과 규칙의 집합이 있고, Prolog 에 다음과 같은 복합 목적이 제시되었다고 가정하자.

male (X), parent (X, shelley).

이 목적은 X 가 male 이고 X 가 shelley 의 parent 가 되는 X 의 사례화가 있는지를 묻는다. Prolog 는 먼저 작용자 (functor) 로 male 을 가지고 있는 데이터베이스에서 첫번째 사실을 찾는다. 그런 후, X 를 찾은 사실의 매개변수 mike 로 사례화시킨다. 그 다음으로, parent (mike, shelley) 가 참이라는 증명을 시도한다. 만약 그것이 실패하면, 첫번째 부목적 male (X) 로 되돌아가고, X 의 다른 사례화로 만족시킬려고 시도한다. 해 도출 과정은 shelley 의 부모인 male 을 찾기 전에 데이터베이스에서 모든 male 을 찾을 수도 있다. 해 도출 과정은 목적을 만족시킬 수 없다는 것을 증명하기 위해 모든 male 을 확실히 찾아야한다. 만약 두 개의 부목적의 순서가 반대로 되어 있으면, 우리의 예제는 좀더 효율적으로 처리된다. 그런 후, 해 도출이 shelley 의 부모를 발견한 후 그 사람과 부목적 male 를 부합시킬려고 할 것이다. 만약 데이터베이스에 shelley 가 male 보다 적은 parent 를 가지고 있으면 (공정한 가정처럼 생각됨) 이것은 좀더 효율적이다. 7.1 절에서 Prolog 시스템에 의해서 수행되는 역행을 제한시키는 방법을 살펴본다.

Prolog 에서 데이터베이스 탐색은 항상 첫번째에서 마지막 방향으로 진행된다.

다음 두 부절은 해 도출 과정을 더 상세히 설명하는 Prolog 예제를 기술한다.

(6) 간단한 산술 연산

Prolog 는 정수 변수와 정수 산술 연산을 지원한다. 원래, 산술 연산자는 작용자 (functor) 였다. 그래서 7 과 변수 X 의 합은 다음과 같이 형성된다.

+ (7, X)

Prolog 는 is 연산자로서 산술 연산의 더욱 간결한 구문을 허용한다. 이 연산자는 오른쪽 피연산자로서 산술 표현식을 왼쪽 피연산자로서 변수를 취한다. 표현식의 모든 변수는 반드시 미리 사례화되어야 하지만, 좌변의 변수는 전에 사례화될 수 없다. 예를 들어, 다음 식을 생각해 보자.

A is B / 17 + C.

만약 B 와 C 가 사례화되었지만, A 는 안되었다면, 이 클로즈는 A 를 표현식의 값으로 사례화할 것이다. 이런 일이 발생하면, 클로즈는 만족된다. 만약 B 와 C 가 사례화되지 않고 A 만이 사례화되었다면, 클로즈는 만족되지 않으며 A 의 사례화는 발생될 수 없다. is 명제의 의미는 명령형 언어의 배정문과는 많은 차이가 있다. 이 차이는 흥미로운 상황을 이끌어 낼 수 있다. is 연산자는 클로즈를 배정문처럼 보이게 하기 때문에, 초보 Prolog 프로그래머는 다음과 같은 문장을 작성할 수 있다.

Sum is Sum + Number.

이것은 Prolog 에서 합법적일지라도 유용하지 않다. 만약 Sum 이 사례화되지 않았다며, 우변의 참조는 정의되지 않고, 클로즈는 실패한다. 만약 Sum 이 이미 사례화되었다면, is 가 평가될 때 왼쪽 피연산자는 현재 사례화를 가질 수 없기 때문에 클로즈는 실패한다. 어느 경우든, 새로운 값에 대한 Sum 의 사례화는 발생하지 않는다 (만약 Sum + Number 의 값이 요구되면, 그것은 어떤 새로운 이름에 바인딩될 수 있다).

Prolog 는 명령형 언어와 같은 동일한 의미로 배정문을 갖지 않는다. 그들은 Prolog 가 설계된 대부분의 프로그래밍에서 필요치 않다. 명령형 언어에서 배정문의 유용성은 배정문이 내장된 코드의 실행 제어 흐름을 제어하는 프로그래머의 능력에 달려있다. 이런 형의 제어는 Prolog 에서 항상 가능하지 않기 때문에, 이러한 문장은 거의 유용하지 않다.

Prolog 에서 수치 계산을 사용한 간단한 예제로서, 다음 문제를 생각해 보자. 우리는 어떤 특별한 자동차 경주 트랙에서 여러 자동차의 평균 속도와 그 트랙에 있는 자동차의 총 시간을 알고 있다고 가정하자. 이 기본 정보는 사실로 코딩되고, 속도, 시간, 거리 사이의 관계는 규칙으로 다음과 같이 작성된다.

   speed (ford, 100).
   speed (vlovo, 80).
   speed (chevy, 105).
   speed (dodge, 95).
   time (ford, 20).
   time (chevy, 21).
   time (dodge, 24).
   time (volvo, 24).
   distance (X, Y) :- speed (X, Speed),
       time (X, Time),
           Y is Speed * Time.

이제, 질의는 특별한 자동차의 주행 거리를 요구한다. 예를 들면, 질의

distance (chevy, Chevy_Distance).

는 Chevy_Distance 를 2205 로 사례화시킨다. 거리 계산 문장의 우변에서 첫 두 클로즈는 간단하게 변수 Speed 와 Time 을 주어진 자동차 작용자의 대응 값으로 사례화시킨다. 목적이 만족된 후에, 또한 Prolog 는 Chevy_Distance 와 값을 디스플레이한다.

이 시점에서, Prolog 시스템이 결과를 생산하는 방법을 연산적인 면에서 관찰하는 것은 유익하다. Prolog 는 주어진 목적을 만족시키는 동안에 각 단계에서 수행한 변수의 사례화를 디스플레이하는 trace 라는 이름의 내장 구조를 갖는다. trace 는 Prolog 프로그램을 이해하고 디버그하는 데 사용된다. trace 를 이해하기 위해, 추적 모델 (tracing model) 이라 불리는 Prolog 프로그램의 다른 실행 모델을 설명하는 것이 가장 좋다.

추적 모델은 네 가지 사건으로 Prolog 실행을 기술한다. (1) call 은 목적을 만족시키려는 시도 초기에 발생한다. (2) exit 는 목적이 만족되었을 때 발생한다. (3) redo 는 목적을 재 만족시킬려고 시도할 때 발생한다. (4) fail 은 목적이 실패되었을 때 발생한다. 만약 distance 와 같은 프로세스가 부프로그램으로 생각된다면 call 과 exit 는 명령형 언어의 부프로그램 실행 모델과 직접적으로 관련시킬 수 있다. 다른 두 사건은 논리 프로그래밍 시스템에서만 유일하다. 다음 trace 예제에서, 목적은 redo 나 fail 사건을 요구하지 않는다.

다음은 Chevy_Distance 를 위한 값의 계산 추적이다.

trace.
distance (chevy, Chevy_Distance).

   (1) 1 Call : distance (chevy, _0)?
   (2) 2 Call : speed (chevy, _5)?
   (2) 2 Exit : speed (chevy, 105)
   (3) 2 Call : time (chevy, _6)?
   (3) 2 Exit : time (chevy, 21)
   (4) 2 Call : _0 is 105 * 21?
   (4) 2 Exit : 2205 is 105 * 21
   (1) 1 Exit : distance (chevy, 2205)

Chevy_distance = 2205

밑줄 문자 (_) 로 시작하는 추적 (trace) 에 있는 기호는 사례화된 값을 저장하는 내부 변수이다. 추적의 첫 열은 부합이 현재 시작되고 있는 부목적을 가리킨다. 예를 들면, 위의 추적에서 표시 (3) 을 갖는 첫 줄은 임시 변수 _6 를 chevy 의 time 값으로 사례화하려는 시도이다. 여기서 time 은 distance 의 계산을 기술하는 문장의 우변의 두번째 항이다. 두번째 열은 부합 과정의 호출 깊이를 나타낸다. 세번째 열은 현재 동작을 나타낸다.

역행을 설명하기 위해, 다음 예제 데이터베이스와 추적된 복합 목적을 생각해보자.

   likes (jake, chocolate).
   likes (jake, apricots).
   likes (darcie, licorice).
   likes (darcie, apricots).

trace.
likes (jake, X), likes (darcie, X).

   (1) 1 Call : likes (jake, _0)?
   (1) 1 Exit : likes (jake, chocolate)
   (2) 1 Call : likes (darcie, chocolate)?
   (2) 1 Fail : likes (darcie, chocolate)
   (1) 1 Redo : likes (jake, _0)?
   (1) 1 Exit : likes (jake, apricots)
   (3) 1 Call : likes (darcie, apricots)?
   (3) 1 Exit : likes (darcie, apricots)

X = apricots

Prolog 계산을 다음과 같이 도표로 생각할 수 있다. 각 목적을 네 개의 포트 - call, fail, exit, redo - 를 가진 상자로 생각해 보자. 제어가 전진 방향에서 call 포트를 통해서 목적에 들어온다. 또한 제어는 반대 방향으로 redo 포트를 통해서 목적에 들어갈 수 있다. 만약 목적이 성공하면, 제어는 exit 포트를 통해서 떠난다. 위의 예제 모델은 그림 1 에 나타나 있다.

그림 1 목적 likes (jake, X) 와 likes (darcie, X) 을 위한 제어 흐름 모델

이 예제에서, 제어 흐름은 부목적을 두 번 통과한다. 두번째 부목적은 처음에 실패하고, 이것은 redo 를 통해서 강제로 첫 부목적으로 되돌려 보낸다.

(7) 리스트 구조

지금까지, 우리가 논의한 Prolog 데이터 구조는 데이터 구조보다 더 함수 호출처럼 보이는 기본 명제이다. 또한 구조라 불리는 기본 명제는 실제로 레코드 형식이다. 지원되는 다른 기본 데이터 구조는 LISP 에서 사용되었던 리스트 구조와 비슷한 리스트이다. 리스트는 많은 원소의 연속이다. 여기서 원소는 원자, 기본 명제 또는 다른 리스트를 포함하는 다른 항이다.

Prolog 는 리스트를 명시하기 위해 전통적 구문을 사용한다. 리스트 원소는 다음과 같이 콤마에 의해 분리되고, 전체 리스트는 사각 괄호에 의해 범위가 정해진다.

[apple, prune, grape, kumquat]

표기법 [] 는 공 리스트를 나타내는 데 사용한다. 리스트를 만들거나 분해하는 명시적인 함수를 사용하는 대신에, Prolog 는 간단하게 특별한 기호를 사용한다. [X | Y] 는 헤드 X 와 테일 Y 를 갖는 리스트이다. 여기서 헤드와 테일은 LISP 의 CAR, CDR 에 대응된다. 이것은 Haskell 에서 사용하는 표기법과 유사하다.

리스트는 다음과 같이 간단한 구조를 갖고 생성된다.

new_list ([apple, prune, grape, kumquat]).

이것은 상수 리스트 [apple, prune, grape, kumquat] 가 new_list (방금 작성한 이름) 라는 이름을 갖는 관계의 새로운 원소라른 것을 나타낸다. 이 문장은 new_list 라는 이름을 갖는 변수에 리스트를 바인딩하지 않는다. 오히려, 그것은 다음과 같은 명제 중에 하나이다.

male (jake)

즉 말하자면, 그것은 [apple, prune, grape, kumquat] 가 new_list 의 새로운 원소라는 것을 나타낸다. 그러므로, 우리는 다음과 같은 리스트 인자를 갖는 두번째 명제를 가질 수 있다.

new_list ([apricot, peach, pear])

질의 모드에서, new_list 의 원소는 다음과 같이 헤드와 테일로 분리될 수 있다.

new_list ([New_List_Head | New_List_Tail]).

만약 new_list 가 위와 같이 두 개의 구성 원소를 갖도록 설정되었다면, 이 문장은 New_List_Tail 를 리스트의 테일 ([prune, grape, kumquat]) 로 사례화한다. 만약 이것이 복합 목적의 부분이고, 역행이 이것의 새로운 평가를 강요했다면, [apricot, peach, pear] 이 new_list 의 다음 원소이기 때문에 New_List_Head 와 New_List_Tail 은 각각 apricot 와 [peach, pear] 에 사례화된다.

리스트를 분해하는 데 사용된 표기법은 주어진 사례화된 헤드와 테일 원소를 다음과 같이 리스트를 생성하는 데 사용될 수 있다.

[Element_1 | List_2]

만약 Element_1 이 pickle 에 사례화되고, List_2 가 [peanut, prune, popcorn] 에 사례화되었다면, 위와 같은 표기법은 리스트 [pickle, peanut, prune, popcorn] 을 생성한다.

위에서 기술된 것처럼, | 기호를 포함하는 리스트 표기법은 보편적이다. 그것은 리스트 생성이나 리스트 분해를 명시할 수 있다. 다음과 같은 예제는 모두 동일하다는 것에 유의해라.

   [apricot, peach, pear | []]
   [apricot, peach | [pear]]
   [apricot, | [peach, pear]]

리스트를 다룰 때, LISP 에서 발견되는 것과 같은 어떤 기본 연산이 종종 요구한다. Prolog 에서 이러한 연산의 예제로서, 우리는 LISP 의 append 함수와 관련이 있는 append 의 정의를 살펴본다. 이 예제에서, 함수형 언어와 선언적 언어의 차이점과 유사점을 볼 수 있다. Prolog 가 주어진 리스트로부터 새로운 리스트를 생성하는 방법에 대해 기술할 필요가 없다. 오히려, 우리는 주어진 리스트로서 새로운 리스트의 특성을 기술하는 것이 필요하다.

외관적으로, Prolog append 정의는 LISP append 정의와 매우 유사하고, 해 도출에서 재귀는 새로운 리스트를 생성하기 위한 유사한 방법으로 사용된다. Prolog 의 경우, 재귀는 해 도출 과정에 의해서 발생되고 제어된다.

append ([], List, List)
append ([Head | List_1], List_2, [Head | List_3]) :- append (List_1, List_2, List_3).

첫 명제는 공 리스트가 다른 리스트에 첨가될 때, 다른 리스트가 결과라는 것을 나타낸다. 이 문장은 LISP append 함수의 재귀-종결 단계에 해당된다. 종결 명제는 재귀 명제 전에 위치한다는 것에 유의하라. Prolog 는 처음부터 시작하여 순서대로 (깊이 우선 탐색을 사용하기 때문에) 두 명제에 부합된다는 것을 알고 있기 때문에, 이것은 수행된다.

두번째 명제는 새로운 리스트의 여러 가지 특성을 명시한다. 그것은 LISP 함수의 재귀 단계에 해당된다. 좌변의 술어는 새로운 리스트의 첫 원소가 처음 주어진 리스트의 첫 원소와 동일하다는 것을 나타낸다. 왜냐하면 그들은 Head 라는 이름을 갖기 때문이다. Head 가 값으로 사례화될 때마다, 목적에 있는 모든 Head 는, 사실상, 동시에 그 값으로 사례화된다. 두번째 문장의 우변은 첫번째 주어진 리스트의 테일 (List_1) 은 두번째 주어진 리스트 (List_2) 를 첫번째 주어진 리스트의 테일에 첨가하여 결과 리스트의 테일 (List_3) 을 형성하라고 지정한다.

append 의 두번째 문장을 읽는 방법은 다음과 같다. 리스트 [Head | List_1] 를 List_2 에 첨가하여 리스트 [Head | List_3] 을 생성하지만, List_3 은 List_1 을 List_2 을 첨가함으로써 형성된다. LISP 에서 이것을 다음과 같이 쓸 수 있다.

(CONS (CAR FIRST) (APPEND (CDR FIRST) SECOND))

Prolog 와 LISP append 에서 결과 리스트는 재귀가 종료 조건을 생산할 때까지 만들어지지 않는다. 이 경우에, 첫 리스트는 반드시 공 리스트이다. 그런 후에, 결과 리스트가 append 함수를 사용해서 만들어진다. 첫 리스트에서 취해진 원소는 역순으로 두번째 리스트에 첨가된다. 역순은 재귀를 해결함으로써 완성된다.

어떻게 append 과정이 진행되는가를 설명하기 위해, 다음의 추적된 예제를 생각해 보자.

trace.
append ([bob, jo], [jake, darcie], family).

   (1) 1 Call : append ([bob, jo], [jake, darcie], _10)?
   (2) 2 Call : append ([jo], [jake, darcie], _18)?
   (3) 3 Call : append ([], [jake, darcie], _25)?
   (3) 3 Exit : append ([], [jake, darcie], [jake, darcie])
   (2) 2 Exit : append ([jo], [jake, darcie], [jo, jake, darcie])
   (1) 1 Exit : append ([bob, jo], [jake, darcie], [bob, jo, jake, darcie])

Family = [bob, jo, jake, darcie]
yes

부목적을 표현하는 첫 두 개의 call 은 공 리스트가 아닌 List_1 을 갖는다. 그래서 두번째 문장의 우변으로부터 재귀 호출을 생성한다. 두번째 문장의 좌변은 효과적으로 재귀 호출 즉 목적을 위한 인자를 명시한다. 그러므로 첫번째 리스트는 각 단계 당 하나의 원소를 분리시킨다. 첫번째 리스트가 호출 즉 부목적에서 공 리스트일 때, 두번째 문장의 우변의 인스턴스는 첫번째 문장에 부합함으로써 성공한다. 이것의 효과는 세번째 매개변수로서 두번째 원래 매개변수 리스트에 첨가된 공 리스트의 값을 반환하는 것이다. 성공적인 부합을 표현하는 연속적인 exit 에서 첫 리스트로부터 제거된 원소는 결과 리스트 - Family - 에 첨가된다. 첫 목적의 exit 가 실행될 때, 그 과정은 완성되고, 결과 리스트가 표시된다.

append 명제는 다음과 같은 다른 리스트 연산을 생성하는 데 사용될 수 있다. 이 연산의 결과를 여러분들이 결정하기 바란다. list_op_2 는 첫 매개변수로 리스트를, 두번째 매개변수로 변수를 제공하고, list_op_2 의 결과는 두번째 매개변수가 사례화된 값임에 유의하라.

list_op_2 ([], []).
list_op_2 ([Head | Tail], List) :- List_op_2 (Tail, Result), append (Result, [Head], List).

독자가 결정할 수 있는 것처럼, list_op_2 는 Prolog 시스템에게 두번째 매개변수를 첫번째 매개변수의 리스트 원소를 역순으로 갖는 리스트로 사례화시키게 한다. 예를 들면, ([apple, orange, grape], Q) 는 Q 를 리스트 [grape, orange, apple] 로 사례화한다.

다시 한번, 비록 LISP 의 Prolog 언어가 본질적으로 다르다고 할지라도, 유사한 연산은 유사한 접근 방법을 사용할 수 있다. 역 리스트 연산의 경우에, Prolog 의 list_op_2 와 LISP 의 reverse 함수는 재귀 종료 조건과 결과 리스트를 생성하기 위하여 리스트의 CDR (즉 테일) 의 역 리스트를 리스트의 CAR (즉 헤드) 에 첨가시키는 기본 과정을 포함한다.

다음은 reverse 라 이름 붙여진 이 과정 추적이다.

trace.
reverse ([a, b, c], Q).

   (1) 1 Call : reverse ([a, b, c], _6)?
   (2) 2 Call : reverse ([b, c], _65636)?
   (3) 3 Call : reverse ([c], _65646)?
   (4) 4 Call : reverse ([ ], _65656)?
   (4) 4 Exit : reverse ([ ], [ ])
   (5) 4 Call : append ([ ], [c], _65646)?
   (5) 4 Exit : append ([ ], [c], [c])
   (3) 3 Exit : reverse ([c], [c])
   (6) 3 Call : append ([c], [b], _65636)?
   (7) 4 Call : append ([ ], [b], _25)?
   (7) 4 Exit : append ([ ], [b], [b])
   (6) 3 Exit : append ([c], [b], [c, b])
   (2) 2 Exit : reverse ([b, c], [c, b])
   (8) 2 Call : append ([c, b], [a], _6)?
   (9) 3 Call : append ([b], [a], _32)?
   (10) 4 Call : append ([ ], [a], _39)?
   (10) 4 Exit : append ([ ], [a], [a])
   (9) 3 Exit : append ([b], [a], [b, a])
   (8) 2 Exit : append ([c, b], [a], [c, b, a])
   (1) 1 eXIT :REVERSE ([A, B, C], [C, B, A])

Q = [c, b, a]

주어진 기호가 주어진 리스트에 있는지를 결정하는 것이 필요하다고 가정하자. 직설적인 Prolog 표현은 다음과 같다.

member (Element, [Element | _]).
member (Element, [_ | List]) :- member (Element, List).

밑줄 문자는 익명 변수를 나타내고, 그것은 단일화로부터 얻어지는 사례화에 관심이 없다는 것을 의미하는 데 사용된다. 만약 처음부터 또는 두 번째 문장을 통과하여 여러 재귀가 있은 후에 Element 가 리스트의 헤드이면, 위의 첫문장은 성공한다. 만약 Element 가 리스트의 테일 중에 하나면, 두 번째 문장은 성공한다. 다음 추적된 예제를 생각해보자.

   trace.
   member (a, [b, c, d] ).
   (1) 1 Call : member (a, [b, c, d])?
   (2) 2 Call : member (a, [c, d])?
   (3) 3 Call : member (a, [d])?
   (4) 4 Call : member (a, [ ])?
   (4) 4 Fail : member (a, [ ])
   (3) 3 Fail : member (a, [d])
   (2) 2 Fail : member (a, [c, d])
   (1) 1 Fail : member (a, [b, c, d])
   no

   member (a, [b, a, c]).
   (1) 1 Call : member (a, [b, a, c])?
   (2) 2 Call : member (a, [a, c])?
   (2) 2 Exit : member (a, [a, c])
   (1) 1 Exit : member (a, [b, a, c])
   yes

7. Prolog 의 결점

논리 프로그래밍 언어로서 Prolog 를 사용할 때 여러 가지 문제가 발생한다. 비록 그것이 유용한 도구일지라도, 그것은 순수하거나 완전한 논리 프로그래밍 언어가 아니다.

(1) 해 도출 순서 제어

효율적인 이유로, Prolog 는 사용자가 해 도출을 수행하는 동안에 패턴 매칭의 순서를 제어하는 것을 허용한다. 순수 논리 프로그래밍 환경에서는, 해 도출 동안에 발생한 시도된 부합의 순서는 비결정적이고 모든 부합은 병렬적으로 시도될 수 있다. 그러나 Prolog 는 항상 데이터베이스의 처음과 주어진 목적의 왼쪽 끝에서 시작하는 동일한 순서로 부합되기 때문에, 사용자는 특별한 응용을 최적화하기 위해 데이터베이스 문장을 정돈함으로써 심오하게 효율성에 영향을 미칠 수 있다. 예를 들면, 만약 사용자가 특별한 실행 동안에 어떤 규칙이 다른 규칙보다 더욱 성공할 것 같다는 지식을 가지고 있다면, 그런 규칙을 데이터베이스의 처음에 위치하게 하여 프로그램을 더욱 효율적으로 만들 수 있다.

느린 프로그램 실행이 Prolog 프로그램에서 사용자-정의 순서의 부정적인 결과만은 아니다. 무한 루프 따라서 전 프로그램 실패를 발생시키는 형식으로 문장을 작성하기는 매우 쉽다. 예를 들면, 다음 재귀 문장 형식을 고려해보자.

f (x, y) :- f (z, Y), g (X, z).

Prolog 의 좌우 (left-to-right) 깊이-우선 평가 순서 때문에, 문장 목적에 관계없이, 이것은 무한 루프를 발생시킨다. 이런 종류의 문장의 예로서 다음을 생각해보자.

ancestor (X, X).
ancestor (X, Y) :- ancestor (Z, Y), parent (X, Z).

두 번째 명제의 우변의 첫 부목적을 만족시키기 위한 시도에서, Prolog 는 ancestor 를 참으로 하기 위해 Z 를 사례화한다. 그런 후, 이 새 부목적을 만족시키려고 시도한다. 즉 ancestor 의 정의로 돌아가서 같은 과정을 반복하여, 결국 무한 재귀에 이른다.

이 특별한 문제는 3 장에서 논의된 것처럼, 문법 규칙에서 왼쪽 재귀를 갖는 재귀 하향 파서가 갖는 문제와 동일하다. 파싱의 문법 규칙처럼, 위 명제의 우변에서 간단하게 항의 순서를 바꾸면 그 문제는 제거된다. 이것의 문제는 항 순서의 간단한 변환이 프로그램 정확성에 결정적이 되어서는 안된다는 것이다. 무엇보다도, 제어 순서에 대해 프로그래머가 걱정할 필요가 없다는 것이 아마도 논리 프로그래밍의 장점 중에 하나일 것이다.

사용자에게 데이터베이스와 부목적 순서 제어를 허용하는 것 이외에도, 효율성을 위해서, Prolog 는 역행의 명시적인 제어를 허용한다. 이것은 cut 연산자로 수행되고, 감탄사 (!) 로 표시된다. cut 연산자는 연산자가 아니라 실제로 목적이다. 목적으로서, cut 은 항상 즉시 성공하지만, 역행을 통해서 재 만족시킬 수 있다. cut 의 부작용은 복합 목적에서 cut 의 왼쪽 부목적은 역행을 통해서 재 만족시킬 수 없다는 것이다. 예로 들면, 다음과 같은 목적에서,

a, b, !, c, d.

만약 a, b 가 성공하고, c 가 실패하면, 전체 목적은 실패한다. c 가 실패할 때마다, b 나 a 를 재 만족시키는 것이 시간 낭비라는 것이 알려졌다면, 이 목적이 사용될 것이다.

cut 의 목적은 완전한 증명을 할 수 없는 부목적을 재 만족시키려는 시도를 하지 않을 시점을 시스템에게 말하게 함으로써 사용자가 프로그램을 더욱 효율적으로 만드는 것을 허용하는 것이다.

cut 연산자의 사용 예로서, 6.7 절의 member 함수를 생각해 보자.

member (Element, [Elemtne | _]).
member (Element, [_ | List]) :- member (Element, List).

만약 member 의 리스트 매개변수가 집합을 나타내면, 그것은 단지 한번만 만족될 수 있다 (집합은 중복된 원소를 갖지 않는다). 그러므로, 만약 member 가 다중 부목적으로 구성된 목적 문장의 부목적으로서 사용된다면, 문제가 될 수 있다. 문제는 만약 member 는 성공하지만 다음 부목적이 실패한다면, 역행이 전 부합을 계속함으로써 member 를 재만족시키려고 할 것이다. 그러나 전 부합을 계속함으로써 member 를 재만족시키려고 할 것이다. 그러나 member 의 리스트 매개변수는 처음부터 그 원소는 하나만 가지기 때문에, member 는 다시 성공할 수 없다. member 를 재만족시키려는 부가적인 시도에도 불구하고 결국은 전체 목적이 실패하게 된다. 이런 비효율성에 대한 해결책은 member 정의의 첫 문장 우변에 다음과 같이 단 하나의 원소로 cut 연산자를 첨가시키는 것이다.

member (Element, [Element | _]) :- !.

역행은 member 를 재 만족시키려고 시도하지 않고, 대신 전체 부목적을 실패하게 한다.

cut 은 Prolog 에서 생성-검사 (generate and test) 라 불리는 프로그래밍 방법에 특별히 유용하다. 이런 프로그램에서, 목적은 잠재적인 해결책을 생성하는 부목적으로 구성된다. 이 잠재적인 해결책은 나중 test 부목적에 의해서 검사된다. 거부된 잠재적인 해결책은 새로운 잠재적인 해결책을 생성하는 생성자 부목적에 역행을 요구한다. 생성-검사 프로그램의 예제로서, Clocksin 과 Mellish (1984) 가 저술한 책에 나오는 다음 예제를 생각해 보자.

    divide (N1, N2, Result) :- is_integer (Result),
                   Product1 is Result * N2,
                   Product2 is (Result + 1) * N2,
                   Product1 =< N1, Product2 > N1, !.

이 프로그램은 합과 곱을 이용해서 정수 나누기를 실행한다. 대부분의 Prolog 시스템은 연산자로서 나누셈을 제공하기 때문에, 간단한 생성-검사 프로그램을 설명하는 것 외에는 이 프로그램은 실제로 유용하지 않다.

술어 is_integer 는 매개변수가 음이 아닌 정수에 사례화되는 한 성공한다. 만약 매개변수가 사례화되지 않았다면, is_integer 는 매개변수를 다음 정수 값으로 사례화한다.

그러므로, divide 에서 is_integer 는 생성자 부목적이다. 그것은 만족될 때마다 하나씩, 수열 0, 1, 2, ..., 의 원소를 생성한다. 모든 다른 것은 검사 부목적이다. 그들은 is_integer 에 의해 생성된 값이, 실제로, 첫 두 매개변수 N1 과 N2 의 몫인가를 결정하기 위해 검사한다. 마지막 부목적으로서 cut 의 용도는 간단하다. 일단 해가 발견되면 divide 가 다른 해를 찾을려는 시도를 막는다. is_integer 가 거대한 후보 수를 생성할 지라도, 하나만이 해이다. 그래서 여기서의 cut 은 두 번째 해를 생성할려는 쓸모 없는 시도를 막는다.

cut 연산자의 사용은 명령형 언어의 goto 사용과 비교되었다 (Van Emden, 1980). 비록 그것이 때때로 필요할지라도, cut 를 남용하는 것도 가능하다. 실제로, 그것은 때때로 명령형 언어 스타일로부터 영감을 받은 제어 흐름을 갖는 논리 프로그램을 만들기 위해 사용된다.

Prolog 프로그램에서 제어 흐름을 고칠 수 있는 능력은 결점이다. 왜냐하면 그것은 논리 프로그래밍의 중요한 장점 중에 하나 - 프로그램은 해가 발견되는 방법을 명기하지 않는다 - 에 해롭기 때문이다. 오히려, 그들은 간단하게 해결책의 형태를 명기한다. 이것은 프로그램을 만들기 쉽고, 읽기 쉽게 한다. 프로그램은 해결책이 결정되는 방법의 세부 사항과, 특히, 해결책을 생성하기 위해 계산이 수행되는 정확한 순서로 인해 복잡하게 되지 않는다. 따라서, 논리 프로그래밍이 제어 흐름 방향을 요구하지 않지만, 주로 효율을 위해서, Prolog 프로그램은 제어흐름을 자주 사용한다.

(2) 닫힌 세계 가정

Prolog 해 도출의 특성은 때때로 잘못된 결과를 생성한다. Prolog 에 관한 한 진리는 Prolog 의 데이터베이스를 사용하여 증명된 진리다. Prolog 는 데이터베이스 이외에 실세계의 지식은 없다. 데이터베이스에 충분한 정보가 없는 질의는 절대적으로 거짓이라고 가정한다. Prolog 는 주어진 목적이 참인 것을 증명할 수 있지만, 주어진 목적이 거짓인 것을 증명할 수 없다. Prolog 는 목적이 참이라고 증명할 수 없기 때문에 목적이 거짓임에 틀림없다고 간단하게 가정한다. 본질적으로, Prolog 는 참/거짓 시스템이 아니라 참/실패 시스템이다.

실제적으로 닫힌 세계 가정 (closed world assumption) 은 여러분에게 전혀 낯선 것은 아니다. 우리의 사법 시스템도 동일하게 동작한다. 용의자는 유죄로 증명될 때까지 무죄이다. 그들은 무죄라고 증명할 필요가 없다. 만약 재판이 어떤 사람이 유죄라고 증명하지 못하면, 용의자는 무죄로 인정된다.

닫힌 세계 가정의 문제점은 다음절에서 논의할 부정 문제와 관련되어 있다.

(3) 부정 문제

Prolog 의 다른 문제는 부정의 어려움이다. 두 개의 사실과 하나의 관계로 구성된 다음 데이터베이스를 살펴보자.

   parent (bill, jake).
   parent (bill, shelley).
   sibling (X, Y) :- parent (M, X), parent (M, Y).

이제, 다음 질의가 주어졌다고 가정하자.

sibling (X, Y).

Prolog 는 다음과 같이 응답을 할 것이다.

X = jake
Y = jake

그러므로, Prolog 는 jake 를 자기 자신의 형제라고 생각한다. 이것은 시스템이 첫 부목적 parent (M, X) 를 참으로 만들기 위해 처음에 M 을 bill 과 x 를 jake 로 사례화시켰기 때문에 발생한다. 그런 후, 두 번째 부목적 parent (M, Y) 를 부합하기 위해 다시 데이터베이스의 처음에서 시작하여, M 을 bill 에 Y 를 jake 에 사례화시킨다. 두 개의 부목적의 부합 모두가 데이터베이스 처음에서 시작하여 독립적으로 만족되기 때문에, 위와 같은 응답이 나온다. 이것을 피하기 위해, 만약 그들이 동일한 부모를 갖고, 그들이 같지 않을 때만, X 는 Y 의 형제라고 기술되어야 한다. 유감스럽게도, 논의하겠지만, Prolog 에서 X 와 Y 가 같지 않다는 것을 나타내는 것은 간단하지 않다. 가장 정확한 방법은 모든 원자 (atom) 쌍에 대해서 그들이 같지 않다는 사실을 첨가하는 것이다. 물론, 긍정적인 정보보다 부정적인 정보가 훨씬 많기 때문에 데이터베이스를 매우 커지게 한다. 예를 들면, 대부분의 사람들은 생일인 날보다 많은 364 일의 생일이 아닌 날은 가지고 있다.

간단한 대안적인 해결책은 다음과 같이 목적에 X 와 Y 는 동일하지 않다고 기술하는 것이다.

sibling (X, Y) :- parent (M, X), parent (M, Y), not (X = Y).

다른 상황에서는 해결책이 그리 간단하지 않다.

만약 해 도출이 부목적 X = Y 를 만족하지 않으면, Prolog not 연산자는 이 경우에 만족한다. 그러므로 만약 not 연산자가 성공한다면, 그것은 반드시 X 가 Y 와 동일하지 않다고 의미하지는 않는다. 더욱이 이것은 해 도출이 데이터베이스로부터 X 가 Y 와 같다는 것을 증명하지 못한다는 것을 뜻한다. 그러므로 Prolog not 연산자는 논리 NOT 연산자와 동일하지 않다. 이 경우에 (거짓이면) NOT 은 피연산자가 아마도 참이라는 것을 의미한다. 만약 Prolog not 연산자가 진정한 논리 NOT 연산자이고 우리가 우연히 다음과 같은 형식의 목적을 갖는다면, 이런 비동등 (nonequivalency) 은 문제를 발생시킬 수 있다.

not (not (some_goal)).

이것은 아래의 것과 동치다.

some_goal.

그러나 어떤 경우에는 그들은 같지 않다. 예를 들면, 다시 member 규칙을 살펴보자.

member (Element, [Element | _]) :- !.
member (Element, [_ | List] :- member (Element, List).

주어진 리스트 원소 중 하나를 찾기 위해, 우리는 다음과 같은 목적을 사용할 수 있다.

member (X, [mary, fred, barb])

이것은 X 를 mary 에 사례화시키고 프린트한다. 그러나 다음 목적을 사용한다면,

not (not (member (X, [mary, fred, barb]))).

다음 일련의 사건이 발생한다. 먼저, 안쪽의 목적이 성공하여, X 를 mary 에 사례화시킨다. 그런 후에 Prolog 는 아래와 같은 다음 목적을 만족시키려고 시도한다.

not (member (X, [mary, fred, barb])).

member 가 성공했기 때문에 이것은 실패할 것이다. 목적이 실패될 때, Prolog 는 항상 실패한 목적에 있는 모든 변수의 사례화를 취소하기 때문에 X 의 사례화도 취소될 것이다. 다음으로 Prolog 는 바깥쪽의 not 목적을 만족시키고자 시도하고, 그것의 매개변수가 실패했기 때문에 성공한다. 마지막으로 결과 X 가 출력된다. 그러나 X 는 현재 사례화되지 않고, 그래서 시스템은 그것을 나타낸다. 일반적으로 사례화되지 않은 변수는 밑줄이 선행하는 숫자의 스트링 형식으로 출력된다. 그래서 Prolog 의 not 이 논리적인 NOT 와 같지 않다는 사실은, 적어도 잘못될 수가 있다.

논리 NOT 이 Prolog 의 중요한 부분이 될 수 없는 기본적인 이유는 혼 크롤즈의 형식에 있다.

A :-

만약 모든 B 명제가 참이면, A 가 참이라고 결론지을 수 있다. 그러나 B 의 모두 또는 일부분의 참 또는 거짓에 상관없이, A 가 거짓이라고 결론 지을 수 없다. 긍정 논리는 긍정 논리로만 결론지을 수 있다. 그러므로 혼 크롤즈 형식의 사용은 어떤 부정적인 결론을 막는다.

(4) 본질적인 한계

4 절에서 언급한 것처럼 논리 프로그래밍의 본질적인 목적은 비절차적인 프로그래밍을 제공하는 것이다. 즉, 프로그래머가 프로그램이 수행할 것은 지정하지만 수행하는 방법을 지정하지 않는 시스템이다. 정렬을 위해 주어진 예제는 여기에 다시 작성하였다.

sort (old_list, new_list) ⊂ permute (old_list, new_list) ∩ sorted (new_list)
sort (list) ⊂ ∀j such that 1 ≤ j < n, list (j) ≤ list (j + 1)

이것은 Prolog 로 쉽게 작성할 수 있다. 예를 들면, sorted 의 부목적은 다음과 같이 표현된다.

   sorted ([]).
   sorted ([x]).
   sorted ([x, y | list]) :- x < = y, sorted ([y | list]).

위의 정렬 과정이 가지고 있는 문제는 그것이 정렬된 순서를 갖는 리스트를 생성시킬 때까지 주어진 리스트의 모든 치환을 열거하는 것 외에는 정렬시키는 방법을 모른다는 것이다.

지금까지, 아무도 정렬 리스트의 정렬을 위한 효율적인 알고리즘으로 변환시킬 수 있는 방법을 발견하지 못했다. 해 도출은 많은 흥미로운 일을 할 수 있지만, 확실히 이것은 아니다. 그러므로, 명령형 언어나 함수 언어처럼, 리스트를 정렬하는 Prolog 프로그램은 정렬이 수행되는 방법에 관한 세부사항을 기술하여야 한다.

이러한 모든 문제들이 논리 프로그래밍은 포기해야만 한다는 것을 의미하는가? 절대적으로 아니다. 그것은 많은 유용한 응용을 처리하는 능력이 있다. 더욱이 그것은 호기심을 자극하는 개념을 기반으로 하고 있고, 그러므로 그 자체로 흥미롭다. 마지막으로, 프로그램의 명세에서 how 가 아니라 what 만을 요구하는 논리 프로그래밍 언어 시스템을 허용하는 어떤 새로운 추론 기술이 개발될 가능성도 있다.

8. 논리 프로그래밍의 응용

이 절에서 일반적으로 논리 프로그래밍 특히 Prolog 의 현재 그리고 잠재적인 응용의 몇 개 부류를 간단히 서술하고자 한다.

(1) 관계형 데이터베이스 관리 시스템

관계형 데이터베이스 관리 시스템 (RDBMS) 은 데이터를 테이블 형식으로 저장한다. 데이터베이스에서의 질의는 종종 기호 논리의 형식을 갖는 관계형 계산법으로 나타낸다. 이런 시스템의 질의 언어는 논리 프로그래밍이 절차적인 것이라는 동일한 의미에서 비절차적이다. 사용자는 응답을 추출하는 방법을 기술하지 않는다. 오히려 사용자는 응답의 특성만을 기술할 수 있다. 논리 프로그래밍과 RDBMS 사이의 연결은 명백하다. 정보의 간단한 테이블은 Prolog 구조에 의해 기술될 수 있고, 테이블의 관계는 Prolog 규칙에 의해 편리하고 쉽게 기술된다. 검색 과정은 해 도출에서 본질적이다. Prolog 의 목적문은 RDBMS 를 위한 질의를 제공한다. 그러므로 논리 프로그래밍은 RDBMS 구현에 자연스럽게 부합한다.

RDBMS 구현에 논리 프로그래밍을 사용하는 장점 중 하나는 단지 단일한 언어만이 요구된다는 것이다. 전통적인 RDBMS 에서, 데이터베이스 언어는 데이터 정의, 데이터 조작, 질의를 위한 문장을 포함하며, 이 모두는 COBOL 과 같은 범용 프로그래밍 언어에 내장된다. 범용 언어는 데이터 처리나 입력, 출력 함수를 위해 사용되었다. 이런 모든 함수는 논리 프로그래밍 언어로 수행될 수 있다.

RDBMS 구현에 논리 프로그래밍을 사용하는 다른 장점은 추론 능력이 내장되어 있다는 것이다. 전통적인 RDBMS 는 명시적으로 데이터베이스에 저장되는 것 외에는 데이터베이스로부터 어떤 것도 추론할 수 없다. 그들은 사실과 추론 규칙을 가지고 있는 것이 아니라 사실만을 가지고 있다. 전통적인 RDBMS 과 비교해서 RDBMS 구현에 논리 프로그래밍을 사용하는 단점은 논리 프로그래밍 구현이 느리다는 것이다. 논리적 추론은 명령형 프로그래밍 기술을 사용한 일반 테이블 탐색 방법보다 시간이 단순히 더 걸린다.

(2) 전문가 시스템

전문가 시스템은 어떤 특별한 영역의 전문적인 지식을 가진 사람을 모방하기 위해 설계된 컴퓨터 시스템이다. 전문가 시스템은 사실의 데이터베이스, 추론 과정, 영역에 대한 어떤 경험, 시스템을 전문 상담자처럼 보이게 만드는 친숙한 인터페이스로 구성된다. 사람 전문가에 의해 제공된 초기 지식 베이스 외에도, 전문가 시스템은 사용되는 과정에서 지식을 학습하고, 따라서 데이터베이스는 반드시 동적으로 확장되는 능력이 있어야 한다. 물론 전문가 시스템은 정보가 필요하다고 결정될 때 부가적인 정보를 얻기 위해 사용자에게 질의하는 능력이 있어야 한다.

전문가 시스템 설계자를 위한 중심적인 문제 중에 하나는 데이터베이스의 피할 수 없는 불일치와 불완전성을 다루는 것이다. 논리 프로그래밍은 이런 문제를 다루는 데 아주 적합한 것처럼 보인다. 예로 들면, 디폴트 추론 규칙은 불완전성의 문제를 다루는 데 도움을 줄 수 있다.

Prolog 는 전문가 시스템을 만드는 데 사용될 수 있고 사용되어 왔다. Prolog 는 질의 처리의 기본으로서 해 도출, 학습 능력을 제공하기 위해 사실이나 규칙을 첨가하는 능력, 주어진 결과에 대한 이유를 사용자에게 알리기 위하여 추적 능력을 사용하여 전문가 시스템의 기본 욕구를 쉽게 만족시킬 수 있다. Prolog 에서 빠진 것은 부가적인 정보가 필요할 때 시스템이 사용자에게 그러한 정보를 질의하는 자동적인 능력이다.

전문가 시스템에서 가장 널리 사용되는 논리 프로그램의 사용 중에 하나는 Sergot (1983) 과 Hammond (1983) 에 의해 기술된 APES 로 알려진 전문가 시스템 제작 시스템이다. APES 시스템은 전문가 시스템을 구축하는 동안 사용자로부터 정보를 모으기 위한 매우 유연한 장치를 포함한다. 또한 질의에 대한 해답의 처리 과정 서술을 생산하기 위해 이차적인 인터프리터도 포함하고 있다.

APES 는 정부 사회 보장 프로그램의 규칙을 위한 전문가 시스템과 영국 시민권의 규칙의 명백한 좌표인 영국 국적법 (British nationality) 을 위한 전문가 시스템을 포함하여 여러 전문가 시스템을 생산하는 데 성공적으로 사용되고 있다.

(3) 자연어 처리

어떤 종류의 자연어 처리는 논리 프로그래밍으로 수행될 수 있다. 특히, 지능 데이터베이스와 다른 지능 지식 기반 시스템 같은 컴퓨터 소프트웨어 시스템에 대한 자연어 인터페이스는 논리 프로그래밍으로 편리하게 수행될 수 있다. 언어 구문 기술에 있어서 논리 프로그래밍의 형식은 문맥 자유 문법 (context-free grammar) 과 동일하다는 것이 알려졌다. 논리 프로그래밍 시스템에서의 증명 절차는 어떤 파싱 전략과 동일한 것으로 알려졌다. 실제로, 후향 체인 (backward chaining) 해 도출은 문맥 자유 문법에 의해 기술된 구조를 갖는 문장을 파싱하는 데 직접 사용할 수 있다. 또한 자연어의 어떤 의미론은 그 언어를 논리 프로그래밍으로 모델링함으로써 명백해질 수 있다는 것이 보여졌다. 특히, 논리-기반 의미 망의 연구는 자연어 문장의 집합이 클로즈 형식으로 표현된다는 것을 보였다 (Deliyanni and Kowalski, 1979). 또한 Kowalski (1979) 논리 기반 의미 망을 논의했다.

(4) 교육

교육 영역에서 7 살의 어린 아이들에게 논리 프로그래밍 언어 micro-Prolog 를 사용하는 방법을 가르치는 광범위한 실험이 행해졌다 (Ennals, 1980). 연구자들은 어린 아이들에게 Prolog 를 가르치는 것이 여러 가지 장점이 있다고 주장한다. 첫째, 이런 접근 방식을 사용해서 컴퓨팅을 소개하는 것이 가능하다. 또한 보다 명확한 사고와 표현을 가져다주는 논리 교육의 부수적인 효과를 가지고 있다. 이것은 수학의 방정식 풀이, 자연어를 위한 문법 다루기, 물리 세계의 규칙과 질서를 이해하는 것과 같은 다양한 주제를 학생들이 배우는 데 도움을 줄 수 있다.

매우 어린 아이들에게 논리 프로그래밍을 가르치는 실험은 명령형 언어에 경험이 많은 프로그래머보다 초심자에게 논리 프로그래밍을 가르치기가 쉽다는 흥미로운 결과를 도출하였다.

9. 결론

많은 사람들은 Prolog 가, 적어도 현 시점에서는 여전히 거대한 실험이라고 믿고 있다. 그러나 다른 많은 언어처럼 많은 지지자가 있다. 그들은 현재 사용중인 명령형 언어는 컴퓨터에 의해 해결되어야 하는 문제를 간단하게 대처할 수 없다는 소프트웨어 위기에 대한 적어도 해결책의 일부분이 될 수 있다고 믿는다 (Cuadrado and Cuadrado, 1985).

지지자들이 Prolog 가 명령형 언어보다 좋다고 믿는 몇 가지 이유 - 원래 Prolog 지지자 중에 하나인 Jacques Cohen (1985) 에 의해 언급되었던 이유 - 는 아래와 같은 것이다.

Prolog 는 논리에 기반하기 때문에, Prolog 프로그램은 좀더 논리적으로 조직화되고 작성될 수 있다. 이것은 적은 오류와 적은 유지 보수를 초래한다.
Prolog 처리는 자연스럽게 병렬적이고, 따라서 Prolog 인터프리터는 다중 프로세서 기계를 특별히 잘 이용할 수 있다.
Prolog 프로그램의 간결성 때문에, 개발 시간이 감소되고, Prolog 는 시제품을 위한 좋은 도구가 된다.

물론 이런 것에 동의하지 않는 사람도 있다. 많은 컴퓨터 과학자들은 몇 가지 작은 인공 지능 영역 밖에서는 Prolog 유용성에 회의적이다. 비록 현 시점에서는 확실히 명확하지 않지만, Prolog 는 인공지능의 주요한 언어인 LISP 를 대체할 것이라고 일부 사람들은 믿는다. Warren et al. (1977) 은 두 언어를 비교하였다.

요점 정리

기호 논리는 논리 프로그래밍과 논리 프로그래밍 언어를 위한 기초를 제공한다. 논리 프로그래밍의 접근 방법은 데이터베이스로서 사실과 사실 사이의 관계를 나타내는 규칙의 집합을 사용하고 새로운 명제의 타당성을 검사하기 위해, 데이터베이스의 사실과 규칙이 사실이라고 가정하여, 자동 추론 과정을 사용한다. 이런 접근 방법은 자동 정리 증명을 위해 개발된 접근 방법이다. Prolog 는 가장 널리 사용되는 논리 프로그래밍 언어이다. 논리 프로그래밍의 기원은 논리 추론을 위한 해 도출 규칙을 개발한 Robinson 에게 있다. Prolog 는 Edinburgh 의 Kowalski 로부터 약간의 도움을 받아 Marseille 의 Roussel 과 Colmeraur 에 의해 처음으로 개발되었다.

논리 프로그램은 해답의 특성은 주어지지만 해답을 얻는 과정은 주어지지 않는 것을 의미하는 비절차적이어야 한다.

Prolog 문장은 fact, 규칙 또는 목적이다. 대부분의 문장은 기본 명제인 구조와, 산술 표현식이 허용될지라도, 논리 연산자로 구성된다.

해 도출은 Prolog 인터프리터의 주요한 동작이다. 역행을 광범위하게 사용하는 이 과정은 주로 명제들의 패턴 부합을 포함한다. 변수가 포함되었을 때, 변수는 부합을 제공하기 위해 값으로 사례화된다. 이런 사례화 과정을 단일화라고 부른다.

현 상태의 논리 프로그래밍은 많은 문제점을 가지고 있다. 효율성의 이유와 무한 루프를 회피하기 위해, 프로그래머는 때때로 프로그램에서 제어 흐름 정보를 나타내야 한다. 또한, 닫힌 세계 가정과 부정의 문제가 있다.

논리 프로그래밍은 많은 다른 영역 - 주로, 관계형 데이터베이스 시스템, 전문가 시스템, 그리고 자연어 처리 - 에 사용되었다.

참고 문헌

Prolog 언어는 여러 책에서 기술되었다. 언어의 Edinburgh 형식은 Clocksin 과 Mellish (1997) 에 서술되었다. 마이크로 컴퓨터 구현은 Clark 과 McCabe (1984) 에 의해 기술되어졌다.

Hogger (1984) 는 일반적인 논리 프로그래밍의 영역에 관한 훌륭한 책이다. 그것은 이 장에 있는 논리 프로그래밍 응용 절 내용의 출처이다.

복습 문제

1. 형식 논리에서 기호 논리의 세 가지 주된 사용은 무엇인가?

2. 복합 항의 두 부분은 무엇인가?

3. 클로즈 형식에서 명제의 일반적인 형식은 무엇인가?

4. 해 도출과 단일화의 일반적인 (엄격하지 않은) 정의를 나타내시오.

5. 혼 클로즈 형식은 무엇인가?

6. 선언적 의미론의 기본 개념은 무엇인가?

7. Prolog 항의 세 가지 형식은 무엇인가?

8. Prolog 에서 사실문과 규칙문의 구문형식과 사용법은 무엇인가?

9. 데이터베이스에 있는 사실과 목적을 부합하는 두 가지 접근 방법을 설명하시오.

10. 다중 목적이 만족되는 방법을 논의할 때, 깊이 우선과 넓이 우선 탐색의 차이점을 설명하시오.

11. Prolog 에서 역행이 어떻게 수행되는지를 설명하시오.

12. Prolog 문장 "K is K + 1" 에 잘못된 것이 무엇인지 설명하시오.

13. 프로그래머가 해 도출 동안 패턴 부합의 순서를 제어할 수 있는 두 가지 방법은 무엇인가?

14. Prolog 에서 생성-검사 프로그래밍 전략을 설명하시오.

15. Prolog 에 의해 사용되는 닫힌 세계 가정을 설명하시오. 왜 이것이 한계인가?

16. Prolog 의 부정 문제를 설명하시오. 왜 이것이 한계인가?

17. 자동 정리 증명과 Prolog 추론 관계의 연결을 설명하시오.

18. 절차적 언어와 비절차적 언어의 차이점을 설명하시오.

19. Prolog 시스템이 역행을 수행하는 이유를 설명하시오.

20. Prolog 에서 해 도출과 단일화 사이의 관계는 무엇인가?

연습 문제

1. Prolog 와 Ada 의 데이터 타입의 개념을 비교하시오.

2. 다중 프로세서 기계가 해 도출 구현을 위해 사용되는 방법을 기술하시오. 현재 정의된 대로 Prolog 는 이 방법을 사용하는가?

3. 당신의 조부모와 모든 자손을 포함하여 당신 가계도를 Prolog 로 작성하시오. 물론 모든 관계를 포함해야 한다.

4. 두 세대를 통한 조부모 관계를 포함하여 가족 관계를 위한 규칙의 집합을 작성하시오. 이제 이 관계를 문제 3 의 f 사실에 첨가하고, 가능한 한 많은 사실을 제거하시오.

5. 만약 주어진 두 리스트 매개변수의 교집합이 공 리스트이면 성공하는 Prolog 프로그램을 작성하시오.

6. 주어진 두 리스트의 원소의 합집합을 갖는 리스트를 반환하는 Prolog 프로그램을 작성하시오.

7. 주어진 리스트의 마지막 원소를 반환하는 Prolog 프로그램을 작성하시오.

8. Scheme 과 Prolog 의 리스트 처리 능력의 유사한 두 가지 방법을 설명하시오.

9. Scheme 과 Prolog 의 리스트 처리 능력이 어떤 면에서 다른가?