B-프로로그

B-Prolog는 일치 조항, 이벤트 처리를 위한 액션 규칙, 유한 도메인 제약 조건 해결, 배열 및 해시 테이블, 선언적 루프, 테이블링 등 몇 가지 확장된 기능을 갖춘 표준 Prolog 언어를 고성능으로 구현한 것이었다.1994년에 처음 출시된 B-Prolog는 현재 널리 사용되는 CLP 시스템이다.제2회 국제솔버대회에서는 B-Prolog의 제약 해결사가 2개 부문에서 1위를 차지했으며,^[1] 제2회 ASP솔버대회에서는 P클래스 2위, 제3회 ASP솔버대회에서는 종합 2위를 차지하기도 했다.^[3]B-프롤로그는 논리 기반의 확률적 추론과 학습 시스템인 프리즘 시스템을 뒷받침한다.B-Prolog는 상업용 제품이지만 학습 및 비영리 연구 목적으로 무료로 사용할 수 있다(상업용 개별 사용자를 포함한 개인 사용자용 버전 7.8이므로 B-Prolog는 무료).B-Prolog는 더 이상 적극적으로 개발되지 않고 Picat 프로그래밍 언어의 기초를 이룬다.

일치절

일치 조항은 결정성과 입출력 통합이 명시적으로 명시되어 있는 조항의 형식이다.컴파일러는 일치하는 조항을 일치하는 트리로 변환하고 모든 입력 인수에 대한 색인을 생성한다.복잡한 프로그램 분석이나 전문화가 필요 없고 생성된 코드는 더 작고 빠른 경향이 있기 때문에 일치 조항의 편성은 일반 프롤로그 조항의 편찬보다 훨씬 간단하다.B-Prolog 컴파일러와 대부분의 라이브러리 술어는 일치하는 조항으로 쓰여 있다.

일치 조항은 다음과 같은 형식을 취한다.

H, G => B 

어디에H원자 공식이야G그리고B원자 공식의 두 시퀀스 입니다. H머리라고 불리고,G경비원, 그리고B조항의 본문호출 없음G변수를 바인딩할 수 있음H그리고 모든 전화들G인라인 테스트여야 한다.즉 경비원이 납작해야 한다.다음은 두 개의 정렬된 목록을 병합하는 일치 절의 술어를 예시한다.

합병하다([],이스,Zs) => Zs=이스. 합병하다(엑스스,[],Zs) => Zs=엑스스. 합병하다([X 엑스스],[Y 이스],Zs),X<Y => Zs=[X ZST],합병하다(엑스스,[Y 이스],ZST). 합병하다(엑스스,[Y 이스],Zs) => Zs=[Y ZST],합병하다(엑스스,이스,ZST). 

반대자들[Y Ys]제3절의 머리와 몸통에서 모두 발생한다.용어 재구성을 피하기 위해 이 조항을 다음과 같이 다시 쓸 수 있다.

합병하다([X 엑스스],이스,Zs),이스=[Y _],X<Y => Zs=[X ZST],합병하다(엑스스,이스,ZST). 

호출Ys=[Y _]수비 시합에서.Ys패턴에 반하여[Y _].

작업 규칙

환경에 반응할 수 있는 "활성" 하위 골격을 프로그래밍할 수 있는 시설이 없다는 것은 논리 프로그래밍의 약점 중 하나로 여겨져 왔다.이를 극복하기 위해 B-Prolog는 프로그래밍 에이전트를 위한 간단하면서도 강력한 언어인 AR(Action Rules)을 제공한다.에이전트는 지연될 수 있고 나중에 이벤트에 의해 활성화될 수 있는 하위 그룹이다.에이전트가 활성화될 때마다 일부 작업이 실행될 수 있다.에이전트는 인스턴스화, 도메인, 시간 및 사용자 정의 이벤트를 포함한 다양한 종류의 이벤트에 에이전트가 대응할 수 있다는 점에서 초기 Prolog 시스템 및 프로세스에서 지연 구성보다 더 일반적인 개념이다.

작업 규칙에는 다음이 필요하다.

H, G, {E} => B 

어디에H요원들을 위한 패턴이지만G요원들의 일련의 조건들이야E에이전트를 활성화할 수 있는 이벤트의 패턴 집합이며B활성 상태일 때 에이전트가 수행하는 일련의 작업.이벤트 패턴이 있을 때E동봉된 가새들이 없어지면서, 행동 규칙이 일치하는 조항으로 변질된다.

