Comments 16
Получив на вход некоторое количество правил и утверждений, программа на прологе попытается удовлетворить их все, решив тем самым задачу (которую принято называть query) относительно определенных переменных.
Вот только вы забыли уточнить, что несмотря на то, что Пролог действительно "подарил миру вагон и маленькую тележку идей", в его основе лежит обычный цикл для перебора комбинаций.
Не очень понял, причем тут это. Кроме того, даже самая первая реализация Колмероэ была построена на дизъюнктах Хорна, насколько мне известно.
При том, что Пролог не "решает задачу", а перебирает варианты возможных комбинаций.
даже самая первая реализация Колмероэ была построена на дизъюнктах Хорна
Верну вопрос, причем тут это? Перебор вариантов, он и в Африке перебор вариантов и не важно, каким образом записаны его условия.
Пролог не «решает задачу», а перебирает варианты возможных комбинаций.
Это казуистика.
Если надо решить задачу «найти два различных натуральных числа, сумма которых равна четырем», перебор — самый лучший (понятный, быстрый, эффективный) способ её решения. Результатом решения является ответ. Если ответ правильный — задача считается решенной. Удивительно, что приходится это проговаривать.
Более того, когда я триста лет назад решал эту задачу сам в уме — вы не поверите, наверное, — я перебирал варианты, отметая заведомо ошибочные (это про дизъюнкты Хорна — перебор не полный, но оптимальный).
Решение на эликсире, которое я когда-то написал для демонстрации мощи акторной модели — было ровно таким же: я запускал процессы на каждое следующее правило и убивал те, которые упирались в противоречие (такой многоуровневый форк). Так вот, это тоже, по большому счету, перебор.
Аналитический способ решения этой задачи мне лично неизвестен, но даже если предположить, что он существует, — он хуже по всем параметрам. Поэтому я и не понимаю, зачем бы мне упоминать перебор per se в тексте заметки. Работает? — Да. Лучше, чем все вместе взятые LLM на сегодняшний день? — Да. Ну и славно.
Я не умоляю важности идей Пролога и необходимости его изучения (да и сам когда то был его приверженцем). Однако способ записи программы на Прологе в декларативном виде не оставляет возможности записывать алгоритмы в более привычном процедурном стиле.
Точнее, в Прологе вообще нет алгоритма решения, как такового. Есть только запись условий, а алгоритм решения только один - перебор.
В некоторых случаях этого действительно будет достаточно или даже более удобно, как в обозначенной вами выше задаче Энштейна. Однако полный перебор всех вариантов - это классика и для обычных алгоритмических языков и у Пролога тут нет никаких существенных преимуществ.
В третий раз повторяю: перебор не полный. Он отсекает ветки, нарушающие условия, сразу. В примере выше — благодаря вот этому факту
% 10. The Norwegian lives in the first house.
rule10([(norwegian,_,_,_,_)|_]).пролог не станет перебирать варианты с норвежцем в дальних домах. Вообще не станет.
способ записи программы на Прологе в декларативном виде не оставляет возможности записывать алгоритмы в более привычном процедурном стиле
Именно поэтому заметка про то, зачем и как я использую пролог внутри библиотечного кода на эликсире, а совсем не про то, как круто решать задачку Эйнштейна на прологе. На этапе компиляции я транслирую кусочек кода из AST эликсира в пролог, решаю проверяю валидность ввода по эмпирическим правилам (как общим, так и для данного проекта) — и либо пропускаю определение FSM дальше, либо заворачиваю.
Раньше я что-то подобное делал на идрисе, но при переносе кода из идриса в эликсир терялась доказательность (теоретически, практически я умею переводить код с языка на язык без ошибок). Теперь доказательность не теряется.
Он отсекает ветки, нарушающие условия, сразу.
Да, я помню про "зеленые" и "красные" отсечения в Прологе и они действительно очень сильно сокращают время по сравнению с полным переборов всех возможных вариантов. Но эти отсечения возможны только для формализуемых алгоритмов и должны задаваться программистом вручную.
Пролог по своему прекрасен, и очень жаль, что он не умеет по настоящему "решать" :-(
Есть только запись условий, а алгоритм решения только один - перебор.
Это не совсем так. Есть оптимизация, когда факты хешируются.
Однако полный перебор всех вариантов - это классика и для обычных алгоритмических языков и у Пролога тут нет никаких существенных преимуществ.
Ну достаточно очевидно, что вы на достаточно универсальном языке можете забабахать весьма эффективный алгоритм поиска. Поэтому, разумеется, на ассемблере, фортране, С, Хрусте и пр, вы можете сделать что-то более эффективное по производительности, чем на Прологе для конкретной задачи. Но производительность - это же только она сторона медали. Есть ещё ремонтопригодность (цена в человеко-часах изменений программы) и скорость написания.
А вы возились с Иерархическими конечными автоматами Харела?
Harel, David. "Statecharts: A Visual Formalism for Complex Systems." Science of Computer Programming 8, North-Holland, 1987.
Нет. Огроменное спасибище за ссылку: уже вожусь (правильная ссылка, на всякий случай: https://www.weizmann.ac.il/math/harel/sites/math.harel/files/users/user56/Statecharts.pdf).
Что касается Datalog из комментария выше — у меня довольно тривиальные факты и мне нужен интерпретатор на эрланге (шеллить компиляцию и выполнение — повышает мою эстетическую энтропию).
я решил освежить в памяти пролог.
1) Начнём с того, что семейство языков называется Prolog.
2) О какой из конкретных реализаций Prolog идёт речь в статье? Например, Wikipedia приводит сравнение двадцати актуальных реализаций. У меня есть обзор на (примерно) сотню реализаций Prolog. И все они очень разные!
Users = [user(1, Name1, male), user(2, Name2, female)],
member(user(_,ivan,male), Users),
member(user(_,maria,_), Users).swish выдаёт
Singleton variables: [Name1,Name2]
Full stop in clause-body? Cannot redefine ,/2
Области видимости в swish очень контринтуитивны. Нужно либо ввести весь код в правое нижнее окно, либо определить функцию: https://swish.swi-prolog.org/p/users-simple-habr.swinb
И теперь в правом нижнем окне ввести
solution(Users,Name1,Name2).
Задача Эйнштейна. Пролог к валидации конечных автоматов