Как реализовать интерпретатор пролога на чисто функциональном языке?

25

Есть ли ясная ссылка с псевдокодом о том, как реализовать интерпретатор Пролога на чисто функциональном языке? То, что я обнаружил до сих пор, похоже, имеет дело только с императивными языками, является просто демонстрацией реализованного самого Пролога или не предлагает никакого конкретного алгоритма, который можно использовать для интерпретации. Я был бы очень благодарен за ответ.

Jimster
источник
4
Реализация Пролога (Серия Принстона в области компьютерных наук) Патриса Буизмо имеет реализацию на Лиспе.
Уилл Несс
Смотрите этот ответ для относительно нового подхода.
ложь

Ответы:

24

Так как Пролог = Синтаксическое Объединение + Обратная Цепочка + REPL

Все три части можно найти в Искусственном интеллекте: структуры и стратегии для решения сложных задач Джорджа Ф. Люгера. В четвертом издании книги все три части реализованы в LISP в разделе 15.8 «Программирование логики в LISP». Он также помещает тот же самый код в свои другие книги, но у меня нет всех их, чтобы отметить здесь. Код для его книг можно найти здесь .

Еще один источник со всеми тремя частями можно найти в « Парадигмах программирования искусственного интеллекта»: тематические исследования в Common Lisp Питера Норвига. См. Главы 11, Программирование логики и 12, Компиляция программ логики. Код для его книги можно найти здесь .

Другой источник - структура и интерпретация компьютерных программ Хэла Абельсона, Джерри Суссмана и Джули Суссман. См. Раздел 4.4 «Логическое программирование». Сайт для книги здесь, а код для книги здесь .

Весьма часто можно найти алгоритм объединения с обратной цепочкой, реализованный во многих приложениях, если вы знаете, где искать; это особенно распространено при выводе типа в функциональных компиляторах. Использование унификации ключевых слов или происходит помогает определить функции. Также большинство реализаций используют unif для имени функции объединения.

Для версии Prolog, за исключением REPL, выполненной в OCaml, см. Код и ресурсы для «Руководства по практической логике и автоматическому рассуждению» - prolog.ml

Перевод кода книги на F # можно найти здесь . Перевод кода книги на Haskell можно найти здесь .

С точки зрения поиска кода, алгоритм объединения проще всего найти, чем реализации, в которые встроены обратные цепочки в приложения. Найти полностью функциональную реализацию Пролога на функциональном языке с REPL - самое сложное. Большую часть времени код не в формате для прямого использования в PROLOG; он сильно настроен для повышения производительности, поэтому вы можете найти код, но он не будет стоить цену, чтобы выявить нужные вам части. Я бы посоветовал прочитать книгу Люгера и создать ее с нуля на выбранном вами языке, даже если это означает установку и изучение LISP и перевод для этого.

РЕДАКТИРОВАТЬ

Так как это дублирующий вопрос от StackOverflow и ОП является новым и в комментариях говорится:

Чтобы дать больше контекста, я пытаюсь реализовать вывод типов, однако сложные функции в системе типов моего языка (зависимые типы, типы уточнения, линейная типизация, чтобы назвать некоторые из менее распространенных) заставляют меня чувствовать, что это было бы полезно основать мой вывод типа на алгоритмах, управляющих Прологом, чтобы получить очень общий алгоритм. Отмечу, что я полностью самоучка, поэтому мне не хватает моих знаний на больших площадях.

Я подробно остановлюсь на этом здесь, но понимаю, что ОП должен задать новый вопрос.

Для некоторых вводных вещей смотрите вывод типа реализации .

Лучшая книга на эту тему, которую я знаю, это « Типы и языки программирования » Бенджамина С. Пирса. Сайт книги здесь . Ресурсы со ссылками на код OCaml находятся здесь . И недавно начался, но в основном полный перевод этого на F # здесь .

Зависимые типы: стр. 462 Типы уточнений: стр. 207 Линейная логика и системы типов: стр. 109

Гай Кодер
источник
1
Парень Кодер, вы, сэр, джентльмен и ученый! Ваша помощь очень полезна, и я не могу отблагодарить вас за то, что вы нашли время ответить на этот вопрос. = D - Сотрудник Джимстера и исследователь, уставший от исследований
Шензао
Я еще раз благодарю вас, я уже получил эти книги (то есть раньше, а не как в быстрой поездке в книжный магазин).
Джимстер
Код @Jimster Norvig хорош и понятен, помещается на странице IIRC. Не помню, если это чисто .
Уилл Несс
Нашел еще одну: лекция 26: Вывод типа и унификация
Guy Coder
Из интереса: unify_P3.py, который является частью Задания 2
Гай Кодер