프롤로그 구문 및 의미론
Prolog syntax and semantics프롤로그 프로그래밍 언어의 구문과 의미론은 프롤로그 프로그램이 어떻게 작성되고 어떻게 해석되는지를 정의하는 규칙 집합이다.Prolog 구현에 차이가 있지만 ISO 표준 ISO/IEC 13211에[1] 규칙이 제시되어 있다.
데이터 유형
프롤로그는 동적으로 입력된다.단일 데이터 유형인 항을 가지며, 원자, 숫자, 변수, 복합 항 등 여러 가지 하위 유형을 가진다.
원자는 고유 의미가 없는 범용 이름이다.프롤로그 판독기가 단일 단위로 구문 분석하는 일련의 문자로 구성된다.원자는 보통 프롤로그 코드에서 특별한 구문 없이 쓰여진 맨 단어들이다.그러나 공백이나 특정 특수 문자를 포함하는 원자는 작은 따옴표로 둘러싸야 한다.대문자로 시작하는 원자도 인용하여 변수와 구별해야 한다.빈 목록, 작성됨[], 또한 원자다.원자의 다른 예는 다음과 같다.x,blue,'Taco', 그리고'some atom'.
숫자는 부유하거나 정수일 수 있다.많은 프롤로그 구현은 또한 무한 정수와 합리적인 숫자를 제공한다.
변수는 문자, 숫자 및 밑줄 문자로 구성된 문자열로 표시되며 대문자 또는 밑줄로 시작한다.변수는 임의의 용어에 대한 자리 표시자라는 점에서 논리적으로 변수들과 매우 유사하다.변수는 통일을 통해 인스턴스화될 수 있다(특정 용어 동일으로 구속됨).단일 밑줄()._)는 익명 변수를 나타내며 "모든 용어"를 의미한다.다른 변수와 달리 밑줄은 술어 정의 내에서 발생하는 모든 곳에서 동일한 값을 나타내지 않는다.
복합 용어는 "functor"라고 불리는 원자와 다시 용어인 다수의 "논쟁"으로 구성되어 있다.복합 용어는 일반적으로 functor로 쓰여진 뒤에 괄호 안에 들어 있는 쉼표로 구분된 인수 용어의 리스트가 뒤따른다.논쟁의 개수는 용어의 경지라고 불린다.원자는 경성 0의 합성어로 간주될 수 있다.
복합 용어의 예는 다음과 같다.truck_year('Mazda', 1986), 그리고'Person_Friends'(zelda,[tom,jim]). 연산자로 선언된 functor가 있는 복합 용어는 접두사 또는 infix 표기법으로 작성할 수 있다.예를 들어, 용어-(z),+(a,b), 그리고=(X,Y)라고도 쓸 수 있다.-z,a+b, 그리고X=Y각각,사용자는 도메인별 표기 허용을 위해 선행 조건이 다른 연산자로 임의의 펑터를 선언할 수 있다.f/n 표기법은 일반적으로 functor f와 arity n을 가진 용어를 나타내기 위해 사용된다.
복합 용어의 특별한 경우:
- 목록은 유도적으로 정의된다.원자
[]리스트다.functor와 합성어.(점)과 arity 2는 두 번째 주장이 목록인 것 자체가 목록이다.목록 표시에 대한 특별한 구문이 있다..(A, B)와 같다[A B]. 예를 들어, 목록.(1, .(2, .(3, [])))라고도 쓸 수 있다.[1 [2 [3 []]]], 또는 보다 간결하게[1,2,3]. - 문자열:따옴표로 둘러싸인 일련의 문자는 (숫자) 문자 코드의 목록과 동일하며, 일반적으로 시스템이 유니코드를 지원하는 경우 로컬 문자 인코딩 또는 유니코드에 해당된다.
프롤로그 프로그램
프롤로그 프로그램은 조항에 의해 정의된 관계를 기술한다.순수 프롤로그는 1차 술어 논리학의 튜링-완전한 부분집합인 혼 절에 제한된다.두 가지 유형의 조항이 있다.사실과 규칙.규칙은 형식이다.
머리 :- 몸. "몸이 참이면 머리가 참"으로 읽힌다.규칙의 몸은 술어를 부르는 것으로 구성되는데, 이를 규칙의 목표라고 한다.기본 제공 술어 ,/2(이름을 가진 2-arrient 연산자를 의미한다.,)은 목표의 결합을 의미한다.;/2불화를 나타내다접속사와 해체는 규칙의 머리부분이 아닌 몸에서만 나타날 수 있다.
빈 몸이 있는 절은 사실이라고 한다.사실의 예는 다음과 같다.
고양이를(톰.). 이는 규칙과 동일하다.
고양이를(톰.) :- 진실의. 또 다른 예는 다음과 같다.
X 이다 3+2. 그리고 당신이 그것을 실행했을 때, 결과는
X=5 네.
기본 제공 술어true/0항상 진실이다.
평가하기
Prolog 프로그램의 실행은 사용자가 쿼리라고 하는 단일 목표를 게시함으로써 시작된다.논리적으로 프롤로그 엔진은 부정된 쿼리의 분해능 재조합을 찾으려고 한다.Prolog에서 사용하는 분해능을 SLD 분해능이라고 한다.부정 쿼리를 반박할 수 있는 경우, 적절한 변수 바인딩이 있는 쿼리는 프로그램의 논리적 결과라는 것을 따른다.이 경우 생성된 변수 바인딩은 모두 사용자에게 보고되며 쿼리는 성공했다고 한다.운용상, 프롤로그의 실행 전략은 다른 언어의 함수 호출을 일반화하는 것으로 생각할 수 있는데, 한 가지 차이점은 여러 절 헤드가 주어진 호와 일치할 수 있다는 것이다.그 경우, 시스템은 선택 지점을 만들고, 첫 번째 대안의 조항 헤드와 목표를 통일하며, 그 첫 번째 대안의 목표를 계속한다.프로그램을 실행하는 과정에서 어떤 목표가 실패하면, 가장 최근의 선택 지점이 생성된 이후 만들어진 모든 가변 바인딩이 취소되고, 그 선택 지점의 다음 대안인 실행이 계속된다.이 실행전략을 연대기적 역추적이라 한다.
mother_child(터벅터벅 걷다, 샐리). father_child(톰., 샐리). father_child(톰., 에리카). father_child(마이크, 톰.). 형제(X, Y) :- parent_child(Z, X), parent_child(Z, Y). parent_child(X, Y) :- father_child(X, Y). parent_child(X, Y) :- mother_child(X, Y). 이로 인해 다음과 같은 쿼리가 참으로 평가된다.
?- 형제(샐리, 에리카). 네 이를 다음과 같이 얻는다.처음에는 쿼리에 일치하는 유일한 절 헤드가sibling(sally, erica)첫 번째 질문이므로 쿼리를 증명하는 것은 적절한 변수 바인딩(즉, 접속사)을 사용하여 해당 조항의 본문을 증명하는 것과 동일하다.(parent_child(Z,sally), parent_child(Z,erica))증명되어야 할 다음 목표는 이 접속사 중 가장 왼쪽이다.parent_child(Z, sally)두 개의 조항 헤드가 이 목표와 일치한다.이 시스템은 선택 지점을 만들고 첫 번째 대안을 시도하는데, 그 신체가 바로 그 것이다.father_child(Z, sally)이 목표는 그 사실을 이용해서 증명될 수 있다.father_child(tom, sally)그래서 구속력이 있다.Z = tom생성되며, 다음 목표는 상기 연결의 두 번째 부분이다.parent_child(tom, erica). 다시 말하지만, 이는 해당 사실에 의해 증명될 수 있다.모든 목표가 증명될 수 있었기 때문에, 질의는 성공한다.쿼리에 변수가 없으므로 바인딩이 사용자에게 보고되지 않는다.다음과 같은 변수가 포함된 쿼리:
?- father_child(아버지, 아이). 역추적 시 유효한 답을 모두 열거한다.
위에 언급된 코드를 사용하여 쿼리를 확인하십시오.?- sibling(sally, sally).또한 성공한다.원하는 경우 관련 제한을 설명하기 위해 추가 목표를 삽입할 수 있다.
루프 및 재귀
반복 알고리즘은 재귀 술어를 통해 구현될 수 있다.프롤로그 시스템은 일반적으로 꼬리의 재귀성을 나타내는 결정론적 술어에 대해 TCO(Tail Call Optimization)라고 하는 잘 알려진 최적화 기법을 실행하거나, 보다 일반적으로 꼬리 통화: 꼬리 위치에서의 통화를 수행하기 전에 절의 스택 프레임을 폐기한다.따라서 결정론적 꼬리-재귀 술어는 다른 언어의 루프처럼 일정한 스택 공간으로 실행된다.
절단
베인 상처 ()!규칙 내부에서는 Prolog가 컷 뒤에 있는 술어를 역추적하지 못하게 한다.
술어를 붙이다(X) :- 하나(X), !, 두 개(X). 의 최초 발견가치가X어떤 것을 위하여one(X)에 대한 진실이다.two(X)거짓으로
익명 변수
익명 변수_값에 구속되지 않으며 술어로 여러 번 사용할 수 있다.
예를 들어 지정된 값을 찾기 위해 목록 검색:
포함하다(V, [V _]). 포함하다(V, [_ T]) :- 포함하다(V, T). 부정
기본 제공 프로로그 술어\+/1부정을 실패로 제공함으로써 비단조적 추론을 가능하게 한다.목표\+ illegal(X)규칙상
법률상의(X) :- \+ 불법의(X). 다음과 같이 평가된다: 프롤로그는illegal(X). 만약 그 목표에 대한 증거가 발견될 수 있다면, 원래의 목표(즉,\+ illegal(X))이 실패하다.증거를 찾을 수 없다면 원래의 목표는 성공한다.그러므로, The는\+/1접두사 연산자를 쿼리 이후 "증명할 수 없는" 연산자라고 한다.?- \+ Goal.목표가 증명할 수 없는 경우 성공한다.이러한 부정은 그 주장이 "근거"(즉, 변수가 없는 경우)라면 건전하다.논쟁에 변수가 포함되면 건전성은 상실된다.특히 질의는?- legal(X).이제 합법적인 모든 것을 열거하는데 사용될 수 없다.
의미론
선언적 읽기에서는 규칙의 순서와 규칙 내의 목표의 순서는 논리적 분리와 결합은 서로 상통하기 때문에 관련이 없다.그러나 절차적으로 효율적 이유나 평가 순서가 중요한 불순물 내장 술어의 의미론 때문에 프롤로그의 실행 전략을 고려하는 것이 중요한 경우가 많다.또한 프롤로그 통역사가 제공된 순서대로 조항을 통일하려고 할 때, 정확한 명령을 내리지 못하면 다음과 같이 무한 재귀로 이어질 수 있다.
술어1(X) :- 술어2(X,X). 술어2(X,Y) :- 술어1(X), X \= Y. 이 순서에 따라 양식에 대한 모든 질의
?- 술어1(원자의). 스택이 소진될 때까지 재발할 것이다.그러나 마지막 3개 라인이 다음과 같이 변경되었다.
술어2(X,Y) :- X \= Y, 술어1(X). 같은 질의가 아주 짧은 시간 안에 No. 결과를 이끌어 낼 것이다.
확정조항 문법
확정조항 그래마(DCGs)라는 특별한 표기법이 있다.다음을 통해 정의된 규칙-->/2대신에:-/2전처리기(전처리기)에 의해 확장됨expand_term/2, 다른 언어로 된 매크로와 유사한 시설) 몇 가지 간단한 재작성 규칙에 따라 일반 프롤로그 조항이 생기게 된다.가장 두드러지게, 재작성은 술어를 다른 언어의 모노드와 유사하게, 암시적으로 주위에서 스레딩하는 데 사용될 수 있는 두 개의 추가적인 인수로 무장시킨다.DCG는 차이를 나열할 수 있는 편리한 인터페이스를 제공하므로 파서나 목록 생성기를 작성하는 데 종종 사용된다.
파서 예제
더 큰 예는 구문 분석에서 Prolog를 사용할 수 있는 가능성을 보여준다.
Backus-Naur 형식으로 표현된 문장으로 볼 때:
<, sentence>.::=<>stat_part>, <, stat_part>.::=<>statement>, <, stat_part>, <, statement>, <, statement>.::=<>id>^<>expression><>expression>.::=<>operand>,<>expression>,<><,<>operand>,<>operand>.::=<>id>, <, digit>,<>id>.::b<>=, digit>.::=0..9<><value>::-+-*이는 DCGs를 사용하여 Prolog에 기록될 수 있으며, 이는 하나의 토큰 룩어헤드로 예측 분석기에 해당한다.
형을 언도하다(S) --> 성명서(S0), 문장_r(S0, S). 문장_r(S, S) --> []. 문장_r(S0, Seq.(S0, S)) --> 성명서(S1), 문장_r(S1, S). 성명서(할당하다(아이디,E)) --> id(아이디), [=], 표현(E), [;]. 표현(E) --> 용어(T), 표현_r(T, E). 표현_r(E, E) --> []. 표현_r(E0, E) --> [+], 용어(T), 표현_r(더하기(E0,T), E). 표현_r(E0, E) --> [-], 용어(T), 표현_r(빼다(E0, T), E). 용어(T) --> 요소(F), 용어_r(F, T). 용어_r(T, T) --> []. 용어_r(T0, T) --> [*], 요소(F), 용어_r(시대(T0, F), T). 요소(id(아이디)) --> id(아이디). 요소(숫자를 매기다(D)) --> [D], { (번호를 붙이다(D) ; 시합을 하다(D)), 사이에(0, 9, D)}. id(a) --> [a]. id(b) --> [b]. 이 코드는 문장(토큰 목록으로 제공)과 추상 구문 트리(AST) 사이의 관계를 정의한다.쿼리 예:
?- 구절(형을 언도하다(AST), [a,=,1,+,3,*,b,;,b,=,0,;]). AST = Seq.(할당하다(a, 더하기(숫자를 매기다(1), 시대(숫자를 매기다(3), id(b)))), 할당하다(b, 숫자를 매기다(0))) ; AST는 Prolog 용어를 사용하여 표현되며 최적화를 적용하거나, 그러한 표현을 기계 코드에 컴파일하거나, 그러한 문장을 직접 해석하는 데 사용할 수 있다.술어의 관계적 성격에서 전형적으로 그렇듯이, 이러한 정의는 문장들을 구문 분석하거나 생성하는 데 사용될 수 있으며, 또한 주어진 트리가 주어진 토큰 리스트에 해당하는지를 확인하는 데도 사용될 수 있다.공정한 열거에 반복적인 심층화를 사용함으로써, 각 임의적이면서도 고정된 문장과 그에 상응하는 AST가 결국 생성될 것이다.
?- 길이(토큰, _), 구절(형을 언도하다(AST), 토큰). 토큰 = [a, =, a, (;)], AST = 할당하다(a, id(a)) ; 토큰 = [a, =, b, (;)], AST = 할당하다(a, id(b)) 등. 
