논리 프로그래밍의 구문 및 의미론

논리 프로그래밍은 Datalogger 및 Prolog를 포함하여 형식 논리에 기반한 언어를 포함하는 프로그래밍 패러다임입니다.이 기사는 이러한 언어의 순수하게 선언적인 하위 집합의 구문과 의미를 설명합니다.혼란스럽게도, "논리 프로그래밍"이라는 이름은 Prolog의 선언적 하위 집합에 대략적으로 해당하는 특정 프로그래밍 언어를 가리키기도 합니다.안타깝게도 이 글에서는 이 용어를 두 가지 의미로 사용해야 합니다.

선언적 논리 프로그램은 전적으로 형식의 규칙으로 구성됩니다.

H :- B1, ..., BN.

이러한 각 규칙은 의미로 읽을 수 있습니다.

\"표시 스타일 B_{1}\land \ldots \land B_{n}\오른쪽 화살표 H}

"만약 각 ${i}$ 가 참이라면 $B_{i}$ , $HH$ 는 $H$ $H$ 이다"라는 의미입니다.논리 프로그램은 규칙에 의해 암시되는 일련의 사실을 계산합니다.

Datalogger, Prolog 및 관련 언어의 많은 구현에는 Prolog의 잘라내기 연산자와 같은 절차적 기능이나 외부 함수 인터페이스와 같은 추가 논리적 기능이 추가됩니다.이러한 확장의 형식적 의미는 이 문서의 범위를 벗어납니다.

데이터로그

데이터로그는 가장 널리 연구되는 논리 프로그래밍 언어입니다.Datalogger의 의미론에 대한 세 가지 주요 정의가 있으며 모두 동일합니다.다른 논리 프로그래밍 언어의 구문 및 의미론은 데이터로그의 확장 및 일반화입니다.

구문

Datalogger 프로그램은 규칙 목록(경음기 절)^[1]으로 구성됩니다.상수와 변수가 각각 상수와 변수의 카운트 가능한 두 집합이고 관계가 술어 기호의 카운트 가능한 집합인 경우 다음 BNF 문법은 Datalogger 프로그램의 구조를 나타냅니다.

<program> ::= <rule> <program> " <rule> " ::= <atom-list> " ". <atom> ::= <tom-list >" < <> <> < <> < < < <> < < < < <>>>> < <," <용어 목록> "

원자는 또한 라고도 합니다.왼쪽에 있는 원자.:-기호는 규칙의 기호라고 하며, 오른쪽에 있는 원자는 입니다. 모든 Datalogger 프로그램은 규칙의 머리에 나타나는 모든 변수가 본문에도 나타나는 조건을 충족해야 합니다(이 조건은 때때로 ^[1]^[2]).

본문이 비어 있는 규칙을 호출합니다.예를 들어, 다음 규칙은 사실입니다.

r(x) :- .

통사당

논리 프로그래밍의 많은 구현은 위의 문법을 확장하여 다음과 같은 것 없이 사실을 쓸 수 있도록 합니다.:-이와 같이:

r(x).

대부분의 경우 괄호 없이 0-ary 관계를 쓸 수 있습니다.

p :- q.

이것들은 단지 약어일 뿐이며 프로그램의 의미에 영향을 미치지 않습니다.

예

다음 프로그램은 관계를 계산합니다.path그것은 관계의 과도적 폐쇄입니다.edge.

가장자리(x, y). 가장자리(y, z). 경로.(A, B) :-    가장자리(A, B). 경로.(A, C) :-    경로.(A, B),    가장자리(B, C).

의미론

Datalogger 프로그램의 의미론에 대해 널리 사용되는 세 가지 접근 방식, 즉 모델 이론, 고정점 및 증명 이론이 있습니다.이 세 가지 접근 방식은 ^[3]동등한 것으로 입증될 수 있습니다.

하위 용어가 변수가 아닌 경우 원자를 호출합니다.직관적으로, 각 의미론은 프로그램의 의미를 사실로부터 시작하여 프로그램의 규칙에서 추론할 수 있는 모든 기저 원자의 집합으로 정의합니다.

모델 이론

