Jak wdrożyć tłumacza prologu w czysto funkcjonalnym języku?

25

Czy istnieje wyraźne odniesienie, z pseudo-kodem, dotyczące sposobu wdrażania interpretera Prolog w czysto funkcjonalnym języku? To, co do tej pory znalazłem, wydaje się dotyczyć wyłącznie języków imperatywnych, jest jedynie demonstracją samego Prologu zaimplementowanego lub nie oferuje żadnego konkretnego algorytmu do zastosowania w interpretacji. Byłbym bardzo wdzięczny za odpowiedź.

Jimster
źródło
4
Implementacja Prolog (Princeton Series in Computer Science) przez Patrice Boizumault ma implementację Lisp.
Czy Ness
Zobacz tę odpowiedź na stosunkowo nowe podejście.
fałsz

Odpowiedzi:

24

Ponieważ Prolog = ujednolicenie składniowe + tworzenie łańcuchów wstecznych + REPL

Wszystkie trzy części można znaleźć w Sztucznej inteligencji: struktury i strategie kompleksowego rozwiązywania problemów autorstwa George'a F. Lugera. W czwartym wydaniu książki wszystkie trzy części zostały zaimplementowane w LISP w rozdziale 15.8, Programowanie logiki w LISP. On również umieszcza ten sam kod w swoich innych książkach, ale nie mam ich wszystkich do odnotowania tutaj. Kod jego książek można znaleźć tutaj .

Kolejne źródło ze wszystkimi trzema częściami można znaleźć w Paradygmatach programowania sztucznej inteligencji: studia przypadków w Common Lisp autorstwa Petera Norviga. Patrz rozdziały 11, Programowanie logiki i 12, Kompilowanie programów logicznych. Kod jego książki można znaleźć tutaj .

Innym źródłem jest struktura i interpretacja programów komputerowych Hal Abelson, Jerry Sussman i Julie Sussman. Patrz rozdział 4.4 Programowanie logiki. Strona książki jest tutaj, a kod książki jest tutaj .

Nierzadko zdarza się znaleźć algorytm unifikacji z łańcuchem wstecznym zaimplementowanym w wielu aplikacjach, jeśli wiesz, gdzie szukać; jest to szczególnie rozpowszechnione w wnioskach typu w kompilatorach funkcjonalnych. Użycie słowa kluczowego ujednolicenie lub występuje pomaga dostrzec funkcje. Również większość implementacji używa unif jako nazwy funkcji unifikacyjnej.

Wersja Prologu, pomniejszona o REPL, wykonana w OCaml, patrz Kod i zasoby dla „Podręcznika praktycznej logiki i automatycznego wnioskowania” - prolog.ml

Tłumaczenie kodu książki na F # można znaleźć tutaj . Tłumaczenie kodu książki na Haskell można znaleźć tutaj .

Jeśli chodzi o znalezienie kodu, najłatwiej jest znaleźć algorytm unifikacji, a następnie implementacje z łańcuchem wstecznym wbudowanym w aplikacje. Najtrudniej jest znaleźć w pełni funkcjonalną implementację Prologa w funkcjonalnym języku z REPL. Przez większość czasu kod nie ma formatu do bezpośredniego użycia w PROLOGU; jest mocno dostosowany, aby zwiększyć wydajność, więc możesz znaleźć kod, ale nie będzie warto kosztować wypróbowania pożądanych części. Radzę przeczytać książkę Lugera i zbudować ją od podstaw w wybranym języku, nawet jeśli oznacza to instalację i naukę LISP oraz tłumaczenie.

EDYTOWAĆ

Ponieważ jest to zduplikowane pytanie StackOverflow, a OP jest nowy, a w komentarzach mówi:

Aby dać więcej kontekstu, próbuję wdrożyć wnioskowanie o typie, jednak zawiłe funkcje w systemie typów mojego języka (typy zależne, typy wyrafinowania, liniowe pisanie, aby wymienić niektóre z mniej popularnych) sprawiają, że czuję, że przydaj się wnioskować o moim typie na podstawie algorytmów napędzających Prolog, aby uzyskać bardzo ogólny algorytm. Zauważę, że jestem całkowicie samoukiem, więc mojej wiedzy brakuje na dużych obszarach.

Omówię to tutaj, ale zdaję sobie sprawę, że OP powinien zadać nowe pytanie.

Aby zapoznać się z niektórymi informacjami wprowadzającymi, zobacz wnioskowanie o typach .

Najlepsza książka, jaką znam na ten temat, to Typy i języki programowania autorstwa Benjamina C. Pierce'a. Strona książki jest tutaj . Zasoby z linkami do kodu OCaml są tutaj . Niedawno rozpoczęto, ale przeważnie pełne tłumaczenie tego na F # jest tutaj .

Zależne typy: str. 462 Typy zawężeń: str. 207 Układy logiczne i typy: str. 109

Guy Coder
źródło
1
Guy Coder, pan jest dżentelmenem i uczonym! Twoja pomoc jest najbardziej przydatna i nie mogę ci podziękować za poświęcenie czasu na odpowiedź na to pytanie. = D - współpracownik Jimstera i
zmęczony badaczem
Jeszcze raz dziękuję, już otrzymałem te książki (to znaczy wcześniej niż nie w szybkiej podróży do księgarni).
Jimster,
@Jimster Norvig kod jest ładny i przejrzysty, mieści się na stronie IIRC. Nie pamiętam jednak, czy jest czysty .
Czy Ness
Znalazłem inny: Wykład 26: Wnioskowanie typu i unifikacja
Guy Coder
Interesujące: unify_P3.py, które jest częścią Zadania 2
Guy Coder,