[PLT/프로그래밍언어론] 13. Logical Programming

13. logical 1

#PLT

논리 프로그래밍 (Logic Programming)

프로그래밍 언어 이론 (Programming Language Theory)

목차 (Topics)

• 논리 프로그래밍 소개 (Logic Programming Introduction)
• 프로로그 기초 (Prolog Basics)
• 1순위 논리 (First-order Logic)
• 치환과 통일 (Substitution and Unification)

⠀

논리 프로그래밍 소개 (Logic Programming Introduction)

알고리즘이란 무엇인가? (What is Algorithm?)

• 알고리즘 (Algorithm) = 논리 (Logic) + 제어 (Control)
• 로버트 A. 코월스키 (Robert A. Kowalski)
• 논리는 "무엇을" 해야 하는지를 나타내고, 제어는 "어떻게" 해야 하는지를 나타냄
• 명령형 언어에서는 일반적으로 알고리즘의 두 부분을 모두 고려함

⠀

논리 프로그래밍 (Logic Programming)

• 컴퓨터(abstract machine)가 "제어 (Control)" 부분을 처리할 수 있다고 가정하면 어떨까?
• 그러면 "논리 (Logic)", 즉 해야 할 일에 집중할 수 있음
• Logic Programming에서는 프로그래머가 Logic Specification만 제공함
• Abstract Machine는 Logical Deduction을 사용하여 specification을 만족하는 해(solution)를 찾음

프로로그 (Prolog)

• PROgramming in LOGic의 약자
• 최초의 논리 프로그래밍 언어 중 하나
• 다양한 버전의 Prolog 구현체가 존재함
• 이 모든 구현체는 efficiency을 위해 일부 "불순한" 구조(impure constructs. handle “control”)를 포함함
• 그럼에도 불구하고 놀라울 정도로 simplicity와 clarity를 즐길 수 있음

⠀

실생활 예제 (A Real-life Example)

• Null Pointer Exception (NPE)이 발생했을 때, 그 root cause를 찾을 수 있을까?
  • 즉, 예외를 실제로 유발한 코드의 부분은 어디일까?
• 단순히 스택 트레이스를 보는 것만으로는 충분하지 않을 때가 있음
  • 예를 들어, 실제 fault는 Person 클래스의 8번째 줄에 있지만, 짧은 스택 트레이스에는 나타나지 않음
• 이를 자동으로 처리하여 너무 신경 쓰지 않아도 될까?
  • 아마도 ChatGPT에게 물어볼까?

⠀

프로로그 솔루션 (Prolog Solution)

• 코드와 테스트 실행에서 사실(facts)을 수집할 수 있음
• NPE의 근본 원인을 추적하기 위한 규칙(rules)을 정의할 수도 있음
• NPE에 대한 쿼리를 통해 논리적 추론(Logical Deduction)을 사용하여 결함을 정확히 위치시킬 수 있음

⠀

항상 하지만... (There is Always But...)

• 매혹적인 simplicity과 우아한 clarity을 위해 performance를 sacrifice해야 함
• 해(solution)를 찾기 위해 추상 기계가 수행하는 계산은 매우 복잡할 수 있음
• 결함 위치를 찾는 이전의 솔루션은 77번의 추론 단계(inference steps)가 필요함
  • 이는 수동으로 정리된 사실을 가진 매우 간단한 예제임
• 자동으로 수집된 fact를 사용하면 결함을 찾는 데 232단계가 필요함

⠀

프로로그 기초 (Prolog Basics)

프로로그 용어 (Prolog Terms)

• 사실 (Facts): child(a). child(b). female(b).
• 규칙 (Rules): daughter(X) :- child(X), female(X).
  • ex) child(Person), female(Person)
  • comma (,)는 logical and
• 변수 (Variables): 대문자 또는 밑줄('_')로 시작. 통일(unification)에 의해 인스턴스화될 수 있음
• Knowledge Base 또는 데이터베이스 (database): facts와 rules의 집합
  • child('John'). child('Jane'). female('Jane'). daughter(X) :- child(X), female(X).
