[프로그래밍언어론] 11. Logic Programming Language (Prolog)

Logic Programming Language

기호 논리(symbolic logic) 에 기반을 두고 있는 프로그래밍 언어다.

논리적으로 맞는 답을 도출하는 것이 목표이다.

논리를 선언하는 것에 신경을 쓰고 (Declarative) 그 도출과정은 신경쓰지 않는다. (procedural)

(답이 뭐가 나와야 한다고만 할 뿐, 어떻게 내는지는 신경쓰지 않는다.)

 

논리형 프로그래밍 언어는 다음과 같은 것들로 구성된다.

 

Proposition (명제)

logical statement 로, 참 / 거짓으로 분류가 된다.

오브젝트와 오브젝트 간 관계로 구성되어 있다.

 

오브젝트는 상수, 변수로 구성된다.

상수는 오브젝트 자체를 나타내는 기호이다.

변수는 명령형 언어의 변수보다, 함수형 언어의 변수에 가깝다. 다른 시점에 다른 오브젝트를 표현할 수 있는 기호이다.

 

Atomic Propositions 는 더이상 나눌 수 없는 명제이다.

compound term 들로 구성되어 있다.

 

compuund term 은 수학적 함수 형태로 작성된 수학적 관계 관계의 요소를 말한다.

수학적 함수는 매핑을 제공한다.

 

 

예시를보면 위와 같다.

compound term 은 functor, parameter 2개로 구성된다.

functor는 이름을 나타내는 함수 심볼로, 위 그림에서 student, like 에 해당한다.

그 옆에 괄호에 들어가는 것은 parameteres로 오브젝트가 들어간다.

 

명제는 다음 두가지 형태로 선언될 수 있다.

1. Fact : 참일 것으로 가정하는 명제이다.

2. Query : 명제의 참/거짓을 판별할 명제이다.

 

2가지 이상의 atomic proposition 을 가지는 명제를 compound proposition 이라고 한다.

연산자에 의해 두개 이상의 명제들이 연결되어 있다.

 

 

논리형 연산자는 위와 같은 것들이 있다.

 

Symbolic Logic

로직은 명제를 표현하고, 명제사이의 관계를 표현하고, 다른 명제로부터 새로운 명제가 어떻게 도출되는지를 묘사한다.

logic programming 에서 사용되는 symbolic logic의 특별한 형태를 가리켜 'predicate calculus' 라고 부른다.

 

 

Clausal Form

똑같은 것을 설명하는 방식이 매우 많다.

그래서 명제를 나타내는 형태의 표준으로 clausal form 을 사용한다.

 

위와 같은 형태로 왼쪽에 결과, 오른쪽에 조건을 나열한다.

왼쪽에 있는 결과를 Consequent 라고 하고, 오른쪽에 있는 조건을 Antecedent 라고 한다.

 

명제를 사용하는 것은 기존에 알려진 axioms 와 theorems를 통해 새로운 theorems를 도출하는 것이 목표이다.

이때 명제를 통해 답을 찾는 것을 resolution 이라고 한다.

 

unification은 여러개의 답 중에 맞는 답 하나를 찾아가고 있다는 것을 의미한다.

답을 찾는 순간에는 instantiation 이 성공했다고 한다.

 

위 예시에서 A1을 참으로 만드는 답이 여러개가 있는데, 하나를 찾아서 instantiation 했다.

그런데 이 A1 이후에 찾은 A2 를 instantiation 했는데 참을 만족시키지 못한다면 A1으로 돌아가서 다른 값으로 바꿔봐야 한다.

이걸 backtrack 이라고 한다.

 

논리가 참인지 확인하는 방법 중에 귀류법도 있다. (contradiction) 하지만 프롤로그에서는 잘 사용하지 않는다.

프롤로그에서는 theorem proving 정리를 증명하는 방법을 사용한다.

이 방법은 Horn Clause 가 맞다/틀리다를 증명한다.

Horn clause는 조건 명제이면 머리가 있다고 해서 Headed Horn Clause 라고 하며 left side에 놓이는 하나의 atomic proposition을 말한다. 반대로 left side가 비면, Headless Horn Clause 라고 한다. (이는 facts 를 나타내기 위해 사용한다.)

 

로직 프로그래밍을 할 때는 horn clause 형태로 fact를 준 다음, 마지막에 쿼리를 주면 된다.

따라서 모든 문장의 형태가 똑같다.

 

논리형 프로그래밍은 Declarative semantics 를 특징으로 하므로, 답을 명확하게 기술하면 어떻게 나오는지 신경쓰지 않고, 프롤로그 런타임 시스템이 알아서 계산할 것이라고 생각하는 것이 특징이다.

(nonprocedural)

 

프롤로그 프로그래밍을 한다는 것은 사람들이 일반적으로 사용하는 말을 최대한 논리적인 표현으로 바꾼 뒤 이를 프롤로그 문법에 맞게 쓰는 것이다.

 

어떤 배열의 정렬에 대해서 위와 같이 논리 기호로 표시할 수 있다.

왼쪽이 결과고 오른쪽이 조건이다.

 

Prolog

프롤로그는 프랑스, 영국과 같은 유럽에서 시작된 언어이다.

프롤로그의 term은 다음과 같다.

 

- constant : atom 또는 정수이다.

