Comments 123
Можно ли на прологе реализовать четырёхзначную логику?
Можно, только надо объявить все 4 состояния и логические отношения для них.
Имеется ввиду таблицы истинности описать? А как описать выражения типа "если из А следует Б, то из В следует Г"?
А зачем 4 состояния для этого?
(А->Б)->(В->Г), где "->" — это импликация. "А->Б" — это "(не А) или Б".
Разворачиваем:
(А->Б)->(В->Г) =
(не ((не А) или Б)) или ((не В) или Г) =
A и не Б или не В или Г
>_<
4 состояния не для этого.
Вы говорите про материальную импликацию, которая по сути и не импликация вовсе.
Но вопрос был в том, как импликация описывается на прогологе. Про десять типов стрелок в математикие и так всё ясно.
Правильно ли я понял, что импликация на прологе не представима?
implication(X) :-
(X = a ->
write('Argument a received.'), nl
; X = b ->
write('Argument b received.'), nl
;
write('Received unknown argument.'), nl
).
В документации есть ещё такое.
Что-то я не понял этот код. Как спросить пролог "следует ли Б из А"?
Неужели это такой сложный вопрос, что на него нельзя просто ответить, не посылая в маны? Там нет ничего про стрелки.
Плюс ещё есть отдельный оператор для импликации #==>
Вот серьёзно, всё это элементарно и есть в доках, кмк если бы вам и вправду было бы интересно, вы бы уже и сами загуглили и прочитали по ссылкам выше.
Вот, смотрите, я пишу:
is_my( Part ) :- part_of( Part, Whole ), is_my( Whole ).
part_of( window, house ).Такой вопрос выдаёт синтаксическую ошибку:
?- is_my( house ) #==> is_my( window ).Такой выдаёт false:
?- is_my( house ) -> is_my( window ).Как мне получить true?
И тогда получите:
?- 0 #==> 1.
true.
?- 1 #==> 0.
false.
Ну а is_my( house ) #==> is_my( window ) в принципе не сработает в том виде, как в описали предикаты выше.
Что-то я не улавливаю смысл такой стрелки работающей лишь с константами.
Что не так с моими предикатами?
Смотрите:
is_my( Part ) :- part_of( Part, Whole ), is_my( Whole ).
part_of( window, house ).
Вызываете первый раз is_my (house).
Пролог передаёт значение hause переменной Part, после чего переходит в предикат part_off, видит, что на первом месте для true должно быть Window и возвращает false.
Просто повызывайте свои предикаты с дебагом и сразу увидите все подобные места
К слову, вот такое вот поведение я считаю большим минусом пролога, т.к. подобные ошибки зачастую неочевидны (у вас ещё простой пример, но я видел достаточно большие проекты, где из-за одного пропущенного предиката всегда был непраивльный результат).
Хотя с другой стороны, может на квантовых компах он и взлетит…
Проблема пролога фундаментальна. NP != P.Чем докажете?
Квантовые компьютеры не решают NP задачи за полиномиальное время.
Вы ходите по очень горячим углям! Проблема перебора до сих пор не решена.
Тем более заявление:
Квантовые компьютеры не решают NP задачи за полиномиальное время.
Не является прямым доказательством неравенства этих классов, так как высказанное может вызвано ограниченностью современных технологий и алгоритмов.
Квантовые компьютеры могут ускорять задачи, которые можно представить так, чтобы сумма амплитуд по всем "путям вычисления" давала конструктивную интерференцию для правильного ответа. Да, не доказано, что такой класс задач не включает NP. Но специалисты практически не рассчитывают на то, что NP=BQP (Bounded error Quantum Polynomial time). У Скотта Ааронсона есть более-менее популярные статьи на эту тему.
www.swi-prolog.org/pack/file_details/turing/prolog/turing.pl?show=src
Стоит отменить, факт настолько известен, что он даже в Википедии идет в графе Тьюринг полнота пролога:
en.wikipedia.org/wiki/Prolog#Turing_completeness
Это сразу отвечает людям, которые несут чушь про NP-полноту.
> Для Пролога совершенно точно существуют задачи, которые он не может в отличии от машины тьюринга решить за конечно время.
Да, это вообще не оттуда — Тьюринг полна говорит о том, может ли язык программирования симулировать универсальную машину Тьюрига — причем тут вообще конечное время и «решить»?
Я уже не говорю, что пролог напрямую прямо синтаксиса оперирует логикой первого порядка, для выводимости из которой справедлива теорема о Геделя о неполноте => откуда следует проблема останова и здесь никаких NP и конечного времени
www.quora.com/Is-there-any-relation-between-halting-problem-and-Godels-incompleteness-theorems
Так что с удовольствием посмотрю на эти «совершенно точно существующие задачи, которые пролог не может в отличии от машины тьюринга решить за конечно время.»
Так что с удовольствием посмотрю на эти «совершенно точно существующие задачи, которые пролог не может в отличии от машины тьюринга решить за конечно время.»
Вы кажется ничего не поняли. Вернее я неудачно сформулировал. Конечно на прологе можно написать интерпритатор машины тьюринга, на которой уже в свою очередь написать что угодно. Но при этом за выполнимостью того что вы напишите на машине тьюринга вы будете следить сами по правилам машины тьюринга. Если же вы ту же самую задачу успешно решённую вами на Тьюринг машине сформулируете как набор правил для Пролога, то запросто можете улететь в бесконечную рекурсию из-за неправильного порядка строк, и в прологе, особенно в не совсем уж тривиальных случаях, правильный порядок или не очевиден, или может вообще не существовать. Например если для того чтобы найти ответ нужно применить сначала правило A, потом Б и потом снова А, и применение не того правила посылает вас в рекурсию, то правильного порядка вообще не существует. Пролог не сможет решить задачу без переформулирования одного из правил.
Таких примеров тьма, если погуглить «Пролог рекурсия».
Еще раз: вы описали правилами пролога описание машины Тьюринга. Всё. Ни за чем не нужно больше следить.
Дали описание новой задачи для машины тьюринга, пролог ее выполнит **в точности** как это сделает машина тьюринга. Если машина улетает в рекурсию, то и пролог улетает. Если машине не улета, то пролог не улетает.
Да уж. Явно проблема не в том, что вы не поняли а в том, что вы не хотите понимать. Вы правы, если программировать тьюринг-машину, можно на ней запрограммировать что угодно.
Но очевидно Вы не понимаете в чём разница между тем, что тьюринг-машину программируете вы, и Прорлог программирует за вас, но со всеми задачами программирования справляется.
Поздравляю вас с победой в споре.
https://ru.wikipedia.org/wiki/Декларативное_программирование ->> «Чисто декларативные» компьютерные языки зачастую неполны по Тьюрингу — так как теоретически не всегда возможно порождение исполняемого кода по декларативному описанию. Это иногда приводит к спорам о корректности термина «декларативное программирование» (менее спорным является «декларативное описание решения» или, что то же самое, «декларативное описание задачи»).
Вы же конечно сами понимаете понимаете в чём таком важном, Prolog не является декларативным, раз так блистательно передискутировали меня. Такому умному и несомненно во всём абсолютно правому человеку мне нечего сказать. Наверное и эту статью в Википедии тоже вы писали. :)))
"такому уровню дискуссии" – это какому?
Здесь нет никаких противоречий, это ссылка на обсуждение термина "декларативное программирование".
Пролог не является декларативным языком по целому ряду причин: это определения через операционную семантику – как например фиксированный порядок выполнения правил сверху вниз, и оператор "cut". Вы меняете порядок правил и меняется результат работы.
Такого не происходит в декларативных таких как Datalog, Answer Set Programming, Minizinc или классический SQL.
Но опять же это вопрос в целом ортогональный обсуждению выразимости языков.
И я не вижу каким образом авторство статьи на Википедии является критерием истинности.
«такому уровню дискуссии» – это какому?
Это к такому, когда человек знает что такое проблема останова, но при этом делает вид, что не понимает взаимосвязи между словами «решить» и «за конечное время».
Давайте я в последний раз попытаюсь пробудить в вас мысль вместо цитирования:
«Существуют такие декларации задач средствами пролога, которые имеют решение, но пролог не может этого решения найти в силу свойственных ему ограничений, которые вы нагуглили для прошлого коммента. И программист используя имеющиеся у него математические знания, в отличии от Пролога, может преобразовать эти задачи в другую форму, которую можно запустить на симулируемой Прологом тьюринг-машине и таки успешно решить. Или даже просто преобразовать в другую форму, в которой пролог её решить сможет».
Вы вроде как делаете вид, что умны. Если и сейчас до вас не допёрло о чём я, см.мой предпоследний коммент. Надеюсь когда-нибудь вы сумеете выйти из этого цикла.
ints(0).
ints(A) :- ints(B), A is B - 1.
ints(A) :- ints(B), A is B + 2.
?- ints(1).Ответ очевиден — true. Любой программист может его получить преобразовав формулировки задачи в другие тождественные, но ни при каком порядке строк сам Prolog ответ найти не сможет, потому что чтобы ответ найти нужно проверять условия в меняющемся порядке.
Я даже как-то в растерянности, куда уж проще то? Я же четыремя комментами выше это описал.
Если они тождественные, то ответ не может меняться — иначе они не тождественные.
Вы привели пример программы, которая зацикливается и она не эквивалента другой программе, которая не зацикливается. Это две разные программы, которые решают две разные задачи. Этим двум программам на прологе будут соответствовать две другие машины Тьюринга.
> Ответ очевиден — true.
«очевидно» — это не формальное утверждение. Очевидно, что гипотеза Римана верна — норм доказательство?
Фактически, вы сделали следующее:
написали некорректную программу, а потом сказали, что ее можно исправить — вопрос какое это отношение имеет к дискуссии в выразимости языка Пролог и его Тьюринг полноте?
Я:
Существуют такие декларации задач
Вы:
Вы привели пример программы, которая зацикливается
Если вы не пытаетесть схранить лицо вопреки очевидному, а всерьёз не понимаете разницы, то это плохо.
Цикл замкнулся.
Хотя конечно вы прикидываетесь, судя по тому, что вы делаете вид, что не способны резвернуть "очевидно" в применение двух последовательно записанных перед вами высказываний. Но тогда опускаться на ваш уровень дискуссии нет смысла и подавно.
Но ясный и понятный запросто:
ints(0).
ints(A) :- ints(B), A is B — 1.
ints(A) :- ints(B), A is B + 2.
?- ints(1).
Ответ очевиден — true.
Вы интерпретируете эти выражения иначе, чем пролог-система. Для вас ответ очевиден, потому что вы думаете не на прологе, но компилятор руководствуется правилами пролога, и у него в полном соответствии с этими правилами получается бесконечная рекурсия. Для интерпретатора какого-нибудь JS тоже можно программу с багами написать и думать, что она должна работать.
Для интерпретатора какого-нибудь JS тоже можно программу с багами написать
Проблема в том, что написать на prolog-е программу которая НЕ попадет в рекурсию и будет выполняться за приемлемое время — гораздо более нетривиальная задача, чем написать программу на JS в которой не будет критичных багов.
И связано это в первую очередь именно с «недодекларативностью» prolog-а. Т.к. во времена его создания не смогли избавиться от вот этого-вот
фиксированный порядок выполнения правил сверху вниз, и оператор «cut»
и чтобы оно при этом все-же работало.
Проблема в том, что написать на prolog-е программу которая НЕ попадет в рекурсию и будет выполняться за приемлемое время — гораздо более нетривиальная задача, чем написать программу на JS в которой не будет критичных багов.
Быть может, если знать пролог лучше, задача становится менее нетривиальной? (я не могу ответить на этот вопрос, т.к. очень плохо понимаю пролог).
Смысл в разнице между декларацией задачи и программой.
А можете расшифровать что этот код описывает?
А является целым, если существует предыдущее целое или существует целое на 2 большее? Почему именно на 2?
А целое если следующее целое.
A целое если число на 2 меньше целое.
Такое определение покрывает все целые числа. На 2, потому что в такой формулировке Prolog не справляется с рекурсией при любом порядке строк.
Чтобы ответить на вопрос про число 1 утвердительно нужно сначала применить первое правило, и выяснить, что 1 целое если и 2 тоже целое. А потом применить второе правило и понять, что 1 целое если целое — 0. Ну или в обратном порядке. Но пролог всегда умеет применять правила только в одном порядке. Если всегда начинать с первого, то начинать с первого и здравствуй бесконечная рекурсия. Если поменять правила местами он перепрыгнет число ноль, и ускачет в другую сторону применяя только правило 2.
То есть он использует поиск в глубину, тогда как тут уместней использовать поиск в ширину.
Человек справляется с этим двумя способами:
1) Наличие понятий, имеющих априорную оценку, в которые может упереться рекурсия. Понятно, что из-за неполноты и неточности таких оценок могут возникать противоречия. И тогда случается «когнитивный диссонанс», разрешающийся через отдельные механизмы.
2) Наличие эвристик.
Вполне возможно, что будущее логического ИИ как раз и лежит в области прололг-подобных систем, снабжённых нейросетевыми эвристиками. Потому что на нейросети строгую логику организовать можно, но очень сложно, и прямое программирование справляется с этой задачей на много лучше, а сложные эвристики уровня АльфаГо наоборот на много лучше удаются нейросетям.
Отличная статья. Пролог действительно интересен. Как кто то уже выше писал — проблема в том что не все типы запросов можно выполнить за разумное время. Вероятно с ростом мощности желена и новыми алгоритмами мы получим большие возможности для декларативных языков в том числе и Prolog — ведь один уже смог взойти на пьедестал, это SQL.)
p.s.
Сам буквально недавно думал над возможностью применить систему работающую с Datalog, искал решения.
Вполне применим, просто вопрос в задачах которые перед ним ставите.
Это ведь не совсем Prolog, просто подход похожий (логическое программирование):
After lowering to logical predicates, Chalk then deploys a logical solver to find the answer to the original query; this solver is similar to a Prolog engine, though different in its particular
(отсюда)
Так можно и python фортраном назвать.
Собственно это скорее 70-х готов всплеск интереса к ИИ и породил пролог (он не много не мало мой ровесник :)
Но там же был и Lisp. Кстати простейший интерпритатор пролога на Lisp пишется в десяток строк.
Prolog — язык "искусственного интеллекта" 1980х. Как и лисп — немногим ранее. Но тогда точно не взлетело. А надежды были.
А нейросети, — наверно, — "искусственный интеллект" 2010х. И, насколько я могу судить, этот подход (на данный момент) более успешен, чем пролог.
интеллектуального поведения на основе биологических элементов. Пролог — нисходящая парадигма — символьные вычисления имитирующие высокоуровневые психические процессы: мышление, рассуждение, речь, эмоции, творчество и т. д.
Подходы к пониманию проблемы
Согласен — не взаимоисключющие. Мне кажется сильный ИИ как раз и будет строится на умелом сочетании символьного вычисления и нейронных сетей.
Мне кажется сильный ИИ как раз и будет строится на умелом сочетании символьного вычисления и нейронных сетей.
Может, но не факт. Пролог сейчас где-то на свалке истории. Скорее всплывёт что-то третье, чем старый никому сейчас не нужный пролог.
Но опять же, использование нейронных сетей сейчас — всегда соединение обучаемых частей (нейронок) и рукотворных алгоритмов.
Он как раз на роли ваших «рукотворных алгоритмов» и используется.
ПС
По вашему вопросу: я вполне понимаю почему я не хочу пролог — они зафиксировали порядок перебора (ну типа чтобы сделать ЯП „взрослым“ — детерминированно работающим в разных реализациях).
Только в этом и проблема — в случае NP задач надо настолько глубоко вдаваться во внутренние детали работы пролога, что проще то же самое на условном С \ Java написать чем „оптимизировать“ пролог.
www.cs.uni-potsdam.de/~torsten/Potassco/Tutorials/fmcad12.pdf
Почти любой программист использует одну специфическую версию Пролога с изменённым синтаксисом: она называется make. Похоже, это единственный случай, когда Пролог пошёл в массы.
Prolog применён в Gerrit для управления требованиями по заданию оценок и выставлению требований к допуску ревью. Я его там настраивал и, по-моему, лучше бы они взяли что угодно другое: хоть Фокал или Javascript, хоть Scheme или Haskell… Дело даже не в том, что 99% админов не знают язык — я вроде знаю, но я чуть не поседел, пытаясь понять, по какому принципу он на каком этапе останавливает преобразование выражения, и от какой фазы какого небесного тела зависит, где остановится свёртка.
сейчас вспоминаю со смехом конечно, но когда я начал свой самостоятельный путь изучения программирования, то купил книгу по prolog и попытался понять для чего это надо )) сейчас понимаю как я мог бы это использовать на одном из текущих проектов (автоматическое составление юридических документов), но сразу подумал о производительности и поддержке… и понял что со временем стал думать в сторону "кто будет работать с этим проектом после меня" в большей степени чем "как мне удобнее это написать"… вот тут наверное причина того что на некоторых языках мало пишут, хоть у них и хорошие казалось бы перспективы
Книжку толстую крутую давали по нюансам реализаций пролога, название не вспомню.
Тема неплохо зашла, ханойские башни и прочие примерчики решались, компилировалось в «шитый» x86-код, вот только реализацию GC не осилил (курсач и так приняли), прога работала до переполнения кучи.
Мечталось ещё реализовать кроме бинарной логики предикатов {0, 1} ещё и «вероятностную» (0..1) и соответствующе допилить механизм логического вывода, было бы что-то вроде Fuzzy Logic Prolog :-)
Однако я слышал, что вроде бы в EPAM-е есть какие-то проекты, где используется какая-то технология, похожая на пролог. Возможно, он немного эволюционировал и занял очень маленькую нишу. Для некоторых задач он действительно хорош.
Да и сам оператор yield показывают всю суть lazy вычислений, так сказать наследие Пролога.
<:o)
Успеваемость студентов по Prolog в том семестре была рекордной :)
Пролог используется в банковских системах некоторых для оценки рисков. У нас даже менеджеры для него правила писали. Но конечно мозг ломает.
Большие данные храним и обрабатываем. С нейронками разобрались. Но! Символьные вычисления осваивают единицы. Реализация нисходящей парадигмы реализации ИИ под угрозой.
Подходы к пониманию проблемы
Пролог помог?
Либретто статьи:
бубубу пролог незаслуженно забыт
бубубу
"hello world"
бубубу
примеры продакшена — ссылка раз, ссылка два, ссылка три — "как видите, он много где используется"
бубубу
ИТОГИ: пролог — мощная вещь, а вы пользуетесь прологом?
Имхо, это вода и студенческий реферат по философии.
— DSL (domain specific languages) — очень удобно создавать свои операторы и вкладывать смысл.
— Парсеры (причем не только КС-грамматик, но и контекстно зависимые)
— Универсальный Решатель задачи и доказательство теорем. [Правда теоремы должны выражаться в предикатах-Хорна, иначе задача не-разрешима за P — Проблема P != NP].
— Описывать функторы и операторы: достаточно просто и изящно можно описывать все функции сортировок,
— Автоматическое доказательство и проверка истинности кода (Используется математический аппарат доказательства теорем).
Prolog не императивный язык! Он требует от каждой операции «возвратности»:
— Нельзя сказать прочитай из памяти и запиши в файл (безвозвратно)
— Проитерируйся по списку и на каждой итерации запиши в базу данных рандомное число
— Вызови REST-API 50 раз и замеряй время выполнения
Конечно, условно можно, но выглядит ужасно (с отсечениями) и ломает всю декларативность. Большинство прикладных задач на практике оказываются императивными, остальное все загоняется в конфиги и sql (декларативная часть) и сшивается снова императивными языками. Поэтому императивный язык — универсален и он побеждает, но наследие идей и красота кода несомненно будут еще долго вдохновлять на различные Domain Specific Languages.
Что значит "условно можно", если предикаты редактирования базы фактов — прямо в стандартной библиотеке на видном месте?
Да, это ломает декларативность и чистоту. (Ну так и на сях, напротив, можно чистые функции писать).
Пролог — довольно тупенький в плане интерпретации предикатов.
Предикат записывается в виде дизъюнкции конъюнкций, которая в общем случае должна одинаково работать для любого исходного состояния — какие аргументы свободные, какие связанные (что нам дано и что надо найти). Мы просто бежим вглубь и откатываемся, бежим и откатываемся.
Проблема в том, что для разных "дано/найти" стратегии забега могут и зачастую должны отличаться.
Тут-то вся декларативность и полетит к чертям.
Единственное отличие от си, в таком случае, — что в си бывают goto-макароны, а в основном код выполняется последовательно; а в прологе код выполняется челночно.
Если хочется декларативности — это надо сформулировать задачу для солвера, а дальше пусть у него голова болит, как строить план вычислений.
Но это уже мета-язык, DSL над прологом.
Понятно, что языки принципиально разные. Но не вызывает ли (какого-нибудь… эээ… как бы это назвать…) удивления (может быть?), что такие разные языки, как весь такой декларативный и логический Prolog и совсем такой недекларативный, недофункциональный, а с акторами еще объектный Erlang внезапно имеют между собой нечто общее? Да синтаксис — и не так уж мало для такой огромной и принципиальной разницы. Не ломает шаблон? Не ставит, например, под сомнение «общепринятое» понятие «декларативности»?
Во-первых, я намекал что далеко не все согласны с тем, что «Erlang совсем не декларативный». Например, в русской Wikipedia про Erlang почему-то прямо так русским по белому и пишут: «декларативный язык программирования». Впрочем, английская тоже поместила его в категорию декларативных.
Тем не менее, я как раз соглашусь — вопрос о декларативности Erlang-а очень спорный. Но просто потому, что трактовка термина «декларативный» довольно смутная.
И родство синтаксиса (практически бесспорно) «декларативного» Prolog и (якобы) «недекларативного» Erlang здесь только подливает масла в огонь. Просто потому, что синтаксис языка с потолка не берется — он, как ни крути, должен соответствовать тому, какие идеи в этот язык заложены. …В общем, удалил я дальнейшее развитие мысли о странностях противопоставления декларативности и императивности и соответствующего деления языков — не место тут разворачивать дискуссию по данной теме.
…Тем более, что я изначально всего-то лишь хотел обратить внимание, что Prolog в свое время стал источником идей и вдохновения не только в области «чистого» логического программирования. И это можно (а, возможно, и нужно) было отразить в статье. Вдруг кто-нибудь нашел бы это достаточным поводом, чтобы задуматься.
Тем более, что связь между Prolog и Erlang гораздо глубже, чем «просто взяли синтаксис». Не интересно разве, почему это для языка, который был предназначен для создания распределенных систем реального времени вдруг взяли синтаксис медленного и узкоспециализированного логического языка? и почему вдруг erlang-исты заявляют, что «Erlang started life as a modified prolog»? — то есть, не «просто взяли синтаксис», а взяли язык и доработали под другую проблематику! Более того, первый компилятор Erlang был написан именно на Prolog-е.
Вообще, ставить под сомнение бывает полезно. Но нужно ли оно лично вам? Каждый решает сам :)
Мало ли чего на заборах пишут. В Prolog есть логическая машина вывода, в Erlang этого и близко нет. Prolog не медленный.Ой, прошу прощения! Я не сразу понял, что разговариваю с носителем Абсолютного и Окончательного Правильного Мнения, а ключевой вопрос у нас — наличие машины вывода… :) Все, больше вопросов не имею.
Так вот на каком языке Deep Thought считал ответ на "Главный вопрос жизни, вселенной и всего такого"!
В лохматом 90 году мной был написан проект АСУТП( управление хим производством на ткацкой фабрике ). Проект был написан на borland turboprolog. Некоторые низкоуровненые куски были написаны на borland turboassembler. Проект был принят, оплачен, и использовался — года 3 точно, потом уже не знаю…
доп:
Автору — а еще есть такой язык SmallTalk. Напишите пожалуйста что нибудь о нем. Очень хороший язык. Делал на нем проект в лохматом 1992-1993 гг. Статистический анализ.
Спасибо.
Изучал в универе, даже собирался внедрить на работе в качестве движка расчета скидок, т.к. они регулируются похожими запутанными правилами.
Но у пролога есть большая проблема — по исходному коду крайне сложно сказать, как именно он будет работать. Из чего следует три проблемы побольше:
- как доработать программу на прологе, чтобы не сломать существующий функционал?
- как обеспечить конечное и разумное время выполнения программы на прологе?
- если программа выдала неверный результат, как найти ошибку?
Вопрос к экспертам Prolog, вдохновлённый примером про magicNumber: какая будет асимптотичекая сложность решения у обобщённой задачи 2-sum?
magicNumber(A[1]).
magicNumber(A[2]).
...
magicNumber(A[N]).
?- magicNumber(X), magicNumber(Y), plus(X, Y, target)Такой же вопрос про 3-sum, 4-sum?
Слышали о языке Prolog?