• Queries: 목표(goals)라고도 하며, knowledge base와 함께 증명되어야 함
  • ?- daughter(Y).
  • Y = 'Jane'
• 주의: dot(.)이 필요함, 이는 C나 Java의 세미콜론(;)과 유사함

프로로그 프로그램은 어떻게 작동하는가? (How Does a Prolog Program Work?)

• 오른쪽에 있는 지식 기반(KB)을 고려함. 처음 두 줄은 규칙을 나타내고, 나머지 줄은 사실을 나타냄
• 쿼리 예제: ?- has_motive(X, burglary).
• has_motive(X, burglary)를 만족하는 X에 대한 치환(substitution)이 있는가?

• ?- culprit(ethan_hunt, Y).
  • X = ethan_hunt, T = Y.
• suspect(ethan_hunt, Y), evidence(ethan_hunt, Y).
  • no_alibi(ethan_hunt), has_motive(ethan_hunt, Y).
  • evidence(ethan_hunt, burglary).
  • Y = burglary.

• ?- culprit(john_wick, kidnap).
  • false
• ?- has_motive(X, burglary).
  • X = ethan_hunt
• ?- culprit(ethan_hunt,Y).
  • Y = burglary
• ?- suspect(X, murder).
  • X = hannibal_lecter
  • X = dexter_morgan
  • false

⠀

치환과 통일 (Substitution and Unification)

• 쿼리 culprit(X, Y)에 대해, 우리가 찾고자 하는 것은 X, Y에 대한 substitution임
  • 예: X = ethan_hunt, Y = burglary.
• 우리가 하고자 하는 것은 주어진 쿼리에 대한 통일자(unifier)를 찾는 것, 즉 통일(unification)
  • 이는 주어진 모든 규칙과 사실을 만족하는 치환을 찾는 것과 유사함
  • (T=Y가 Unifier. 즉, 변수를 구체화하는 값의 집합)
  • (Unification: 주어진 두 항이 같은 구조를 가지도록 만들기 위해 변수에 값을 할당하는 과정)
• 이는 방정식 시스템의 해(solution)를 찾는 것과 매우 유사함
  • 예: x + 2y = 4
  • x = 0, y = 2.
  • x + y = 2

증명 탐색 (Proof Search)

지식 기반 (KB)

• sweet(cookie).
• sweet(y_chicken).
  
• salty(cookie).
• salty(y_chicken).
  
• spicy(y_chicken).
  
• delicious(X) :- sweet(X), salty(X), spicy(X).
• 쿼리: ?- delicious(Y).

⠀

증명 탐색 (Proof Search)

일단 Y 대신 임시 변수 _G1을 둔다.
sweet(_G1) 을 만족하는게 cookie와 양념치킨이다.
일단 _G1에 cookie를 넣고 진행한다
cookie가 spicky하다는 KB가 없으므로 fail한다.

• from top to bottom, left to right으로 진행함

지식 기반 (KB):

• sweet(cookie).
• sweet(y_chicken).
• salty(cookie).
• salty(y_chicken).
• spicy(y_chicken).
• delicious(X) :- sweet(X), salty(X), spicy(X).

증명 탐색 (Proof Search)

다시 _G1 선택 지점으로 돌아가서 _G1에 양념치킨을 넣는다.

• 프로로그는 선택 지점(choice points)을 추적함
• 마지막 선택 지점으로 돌아가서(backtracking) 다른 옵션을 시도함
• empty leaf nodes는 가능한 solution을 의미함
• 루트에서 빈 리프로 가는 경로는 변수의 인스턴스화를 보여줌

다중 해 (Multiple Solutions)

지식 기반 (KB)

• loves(jane, john).

• loves(jane, jack).
• jealous(A, B) :- loves(C, A), loves(C, B).

A, B, C 대신에 G1, G2, G3을 사용

• 쿼리: ?- jealous(X, Y).

다중 해 (Multiple Solutions)

• 가능한 해 (Possible Solutions)
  • X = john, Y = john
  • X = john, Y = jack
  • X = jack, Y = john
  • X = jack, Y = jack