- atom : 프롤로그의 기호 값이다. (symbolic value) 아톰은 소문자로 시작하는 문자, 숫자, 언더스코어의 조합 문자열로 구성되거나, `로 구분된 ASCII 문자로 구성된다.

 

- 변수 : 대문자로 시작하는 문자, 숫자, 언더스코어의 조합 문자열. 연산 중간 값을 잠깐 저장할 뿐이다.

- Instantiation :  변수에 값을 바인딩하는 것을 말한다. 

- Structure : atomic proposition을 나타낸다.

 

1. Fact

Headless Horn Clause 형태로, 가정을 위해 사용된다.

female ( Mary ) . 와 같이 사용한다.

 

2. Rule

Headed Horn clause 형태로, 가정을 위해 사용된다.

왼쪽에는 consequent 가 ( 결과) 오른쪽에는 antecedent 가 (조건) 이 나온다.

왼쪽에는 1개 term 이 나오지만, 오른쪽에는 여러 temr 이 나올 수도 있다. (conjunction)

conjunction은 logical and 로 구분된 여러 term들을 의미한다.

 

다음과 같은 형태로 사용된다.

변수를 사용하여 임의 오브젝트에 대한 일반적인 rule을 정의할 수도 있다.

 

3. Goal Statement

우리가 찾고 싶은 가정을 말한다.

이 가정이 맞는지 아닌지 주어진 fact 로부터 찾아보라고 시키는 것이다.

 

headless Horn 형태와 같다.

man(fred) 라고 하면 fred 가 남자인가? 하고 시스템에게 물어서 확인시키는 것이다.

 

conjunctive propositions 와, 변수를 사용해서도 목표를 찾을 수 있다.

father( X, mike) 라고 하면 mike의 아빠가 누구인가? 를 찾을 수도 있다.

 

이런 query를 goal 이라고 한다.

만약 골이 compound proposition 이면, 그 조건을 모두 만족해야 한다.

 

 

 

어떤 goal 이 맞는지 확인하기 위해서는 이렇게 여러 룰과 fact 의 체인을 거쳐야 할 수 있다.

체인을 따라가는 것을 inference 라고 한다.

sub goal 을 증명하는 것을 matching 또는 satisfying, resolution 이라고 부른다.

 

매칭할 때는 답을 찾을 때 일단 서브부터 맞는지 확인해야 한다.

이때 2가지 방법이 있다. 아래부터 찾아서 위로 가는 Bottom-up Resolution / 또는 Forwarding chaining

fact, rule에서 시작해서 goal 까지 가는 것이다.

 

거꾸로 위에서부터 내려오는 Top-down resolution 또는 Backward chaining

goal 부터 시작해서 fact rule을 체크한다.

 

이때 프롤로그의 쿼리가 top에 있기 때문에 보통 백워드 체이닝을 사용한다.

 

만약 하나의 goal 이 여러개의 subgoal로 이루어져있다면, 각각의 서브골을 체크할 때 DFS, BFS를 사용할 수 있다.

프롤로그는 보통 DFS를 사용한다. (BFS가 컴퓨팅 자원을 많이 소모하기 때문)

 

이때 열심히 서브골이 맞는지 확인하다가 backtracking이 발생한다.

서브골 중 하나가 만족하지 않으면 뒤로 돌아가서 서브골을 만족시키는 것 중에 다른 답을 이용해 다시 탐색을 시작한다.

따라서 백트레킹에 한번 걸리면 많은 시간과 공간을 필요로 한다.

 

또 아무리 논리형 언어라고는 해도 기본적인 산술 연산은 제공해야 한다.

그래서 is 연산자를 사용해 산술 연산의 결과를 변수에 저장할 수 있는 기능을 제공한다.

그런데 문제는 명령형 언어의 변수와 다르기 때문에 한번 변수에 값이 바인딩되면 그 변수에 다른 값을 바인딩할 수 없다.

산술 연산 예시

 

Trace

내장 structure 로, 각 단계의 instantiations 를 보여준다.

trace 에는 4가지 실행 이벤트가 있다.

 

- call : 골을 찾기 위한 값을 찾아서 시작해라

- Exit: : 값이 찾아진 경우

- Fail : 골이 실패한 경우

- Redo : 백트래킹이 발생한 경우

trace 예시

 

List

프롤로그의 기본 자료구조이다.

atom 과 atomic proposition, 다른 리스트를 나열한 것이다.

 

이것이 리스트이다.

| 를 사용해서 head 와 tail 을 분리할 수 있다.

 

 

append 메소드도 제공한다.

 

reverse, member 메소드도 제공한다.

 

여기에서 _ 는 익명 변수를 의미한다. (아무값을 의미)

 

프롤로그의 문제

우리가 넣은 팩트가 몇 개 안되는데, 팩트는 그게 다가 아니다.

- 아주 적은 수의 팩트만 갖고 답을 내고 있기 때문에, 닫힌 세계를 가정한다.

- 모르는 내용은 무조건 false로 취급한다.

- 정렬은 절차적인데, 프롤로그는 절차적이지 않은 언어라서 재귀 표현을 사용하는데, 재귀적으로 표현하니 이해하기 힘들다.

 

---

논리형 언어는 관계형 DBMS, 전문가 시스템, NLP 등에 사용된다.

 

symbolic logic 은 로직 프로그래밍의 기반이 된다.

로직 프로그램은 nonprocedural 해야 한다.

프롤로그는 fact rule goal 3가지 종류의 statement로 구성된다.

resolution 은 프롤로그 인터프리터의 주 기능이다.

논리형 프로그래밍은 현재 많은 결점이 있지만, 그럼에도 많은 분야에서 사용된다.