Datalogger 프로그램에 대한 Herbrand 해석의 해시 다이어그램
e(x, y). e(y, z). p(A, B) :- e(A, B). p(A, C) :- p(A, B), e(B, C).
$해석$ M은 $M$ 최소 Herbrand 모델입니다.위의 모든 해석도 모형이고 아래의 모든 해석도 모형이 아닙니다.

규칙의 모든 원자(머리와 몸)가 접지된 경우 규칙을 접지라고 합니다.R이 R의 모든₂ 변수에 대한 상수를 대체한 결과인 경우₁ 지면 규칙₁ R은 다른 규칙₂ R의 지면 인스턴스입니다.

Datalogger 프로그램의 Herbrand 베이스는 프로그램에 나타나는 상수로 만들 수 있는 모든 접지 원자의 집합입니다.해석(데이터베이스 인스턴스라고도 함)은 Herbrand 베이스의 하위 집합입니다. $기저$ 원자는 해석 $I$ 에서 참입니다. 규칙은 $해석$ I에서 참입니다. 규칙의 각 기저 인스턴스에 대해 본문의 모든 절이 $I$ 에서 참이라면, 규칙의 머리도 $I$ 에서 참입니다.

Datalogger 프로그램 P의 모델은 P의 모든 근거 사실을 포함하고 있으며 $I$ 에서 P의 모든 규칙을 참으로 만드는 P의 $해석$ I입니다.모델 이론적 의미론은 데이터로그 프로그램의 의미가 최소 모델(모든 ^[4]모델의 교차점)이라고 말합니다.

예를 들어, 이 프로그램은 다음과 같습니다.

가장자리(x, y). 가장자리(y, z). 경로.(A, B) :-    가장자리(A, B). 경로.(A, C) :-    경로.(A, B),    가장자리(B, C).

다음과 같은 Herbrand 세계가 있습니다.x,y,z

그리고 이 헤르브랜드 기반:edge(x, x),edge(x, y), ...,edge(z, z),path(x, x), ...,path(z, z)

그리고 이 최소 Herbrand 모델:edge(x, y),edge(y, z),path(x, y),path(y, z),path(x, z)

고정점

제가 Datalogger 프로그램 $P$ 의 해석 집합, 즉 $I =$ P( $H$ )입니다. 여기서 H는 P의 Herbrand 베이스이고 P는 전력 집합 연산자입니다.P에 대한 값은 $I$ 에서 $I$ 까지의 $맵$ T입니다. P에 있는 각 규칙의 각 지면 인스턴스에 대해 본문의 모든 절이 입력 해석에 있으면 지면 인스턴스의 머리를 출력 해석에 추가합니다.이 $맵$ T는 T의 $부분$ 집합 포함에 의해 주어진 부분 순서와 관련하여 단조롭습니다.Knaster-Tarski 정리에 따르면, 이 지도는 최소 고정점을 가지며, Kleene 고정점 정리에 따르면, 고정점은 체인 $T(\emptyset ),T(T(\emptyset )),\ldots ,T^{n}(\emptyset ),\ldots$ T $T(\emptyset ),T(T(\emptyset )),\ldots ,T^{n}(\emptyset ),\ldots$ ( $T$ $T(\emptyset ),T(T(\emptyset )),\ldots ,T^{n}(\emptyset ),\ldots$ $Tn$ $…,$ ...\ $displaystyle$ T $(\emptyset), T(\emptyset),$ \ $ldots$ 의 최댓값입니다.M의 $최소$ 고정점은 ^[5]프로그램의 최소 Herbrand 모델과 일치합니다.

픽스포인트 의미론은 최소 Herbrand 모델을 계산하기 위한 알고리즘을 제안합니다.프로그램의 기본 사실 집합으로 시작한 다음 고정점에 도달할 때까지 규칙의 결과를 반복적으로 추가합니다.이 알고리즘을 순진한 평가라고 합니다.

증명론

$프로그램$ P가 주어졌을 때, $지면$ 원자 A의 a는 $A$ 로 표시된 뿌리를 가진 나무이고, P의 $사실$ 머리에서 지면 원자로 표시된 잎은 $A_{1},\ldots ,A_{n}$ …, An_ $1},\ldots, A_{n}$ 로 $A_{1},\ldots ,A_{n}$ 분기되어 지면 $인스턴스$ 가 존재합니다.

G :- A₁, …, A_n.

