Prolog 논리 프로그래밍 언어

Prolog 개요

 논리 프로그래밍 언어

 Prolog는 범용 언어가 아니라 predicate calculus를 사용한 논리 문제를 효과적으로 표현하기 위하여 개발된 것이다.

 1970년대에 프랑스 마르세유 대학의 콜메로에

   (A. Colmerauer)와 P. Roussel이 수학 논리에 기반을 둔 프로그래밍 언어인 Prolog를 개발하였다.

Prolog 특징 

 주어진 사실을 선언하고, 원하는 문제를 질의하는 형식. Prolog 프로그램은 정보와 추론 규칙만을 기술하고, 실행순서를 기술하지 않으므로, 초고급언어(혹은 5세대 언어)라고 일컬어진다.

 Prolog는 인공지능 분야에서 효과적으로 사용되었으나, 큰 프로그램의 경우에 프로그램 수정이 어렵고 실행시간이 오래 걸린다는 단점이 있다.

Prolog 설치

 설치 Prolog

• SWI-Prolog

 SWI-Prolog site

• http://www.swi.psy.uva.nl/projects/SWI-Prolog/

 SWI-Prolog 설치

• W32PL5213 응용프로그램 아이콘을 누른다.

• 모든 물음 항목에 대해서 "OK"를 누른다.

Prolog 실행

 Prolog 프로그램을 작성한다.

• 메모장을 이용한다.

• 확장자는 PL이다.

 Prolog 프로그램을 더블 클릭한다.

 직접 입력하려면

?-[user].하고 나서

 |: 상태 될 때 직접 입력할 것.

 ^ D 누르면 ?-로 복귀

Prolog 구성 요소

 객체 

 관계 

 변수

 논리곱

 사실과 규칙

사실

 가장 단순한 종류의 문을 사실(fact)이라 하며, 사실은 객체 간의 성립하는 관계를 기술하는 수단.

 "John이 Mary를 좋아한다."는 사실을 Prolog에서는 다음과 같이 표현한다.

likes(john, mary).

 모든 관계와 객체들의 이름은 반드시 소문자로 써야 한다.

 관계를 먼저 쓰고, 객체들은 쉼표로 구분하며, 괄호로 묶어야 한다.

 "."이 사실의 끝에 나타나야 한다.

사실 

valuable(gold).

• 금은 귀중하다.

female(jane).

• Jane은 여성이다.

owns(john, gold).

• John이 금을 소유하고 있다.

father(john, mary).

• John은 Mary의 아버지이다.

gives(john, book, mary).

• John이 Mary에게 책을 주었다.

질문

 어떤 사실을 갖게 되면, 그에 대한 여러 질문을 할 수 있다.

?- owns(mary, book).

 질문이 주어지면 사실로 이루어진 데이터베이스를 탐색하여 사실과 부합하면 Yes라고 반응하고 그렇지 않으면 No라고 반응한다.

질문

<예제 9>

likes(joe, fish).

likes(joe, mary).

likes(mary, book).

likes(john, book).

?- likes(joe, money).

No

?- likes(mary, joe).

No

?- likes(mary, book).

Yes

<예제 9>를 실행해 보자. 사실을 입력하고 다양한 질문을 하기 바란다.

변수

 사실에서 객체가 무엇인지를 알기 원할 때는 변수 X를 사용한다.

?- likes(john, X).

 X에 해당하는 여러 개의 객체가 있을 경우에는 “ ; "를 입력하여 다른 객체를 계속 찾는다는 것을 나타낸다.

변수 

<예제 10>

likes(joe, fish).

likes(mary, book).

likes(mary, flower).

?- likes(joe, X).

X = fish 

Yes

?- likes(mary, X).

X = book ;

X = flower ;

No

<예제 10>실행. 사실을 입력하고 다양한 질문을 하기 바란다.

논리곱 

 단순 명제를 논리곱으로 합성하여 합성 명제에 대한 질문을 할 수 있다.(“,” 사용, 목표들이 or로 결합되는 경우 ‘;’로 표시)

?- likes(john, mary), likes(mary, john).

 논리곱을 이용한 질문에 변수를 사용할 수도 있다.

?- likes(john, X), likes(mary, X).

논리곱

<예제 11-1>  4명의 남학생과 3명의 여학생을 짝짓기하기. 가능한 모든 해를 구할 것.

      possible_pair(X,Y):-boy(X), girl(Y).

boy(영수).

boy(철수).

boy(학민).

boy(호섭).

girl(영희).

girl(려화).

girl(해려).

질의 ?- possible_pair(X,Y).

 

논리곱 (2)

<예제 11-2>

likes(mary, food).

likes(mary, wine).

likes(john, mary).

