Jakie są główne różnice techniczne między Prologiem i miniKanren w odniesieniu do programowania logicznego? [Zamknięte]

Kiedy chcę poczytać o programowaniu logicznym, zawsze napotykam dwa "główne" sposoby na zrobienie tego w dzisiejszych czasach:

• miniKanren , miniazyk wprowadzony w The Reasoned Schemer i obecnie popularny ze względu na core.logic .
• Prolog , pierwszy „duży” język programowania logiki.

Co mnie teraz interesuje: jakie są główne różnice techniczne między nimi? Czy są bardzo podobne w podejściu i implementacji, czy też przyjmują zupełnie inne podejście do programowania logicznego? Z jakich gałęzi matematyki się wywodzą i jakie są podstawy teoretyczne?

Po pierwsze, pozwól mi pochwalić twoją dobrą ikonę pw0n1e.

To trudne pytanie, głównie dlatego, że istnieje wiele wariantów zarówno miniKanren, jak i Prolog. miniKanren i Prolog to tak naprawdę rodziny języków, co utrudnia porównanie ich cech, a nawet tego, jak są one używane w praktyce. Z tego powodu, proszę, weź wszystko, co powiem, ostrożnie: jeśli powiem, że Prolog używa wyszukiwania najpierw w głąb, pamiętaj, że wiele implementacji Prologu obsługuje inne strategie wyszukiwania, a alternatywne strategie wyszukiwania mogą być również zakodowane w meta poziom tłumacza. Mimo to miniKanren i Prolog mają różne filozofie projektowania i dokonują różnych kompromisów.

Prolog jest jednym z dwóch klasycznych języków programowania symbolicznej sztucznej inteligencji (drugim klasycznym językiem jest Lisp). Prolog wyróżnia się we wdrażaniu systemów opartych na regułach symbolicznych, w których wiedza deklaratywna jest kodowana w logice pierwszego rzędu. Język jest zoptymalizowany pod kątem ekspresyjności i wydajności dla tego typu zastosowań, czasami kosztem logicznej czystości. Na przykład, domyślnie Prolog nie używa „sprawdzania występowania” w unifikacji. Z matematyczno-logicznego punktu widzenia ta wersja ujednolicenia jest niepoprawna. Jednak taka kontrola jest kosztowna, aw większości przypadków jej brak nie stanowi problemu. Jest to bardzo pragmatyczna decyzja projektowa, podobnie jak użycie w Prologu wyszukiwania w głąb i użycia cięcia (!), aby kontrolować cofanie. Jestem pewien, że te decyzje były absolutnie konieczne podczas pracy na sprzęcie z lat 70., a dziś są bardzo przydatne podczas pracy nad dużymi problemami i podczas zajmowania się ogromnymi (często nieskończonymi!) Przestrzeniami wyszukiwania.

Prolog obsługuje wiele „nielogicznych” lub „nielogicznych” funkcji, w tym wycinanie asserti retractrzutowanie zmiennych do arytmetyki przy użyciuis, i tak dalej. Wiele z tych funkcji ułatwia wyrażanie złożonego przepływu sterowania i manipulowanie globalną bazą danych Prologu. Jedną z bardzo interesujących cech Prologu jest to, że sam kod Prologu jest przechowywany w globalnej bazie danych faktów i może być sprawdzany w czasie wykonywania. To sprawia, że ​​pisanie meta-interpreterów, które modyfikują zachowanie interpretowanego kodu Prologu, jest trywialne. Na przykład możliwe jest zakodowanie wyszukiwania wszerz w Prologu przy użyciu meta-interpretera, który zmienia kolejność wyszukiwania. To niezwykle potężna technika, która nie jest dobrze znana poza światem Prologu. „The Art of Prolog” szczegółowo opisuje tę technikę.

Ogromny wysiłek włożono w ulepszenie implementacji Prologu, z których większość opiera się na maszynie abstrakcyjnej Warrena (WAM). WAM wykorzystuje model efektów ubocznych, w którym wartości są destrukcyjnie przypisywane zmiennym logicznym, przy czym te efekty uboczne są cofane po cofnięciu. Wiele funkcji można dodać do Prologu poprzez rozszerzenie instrukcji WAM. Wadą tego podejścia jest to, że dokumenty implementacyjne Prologu mogą być trudne do odczytania bez solidnego zrozumienia WAM. Z drugiej strony, realizatorzy Prologu mają wspólny model omawiania zagadnień związanych z implementacją. W równoległym Prologu przeprowadzono wiele badań, których kulminacją był Andorra Prolog w latach 90. Przynajmniej niektóre z tych pomysłów są obecne w Ciao Prolog. (Ciao Prolog jest pełen interesujących pomysłów, z których wiele wykracza daleko poza standard Prologu).

