B-Prolog

B-Prolog był wysokowydajną implementacją standardowego języka Prolog z kilkoma rozszerzonymi funkcjami, w tym klauzulami dopasowującymi, regułami akcji do obsługi zdarzeń, rozwiązywaniem ograniczeń w domenie skończonej, tablicami i tablicami skrótów, pętlami deklaratywnymi i tworzeniem tabel. Wydany po raz pierwszy w 1994 roku, B-Prolog jest obecnie szeroko stosowanym CLP . Narzędzie do rozwiązywania problemów B-Prolog zajęło czołowe miejsca w dwóch kategoriach II Międzynarodowego Konkursu Solvers, a także drugie miejsce w klasie P w drugim konkursie rozwiązywania ASP oraz drugie miejsce w klasyfikacji generalnej trzeciego konkursu rozwiązywania problemów ASP. B-Prolog stanowi podstawę systemu PRISM, opartego na logice probabilistycznego systemu rozumowania i uczenia się. B-Prolog jest produktem komercyjnym, ale można go bezpłatnie wykorzystywać do celów edukacyjnych i badawczych non-profit (od wersji 7.8 dla użytkowników indywidualnych, w tym indywidualnych użytkowników komercyjnych, B-Prolog jest bezpłatny). B-Prolog nie jest już aktywnie rozwijany, ale stanowi podstawę języka programowania Picat.

Dopasowane klauzule

Klauzula dopasowująca jest formą klauzuli, w której determinacja i ujednolicenie wejścia/wyjścia są wyraźnie oznaczone. Kompilator tłumaczy pasujące klauzule na pasujące drzewa i generuje indeksy dla wszystkich argumentów wejściowych. Kompilacja klauzul dopasowujących jest znacznie prostsza niż w przypadku normalnych klauzul Prologu, ponieważ nie jest konieczna złożona analiza programu ani specjalizacja; a wygenerowany kod jest zwykle bardziej zwarty i szybszy. Kompilator B-Prolog i większość predykatów bibliotecznych jest zapisywana w klauzulach dopasowujących.

Klauzula dopasowania ma następującą postać:

    H  ,  G  =>  B

gdzie H to wzór atomowy, G i B to dwie sekwencje wzorów atomowych. H nazywa się głową, G strażnikiem, a B treścią klauzuli. Żadne wywołanie w G nie może powiązać zmiennych w H , a wszystkie wywołania w G muszą być testami liniowymi. Innymi słowy, garda musi być płaska. Poniżej podano przykład predykatu w klauzulach dopasowujących, który łączy dwie posortowane listy:

  
  
  
   scalaj  ([],  Ys  ,  Zs  )  =>  Zs  =  Ys  .  scalanie  (  Xs  ,[],  Zs  )  =>  Zs  =  Xs  .  scal  ([  X  |  Xs  ],[  Y  |  Ys  ],  Zs  ),  X  <  Y  =>  Zs  =  [  X  |  ZsT  ],  połącz  (  Xs  , [  Y  |  Ys  ],  ZsT  ).  połącz  (  Xs  ,[  Y  |  Ys  ],  Zs  )  =>  Zs  =  [  Y  |  ZsT  ],  scalanie  (  Xs  ,  Ys  ,  ZsT  ).

Wady [Y|Ys] występują zarówno w nagłówku, jak iw treści trzeciej klauzuli. Aby uniknąć rekonstrukcji terminu, możemy przepisać klauzulę w następujący sposób:

   połącz  ([  X  |  Xs  ],  Ys  ,  Zs  ),  Ys  =  [  Y  |  _  ],  X  <  Y  =>  Zs  =  [  X  |  ZsT  ],  scalanie  (  Xs  ,  Ys  ,  ZsT  ).

Wywołanie Ys=[Y|_] w strażniku dopasowuje Ys do wzorca [Y|_] .

Zasady akcji