likes(john, wine).

?- likes(mary, john), likes(john, mary).

No

?- likes(mary, X), likes(john, X).

X = wine 

Yes

 <예제 11>실행. 사실을 입력하고 논리곱이 있는 질문을 하기 바란다.

논리곱 – 답을 찾아 가는 과정

규칙 

 규칙(rule)은 어떤 사실이 다른 사실들의 모임에 의존한다는 것을 말하고 싶을 때 사용한다.

 예를 들어 "John은 와인을 좋아하는 사람은 누구나 좋아한다."라고 할 때 다음과 같이 Prolog 규칙을 작성할 수 있다.

likes(john, X) :- likes(X, wine).

 규칙을 나타내는 기호인 ":-"는 if로 발음하고 해석하면 된다.

 또 다른 예로는 "John은 와인을 좋아하는 어떤 여성도 좋아한다."는 다음과 같이 작성한다.

likes(john, X) :- female(X), likes(X, wine).

규칙 

<예제 12>

male(albert).

male(edward).

female(alice).

female(victoria).

parents(edward, victoria, albert).

parents(alice, victoria, albert).

sister_of(X, Y) :- female(X), parents(X, M, F), parents(Y, M, F).

?- sister_of(alice, edward).

Yes

?- sister_of(alice, X).

X = edward 

Yes

 <예제 12>실행. 사실을 입력하고 논리곱이 있는 질문을 하기 바란다.

간단한 산술 연산

 +(7, X)

 A is B / 17 + C. 

 Sum is Sum + Number. (유효하지 않음)

 예

 add_em_up(X,Y,Sum):-    Sum is X+Y.

  multiply_em(X,Y,Product):- Product is X*Y. 

 질의 add_em_up(35,24,Sum).

 결과 Sum = 59

       

간단한 산술 연산 예

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

     

     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). 로 질의

가족 관계 탐색

<예제 13-1>

male(albert).

male(edward).

female(alice).

female(victoria).

parents(edward, victoria, albert).

parents(alice, victoria, albert).

sister_of(X, Y) :- female(X), parents(X, M, F), parents(Y, M, F).

 가족 관계를 나타내는 다양한 규칙을 만들어 보라.

가족 관계 탐색

<예제 13-3>

father(cheolsu, youngduk).  /* 사실 */

father(youngsu, youngduk).

father(youngduk, youngho).

father(hoduk, youngho).

father(minhee, youngmin).

father(minyoung, youngmin).

mother(younghee, minhee).

mother(youngsun, minhee).

male(cheolsu).

male(youngduk).

male(hoduk).

male(youngho).

male(youngmin).

male(minyoung).

female(younghee).

female(minhee).

      female(youngsun).

삼단 논법

<예제 14>

man(socrates).

mortal(X) :- man(X).

 다양한 삼단 논법을 작성하여 보아라.

[참고문헌]

  W.F.Clocksin, C.S.Mellish, Programming in Prolog, Springer-Verlag, 1981

 백트랙킹(backtracking)

 Prolog는 주어진 목표에 만족하는 답을 모두 찾음

 목표가 만족되는 경우 다른 답을 찾기 위해, 목표가 만족되지

      않는 경우 만족되는 답을 찾기 위해 데이터베이스를 다시

      탐색 : 되돌림(backtracking)

백트랙킹

<예제 15-1> turbo-prolog syntax

    predicates

            boy(symbol)

            girl(symbol)

            possible_pair(symbol, symbol)

        clauses

             boy(john).

             boy(mark).

             boy(ted).

             boy(andy).

             girl(sandy).

             girl(alice).

             girl(mary).

             possible_pair(X, Y) :- boy(X), girl(Y).

       goal

              possible_pair(X, Y).

백트랙킹

<예제 15-2>

    predicates

              boss(symbol, symbol)

        clauses

              boss(dick, harry).

              boss(tom, dick).

              boss(ann, mary).

              boss(mary, harry).

        goal 

           boss(X, Y), boss(Y, Z).

               

백트랙킹

 Backtracking with rules

<예제 15-3>

clauses

             department(tom, sales).

      department(harry, production).

             manager(dick, sales).

             manager(mary, production).

             boss(B, E) :- department(E, D), manager(B, D).

       goal 

           boss(X, Y).

                           

       

 컷(cut)과 fail

 컷(cut)

      - Backtracking을 통해 다른 해를 구하는 것을 막을 필요가 있을 때 사용(backtracking 방지)

      - 원하는 해를 찾은 후에 더 이상 다른 해를 찾는 것이 불필요할 때

         사용

      - !로 표시

컷(cut)과 fail

<예제 16-1>

