프롤로그 (프로그래밍 언어)
프롤로그(Prolog)는 논리형 프로그래밍 언어이다. 이름은 '논리 프로그래밍'을 의미하는 프랑스어: programmation en logique에서 온 것이다. 1973년 프랑스 마르세유대학교의 알랭 콜메르(Alan Colmerauer)가 개발한 언어로서, 논리식을 토대로 하여 오브젝트와 오브젝트 간의 관계에 관한 문제를 해결하기 위해 사용한다.
| 패러다임 | 논리형 |
|---|---|
| 설계자 | Alain Colmerauer |
| 발표일 | 1972년 |
| 최근 버전 | Part 1: General core-Edition 1 (1995년 6월) Part 2: Modules-Edition 1 (2000년 6월) |
| 운영 체제 | 크로스 플랫폼 |
| 파일 확장자 | .pl, .pro, .P |
| 주요 구현체 | |
| GNU Prolog, SWI-Prolog, .. | |
| ISO Prolog, Edinburgh Prolog | |
| 영향을 준 언어 | |
| 머큐리, 얼랭, 오즈, .. | |
프롤로그는 술어 논리식을 프로그램, 증명하는 것을 계산한다는 것으로 간주하는 관점에서 새로운 계산의 기술 형태를 취하고 있다. 즉, 프로그램 자체는 논리식의 모양으로 만들어지고, 그 프로그램을 실행하는 처리계가 그 증명기로 되어 있다.
추론 기구를 간결하게 표현할 수 있기 때문에 인공지능이나 계산 언어학 분야, 특히 프롤로그가 만들어진 목적이었던 자연언어 처리 분야에서 많이 사용된다.
데이터형
편집프롤로그의 데이터형은 아톰과 숫자, 이들의 조합인 텀으로 구성된다.
아톰(Atom)
편집일반적인 문자열이 아톰의 역할을 한다. 소문자로 시작하는 문자, 숫자, 밑줄(_)의 조합으로 나타내어지며, 일부 특수문자들의 조합 또한 아톰이 되기도 한다. 작은 따옴표(')로 둘러싸서 아톰을 나타낼 때도 있다.('+'는 atom이고, +는 연산자이다)
abc09, table_303_133_a, camelOnARoad
숫자
편집대부분의 Prolog 구현에서는 정수와 실수를 구분하지 않는다.
변수
편집대문자나 밑줄(_)로 시작하는 문자, 숫자, 밑줄의 조합으로 된 문자열이 변수의 역할을 한다. 일반적인 언어에서와 달리 변수는 어떤 값을 저장하는 메모리상의 공간을 의미하지 않는다.
ABC, A_variable, _AAA
_ 와 같이 밑줄이 하나만 단독으로 쓰이는 경우는 어느 값에나 매치되는 특수 변수가 된다.
텀(Terms)
편집텀, 혹은 스트럭처(Strucuture)는 프롤로그에서 복잡한 데이터를 표현할 때 쓰는 방법이다. 펑터(functor)라 불리는 아톰의 형태를 띤 것을 앞에 쓰고, 인자들(parameters)을 괄호 안에 나열하여 구성된다. 예를 들어 love(tom,mary)에서 love는 펑터이고, tom과 mary는 인자가 된다. 각 텀은 펑터와 인자의 수에 따라 구별되고, 펑터/인자수 (예를 들어 앞의 예의 경우 love/2)와 같이 표시한다. 인자의 수가 다르면 다른 텀이 되는데, 즉, aTerm(A)는 aTerm(A,B)와 매치되지 않는다는 데 주의해야한다.
리스트
편집리스트는 대괄호([])로 표시되며, 내부적으로는 '.'/2라는 텀을 재귀적으로 사용함으로써 표현된다.
[]는 빈 리스트이다.T가 리스트이고,H가 리스트의 한 요소라고 하면,'.'(H, T)라는 텀은 리스트가 된다.
H는 머릿요소가 되고, 리스트의 나머지 부분 전체는 꼬리가 된다.
예를 들어 [1,2,3]이라는 리스트는 '.'(1,'.'(2,'.'(3,[])))이라는 텀과 동일하다. 편의를 위해 [H|T] 같이 써서 리스트 맨 앞의 머릿 요소와 나머지 부분 전체를 분리할 수 있다. 즉 [1,2,3]이 [H|T]에 매칭되면 H는 1, T는 [2,3]이 된다.
역시 편의를 위해 다음과 같이 리스트를 사용할 수 있다.
- 리스트 만들기:
[abc, 1, f(x), Y, g(A,rst)] - 리스트
L1앞에 하나 붙이기:[abc | L1] - 리스트
L2앞에 여러 개 붙이기:[abc, 1, f(x) | L2] - 텀으로 표현:
'.'(abc, '.'(1, '.'(f(x), '.'(Y, '.'(g(A,rst), [])))))
문자열
편집따옴표 안에 둘러싸여진 문자열로, 일반적으로 ASCII 값들의 리스트로 표현된다.
사실(Fact)
편집프롤로그에서는 사실(Fact)과 규칙(Rule)들을 제공하여 데이터베이스를 만들고, 이 데이터베이스에 질의를 함으로써 프로그램을 수행하게 된다. 프롤로그에서는 어떤 하나의 사실을 true로 정의하는 것이 가장 기본적인 동작이다. 하나의 사실은 헤드(head)와 그에 딸린 인자들(arguments)로 구성되는 서술식(predicate)으로 표현 되는데, 예를 들면 다음과 같다.
cat(tom).
'tom'이 'cat'이라고 입력했다. 여기서 'cat'은 헤드이고, 'tom'이 인자가 된다. 위 사실이 프롤로그의 데이터베이스에 저장되면 사용자는 다음과 같이 질의를 할 수 있다.
'tom'이 'cat'인지 물어보고 싶다면,
?- cat(tom).
yes.
무엇이 'cat'인지 물어보고 싶다면,
?- cat(X).
X = tom;
yes.
이와같이 어떤 사실들을 프로그램이 알 수 있도록 할 수 있다. 하지만 세상의 지식을 프롤로그의 서술식으로 표현하는 데는 여러 가지 방법이 있을 수 있다. 예를 들면, 다음의 경우, 'pat'과 'sally'간에 'father'관계가 있을 때, 'pat'이 'sally'의 'father'임을 표현하는 데는 두 가지 방법이 있다.
father(pat,sally).
father(sally,pat).
두 가지 모두 'father'가 헤드이고, 'pat'과 'sally'가 인자이다. 이 중 첫 번째 경우는 관계-주어-목적어 로 표현한 것이고, 두 번째 경우는 관계-목적어-주어로 표현한 것이다. 둘 중 어느 형태를 사용할 것인지는 프로그래머의 선택이나, 이왕이면 하나의 프로그램 안에서는 일관된 순서를 갖는 것이 좋을 것이다.
몇몇 특수한 서술식은 내부적으로 미리 정의되어 입출력이나 운영체제와의 통신 같은 특수한 기능을 수행할 수 있도록 한다. 예를 들어 write는 화면에 문자열을 출력하기 위해 사용된다.
write('Hello').
위 식은 화면에 'Hello'를 출력한다.
규칙(Rule)
편집프롤로그 프로그램의 또다른 표현방법은 규칙 혹은 클로즈(clause)다. 규칙은 다음과 같이 표현된다.
light(on) :- switch(on).
":-"는 만약 ...하다면을 의미한다. 즉 위 규칙은 만약 switch(on)이라면, light(on)이라는 것을 의미한다. 룰에는 변수들이 사용될 수 있다. 예를 들어,
father(X,Y) :- parent(X,Y),male(X).
위 식은 만약 X와 Y가 parent관계이고, 이와 동시에 X가 male이면 X와 Y가 father관계라는 것을 의미한다. 그리고(and)는 ","로 표시되고, 또는(or)은 ";"로 표시된다. 여러 규칙을 또는 표시를 사용하여 한꺼번에 표시할 수도 있는데, 즉
a :- b;c;d.
는 아래와 같다.
a :- b.
a :- c.
a :- d.
하지만 아래와 같이는 쓸 수 없다.
a;b :- c.
계산
편집인터프리터에 질의를 입력하면, 그 질의에 맞는 사실을 찾으려고 노력한다. 만약 직접적인 사실이 주어지지 않은 경우, 해당 사실을 결론으로 갖는 규칙들을 만족시키기 위해 재귀적으로 계속 노력한다. 예를 들어,
sibling(X,Y) :- parent(Z,X), parent(Z,Y).
father(X,Y) :- parent(X,Y), male(X).
mother(X,Y) :- parent(X,Y), female(X).
parent(trude, sally).
parent(tom, sally).
parent(tom, erica).
parent(mike, tom).
male(tom).
female(trude).
male(mike).
위와 같이 사실과 규칙들을 정의하고, 다음과 같이 질의를 하였다고 하자.
?- sibling(sally, erica)
yes.
인터프리터는 먼저 sibling/2 규칙에서 X와 sally, Y와 erica를 매치 시키고, 그에 따라 parent(Z, sally)와 parent(Z, erica)를 동시에 만족시키기 위하여 노력하는데, parent(tom, sally)가 있으므로 Z와 tom을 매치시키고, parent(tom, erica)를 살펴보면 parent(tom, erica)가 있으므로, 주어진 조건을 모두 만족시키게 된다. 따라서 sally와 erica가 sibling 관계임을 확인하였으므로 yes를 출력한다.
male(X) :- father(X,_).
과 같이 쓰면, father 관계가 존재하기만 하면, father의 두 번째 인자가 무엇이든 상관 없이 X가 male이라는 것을 의미한다.
부정
편집만약 주어진 질의를 증명하는 어떤 사실과 규칙의 조합도 찾지 못한다면, 거짓이 된다. 이는 닫힌 세계 가정(Closed world assumption)이라 불리는데, 즉 프롤로그의 데이터베이스에 의해 사실임이 증명되지 않는다는 것은 거짓임을 의미한다는 것이다.
legal(X) :- NOT illegal(X).
와 같은 것은 가능한 모든 illegal을 찾아봄으로써 계산할 수 있다. 만약 어떤 illegal한 X도 찾지 못하는 경우, X는 legal이 된다. 이를 'Negation as failure'라고 한다.
예제
편집아래 예제는 ISO-PROLOG에 맞추어 작성된 것으로, 프롤로그 구현에 따라 문법이 조금씩 다를 수 있다.
split(H, [A|X], [A|Y], Z) :-
order(A, H), split(H, X, Y, Z).
split(H, [A|X], Y, [A|Z]) :-
not(order(A, H)), split(H, X, Y, Z).
split(_, [], [], []).
quicksort([], X, X).
quicksort([H|T], S, X) :-
split(H, T, A, B),
quicksort(A, S, [H|Y]),
quicksort(B, Y, X).
hanoi(N) :- move(N, left, center, right).
move(0, _, _, _) :- !.
move(N, A, B, C) :-
M is N-1,
move(M, A, C, B), inform(A, B), move(M, C, B, A).
inform(X, Y) :-
write([move, a, disc, from, the, X, pole, to, the, Y, pole]),
nl.
Computer Algebra
편집아래 예제는 프롤로그의 간편하고도 강력한 힘을 보여주기 위한 것이다.
미분 정의
편집 d(X,X,1) :- !. /* d x dx = 1 */
d(C,X,0) :- atomic(C). /* d c dx = 0 */
d(-U,X,-A) :- d(U,X,A). /* d -u dx = - d u dx */
d(U+V,X,A+B) :- d(U,X,A), d(V,X,B). /* d u+v dx = d u dx + d v dx */
d(U-V,X,A-B) :- d(U,X,A), d(V,X,B). /* d u-v dx = d u dx - d v dx */
d(C*U,X,C*A) :- atomic(C), C \= X, d(U,X,A), !. /* d c*u dx = c*d u dx */
d(U*V,X,B*U+A*V) :- d(U,X,A), d(V,X,B). /* d u*v dx = u*d v dx + v*d u dx */
d(U/V,X,A) :- d(U*V^(-1),X,A). /* d u/v dx = d (u*v)^-1 dx */
d(U^C,X,C*U^(C-1)*W) :- atomic(C), C \= X, d(U,X,W). /* d u^c dx = c*u^(c-1)*d u dx */
d(log(U),X,A*U^(-1)) :- d(U,X,A). /* d ln(u) dx = u^-1 * d u dx */
적분 정의
편집 i(0,X,0) :- !. /* Int 0 dx = 0 */
i(X,X,(X*X)/2) :- !. /* Int X dx = (X^2)/2 */
i(C,X,C*X) :- atomic(C). /* Int c dx = c*x */
i(-U,X,-A) :- i(U,X,A). /* Int -U dx = - Int U dx */
i(U+V,X,A+B) :- i(U,X,A), i(V,X,B). /* Int U+V dx = Int U dx + Int V dx */
i(U-V,X,A-B) :- i(U,X,A), i(V,X,B). /* Int U-V dx = Int U dx - Int V dx */
i(C*U,X,C*A) :- atomic(C), C \= X, i(U,X,A), !. /* Int cU dx = c (Int U dx) */
i(X^C,X,(X^(C+1))/(C+1)) :- atomic(C), !. /* Int x^c dx = x^(c+1)/(c+1) */
i(U,V,U*V-A) :- d(V,U,A), !. /* Int u dv = u*v - Int v du */
정리하기 위한 규칙들
편집 s(+,X,0,X). /* x + 0 = x */
s(+,0,X,X). /* 0 + x = x */
s(+,X,Y,X+Y). /* x + y = x + y */
s(+,X,Y,Z) :- integer(X), integer(Y), Z is X+Y. /* x + y = z <- 값 계산 */
s(*,_,0,0). /* 모든 값 * 0 = 0 */
s(*,0,_,0). /* 0 * 모든 값 = 0 */
s(*,1,X,X). /* 1 * x = x */
s(*,X,1,X). /* x * 1 = x */
s(*,X,Y,X*Y). /* x * y = x * y */
s(*,X*Y,W,X*Z) :- integer(Y), integer(W), Z is Y*W.
s(*,X,Y,Z) :- integer(X), integer(Y), Z is X*Y. /* x * y = z <- 값 계산 */
정리하기
편집 simp(E,E) :- atomic(E), !.
simp(E,F) :- E =.. [Op, La, Ra], simp(La,X), simp(Ra,Y), s(Op,X,Y,F).
/* =..는 텀을 리스트형태로 바꾸어주는 것으로, E가 x * y 일 때 E =.. [*,x,y]이다. */