• X와 Y가 같은 사람이 아닌 경우를 제외하려면?
  • jealous(X, Y), X \= Y.
  • 뒤에다가 X \= Y라는 condition을 붙여줘야 한다.
  • 규칙에다가 condition을 붙여주면 매번 이렇게 안 물어봐도 된다.
    • jealous(A, B) :- loves(C, A), loves(C, B).
    • 뒤에다가 , X \= Y.를 붙여주면 된다.

⠀Top to bottom, left to right로 진행한다는 것을 기억하자.

기타 연산자 (Other Operators)

• 객체에 대한 연산자 (For objects):
  • X = Y : 통일 (unification)
    • X와 Y를 같은걸로 보겠다.
  • X == Y : 동일 (identical)
  • X \= Y : 통일 불가 (cannot be unified)
  • X \== Y : 동일하지 않음 (not identical)
• 목표(goal)에 사용됨:
  • X , Y : X 그리고 Y (X and Y)
  • X ; Y : X 또는 Y (X or Y)
  • \+ X : X가 아님 (not X)

⠀

자연수 (Natural Number)

• 0을 자연수로 간주함
• succ(0)은 0보다 한 단위 큰 수, 즉 1을 나타냄
• 따라서 x보다 한 단위 큰 수는 succ(x)로 표현할 수 있음
• 이는 자연수의 귀납적 정의(inductive definition)임
  • succ(succ(0)): 2
  • succ(succ(succ(0))): 3
  • ...

⠀

합계는 어떨까? (How about Sum?)

• 합(sum)을 정의: sum(0, X, X).
  • 0 + X = X라는 건 자명하다.
• sum(succ(X), Y, succ(Z)) :- sum(X, Y, Z).
  • sum(succ(X), Y, succ(Z))는 X + 1 + Y = Z + 1을 의미한다.
  • sum(X, Y, Z)는 X + Y = Z를 의미한다.
    • 양변에 1을 더해도 성립한다.
• 예: 2 + 1?
  • ?- sum(succ(succ(0)), succ(0), A).
    • succ(0)을 X라고 하면, Y = succ(0)이고 A = succ(Z1)이다.
    • 이거를 다시 sum(X, Y, Z)에 넣는다면 sum(succ(0), succ(0), Z1)이다.
      • X = 0, Y = succ(0), Z1 = succ(Z2)라하면 sum(X, Y, Z2)
        • sum(0, succ(0), Z2)인데, Z2가 succ(0)이면 성립한다.
  • 이제 거꾸로 올라가면 Z1 = succ(succ(0)), A = succ(succ(succ(0)))
  • A = succ(succ(succ(0)))
  
  
• 너무 불편함. 1,000,000은 어떨까?

⠀

프로로그 산술 (Prolog Arithmetic)

• 일반적인 연산자:
  • +, -, *, /
• 비교 연산자:
  • A > B : A가 B보다 큼
  • A < B : A가 B보다 작음
  • A >= B : A가 B 이상임
  • A =< B : B가 A 이상임
  • A =:= B : A와 B가 같음
  • A =\= B : A와 B가 같지 않음

⠀

is Predicate

• 프로로그에서 =는 unification을 위해 예약됨
• 대신 산술적 동등성을 위해 is predicate를 제공함
  • computation result를 얻으려면 =가 아니라 is를 사용해야 한다.
• 예: half(X, Y) :- Y = X / 2.
• half2(X, Y) :- Y is X / 2.
  
• 쿼리 예제: ?- half(4, Y).
• Y = 4 / 2

• ?- half2(4, Y)

• Y = 2

⠀

리스트 (List)

• 프로로그에서 리스트를 표현할 수 있음
  • [1, 2, 3, 4], [a, b, c],
• Head + Tail 표현 방식
  • [a|[b, c]], [a, b|[c]]
• H를 머리(head, 첫 번째 요소), T를 꼬리(tail, 나머지 요소)로 사용할 수 있음
  • [h|t], [x|y]
  • 헤드는 항상 첫 요소 (딱 1개), tail는 나머지