$P$ 에 있는 규칙의.증명-이론적 의미론은 데이터로그 프로그램의 의미를 그러한 트리에서 벗어날 수 있는 접지 원자 집합으로 정의합니다.이 집합은 최소 Herbrand ^[6]모델과 일치합니다.

데이터로그 프로그램의 최소 Herbrand 모델에 특정 지상 원자가 나타나는지 여부에 관심이 있을 수 있습니다. 아마도 나머지 모델에 대해서는 크게 신경 쓰지 않을 것입니다.위에서 설명한 증명 트리의 하향식 판독은 이러한 쿼리의 결과를 계산하기 위한 알고리듬을 제안하며, 이러한 판독은 Prolog 평가의 기초를 형성하는 SLD 해상도 알고리듬을 알려줍니다.

기타 접근법

데이터로그의 의미론은 또한 더 일반적인 ^[7]세미링에 대한 고정점의 맥락에서 연구되었습니다.

논리 프로그래밍

"논리 프로그래밍"이라는 이름은 Datalog와 Prolog를 포함한 프로그래밍 언어의 전체 패러다임을 가리키는 데 사용되지만, 공식적인 의미론을 논의할 때 일반적으로 Datalog를 함수 기호로 확장한 것을 의미합니다.논리 프로그램은 또한 불립니다. 이 기사에서 논의된 논리 프로그래밍은 Prolog의 "순수한" 또는 선언적 하위 집합과 밀접한 관련이 있습니다.

구문

로직 프로그래밍의 구문은 함수 기호를 사용하여 데이터로그의 구문을 확장합니다.논리 프로그래밍은 범위 제한을 삭제하여 변수가 ^[8]본문에 나타나지 않는 규칙 머리에 나타날 수 있도록 합니다.

의미론

함수 기호의 존재로 인해 논리 프로그램의 Herbrand 모델은 무한할 수 있습니다.그러나 논리 프로그램의 의미론은 여전히 최소 Herbrand 모델로 정의됩니다.이와 관련하여, 직접 결과 연산자의 고정점은 유한한 수의 단계(또는 유한 집합)로 수렴되지 않을 수 있습니다.그러나 최소 헤르브랜드 모델의 모든 기저 원자는 유한 증명 트리를 가질 것입니다.이것이 프롤로그가 ^[8]하향식으로 평가되는 이유입니다.데이터로그에서와 마찬가지로 세 가지 의미론이 동등하다는 것을 증명할 수 있습니다.

부정

논리 프로그래밍은 논리 프로그램의 의미론에 대한 세 가지 주요 정의가 모두 동의하는 바람직한 특성을 가지고 있습니다.대조적으로, 논리 프로그램의 의미와 부정에 대한 많은 상충되는 제안이 있습니다.불일치의 원인은 논리 프로그램에는 고유한 최소 Herbrand 모델이 있지만 일반적으로 부정이 있는 논리 프로그래밍(또는 데이터로그) 프로그램에는 그렇지 않다는 것입니다.

구문

부정이 기록됩니다.not규칙 본문의 원자 앞에 나타날 수 있습니다.

<atom-list> ::= <atom> "not" <atom> <atom> ", <atom-list> ""

의미론

계층화 부정

부정이 있는 논리 프로그램은 각 관계를 일부 계층에 할당할 수 있을 때 계층화됩니다. 따라서 $관계$ R이 $관계$ S의 본문에서 부정으로 나타나면 $R$ 이 ^[9] $S$ 보다 낮은 계층에 있게 됩니다.데이터로그의 모델 이론 및 고정점 의미론은 계층화된 부정을 처리하도록 확장될 수 있으며, 이러한 확장은 동등함을 증명할 수 있습니다.

데이터로그의 많은 구현은 고정점 의미론에서 영감을 얻은 상향식 평가 모델을 사용합니다.이 의미론은 계층화된 부정을 처리할 수 있으므로 데이터로그의 여러 구현은 계층화된 부정을 구현합니다.

계층화된 부정은 데이터로그의 일반적인 확장이지만 계층화할 수 없는 합리적인 프로그램이 있습니다.다음 프로그램은 상대가 ^[10]움직임이 없을 경우 플레이어가 승리하는 2인 게임에 대해 설명합니다.