Prolog ma piękną, opartą na unifikacji składnię w stylu "dopasowywania wzorców", która daje w rezultacie bardzo zwięzłe programy. Prologowie uwielbiają swoją składnię, tak jak Lispers uwielbiają swoje wyrażenia s. Prolog posiada również dużą bibliotekę standardowych predykatów. Ze względu na całą inżynierię, która przyczyniła się do uczynienia WAM-a szybkim, istnieją bardzo wydajne i dojrzałe implementacje Prologu. W rezultacie wiele dużych systemów opartych na wiedzy zostało w całości napisanych w Prologu.

miniKanren został zaprojektowany jako minimalny język programowania logiki, z małą, łatwo zrozumiałą i łatwą do hakowania implementacją. miniKanren był pierwotnie osadzony w Scheme i został przeniesiony na dziesiątki innych języków hosta w ciągu ostatniej dekady. Najpopularniejszą implementacją miniKanren jest „core.logic” w Clojure, który ma teraz wiele rozszerzeń podobnych do Prologu i kilka optymalizacji. Niedawno rdzeń implementacji miniKanren został jeszcze bardziej uproszczony, w wyniku czego powstało małe „mikro jądro” o nazwie „microKanren”. MiniKanren można następnie zaimplementować na szczycie tego rdzenia microKanren. Przeniesienie microKanren lub miniKanren na nowy język hosta stało się standardowym ćwiczeniem dla programistów uczących się miniKanren. W rezultacie,

Standardowe implementacje miniKanren i microKanren nie zawierają mutacji ani innych skutków ubocznych, z jednym wyjątkiem: niektóre wersje miniKanren używają równości wskaźnika do porównywania zmiennych logicznych. Uważam to za „łagodny efekt”, chociaż wiele implementacji unika nawet tego efektu, przekazując licznik przez implementację. Nie ma również globalnej bazy danych faktów. Filozofia implementacji miniKanren jest inspirowana programowaniem funkcjonalnym: należy unikać mutacji i efektów, a wszystkie konstrukcje językowe powinny uwzględniać zakres leksykalny. Jeśli przyjrzysz się uważnie implementacji, możesz nawet zauważyć kilka monad. Implementacja wyszukiwania opiera się na łączeniu i manipulowaniu leniwymi strumieniami, po raz kolejny bez użycia mutacji. Te wybory implementacji prowadzą do bardzo różnych kompromisów niż w Prologu. W Prologu wyszukiwanie zmiennych jest stałe, ale cofanie wymaga cofnięcia efektów ubocznych. W miniKanren wyszukiwanie zmiennych jest droższe, ale cofanie jest „bezpłatne”. W rzeczywistości w miniKanren nie ma wycofywania się ze względu na sposób obsługi strumieni.

Interesującym aspektem implementacji miniKanren jest to, że kod jest z natury bezpieczny dla wątków i - przynajmniej w teorii - trywialnie równoległy. Oczywiście zrównoleglenie kodu bez spowalniania go nie jest trywialne, biorąc pod uwagę, że każdy wątek lub proces musi mieć wystarczająco dużo pracy, aby nadrobić narzut związany z równoległością. Mimo to jest to obszar implementacji miniKanren, który, mam nadzieję, zostanie poświęcony większej uwagi i eksperymentom.

miniKanren używa sprawdzania wystąpienia do ujednolicenia i używa pełnego wyszukiwania z przeplotem zamiast wyszukiwania w głąb. Wyszukiwanie z przeplotem zajmuje więcej pamięci niż wyszukiwanie w głąb, ale może znaleźć odpowiedzi w niektórych przypadkach, w których przeszukiwanie w głąb odejdzie / zapętli się na zawsze. miniKanren nie obsługuje kilku operatorów logicznych --- ekstra conda, condui project, na przykład. condai condumoże być używany do symulacji cięcia Prologu i projectmoże być używany do uzyskania wartości związanej ze zmienną logiczną.

Obecność conda,condu iproject--- i możliwość łatwego modyfikowania strategii wyszukiwania --- pozwala programistom używać miniKanren jako wbudowanego języka podobnego do Prologu. Jest to szczególnie prawdziwe w przypadku użytkowników „core.logic” Clojure, który zawiera wiele rozszerzeń podobnych do Prologu. Wydaje się, że to „pragmatyczne” wykorzystanie miniKanren odpowiada za większość zastosowań miniKanren w przemyśle. Programiści, którzy chcą dodać system wnioskowania oparty na wiedzy do istniejącej aplikacji napisanej w Clojure, Python lub JavaScript, generalnie nie są zainteresowani przepisywaniem całej swojej aplikacji w Prologu. Osadzanie małego języka programowania logiki w Clojure lub Pythonie jest znacznie bardziej atrakcyjne. Prawdopodobnie wbudowana implementacja Prologu działałaby równie dobrze w tym celu.

