로직 프로그래밍

Logic programming

논리 프로그래밍은 형식 논리를 기반으로 하는 프로그래밍, 데이터베이스, 지식 표현추론 패러다임입니다.논리 프로그래밍 언어의 프로그램, 데이터베이스 또는 지식 기반은 어떤 문제 영역에 대한 사실과 규칙을 표현하는 논리적 형태의 문장 집합입니다.주요 로직 프로그래밍 언어 계열로는 프롤로그, 응답 집합 프로그래밍(ASP) 및 데이터로그가 있습니다.이러한 모든 언어에서 규칙은 의 형태로 작성됩니다.

A :- B1, …, Bn.

논리적 의미로 선언적으로 읽힙니다.

A if B1 and … and Bn.

A규칙의 우두머리, , , , , , , , , 는 몸, , 리터럴이라고 불립니다.n = 0인 경우 규칙을 팩트(fact)라고 하며 단순화된 형태로 작성됩니다.

A.

, , , , , , , 가 모두 원자 공식인 가장 간단한 경우, 이 절들을 정칙절 또는 Horn 절이라고 합니다.

그러나 이 단순한 경우에는 많은 확장이 있는데, 가장 중요한 것은 절의 본문에 있는 조건이 또한 원자 공식의 부정이 될 수 있는 경우입니다.이 확장을 포함하는 논리 프로그래밍 언어는 비단조 논리의 지식 표현 기능을 가지고 있습니다.

ASP 및 Datalog에서 논리 프로그램은 선언적 판독값만 있으며, 이들의 실행은 프로그래머가 제어하는 동작이 아닌 증명 절차 또는 모델 생성기를 통해 수행됩니다.그러나 프롤로그 언어군에서 논리 프로그램은 목표 감소 절차로서 절차적 해석을 하기도 합니다.

해결하다, 해결하다, 그리고... 그리고 해결하다.

제안된 경우, 양식의 목표가 주어질 때:

?- A, A1, …, Am.

원자 공식인 선택된 하위 목표를 사용하여 목표 감소는 새로운 목표를 생성합니다.

?- B1,..., Bn, A1, …, Am.

n=0인 경우 하위 목표는 해결되고 새 목표는 나머지 하위 목표로 구성됩니다.

?- A1, …, Am.

논리 프로그래머가 원하는 특수 목적 절차로 동작하는 프로그램을 작성하기 위해 논리 프로그램의 범용적인 절차 판독을 사용할 수 있습니다.

다음 조항을 생각해 보십시오.

fallible(X) :- human(X).

Terry Winograd[1] 프로그래밍 언어 Planner를 설명하기 위해 사용한 예를 바탕으로 합니다.논리프로그램의 조항으로서, 그것은 가 있는지를 시험하는 절차로서, 를 시험하는 절차로서 그리고 를 찾는 절차로서 둘 다 사용될 수 있습니다. 심지어 사실은 절차적인 해석을 가지고 있습니다.예를 들어, 다음과 같은 조항이 있습니다.

human(socrates).

를 나타내는 절차로 사용할 수 있으며, "assigning"에서 을 찾는 절차로 사용할 수 있습니다.

Horn clause 논리 프로그램은 튜링(Turing)이 완벽하지만,[2][3] 대부분의 실제 응용 프로그램과 인공 지능에서 단음절이 아닌 추론이 필요한 응용 프로그램의 경우 Horn clause 프로그램을 부정적인 조건을 가진 "정상" 논리 프로그램으로 확장해야 합니다.

논리 프로그래밍 언어의 프롤로그 계열에서 절 본문의 음의 리터럴은 절차적 해석도 가지고 있는데, 이를 negative as failure라고 합니다. 음의 리터럴은 양의 리터럴이 유지되지 못하는 경우에만 유지되는 것으로 간주됩니다.

예를 들어, 다음과 같은 프로그램을 생각해 봅니다.

날 수 있는(X) :- (X), 것은 아니다. 비정상적인(X). 비정상적인(X) :- 상처 입은(X). (존.). (메리). 상처 입은(존.). 

비행할 수 있는 X를 찾는다는 목표가 주어졌을 때:

?- 날 수 있는(X). 

첫 번째 조항은 목표를 두 가지 하위 목표로 줄입니다.

?- (X), 것은 아니다. 비정상적인(X). 

첫 번째 하위 목표는 두 가지 후보 솔루션과 .첫 번째 후보는 인스턴스화된 두 번째 하위 목표를 산출합니다.

?- 것은 아니다. 비정상적인(존.). 

이 부정적인 하위 목표는 실패하는데, 이는 해당하는 긍정적인 하위 목표가 성공하기 때문입니다.

?- 비정상적인(존.). 진실의. 

따라서 최상위 목표의 후보해법도 실패하고,

반면, 상위 목표의 대체 후보 솔루션은 성공하는데, 인스턴스화된 두 번째 하위 목표는 성공하기 때문에, 대응하는 양의 하위 목표는 실패하기 때문입니다.

논리 프로그래밍 분야의 많은 연구들은 부정을 실패로 보는 논리적 의미론을 개발하려고 노력하고 부정을 위한 다른 의미론과 다른 구현을 개발하는 것과 관련이 있습니다.이러한 개발은 결국 논리 기반 프로그램 검증프로그램 변환을 위한 공식 방법 개발을 지원하는 데 중요했습니다.

역사

컴퓨터 프로그램을 표현하고 실행하기 위해 수학적 논리를 사용하는 것도 1930년대 알론조 처치에 의해 개발된 람다 미적분학의 특징입니다.그러나 컴퓨터 프로그램을 표현하기 위해 논리학의 수업 형태를 사용하자는 최초의 제안은 Cordell Green에 의해 이루어졌습니다.[4]이것은 LISP에서 프로그램의 실행을 시뮬레이션함으로써 관계를 계산하기 위해 입력-출력 관계의 표현과 함께 LISP의 부분집합의 공리화를 사용했습니다.반면에 Foster와 Elcock의 Absys는 방정식과 람다 미적분학의 조합을 사용하여 연산이 수행되는 순서에 제약을 두지 않았습니다.[5]