predicates

              temperature(integer, symbol)

       clauses

               temperature(X, normal) :- X <= 25.

               temperature(X, warm) :- X <  30.

               temperature(X, warning) :- X > 35.

       goal

              temperature(20, Y).

                 

       

컷(cut)과 fail

*   cut(!)을 삽입한 경우 :temperature(X, normal) :- X <= 25, !

       goal

              temperature(20, Y).

                 

컷(cut)과 fail

 fail

     - 부 목표가 있을 때 backtracking을 발생시키려면 fail을 사용.

     - backtracking을 강제로 시켜 줌

 

컷(cut)과 fail

<예제 16-2>

domains

              name = symbol

     predicates

              father( name, name)

              everybody

     clauses

               father(leonard, katherine).

               father( carl, jason).

               father(carl, marilyn).

               everybody :- 

                     father(X, Y),

                     write(X),write(' is '),write(Y),

                     write(' ''s father.'),nl,

                     fail.  

재귀적 구조

 규칙의 머리가 같은 규칙의 몸체에도 나타나는 구조

<예제 17-1>

predicates

             sum_to(integer, integer)

       clauses

              sum_to(1,1) :- !. 

              sum_to (N, Res) :- N1 = N-1, sum_to (N1, Res1),

                                                                Res = Res1+N.

        goal 

              sum_to (5, X) .

                

                 

선택구조

 CASE나 IF-THEN-ELSE와 비슷한 기능을 갖는 program

<예제 18>

     predicates

              classify(integer, symbol)

         clauses

              classify(0, zero).

              classify(X, negative) :- X < 0.

              classify(X, positive) :- X > 0.

          goal

              classify(5, What).

                 

        

재귀적 구조

<예제 17-2>

predicates

                factorial(integer,integer)

         clauses

                factorial(1,1).

                factorial(N, A) :- 

                          N1 = N-1,

                          factorial(N1, A1), A = N * A1.

         goal 

                factorial(5, X).

                          

 리스트

 리스트의 구성 및 표현

리스트 : ordered sequence of elements 

               비수치의 응용분야 프로그래밍을 위한 자료구조

리스트의 원소 : 상수, 변수, 구조, 다른 리스트

(ex)          List                  Head                 Tail

           [a, b, c, d]                  a                 [b, c, d]

                [a]                         a                     [ ]

                [  ]                     no head              [ ]

        [[the, cat], sat]         [the, cat]             [sat]

        [the, [cat, sat]]            the               [[cat, sat]]

   [the, [cat, sat], down]      the         [[cat, sat], down]

         [X+Y, x+y]             X+Y                  [x+y] 

리스트

 리스트의 기본 술어

 리스트의 생성

<예제 19-1>

   domains

         list = integer*

    predicates

         make_list(integer, list, list)

    clauses

        make_list(Head, List, [Head|List]).

    goal

     make_list(1, [2,3], New_list).  

          

리스트

(2) 리스트의 결합

<예제 19-2>

     domains

         list = symbol*

     predicates

         append(list,list, list)

     clauses

         append([ ], L, L).

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

     goal

          append([a,b,c], [d,e,f], L).

            

리스트

(3) 리스트의 반전

<예제 19-3>

   domains

         list = symbol*

    predicates

         reverse(list, list)

         reverse1(list, list, list)

   clauses

         reverse(L1, L2) :- reverse1(L1, [ ], L2).

         reverse1([ ], L, L).

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

   goal

        reverse([a,b,c,d], L).

           

리스트

(4) 구성요소의 확인

     <예제 19-4>

 domains

            list = symbol*

       predicates

            member(symbol, list)

       clauses

            member(X, [X| _ ]).

            member(X, [ _ |Y]) :- member(X, Y).

       goal

           member(d, [a, b, c, d, e]).

       goal

           member(2, [3, a, 4, f]).

             

리스트

(5) 리스트 선두에 추가

<예제 19-5>

       domains

            list = symbol*

       predicates

           cons(symbol, list, list)

       clauses    

           cons(X, L, [X | L]).

      goal

           cons(a, [b, c, d, e], L).

               

리스트

(6) 리스트의 마지막 항 검색

<예제19-6>      

domains

           list = symbol*

      predicates

           last(symbol, list)

     clauses

           last(X, [X]).

           last(X, [ _ | Y|]) :- last(X, Y).

     goal

           last(X, [talk, of, the, town]).

               

리스트

(6) 짝수 구하는 프로그램

리스트에서 짝수만 골라내는 프로그램을 작성하여라.

     clauses

           evennumbert(X, [X|_]) :- 0 is X mod 2.

          evennumbert(X, [_|Y]) :- evennumber(X,Y).

    goal

           evennumber(X, [1,2,3,4,5]).