이사를(a, b). 이기다(X) :- 이사를(X, Y), 것은 아니다. 이기다(Y).

이 프로그램은 계층화되지 않았지만, 그렇게 생각하는 것이 합리적인 것 같습니다.a게임에서 이겨야 합니다.

완성 의미론

완벽한 모델 의미론

안정된 모델 의미론

안정적 모델 의미론은 프로그램의 특정 Herbrand 모델을 안정적으로 부르기 위한 조건을 정의합니다.직관적으로, 안정적인 모델은 "[프로그램]을 ^[11]전제로 한 합리적인 에이전트가 가질 수 있는 가능한 믿음의 집합"입니다.

음수가 있는 프로그램에는 안정적인 모형이 많거나 안정적인 모형이 없을 수 있습니다.예를 들어, 그 프로그램은

p :- 것은 아니다. q. q :- 것은 아니다. p.

에는 두 개의 안정적인 $\{p\}$ 모델 { $\{p\}$ } \{ $p$ $\{q\}$ { $\{q\}$ $}$ \{ $q$ 이 있습니다.단일 규칙 프로그램

p :- 것은 아니다. p.

안정적인 모델이 없습니다.

모든 안정된 모델은 최소 Herbrand 모델입니다.부정이 없는 데이터로그 프로그램에는 안정적인 단일 모델이 있으며, 이는 정확히 최소 Herbrand 모델입니다.안정적 모델 의미론은 부정이 있는 논리 프로그램의 의미를 정확하게 존재하는 경우 안정적 모델로 정의합니다.그러나 프로그램의 안정적인 모델을 모두(또는 적어도 여러 개) 조사하는 것이 유용할 수 있습니다. 이것이 응답 집합 프로그래밍의 목표입니다.

근거가 충분한 의미론

추가 확장

정수 상수 및 함수(데이터로그 ^[12]^[13]포함_ℤ)를 지원하는 변형, 규칙 본문의 불평등 제약 조건 및 집계 함수를 포함하여 데이터로그의 다른 여러 확장이 제안되고 연구되었습니다.

제약 조건 논리 프로그래밍을 사용하면 실수 또는 정수와 같은 도메인에 대한 제약 조건이 규칙 본문에 나타날 수 있습니다.

참고 항목

레퍼런스

메모들

^ ^a ^b 세리, 고틀로브 & 탄카 1989, 146페이지
^ Eisner, Jason; Filardo, Nathaniel W. (2011). de Moor, Oege; Gottlob, Georg; Furche, Tim; Sellers, Andrew (eds.). "Dyna: Extending Datalog for Modern AI". Datalog Reloaded. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6702: 181–220. doi:10.1007/978-3-642-24206-9_11. ISBN 978-3-642-24206-9.
^ van Emden, M. H.; Kowalski, R. A. (1976-10-01). "The Semantics of Predicate Logic as a Programming Language". Journal of the ACM. 23 (4): 733–742. doi:10.1145/321978.321991. ISSN 0004-5411. S2CID 11048276.
^ 세리, 고틀로브 & 탄카 1989, 149페이지
^ 세리, 고틀로브 & 탄카 1989, 150페이지
^ Abiteboul, Serge (1996). Foundations of databases. Addison-Wesley. ISBN 0-201-53771-0. OCLC 247979782.
^ Khamis, Mahmoud Abo; Ngo, Hung Q.; Pichler, Reinhard; Suciu, Dan; Wang, Yisu Remy (2023-02-01). "Convergence of Datalog over (Pre-) Semirings". arXiv:2105.14435 [cs.DB].
^ ^a ^b Abiteboul, p. 299. sfn 오류: 대상 없음: CITERE FAbiteboul(도움말)
^ Halevy, Alon Y.; Mumick, Inderpal Singh; Sagiv, Yehoshua; Shmueli, Oded (2001-09-01). "Static analysis in datalog extensions". Journal of the ACM. 48 (5): 971–1012. doi:10.1145/502102.502104. ISSN 0004-5411. S2CID 18868009.
^ Leone, N; Rullo, P (1992-01-01). "Safe computation of the well-founded semantics of datalog queries". Information Systems. 17 (1): 17–31. doi:10.1016/0306-4379(92)90003-6. ISSN 0306-4379.
^ Lifschitz, Michael Gelfond and Vladimir (1988). "The Stable Model Semantics for Logic Programming". {{cite journal}}:저널 요구 사항 인용 journal=(도움말)
^ Kaminski, Mark; Grau, Bernardo Cuenca; Kostylev, Egor V.; Motik, Boris; Horrocks, Ian (2017-11-12). "Foundations of Declarative Data Analysis Using Limit Datalog Programs". arXiv:1705.06927 [cs.AI].
^ Grau, Bernardo Cuenca; Horrocks, Ian; Kaminski, Mark; Kostylev, Egor V.; Motik, Boris (2020-02-25). "Limit Datalog: A Declarative Query Language for Data Analysis". ACM SIGMOD Record. 48 (4): 6–17. doi:10.1145/3385658.3385660. ISSN 0163-5808. S2CID 211520719.

원천

Ceri, S.; Gottlob, G.; Tanca, L. (March 1989). "What you always wanted to know about Datalog (and never dared to ask)" (PDF). IEEE Transactions on Knowledge and Data Engineering. 1 (1): 146–166. CiteSeerX 10.1.1.210.1118. doi:10.1109/69.43410. ISSN 1041-4347.

[FOOTNOTECeriGottlobTanca1989146-1] 세리, 고틀로브 & 탄카 1989, 146페이지

[2] Eisner, Jason; Filardo, Nathaniel W. (2011). de Moor, Oege; Gottlob, Georg; Furche, Tim; Sellers, Andrew (eds.). "Dyna: Extending Datalog for Modern AI". Datalog Reloaded. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6702: 181–220. doi:10.1007/978-3-642-24206-9_11. ISBN 978-3-642-24206-9.

[3] van Emden, M. H.; Kowalski, R. A. (1976-10-01). "The Semantics of Predicate Logic as a Programming Language". Journal of the ACM. 23 (4): 733–742. doi:10.1145/321978.321991. ISSN 0004-5411. S2CID 11048276.

[FOOTNOTECeriGottlobTanca1989149-4] 세리, 고틀로브 & 탄카 1989, 149페이지

[FOOTNOTECeriGottlobTanca1989150-5] 세리, 고틀로브 & 탄카 1989, 150페이지

[6] Abiteboul, Serge (1996). Foundations of databases. Addison-Wesley. ISBN 0-201-53771-0. OCLC 247979782.

[7] Khamis, Mahmoud Abo; Ngo, Hung Q.; Pichler, Reinhard; Suciu, Dan; Wang, Yisu Remy (2023-02-01). "Convergence of Datalog over (Pre-) Semirings". arXiv:2105.14435 [cs.DB].

[FOOTNOTEAbiteboul299-8] Abiteboul, p. 299. sfn 오류: 대상 없음: CITERE FAbiteboul(도움말)

[9] Halevy, Alon Y.; Mumick, Inderpal Singh; Sagiv, Yehoshua; Shmueli, Oded (2001-09-01). "Static analysis in datalog extensions". Journal of the ACM. 48 (5): 971–1012. doi:10.1145/502102.502104. ISSN 0004-5411. S2CID 18868009.

[10] Leone, N; Rullo, P (1992-01-01). "Safe computation of the well-founded semantics of datalog queries". Information Systems. 17 (1): 17–31. doi:10.1016/0306-4379(92)90003-6. ISSN 0306-4379.

[11] Lifschitz, Michael Gelfond and Vladimir (1988). "The Stable Model Semantics for Logic Programming". {{cite journal}}:저널 요구 사항 인용 journal=(도움말)

[12] Kaminski, Mark; Grau, Bernardo Cuenca; Kostylev, Egor V.; Motik, Boris; Horrocks, Ian (2017-11-12). "Foundations of Declarative Data Analysis Using Limit Datalog Programs". arXiv:1705.06927 [cs.AI].

[13] Grau, Bernardo Cuenca; Horrocks, Ian; Kaminski, Mark; Kostylev, Egor V.; Motik, Boris (2020-02-25). "Limit Datalog: A Declarative Query Language for Data Analysis". ACM SIGMOD Record. 48 (4): 6–17. doi:10.1145/3385658.3385660. ISSN 0163-5808. S2CID 211520719.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Search