Brak możliwości programowania „aktywnych” celów cząstkowych, które mogą reagować na środowisko, został uznany za jedną ze słabości programowania logicznego. Aby temu zaradzić, B-Prolog zapewnia prosty, a jednocześnie potężny język, zwany Action Rules (AR), dla agentów programistycznych. Agent to cel cząstkowy, który można opóźnić i który może być później aktywowany przez zdarzenia. Za każdym razem, gdy agent jest aktywowany, może zostać wykonana jakaś akcja. Agenci są pojęciem bardziej ogólnym niż konstrukcje opóźniające we wczesnych systemach i procesach Prologu w językach programowania w logice współbieżnej w tym sensie, że agenci mogą reagować na różne rodzaje zdarzeń, w tym tworzenie instancji, dziedzinę, czas i zdarzenia zdefiniowane przez użytkownika.

Reguła akcji jest następująca

     H.  ,  G.  ,  {  mi.  }  =>  B

gdzie H to wzorzec dla agentów, G to sekwencja warunków dla agentów, E to zestaw wzorców dla zdarzeń, które mogą aktywować agentów, a B to sekwencja działań wykonywanych przez agentów, gdy są aktywowani. Gdy brakuje wzorca zdarzenia E wraz z nawiasami klamrowymi, reguła akcji degeneruje się do klauzuli dopasowania.

Dostępny jest zestaw wbudowanych zdarzeń do programowania propagatorów ograniczeń i interaktywnych graficznych interfejsów użytkownika. Na przykład ins(X) jest zdarzeniem wysyłanym, gdy tworzona jest instancja zmiennej X. Program użytkownika może tworzyć i publikować własne zdarzenia oraz definiować agentów do ich obsługi. Zdarzenie zdefiniowane przez użytkownika ma postać event(X,O) , gdzie X jest zmienną, zwaną zmienną zawieszającą, która łączy zdarzenie z jego agentami obsługi, a O jest terminem Prologu zawierającym informacje, które mają być przesłane do agenci. Wbudowany post(E) wysyła zdarzenie E .

Rozważ następujące przykłady:


   echo  (  X  ), {  zdarzenie  (  X  ,  Mes  )}  =>  writeln  (  Mes  ).  ping  (  T  ), {  czas  (  T  )}  =>  writeln  (  ping  ).

Agent echo(X) wysyła echo każdej otrzymanej wiadomości. Na przykład,

 ?-  echo  (  X  ),  post  (  zdarzenie  (  X  ,  cześć  )),  post  (  zdarzenie  (  X  ,  świat  )).

wyświetla komunikat hello, po którym następuje world . Agent ping(T) odpowiada na zdarzenia czasowe z timera T . Za każdym razem, gdy odbiera zdarzenie czasowe, drukuje komunikat ping . Na przykład,

 ?-  timer  (  T  ,  1000  ),  ping  (  T  ),  powtórz  ,  niepowodzenie  .

tworzy timer, który wysyła zdarzenie czasowe co sekundę i tworzy agenta ping(T) w celu reagowania na zdarzenia. Pętla po agencie jest potrzebna, aby agent był wieczny.

AR okazał się przydatny do programowania prostej współbieżności, implementacji propagatorów ograniczeń i tworzenia interaktywnych graficznych interfejsów użytkownika. Służył jako język pośredni do kompilowania reguł obsługi ograniczeń (CHR) i programów zestawu odpowiedzi (ASP).

CLP(FD)

Podobnie jak wiele programów do rozwiązywania problemów w domenie skończonej opartych na Prologu, program do rozwiązywania problemów w domenie skończonej B-Prolog był pod silnym wpływem systemu CHIP . Pierwszy pełnoprawny solver został wydany wraz z B-Prolog w wersji 2.1 w marcu 1997 roku. Solver ten został zaimplementowany we wczesnej wersji AR, zwanej klauzulami opóźniającymi. W ciągu ostatniej dekady język implementacji AR został rozszerzony o obsługę bogatej klasy zdarzeń domenowych ( ins(X) , bound(X) , dom(X,E) i dom_any(X,E) ) do programowania propagatorów ograniczeń a system został wzbogacony o nowe domeny (boolowskie, drzewa i zbiory skończone), ograniczenia globalne i wyspecjalizowane szybkie propagatory ograniczeń. Ostatnio dwie wbudowane in/2 i notin/2 zostały rozszerzone, aby umożliwić dodatnie i ujemne ograniczenia tabeli (zwane również rozszerzeniami).