제약 조건 전파기와 대화형 그래픽 사용자 인터페이스를 프로그래밍하기 위해 일련의 내장 이벤트가 제공된다.예를 들어,ins(X)변수를 사용할 때 게시되는 이벤트X즉흥적이다.사용자 프로그램은 자체 이벤트를 만들고 게시할 수 있으며, 이를 처리할 에이전트를 정의할 수 있다.사용자 정의 이벤트는 다음과 같은 형태를 취한다.event(X,O)어디에X서스펜션 변수라고 불리는 변수로서 이벤트를 처리 에이전트와 연결하며O에이전트에게 전송할 정보를 포함하는 Prolog 용어.빌트인post(E)이벤트를 게시하다E.

다음 예를 생각해 보십시오.

메아리치다(X),{사건(X,메스)}=>글씨를 쓰다(메스). 핑핑을 하다(T),{시간(T)} => 글씨를 쓰다(핑핑을 하다). 

에이전트echo(X)어떤 메시지를 받든 반향한다.예를 들어,

?-메아리치다(X),우편으로 부치다(사건(X,안녕)),우편으로 부치다(사건(X,세계)). 

메시지를 출력하다hello그 뒤를 이어world. 에이전트ping(T)타이머의 시간 이벤트에 응답T. 시간 이벤트를 수신할 때마다 메시지를 인쇄한다.ping예를 들어,

?-타이머를 치다(T,1000),핑핑을 하다(T),되풀이하여 말하다,실패하다. 

매 초마다 시간 이벤트를 게시하는 타이머를 만들고 에이전트를 만든다.ping(T)그 사건에 반응하기 위해서.에이전트를 영구적으로 만들기 위해 에이전트 이후의 루프가 필요한 경우.

AR은 단순한 동시성 프로그래밍, 제약조건 전파자 구현, 대화형 그래픽 사용자 인터페이스 개발에 유용한 것으로 밝혀졌다.제약 처리 규칙(CHR)과 ASP(Answer Set Programs)를 편찬하는 중간 언어의 역할을 해왔다.

CLP(FD)

