인공지능 논리 Prolog Programming
- PROLOG : PROgramming in LOGic
[Chapter 1. Tutorial Introduction (길라잡이 입문)]
1.1 Prolog (프롤로그)
- Prolog는 아래와 같은 Symbolic Computation(기호 계산) 영역의 Application을 설계하는 데 유용하다.
1) 관계형 데이터베이스
2) 수리논리
3) 추상적 문제해결
4) 자연어 이해
5) 설계 자동화
6) 기호 방정식 풀이
7) 생화학 구조 분석
8) 인공지능 분야
- Prolog 프로그래밍은 전통적인 프로그래밍 언어를 통해 Algorithm(해법)을 Specify(명세)하는 것이 아닌,
풀어야 할 문제에서 어떠한 Formal(정형적인) 관계와 객체를 분석하고 어떤 해답과의 관계가 True인지를 구상하는 것이다.
- Prolog 프로그래밍은 컴퓨터에게 실행해야하는 일련의 단계를 '지시'하는 것 보다는, 주어진 문제에 대해 알려진 사실과 관계를 '기술'하는 것에 치중하는 방식이다.
1.2 Objects and Relationships (객체와 관계)
- Prolog에서는 Term(항)과 Uniform(일양) 자료구조를 제공한다.
- Prolog 프로그램은 일련의 Clause(절)로 구성되며, 각각의 절은 다시 Fact(사실), Rule(규칙)로 구성된다.
- Fact(사실)는 주어진 정보를 표현하는 절이다.
- Rule(규칙)은 문제의 Solution(해답)이 주어진 사실과 어떻게 연관되어 있는지 혹은 주어진 사실에서 어떻게 추론될 수 있는 지를 표현하는 절이다.
1.3 Programming (프로그래밍)
- Prolog 프로그래밍은 아래와 같은 작업들로 구성된다.
1) 객체와 객체 간 관계에 대한 Fact(사실) 명세하기
2) 객체와 객체 간 관계에 대한 Rule(규칙) 정의하기
3) 객체와 객체 간 관계에 대하여 Query(질문)하기
1.4 Facts (사실)
- Prolog에서는 Facts를 아래와 같은 표준 형태로 기술해야 한다.
1) 모든 관계와 객체 이름은 소문자로 시작해야 한다.
2) 관계를 먼저 쓰고, 객체들은 쉼표로 구분해서 쓰며, 객체들은 소괄호 쌍으로 둘러싼다.
3) 점문자 "."는 Fact절의 마지막에 위치해야 한다. "."은 "Period" 혹은 "Full Stop"이라 부른다.
- Prolog에서 하나의 이름은 하나 이상의 방법으로 해석될 수 있기 때문에 개발자가 해석을 결정해야 한다.
- 소괄호 안에서 기술되는 객체의 순서에 따라 의미가 달라질 수 있음에 유의해야 한다.
ex) likes(john, mary). john이 mary를 좋아한다.
ex) likes(mary, john). mary가 john을 좋아한다.
- Argument(인수): 각각의 Facts에서 소괄호 안에 위치하는 객체들의 이름을 의미한다.
- Predicate(술어): 소괄호 앞에 위치하는 Relationship(관계)의 이름을 의미한다.
ex) likes(john, mary). jonh, mary는 Arguments이고, likes는 Predicate이다.
- Database(데이터베이스): Facts(사실)들의 집합을 의미한다.
1.5 Questions (질문)
- Prolog에서 Question은 "?-"을 접두어로 한 문장으로 표현한다.
ex) ?- likes(peter, mary)
ex) ?- own(mary, book)
- 사용자가 Prolog 시스템에 질문을 하면, 프로그램은 데이터베이스를 검색하여, 질문에 나타난 Facts와 Unify(통일)되는 Facts를 찾는다.
- Predicate의 이름이 같고, 상응하는 위치의 Argument가 같을 때, Unify(통일)가 가능해진다.
- Prolog 프로그램은 Question과 Unify되는 Fatcs를 발견하면 "yes"로 응답하고, Question의 Fatcs가 데이터베이스에 없다면, "no"로 응답한다.
※ "no"와 "false"는 같은 의미가 아니다.
Existence error: procedure greek
- 데이터베이스에 기술된 Facts로 Question에 대한 충분한 답변을 도출하지 못할 때 주로 발생하는 오류이다.
1.6 Variables (변수)
- Prolog에서 변수는 이름을 지을 수 없는 불특정 다수의 객체를 나타내기 위해 사용된다.
- 변수가 포함된 Question을 받으면, 변수 값이 될 수 있는 객체를 찾기 위해 주어진 모든 Facts를 조사한다.
- 변수가 사용될 때, 변수가 표현하는 객체가 있는 경우, 그 변수는 Instantiation(사례화)되었다 표현한다.
- 변수가 Instantiation될 때, Place-Marker(위치 표식)을 남기게 된다. (목표 Facts가 발견된 위치를 표시, Backtracking에 이용하기 위해서이다.)
- 반대로, 변수가 표현하는 객체가 아직 정해지지 않은 경우, 그 변수는 Uninstantiation(해례화)되었다 표현한다.
- Prolog에서 변수는 대문자로 시작한다. (객체는 소문자로 시작한다.)
ex) ?- likes(john, X). john이 좋아하는 무엇(변수 X)을 묻는다.
- Prolog에서는 Question에 Unify된 Fatcs를 발견하면, 변수가 나타내는 객체를 출력한다.
- 출력 후, Prolog는 이후의 명령을 기다리는데, 이 때 Enter를 입력하면 출력이 Satisfy(충족)되었음을 표현하는 것이고,
Semicolon + Enter를 입력하면 Place-Marker부터 다시 Question에 대한 해답을 데이터베이스에서 탐색한다.
(이처럼, Place-Marker부터 다시 탐색을 시작하는 것을 Prolog가 주어진 Question을 re-Satisfy(재충족)하려 한다고 표현한다.)
1.7 Conjunctions (연접)
- 다수의 목적이 모두 Satisfy되는지(연접하는지)를 확인하기 위해, 여러 목적들 사이에 쉼표를 사용할 수 있다.
- 여기서, 쉼표(",")는 "그리고"를 의미한다.
- 일련의 목적들이 쉼표를 통해 구분되어 입력되었다면, Prolog는 각 목적을 순서대로 Satisfy하려 한다.
- 이 때, 각각의 목적들은 자신의 Place-Marker를 관리하고 있는 상태이다.
ex) ?- likes(john, mary), likes(mary, john). john과 mary가 서로 좋아하는지를 Question한다.
ex) ?- likes(john, X), likes(mary, X). john과 mary가 공통으로 좋아하는 것을 Question한다.
- Prolog는 각 목적에 대해 데이터베이스의 전 영역을 탐색하게 되는데, 첫 번째 목적은 Satisfy되었으나,
두 번째 목적이 Satisfy되지 않으면, Place-Marker를 이용하여 Backtracking(무름)을 수행한다.
- Backtracking시, Instantiation이 진행된 변수를 다시 Uninstantiation하여 다른 객체와 Unify될 수 있는 상태로 만든다.
ex) Instantiation 예시
1.8 Rules (규칙)
- Rules는 한 Facts가 다른 Facts 집합에 depends(의존)하고 있다는 것을 표현하거나, 정의를 표현하는 데 사용한다.
- Rules는 Head(머리)와 Body(몸)으로 구성되며, Fact와 같이 점 문자(".")로 끝마친다.
- Head와 Body는 ":-"으로 연결되어 있다.
- Head에는 Rule로 정의하고자 한 사실이 무엇인지를 기술한다.
- Body에는 일반적으로, Head가 참이 되기 위한 조건들의 Conjunction들을 기술한다.
- Body에는 Head에 명시되지 않은 변수도 사용할 수 있다.
- ":-"는 "if"로 해석할 수 있다.
- Prolog에서 주석은 /* ... */ 구문을 이용한다.
ex) likes(john, X) :- likes(X, wine). john은 X를 좋아한다 X가 wine을 좋아한다면.
여기서, Head는 likes(john, X)이고, Body는 likes(X, wine)이다.
1.9 Summary and Exercises (요약 및 연습문제)
[Chapter 2. A Closer Look (눈여겨보기)]
2.1 Syntax (문법)
- Prolog 프로그램은 일련의 Characters(문자)로 이루어진 Terms(항)으로 구성된다.
- Terms는 Constants(상수), Variables(변수), Structures(구조체)로 이루어질 수 있다.
Characters in Prolog (Prolog에서 허용한 문자)
| 영문 대문자 | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
| 영문 소문자 | a b c d e f g h i j k l m n o p q r s t u v w x y z |
| 숫자 | 0 1 2 3 4 5 6 7 8 9 |
| 특수기호 | ! " # $ % & ' ( ) = - ~ ^ | \ { } [ ] _ ` @ + ; * : < > , . ? / |
2.1.1 Constants (상수)
- 상수는 특정 Objects 혹은 특정 Relationship의 이름이다.
- 상수의 종류로는 Atom(원자), Numbers(수)가 있다.
Atom (원자)
- 문자와 숫자로 구성되거나(이 경우 소문자로 시작한다.),
특수 기호만으로 구성된다.
- 원자를 Single Quote로 묶으면, 원자명에 어떤 종류의 문자도 포함시킬 수 있게 된다.
Numbers (수)
- 일반적인 수치값을 의미하며, Scientific Notation(Exponential Notation) 또한 허용된다.
- 유리수나 임의의 Precision을 가진 수에 대한 연산과 특수 기능들이 정의된 Prolog Library 또한 존재한다.
2.1.2 Variables (변수)
- 변수는 영문 대문자 혹은 Underscore "_"로 시작한다.
Anonymous Variables (익명 변수)
- 변수가 필요하지만, 변수 이름을 사용할 필요는 없을 때 사용하는 변수이다.
- Anonymous Variables는 Underscore 하나로 대표된다. ("_")
- 같은 Terms 내에서의 Anonymous Variables들은 서로 Coreference를 하지 않는 독립적인 변수로 작용한다.
ex) ?- likes(_, John).
2.1.3 Structures (구조체) = Compound Term (합성항; 표준 Prolog 표기)
- 구조체는 Component(성분)로 로 구성되는 객체이다.
- 구조체로 객체에 문맥을 부여하여 구분을 쉽게 할 수 있다.
(Prolog에서 객체 구분 방법은 이름을 통한 구분법 말고는 존재하지 않는다.)
- 구조체는 Functor(함자)와 성분을 명세하여 작성된다.
- Functor는 일반적인 PL에서 데이터 형에 해당되는 개념이고, 성분은 쉼표(",")로 구분되어 소괄호 내에 위치한다.
ex) book(wuthering_heights, bronte). bronte 작가가 쓴 wuthering_heights라는 책에 해당하는 book 구조체 객체
※ Prolog에서는 Structures와 Facts의 문법이 동일하다.
- Facts와 Rules의 Arguments가 실제로 Structures의 Components들이다.
2.2 Characters (문자)
- Prolog가 인식하는 문자는 Printing Character(인쇄자), Non-Printing Character(비인쇄자) 두 종류이다.
- Printing(인쇄자)은 컴퓨터 터미널 화면에 기호로 나타난다.
- Non-Printing(비인쇄자)은 화면에 직접적으로 나타나지 않고, 출력 관련 동작을 수행한다. (공백, 출력, 줄 바꿈, 경적 등)
2.3 Operators (연산자)
- Prolog에서 연산자는 하나의 구조체이다.
ex) Prolog에서 Terms: 3 + 4 와 Terms: +(3, 4)는 논리적으로 동일한 표현이다.
- 연산자를 구분짓는 특성으로는 Position(위치), Precedence(우선순위), Associativity(결합성)이 있다.
2.4 Equality and Unification (상등과 통일)
Equality (=)
- 피연산자들이 "같다"를 의미하는 Built-In Predicate이다.
* Equality의 Side-Effect: 대입 기능
X = Y. 와 같은 Prolog Clause에서
X는 Instantiation되지 않은 상태이고, Y는 Instantiation되어 있는 상태라면,
X에는 Y가 가리키는 객체가 대입된다.
ex) rides(student, bicycle) = rides(student, X).
- X가 Instantiation된 적이 없거나, X가 bicycle을 의미한다면, 위 문장의 결과는 true이다.
- X가 Instantiation된 적이 없는 경우, Equality의 Side-Effect로 인해 X에 bicycle이 대입된다.
* 두 구조체가 같기 위한 조건: Functor, Component의 개수, 대응하는 모든 Component가 서로 같아야 한다.
- Instantiation되지 않은 두 변수 A, B에 대한 A = B. 절은 두 변수를 Co-Reference(공참조)하게 한다.
(즉, 두 변수가 같은 것을 참조하게 한다.)
2.5 Arithmetic (산술)
| X =:= Y | X와 Y가 같은 숫자를 나타낸다. |
| X =\= Y | X와 Y가 다른 숫자를 나타낸다. |
| X < Y | X가 Y보다 작다. |
| X > Y | X가 Y보다 크다. |
| X =< Y | X가 Y보다 작거나 같다. |
| X >= Y | X가 Y보다 크거나 같다. |
| X is Y | X가 Y 값을 가리키게 한다. |
| X + Y | X와 Y의 합 |
| X - Y | X와 Y의 차 |
| X * Y | X와 Y의 곱 |
| X / Y | X를 Y로 나눈 실수 몫 |
| X // Y | X를 Y로 나눈 정수 몫 |
| X mod Y | X를 Y로 나눈 나머지 |
2.6 Summary of Satisfying Goals (목적 충족시킴 요약)
Successful Satisfaction of a Conjunction of Goals (연접된 목적 충족시키기)
Consideration of Goals in Backtracking (무름 시 목적 처리)
Unification (통일)
[Chapter 3. Using Data Structures (자료구조 사용)]
- Recursion은 구조체 표현에 사용되거나, 프로그램 표현에 사용된다.
1) 구조체가 구조체의 component가 되는 경우
2) 프로그램 사본이 목적을 완수한 후에, 본 프로그램이 목적을 달성하는 경우
3.1 Structures and Trees (구조체 및 나무)
- Tree구조에서 Node는 Functor에, Edge는 Component에 대응된다.
3.2 Lists (목록)
- List는 Element(요소)로 구성된 임의의 크기의 Ordered Sequence(순서열)이다.
- 상수, 변수, 구조체, 목록 그 자체는 목록을 이루는 Element가 될 수 있다.
- List는 Empty List이거나, Head와 Tail 두 Component로 구성된 구조체이다.
- List의 Head는 List의 첫 번째 Element, Tail은 List의 첫 번째 Element를 제외한 나머지 모든 Element를 의미한다.
- List의 끝은 관습적으로 Empty List로 표현한다.
List Notation (목록 표기법)
- List의 Element들을 서로 쉼표(",")로 구분하고, 요소 전체를 대괄호("[ ]")로 묶는다.
ex) [X|Y]
- Head X와 Tail Y로 구성된 List를 의미한다.
- 즉, X는 단일 Element이며, Y는 0개 이상의 Element를 포함한 List이다.
※ 이러한 Head(One), Tail(Others) 구조로 인해, Prolog가 구조체를 탐색할 때, 자연스레 재귀적 탐색을 수행하게 된다.
3.3 Recursive Search (재귀 탐색)
3.4 Mapping (사상)
3.5 Recursive Comparison (재귀 비교)
3.6 Joining Structures Together (구조체 결합)
3.7 Accumulators (누산기)
3.8 Difference Structures (차이 구조체)