Dzięki zastosowaniu AR jako języka implementacji, część B-Prolog zajmująca się rozwiązywaniem ograniczeń jest stosunkowo niewielka (3800 linii kodu Prologu i 6000 linii kodu C, wliczając komentarze i spacje), ale jej wydajność jest bardzo konkurencyjna. Język AR jest otwarty dla użytkownika w celu implementacji propagatorów specyficznych dla problemu. Na przykład poniżej zdefiniowano propagator do zachowania spójności łuku dla wiązania X+Y #= C . Ilekroć wewnętrzny element Ey jest wykluczony z domeny Y , ten propagator jest wyzwalany w celu wykluczenia Ex , odpowiednika Ey , z domeny X. Dla ograniczenia X+Y #= C musimy wygenerować dwa propagatory, a mianowicie 'X_in_C_Y_ac'(X,Y,C) i 'X_in_C_Y_ac'(Y,X,C) , aby zachować spójność łuku. Oprócz tych dwóch propagatorów musimy również wygenerować propagatory, aby zachować spójność interwałów, ponieważ żadne dom(Y,Ey) nie jest wysyłane, jeśli wykluczona wartość jest ograniczeniem. Ograniczenie musi zostać wstępnie przetworzone, aby było spójne przed wygenerowaniem propagatorów.


   
            
             
   
   'X_in_C_Y_ac'  (  X  ,  Y  ,  C  ),  var  (  X  ),  var  (  Y  ),  {  dom  (  Y  ,  Ey  )}  =>  Ex  to  C  -  Ey  ,  domain_set_false  (  X  ,  Ex  ).  'X_in_C_Y_ac'  (  X  ,  Y  ,  C  )  =>  true  .

Tablice i notacja indeksu tablicy

W B-Prologu maksymalna liczba struktur wynosi 65535. Oznacza to, że struktura może być używana jako tablica jednowymiarowa, a tablica wielowymiarowa może być reprezentowana jako struktura struktur. Aby ułatwić tworzenie tablic, B-Prolog zapewnia wbudowaną funkcję, zwaną new_array(X,Dims) , gdzie X musi być zmienną niekonstancjonowaną, a Dims listę dodatnich liczb całkowitych, które określają wymiary tablicy. Na przykład wywołanie new_array(X,[10,20]) wiąże X z tablicą dwuwymiarową, której pierwszy wymiar ma 10 elementów, a drugi wymiar ma 20 elementów. Wszystkie elementy tablicy są inicjowane jako wolne zmienne.