현재의 사실과 규칙 구문을 사용하는 논리 프로그래밍은 1960년대 말과 1970년대 초 인공 지능에서 지식의 선언적 대 절차적 표현에 대한 논쟁으로 거슬러 올라갈 수 있습니다.선언적 표현의 옹호자들은 특히매카시, 베르트람 라파엘, 코델 그린과 관련된 스탠포드에서, 그리고 에든버러에서는 존 앨런 로빈슨(시라큐스 대학의 학술 방문객), 팻 헤이스, 그리고 로버트 코왈스키와 함께 일하고 있었습니다.절차적 표현의 옹호자들은 주로 마빈 민스키시모어 파퍼트의 주도하에 MIT를 중심으로 이루어졌습니다.[6]

비록 논리의 증명 방법을 기반으로 했지만, MIT에서 개발된 플래너는 이러한 절차주의 패러다임 안에서 처음으로 등장한 언어였습니다.[7]플래너는 목표(즉, 목표 감소 또는 후방 연쇄)와 주장(즉, 전방 연쇄)에서 절차 계획을 패턴 주도적으로 호출하는 것을 특징으로 합니다.플래너의 가장 영향력 있는 구현은 Gerry Sussman, Eugene CharniakTerry Winograd에 의해 구현된 Micro-Planner라고 불리는 플래너의 하위 집합이었습니다.당시 랜드마크였던 위노그라드의 자연어 이해 프로그램 SHRDLU를 구현하는 데 사용되었습니다.[1]당시 매우 제한적인 메모리 시스템에 대응하기 위해 플래너는 한 번에 하나의 가능한 계산 경로만 저장해야 하는 역추적 제어 구조를 사용했습니다.플래너는 프로그래밍 언어 QA4,[8] Popler,[9] Conniver,[10] QLISP,[11] 그리고 동시 언어 Ether를 탄생시켰습니다.[12]

에든버러의 Hayes와 Kowalski는 지식 표현에 대한 논리 기반 선언적 접근과 Planner의 절차적 접근을 조화시키고자 했습니다.Hayes(1973)는 방정식 언어인 Golux를 개발하였는데, 이 언어는 정리 속담의 행동을 변경함으로써 다른 절차를 얻을 수 있었습니다.[13]

한편, 마르세유알랭 콜메라우어는 의미론을 나타내기 위한 논리를 사용하고 질문-답변을 위해 해결책을 사용하면서 자연어 이해에 힘썼습니다.1971년 여름 동안 콜메라우어는 코발스키를 마르세유로 초대했고, 그들은 논리학의 접합 형태가 공식 문법을 나타내는데 사용될 수 있고, 분해 정리 증명자가 파싱에 사용될 수 있다는 것을 함께 발견했습니다.그들은 초해상도와[14] 같은 일부 정리 증명자는 상향 파서로 동작하고 SL 해상도(1971)[15]와 같은 다른 정리 증명자는 하향 파서로 동작한다는 것을 관찰했습니다.

Kowalski가 다시 Colmerauer와 함께 작업한 것은 1972년 여름의 다음과 같습니다. 또한 그러한 조항은 명확한 조항 또는 Horn 조항으로 제한될 수 있으며 SL-resolution이 SLD 결의안으로 제한(및 일반화)될 수 있다는 것이 명확해졌습니다.Kowalski의 절차적 해석과 SLD는 1974년에 출판된 1973년 메모에서 설명되었습니다.[16]

콜메라우어는 Philippe Roussel과 함께 절차해석을 1972년 여름과 가을에 시행된 프롤로그의 기초로 삼았습니다.1972년에 작성되어 마르세유에서 시행된 최초의 프롤로그 프로그램은 프랑스식 질의응답 시스템이었습니다.프롤로그를 실제적인 프로그래밍 언어로 사용하는 것은 1977년 에든버러에서 데이비드 H. D. 워렌에 의한 컴파일러의 개발에 의해 큰 추진력을 얻었습니다.실험은 에든버러 프롤로그가 리스프와 같은 다른 상징적인 프로그래밍 언어의 처리 속도와 경쟁할 수 있다는 것을 보여주었습니다.[17]에든버러 프롤로그는 사실상의 표준이 되었고 ISO 표준 프롤로그의 정의에 큰 영향을 주었습니다.

로직 프로그래밍은 1980년대 일본 국제산업성5세대 컴퓨터 시스템(FGCS) 프로젝트를 위한 소프트웨어 개발에 선정하면서 국제적인 주목을 받았습니다.FGCS 프로젝트는 로직 프로그래밍을 사용하여 대규모 병렬 컴퓨터에서 고급 인공 지능 응용 프로그램을 개발하는 것을 목표로 했습니다.이 프로젝트는 처음에는 프롤로그의 사용을 탐구했지만 나중에 FGCS 컴퓨터 아키텍처에 더 가까웠기 때문에 동시 논리 프로그래밍의 사용을 채택했습니다.

그러나 동시 논리 프로그래밍의 커밋된 선택 기능은 언어의 논리적 의미론과 지식 표현 및 문제 해결 응용 프로그램에 대한 적합성을 방해했습니다.게다가, 프로젝트에서 개발된 병렬 컴퓨터 시스템은 더 일반적인 범용 컴퓨터의 개발에서 일어나는 발전과 경쟁하는 데 실패했습니다.이 두 가지 문제가 함께 FGCS 프로젝트가 목표를 달성하는 데 실패하는 결과를 초래했습니다.로직 프로그래밍과 AI에 대한 관심이 전 세계적으로 떨어졌습니다.

한편, FGCS 프로젝트와는 독립적으로 Prolog를 사용하는 것을 포함하여 보다 선언적인 논리 프로그래밍 접근 방식이 지속적으로 발전했습니다.특히 프롤로그는 지식에 대한 선언적 표현과 절차적 표현을 결합하기 위해 개발되었지만, 논리 프로그램에 대한 순수한 선언적 해석은 연역 데이터베이스 분야의 응용에 초점이 되었습니다.1977년 에르베 갈레르와 잭 밍커가 툴루즈에서 논리와 데이터베이스에 대한 워크숍을 조직하면서 이 분야의 연구가 두드러졌습니다.[18]필드 이름이 Datalog(데이터로그)로 변경되었습니다.

논리 프로그램의 논리적이고 선언적인 읽기에 대한 이러한 초점은 1980년대 제약 논리 프로그래밍과 1990년대 답변 세트 프로그래밍의 발전에 의해 더욱 촉진되었습니다.또한 최근 Prolog[19] 애플리케이션에서도 새롭게 강조되고 있습니다.