Oprócz wykorzystania miniKanren jako pragmatycznego wbudowanego języka programowania logicznego, podobnego w duchu do Prologu, miniKanren jest używany do badań nad programowaniem „relacyjnym”. To znaczy, pisząc programy, które zachowują się raczej jak relacje matematyczne niż funkcje matematyczne. Na przykład w Scheme appendfunkcja może dołączyć dwie listy, zwracając nową listę: wywołanie funkcji (append '(a b c) '(d e))zwraca listę (a b c d e). Możemy jednak również traktować appendjako relację trójmiejscową, a nie jako funkcję dwuargumentową. Wywołanie (appendo '(a b c) '(d e) Z)skojarzy wtedy zmienną logiczną Zz listą (a b c d e). Oczywiście sytuacja staje się bardziej interesująca, gdy umieścimy zmienne logiczne w innych pozycjach. Połączenie (appendo X '(d e) '(a b c d e))kojarzy się Xze współpracownikami(a b c) , podczas gdy połączenie(appendo X Y '(a b c d e))Xoraz Yz parami list, które po dołączeniu są równe (a b c d e). Na przykład X= (a b)i Y= (c d e)są jedną z takich par wartości. Możemy również napisać (appendo X Y Z), która będzie produkować nieskończenie wiele trójek list X, Yi Ztakie, że dołączenie Xdo Yprodukuje Z.

Tę relacyjną wersję appendmożna łatwo wyrazić w Prologu i rzeczywiście jest ona pokazana w wielu tutorialach Prologu. W praktyce bardziej złożone programy Prologu mają tendencję do używania co najmniej kilku funkcji pozalogicznych, takich jak cut, które uniemożliwiają traktowanie wynikowego programu jako relacji. W przeciwieństwie do tego miniKanren jest wyraźnie zaprojektowany do obsługi tego stylu programowania relacyjnego. Nowsze wersje miniKanren obsługują symboliczne rozwiązywanie więzów ( symbolo,numbero ,absento, ograniczenia nierówności, programowanie w logice nominalnej), aby ułatwić pisanie nietrywialnych programów jako relacji. W praktyce nigdy nie używam żadnych nielogicznych cech miniKanren, a wszystkie programy miniKanren piszę jako relacje. Najbardziej interesującymi programami relacyjnymi są relacyjni tłumacze dla podzbioru Schematu. Tłumacze ci mają wiele interesujących możliwości, takich jak generowanie miliona programów Scheme, które oceniają do listy (I love you)lub trywialne generowanie quinesów (programów, które oceniają się same).

miniKanren dokonuje wielu kompromisów, aby umożliwić ten relacyjny styl programowania, który jest bardzo różny od kompromisów oferowanych przez Prolog. Z biegiem czasu miniKanren dodał więcej symbolicznych ograniczeń, stając się naprawdę zorientowanym symbolicznie językiem programowania w logice ograniczeń. W wielu przypadkach te symboliczne ograniczenia sprawiają, że praktyczne jest unikanie stosowania operatorów pozalogicznych, takich jak condui project. W innych przypadkach te symboliczne ograniczenia nie są wystarczające. Lepsze wsparcie dla symbolicznych ograniczeń jest jednym z aktywnych obszarów badań miniKanren, wraz z szerszą kwestią, jak pisać większe i bardziej złożone programy jako relacje.

Krótko mówiąc, zarówno miniKanren, jak i Prolog mają ciekawe funkcje, implementacje i zastosowania i myślę, że warto uczyć się pomysłów z obu języków. Istnieją również inne bardzo interesujące języki programowania logiki, takie jak Mercury, Curry i Gödel, z których każdy ma własne podejście do programowania logicznego.

Zakończę kilkoma zasobami miniKanren:

Główna strona miniKanren: http://minikanren.org/

Wywiad, którego udzieliłem na temat programowania relacyjnego i miniKanren, w tym porównanie z Prologiem: http://www.infoq.com/interviews/byrd-relational-programming-minikanren

Twoje zdrowie,

--Będzie

Wstępna odpowiedź:

AFAIK, „The Reasoned Schemer” wprowadził podstawowe programowanie logiczne w składni Scheme-y i funkcjonalnym stylu programowania, dodając w szczególności stałe cele „#u” (niepowodzenie) i „#s” (suceeed) do wartości logicznych ”#t ”i„ #f ”. Używał tego samego podejścia do programowania logicznego co Prolog: Unification and backtracking search. Zobaczę, czy w weekend zdążę zabrać tę książkę z półki. Gałąź matematyki to logika pierwszego rzędu w formie zastrzeżonej, w tym przypadku klauzule Horn i Unfikacja Rezolucji. Zobacz: Logika obliczeniowa: wspomnienia z przeszłości i wyzwania dla przyszłości Johna Alana Robinsona i Wczesne lata programowania logicznego Roberta Kowalskiego na zimny start.