Wbudowany predykat arg/3 może służyć do uzyskiwania dostępu do elementów tablicy, ale wymaga tymczasowej zmiennej do przechowywania wyniku oraz łańcucha wywołań w celu uzyskania dostępu do elementu tablicy wielowymiarowej. Aby ułatwić dostęp do elementów tablicy, B-Prolog obsługuje notację tablicową w indeksie dolnym X[I1,...,In] , gdzie X jest strukturą, a każdy Ii jest wyrażeniem całkowitym. Ta popularna notacja dostępu do tablic nie jest jednak częścią standardowej składni Prologu. Aby dostosować się do tej notacji, parser jest modyfikowany, aby wstawić token ^ między tokenem zmiennej a [ . Zatem notacja X[I1,...,In] jest skrótem dla X^[I1,...,In] . Ta notacja jest interpretowana jako dostęp do tablicy, gdy występuje w wyrażeniu arytmetycznym, ograniczeniu lub jako argument wywołania @=/2 . W każdym innym kontekście jest traktowany jako sam termin. Notacja indeksu tablicowego może być również używana do uzyskiwania dostępu do elementów list. Na przykład n-ty/3 można zdefiniować w następujący sposób:

     n-ty  (  ja  ,  L  ,  mi  )  :-  mi  @=  L  [  ja  ].

Pętle z foreach i rozumieniem list

Prolog opiera się na rekurencji do opisu pętli. Brak potężnych konstrukcji pętli prawdopodobnie sprawił, że Prolog jest mniej akceptowalny dla początkujących i mniej produktywny dla doświadczonych programistów, ponieważ często nudne jest definiowanie małych pomocniczych predykatów rekurencyjnych dla pętli. Pojawienie się konstrukcji programowania z ograniczeniami, takich jak CLP(FD), dodatkowo ujawniło tę słabość Prologu jako języka modelowania. B-Prolog zapewnia wbudowany, zwany foreach , do iteracji po kolekcjach oraz notację rozumienia list do konstruowania list.

Wbudowana funkcja foreach ma bardzo prostą składnię i semantykę. Na przykład,

       foreach  (  A  w  [  a  ,  b  ],  I  w  1..2  ,  napisz  ((  A  ,  I  )))

wyprowadza cztery krotki (a,1) , (a,2) , (b,1) i (b,2) . Składniowo, foreach jest wywołaniem o zmiennej długości, którego ostatni argument określa cel do wykonania dla każdej kombinacji wartości w sekwencji kolekcji. Wywołanie foreach może również podać listę zmiennych lokalnych dla każdej iteracji oraz listę akumulatorów, których można użyć do akumulacji wartości z każdej iteracji. W przypadku akumulatorów możemy użyć foreach do opisania cykli dla agregatów obliczeniowych. Rekurencje należy odczytywać proceduralnie i dlatego nie pasują dobrze do Prologu. Z tego powodu przyjmujemy notację rozumienia listy z języków funkcjonalnych. Lista składana to lista, której pierwszym elementem jest funktor „ : ”. Lista w tej formie jest interpretowana jako rozumienie listy w wywołaniach @=/2 i ograniczeniach arytmetycznych. Na przykład zapytanie

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

wiąże X z listą [(a,1),(a,2),(b,1),(b,2)] . Zrozumienie listy jest traktowane jako foreach z akumulatorem w implementacji.

Wywołania foreach i rozumienia list są tłumaczone na predykaty rekurencyjne ogona. Dlatego nie ma kary za użycie tych konstrukcji lub jest ona niewielka w porównaniu z użyciem rekurencji.

Konstrukcje pętli znacznie zwiększają moc modelowania CLP(FD). Poniżej przedstawiono program dla problemu N-królowych w B-Prologu:


    
      
         
              
               
    
     królowe  (  N  ): -  długość  (  Qs  ,  N  ),  Qs  ::  1.  .  N  ,  foreach  (  I  w  1.  .  N  -  1  ,  J  w  I  +  1.  .  N  ,  (  Qs  [  I  ]  #\=  Qs  [  J  ],  abs  (  Qs  [  I  ]  -  Qs  [  J  ])  #\=  J  -  I  )),  etykietowanie  ([  ff  ],  Qs  ),  writeln  (  Qs  ).

Notacja tablicowa na listach pomaga skrócić opis. Bez niego foreach w programie musiałaby być napisana w następujący sposób:

     
        
         
           
            foreach  (  I  w  1.  .  N  -  1  ,  J  w  I  +  1.  .  N  ,[  Qi  ,  Qj  ],  (  n-ty  (  Qs  ,  I  ,  Qi  ),  n-ty  (  Qs  ,  J  ,  Qj  ),  Qi  #\=  Qj  ,  abs  (  Qi  -  Qj  )  #\=  J  -  I  )),

gdzie Qi i Qj są deklarowane jako lokalne dla każdej iteracji. Poniżej przedstawiono program dla problemu N-królowych, który wykorzystuje zmienną logiczną dla każdego kwadratu na planszy.


   
            
     
          
                 
          
                 
      
                     
        
                     
   
     
                   bool_queens  (  N  ):-  nowa_tablica  (  Qs  ,[  N  ,  N  ]),  Vars  @=  [  Qs  [  I  ,  J  ]  :  I  w  1.  .  N  ,  J  w  1.  .  N  ],  Vars  ::  0..1  ,  foreach  (  I  w  1.  .  N  ,  % jednego hetmana w każdym rzędzie  suma  ([  Qs  [  I  ,  J  ]  :  J  w  1.  .  N  ])  #=  1  ),  foreach  (  J  w  1.  .  N  ,  % jednego hetmana w każdej kolumnie  suma  ([  Qs  [  I  ,  J  ]  :  I  w  1.  .  N  ])  #=  1  ),  foreach  (  K  w  1  -  N  ..  N  -  1  ,  % co najwyżej jeden hetman w każdej lewej diag  sumie  ([  Qs  [  I  ,  J  ]  :  I  w  1.  .  N  ,  J  w  1.  .  N  ,  I  -  J  =:=  K  ])  #=<  1  ),  foreach  (  K  w  2..2  *  N  ,  % co najwyżej jeden hetman w każdym lewym diagramie  sumy  ([  Qs  [  I  ,  J  ]  :  I  w  1.  .  N  ,  J  w  1.  .  N  ,  I  +  J  = :=  K  ])  #=<  1  ),  etykietowanie  (  Vars  ),  foreach  (  I  in  1.  .  N  ,[  Row  ],  (  Row  @=  [  Qs  [  I  ,  J  ]  :  J  in  1.  .  N  ],  writeln  (  wiersz  ))).

Obstawianie

Tworzenie tabel staje się coraz ważniejsze nie tylko dla początkujących w pisaniu praktycznych programów deklaratywnych, ale także dla tworzenia aplikacji w świecie rzeczywistym, takich jak przetwarzanie języka naturalnego, sprawdzanie modeli i aplikacje do uczenia maszynowego. B-Prolog implementuje mechanizm tworzenia tabel, zwany tabelowaniem liniowym, który opiera się na iteracyjnym obliczaniu zapętlonych celów podrzędnych, a nie zawieszaniu ich w celu obliczenia stałych punktów. System PRISM, który w dużym stopniu opiera się na tworzeniu tabel, był główną siłą napędową projektowania i wdrażania systemu tabelowania firmy B-Prolog.

Ideą tabingu jest zapamiętywanie odpowiedzi na ułożone w tabeli wezwania i wykorzystywanie odpowiedzi do rozwiązywania kolejnych wariantów wezwań. W B-Prologu, podobnie jak w XSB, tablicowe predykaty deklarowane są jawnie przez deklaracje w następującej postaci:

  :-  tabela  P1  /  N1  ,...,  Pk  /  Nk  .

Na przykład poniższy predykat w tabeli definiuje przechodnie zamknięcie relacji podane przez edge/2 .

 

 :-  ścieżka  tabeli  /  2.  ścieżka  (  X  ,  Y  ):-  krawędź  (  X  ,  Y  ).  ścieżka  (  X  ,  Y  ):-  ścieżka  (  X  ,  Z  ),  krawędź  (  Z  ,  Y  ).

Dzięki tworzeniu tabel każde zapytanie skierowane do programu ma gwarancję zakończenia, o ile rozmiary terminów są ograniczone.

Domyślnie wszystkie argumenty wywołania w tabeli są używane do sprawdzania wariantów, a wszystkie odpowiedzi są umieszczane w tabeli dla predykatu w tabeli. B-Prolog obsługuje tryby tabel, które pozwalają systemowi używać tylko argumentów wejściowych w sprawdzaniu wariantów i wybiórczo odpowiedzi w tabelach. Deklaracja trybu tabeli

  :-  tablica  p  (  M1  ,...,  Mn  )  :  C  .

instruuje system, jak wykonać tabelowanie na p/n , gdzie C , zwane granicą liczności , jest liczbą całkowitą, która ogranicza liczbę odpowiedzi do zestawienia, a każdy Mi jest trybem, który może być min , max , + (wejściowy) , lub - (wyjście). Zakłada się, że argument z trybem min lub max jest wyprowadzany. Jeśli granica liczności C wynosi 1 , można ją pominąć, poprzedzając ją znakiem „ : ”.

Tryby tablicowe są bardzo przydatne do deklaratywnego opisu problemów programowania dynamicznego. Na przykład poniższy program koduje algorytm Dijkstry do znajdowania ścieżki o minimalnej wadze między parą węzłów.

 
 
    
 
    
    
       :-  tabela  sp  (  +  ,  +  ,  -  ,  min  ).  sp  (  X  ,  Y  , [(  X  ,  Y  )],  W  )  :-  krawędź  (  X  ,  Y  ,  W  ).  sp  (  X  ,  Y  , [(  X  ,  Z  )|  Ścieżka  ],  W  )  :-  krawędź  (  X  ,  Z  ,  W1  ),  sp  (  Z  ,  Y  ,  Ścieżka  ,  W2  ),  W  to  W1  +  W2  .

W trybie tabelarycznym dla każdej pary węzłów umieszczana jest tylko jedna ścieżka o minimalnej wadze.

Linki zewnętrzne