ALP(Association for Logic Programming)는 1986년 로직 프로그래밍을 장려하기 위해 설립되었습니다.2000년까지 공식 저널은 The Journal of Logic Programming이었습니다.창립 편집장J. Alan Robinson이었습니다.[20]2001년, 이 저널은 The Journal of Logic and Agebric Programming으로 이름이 바뀌었고, ALP의 공식 저널은 Cambridge University Press에서 발행하는 Theory and Practice of Logic Programming이 되었습니다.

컨셉트

논리 프로그램은 프로그래밍, 데이터베이스, 지식 표현 및 문제 해결의 다양한 응용 분야뿐만 아니라 다양한 의미론과 문제 해결 방법을 즐깁니다.

알고리즘 = 로직 + 컨트롤

논리 프로그램의 절차적 해석은 목표를 하위 목표로 줄이기 위해 역추론을 사용하는 것으로 알고리즘의 동작을 얻기 위해 지식의 선언적이고 논리적인 표현의 사용을 제어하는 문제 해결 전략의 사용의 특별한 경우입니다.보다 일반적으로, 상이한 문제 해결 전략을 동일한 논리 표현에 적용하여 상이한 알고리즘을 얻을 수 있습니다.[21]

논리 프로그래밍 언어의 프롤로그 계열에서는 하위 목표가 작성된 순서대로 하위 목표를 해결하기 위해 역추론을 사용하고, 같은 목표 또는 하위 목표와 머리가 일치하는 다른 절들도 절이 작성된 순서대로 사용합니다.그러나 이 문제 해결 전략의 다른 변형들도 사용될 수 있습니다.예를 들어 하위 목표를 병렬적으로 해결할 수 있고, 절도 병렬적으로 시도할 수 있습니다.첫 번째 전략은 안드-평행론이고 두 번째 전략은 오르-평행론이라고 불립니다.

프롤로그와 대조적으로, 논리 프로그래밍 언어의 데이터로그 계열에서 전진(또는 상향) 추론은 기존 사실과 조항 본문의 조건을 일치시키고 새로운 사실로서 조항의 인스턴스화된 머리 부분을 도출함으로써 기존 사실로부터 새로운 사실을 도출합니다.이 과정은 이러한 방식으로 도출할 수 있는 새로운 사실이 없을 때까지 또는 기존(초기 및 파생) 사실 중 일부가 해결해야 할 쿼리에 직접 대답할 때까지 계속됩니다.범위 제한(절 머리 부분의 모든 변수도 절 본문에 있음)은 초기 사실과 파생 사실에 변수가 없음을 보장합니다.

대부분의 경우, 질의나 목표에서 역추론이 순추론보다 더 효율적입니다.그러나 때로는 데이터로그 및 응답 집합 프로그래밍을 사용하면 전체적으로 절 집합과 분리된 쿼리가 없을 수 있으며, 그런 다음 절에서 도출할 수 있는 모든 사실을 생성하는 것이 합리적인 문제 해결 전략입니다.여기 또 다른 예가 있는데, 목표가 기존 계산 작업에서 순방향 추론이 역방향 추론을 이기는 경우입니다.?- fibonacci(n, Result)nth fibonacci 번호를 찾는 것입니다.

피보나치(0, 0). 피보나치(1, 1).  피보나치(N, 결과) :-     N > 1,     N1  N - 1,     N2  N - 2,     피보나치(N1, F1),     피보나치(N2, F2),     결과  F1 + F2. 

여기 관계가 있습니다.fibonacci(N, M)함수의 약자fibonacci(N) = M, 술어와 술어.N is Expression변수를 인스턴스화하는 술어에 대한 프롤로그 표기법입니다.N의 가치까지Expression.

피보나치 수를 계산하는 목표가 주어지면n, 역추론은 n-1과 n-2의 피보나치 수를 계산하는 두 가지 하위 목표로 목표를 줄입니다.n-1의 피보나치 수를 계산하는 하위 목표를 n-2와 n-3의 피보나치 수를 계산하는 두 하위 목표로 감소시켜 n-2의 피보나치 수를 중복적으로 계산합니다.하나의 피보나치 하위 목표를 두 개의 피보나치 하위 목표로 줄이는 이 과정은 숫자 0과 1에 도달할 때까지 계속됩니다.그것의 복잡성은 2등급입니다n.이와 대조적으로, 순방향 추론은 재계산 없이 0과 1부터 시작하는 피보나치 수열을 생성하고, 그 복잡성은 n에 대해 선형입니다.

프롤로그는 순방향 추론을 직접 수행할 수 없습니다.그러나 그것은 를 사용하여 후진 추론의 맥락 안에서 전진 추론의 효과를 얻을 수 있습니다: 하위 목표는 그들의 해결책과 함께 표에 유지됩니다.하위 목표를 다시 설정할 경우 하위 목표를 중복적으로 다시 해결하는 대신 표에 이미 있는 솔루션을 사용하여 직접 해결합니다.

문제해결

변수가 없는 명제 Horn 절 프로그램과 최상위 원자 목표의 단순한 경우, 역추론은 목표 해결을 위한 탐색 공간을 구성하는 And-또는 Tree를 결정합니다.최상위 목표는 나무의 뿌리입니다.트리의 임의의 노드와 머리가 노드와 일치하는 임의의 조항이 주어지면, 조항의 본문에는 하위 목표에 해당하는 하위 노드 집합이 존재합니다.이러한 하위 노드는 "and"로 함께 그룹화됩니다.노드를 해결하는 대안적인 방법에 해당하는 대안적인 자식 집합은 "또는"으로 함께 그룹화됩니다.

이 공간을 검색하는 데는 어떤 검색 전략도 사용할 수 있습니다.프롤로그는 한 번에 하나의 대안과 하나의 하위 목표만을 고려하는 순차적인 선입선출 역추적 전략을 사용합니다.병렬 검색, 지능형 역추적 또는 최적의 솔루션을 찾기 위한 최선의 검색과 같은 다른 검색 전략도 가능합니다.