많은 프롤로그 기반 유한 도메인 제약 해결사들과 마찬가지로 B-Prolog의 유한 도메인 해결사도 CHIP 시스템의 영향을 많이 받았다.첫 번째 완전 해결사는 1997년 3월 B-Prolog 버전 2.1로 출시되었다.그 해결사는 지연 조항이라 불리는 AR의 초기 버전에서 실행되었다.지난 10년 동안, 구현 언어 AR은 풍부한 등급의 도메인 이벤트를 지원하도록 확장되었다(ins(X),bound(X),dom(X,E)그리고dom_any(X,E)프로그래밍 제약 조건 전파자 및 시스템은 새로운 도메인(부울, 트리 및 유한 집합), 전역 제약 조건 및 특수화된 고속 제약 조건 전파자로 강화되었다.최근 두 사람의 빌트인(Built-in)은in/2그리고notin/2양수 및 음수 테이블(확장이라고도 함) 제약 조건을 허용하도록 확장되었다.

AR을 구현 언어로 채용한 덕분에 B-Prolog의 제약 해결 부분(프로로그 코드 3800라인, 코멘트·공간을 포함한 C 코드 6000라인)은 상대적으로 작지만 그 성능이 매우 경쟁력이 있다.AR 언어는 문제별 전파자를 구현하기 위해 사용자에게 개방된다.예를 들어, 다음은 제약조건에 대한 호 일관성을 유지하기 위한 전파기를 정의한다.X+Y #= C. 내부 요소일 때마다Ey의 도메인에서 제외되다Y, 이 전파자는 제외하도록 트리거됨Ex, 의 상대Ey, 의 도메인에서X. 제약조건에 대하여X+Y #= C두 개의 전파기를 생성해야 해, 다시 말해,'X_in_C_Y_ac'(X,Y,C)그리고'X_in_C_Y_ac'(Y,X,C), 호 일관성을 유지하기 위해.이 두 개의 전파자 외에도, 우리는 또한 존재하지 않기 때문에 간격 일관성을 유지하기 위한 전파자를 생성할 필요가 있다.dom(Y,Ey)제외된 값이 바운드일 경우 이벤트가 게시된다.제약조건은 전파자가 생성되기 전에 호가 일치하도록 사전 처리되어야 한다.

'X_in_C_'Y_ac'(X,Y,C),시합을 하다(X),시합을 하다(Y),    {돔을 씌우다(Y,아이)}    =>             Ex 이다 C-아이,            domain_set_false(X,Ex). 'X_in_C_'Y_ac'(X,Y,C) => 진실의. 

배열 및 배열 첨자 표기법

B-Prolog에서 구조물의 최대 경지는 65535이다.이것은 구조물을 1차원 배열로 사용할 수 있고, 다차원 배열을 구조로 나타낼 수 있다는 것을 수반한다.어레이 생성을 용이하게 하기 위해 B-Prolog는 "built-in"이라는 기본 기능을 제공한다.new_array(X,Dims)어디에X비인스턴트 변수여야 하며Dims배열의 치수를 지정하는 양의 정수 목록예를 들어, 통화new_array(X,[10,20])묶다X첫 번째 치수는 10개의 원소를 가지고 있고 두 번째 치수는 20개의 원소를 가지고 있는 2차원 배열로.모든 배열 요소는 자유 변수로 초기화된다.

기본 제공 술어arg/3배열 요소에 접근하기 위해 사용될 수 있지만, 그것은 결과를 저장하기 위한 임시 변수와 다차원 배열의 요소에 접근하기 위한 통화 체인이 필요하다.어레이 요소에 쉽게 액세스할 수 있도록 B-Prolog는 어레이 첨자 표기법을 지원한다.X[I1,...,In]어디에X하나의 구조와 각각의Ii정수 표현식이다.그러나 어레이에 액세스하기 위한 이 일반적인 표기법은 표준 Prolog 구문의 일부가 아니다.이 표기법을 수용하기 위해 구문 분석기가 토큰을 삽입하도록 수정됨^변수 토큰 사이에[그래서 그 표기법.X[I1,...,In]의 줄임말일 뿐이다.X^[I1,...,In]. 이 표기법은 산술적 표현식, 제약조건 또는 호출의 인수로써 발생할 때 배열 접근으로 해석된다.@=/2. 다른 어떤 맥락에서도 그것은 용어 그 자체로 취급된다.배열 첨자 표기법은 목록 요소에 접근하는 데도 사용될 수 있다.예를 들어,nth/3술어는 다음과 같이 정의할 수 있다.

n번째(I,L,E) :- E @= L[I]. 

예측 및 목록 이해가 있는 루프

프롤로그는 루프를 설명하기 위해 반복에 의존한다.강력한 루프 구성의 부족은 종종 루프의 작은 보조 재귀 술어를 정의하는 것이 지루하기 때문에 프롤로그를 초보자들에게 덜 받아들여지고 경험 많은 프로그래머들에게 덜 생산적이게 만들었다.CLP(FD)와 같은 제약 프로그래밍 구조의 등장은 모델링 언어로서의 프롤로그의 이러한 약점을 더욱 드러냈다.B-Prolog는 "built-in"이라는 기본 제공foreach목록 구성을 위한 목록 이해 표기법과 컬렉션 반복용.

그foreach빌트인은 매우 간단한 구문과 의미론을 가지고 있다.예를 들어,

앞을 내다(A 에 [a,b], I 에 1..2, 글씨를 쓰다((A,I))) 

네 개의 튜플을 출력하다.(a,1),(a,2),(b,1)그리고(b,2). 구문론적으로,foreach마지막 인수가 일련의 집합에서 각 값의 조합에 대해 실행할 목표를 지정하는 가변 길이 호출이다.aforeach호출은 또한 각 반복에 로컬인 변수의 목록과 각 반복에서 값을 누적하는 데 사용할 수 있는 축전지의 목록을 제공할 수 있다.축전지로 우리는 사용할 수 있다.foreachAggregate를 계산하기 위한 반복을 설명한다.반복은 절차적으로 읽어야 하므로 Prolog와 잘 맞지 않는다.이러한 이유로, 우리는 기능 언어로부터 목록 이해 기법을 채택한다.목록 이해는 첫 번째 요소가 functor를 가진 목록이다.:'. 이 양식의 목록은 다음과 같은 통화의 목록 이해로 해석된다.@=/2및 산술적 제약 조건.예를 들어, 쿼리

X @= [(A,I) : A 에 [a,b], I 에 1..2] 

묶다X명부에 올라[(a,1),(a,2),(b,1),(b,2)]목록 이해는 다음과 같이 처리된다.foreach구현 시 축전지를 호출한다.

호출 위치foreach그리고 목록 포괄성은 꼬리가 되뇌는 술어로 번역된다.따라서 재귀 사용과 비교하여 이러한 구조를 사용하는 것에 대한 벌칙이 없거나 거의 없다.

루프 구조는 CLP(FD)의 모델링 능력을 상당히 강화한다.다음은 B-Prolog의 N-Queens 문제에 대한 프로그램을 제공한다.

여왕들(N):-     길이(Qs,N),     Qs :: 1..N,     앞을 내다(I 에 1..N-1, J 에 I+1..N,             (Qs[I] #\= Qs[J],              복근(Qs[I]-Qs[J]) #\= J-I)),     라벨링([ff],Qs),     글씨를 쓰다(Qs). 

목록의 배열 표기법은 설명을 단축하는 데 도움이 된다.그것 없이, The는foreach프로그램의 루프는 다음과 같이 작성되어야 할 것이다.

앞을 내다(I 에 1..N-1, J 에 I+1..N,[제,qj],         (n번째(Qs,I,제),          n번째(Qs,J,qj),          제 #\= qj,          복근(제-qj) #\= J-I)), 

어디에Qi그리고Qj각 반복마다 로컬로 선언된다.다음은 보드의 각 사각형에 대해 부울 변수를 사용하는 N-Queens 문제에 대한 프로그램을 제공한다.

bool_booles(N):-    new_array(Qs,[N,N]),    바스 @= [Qs[I,J] : I 에 1..N, J 에 1..N],    바스 :: 0..1,    앞을 내다(I 에 1..N,     각 행에서 여왕 1명 비율            합계를 내다([Qs[I,J] : J 에 1..N]) #= 1),    앞을 내다(J 에 1..N,     각 열에 여왕이 한 명씩 있는 비율(%)            합계를 내다([Qs[I,J] : I 에 1..N]) #= 1),    앞을 내다(K 에 1-N..N-1, 각 왼쪽-아래쪽 diag에서 최대 한 개의 여왕에서 백분율            합계를 내다([Qs[I,J] : I 에 1..N, J 에 1..N, I-J=:=K]) #=< 1),    앞을 내다(K 에 2..2*N,   각 왼쪽 위 diag에서 최대 한 개의 퀸에서 백분율            합계를 내다([Qs[I,J] : I 에 1..N, J 에 1..N, I+J=:=K]) #=< 1),    라벨링(바스),    앞을 내다(I 에 1..N,[배를 젓다],            (배를 젓다 @= [Qs[I,J] : J 에 1..N], 글씨를 쓰다(배를 젓다))). 

태블링

태블링은 초보자들이 실행 가능한 선언적 프로그램을 쓸 수 있도록 돕는 것뿐만 아니라 자연 언어 처리, 모델 확인, 기계 학습 애플리케이션과 같은 실제 응용 프로그램 개발에도 점점 더 중요한 것으로 밝혀졌다.B-Prolog는 선형 태블링이라고 불리는 태블링 메커니즘을 구현하는데, 이것은 고정된 포인트를 계산하기 위해 루핑 하위 골의 중단이 아니라 루핑 하위 골의 반복적인 계산에 기초한다.탭링 의존도가 높은 프리즘 시스템은 B-Prolog의 탭링 시스템의 설계와 구현에 주된 원동력이 되어 왔다.

태블링의 아이디어는 전화 번호판의 답을 외우고 그 답을 사용하여 후속 변종 통화를 해결하는 것이다.B-Prolog에서 XSB에서와 같이 tableed 술어는 다음과 같은 형태로 선언에 의해 명시적으로 선언된다.

:-테이블 P1/N1,...,PK/NK. 

예를 들어, 다음의 tableed 술어는 다음과 같이 관계의 transitive closure를 정의한다.edge/2.

:-테이블 경로/2. 경로(X,Y):-가장자리를 잡다(X,Y). 경로(X,Y):-경로(X,Z),가장자리를 잡다(Z,Y). 

태블링을 통해 프로그램에 대한 모든 쿼리는 기간 크기가 제한되는 한 종료될 수 있다.

기본적으로, 전화 연결의 모든 인수는 변형 확인에 사용되고 모든 답변은 전화 연결 술어에 대해 연결된다.B-Prolog는 테이블 모드를 지원하는데, 이 모드에서는 시스템이 변형 확인과 테이블 답변에서 입력 인수만 선택적으로 사용할 수 있다.테이블 모드 선언

:-테이블 p(M1,...,Mn):C. 

시스템에 표 그리는 법을 가르치다.p/n어디에C카디널리티 한계(cardinality limit)라고 하는 정수로, table을 할 수 있는 답변의 수를 제한하며, 각각Mi할 수 있는 모드다.min,max,+(iii), 또는-(출력)모드를 사용한 인수min또는max출력된 것으로 가정한다.카디널리티가 제한되는 경우C이다1, 앞의 '로 생략할 수 있다.:'.

표 모드는 동적 프로그래밍 문제의 선언적 설명에 매우 유용하다.예를 들어, 다음 프로그램은 한 쌍의 노드 사이에 최소 중량을 가진 경로를 찾기 위한 Dijkstra의 알고리즘을 인코딩한다.

:-테이블 sp(+,+,-,분). sp(X,Y,[(X,Y)],W) :-     가장자리를 잡다(X,Y,W). sp(X,Y,[(X,Z)경로],W) :-     가장자리를 잡다(X,Z,W1),     sp(Z,Y,경로,W2),     W 이다 W1+W2. 

테이블 모드에서는 각 노드 쌍에 대해 최소 중량을 가진 하나의 경로만 배선되어 있다고 명시한다.

참조

외부 링크

• 공식 웹사이트: http://www.picat-lang.org/bprolog/
• B-Prolog로 해결하는 방법
• B-Prolog의 언어특성과 건축
• Prolog 시스템과 CLP 시스템의 성능 비교
• 로그톡 성능