⠀

리스트 (List)

• 쿼리 예제: ?- [h | t] = [a, b, c].
  • H = a
  • T = [b, c]
• ?- [a | y] = [x, b, c]
  • Y = [b, c]
  • X = a

append

• append fact: append(, Y, Y).
• append rule(inductive definition) : append([h | x], Y, [h | z]) :- append(X, Y, Z).

append(X, Y, Z).가 precondition이고 결과가 append([h | x], Y, [h | z])이다. 즉 X::Y = Z가 Precondition이다. 그러면 양 변에 H를 붙여주면 H|X::Y = H|Z 가 된다.

• 쿼리 예제
• ?- append([a, b], [1, 2], Z).
  • Z = [a, b, 1, 2]
• ?- append(X, Y, [1, 2, 3]).
  • X = , Y = [1, 2, 3]
  • X = [1], Y = [2, 3]
  여기 알 수 있는 건 [1, 2, 3]이 두 개 list의 결과 합이라는 거다.

어떻게 작동하는가? (How it works?)

• append 정의: append(, Y, Y).
• append([h | x], Y, [h | z]) :- append(X, Y, Z).

• ?- append([a, b], [c, d], Ans).
  • 축약 과정: _H1 = a, _X1 = [b], _Y1 = [c, d]
    • H1이라는 임시 변수에 a가 들어가고, 헤드 제외 나머지가 X1이 된다.
    • [c,d]는 Y가 된다.
    • 그러면 Ans = [h | z] = [h1 | z1] = [a | _z1]이 된다.
  • Ans = [a | _z1]
• append([b], [c, d], _Z1)
• _H2 = b, _X2 = ,
  • _Z1 = [b | _z2]
• append( , [c, d], _Z2)
  • append 정의: append(, Y, Y).를 만족하므로 여기서 끝.
  • _L = [c,d], _Z2 = _L, Z2 = [c, d]
• _L = [c, d],
  • _Z2 = _L
• _Z2 = [c, d], _Z1 = [b, c, d]
  • Ans = [a, b, c, d]

⠀

절(clause)과 목표(goal)의 순서 (Clausal and Goal Orders)

• 순수 논리 언어는 적용 순서에 영향을 받지 않음
• 그러나 Prolog는 효율성을 위해 자체 제어(Control)를 가지는 실용적 구현체이므로 순서가 중요함
• 절(clause) = 사실(Facts)과 규칙(Rules)
• 절의 순서 (Clausal Order): 첫 번째 applicable clause가 선택됨 (위에서 아래로, Top to Bottom)
• 목표의 순서 (Goal Order): 가장 왼쪽 서브 목표(leftmost sub-goal)를 먼저 선택함 (왼쪽에서 오른쪽으로, Left to Right). sub-goal들이 여러 개 있는 경우

⠀

절의 순서 (Clausal Order)

• 두 개의 append 프로그램
  
• append(, Y, Y).
  append([h|x], Y, [h|z]) :- append(X, Y, Z).
  
• append2([h|x], Y, [h|z]) :- append2(X, Y, Z).
  append2(, Y, Y).
  
• 차이점은 사실과 규칙의 순서뿐임

append2를 사용하면 첫 번째에만 걸려서 base case에 멈추지 않는다. 계속 임시 변수를 할당해 줌 스택오버플로우

• 쿼리 예제:
• ?- append(X, [c], Z).
  • X = [_x1], Z = [_x1, c]
  • X = [_x1, _x2], Z = [_x1, _x2, c]
  • ...
  
  
• ?- append2(X, [c], Z).
  • X = , Y = [c] Z = [c]. 이게 답인데, 계속가버린다.
  • 가 [h|x]가 되어서 H는 none, X는 empty list가 된다.
  • append2(, Y, Z2)이런식이 되버린다.
  • 결과: Stack Overflow!!

목표의 순서 (Goal Order)

• 서브리스트(sublist)를 위한 두 개의 프로그램
  
• prefix(X, Z) :- append(X, Y, Z).
  • X가 Z의 prefix이다.