하위 목표가 변수를 공유하는 일반적인 경우에는 가장 많이 인스턴스화되거나 한 절차만 적용되도록 충분히 인스턴스화된 하위 목표를 선택하는 등 다른 전략을 사용할 수 있습니다.그러한 전략은, 예를 들어, 동시 논리 프로그래밍에서 사용됩니다.

네거티브 as failure

NAF(Negative as failure)를 통해 구현된 부정적 조건은 이미 초기 프롤로그 시스템의 특징이었습니다.SLD 해상도의 결과적인 확장을 SLDNF라고 합니다. "thnot"이라고 불리는 유사한 구성이 Micro-Planner에도 존재했습니다.

실패로서의 부정의 논리적 의미론은 키스 클라크[22] 특정한 자연 조건 하에서 NAF가 고전적 부정을 사용한 프로그램의 완성과 함께 효율적이고 정확한(때로는 완전한) 추론 방식이라는 것을 보여주기 전까지 해결되지 않았습니다.

완성은 대략 동일한 술어를 머리에 가진 모든 프로그램 절들의 집합에 관한 것과 같습니다.

A :- Body1.
A :- Bodyk.

술어의 정의로서

A iff (Body1 or … or Bodyk)

여기서 "if and only if"를 의미합니다.완성에는 통일에 해당하는 평등의 공리도 포함되어 있습니다.클라크는 SLDNF에 의해 생성된 증명이 프로그램의 완료와 함께 자연스러운 추론 스타일에 의해 생성된 증명과 구조적으로 유사하다는 것을 보여주었습니다.

예를 들어, 이 글의 시작 부분에 주어진 프로그램의 완료는 다음과 같습니다.

canfly(X) iff bird(X), not abnormal(X).
abnormal(X) iff wounded(X).
bird(X) iff X = john or X = mary.
X = X.
not john = mary.
not mary = john.

완성의 개념은 존 매카시의 기본 추론에 대한 외접 의미론 [23]레이 리터의 닫힌 세계 가정과 밀접한 관련이 있습니다.[24]

부정에 대한 완료 의미론은 논리적 결과 의미론의 한 형태이며, 이를 위해 SLDNF는 증명 이론적 구현을 제공합니다.그러나 1980년대 들어 대안적인 만족도 의미론이 더욱 대중화되기 시작했습니다.만족성 의미론에서 부정은 논리 프로그램의 의도된 또는 표준 모델에서 진리에 대한 고전적 정의에 따라 해석됩니다.만족도 의미론의 구현은 프로그램과 목표가 참인 전체 표준 모델을 생성하거나, 모델 전체를 반드시 계산할 필요 없이 표준 모델에서 참인 목표의 인스턴스를 계산합니다.

예를 들어, 여기 이 글의 앞부분에 주어진 프로그램의 표준 모델에서 참인 모든 무변수(근거) 사실의 목록이 있습니다.다른 모든 근거 사실은 거짓입니다.

(존.). (메리). 상처 입은(존.). 비정상적인(존.). 날 수 있는(메리). 

의미론 및 목표 솔루션 전략

순수 논리적 용어로 볼 때, 논리 프로그래밍의 모델 이론적 의미론에 대한 두 가지 접근 방식이 있습니다.하나의 접근법은 원래의 논리적 결과 의미론으로, 목표를 해결하는 것은 목표가 프로그램의 모든 모델에서 참인 정리라는 것을 보여주는 것으로 이해합니다.다른 접근 방식은 만족도 의미론으로, 목표를 해결하는 것은 프로그램의 어떤 의도된(또는 표준) 모델에서 목표가 참(또는 충족된) 것임을 보여주는 것으로 이해합니다.

논리적 결과 의미론의 경우, SLD 및 SLDNF 해상도에서와 같은 역추론과 초해상도에서와 같은 순추론은 동일한 의미론에 대한 대안적 추론 규칙입니다.때때로 그러한 추론 규칙은 논리 프로그램에 대한 증명 이론적 의미론을 제공하는 것으로도 간주됩니다.

Horn 절 프로그램에 대한 만족도 의미론의 경우, 의도된 모델은 항상 존재하는 프로그램의 고유한 최소 모델입니다.비공식적으로 말하면, 프로그램의 최소 모델은 모델에서 참인 모든 사실들의 집합으로 간주될 때, 프로그램의 모델이기도 한 더 작은 사실들의 집합을 포함하지 않는 모델입니다.만족도 의미론은 또한 초해상도의 한 단계에서 기존 사실로부터 새로운 사실을 도출하는 함수의 최소 고정점으로서 대안적이고 수학적인 특성을 갖습니다.[25]

논리 프로그램의 두 의미론 사이의 관계는 후속 산술에서 덧셈과 곱셈의 경적 절 정의로 볼 수 있습니다.

더하다(X, 0, X). 더하다(X, s(Y), s(Z)) :- 더하다(X, Y, Z)).  곱셈을 하다(X, 0, 0). 곱셈을 하다(X, s(Y), W) :- 곱셈을 하다(X, Y, Z), 더하다(X, Z, W). 

여기서 항 s(X)는 X의 계승자, 즉 X+1을 나타내고, 덧셈(X, Y, Z)은 X+Y=Z를 나타내고, 곱셈(X, Y, Z은 X ⋅ {\displaystyle \cdot } Y = Z를 나타냅니다.

두 의미론 모두 동일하게 존재적으로 정량화된 덧셈 및 곱셈 목표의 연결에 대해 동일한 답을 제공합니다.예를 들어,

?- 곱셈을 하다(s(s(0)), s(s(0)), Z). Z = s(s(s(s(0)))).  ?- 곱셈을 하다(X, X, Y), 더하다(X, X, Y). X = 0, Y = 0  X = s(s(0)), Y = s(s(s(s(0)))). 

그러나 논리 consequence 시맨틱스를 사용하면 덧셈(s(s(0)), s(s(0)), 즉 2+2=5인 프로그램의 비표준 모델이 있습니다.그러나 만족도 의미론을 사용하면 산술의 표준 모델, 예를 들어 2+2=5가 거짓인 모델이 하나뿐입니다.

부정적인 조건을 가진 논리 프로그램의 경우, 모델 이론적 의미론의 두 가지 주요 변형이 있습니다.근거가 충분한 의미론에서, 논리 프로그램의 의도된 모델은 항상 존재하는 고유한 세 값의 최소 모델입니다.잘 근거가 있는 의미론은 수학적 논리에서 귀납적 정의의 개념을 일반화합니다.[26]XSB Prolog[27] SLG 해상도를 이용하여 근거가 충분한 시맨틱스를 구현합니다.[28]

대안적인 안정적 모델 의미론에서는 의도된 모델이나 의도된 모델이 없을 수 있으며, 이들은 모두 최소값이고 2-값입니다.안정적인 모델 의미론은 ASP(Answer set programming)를 뒷받침합니다.ASP의 대부분의 구현은 두 단계로 진행됩니다.우선, 이들은 가능한 모든 방법으로 프로그램을 인스턴스화하여 명제 논리 프로그램(접지라고 함)으로 축소합니다.그런 다음 DPLL 알고리즘이나 Boolean SAT 해결사와 같은 명제 논리 문제 해결사를 적용합니다.그러나, s(CASP)[29]와 같은 일부 구현에서는 접지 없이 목표 지향, 하향식, SLD 해결과 같은 절차를 사용합니다.

지식표상

Horn 절에 절차적 해석이 주어질 수 있고, 반대로 목표 감소 절차가 Horn 절 + 역추론으로 이해될 수 있다는 사실은 논리 프로그램이 지식에 대한 선언적 및 절차적 표현을 결합한다는 것을 의미합니다.네거티브를 실패로 포함하는 것은 논리 프로그래밍이 비일조 논리의 일종이라는 것을 의미합니다.

고전적 논리와 비교했을 때 단순함에도 불구하고, 이러한 혼절과 실패로서의 부정의 조합은 놀랍게도 표현적인 것으로 증명되었습니다.예를 들어, 그것은 상황 미적분학과 사건 미적분학에 의해 형식화된 상식적인 원인과 결과의 법칙에 대한 자연스러운 표현을 제공합니다.그것은 또한 입법이라는 준형식적인 언어에 아주 자연스럽게 부합하는 것으로 나타났습니다.특히 Prakken과 Sartor는[30] 영국 국적법의 표현이 "입법의 계산적 표현의 발전에 지대한 영향력을 가진" 논리 프로그램이라고[31] 공을 돌리며,논리 프로그래밍을 통해 직관적으로 매력적인 표현을 구현하여 자동 추론을 생성할 수 있는 방법을 보여줍니다."

변형 및 확장

프롤로그

SLD 해결 추론 규칙은 절 본문의 하위 목표가 해결을 위해 선택될 수 있는 순서에 대해 중립적입니다.효율성을 위해 Prolog는 이 순서를 하위 목표가 작성된 순서로 제한합니다.SLD는 또한 SLD 증명의 공간을 탐색하는 전략에 대해 중립적입니다.프롤로그는 이 공간을 톱다운, 깊이 우선으로 검색하고, 절이 작성된 순서대로 동일한 (하위) 목표를 해결하기 위해 다른 절을 시도합니다.

이 검색 전략은 현재 트리의 가지를 스택으로 효율적으로 표현할 수 있다는 장점이 있습니다.스택 상단의 목표 조항이 새 목표 조항으로 축소되면 새 목표 조항이 스택 상단으로 푸시됩니다.스택 상단의 목표 절에서 선택된 하위 목표를 새로운 목표 절로 축소할 수 없는 경우, 스택 상단에서 목표 절을 제거하고 대신 이전 목표 절을 시도합니다.

항상 성공하지만 역추적할 수 없는 !로 쓰인 컷이라는 하위 목표를 사용하여 역추적을 제한할 수 있습니다.절은 효율성을 향상시키기 위해 사용될 수 있지만 절의 논리적 의미를 방해할 수도 있습니다.많은 경우 컷 사용이 실패로 부정으로 대체될 수 있습니다.실제로 프롤로그에서는 negative as failure를 실패로 정의할 수 있습니다. cut을 다른 리터럴과 함께 사용하면 no 절의 머리말과 일치하는 false라고 말합니다.

것은 아니다.(P) :- P, !, 거짓의. 것은 아니다.(P). 

이 정의는 프로그램 및 프로그램 구성 요소(not(P))의 정의에서 P와 같은)가 데이터로 취급될 수 있음을 의미하는 Prolog의 호모아이콘 속성을 보여줍니다.이것은 메타인 해석기를 구현하기 위한 용도를 포함하여 많은 응용 프로그램을 가지고 있는 강력한 기능입니다.

2022년 프롤로그 창립 50주년을 기념하는 '프롤로그의 해'에서는 다양한 프롤로그 응용 프로그램이 고립되어 있고 다른 언어와 결합되어 있습니다.

프롤로그는 ALF, 프릴, 괴델, 머큐리, 오즈, 치아오, 비주얼 프롤로그, XSB, λ 프롤로그 등 다른 프로그래밍 언어의 개발에도 기여했습니다.

유괴 논리 프로그래밍

납북 논리 프로그래밍은 정상 논리 프로그래밍의 확장으로, 추론 가능한 술어로 선언된 일부 술어를 "열리거나" 정의되지 않도록 허용합니다.납치 논리 프로그램의 조항은 다음과 같은 형태를 갖습니다.

H :- B1, …, Bn, A1, …, An.

여기서 는 가환산할 수 없는 원자 공식이고, 모든 는 술어가 가환산할 수 없는 리터럴이고, 는 술어가 가환산할 수 있는 원자 공식입니다.추론 가능한 술어는 무결성 제약 조건에 의해 제한될 수 있으며, 다음과 같은 형태를 가질 수 있습니다.

false :- L1, …, Ln.

여기서 는 임의의 리터럴(정의되거나 가증성, 원자 또는 가증성)입니다.예를 들어,

날 수 있는(X) :- (X), 보통의(X). 거짓의 :- 보통의(X), 상처 입은(X). (존.). (메리). 상처 입은(존.). 

술어가 가증 가능한 경우.

문제 해결은 해결해야 할 문제에 대한 해결책으로 추론 가능한 술어로 표현된 가설을 도출함으로써 달성됩니다.이러한 문제는 (고전적인 납치 추론에서와 같이) 설명이 필요한 관찰이거나 (정상 논리 프로그래밍에서와 같이) 해결해야 할 목표일 수 있습니다.예를 들어, 가설은 관측을 설명합니다. 게다가, 같은 가설은 날아갈 수 있는 무언가를 찾는 목표의 유일한 해결책을 수반합니다.

:- 날 수 있는(X). 

납북 논리 프로그래밍은 고장 진단, 계획, 자연어 처리 및 기계 학습에 사용되었습니다.또한 이것은 네거티브를 실패로 해석하는 데에도 사용되어 왔습니다.

메탈로직 프로그래밍

수학적 논리는 사물 언어와 금속 언어를 구별하는 오랜 전통을 가지고 있기 때문에 논리 프로그래밍은 또한 금속 수준의 프로그래밍을 가능하게 합니다.가장 간단한 메탈로직 프로그램은 소위 "바닐라" 메타 해석기입니다.

    풀다(진실의).     풀다((A,B)):- 풀다(A),풀다(B).     풀다(A):- 절을(A,B),풀다(B). 

여기서 true는 빈 접속사를 나타내고, 절 (A,B)는 A:-B 형식의 객체 수준 절이 있음을 의미합니다.

메탈로직 프로그래밍은 자연어에서처럼 객체 수준 표현과 메탈 수준 표현을 결합할 수 있게 해줍니다.추론 규칙으로 지정된 논리를 구현하는 데도 사용할 수 있습니다.메탈로직은 메타 프로그램을 구현하기 위한 논리 프로그래밍에 사용되며, 메타 프로그램은 다른 프로그램, 데이터베이스, 지식 기반 또는 공리 이론을 데이터로 조작합니다.

제약 로직 프로그래밍

제약 조건 논리 프로그래밍은 Horn 절 논리 프로그래밍과 제약 조건 해결을 결합합니다.제약 술어로 선언된 일부 술어가 절 본문에서 리터럴로 발생할 수 있도록 하여 Horn 절을 확장합니다.제약 논리 프로그램은 다음과 같은 형태의 절들의 집합입니다.

H :- C1, …, Cn ◊ B1, …, Bn.

여기서 모든 것은 원자 공식이고, 가 제약 조건입니다.선언적으로 이러한 절은 일반적인 논리적 의미로 읽힙니다.

H if C1 and … and Cn and B1 and … and Bn.

그러나 절의 머리 부분에 있는 술어들은 제약 논리 프로그램에 의해 정의되는 반면, 제약 부분에 있는 술어들은 일부 도메인별 모델 이론 구조 또는 이론에 의해 미리 정의됩니다.

절차적으로, 프로그램에 의해 술어가 정의되는 하위 목표는 일반 논리 프로그래밍과 마찬가지로 목표 감소로 해결되지만, 제약 조건은 제약 조건 술어의 의미론을 구현하는 도메인별 제약 해결사에 의해 만족도를 확인합니다.초기 문제는 만족스러운 제약 조건의 연결로 줄임으로써 해결됩니다.

다음 제약 논리 프로그램은 교사로서 역사의 장난감 시간 데이터베이스를 나타냅니다.

교편을 잡니다(존., 철물을, T) :- 1990  T, T < 1999. 교편을 잡니다(존., 소프트웨어를, T) :- 1999  T, T < 2005. 교편을 잡니다(존., 논리, T) :- 2005  T, T  2012. 순위(존., 교관, T) :- 1990  T, T < 2010. 순위(존., 교수님, T) :- 2010  T, T < 2014. 

여기 및 는 제약 조건 술어로, 일반적으로 의도된 의미론을 사용합니다.다음 목표 조항은 데이터베이스를 쿼리하여 와 둘 다 언제 가르쳤는지 알아봅니다.

:- teaches(john, logic, T), rank(john, professor, T).

해결책은.

제약 로직 프로그래밍은 토목 공학, 기계 공학, 디지털 회로 검증, 자동화된 시간표 작성, 항공 교통 통제, 금융 등의 분야에서 문제를 해결하는 데 사용되어 왔습니다.그것은 납치 논리 프로그래밍과 밀접한 관련이 있습니다.

동시 논리 프로그래밍

동시 논리 프로그래밍은 논리 프로그래밍의 개념과 동시 프로그래밍을 통합합니다.1980년대에 일본 5세대 프로젝트(FGCS)의 시스템 프로그래밍 언어를 선택함으로써 개발이 크게 촉진되었습니다.[32]

동시 논리 프로그램은 다음과 같은 형태의 보호된 Horn 절의 집합입니다.

H :- G1, …, Gn B1, …, Bn.

접속사는 절의 수호자라고 불리며, 약속 연산자입니다.선언적으로 보호된 Horn 절은 일반적인 논리적 의미로 읽힙니다.

H if G1 and … and Gn and B1 and … and Bn.

그러나 절차적으로 머리가 주어진 목표와 일치하는 여러 개의 조항이 있을 경우, 모든 조항이 병렬적으로 실행되어 그들의 경비원들이 붙잡히는지 여부를 확인합니다.두 개 이상의 조항의 보호자가 유지될 경우 해당 조항 중 하나에 대해 커밋된 선택이 수행되고 선택된 조항의 하위 목표로 실행이 진행됩니다.이러한 하위 목표를 병렬적으로 실행할 수도 있습니다.따라서 동시 논리 프로그래밍은 "무결정성을 알지 못한다"가 아니라 "무결정성을 신경쓰지 않는다"의 형태를 구현합니다.

예를 들어, 다음의 동시 논리 프로그램은 술어를 정의하는데, 술어는 두 개의 목록을 섞는 데 사용할 수 있으며, 두 개의 목록의 순서를 보존하는 단일 목록으로 결합할 수 있습니다.

꼬불꼬불한([], [], []). 꼬불꼬불한(왼쪽, 맞다, 병합) :-     왼쪽 = [첫번째   쉬다]       병합 = [첫번째   쇼트 머지],     꼬불꼬불한(쉬다, 맞다, 쇼트 머지). 꼬불꼬불한(왼쪽, 맞다, 병합) :-     맞다 = [첫번째   쉬다]       병합 = [첫번째   쇼트 머지],     꼬불꼬불한(왼쪽, 쉬다, 쇼트 머지). 

여기서 는 빈 목록을 나타내며, 프롤로그에서처럼 첫 번째 요소 다음에 목록이 있는 목록을 나타냅니다.(두 번째와 세 번째 절에서 첫 번째가 리스트 생성자인 반면, 두 번째가 커밋 연산자임에 유의하십시오.)이 프로그램은 예를 들어 목록을 셔플하고 목표 절을 호출하는 데 사용할 수 있습니다.

꼬불꼬불한([에이스인, 여왕님, ], [1, 4, 2], 병합). 

예를 들어, 프로그램은 비결정적으로 단일 솔루션을 생성합니다.

동시 논리 프로그래밍은 메시지 전달을 기반으로 하므로 액터(Actor)와 같은 다른 동시 메시지 전달 시스템과 동일한 불확정성을 가질 수 있습니다(동시 계산의 불확정성 참조).칼 휴이트는 동시 논리 프로그래밍은 계산 단계를 논리적으로 추론할 수 없다는 의미에서 논리에 기초하지 않는다고 주장했습니다.[33]그러나 동시 논리 프로그래밍에서, 종료 계산의 결과는 프로그램의 논리적 결과이며, 부분 계산의 결과 부분적 결과는 프로그램과 잔차 목표(프로세스 네트워크)의 논리적 결과입니다.따라서 계산의 불확정성은 프로그램의 모든 논리적 결과를 추론할 수 없음을 의미합니다.[neutrality is disputed]

동시제약 로직 프로그래밍

동시 제약 로직 프로그래밍은 동시 논리 프로그래밍과 제약 로직 프로그래밍을 결합하여 동시성을 제어하는 제약 조건을 사용합니다.절에는 절의 적용 가능성을 차단할 수 있는 제약 조건의 집합인 가드가 포함될 수 있습니다.여러 절의 보호가 충족되면 동시 제약 로직 프로그래밍은 하나만 사용하도록 커밋된 선택을 합니다.

유도 논리 프로그래밍

귀납적 논리 프로그래밍은 논리 프로그램의 기계 학습이라는 배경 지식의 맥락에서 긍정적인 예와 부정적인 예를 일반화하는 것과 관련이 있습니다.논리 프로그래밍, 학습 및 확률을 결합한 이 분야의 최근 연구는 통계적 관계 학습확률론적 귀납 논리 프로그래밍의 새로운 분야를 만들었습니다.

고차 논리 프로그래밍

몇몇 연구자들은 술어 변수와 같은 고차 논리에서 파생된 고차 프로그래밍 기능으로 확장된 논리 프로그래밍을 가지고 있습니다.이러한 언어에는 Prolog 확장자 HiLog λProlog가 포함됩니다.

선형논리프로그래밍

선형 논리에 기초한 논리 프로그래밍은 고전 논리에 기초한 논리 프로그래밍 언어보다 훨씬 더 표현력이 뛰어난 논리 프로그래밍 언어를 설계하는 결과를 낳았습니다.경적절 프로그램은 술어에 대한 인수의 변경에 의해서만 상태 변화를 나타낼 수 있습니다.선형 논리 프로그래밍에서 주변 선형 논리를 사용하여 상태 변화를 지원할 수 있습니다.선형 논리에 기반한 논리 프로그래밍 언어의 초기 설계로는 LO,[34] 롤리,[35] ACL,[36] 포럼 등이 있습니다.[37]포럼은 모든 선형 논리에 대한 목표 지향적 해석을 제공합니다.

객체지향논리프로그래밍

F-logic은 객체와 프레임 구문으로 논리 프로그래밍을 확장합니다.

Logtalk는 개체, 프로토콜 및 기타 OOP 개념을 지원하는 Prolog 프로그래밍 언어를 확장합니다.대부분의 표준 호환 Prolog 시스템을 백엔드 컴파일러로 지원합니다.

트랜잭션 로직 프로그래밍

트랜잭션 로직은 상태 수정 업데이트에 대한 논리 이론을 가진 논리 프로그래밍의 확장입니다.그것은 모델 이론적 의미론과 절차적 의미론을 모두 가지고 있습니다.Flora-2 시스템에서는 트랜잭션 로직의 하위 집합을 구현할 수 있습니다.다른 시제품들도 있습니다.

참고 항목

인용문

  1. ^ a b Winograd, Terry (1972). "Understanding natural language". Cognitive Psychology. 3 (1): 1–191. doi:10.1016/0010-0285(72)90002-3.
  2. ^ Tärnlund, S.Å. (1977). "Horn clause computability". BIT Numerical Mathematics. 17 (2): 215–226. doi:10.1007/BF01932293. S2CID 32577496.
  3. ^ Andréka, H.; Németi, I. (1978). "The generalised completeness of Horn predicate-logic as a programming language". Acta Cybernetica. 4 (1): 3–10.
  4. ^ Green, Cordell. Application of Theorem Proving to Problem Solving (PDF). IJCAI 1969.
  5. ^ Foster, J.M.; Elcock, E.W. (1969). ABSYS 1: An Incremental Compiler for Assertions: an Introduction. Fourth Annual Machine Intelligence Workshop. Machine Intelligence. Vol. 4. Edinburgh, UK: Edinburgh University Press. pp. 423–429.
  6. ^ Kowalski, R. A. (1988). "The early years of logic programming" (PDF). Communications of the ACM. 31: 38–43. doi:10.1145/35043.35046. S2CID 12259230.
  7. ^ Hewitt, Carl. Planner: A Language for Proving Theorems in Robots (PDF). IJCAI 1969.
  8. ^ Jeff Rulifson; Jan Derksen; Richard Waldinger (November 1973). QA4, A Procedural Calculus for Intuitive Reasoning (PDF) (Technical report). SRI AI Center Technical Note 73.
  9. ^ 데이비스, J.M., 1971. 팝플러: POP-2 기획자.에든버러 대학교 기계지능과 지각학과.
  10. ^ McDermott, D.V.; Sussman, G.J. (May 1972). The Conniver reference manual (Technical report). Artificial Intelligence Memo No. 259.
  11. ^ Reboh, R.; Sacerdoti, E.D. (August 1973). A preliminary QLISP manual (Technical report). Artificial Intelligence Center, SRI International.
  12. ^ Kornfeld, W.A.; Hewitt, C.E. (1981). "The scientific community metaphor". IEEE Transactions on Systems, Man, and Cybernetics. 11 (1): 24–33. doi:10.1109/TSMC.1981.4308575. hdl:1721.1/5693. S2CID 1322857.
  13. ^ Hayes, Pat (1973). "Computation and Deduction". Proceedings of the 2nd MFCS Symposium. Czechoslovak Academy of Sciences. pp. 105–118.
  14. ^ Robinson, J. (1965). "Automatic deduction with hyper-resolution". International Journal of Computer Mathematics. 1: 227–234. doi:10.2307/2272384. JSTOR 2272384.
  15. ^ Kowalski, Robert; Kuehner, Donald (1971). "Linear Resolution with Selection Function" (PDF). Artificial Intelligence. 2 (3–4): 227–260. doi:10.1016/0004-3702(71)90012-9.
  16. ^ Kowalski, Robert (1973). "Predicate Logic as a Programming Language" (PDF). Department of Artificial Intelligence, Edinburgh University. Memo 70. 또한 IFIP 총회, 스톡홀름, 노스 홀랜드 출판사, 1974, 페이지 569-574.
  17. ^ Warren, D.H.; Pereira, L.M.; Pereira, F. (1977). "Prolog-the language and its implementation compared with Lisp". ACM SIGPLAN Notices. 12 (8): 109–115. doi:10.1145/872734.806939.
  18. ^ Gallaire, Hervé; Minker, John 'Jack', eds. (1978), "Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977", Advances in Data Base Theory, New York: Plenum Press, ISBN 978-0-306-40060-5.
  19. ^ a b Warren, D.S. (2023). "Introduction to Prolog". In Warren, D.S.; Dahl, V.; Eiter, T.; Hermenegildo, M.V.; Kowalski, R.; Rossi, F. (eds.). Prolog: The Next 50 Years. Lecture Notes in Computer Science(). Vol. 13900. Springer, Cham. pp. 3–19. doi:10.1007/978-3-031-35254-6_1. ISBN 978-3-031-35253-9.
  20. ^ Robinson, J. Alan (2001). "Invited Editorial". Theory and Practice of Logic Programming. Cambridge University Press. 1 (1): 1. doi:10.1017/s1471068400000028.
  21. ^ R.A.Kowalski (July 1979). "Algorithm=Logic + Control". Communications of the ACM. 22 (7): 424–436. doi:10.1145/359131.359136. S2CID 2509896.
  22. ^ Clark, K.L. (1977). "Negation as failure". Logic and data bases. Boston, MA: Springer US. pp. 293–322. doi:10.1007/978-1-4684-3384-5_11. ISBN 978-1-4684-3386-9.
  23. ^ Gelfond, M.; Przymusinska, H.; Przymusinski, T. (1989). "On the relationship between circumscription and negation as failure". Artificial Intelligence. 38 (1): 75–94. doi:10.1016/0004-3702(89)90068-4.
  24. ^ Shepherdson, J.C. (1984). "Negation as failure: a comparison of Clark's completed data base and Reiter's closed world assumption". The Journal of Logic Programming. 1 (1): 51–79. doi:10.1016/0743-1066(84)90023-2.
  25. ^ Van Emden, M.H.; Kowalski, R.A. (October 1976). "The semantics of predicate logic as a programming language". Journal of the ACM. 23 (4): 733–742. doi:10.1145/321978.321991. S2CID 11048276.
  26. ^ Denecker, M.; Ternovska, E. (2008). "A logic of nonmonotone inductive definitions". ACM Transactions on Computational Logic. 9 (2): 14:1–14:52. doi:10.1145/1342991.1342998. S2CID 13156469.
  27. ^ Rao, P.; Sagonas, K.; Swift, T.; Warren, D.S.; Freire, J. (July 28–31, 1997). XSB: A system for efficiently computing well-founded semantics. Logic Programming And Nonmonotonic Reasoning: 4th International Conference, LPNMR'97. Dagstuhl Castle, Germany: Springer Berlin Heidelberg. pp. 430–440. doi:10.1007/3-540-63255-7_33.
  28. ^ W. Chen; D. S. Warren (January 1996). "Tabled Evaluation with Delaying for General Logic Programs". Journal of the ACM. 43 (1): 20–74. doi:10.1145/227595.227597. S2CID 7041379.
  29. ^ Arias, J.; Carro, M.; Salazar, E.; Marple, K.; Gupta, G. (2018). "Constraint Answer Set Programming without Grounding". Theory and Practice of Logic Programming. 18 (3–4): 337–354. arXiv:1804.11162. doi:10.1017/S1471068418000285. S2CID 13754645.
  30. ^ Prakken, H.; Sartor, G. (October 2015). "Law and logic: a review from an argumentation perspective" (PDF). Artificial Intelligence. 227: 214–245. doi:10.1016/j.artint.2015.06.005. S2CID 4261497.
  31. ^ Sergot, M.J.; Sadri, F.; Kowalski, R.A.; Kriwaczek, F.; Hammond, P; Cory, H.T. (1986). "The British Nationality Act as a logic program" (PDF). Communications of the ACM. 29 (5): 370–386. doi:10.1145/5689.5920. S2CID 5665107.
  32. ^ 우치다 슌이치와 후치 가즈히로.FGCS 프로젝트 평가 워크샵 진행신세대 컴퓨터 기술 연구소 (ICOT) 1992.
  33. ^ Hewitt, Carl (27 April 2016). "Inconsistency Robustness for Logic Programs". Hal Archives. pp. 21–26. Retrieved 7 November 2016.
  34. ^ Andreoli, Jean-Marc (1 June 1992). "Logic Programming with Focusing Proofs in Linear Logic". Journal of Logic and Computation. 2 (3): 297–347. doi:10.1093/logcom/2.3.297.
  35. ^ Hodas, Joshua; Miller, Dale (1994). "Logic Programming in a Fragment of Intuitionistic Linear Logic". Information and Computation. 110 (2): 327–365. doi:10.1006/inco.1994.1036.
  36. ^ Kobayashi, Naoki; Yonezawa, Akinori (1994). Asynchronous communication model based on linear logic. US/Japan Workshop on Parallel Symbolic Computing. pp. 279–294. CiteSeerX 10.1.1.42.8749.
  37. ^ Miller, Dale (30 September 1996). "Forum: A Multiple-Conclusion Specification Logic". Theoretical Computer Science. 165 (1): 201–232. doi:10.1016/0304-3975(96)00045-X.

원천

일반소개

기타출처

추가열람

외부 링크