• suffix(Y, Z) :- append(X, Y, Z).
  • Y가 Z의 suffix이다.
• sublist1(S, Z) :- prefix(X, Z), suffix(S, X).
  • S가 Z의 sublist이려면 Z의 prefix인 것의 suffix이어야 한다.
• sublist2(S, Z) :- suffix(S, X), prefix(X, Z).
  • S가 Z의 sublist이려면 어떤 X의 suffix이면서, 그 X는 Z의 prefix이어야 한다.
• 쿼리 예제:
• ?- sublist1([e], [a,b,c]).
  false
• ?- sublist2([e], [a,b,c]).
  Stack Overflow!!

목표의 순서 (Goal Order)

• prefix(X, Z) :- append(X, Y, Z).
• suffix(Y, Z) :- append(X, Y, Z).
• sublist1(S, Z) :- prefix(X, Z), suffix(S, X).
• sublist2(S, Z) :- suffix(S, X), prefix(X, Z).
  
• 쿼리 예제:

목표의 순서 (Goal Order)

• 프로그램 정의: prefix(X, Z) :- append(X, Y, Z).
• suffix(Y, Z) :- append(X, Y, Z).
• sublist1(S, Z) :- prefix(X, Z), suffix(S, X).
• sublist2(S, Z) :- suffix(S, X), prefix(X, Z).
  
• 쿼리 예제: ?- sublist2([e], [a,b,c]).

추측과 검증 (Guess-and-Verify)

• 프로로그 프로그램의 실행은 절(clause)과 목표(goal)의 순서에 민감할 수 있음
• 따라서 추측과 검증 방법 (Guess-and-Verify method)이 권장됨
  • 예제: conclusion(S) :- guess(S), verify(S).
  • guess로 줄이고 verify
• 가능한 해를 줄이기 위해 추측(guess)을 사용하고, 그 후 검증(verify)함
  • 예: sublist(S, Z) :- prefix(X, Z), suffix(S, X).
  • Z의 prefix인 X는 한정적이다. 범위가 줄어든다.
  • suffix(S, X)가 additional constraint 역할로 verify한다.

⠀

컷 (Cut)

• 최대값(max value)을 찾기 위한 예제:
  • 1. max(X, Y, X) :- X >= Y, !.
    • max(X, Y, X): X와 Y 중에 X가 더 크다.
  • 2. max(X, Y, Y) :- X < Y.
    • max(X, Y, Y): X와 Y중에 Y가 더크다
  • 1번이 만족되면 2번을 볼 필요하 없다. mutually exclusive하다.
• 쿼리 예제:
• ?- max(12, 2, Max).
  Max = 12
• 첫 번째 규칙이 선택되면, 두 번째 규칙을 더 이상 확인할 필요가 없음
  • 두 규칙은 상호 배타적(mutually exclusive)임
• 따라서 컷(!)을 사용하여 더 이상 탐색할 필요가 없음을 나타낼 수 있음

⠀

컷 (Cut)

• 리스트의 멤버십을 확인하는 또 다른 예제:
  • member(X, [x | _]) :- !.
    • X와 리스트가 멤버로 주어질 때, True라면 X가 리스트에 있는 것이다.
    • False라면 멤버에 없는거다
  • member(X, [_ | t]) :- member(X, T).
    • 헤드에 뭐가 올 지 모름. 만약 X가 Tail Part에 있다면 만족되는 것이다. member(X, T)
    • member(X, T)가 만족되면 member(X, [_ | t]) 또한 만족되는 것이다.
  • X가 헤드에 있다면, Tail part를 확인할 필요가 없다. 따라서 cut을 써준다.
• 쿼리 예제:
• ?- member(3, [1, 3, 5, 4]).
  true
• ?- member(2, [1, 3, 5, 4]).
  false
  
• X가 헤드에 포함되어 있으면, 꼬리 부분을 더 이상 확인할 필요가 없음
  • 따라서 첫 번째 규칙에 컷을 사용함
• 예제들처럼, 컷은 규칙 간의 OR 조건을 나타내는 데 사용될 수 있음